Дали е можно да се генерираат случајни броеви ако не си веруваме? Дел 1

Еј Хабр!

Во оваа статија ќе зборувам за генерирање на псевдо-случајни броеви од учесници кои не си веруваат едни на други. Како што ќе видиме подолу, имплементирањето на „речиси“ добар генератор е прилично едноставно, но многу добар е тешко.

Зошто би било неопходно да се генерираат случајни броеви меѓу учесниците кои не си веруваат? Една област на примена се децентрализираните апликации. На пример, апликација која прифаќа облог од учесник и или го удвојува износот со 49% веројатност или одзема со веројатност од 51%, ќе работи само ако може непристрасно да добие случаен број. Ако напаѓачот може да влијае на исходот на генератор на случаен број, па дури и малку да ја зголеми својата шанса да добие исплата во апликацијата, тој лесно ќе ја уништи.

Кога дизајнираме протокол за генерирање на дистрибуиран случаен број, сакаме тој да има три својства:

1. Тој мора да биде непристрасен. Со други зборови, ниту еден учесник не треба на кој било начин да влијае на резултатот од генератор на случаен број.

2. Тој мора да биде непредвидлив. Со други зборови, ниту еден учесник не треба да може да предвиди кој број ќе се генерира (или да заклучи некоја од неговите својства) пред да се генерира.

3. Протоколот мора да биде остварлив, односно отпорен на фактот дека одреден процент од учесниците се исклучуваат од мрежата или намерно се обидуваат да го запрат протоколот.

Во оваа статија ќе разгледаме два пристапа: RANDAO + VDF и пристапот на кодови за бришење. Во следниот дел, детално ќе го испитаме пристапот заснован на праговите потписи.

Но, прво, да погледнеме едноставен и најчесто користен алгоритам кој е остварлив, непредвидлив, но пристрасен.

РАНДАО

RANDAO е многу едноставен и затоа доста често користен пристап за генерирање на случајност. Сите учесници во мрежата прво локално избираат псевдослучаен број, а потоа секој учесник испраќа хаш од избраниот број. Следно, учесниците наизменично ги откриваат нивните избрани броеви и вршат операција XOR на откриените броеви, а резултатот од оваа операција станува резултат на протоколот.

Чекорот на објавување на хашовите пред откривање на броевите е неопходен за напаѓачот да не може да го избере својот број откако ќе ги види броевите на другите учесници. Ова ќе му овозможи практично сам да го одреди излезот од генераторот на случаен број.

Во текот на протоколот, учесниците треба двапати да дојдат до заедничка одлука (т.н. консензус): кога да почнат да ги откриваат избраните броеви и затоа да престанат да прифаќаат хашови и кога да престанат да ги прифаќаат избраните броеви и да го пресметуваат резултатот по случаен избор број. Донесувањето такви одлуки меѓу учесниците кои не си веруваат еден на друг не е лесна задача сама по себе и ќе се навратиме на тоа во идни написи; во оваа статија ќе претпоставиме дека ни е достапен таков алгоритам за консензус.

Кое од својствата што ги опишавме погоре го има RANDAO? Тој е непредвидлив, ја има истата виталност како основниот протокол за консензус, но е пристрасен. Поточно, напаѓачот може да ја набљудува мрежата и откако другите учесници ќе ги откријат своите броеви, тој може да го пресмета нивниот XOR и да одлучи дали да го открие својот број или не за да влијае на исходот. Иако ова го спречува напаѓачот сам да го одреди излезот од генераторот на случаен број, сепак му дава 1 бит влијание. И ако напаѓачите контролираат неколку учесници, тогаш бројот на битови што тие ги контролираат ќе биде еднаков на бројот на учесници под нивна контрола.

Влијанието на напаѓачите може значително да се намали ако се бара од учесниците да ги откријат бројките по редослед. Тогаш напаѓачот ќе може да влијае на исходот само ако се отвори последен. Иако влијанието е значително помало, алгоритмот сè уште е пристрасен.

РАНДАО+ВДФ

Еден начин да се направи 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 пресметан на хардвер за стоки мора да потрае 100 x 100 секунди = ~ 3 часа.

Фондацијата Ethereum планира да го реши овој проблем со создавање на свои јавно достапни, бесплатни 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 тука.

Можете да ги следите сите вести на руски на телеграма група и група на VKontakte, и на англиски јазик во службеното твитер.

Се гледаме наскоро!

Извор: www.habr.com