Здравей, Хабр!
В тази статия ще говорим за генериране на псевдослучайни числа от участници, които не си вярват. Както ще видим по-долу, реализацията на "почти" добър генератор е достатъчно проста, но създаването на много добър е сложно.
Защо изобщо е необходимо участниците да генерират случайни числа, когато не си вярват? Една от областите на приложение е децентрализираните приложения. Например, приложение, което приема залог от участник и удвоява сумата с вероятност 49%, или взима 51%, ще работи само ако може безпристрастно да получи случайно число. Ако злоумишникът може да влияе на резултата от работата на генератора на случайни числа и дори незначително да увеличи шанса си да получи плащане в приложението, той лесно ще го опустоши.
Когато разработваме разпределен протокол за генериране на случайни числа, искаме той да притежава три свойства:
Той трябва да бъде безпристрастен. С други думи, нито един участник не трябва по какъвто и да е начин да влияе на резултата от генератора на случайни числа.
Той трябва да бъде непредсказуем. С други думи, нито един участник не трябва да има способността да предскаже кое число ще бъде генерирано (или да извлече каквито и да е негови свойства) преди то да бъде генерирано.
Протоколът трябва да бъде жизнеспособен, тоест устойчив на ситуация, при която някакъв процент от участниците се изключват от мрежата или умишлено се опитват да спрат протокола.
В тази статия ще разгледаме два подхода: 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 планира да разреши този проблем, като създаде собствен публичен безплатен ASIC. След като това се случи, всички останали протоколи също могат да се възползват от тази технология, но дотогава подходът RANDAO + VDF няма да бъде толкова жизнеспособен за протоколите, които не могат да инвестират в разработването на свои собствени ASIC.
Много статии, видеа и друга информация за VDF са събрани на .
Използваме стираещи кодове
В този раздел ще разгледаме протокола за генериране на случайни числа, който използва . Той може да понесе до ⅓ злонамерени участници, оставайки жизнеспособен, и допуска съществуването на до ⅔ злонамерени участници, преди те да могат да предскажат или да повлияят на резултата.
Основната идея на протокола е следната. За опростяване нека предположим, че има точно 100 участника. Нека също така предположим, че всички участници локално имат някакъв частен ключ, а публичните ключове на всички участници са известни на всички участници:
Всеки участник локално измисля дълга низ, разделя я на 67 части, създава стираещи кодове, за да получи 100 дялове, така че всякакви 67 да са достатъчни за възстановяване на низа, назначава всяка от 100-те дялове на един от участниците и ги шифрова с публичния ключ на същия участник. След това всички кодирани дялове се публикуват.
Участниците използват определен консенсус, за да постигнат съгласие относно кодирани набори от конкретни 67 участника.
След като консенсусът е достигнат, всеки участник взема кодирани дялове от всеки от 67-те набори, шифровани с техния публичен ключ, декодира всички такива дялове и публикува всички такива декодирани дялове.
След като 67 участника изпълнят стъпка (3), всички съгласувани набори могат да бъдат напълно декодирани и възстановени благодарение на свойствата на стираещите кодове, а окончателното число може да бъде получено като XOR на началните низове, с които участниците започват в (1).
Може да се покаже, че този протокол е безпристрастен и непредсказуем. Полученото случайно число е определено след постигане на консенсус, но на никого не е известно, докато ⅔ от участниците не декодират частите, криптирани с техния публичен ключ. По този начин, случайното число е определено преди информацията, необходима за неговото възстановяване, да бъде публикувана.
Какво се случва, ако на стъпка (1) един от участниците изпрати на другите участници кодифицирани дялове, които не са валиден стиращ код на някакъв ред? Без допълнителни промени различните участници или няма да могат да възстановят реда изобщо, или ще възстановят различни редове, което ще доведе до това, че различните участници ще получат различно случайно число. За да се предотврати това, може да се направи следното: всеки участник, освен кодифицираните дялове, също изчислява на всички такива дялове и изпраща на всеки участник както самия кодифициран дял, така и корена на мерклевото дърво, както и доказателство за включването на дяла в мерклевото дърво. На консенсуса в стъпка (2) участниците не просто се съгласяват на множество комплекти, но на множество конкретни корени на такива дървета (ако някой участник се отклони от протокола и изпрати различни корени на мерклевото дърво на различни участници, и два такива корена се показват по време на консенсуса, редът му не се включва в резултатния набор). В края на консенсуса ще имаме 67 кодифицирани реда и съответстващите им корени на мерклевото дърво, такива че има поне 67 участници (не непременно същите, които предложиха съответстващите редове), при които за всеки от 67-те реда има съобщение с дял от стиращия код и доказателство за присъединяването на дяла им в съответстващото меркливо дърво.
Когато на стъпка (4) участникът декодира 67 дяла за някакъв ред и опитва да възстанови оригиналния ред, един от вариантите е:
Редът се възстановява и ако след това бъде кодифициран с стиращите кодове отново и се изчисли меркливо дърво за локално изчислените дялове, корена съвпада с този, при който е постигнат консенсус.
Редът се възстановява, но локално изчисленият корен не съответства на този, при който е постигнат консенсус.
Редът не се възстановява.
Лесно е да се покаже, че ако поне за един участник е настъпил вариант (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
