Posible ba nga makamugna og mga random nga numero kung wala kami pagsalig sa usag usa? Bahin 2

Hoy Habr!

В ang una nga bahin Niini nga artikulo, among gihisgutan kung nganong gikinahanglan ang paghimo og mga random nga numero alang sa mga partisipante nga walay pagsalig sa usag usa, unsa nga mga kinahanglanon ang gibutang sa unahan alang sa maong mga random number generators, ug gikonsiderar ang duha ka pamaagi sa ilang pagpatuman.

Niini nga bahin sa artikulo, atong tan-awon pag-ayo ang lain nga pamaagi nga naggamit sa mga pirma sa threshold.

Usa ka gamay nga cryptography

Aron masabtan kung giunsa paglihok ang mga pirma sa threshold, kinahanglan nimo nga masabtan ang gamay nga sukaranan nga kriptograpiya. Duha ka konsepto ang atong gamiton: scalar, o yanong mga numero, nga atong ipasabot pinaagi sa gagmay nga mga letra (x, y) ug mga punto sa elliptic curve, nga atong itudlo pinaagi sa dagkong mga letra.

Aron masabtan ang mga sukaranan sa mga pirma sa threshold, dili nimo kinahanglan nga masabtan kung giunsa paglihok ang mga elliptic curve, gawas sa pipila ka sukaranang mga butang:

1. Ang mga punto sa usa ka elliptic curve mahimong idugang ug i-multiply sa usa ka scalar (atong ipasabut ang pagpadaghan sa usa ka scalar ingon nga xG, bisan pa ang notasyon Gx kanunay usab nga gigamit sa literatura). Ang resulta sa pagdugang ug pagpadaghan pinaagi sa usa ka scalar usa ka punto sa usa ka elliptic curve.

2. Nahibal-an lamang ang punto G ug ang produkto niini nga adunay scalar xG dili makalkulo x.

Atong gamiton usab ang konsepto sa usa ka polynomial p (x) degrees k-1. Sa partikular, atong gamiton ang mosunod nga kabtangan sa mga polynomial: kung nahibal-an nato ang bili p (x) alang sa bisan unsa k lain-laing mga x (ug wala na kamiy dugang nga impormasyon bahin sa p (x)), mahimo natong kuwentahon p (x) para ni bisan kinsa x.

Kini mao ang makapaikag nga alang sa bisan unsa nga polynomial p (x) ug pipila ka punto sa kurba Gnahibalo sa kahulogan p(x)G alang sa bisan unsa k lainlain nga kahulogan x, mahimo usab natong kuwentahon p(x)G alang sa bisan unsa x.

Igo na kini nga kasayuran aron makutkot ang mga detalye kung giunsa ang mga pirma sa threshold ug kung giunsa kini gamiton aron makamugna ang mga random nga numero.

Random nga numero generator sa mga pirma sa threshold

Ingnon ta n ang mga partisipante gusto nga makamugna og usa ka random nga numero, ug gusto namo nga bisan kinsa nga moapil k adunay igo sa kanila aron makamugna og usa ka numero, apan aron ang mga tig-atake nga nagkontrol k-1 o mas gamay nga mga partisipante dili makatagna o makaimpluwensya sa gidaghanon nga nahimo.

Ibutang ta nga adunay ingon nga polynomial p (x) degrees k-1 unsay nahibaloan sa unang partisipante p (1), ang ikaduha nahibalo p(2), ug uban pa (n-th nahibalo p(n)). Gituohan usab namo nga alang sa pipila ka gitino nang daan nga punto G ang tanan nahibalo p(x)G alang sa tanan nga mga kantidad x. Magtawag mi p(i) "pribado nga sangkap" iika nga partisipante (kay lang iang ika-unom nga partisipante nakaila kaniya), ug p(i)G "publiko nga sangkap" i-th partisipante (kay ang tanan nga partisipante nakaila kaniya). Sa imong nahinumduman, kahibalo p(i)G dili igo aron mapasig-uli p(i).

Paghimo sa ingon nga usa ka polynomial aron nga lamang i-Ang una nga partisipante ug wala’y lain nga nahibal-an ang iyang pribado nga sangkap - kini ang labing komplikado ug makapaikag nga bahin sa protocol, ug among susihon kini sa ubos. Sa pagkakaron, atong hunahunaon nga kita adunay ingon nga polynomial ug ang tanan nga mga partisipante nahibal-an ang ilang mga pribadong sangkap.

Unsaon nato paggamit ang ingon nga polynomial aron makamugna og random nga numero? Sa pagsugod, kinahanglan namon ang pila ka pisi nga wala pa gigamit kaniadto ingon input sa generator. Sa kaso sa usa ka blockchain, ang hash sa katapusang block h usa ka maayong kandidato alang sa ingon nga linya. Himoa nga ang mga partisipante gusto nga maghimo usa ka random nga numero gamit h sama sa liso. Ang mga partisipante unang nakabig h sa usa ka punto sa kurba gamit ang bisan unsang gitakda nga function:

H = scalarToPoint(h)

Unya ang matag partisipante i kalkulado ug gipatik Kumusta = p(i)H, unsa may ilang buhaton kay kabalo sila p(i) ug H. Pagbutyag HDili nako tugutan ang ubang mga partisipante nga ibalik ang pribadong sangkap iika nga partisipante, ug busa ang usa ka set sa pribadong mga sangkap mahimong gamiton gikan sa block ngadto sa block. Busa, ang mahal nga polynomial generation algorithm nga gihulagway sa ubos kinahanglan lamang nga ipatuman kausa.

Kanus-a k ang mga partisipante gi-autopsy Kumusta = p(i)H, ang tanan makakalkula Hx = p(x)H para sa tanan x salamat sa kabtangan sa mga polynomial nga among gihisgutan sa miaging seksyon. Niining higayona, ang tanan nga mga partisipante nagkalkula H0 = p(0)H, ug kini ang resulta nga random nga numero. Palihug timan-i nga walay nahibalo p(0), ug busa ang bugtong paagi sa pagkalkulo p(0)H – kini mao ang interpolation p(x)H, nga mahimo lamang kung k mga mithi p(i)H nailhan. Pag-abli sa bisan unsang gamay nga gidaghanon p(i)H wala maghatag bisan unsang kasayuran bahin sa p(0)H.

Ang generator sa ibabaw adunay tanan nga mga kabtangan nga gusto namon: mga tig-atake nga nagkontrol lamang k-1 ka partisipante o mas ubos walay impormasyon o impluwensya sa konklusyon, samtang bisan unsa k ang mga partisipante makakalkula sa resulta nga numero, ug bisan unsang subset sa k ang mga partisipante kanunay nga moabut sa parehas nga sangputanan alang sa parehas nga liso.

Adunay usa ka problema nga among gilikayan pag-ayo sa ibabaw. Aron molihok ang interpolation, hinungdanon nga ang kantidad Hi nga gimantala sa matag partisipante i parehas ra gyud p(i)H. Kay walay gawas i-th partisipante wala mahibalo p(i), walay lain gawas i-ang partisipante dili makapamatuod niana Hi aktuwal nga kalkulado sa husto, ug walay bisan unsa nga cryptographic nga pamatuod sa pagkahusto Hako ang usa ka tig-atake mahimong magmantala sa bisan unsang kantidad ingon Hi, ug arbitraryong impluwensya sa output sa random number generator:

Ang lain-laing mga kantidad sa H_1 nga gipadala sa unang partisipante mosangpot sa lain-laing resulta H_0

Adunay labing menos duha ka paagi aron mapamatud-an ang pagkahusto Hi, atong tagdon sila human nato analisa ang henerasyon sa polynomial.

Polinomyal nga kaliwatan

Sa katapusan nga seksyon among gihunahuna nga kami adunay ingon nga polynomial p (x) degrees k-1 nga ang partisipante i nahibal-an p(i), ug walay lain nga adunay bisan unsa nga impormasyon mahitungod niini nga bili. Sa sunod nga seksyon kinahanglan usab naton kana alang sa pipila nga gitino nang daan nga punto G ang tanan nahibalo p(x)G para sa tanan x.

Niini nga seksyon atong hunahunaon nga ang matag partisipante sa lokal adunay pipila ka pribado nga yawe xi, sa ingon nga ang tanan nahibalo sa katugbang nga publiko nga yawe Xi.

Usa ka posible nga polynomial generation protocol mao ang mosunod:

1. Ang matag partisipante i lokal nga nagmugna sa usa ka arbitraryong polynomial pi(x) degree k-1. Dayon ipadala nila ang matag partisipante j kahulugan pi(j), gi-encrypt gamit ang public key Xj. Sa ingon lamang i-y и j-y nasayod ang partisipante pako(j). Partisipante i gipahibalo usab sa publiko pi(j)G para sa tanan j gikan sa 1 sa k lakip na.

2. Ang tanan nga mga partisipante naggamit sa pipila ka consensus sa pagpili k mga partisipante kansang mga polynomial gamiton. Tungod kay ang ubang mga partisipante mahimong offline, dili kami makahulat hangtod sa tanan n ang mga partisipante magpatik ug mga polynomial. Ang resulta niini nga lakang usa ka set Z naglangkob sa labing menos k polynomial nga gihimo sa lakang (1).

3. Gisiguro sa mga partisipante nga ang mga mithi nga ilang nahibal-an pi(j) katumbas sa gipahibalo sa publiko pi(j)G. Human niini nga lakang sa Z mga polynomial lamang nga pribado nga gipasa pi(j) katumbas sa gipahibalo sa publiko pi(j)G.

4. Ang matag partisipante j kalkulado ang pribadong bahin niini p(j) isip sum pi(j) para sa tanan i в Z. Ang matag partisipante usab nagkalkula sa tanan nga mga kantidad p(x)G isip sum pi(x)G para sa tanan i в Z.

timan-i nga p(x) - polynomial gyud ni k-1, tungod kay kini ang sumada sa indibidwal pi(x), ang matag usa usa ka polynomial sa degree k-1. Unya, timan-i nga samtang ang matag partisipante j nahibal-an p(j), wala silay impormasyon bahin sa p (x) alang sa x ≠ j. Sa tinuud, aron makalkulo kini nga kantidad, kinahanglan nila mahibal-an ang tanan pi(x), ug basta ang partisipante j wala mahibalo sa labing menos usa sa mga pinili nga polynomials, sila walay igong impormasyon mahitungod sa p(x).

Kini ang tibuuk nga proseso sa henerasyon nga polynomial nga gikinahanglan sa katapusan nga seksyon. Ang mga lakang 1, 2 ug 4 sa ibabaw adunay klaro nga pagpatuman. Apan ang lakang 3 dili kaayo hinungdanon.

Sa piho, kinahanglan naton nga mapamatud-an kana nga naka-encrypt pi(j) katumbas gayod sa mga gipatik pi(j)G. Kung dili nato kini mapamatud-an, ang tig-atake i mahimong magpadala na hinuon og basura pi(j) sa partisipante j, ug partisipante j dili makuha ang tinuod nga kahulogan pi(j), ug dili makalkulo ang pribadong bahin niini.

Adunay usa ka cryptographic protocol nga nagtugot kanimo sa paghimo og dugang nga mensahe pamatuodi(j), sa ingon nga bisan kinsa nga partisipante, adunay pipila ka bili e, а также pamatuod(j) и pi(j)G, makamatuod niana sa lokal e - mao gyud pi(j), gi-encrypt gamit ang yawe sa partisipante j. Ikasubo, ang gidak-on sa ingon nga ebidensya dako kaayo, ug gihatag nga kini kinahanglan nga imantala O(nk) Ang ingon nga ebidensya dili magamit alang niini nga katuyoan.

Imbes pamatud-an kana pi(j) соответствует pi(j)G kita makagahin ug dako kaayong yugto sa panahon sa polynomial generation protocol, diin ang tanang partisipante magsusi sa nadawat nga naka-encrypt pi(j), ug kung ang decrypted nga mensahe dili katumbas sa publiko pi(j)G, nagmantala sila og cryptographic nga pruweba nga ang naka-encrypt nga mensahe nga ilang nadawat dili husto. Pamatud-i nga ang mensahe dili соответствует pi(G) mas sayon ​​kay sa pagpamatuod nga kini motakdo. Kinahanglang hinumdoman nga kini nagkinahanglan sa matag partisipante nga magpakita online labing menos kausa sa panahon nga gigahin sa paghimo sa maong ebidensya, ug nagsalig sa pangagpas nga kon ilang imantala ang maong pruweba, kini makaabot sa tanang ubang mga partisipante sa samang gitagal nga panahon.

Kung ang usa ka partisipante wala magpakita online sa niining yugto sa panahon, ug siya adunay labing menos usa ka sayup nga sangkap, nan kana nga partikular nga partisipante dili na makaapil sa dugang nga henerasyon sa numero. Ang protocol, bisan pa, molihok gihapon kung adunay labing menos k mga partisipante nga bag-o lang nakadawat sa husto nga mga sangkap o nakahimo sa pagbilin og pruweba sa pagkasayop sulod sa gitakdang panahon.

Mga pamatuod sa pagkahusto sa H_i

Ang kataposang bahin nga hisgotan pa mao ang paagi sa pagmatuod sa pagkahusto sa gipatik Hako, sa ato pa Kumusta = p(i)H, walay pag-abli p(i).

Atong hinumduman nga ang mga mithi H, G, p(i)G publiko ug nailhan sa tanan. Pagdawat sa operasyon p(i) nahibalo p(i)G и G gitawag nga discrete logarithm, o dlog, ug gusto namong pamatud-an nga:

dlog(p(i)G, G) = dlog(Hi, H)

walay pagbutyag p(i). Ang mga pagtukod alang sa ingon nga mga pruweba adunay, pananglitan Schnorr Protocol.

Uban niini nga disenyo, ang matag partisipante, uban sa Hi nagpadala ug pamatuod sa pagkahusto sumala sa disenyo.

Sa higayon nga mamugna ang usa ka random nga numero, kasagaran kinahanglan kining gamiton sa mga partisipante gawas sa mga nagmugna niini. Ang maong mga partisipante, uban sa numero, kinahanglan ipadala ang tanan Hi ug may kalabutan nga ebidensya.

Ang usa ka mausisaon nga magbabasa mahimong mangutana: tungod kay ang katapusan nga random nga numero mao ang H0, ug p(0)G – Kini mao ang publiko nga impormasyon, nganong kita nagkinahanglan og pruweba alang sa matag indibidwal Hako, nganong dili ipadala pamatuod nga sa baylo

dlog(p(0)G, G) = dlog(H0, H)

Ang problema mao nga ang ingon nga pruweba dili mahimo gamit ang Schnorr Protocol tungod kay wala’y nahibal-an ang kantidad p (0), gikinahanglan sa paghimo sa pamatuod, ug unsa pa, ang tibuok random nga numero generator gibase sa kamatuoran nga walay usa nga nahibalo niini nga bili. Busa gikinahanglan nga adunay tanan nga mga bili Hi ug ang ilang tagsa-tagsa nga ebidensya aron pamatud-an ang pagkahusto H0.

Bisan pa, kung adunay pipila nga operasyon sa mga punto sa elliptic curves nga parehas sa semantiko sa pagpadaghan, ang pamatuod sa pagkahusto. H0 gamay ra, ato lang sigurohon kana

H0 × G = p(0)G × H

Kung ang gipili nga kurba nagsuporta elliptic curve pairings, kini nga pruweba molihok. Niini nga kaso HAng 0 dili lamang ang output sa usa ka random number generator, nga mahimong mapamatud-an sa bisan kinsa nga partisipante nga nahibal-an G, H и p(0)G. H0 usa usab ka pirma sa mensahe nga gigamit ingon usa ka liso, nga nagpamatuod niana k и n ang mga partisipante mipirma niini nga mensahe. Sa ingon, kung liso - mao ang hash sa block sa blockchain protocol, unya H0 pareho nga multi-signature sa block ug maayo kaayo nga random number.

Sa konklusyon

Kini nga artikulo kabahin sa usa ka teknikal nga serye sa blog DUOL. Ang NEAR usa ka protocol sa blockchain ug plataporma alang sa pagpalambo sa mga desentralisadong aplikasyon nga adunay gibug-aton sa kasayon ​​sa pagpalambo ug kasayon ​​sa paggamit alang sa mga end user.

Ang protocol code bukas, ang among pagpatuman gisulat sa Rust, kini makita dinhi.

Makita nimo kung unsa ang hitsura sa pag-uswag alang sa NEAR ug mag-eksperimento sa online IDE dinhi.

Mahimo nimong sundon ang tanan nga balita sa Russian sa grupo sa telegrama ug sa grupo sa VKontakte, ug sa English sa opisyal twitter.

О скорых встреч!

Source: www.habr.com