Оё имконпазир аст, ки рақамҳои тасодуфиро тавлид кунем, агар мо ба ҳамдигар эътимод накунем? Қисми 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 сония тӯл кашад, пас VDF-и дар чунин ASIC ҳисобшуда бояд зиёда аз 100 сонияро дар бар гирад, то маржаи бехатарии 10x дошта бошад ва ҳамин тавр, ҳамон VDF, ки дар сахтафзори молӣ ҳисоб карда мешавад, бояд 100x 100 сония = ~3 соатро дар бар гирад.

Бунёди Ethereum нақша дорад, ки ин мушкилотро тавассути эҷоди ASIC-ҳои дастраси ройгони худ ҳал кунад. Пас аз он ки ин рӯй медиҳад, ҳама протоколҳои дигар низ метавонанд аз ин технология истифода баранд, аммо то он вақт равиши RANDAO+VDF барои протоколҳое, ки наметавонанд барои таҳияи ASIC-ҳои худ сармоягузорӣ кунанд, қобили кор нахоҳад буд.

Дар бораи VDF бисёр мақолаҳо, видеоҳо ва маълумоти дигар ҷамъ оварда шудаанд ин сайт.

Мо рамзҳои тозакуниро истифода мебарем

Дар ин бахш, мо протоколи тавлиди рақамҳои тасодуфиро дида мебароем, ки онро истифода мебарад тоза кардани кодҳо. Он метавонад то ⅓ ҳамлагаронро таҳаммул карда, дар ҳоле ки қобили ҳаёт боқӣ мемонад ва имкон медиҳад, ки то ⅔ ҳамлагарон пеш аз он ки онҳо пешгӯӣ кунанд ё ба натиҷа таъсир расонанд, вуҷуд дошта бошанд.

Идеяи асосии протокол чунин аст. Барои соддатар, фарз кунем, ки 100 нафар иштирокчиён ҳастанд. Биёед инчунин фарз кунем, ки ҳамаи иштирокчиён ба таври маҳаллӣ як калиди махфӣ доранд ва калидҳои оммавии ҳамаи иштирокчиён ба ҳама иштирокчиён маълуманд:

1. Ҳар як иштирокчӣ ба таври маҳаллӣ бо як сатри дароз мебарояд, онро ба 67 қисм тақсим мекунад, рамзҳои тозакуниро барои ба даст овардани 100 саҳмия эҷод мекунад, ки ҳар як 67 барои барқарор кардани сатр кифоя аст, ҳар як аз 100 саҳмияро ба яке аз иштирокчиён таъин мекунад ва онҳоро бо рамз рамзгузорӣ мекунад. калиди ҷамъиятии ҳамон иштирокчӣ. Ҳама саҳмияҳои рамзгузоришуда баъдан нашр мешаванд.

2. Иштирокчиён як навъ консенсусро барои ба даст овардани созиш дар маҷмӯи рамзгузорӣ аз 67 иштирокчии мушаххас истифода мебаранд.

3. Пас аз ба даст овардани консенсус, ҳар як иштирокчӣ саҳмияҳои рамзгузоришударо дар ҳар як аз 67 маҷмӯи бо калиди оммавии худ рамзкунонидашуда мегирад, ҳамаи ин гуна саҳмияҳоро рамзкушоӣ мекунад ва ҳамаи чунин саҳмияҳои рамзкушошударо нашр мекунад.

4. Пас аз он ки 67 иштирокчӣ қадами (3)-ро анҷом доданд, ҳамаи маҷмӯаҳои мувофиқашуда метавонанд бо сабаби хосиятҳои рамзҳои тозакунӣ пурра рамзкушоӣ ва аз нав барқарор карда шаванд ва рақами ниҳоиро метавон ҳамчун XOR аз сатрҳои ибтидоӣ, ки иштирокчиён дар (1) оғоз карданд, гирифтан мумкин аст. .

Ин протоколро метавон беғаразона ва пешгӯинашаванда нишон дод. Рақами тасодуфии натиҷавӣ пас аз ба даст овардани консенсус муайян карда мешавад, аммо то ⅔ ҳиссаи иштирокчиён қисмҳои бо калиди оммавии худ рамзкунонидашударо рамзкушоӣ накунанд, ба касе маълум нест. Ҳамин тариқ, рақами тасодуфӣ пеш аз нашри маълумоти кофӣ барои барқарорсозии он муайян карда мешавад.

Чӣ мешавад, агар дар қадами (1) яке аз иштирокчиён саҳмияҳои рамзгузориро ба иштирокчиёни дигар фиристад, ки рамзи тозакунии дурусти баъзе сатр нестанд? Бе тағироти иловагӣ, иштирокчиёни гуногун ё умуман сатрро барқарор карда наметавонанд, ё онҳо сатрҳои гуногунро барқарор мекунанд, ки дар натиҷа иштирокчиёни гуногун рақами тасодуфии гуногун мегиранд. Барои пешгирии ин, шумо метавонед амалҳои зеринро иҷро кунед: ҳар як иштирокчӣ, ба ғайр аз саҳмияҳои рамзгузорӣ, инчунин ҳисоб мекунад Дарахти Меркла ҳама чунин саҳмияҳоро мефиристад ва ба ҳар як иштирокчӣ ҳам худи саҳмияи рамзгузоришуда ва ҳам решаи дарахти merkle ва далели дохил кардани саҳмияро ба дарахти merkle мефиристад. Дар тавофуқ дар қадами (2), иштирокчиён на танҳо дар бораи маҷмӯи маҷмӯаҳо, балки дар бораи маҷмӯи решаҳои мушаххаси чунин дарахтҳо мувофиқат мекунанд (агар баъзе иштирокчиён аз протокол дур шуда, решаҳои дарахти меркро ба иштирокчиёни гуногун фиристоданд, ва ду чунин реша ҳангоми консенсус нишон дода шудаанд, сатри ӯ ба маҷмӯи натиҷа дохил карда нашудааст). Дар натиҷаи консенсус, мо 67 хати рамзгузоришуда ва решаҳои мувофиқи дарахти merkle хоҳем дошт, ки ҳадди аққал 67 иштирокчӣ ҳастанд (на ҳатман ҳамон шахсоне, ки сатрҳои мувофиқро пешниҳод кардаанд), ки барои ҳар як аз 67 сатр паём бо ҳиссаи рамзи тозакунӣ ва далели пайдоиши ҳиссаи онҳо дар дарахти мувофиқ пажмурда мешавад.

Вақте ки дар қадами (4) иштирокчӣ 67 зарбаи сатри муайянро дешифратсия мекунад ва кӯшиш мекунад, ки сатри аслиро аз онҳо барқарор кунад, яке аз вариантҳо имконпазир аст:

1. Сатр барқарор карда мешавад ва агар он аз нав тозакунӣ-рамзгузорӣ карда шавад ва дарахти Merkle барои саҳмияҳои ба таври маҳаллӣ ҳисобшуда ҳисоб карда шавад, реша бо оне, ки дар он консенсус ба даст омадааст, мувофиқат мекунад.

2. Сатр барқарор карда мешавад, аммо решаи ба таври маҳаллӣ ҳисобшуда ба решае, ки дар он консенсус ба даст оварда шудааст, мувофиқат намекунад.

3. Сатр барқарор карда нашудааст.

Нишон додан осон аст, ки агар варианти (1) барои ҳадди аққал як иштирокчии боло рух дода бошад, пас варианти (1) барои ҳамаи иштирокчиён рух додааст ва баръакс, агар варианти (2) ё (3) ҳадди аққал барои як иштирокчӣ рух дода бошад, пас барои ҳамаи иштирокчиён варианти (2) ё (3) рӯй медиҳад. Ҳамин тариқ, барои ҳар як сатри маҷмӯи, ё ҳамаи иштирокчиён онро бомуваффақият барқарор мекунанд ё ҳамаи иштирокчиён онро барқарор карда наметавонанд. Рақами тасодуфии натиҷа XOR танҳо сатрҳое мебошад, ки иштирокчиён тавонистанд барқарор кунанд.

Имзоҳои ҳадди аксар

Равиши дигар ба тасодуфӣ истифодаи он чизест, ки имзоҳои ҳадди ақали BLS номида мешаванд. Генератори рақамҳои тасодуфӣ, ки ба имзоҳои ҳадди ақал асос ёфтааст, айнан ҳамон кафолати алгоритми дар асоси коди тозакунӣ дар боло тавсифшударо дорад, аммо шумораи асимптотикии паёмҳои тавассути шабака фиристодашуда барои ҳар як рақами тавлидшуда хеле камтар аст.

Имзои BLS тарҳест, ки ба иштирокчиёни сершумор имкон медиҳад, ки як имзои умумиро барои паём эҷод кунанд. Ин имзоҳо аксар вақт барои сарфа кардани ҷой ва фарохмаҷрои интиқол истифода мешаванд, ки фиристодани имзоҳои сершуморро талаб намекунанд. 

Як барномаи маъмул барои имзоҳои BLS дар протоколҳои blockchain, ба ғайр аз тавлиди рақамҳои тасодуфӣ, имзои блок дар протоколҳои BFT мебошад. Фарз мекунем, ки 100 иштирокчӣ блокҳо эҷод мекунанд ва агар 67 нафари онҳо имзо гузоранд, блок ниҳоӣ ҳисобида мешавад. Ҳамаи онҳо метавонанд қисмҳои имзои BLS-ро пешниҳод кунанд ва аз алгоритми консенсус истифода баранд, то дар бораи 67-тои онҳо мувофиқа кунанд ва сипас онҳоро ба як имзои BLS муттаҳид кунанд. Ҳама гуна 67 (ё бештар) қисмҳоро барои эҷоди имзои ниҳоӣ истифода бурдан мумкин аст, ки аз он вобаста аст, ки 67 имзо якҷоя карда шудаанд ва аз ин рӯ метавонанд фарқ кунанд, гарчанде ки интихоби мухталифи 67 иштирокчӣ имзои дигарро эҷод мекунад, ҳар гуна чунин имзо эътибор дорад. имзо барои блок. Ба иштирокчиёни боқимонда лозим меояд, ки танҳо як имзоро дар як блок ба ҷои 67 тавассути шабака қабул ва тафтиш кунанд, ки сарбории шабакаро ба таври назаррас коҳиш медиҳад.

Маълум мешавад, ки агар калидҳои хусусие, ки иштирокчиён истифода мебаранд, ба таври муайян тавлид шаванд, пас новобаста аз он, ки кадом 67 имзо (ё бештар, вале на камтар) ҷамъ карда мешаванд, имзои натиҷавӣ якхела хоҳад буд. Ин метавонад ҳамчун манбаи тасодуфӣ истифода шавад: иштирокчиён аввал дар бораи баъзе паёмҳо розӣ мешаванд, ки онҳо имзо хоҳанд кард (ин метавонад баромади RANDAO ё танҳо хэши блоки охирин бошад, то он даме ки он ҳар дафъа тағир меёбад, муҳим нест. ва пайваста аст) ва барои он имзои BLS эҷод кунед. Натиҷаи тавлид то он даме, ки 67 иштирокчӣ қисмҳои худро таъмин накунанд, пешгӯинашаванда хоҳад буд ва баъд аз он натиҷа аллакай пешакӣ муайян шудааст ва наметавонад аз амали ягон иштирокчӣ вобаста бошад.

Ин равиш ба тасодуфӣ то он даме, ки ҳадди аққал ⅔ иштирокчиёни онлайн ҳам протоколро риоя мекунанд, қобили ҳаёт аст ва то даме ки ҳадди аққал ⅓ иштирокчиён протоколро риоя кунанд, беғаразона ва пешгӯинашаванда аст. Бояд қайд кард, ки ҳамлакунанда, ки зиёда аз ⅓, вале камтар аз ⅔ иштирокчиёнро назорат мекунад, метавонад протоколро боздорад, аммо наметавонад пешгӯӣ кунад ё ба натиҷаи он таъсир расонад.

Худи имзоҳои остона як мавзӯи хеле ҷолиб аст. Дар қисми дуюми мақола мо ба таври муфассал таҳлил хоҳем кард, ки онҳо чӣ гуна кор мекунанд ва чӣ гуна маҳз тавлид кардани калидҳои иштирокчӣ зарур аст, то имзоҳои ҳадди ақал ҳамчун генератори рақамҳои тасодуфӣ истифода шаванд.

Дар охир

Ин мақола аввалин силсилаи мақолаҳои блоги техникӣ мебошад НАВ. NEAR як протокол ва платформаи blockchain барои таҳияи барномаҳои ғайримарказонидашуда бо таваҷҷӯҳ ба осонии таҳия ва осонии истифода барои корбарони ниҳоӣ мебошад.

Рамзи протокол кушода аст, татбиқи мо дар Rust навишта шудааст, онро ёфтан мумкин аст дар ин ҷо.

Шумо метавонед бубинед, ки таҳияи NEAR чӣ гуна аст ва дар IDE онлайн озмоиш кунед дар ин ҷо.

Шумо метавонед ҳама хабарҳоро бо забони русӣ дар ин ҷо пайгирӣ кунед гурӯҳи телеграмма ва дар гурӯҳ дар ВКонтакте, ва ба забони англисӣ дар расмӣ twitter.

То боз дид!

Манбаъ: will.com