Възможно ли е да генерираме произволни числа, ако нямаме доверие един на друг? Част 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) // это очень быстро

Тази функция се нарича Verifiable Delay Function или 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) участниците след това не просто се споразумяват за набор от набори, а за набор от специфични корени на такива дървета (ако някой участник се отклони от протокола и изпрати различни корени на 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, по мрежата, което значително намалява натоварването на мрежата.

Оказва се, че ако личните ключове, които участниците използват, са генерирани по определен начин, тогава без значение кои 67 подписа (или повече, но не по-малко) са събрани, полученият подпис ще бъде същият. Това може да се използва като източник на произволност: участниците първо се споразумяват за някакво съобщение, което ще подпишат (това може да е резултатът от RANDAO или просто хешът на последния блок, няма особено значение, стига да се променя всеки път и е последователен) и създайте BLS подпис за него. Резултатът от генерирането ще бъде непредсказуем, докато 67 участници не предоставят своите части, а след това изходът вече е предварително определен и не може да зависи от действията на който и да е участник.

Този подход към произволността е жизнеспособен, стига поне ⅔ от участниците онлайн да следват протокола и е безпристрастен и непредсказуем, стига поне XNUMX/XNUMX от участниците да следват протокола. Важно е да се отбележи, че нападател, който контролира повече от ⅓, но по-малко от ⅔ от участниците, може да спре протокола, но не може да предвиди или повлияе на изхода му.

Самите прагови подписи са много интересна тема. Във втората част на статията ще анализираме подробно как работят и как точно е необходимо да се генерират ключове на участници, така че праговите подписи да могат да се използват като генератор на произволни числа.

В заключение

Тази статия е първата от поредица технически статии в блогове NEAR. NEAR е блокчейн протокол и платформа за разработване на децентрализирани приложения с акцент върху лекотата на разработка и лекотата на използване от крайните потребители.

Кодът на протокола е отворен, нашата реализация е написана на Rust, може да бъде намерена тук.

Можете да видите как изглежда разработката за NEAR и да експериментирате в онлайн IDE тук.

Можете да следите всички новини на руски език на телеграм група и група във VKontakte, а на английски в официалния кикотене.

Ще се видим скоро!

Източник: www.habr.com