Հնարավո՞ր է պատահական թվեր ստեղծել, եթե մենք միմյանց չվստահենք: Մաս 2

Հե՜յ Հաբր։

В առաջին մասը Այս հոդվածում մենք քննարկեցինք, թե ինչու կարող է անհրաժեշտ լինել պատահական թվեր ստեղծել միմյանց չվստահող մասնակիցների համար, ինչ պահանջներ են առաջադրվում նման պատահական թվերի գեներատորների համար և դիտարկեցինք դրանց իրականացման երկու մոտեցում:

Հոդվածի այս մասում մենք ավելի մանրամասն կանդրադառնանք մեկ այլ մոտեցմանը, որն օգտագործում է շեմային ստորագրությունները:

Մի քիչ գաղտնագրություն

Որպեսզի հասկանաք, թե ինչպես են գործում շեմային ստորագրությունները, դուք պետք է հասկանաք մի փոքր հիմնական ծածկագրությունը: Մենք կօգտագործենք երկու հասկացություն՝ սկալերներ կամ պարզապես թվեր, որոնք կնշանակենք փոքրատառերով (x, y) և էլիպսային կորի կետերը, որոնք կնշանակենք մեծատառերով։

Շեմային ստորագրությունների հիմունքները հասկանալու համար ձեզ հարկավոր չէ հասկանալ, թե ինչպես են աշխատում էլիպսային կորերը, բացի մի քանի հիմնական բաներից.

1. Էլիպսային կորի կետերը կարող են գումարվել և բազմապատկվել սկալյարով (մենք կնշանակենք սկալյարով բազմապատկումը որպես xG, չնայած նշումը Gx հաճախ օգտագործվում է նաև գրականության մեջ): Սկալյարով գումարման և բազմապատկման արդյունքը էլիպսային կորի կետն է:

2. Իմանալով միայն կետը G և դրա արտադրանքը սկալարի հետ xG չի կարող հաշվարկվել x.

Կօգտագործենք նաև բազմանդամ հասկացությունը p(x) աստիճան k-1. Մասնավորապես, կօգտագործենք բազմանդամների հետևյալ հատկությունը՝ եթե իմանանք արժեքը p(x) ցանկացածի համար k տարբեր x (և մենք այլ տեղեկություն չունենք p(x)), կարող ենք հաշվարկել p(x) ուրիշի համար x.

Հետաքրքիր է, որ ցանկացած բազմանդամի համար p(x) և ինչ-որ կետ կորի վրա Gիմանալով իմաստը p(x)G ցանկացածի համար k տարբեր իմաստներ x, կարող ենք նաև հաշվարկել p(x)G ցանկացածի համար x.

Սա բավական տեղեկատվություն է՝ մանրամասնելու համար, թե ինչպես են գործում շեմային ստորագրությունները և ինչպես օգտագործել դրանք պատահական թվեր ստեղծելու համար:

Պատահական թվերի գեներատոր շեմային ստորագրությունների վրա

Ասենք, որ n մասնակիցները ցանկանում են ստեղծել պատահական թիվ, և մենք ցանկանում ենք, որ որևէ մեկը մասնակցի k նրանց թիվը բավական էր՝ թվեր առաջացնելու համար, բայց այնպես, որ հարձակվողները, ովքեր վերահսկում են k-1 կամ ավելի քիչ մասնակիցներ չկարողացան կանխատեսել կամ ազդել ստեղծված թվի վրա:

Ենթադրենք, կա նման բազմանդամ p(x) աստիճան k-1 այն, ինչ գիտի առաջին մասնակիցը p (1), երկրորդը գիտի p(2), և այլն (n- գիտի p(n)) Մենք նաև ենթադրում ենք, որ որոշ կանխորոշված ​​կետի համար G բոլորը գիտեն p(x)G բոլոր արժեքների համար x. Մենք կզանգենք p(i) «մասնավոր բաղադրիչ» i-րդ մասնակիցը (որովհետև միայն iերրորդ մասնակիցը ճանաչում է նրան), և խոզ «հասարակական բաղադրիչ» i-րդ մասնակիցը (քանի որ բոլոր մասնակիցները ճանաչում են նրան): Ինչպես հիշում եք՝ գիտելիք խոզ բավարար չէ վերականգնելու համար p(i).

Ստեղծելով այնպիսի բազմանդամ, որ միայն i-Առաջին մասնակիցը և ոչ ոք չգիտեր նրա անձնական բաղադրիչը. սա արձանագրության ամենաբարդ և հետաքրքիր մասն է, և մենք այն կվերլուծենք ստորև: Առայժմ ենթադրենք, որ մենք ունենք նման բազմանդամ, և բոլոր մասնակիցները գիտեն դրանց մասնավոր բաղադրիչները:

Ինչպե՞ս կարող ենք օգտագործել նման բազմանդամը պատահական թիվ առաջացնելու համար: Սկսելու համար մեզ անհրաժեշտ է որոշակի տող, որը նախկինում չի օգտագործվել որպես գեներատորի մուտքագրում: Բլոկչեյնի դեպքում՝ վերջին բլոկի հեշը h լավ թեկնածու է նման գծի համար։ Թույլ տվեք մասնակիցներին ցանկանալ ստեղծել պատահական թիվ՝ օգտագործելով h սերմի նման: Մասնակիցները առաջին հերթին փոխակերպվում են h դեպի կորի մի կետ՝ օգտագործելով ցանկացած նախապես սահմանված ֆունկցիա.

H = scalarToPoint(h)

Այնուհետև յուրաքանչյուր մասնակից i հաշվարկում և հրապարակում է Hi = p(i)H, ինչ կարող են անել, որովհետև գիտեն p(i) և H. Բացահայտում Hես այլ մասնակիցներին թույլ չեմ տալիս վերականգնել մասնավոր բաղադրիչը iրդ մասնակիցը, և, հետևաբար, մասնավոր բաղադրիչների մեկ հավաքածու կարող է օգտագործվել բլոկից բլոկ: Այսպիսով, ստորև նկարագրված թանկարժեք բազմանդամների առաջացման ալգորիթմը պետք է գործարկվի միայն մեկ անգամ:

Երբ k մասնակիցներին դիահերձել են Hi = p(i)H, բոլորը կարող են հաշվարկել Hx = = p(x)H բոլորի համար x շնորհիվ բազմանդամների հատկության, որը մենք քննարկեցինք վերջին բաժնում: Այս պահին բոլոր մասնակիցները հաշվարկում են H0 = p(0)H, և սա ստացված պատահական թիվն է: Խնդրում ենք նկատի ունենալ, որ ոչ ոք չգիտի p(0), և հետևաբար հաշվարկելու միակ միջոցը p(0)H – սա ինտերպոլացիա է p(x)H, ինչը հնարավոր է միայն այն ժամանակ, երբ k արժեքներ p(i)H հայտնի է. Ցանկացած ավելի փոքր քանակի բացում p(i)H մասին որևէ տեղեկություն չի տրամադրում p(0)H.

Վերևում գտնվող գեներատորն ունի մեր ուզած բոլոր հատկությունները. միայն հարձակվողները վերահսկում են k-1 կամ ավելի քիչ մասնակիցներ չունեն տեղեկատվություն կամ ազդեցություն եզրակացության վրա, մինչդեռ որևէ մեկը k մասնակիցները կարող են հաշվարկել ստացված թիվը և դրանց ցանկացած ենթաբազմություն k մասնակիցները միշտ նույն արդյունքի կհասնեն նույն սերմի համար:

Կա մեկ խնդիր, որից մենք զգուշորեն խուսափեցինք վերևում. Որպեսզի ինտերպոլացիան աշխատի, կարևոր է, որ արժեքը Hi որը հրապարակվել է յուրաքանչյուր մասնակցի կողմից i դա իսկապես նույնն էր p(i)H. Քանի որ ոչ ոք բացի i-րդ մասնակիցը չգիտի p(i), ոչ ոք բացի i-մասնակիցը չի կարող դա հաստատել Hi իրականում ճիշտ հաշվարկված և առանց ճշտության որևէ գաղտնագրային ապացույցի Hես հարձակվողը կարող է հրապարակել ցանկացած արժեք որպես Ողջու՜յն, և կամայականորեն ազդել պատահական թվերի գեներատորի արդյունքի վրա:

Առաջին մասնակցի կողմից ուղարկված H_1-ի տարբեր արժեքները հանգեցնում են տարբեր արդյունքների՝ H_0

Կոռեկտությունն ապացուցելու առնվազն երկու եղանակ կա Hi, մենք դրանք կդիտարկենք բազմանդամի առաջացումը վերլուծելուց հետո:

Բազմանդամ սերունդ

Վերջին բաժնում մենք ենթադրեցինք, որ ունենք նման բազմանդամ p(x) աստիճան k-1 որ մասնակիցը i գիտի p(i), և ոչ ոք որևէ տեղեկություն չունի այս արժեքի մասին։ Հաջորդ բաժնում դա մեզ նույնպես պետք կգա որոշ կանխորոշված ​​կետի համար G բոլորը գիտեին p(x)G բոլորի համար x.

Այս բաժնում մենք կենթադրենք, որ տեղական յուրաքանչյուր մասնակից ունի որոշակի մասնավոր բանալի xi, այնպես, որ բոլորն իմանան համապատասխան հանրային բանալին Xi.

Հնարավոր բազմանդամների առաջացման արձանագրությունը հետևյալն է.

1. Յուրաքանչյուր մասնակից i լոկալ կերպով ստեղծում է կամայական բազմանդամ pi(x) աստիճան k-1. Նրանք այնուհետև ուղարկում են յուրաքանչյուր մասնակցի j արժեք pi(j), կոդավորված հանրային բանալիով Xj. Այսպիսով միայն i-հ и j-հ մասնակիցը գիտի pi(j). Մասնակից i նաև հրապարակայնորեն հայտարարում է պի(ժ)Գ բոլորի համար j - ից 1 դեպի k ներառական։

2. Բոլոր մասնակիցներն ընտրելու համար օգտագործում են որոշակի կոնսենսուս k մասնակիցներ, որոնց բազմանդամները կօգտագործվեն: Քանի որ որոշ մասնակիցներ կարող են անցանց լինել, մենք չենք կարող սպասել մինչև բոլորը n մասնակիցները կհրապարակեն բազմանդամներ: Այս քայլի արդյունքը մի շարք է Z բաղկացած առնվազն k (1) քայլում ստեղծված բազմանդամներ.

3. Մասնակիցները համոզվում են, որ իրենց իմացած արժեքները pi(j) համապատասխանում է հրապարակայնորեն հայտարարվածին պի(ժ)Գ. Այս քայլից հետո Z միայն բազմանդամներ, որոնց համար մասնավոր կերպով փոխանցվում են pi(j) համապատասխանում է հրապարակայնորեն հայտարարվածին պի(ժ)Գ.

4. Յուրաքանչյուր մասնակից j հաշվարկում է իր մասնավոր բաղադրիչը p(j) որպես գումար pi(j) բոլորի համար i в Z. Յուրաքանչյուր մասնակից նաև հաշվարկում է բոլոր արժեքները p(x)G որպես գումար pi(x)G բոլոր i в Z.

Խնդրում ենք նկատի ունենալ, որ p(x) – դա իսկապես բազմանդամ է k-1, քանի որ դա անհատի գումարն է pi(x), որոնցից յուրաքանչյուրը աստիճանի բազմանդամ է k-1. Այնուհետեւ, նշեք, որ մինչ յուրաքանչյուր մասնակից j գիտի p(j), մասին տեղեկություն չունեն p(x) համար x ≠ ժ. Իսկապես, այս արժեքը հաշվարկելու համար նրանք պետք է ամեն ինչ իմանան pi (x), եւ քանի դեռ մասնակիցը j չգիտի ընտրված բազմանդամներից գոնե մեկը, նրանք բավարար տեղեկություններ չունեն դրա մասին p(x):

Սա բազմանդամների առաջացման ամբողջ գործընթացն է, որն անհրաժեշտ էր վերջին բաժնում: Վերոնշյալ 1-ին, 2-րդ և 4-րդ քայլերն ունեն բավականին ակնհայտ իրականացում: Բայց 3-րդ քայլն այնքան էլ տրիվիալ չէ:

Մասնավորապես, մենք պետք է կարողանանք ապացուցել, որ կոդավորված է pi(j) իսկապես համապատասխանում է հրապարակվածներին պի(ժ)Գ. Եթե ​​մենք չկարողանանք դա ապացուցել, հարձակվողը i փոխարենը կարող է աղբ ուղարկել pi(j) մասնակցին j, և մասնակից j չի կարողանա ստանալ իրական իմաստը pi (j), և չի կարողանա հաշվարկել դրա մասնավոր բաղադրիչը.

Կա գաղտնագրման արձանագրություն, որը թույլ է տալիս ստեղծել լրացուցիչ հաղորդագրություն ապացույցi(j), այնպիսին, որ ցանկացած մասնակից, որն ունի որոշակի արժեք e, ինչպես նաեւ ապացույց (ժ) и pi(j)G, կարող է տեղական կերպով հաստատել դա e - իսկապես այդպես է pi (j), կոդավորված է մասնակցի բանալիով j. Ցավոք, նման ապացույցների չափերը աներևակայելի մեծ են, և հաշվի առնելով, որ անհրաժեշտ է հրապարակել O(nk) Նման ապացույցները չեն կարող օգտագործվել այդ նպատակով:

Դա ապացուցելու փոխարեն pi(j) համապատասխանում pi(j)G մենք կարող ենք շատ երկար ժամանակ հատկացնել բազմանդամների առաջացման արձանագրությանը, որի ընթացքում բոլոր մասնակիցները ստուգում են ստացված կոդավորվածը pi (j), և եթե վերծանված հաղորդագրությունը չի համապատասխանում հանրությանը pi(j)G, նրանք հրապարակում են ծածկագրային ապացույց, որ իրենց ստացած գաղտնագրված հաղորդագրությունը սխալ է: Ապացուցեք, որ ուղերձը ոչ համապատասխանում խոզ) շատ ավելի հեշտ է, քան ապացուցել, որ այն համապատասխանում է: Հարկ է նշել, որ սա պահանջում է, որ յուրաքանչյուր մասնակից հայտնվի առցանց առնվազն մեկ անգամ՝ նման ապացույցներ ստեղծելու համար հատկացված ժամանակի ընթացքում, և հիմնվում է այն ենթադրության վրա, որ եթե նրանք հրապարակեն նման ապացույց, այն կհասնի մյուս բոլոր մասնակիցներին նույն հատկացված ժամանակում։

Եթե ​​տվյալ ժամանակահատվածում մասնակիցը չի հայտնվել առցանց, և նա ունեցել է առնվազն մեկ սխալ բաղադրիչ, ապա այդ կոնկրետ մասնակիցը չի կարողանա մասնակցել հետագա թվերի ստեղծմանը: Արձանագրությունը, սակայն, դեռ կգործի, եթե գոնե լինի k մասնակիցներ, ովքեր կա՛մ պարզապես ստացել են ճիշտ բաղադրիչները, կա՛մ կարողացել են տրամադրված ժամանակում թողնել սխալի ապացույցը:

H_i-ի ճիշտության ապացույցներ

Վերջին մասը, որը մնում է քննարկել, այն է, թե ինչպես կարելի է ապացուցել հրապարակվածի ճիշտությունը Hես, մասնավորապես դա Hi = p(i)H, առանց բացելու p(i).

Հիշենք, որ արժեքները H, G, p(i)G հանրային և բոլորին հայտնի։ Ստանալ վիրահատություն p(i) իմանալով խոզ и G կոչվում է դիսկրետ լոգարիթմ, կամ dlog, և մենք ուզում ենք ապացուցել, որ.

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

առանց բացահայտման p(i). Նման ապացույցների կոնստրուկցիաներ կան, օրինակ Schnorr արձանագրություն.

Այս դիզայնով, յուրաքանչյուր մասնակից, հետ միասին Hi ուղարկում է կոռեկտության ապացույց՝ ըստ դիզայնի:

Երբ պատահական թիվը ստեղծվում է, այն հաճախ անհրաժեշտ է օգտագործել այլ մասնակիցների կողմից, բացի նրանցից, ովքեր ստեղծել են այն: Նման մասնակիցները համարի հետ միասին պետք է ուղարկեն բոլորին Hi և հարակից ապացույցներ:

Հետաքրքրասեր ընթերցողը կարող է հարցնել. քանի որ վերջնական պատահական թիվն է H0, և p(0)G – Սա հանրային տեղեկատվություն է, ինչի համար է մեզ անհրաժեշտ յուրաքանչյուր անհատի ապացույց Hես, ինչու դրա փոխարեն ապացույց չուղարկեմ

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

Խնդիրն այն է, որ նման ապացույց չի կարող ստեղծվել Schnorr արձանագրության միջոցով, քանի որ ոչ ոք չգիտի դրա արժեքը p (0), որը անհրաժեշտ է ապացույցը ստեղծելու համար, և ավելին, ամբողջ պատահական թվերի գեներատորը հիմնված է այն փաստի վրա, որ ոչ ոք չգիտի այս արժեքը: Ուստի անհրաժեշտ է ունենալ բոլոր արժեքները Hi և դրանց անհատական ​​ապացույցները՝ ապացուցելու ճիշտությունը H0.

Այնուամենայնիվ, եթե էլիպսային կորերի կետերի վրա ինչ-որ գործողություն է եղել, որը իմաստային առումով նման է բազմապատկմանը, ապա կոռեկտության ապացույցը. H0 աննշան կլիներ, մենք պարզապես կհամոզվեինք դրանում

H0 × G = p(0)G × H

Եթե ​​ընտրված կորը աջակցում է էլիպսային կորի զուգավորումներ, այս ապացույցն աշխատում է։ Այս դեպքում H0-ը ոչ միայն պատահական թվերի գեներատորի ելքն է, որը կարող է ստուգել ցանկացած մասնակից, ով գիտի Գ, Հ и p(0)G. Հ0-ը նաև ստորագրություն է հաղորդագրության վրա, որն օգտագործվել է որպես սերմ, որը հաստատում է դա k и n մասնակիցները ստորագրել են այս հաղորդագրությունը։ Այսպիսով, եթե սերմ - բլոկի հեշն է բլոկչեյն արձանագրության մեջ, ապա H0 դա և՛ բազմաստորագրություն է բլոկի վրա, և՛ շատ լավ պատահական թիվ:

Վերջում

Այս հոդվածը տեխնիկական բլոգի շարքի մի մասն է NEAR. NEAR-ը բլոկչեյն արձանագրություն և հարթակ է ապակենտրոնացված հավելվածների մշակման համար՝ շեշտը դնելով վերջնական օգտագործողների համար մշակման և օգտագործման հեշտության վրա:

Արձանագրության կոդը բաց է, մեր իրականացումը գրված է Rust-ով, այն կարելի է գտնել այստեղ.

Դուք կարող եք տեսնել, թե ինչ տեսք ունի NEAR-ի զարգացումը և փորձարկել առցանց IDE-ում այստեղ.

Բոլոր նորություններին կարող եք հետևել ռուսերեն հետևյալ հասցեով հեռագրային խումբ իսկ խումբ VKontakte-ում, իսկ անգլերեն՝ պաշտոնական թվիթեր.

Տեսնու՞մ եք շուտով:

Source: www.habr.com