Ці можна генераваць выпадковыя лікі, калі мы не давяраем адзін аднаму? Частка 1

Прывітанне, Хабр!

У гэтым артыкуле я раскажу пра генерацыю псеўда-выпадковых лікаў удзельнікамі, якія не давяраюць адзін аднаму. Як мы ўбачым ніжэй, рэалізаваць "амаль" добры генератар досыць проста, а вось вельмі добры - складана.

Навошта наогул трэба генераваць выпадковыя лікі ўдзельнікам, якія не давяраюць адзін аднаму? Адна з абласцей прымянення - гэта дэцэнтралізаваныя прыкладанні. Напрыклад, дадатак, якое прымае стаўку ад удзельніка і альбо падвойвае суму з верагоднасцю 49%, альбо забірае з 51%, будзе працаваць толькі калі яно можа непрадузята атрымаць выпадковы лік. Калі зламыснік можа паўплываць на вынік працы генератара выпадковых лікаў, і нават нязначна павялічыць свой шанец атрымаць выплату ў дадатку, ён лёгка спустошыць яго.

Калі мы распрацоўваем размеркаваны пратакол генерацыі выпадковых лікаў, мы жадаем, каб ён валодаў трыма ўласцівасцямі:

1. Ён павінен быць непрадузятым. Іншымі словамі, ніводны ўдзельнік не павінен якой-небудзь выявай уплываць на вынік генератара выпадковых лікаў.

2. Ён павінен быць непрадказальным. Іншымі словамі, ніводны ўдзельнік не павінен мець магчымасць прадбачыць, які лік будзе згенеравана (ці вывесці якія-небудзь яго ўласцівасці) да таго, як яно будзе згенеравана.

3. Пратакол павінен быць жыццяздольным, гэта значыць устойлівым да таго, што нейкі працэнт удзельнікаў адключацца ад сеткі ці наўмысна паспрабуюць спыніць пратакол.

У гэтым артыкуле мы разгледзім два падыходы: RANDAO + VDF і падыход, заснаваны на сціраючых кодах. У наступнай частцы мы падрабязна разбяром падыход, заснаваны на парогавых подпісах.

Але для пачатку давайце разбяром просты і часта выкарыстоўваны алгарытм, які жыццяздольны, непрадказальны, але прадузяты.

RANDAO

RANDAO - гэта вельмі просты і, такім чынам, даволі часта выкарыстоўваецца падыход да атрымання выпадковасці. Усе ўдзельнікі сеткі спачатку лакальна выбіраюць псеўдавыпадковы лік, затым кожны ўдзельнік дасылае хэш абранага ліку. Далей удзельнікі па чарзе выкрываюць свае абраныя лікі, і выконваюць над выкрытымі лікамі аперацыю XOR, а вынік гэтай аперацыі і становіцца вынікам працы пратакола.

Крок з публікацыяй хэшаў перш чым выкрываць лікі неабходзен, каб зламыснік не мог абраць свой лік пасля таго, як ён убачыў лікі астатніх удзельнікаў. Гэта дазволіла б яму фактычна аднаасобна вызначыць выснову генератара выпадковых лікаў.

Па ходзе пратакола ўдзельнікам трэба двойчы прыйсці да агульнага рашэння (т.зв. кансенсусу): калі пачаць выкрываць абраныя лікі, і такім чынам спыніць прымаць хешы, і калі завяршыць прымаць абраныя лікі і вылічыць выніковы выпадковы лік. Прыняцце такіх рашэнняў паміж удзельнікамі, якія адзін аднаму не давяраюць, само па сабе няпростая задача, і мы вернемся да яе ў будучых артыкулах, у гэтым артыкуле мы будзем меркаваць, што такі алгарытм кансенсусу нам даступны.

Якія з уласцівасцяў, якія мы апісалі вышэй, ёсць у RANDAO? Ён непрадказальны, мае тую ж жыццяздольнасць, што і які ляжыць у яго аснове пратакол кансенсусу, але ён з'яўляецца прадузятым. У прыватнасці, зламыснік можа назіраць за сеткай, і пасля таго, як іншыя ўдзельнікі раскрыюць свае лікі, ён можа вылічыць іх XOR, і вырашыць, раскрываць ці не раскрываць свой лік, каб паўплываць на вынік. У той час як гэта не дазваляе зламысніку аднаасобна вызначыць выснову генератара выпадковых лікаў, гэта ўсё яшчэ дае яму 1 біт уплыву. А калі зламыснікі кіруюць некалькімі ўдзельнікамі, тая колькасць кантраляваных імі бітаў будзе роўна колькасці ўдзельнікаў пад іх кіраваннем.

Уплыў зламыснікаў можна моцна паменшыць, калі патрабаваць, што ўдзельнікі выкрываюць лікі па-парадку. Тады зламыснік зможа паўплываць на зыход толькі калі ён выкрываецца апошнім. У той час як уплыў значна менш, алгарытм усё яшчэ з'яўляецца прадузятым.

RANDAO + VDF

Адзін з варыянтаў, як зрабіць RANDAO непрадузятым, складаецца ў наступным: пасля таго, як усе лікі выкрытыя, і XOR палічаны, яго вынік падаецца на ўваход функцыі, якая займае вельмі шмат часу, каб яе вылічыць, але дазваляе праверыць правільнасць вылічэнні вельмі хутка.

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

Такая функцыя завецца Verifiable Delay Function, ці VDF. Калі вылічэнне канчатковага выніку займае больш часу, чым этап раскрыцця лікаў, то зламыснік не зможа прадказаць эфект ад дэманстрацыі ці утойвання свайго ліку, а такім чынам ён страціць магчымасць уплываць на вынік.

Распрацоўка добрых VDF надзвычай складана. У апошні час было зроблена некалькі прарываў, напрыклад гэты и гэты, якія зрабілі VDF больш дастасавальнымі на практыцы, і Ethereum 2.0 у доўгатэрміновай перспектыве плануе выкарыстоўваць RANDAO з VDF у якасці крыніцы выпадковых лікаў. Акрамя таго факту, што гэты падыход непрадказальны і непрадузяты, у яго ёсць дадатковая перавага, якая заключаецца ў жыццяздольнасці, калі хаця б два ўдзельнікі даступныя ў сетцы (пры ўмове, што выкарыстоўваецца пратакол кансенсусу жыццяздольны пры працы з такой невялікай колькасцю ўдзельнікаў).

Самая вялікая складанасць гэтага падыходу складаецца ў такой наладзе VDF, каб нават удзельнік з вельмі дарагім спецыялізаваным абсталяваннем не змог вылічыць VDF да канчатка фазы расчынення. У ідэале алгарытм павінен мець нават значны запас трываласці, скажам, 10x. На малюнку ніжэй паказана атака ўдзельніка, які мае спецыялізаваны ASIC, які дазваляе яму запускаць VDF хутчэй, чым час, наадварот для расчынення пацверджання RANDAO. Такі ўдзельнік можа па-ранейшаму вылічаць канчатковы вынік выкарыстоўваючы і не выкарыстоўваючы свой лік, і пасля гэтага, на аснове разлікаў, выбіраць, паказваць яго ці не.

Для згаданага вышэй сямейства VDF прадукцыйнасць спецыялізаванага ASIC можа быць у 100+ разоў вышэй, чым у звычайнага абсталявання. Такім чынам, калі фаза расчынення доўжыцца 10 секунд, то VDF, вылічаная на такі ASIC, павінна займаць больш 100 секунд, каб мець 10-кратны запас бяспекі, і, такім чынам, той жа VDF, вылічаны на звычайным абсталяванні, павінен заняць 100 x 100 секунд = ~ 3 гадзіны.

Ethereum Foundation плануе вырашыць гэтую праблему за рахунак стварэння ўласных агульнадаступных бясплатных ASIC. Як толькі гэта адбудзецца, усе іншыя пратаколы таксама могуць выкарыстоўваць перавагі гэтай тэхналогіі, але датуль падыход RANDAO + VDF не будзе гэтак жа жыццяздольным для пратаколаў, якія не могуць інвеставаць у распрацоўку сваіх уласных ASIC.

Шмат артыкулаў, відэа і іншай інфармацыі аб VDF сабрана на гэтым сайце.

Выкарыстоўваны сціраючыя коды

У гэтым раздзеле мы разгледзім пратакол генерацыі выпадковых лікаў, які выкарыстоўвае сціраючыя коды. Ён можа вытрываць да ⅓ зламыснікаў, застаючыся жыццяздольным, і дапускае існаванне да ⅔ зламыснікаў, перш чым яны змогуць прадказаць або паўплываць на вынік.

Асноўная ідэя пратакола заключаецца ў наступным. Для прастаты выкажам здагадку, што ў ім роўна 100 удзельнікаў. Дапушчальны таксама што ва ўсіх удзельнікаў лакальна ёсць некаторы прыватны ключ, і публічныя ключы ўсіх удзельнікаў вядомыя ўсім удзельнікам:

1. Кожны ўдзельнік лакальна прыдумляе доўгі радок, разбівае яго на 67 частак, стварае сціраючыя коды для атрымання 100 доляй, такіх, што любых 67 дастаткова для аднаўлення радка, прызначае кожную з 100 доляй аднаму з удзельнікаў і шыфруе іх з дапамогай адкрытага ключа таго ж удзельніка. Затым усе закадаваныя долі публікуюцца.

2. Удзельнікі выкарыстоўваюць некаторы кансэнсус, каб дасягнуць згоды аб закадаваных наборах ад канкрэтных 67 удзельнікаў.

3. Як толькі кансэнсус дасягнуты, кожны ўдзельнік бярэ закадаваныя долі ў кожным з 67 набораў, зашыфраваныя іх адкрытым ключом, расшыфроўвае ўсе такія долі і публікуе ўсе такія расшыфраваныя долі.

4. Як толькі 67 удзельнікаў выканалі крок (3), усе ўзгодненыя наборы могуць быць цалкам дэкадаваны і адноўлены дзякуючы ўласцівасцямі сціраючых кодаў, і канчатковы лік можа быць атрымана як XOR пачатковых радкоў, з якіх удзельнікі пачалі ў (1).

Можна паказаць, што гэты пратакол непрадузяты і непрадказальны. Выніковы выпадковы лік вызначаны пасля дасягнення кансэнсусу, але нікому не вядома да таго часу, пакуль ⅔ удзельнікаў не дэкадуюць часткі, зашыфраваныя іх адкрытым ключом. Такім чынам, выпадковы лік вызначаны раней, чым інфармацыя, дастатковая для яго аднаўлення, апублікавана.

Што адбываецца, калі на кроку (1) адзін з удзельнікаў адправіў іншым удзельнікам закадаваныя долі, якія не з'яўляюцца карэктным сціраючым кодам некаторага радка? Без дадатковых змен розныя ўдзельнікі альбо не змогуць аднавіць радок зусім, альбо адновяць розныя радкі, што прывядзе да таго, што розныя ўдзельнікі атрымаюць розны выпадковы лік. Каб гэта прадухіліць, можна зрабіць наступнае: кожны ўдзельнік, акрамя закадаваных доляй, вылічае таксама дрэва меркла усіх такіх дзеляў, і кожнаму ўдзельніку пасылае як саму закадаваную дзель, так і корань дрэва меркла, і доказ уключэння дзелі ў дрэва меркла. У кансэнсусе на кроку (2) затым удзельнікі не проста згаджаюцца на мностве набораў, але на мностве канкрэтных каранёў такіх дрэў (калі некаторы ўдзельнік адышоў ад пратакола, і адправіў розныя карані дрэва меркла розным удзельнікам, і два такіх кораня паказаны падчас кансенсусу, яго радок не ўключаецца ў выніковы набор). Па выніку кансенсусу мы будзем мець 67 закадаваных радкоў і адпаведных ім каранёў дрэва меркла такіх, што ёсць хаця б 67 удзельнікаў (не абавязкова тых жа хто прапанавалі адпаведныя радкі), у якіх для кожнага з 67 радкоў ёсць паведамленне з доляй сціральнага кода, і доказ уваходжання іх долі ў адпаведнае дрэва меркла.

Калі на кроку (4) удзельнік расшыфроўвае 67 доляй для некаторага радка, і спрабуе па іх аднавіць арыгінальны радок, магчымы адзін з варыянтаў:

1. Радок аднаўляецца, і калі яе затым закадаваць сціраючымі кодамі зноў, і палічыць дрэва меркла для палічаных лакальна доляй, корань супадае з тым, на якім дасягнуты кансэнсус.

2. Радок аднаўляецца, але палічаны лакальна корань не адпавядае таму, на якім дасягнуты кансэнсус.

3. Радок не аднаўляецца.

Лёгка паказаць, што калі хаця б для аднаго ўдзельніка вышэй здарыўся варыянт (1), то для ўсіх удзельнікаў здарыцца варыянт (1), і наадварот, калі хаця б для аднаго ўдзельніка здарыўся варыянт (2) або (3), то для ўсіх удзельнікаў. здарыцца варыянт (2) ці (3). Такім чынам, для кожнага радка ў наборы або ўсе ўдзельнікі паспяхова яго адновяць, або ўсе ўдзельнікі не змогуць яго аднавіць. Затым выніковы выпадковы лік - гэта XOR толькі тых радкоў, якія ўдзельнікі змаглі аднавіць.

Парогавыя подпісы

Іншы падыход да выпадковасці заключаецца ў выкарыстанні так званых парогавых подпісаў BLS. Генератар выпадковых лікаў, заснаваны на парогавых подпісах, мае сапраўды такія ж гарантыі, як і апісаны вышэй алгарытм на аснове сціраючых кодаў, але мае значна меншую асімптатыку колькасці паведамленняў, якія перасылаюцца па сетцы на кожны згенераваны лік.

Подпісы BLS – гэта канструкцыя, якая дазваляе некалькім удзельнікам ствараць адзін агульны подпіс для паведамлення. Такія подпісы часта выкарыстоўваюцца для эканоміі месца і прапускной здольнасці за кошт таго, што не патрабуе рассылання некалькіх подпісаў. 

Частае ўжыванне для BLS-подпісаў у пратаколах блокчейна, акрамя генерацыі выпадковых лікаў, - гэта падпісванне блокаў у пратаколах BFT. Скажам, 100 удзельнікаў ствараюць блокі, і блок лічыцца канчатковым, калі 67 з іх падпісваюць яго. Усе яны могуць прадставіць свае часткі BLS-подпісы і выкарыстоўваць некаторы кансэнсус-алгарытм, каб узгадніць 67 з іх, а затым аб'яднаць іх у адну BLS-подпіс. Любыя 67 (ці больш) частак могуць быць скарыстаны для стварэння выніковага подпісу, які будзе залежаць ад таго, якія менавіта 67 подпісаў былі аб'яднаныя, і таму можа адрознівацца, але не гледзячы на ​​тое, што розны выбар 67-мі ўдзельнікаў будзе ствараць розны подпіс. , любы такі подпіс будзе карэктным подпісам для блока. Астатнім удзельнікам затым дастаткова атрымаць па сетцы і праверыць толькі адзін подпіс на кожны блок, замест 67, што прыкметна паніжае нагрузку на сетку.

Аказваецца, што калі закрытыя ключы, якія выкарыстоўваюць удзельнікі, генеруюцца пэўным чынам, то незалежна ад таго, якія 67 подпісаў (ці больш, але ніяк не менш) агрэгаваныя, подпіс, які атрымліваецца ў выніку, будзе аднолькавым. Гэта можа быць выкарыстана ў якасці крыніцы выпадковасці: удзельнікі спачатку дамаўляюцца аб некаторым паведамленні, якое яны падпішуць (гэта можа быць выснова RANDAO ці проста хэш апошняга блока, насамрэч гэта не мае значэння, абы яно кожны раз мянялася і было ўзгодненым), і ствараюць для яго BLS-подпіс. Вынік генерацыі будзе непрадказальным, пакуль 67 удзельнікаў не дадуць свае часткі, а пасля гэтага выходныя дадзеныя ўжо наканаваныя і не могуць залежаць ад дзеянняў любога ўдзельніка.

Такі падыход да выпадковасці жыццяздольны, калі хаця б ⅔ удзельнікаў анлайн і ідуць пратаколу, і непрадузяты і непрадказальны пакуль хаця б ⅓ удзельнікаў ідуць пратаколу. Важна звярнуць увагу, што зламыснік, які кантралюе больш за ⅓ але менш чым ⅔ удзельнікаў можа спыніць пратакол, але не можа прадказаць ці паўплываць на яго выснову.

Парогавыя подпісы самі па сабе - вельмі цікавая тэма. У другой частцы артыкула мы дэталёва разбяром як яны працуюць, і як менавіта неабходна генераваць ключы ўдзельнікаў, каб парогавыя подпісы можна было выкарыстоўваць як генератар выпадковых лікаў.

У заключэнне

Гэты артыкул - першы ў серыі тэхнічных артыкулаў у блогу БЛЯЗЕ. NEAR - гэта блокчейн пратакол і платформа для распрацоўкі дэцэнтралізаваных прыкладанняў з акцэнтам на прастату распрацоўкі, і прастату выкарыстання для канчатковых карыстальнікаў.

Код пратакола адкрыты, наша рэалізацыя напісана на Rust, яе можна знайсці тут.

Паглядзець як выглядае распрацоўка пад NEAR, і паэксперыментаваць у анлайн-IDE можна тут.

Сачыць за ўсімі навінамі на рускай можна ў групе ў тэлеграме і ў групе на Укантакце, а на англійскай у афіцыйным твітэры.

Да хуткіх сустрэч!

Крыніца: habr.com