Въведение
„Генерирането на случайни числа е твърде важно, за да бъде оставено на случайността“
Робърт Кавью, 1970
Тази статия е посветена на практическото приложение на решения, използващи колективно генериране на случайни числа в недоверена среда. Накратко — как и за какво се използва случайността в блокчейните и малко за това как да се различи „добрият“ рандом от „лошия“. Генерирането на истински случайно число е изключително сложен проблем дори на един единствен компютър, и отдавна е тема на изучаване от криптографите. А в децентрализираните мрежи генерирането на случайни числа е още по-сложно и важно.
Особено в мрежи, където участниците не се доверяват помежду си, способността да се генерира неоспоримо случайно число позволява ефективно решаване на множество важни задачи и значително подобрява съществуващите схеми. Всъщност хазартните игри и лотарии не са цел номер едно, каквато може да изглежда на неопитния читател.
Генериране на случайни числа
Компютрите не могат сами да генерират случайни числа, за това им е необходима помощ отвън. Компютърът може да получи случайна стойност, използвайки например движения на мишката, количеството използвана памет, паразитни токове по контактите на процесора и множество други източници, наречени източници на ентропия. Самите тези стойности не са напълно случайни, тъй като се намират в определен диапазон или показват предсказуем характер на измененията. За да се превърнат тези числа в действително случайно число в зададен диапазон, се прилагат криптографски преобразования, за да могат неравномерно разпределените стойности на източника на ентропия да се превърнат в равномерно разпределени псевдослучайни стойности. Получените стойности се наричат псевдослучайни, тъй като не са истински случайни, а детерминистично произведени от ентропия. Всеки добър криптоалгоритъм, шифровайки данни, произвежда шифротекстове, които статистически трябва да са неразличими от случайна последователност, така че за генериране на случайние стойности може да се вземе източник на ентропия, който осигурява само добра неповторимост и непредсказуемост на стойностите дори в малки диапазони; останалата част от работата по разсейването и разбъркването на битовете в крайното значение ще поеме алгоритъмът за шифриране.
За да обобщим краткото си лекции, ще добавя, че генерирането на случайни числа дори на едно устройство е един от стълбовете на осигуряване на сигурността на нашите данни. Сгенерираните псевдослучайни числа се използват при установяване на защитени връзки в различни мрежи, за генериране на криптографски ключове, за натоварване, контрол на целостта и още за множество приложения. Сигурността на много протоколи зависи от способността да се генерира надежден, непредсказуем извъншен рандом, да се запази и да не се разкрие до следващата стъпка на протокола, в противен случай сигурността би била поставена под заплаха. Атаката срещу генератора на псевдослучайни стойности е изключително опасна и поставя под заплаха цял софтуер, използващ генерирането на случайни стойности.
Всичко това трябва да знаете, ако сте преминали основен курс по криптография, затова ще продължим с децентрализираните мрежи.
Случайност в блокчейните
На първо място ще говоря за блокчейни с поддръжка на смарт-контракти, именно те могат напълно да използват възможностите, предоставени от качествена и неоспорима случайност. По-надолу, за краткост, ще наричам тази технология “Обществено Проверяеми Случайни Маяци” или ОПСМ. Тъй като блокчейните са мрежи, информацията в които може да бъде проверена от всеки участник, ключова част от името е “Обществено Проверяемо”, т.е. всеки желаещ може с помощта на изчисления да получи доказателство, че полученото число, публикувано в блокчейна, притежава следните свойства:
- Резултатът трябва да има доказуемо равномерно разпределение, т.е. да се основава на доказуемо устойчива криптография.
- Невъзможно е да се контролира нито един от битовете на резултата. Следователно, резултатът не може да бъде предварително предсказан.
- Не може да се саботира протокола за генериране чрез неучастие в протокола или чрез пренасищане на мрежата с атакуващи съобщения.
- Всичко изброено трябва да бъде устойчиво на сговор на допустим брой нечестни участници в протокола (например 1/3 от участниците).
Всяка възможност за сговаряне на малка група участници да произведат контролирана четна/нечетна случайност е дупка в сигурността. Всяка възможност за група да спре генерирането на случайност е дупка в сигурността. Общо казано, проблемите са много и тази задача не е от лесните…
Изглежда, че най-важното приложение за ОПСМ са различни игри, лотарии и по принцип всякакви видове хазарт на блокчейна. Наистина, това е важно направление, но случайността в блокчейните има и по-важни приложения. Нека ги разгледаме.
Алгоритми на консенсуса
PVRB за организиране на мрежов консенсус играе огромна роля. Транзакциите в блокчейните са защитени с електронен подпис, следователно "атака върху транзакция" е винаги включване/изключване на транзакция в блок (или в няколко блока). Основната задача на алгоритъма за консенсус е да се споразумее относно реда на тези транзакции и реда на блоковете, които включват тези транзакции. Освен това, необходимо свойство за реалните блокчейни е финалността — възможността на мрежата да се договори, че веригата до финализирания блок е окончателна и никога няма да бъде изключена поради появата на нов форк. Обикновено, за да се договорим, че блокът е валиден и, най-важното, финален, е необходимо да се съберат подписи от мнозинството производители на блокове (нататък BP — block-producers), което изисква най-малко да се достави веригата от блокове на всички BP и да се разпространят подписите между всички BP. С нарастването на броя на BP, количеството необходими съобщения в мрежата експоненциално нараства, затова, алгоритмите за консенсус, изискващи финалност, използвани например в pBFT консенсуса на Hyperledger, не работят с необходимата скорост, започвайки още от няколко десетки BP, изисквайки огромен брой връзки.
Ако в мрежата има неоспорим и честен PVRB, то дори в най-простия случай, може на неговата основа да се избере един от блок производителите и да му се назначи "лидер" в продължение на един рунд от протокола. Ако имаме N блок производители, от които M: M > 1/2 N са честни, не цензурират транзакции и не изграждат форкове на веригата с цел провеждане на атака "двойно похарчване", то използването на равномерно разпределен неоспорим PVRB ще позволи да се избере честен лидер с вероятност M / N (M / N > 1/2). Ако на всеки лидер се назначи собственен времеви интервал, в който може да създаде блок и да валидира веригата, и тези интервали са равни по време, то веригата от блокове на честните BP ще бъде по-дълга от веригата, формирана от злонамерени BP, и алгоритъмът на консенсус, основан на дължината на веригата, просто ще отхвърли “лошата”. Този принцип за разпределяне на равни времеви квоти на всеки BP за пръв път беше приложен в Graphene (предшественика на EOS) и позволява на повечето блокове да се затварят с един подпис, което значително намалява мрежовото натоварване и позволява на този консенсус да работи изключително бързо и устойчиво. Въпреки това, мрежата на EOS в момента трябва да използва специални блокове (Last Irreversible Block), които се потвърдват с подписи на 2/3 от BP. Тези блокове служат за осигуряване на финалност (невъзможност за появата на форк на веригата, започващ преди последния Last Irreversible Block).
Също така, в реалните имплементации, схемата на протокола е по-сложна — гласуванията за предложените блокове се провеждат в няколко етапа, за да се поддържа работата на мрежата в случай на пропуски на блокове и проблеми със свързаността, но дори с оглед на това, алгоритмите на консенсуса, използващи PVRB, изискват значително по-малко съобщения между BP, което позволява да бъдат по-бързи от традиционния PВFT или различни негови модификации.
Най-забележителният представител на такива алгоритми: от екипа на Cardano, който, както е обявено, притежава математически доказана устойчивост на наличието на съглашение сред BP.
В Ouroboros PVRB се използва за определяне на т.нар. “график на BP” — график, съгласно който на всеки BP се назначава свой времеви слот за публикуване на блок. Голямо предимство на използването на PVRB е пълното “равноправие” на BP (според размера на техните баланси). Честността на PVRB гарантира, че злонамерените BP не могат да контролират графика на времевите слотове и следователно не могат да манипулират веригата, предварително подготвяйки и анализирайки форкове на веригата, а за избора на форк е достатъчно да се разчита просто на дължината на веригата, без да се използват хитри методи на изчисление на “полезността” на BP и “тежестта” на неговите блокове.
Във всички случаи, когато в децентрализирана мрежа трябва да се избере случаен участник, почти винаги най-добрият избор е PVRB, а не детерминистичен вариант, основан, например, на хеша на блока. Без PVRB възможността да се повлияе на избора на участник води до появата на атаки, при които атакуващият може, избирайки между различни варианти за бъдещето, да избере следващия корумпиран участник или направо няколко, за да осигури по-съществени дялове в вземането на решение. Използването на PVRB дискредитира тези типове атаки.
Мащабиране и натоварване на баланса
PVRB може да донесе сериозни ползи и в задачи за намаляване на натоварването, мащабиране на плащанията. Първо, има смисъл да се запознаете с на Ривеста "Електронни лотарийни билети като микроплащания". Основната идея е, че вместо да се правят 100 плащания по 1c от платеца на получателя, може да се играе в честна лотария с награда 1$ = 100c, където платецът при всяко плащане от 1c предава на банката един от 100-те си "лотарийни билета". Един от тези билети печели на банката 1$, и именно този билет получателят може да фиксира в блокчейна. Най-важното е, че останалите 99 билета се предават между получателя и платеца без всякакво участие отвън, по приватен канал и с всякаква необходима скорост. Добро описание на протокола, базиран на тази схема в мрежата Emercoin, може да се прочете .
Тази схема има няколко проблема, например получателят може да спре да обслужва платеца веднага след получаването на печелившия билет, но за много специализирани приложения, като таксуване на минута или електронни абонаменти за услуги, те могат да се пренебрегнат. Основното изискване, разбира се, е честността на провежданата лотария, а за нейния провеждане е абсолютно необходим PVRB.
Изборът на случаен участник е изключително важен и за протоколите за шардване, чиято цел е хоризонталното мащабиране на блокчейн мрежата, позволявайки на различни BP да обработват само своя обхват на транзакции. Това е изключително сложна задача, особено що се отнася до безопасността при комбиниране на шардовете. Честният избор на случаен BP за назначаване на отговорни за конкретен шард, подобно на алгоритмите за консенсус, също е задача за PVRB. В централизирани системи шардовете се назначават от балансировчик, който просто изчислява хеш от заявката и я праща на необходимия изпълнител. В блокчейн мрежите, възможността за влияние върху това назначение може да доведе до атака върху консенсуса. Например, съдържанието на транзакциите може да бъде контролирано от нападателя, който може да контролира кои транзакции попадат в контролиран от него шард и да манипулира блокчейн веригата в него. Можете да прочетете за проблема с използването на случайни числа за задачи по шардване в Ethereum.
Шардингът е една от най-амбициозните и сериозни задачи в сферата на блокчейн технологийте, а решението й ще позволи изграждането на децентрализирани мрежи с фантастична производителност и обем. PVRB е само един от важните елементи за нейното решаване.
Игри, икономически протоколи, арбитраж
Ролята на случајни броеви во игропрометот е тешко да се прецени. Очигледната употреба во онлајн казина и нејзината неприметна улога при пресметување на ефектите од одредени дејства на играчот — сè ова се исклучително сложени прашања за децентрализирани мрежи, каде што не постои можност да се потпрете на централен извор на случајност. Но, случајниот избор може да решава и многу економски проблеми и да помага во изградба на поедноставни и поефикасни протоколи. Предпоставиме дека во нашиот протокол постојат спорови околу плаќање на евтини услуги, и тие спорови се случуваат доста ретко. Во овој случај, ако има неоспорен PVRB, клиентите и продавачите можат да се договоријат за случајно решавање на споровите, но со зададена веројатност. На пример, со веројатност од 60% победи клиентот, а со веројатност од 40% — продавачот. Таков, на прв поглед абсурден, пристап дозволува автоматско решавање на споровите со точно предвидлива поделба на победи/порази, прифатлива за двете страни без какво било учество на трета страна и непотребна потрошувачка на време. Понатаму, соодносот на веројатности може да биде динамичен и да зависи од некои глобални променливи. На пример, ако компанијата добро напредува, забележува низок број на спорови и висока профитабилност, компанијата може автоматски да ја помести веројатноста за решавање на спорот кон клиентската ориентираност, на пример 70/30 или 80/20, и обратно, ако спорите одземаат многу средства и се измамнички или неадекватни, може да се помести веројатноста во спротивна насока.
Голям брой интересни децентрализирани протоколи, като token curated registries, prediction markets, bonding curves и много други, представляват икономически игри, в които се награждава доброто поведение и се налагат наказания за лошо. В тях често възникват проблеми със сигурността, чиято защита е взаимно противоречива. Това, което е защитено от атака на „китовете“ с милиарди токени (“big stake”), е уязвимо на атаки от хиляди акаунти с малки баланси (“sybil stake”), а мерките, предприети срещу една атака, като нелинейни такси, създадени за да направят действието на големия залог неизгодно, обикновено губят стойност срещу друга атака. Като става въпрос за икономическа игра, съответните статистически тежести могат да се изчислят предварително и просто да се заменят таксите с рандомизирани с подходящо разпределение. Такива вероятностни такси могат да се реализират изключително лесно, ако в блокчейна има надежден източник на случайност и не изискват никакви сложни изчисления, усложнявайки живота както на китовете, така и на sybil-ите.
Въпреки това, трябва да продължим да помним, че контролът върху единствен бит в тази случайност позволява манипулация, намалявайки и увеличавайки вероятностите на два пъти, така че честният PVRB е изключително важен елемент на такива протоколи.
Къде да намерим правилната случайност?
В теорията, честният случайно избор в децентрализирани мрежи позволява да се осигури доказуема сигурност на почти всеки протокол срещу сговор. Обосновката е доста проста — ако мрежата се споразумее за един бит 0 или 1, и между участниците няма повече от половината нечестни, то при достатъчно количества итерации, мрежата гарантирано ще постигне консенсус относно този бит с фиксирана вероятност. Просто защото честният рандом ще избира 51 от 100 участници в 51% от случаите. Но това е в теорията, тъй като в реални мрежи, за да се осигури такова ниво на сигурност, каквото е описано в статиите, е необходима голяма степен на съобщения между хостовете, сложна многоходова криптография, а всяко усложнение на протокола веднага добавя нови вектори на атака.
Затова все още не наблюдаваме в блокчейните доказано устойчив PVRB, който да е използван достатъчно дълго, за да премине тестовете на реални приложения, множество одити, натоварвания и, разбира се, реални атаки, без които е трудно да се нарече продуктът наистина безопасен.
Въпреки това, съществуват няколко обещаващи подхода, които се отличават с много детайли, и един от тях със сигурност ще реши проблема. При съвременните компютърни ресурси, криптографската теория може доста ловко да се превърне в практически приложения. В бъдеще с удоволствие ще разкажем за имплементациите на PVRB: в момента има няколко, всяка от които притежава свой набор от важни свойства и особености в реализацията, и зад всяка стои добра идея. Не много екипи се занимават с рандомизиране и опитът на всеки от тях е изключително важен за всички останали. Надяваме се, че информацията ни ще помогне на другите екипи да напредват по-бързо, вземайки предвид опитите на предшествениците.
Източник: habr.com
