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

Հե՜յ Հաբր։

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

Ինչո՞ւ պետք է պատահական թվեր ստեղծվեն միմյանց չվստահող մասնակիցների միջև: Կիրառական ոլորտը ապակենտրոնացված հավելվածներն են: Օրինակ, հավելվածը, որն ընդունում է խաղադրույքը մասնակցից և կամ կրկնապատկում է գումարը 49% հավանականությամբ, կամ վերցնում է 51% հավանականությամբ, կաշխատի միայն այն դեպքում, եթե այն կարող է անաչառ կերպով ստանալ պատահական թիվ: Եթե ​​հարձակվողը կարող է ազդել պատահական թվերի գեներատորի արդյունքի վրա և նույնիսկ մի փոքր մեծացնել հավելվածում վճարում ստանալու իր հնարավորությունը, նա հեշտությամբ կկործանի այն:

Երբ մենք նախագծում ենք բաշխված պատահական թվերի ստեղծման արձանագրություն, մենք ցանկանում ենք, որ այն ունենա երեք հատկություն.

1. Նա պետք է լինի անաչառ: Այլ կերպ ասած, ոչ մի մասնակից չպետք է որևէ կերպ ազդի պատահական թվերի ստեղծման արդյունքի վրա։

2. Նա պետք է անկանխատեսելի լինի։ Այլ կերպ ասած, ոչ մի մասնակից չպետք է կարողանա գուշակել, թե ինչ թիվ կստեղծվի (կամ եզրակացնի դրա հատկություններից որևէ մեկը), նախքան դրա գեներացումը:

3. Արձանագրությունը պետք է լինի կենսունակ, այսինքն՝ դիմացկուն այն փաստին, որ մասնակիցների որոշակի տոկոսը անջատվում է ցանցից կամ միտումնավոր փորձում է դադարեցնել արձանագրությունը։

Այս հոդվածում մենք կդիտարկենք երկու մոտեցում՝ RANDAO + VDF և ջնջման կոդերի մոտեցում: Հաջորդ մասում մանրամասն կուսումնասիրենք շեմային ստորագրությունների վրա հիմնված մոտեցումը։

Բայց նախ, եկեք նայենք պարզ և սովորաբար օգտագործվող ալգորիթմին, որը կենսունակ է, անկանխատեսելի, բայց կողմնակալ:

ՌԱՆԴԱՈ

RANDAO-ն շատ պարզ և, հետևաբար, բավականին հաճախ օգտագործվող մոտեցում է պատահականություն առաջացնելու համար: Ցանցի բոլոր մասնակիցները սկզբում տեղական ընտրում են կեղծ պատահական համար, այնուհետև յուրաքանչյուր մասնակից ուղարկում է ընտրված համարի հեշը: Այնուհետև մասնակիցները հերթով բացահայտում են իրենց ընտրած համարները և կատարում են XOR գործողություն բացահայտված թվերի վրա, և այս գործողության արդյունքը դառնում է արձանագրության արդյունք։

Թվերը բացահայտելուց առաջ հեշերը հրապարակելու քայլն անհրաժեշտ է, որպեսզի հարձակվողը չկարողանա ընտրել իր համարը մյուս մասնակիցների համարները տեսնելուց հետո։ Սա թույլ կտա նրան գործնականում միայնակ որոշել պատահական թվերի գեներատորի ելքը:

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

Վերևում նկարագրված հատկություններից ո՞րն ունի RANDAO-ն: Այն անկանխատեսելի է, ունի նույն կենսունակությունը, ինչ հիմքում ընկած կոնսենսուսային արձանագրությունը, բայց կողմնակալ է: Մասնավորապես, հարձակվողը կարող է դիտարկել ցանցը և այն բանից հետո, երբ մյուս մասնակիցները բացահայտեն իրենց համարները, նա կարող է հաշվարկել իրենց XOR-ը և որոշել՝ բացահայտել իր համարը, թե ոչ՝ արդյունքի վրա ազդելու համար: Թեև դա խանգարում է հարձակվողին ինքնուրույն որոշել պատահական թվերի գեներատորի ելքը, այնուամենայնիվ, դա նրան տալիս է 1 բիթ ազդեցություն: Եվ եթե հարձակվողները վերահսկում են մի քանի մասնակիցների, ապա նրանց կողմից վերահսկվող բիթերի քանակը հավասար կլինի նրանց վերահսկողության տակ գտնվող մասնակիցների թվին:

Հարձակվողների ազդեցությունը կարող է զգալիորեն կրճատվել՝ մասնակիցներից պահանջելով նշել թվերը հերթականությամբ: Այդ դեպքում հարձակվողը կկարողանա ազդել արդյունքի վրա միայն այն դեպքում, եթե այն բացվի վերջինը: Թեև ազդեցությունը զգալիորեն պակաս է, ալգորիթմը դեռ կողմնակալ է:

RANDAO+VDF

RANDAO-ն անկողմնակալ դարձնելու եղանակներից մեկն այսպիսին է. բոլոր թվերը բացահայտվելուց և XOR-ը հաշվարկվելուց հետո դրա արդյունքը սնվում է ֆունկցիայի մուտքագրման մեջ, որը շատ երկար ժամանակ է պահանջում հաշվարկելու համար, բայց թույլ է տալիս ստուգել դրա ճիշտությունը: շատ արագ հաշվարկ.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Այս ֆունկցիան կոչվում է Ստուգելի հետաձգման ֆունկցիա կամ VDF: Եթե ​​վերջնական արդյունքի հաշվարկն ավելի երկար տևի, քան թվերի բացահայտման փուլը, ապա հարձակվողը չի կարողանա կանխատեսել իր համարը ցուցադրելու կամ թաքցնելու էֆեկտը, և հետևաբար նա կկորցնի արդյունքի վրա ազդելու հնարավորությունը։

Լավ VDF-ների մշակումը չափազանց դժվար է: Վերջերս մի քանի բեկում է եղել, օրինակ. այս и սա, ինչը VDF-ն ավելի գործնական դարձրեց գործնականում, և Ethereum 2.0-ը պլանավորում է երկարաժամկետ հեռանկարում օգտագործել RANDAO-ն VDF-ի հետ որպես պատահական թվերի աղբյուր: Բացի այն, որ այս մոտեցումն անկանխատեսելի է և անկողմնակալ, այն ունի կենսունակ լինելու հավելյալ առավելությունը, եթե ցանցում առկա են առնվազն երկու մասնակից (ենթադրելով, որ օգտագործված կոնսենսուսային արձանագրությունը կենսունակ է, երբ գործ ունենք մասնակիցների այդքան փոքր թվի հետ):

Այս մոտեցման ամենամեծ մարտահրավերը VDF-ի ստեղծումն է այնպես, որ նույնիսկ շատ թանկ մասնագիտացված սարքավորում ունեցող մասնակիցը չի կարողանա հաշվարկել VDF-ն մինչև հայտնաբերման փուլի ավարտը: Իդեալում, ալգորիթմը նույնիսկ պետք է ունենա անվտանգության զգալի մարժան, ասենք 10x: Ստորև բերված նկարը ցույց է տալիս մի դերասանի հարձակումը, որն ունի մասնագիտացված ASIC, որը թույլ է տալիս նրան VDF-ն ավելի արագ վարել, քան RANDAO-ի հաստատումը բացահայտելու համար հատկացված ժամանակը: Նման մասնակիցը դեռ կարող է վերջնական արդյունքը հաշվարկել՝ օգտագործելով կամ չօգտագործելով իր համարը, իսկ հետո հաշվարկի հիման վրա ընտրել՝ ցույց տալ, թե ոչ։

Վերը նշված VDF ընտանիքի համար հատուկ ASIC-ի կատարումը կարող է 100+ անգամ ավելի բարձր լինել, քան սովորական սարքաշարը: Այսպիսով, եթե տեղակայման փուլը տևում է 10 վայրկյան, ապա նման ASIC-ի վրա հաշվարկված VDF-ին պետք է տևի ավելի քան 100 վայրկյան, որպեսզի ունենա 10x անվտանգության մարժան, և, հետևաբար, ապրանքային սարքավորումների վրա հաշվարկված նույն VDF-ին պետք է տևի 100x100 վայրկյան = ~ 3 ժամ:

Ethereum հիմնադրամը նախատեսում է լուծել այս խնդիրը՝ ստեղծելով իր հանրությանը հասանելի, անվճար ASIC-ները: Երբ դա տեղի ունենա, բոլոր մյուս արձանագրությունները նույնպես կարող են օգտվել այս տեխնոլոգիայից, բայց մինչ այդ RANDAO+VDF մոտեցումը այնքան էլ կենսունակ չի լինի արձանագրությունների համար, որոնք չեն կարող ներդրումներ կատարել սեփական ASIC-ների մշակման մեջ:

VDF-ի մասին շատ հոդվածներ, տեսանյութեր և այլ տեղեկություններ են հավաքվել այս կայքը.

Մենք օգտագործում ենք ջնջման կոդեր

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

Արձանագրության հիմնական գաղափարը հետևյալն է. Պարզության համար ենթադրենք, որ կա ուղիղ 100 մասնակից։ Ենթադրենք նաև, որ տեղական բոլոր մասնակիցներն ունեն որոշ մասնավոր բանալի, և բոլոր մասնակիցների հանրային բանալիները հայտնի են բոլոր մասնակիցներին.

1. Տեղական յուրաքանչյուր մասնակից հանդես է գալիս երկար տողով, այն բաժանում է 67 մասի, ստեղծում է ջնջման կոդեր՝ 100 բաժնետոմս ստանալու համար, այնպես որ ցանկացած 67-ը բավարար է տողը վերականգնելու համար, 100 բաժնետոմսերից յուրաքանչյուրը վերագրում է մասնակիցներից մեկին և գաղտնագրում դրանք նույն մասնակցի հանրային բանալին: Այնուհետև հրապարակվում են բոլոր կոդավորված բաժնետոմսերը:

2. Մասնակիցները օգտագործում են որոշակի կոնսենսուս՝ կոնկրետ 67 մասնակիցների կոդավորված հավաքածուների վերաբերյալ համաձայնության հասնելու համար:

3. Կոնսենսուսի հասնելուց հետո յուրաքանչյուր մասնակից վերցնում է կոդավորված բաժնետոմսերը 67 հավաքածուներից յուրաքանչյուրում, որոնք գաղտնագրված են իրենց հանրային բանալիով, վերծանում է բոլոր այդպիսի բաժնետոմսերը և հրապարակում բոլոր այդպիսի ապակոդավորված բաժնետոմսերը:

4. Երբ 67 մասնակից ավարտեն քայլը (3), բոլոր համաձայնեցված հավաքածուները կարող են ամբողջությամբ վերծանվել և վերակառուցվել՝ շնորհիվ ջնջման կոդերի հատկությունների, և վերջնական թիվը կարող է ստացվել որպես սկզբնական տողերի XOR, որոնցով մասնակիցները սկսել են (1): .

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

Ի՞նչ կլինի, եթե (1) քայլում մասնակիցներից մեկը մյուս մասնակիցներին ուղարկի կոդավորված բաժնետոմսեր, որոնք որոշ տողի համար ճիշտ ջնջման կոդը չեն: Առանց լրացուցիչ փոփոխությունների, տարբեր մասնակիցներ կամ ընդհանրապես չեն կարողանա վերականգնել տողը, կամ նրանք կվերականգնեն տարբեր տողեր, ինչը կհանգեցնի նրան, որ տարբեր մասնակիցներ կստանան այլ պատահական համար: Դա կանխելու համար կարող եք անել հետևյալը՝ յուրաքանչյուր մասնակից, բացի կոդավորված բաժնետոմսերից, նաև հաշվարկում է. Մերկլայի ծառ բոլոր այդպիսի բաժնետոմսերը, և յուրաքանչյուր մասնակցի ուղարկում է և՛ կոդավորված մասնաբաժինը, և՛ մերկլի ծառի արմատը, և՛ մերկլի ծառի մեջ մասնաբաժնի ներառման ապացույցը: Քայլ (2) կոնսենսուսի համաձայն, մասնակիցներն այնուհետև համաձայնում են ոչ միայն մի շարք խմբերի, այլ այդպիսի ծառերի որոշակի արմատների (եթե որոշ մասնակից շեղվել է արձանագրությունից և ուղարկել տարբեր merkle ծառերի արմատներ տարբեր մասնակիցների, և երկու այդպիսի արմատներ ցուցադրվում են կոնսենսուսի ժամանակ, նրա շարքը ներառված չէ արդյունքների հավաքածուում): Կոնսենսուսի արդյունքում մենք կունենանք 67 կոդավորված տողեր և մերկլի ծառի համապատասխան արմատներ, որպեսզի լինեն առնվազն 67 մասնակից (պարտադիր չէ, որ նույն նրանք, ովքեր առաջարկել են համապատասխան տողերը), ովքեր ունեն 67 տողերից յուրաքանչյուրի համար։ ջնջման կոդի մասնաբաժինով հաղորդագրություն և համապատասխան ծառի մեջ դրանց մասնաբաժնի հայտնվելու ապացույցը խունացած է:

Երբ (4) քայլում մասնակիցը վերծանում է 67 հարված որոշակի լարայինի համար և փորձում է դրանցից վերակառուցել սկզբնական լարը, հնարավոր է տարբերակներից մեկը.

1. Տողը վերականգնվում է, և եթե այն նորից ջնջվում է, և Merkle ծառը հաշվարկվում է տեղական հաշվարկված բաժնետոմսերի համար, արմատը համընկնում է այն մեկի հետ, որի շուրջ համաձայնություն է ձեռք բերվել:

2. Շարքը վերականգնված է, սակայն տեղական հաշվարկված արմատը չի համընկնում այն ​​արմատին, որի ժամանակ ձեռք է բերվել համաձայնություն:

3. Շարքը չի վերականգնվել։

Հեշտ է ցույց տալ, որ եթե տարբերակը (1) տեղի է ունեցել վերը նշված առնվազն մեկ մասնակցի համար, ապա տարբերակը (1) տեղի է ունեցել բոլոր մասնակիցների համար, և հակառակը, եթե (2) կամ (3) տարբերակը եղել է առնվազն մեկ մասնակցի համար, ապա բոլոր մասնակիցների համար տեղի կունենա տարբերակ (2) կամ (3): Այսպիսով, հավաքածուի յուրաքանչյուր տողի համար կա՛մ բոլոր մասնակիցները հաջողությամբ կվերականգնեն այն, կա՛մ բոլոր մասնակիցները չեն կարողանա վերականգնել այն: Արդյունքում ստացված պատահական համարն այնուհետև XOR է միայն այն տողերի, որոնք մասնակիցները կարողացել են վերականգնել:

Շեմային ստորագրություններ

Պատահականության մեկ այլ մոտեցում է օգտագործել այն, ինչ կոչվում է BLS շեմային ստորագրություններ: Պատահական թվերի գեներատորը, որը հիմնված է շեմային ստորագրությունների վրա, ունի ճիշտ նույն երաշխիքները, ինչ վերը նկարագրված ջնջման կոդերի վրա հիմնված ալգորիթմը, բայց յուրաքանչյուր գեներացված թվի համար ունի ցանցով ուղարկված հաղորդագրությունների էապես ավելի ցածր ասիմպտոտիկ քանակ:

BLS ստորագրությունները դիզայն են, որը թույլ է տալիս մի քանի մասնակիցների ստեղծել մեկ ընդհանուր ստորագրություն հաղորդագրության համար: Այս ստորագրությունները հաճախ օգտագործվում են տարածք և թողունակություն խնայելու համար՝ չպահանջելով ուղարկել բազմաթիվ ստորագրություններ: 

Բլոկչեյն արձանագրություններում BLS ստորագրությունների ընդհանուր կիրառումը, պատահական թվեր ստեղծելուց բացի, BFT արձանագրություններում արգելափակման ստորագրումն է: Ենթադրենք, 100 մասնակից է ստեղծում բլոկներ, և բլոկը համարվում է վերջնական, եթե ստորագրում է 67-ը: Նրանք բոլորը կարող են ներկայացնել BLS ստորագրության իրենց մասերը և օգտագործել որոշակի համաձայնության ալգորիթմ՝ համաձայնեցնելու դրանցից 67-ը, այնուհետև դրանք միավորել մեկ BLS ստորագրության մեջ: Ցանկացած 67 (կամ ավելի) մասեր կարող են օգտագործվել վերջնական ստորագրության ստեղծման համար, որը կախված կլինի նրանից, թե որ ստորագրությունն է համակցվել և, հետևաբար, կարող է տարբեր լինել, չնայած 67 մասնակիցների տարբեր ընտրությունը կստեղծի այլ ստորագրություն, ցանկացած նման ստորագրություն վավեր կլինի: ստորագրություն բլոկի համար: Մնացած մասնակիցներն այնուհետև պետք է ստանան և ստուգեն միայն մեկ ստորագրություն մեկ բլոկի փոխարեն, 67-ի փոխարեն, ցանցի միջոցով, ինչը զգալիորեն նվազեցնում է ցանցի բեռը:

Ստացվում է, որ եթե մասնավոր բանալիները, որոնք օգտագործում են մասնակիցները, գեներացվել են որոշակի ձևով, ապա անկախ նրանից, թե որ 67 ստորագրությունը (կամ ավելի, բայց ոչ պակաս) է հավաքվում, ստացված ստորագրությունը կլինի նույնը: Սա կարող է օգտագործվել որպես պատահականության աղբյուր. մասնակիցները նախ համաձայնում են ինչ-որ հաղորդագրության շուրջ, որը կստորագրեն (սա կարող է լինել RANDAO-ի արդյունքը կամ պարզապես վերջին բլոկի հեշը, իրականում կարևոր չէ, քանի դեռ այն ամեն անգամ փոխվում է: և հետևողական է) և դրա համար ստեղծել BLS ստորագրություն: Սերնդի արդյունքն անկանխատեսելի կլինի այնքան ժամանակ, քանի դեռ 67 մասնակից չեն տրամադրել իրենց մասերը, իսկ դրանից հետո արդյունքն արդեն կանխորոշված ​​է և չի կարող կախված լինել որևէ մասնակցի գործողություններից։

Պատահականության այս մոտեցումը կենսունակ է այնքան ժամանակ, քանի դեռ առցանց մասնակիցներից առնվազն ⅔-ը հետևում է արձանագրությանը, և անաչառ և անկանխատեսելի է, քանի դեռ մասնակիցներից առնվազն XNUMX-ը հետևում է արձանագրությանը: Կարևոր է նշել, որ հարձակվողը, որը վերահսկում է մասնակիցների ⅓-ից ավելին, բայց ավելի քիչ, քան ⅔-ը, կարող է դադարեցնել արձանագրությունը, բայց չի կարող կանխատեսել կամ ազդել դրա արդյունքի վրա:

Շեմային ստորագրություններն ինքնին շատ հետաքրքիր թեմա են։ Հոդվածի երկրորդ մասում մենք մանրամասն կվերլուծենք, թե ինչպես են դրանք աշխատում և ինչպես է անհրաժեշտ գեներացնել մասնակիցների ստեղները, որպեսզի շեմային ստորագրությունները օգտագործվեն որպես պատահական թվերի գեներատոր:

Վերջում

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

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

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

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

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

Source: www.habr.com