Случайни числа и децентрализирани мрежи: Практически приложения

въведение

„Генерирането на случайни числа е твърде важно, за да бъде оставено на случайността.“
Робърт Каву, 1970 г

Тази статия е посветена на практическото приложение на решения, използващи колективно генериране на случайни числа в ненадеждна среда. Накратко, как и защо произволният се използва в блокчейните и малко за това как да се разграничи „добрият“ произволен от „лошия“. Генерирането на наистина произволно число е изключително труден проблем, дори на един компютър, и отдавна се изучава от криптографи. Е, в децентрализираните мрежи генерирането на произволни числа е още по-сложно и важно.

Именно в мрежи, където участниците нямат доверие един на друг, възможността за генериране на неоспоримо произволно число ни позволява ефективно да решаваме много критични проблеми и значително да подобряваме съществуващите схеми. Освен това хазартът и лотарията не са цел номер едно тук, както може да изглежда в началото на неопитния читател.

Генериране на случайни числа

Компютрите не могат сами да генерират произволни числа; те се нуждаят от външна помощ, за да го направят. Компютърът може да получи някаква произволна стойност от, например, движения на мишката, количеството използвана памет, блуждаещи токове на щифтовете на процесора и много други източници, наречени източници на ентропия. Тези стойности сами по себе си не са напълно случайни, тъй като са в определен диапазон или имат предвидим модел на промени. За да се превърнат такива числа в наистина произволно число в даден диапазон, към тях се прилагат криптотрансформации, за да се получат равномерно разпределени псевдослучайни стойности от неравномерно разпределените стойности на източника на ентропия. Получените стойности се наричат ​​псевдослучайни, защото не са наистина случайни, а са детерминистично получени от ентропията. Всеки добър криптографски алгоритъм, когато криптира данни, произвежда шифровани текстове, които трябва да бъдат статистически неразличими от случайна последователност, така че за да произведете случайност, можете да вземете източник на ентропия, който осигурява само добра повторяемост и непредсказуемост на стойностите дори в малки диапазони, Останалата част от работата е разпръскване и смесване на битове в Получената стойност ще бъде поета от алгоритъма за криптиране.

За да завърша кратка образователна програма, ще добавя, че генерирането на случайни числа дори на едно устройство е един от стълбовете за гарантиране на сигурността на нашите данни.Генерираните псевдослучайни числа се използват при установяване на защитени връзки в различни мрежи, за генериране на криптографски ключове, за балансиране на натоварването, наблюдение на целостта и за много други приложения. Сигурността на много протоколи зависи от способността да се генерира надежден, външно непредсказуем случаен, да се съхранява и да не се разкрива до следващата стъпка на протокола, в противен случай сигурността ще бъде компрометирана. Атаката срещу генератор на псевдослучайни стойности е изключително опасна и незабавно застрашава целия софтуер, който използва генериране на случайни стойности.

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

Случайни в блокчейни

На първо място, ще говоря за блокчейни с поддръжка на интелигентни договори; те са тези, които могат напълно да се възползват от възможностите, предоставени от висококачествена, неоспорима случайност. Освен това, за краткост, ще наричам тази технология „Публично проверими произволни маяци” или PVRB. Тъй като блокчейните са мрежи, в които информацията може да бъде проверена от всеки участник, ключовата част от името е „Публично проверено“, т.е. Всеки може да използва изчисления, за да получи доказателство, че полученото число, публикувано в блокчейна, има следните свойства:

• Резултатът трябва да има доказано равномерно разпределение, т.е. да се основава на доказано силна криптография.
• Не е възможно да се контролира нито един от битовете на резултата. В резултат на това резултатът не може да бъде предвиден предварително.
• Не можете да саботирате протокола за генериране, като не участвате в протокола или като претоварвате мрежата със съобщения за атака
• Всичко по-горе трябва да е устойчиво на тайно споразумение на допустим брой нечестни участници в протокола (например 1/3 от участниците).

Всяка възможност за съгласувана малка група участници да произведе дори контролирано произволно четно/нечетно е дупка в сигурността. Всяка възможност на групата да спре произволното издаване е дупка в сигурността. Като цяло проблемите са много и тази задача не е лесна...

Изглежда, че най-важното приложение за PVRB са различни игри, лотарии и изобщо всякакъв вид хазарт в блокчейна. Наистина, това е важна посока, но случайността в блокчейните има още по-важни приложения. Нека да ги разгледаме.

Консенсусни алгоритми

PVRB играе огромна роля в организирането на мрежов консенсус. Транзакциите в блокчейн са защитени с електронен подпис, така че „атака срещу транзакция“ винаги е включването/изключването на транзакция в блок (или няколко блока). И основната задача на консенсусния алгоритъм е да се споразумеят за реда на тези транзакции и реда на блоковете, които включват тези транзакции. Също така, необходимо свойство за истинските блокчейни е окончателността - способността на мрежата да се съгласи, че веригата до финализирания блок е окончателна и никога няма да бъде изключена поради появата на нов форк. Обикновено, за да се съгласи, че блокът е валиден и най-важното окончателен, е необходимо да се съберат подписи от мнозинството производители на блокове (наричани по-нататък BP - блок-продуценти), което изисква най-малко доставка на веригата на блокове до всички BP и разпространение на подписи между всички BP. С нарастването на броя на BP, броят на необходимите съобщения в мрежата нараства експоненциално, следователно консенсусните алгоритми, които изискват окончателност, използвани например в консенсуса Hyperledger pBFT, не работят с необходимата скорост, като се започне от няколко десетки 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. Тези блокове служат за осигуряване на окончателност (невъзможността вилицата на веригата да започне преди последния последен необратим блок).

Освен това при реални реализации схемата на протокола е по-сложна - гласуването за предложените блокове се извършва на няколко етапа, за да се поддържа мрежата в случай на липсващи блокове и проблеми с мрежата, но дори като се има предвид това, консенсусните алгоритми, използващи PVRB, изискват значително по-малко съобщения между BP, което прави възможно те да бъдат по-бързи от традиционния PVFT или неговите различни модификации.

Най-яркият представител на такива алгоритми: Ouroboros от екипа на Cardano, за който се твърди, че е математически доказуем срещу тайно споразумение с BP.

В Ouroboros PVRB се използва за дефиниране на така наречения „BP ​​график“ - график, според който на всеки BP се присвоява собствен времеви интервал за публикуване на блок. Голямото предимство на използването на PVRB е пълното „равенство“ на BP (според размера на техните баланси). Целостта на PVRB гарантира, че злонамерените BP не могат да контролират планирането на времевите интервали и следователно не могат да манипулират веригата, като подготвят и анализират разклоненията на веригата предварително, а за да изберете разклонение, е достатъчно просто да разчитате на дължината на верига, без да се използват хитри начини за изчисляване на „полезността“ на BP и „теглото“ на неговите блокове.

Като цяло, във всички случаи, когато произволен участник трябва да бъде избран в децентрализирана мрежа, PVRB е почти винаги най-добрият избор, а не детерминистична опция, базирана например на блоков хеш. Без PVRB способността да се влияе върху избора на участник води до атаки, при които нападателят може да избира от множество фючърси, за да избере следващия корумпиран участник или няколко наведнъж, за да осигури по-голям дял в решението. Използването на PVRB дискредитира този тип атаки.

Мащабиране и балансиране на натоварването

PVRB също може да бъде от голяма полза при задачи като намаляване на натоварването и мащабиране на плащанията. Като начало има смисъл да се запознаете с статия Rivesta „Електронни лотарийни билети като микроплащания“. Общата идея е, че вместо да правите 100 1c плащания от платеца към получателя, можете да играете на честна лотария с награда от 1$ = 100c, където платецът дава на банката един от 1 от своите „лотарийни билети“ за всеки 100c плащане. Един от тези билети печели буркан от $1 и именно този билет получателят може да запише в блокчейна. Най-важното е, че останалите 99 билета се прехвърлят между получателя и платеца без външно участие, по частен канал и с желана скорост. Може да се прочете добро описание на протокола, базиран на тази схема в мрежата Emercoin тук.

Тази схема има няколко проблема, като например получателят може да спре да обслужва платеца веднага след получаване на печеливш билет, но за много специални приложения, като таксуване на минута или електронни абонаменти за услуги, те могат да бъдат пренебрегнати. Основното изискване, разбира се, е честността на лотарията, а за провеждането й е абсолютно необходим ПВРБ.

Изборът на произволен участник също е изключително важен за протоколите за шардинг, чиято цел е хоризонтално мащабиране на блоковата верига, което позволява на различни BP да обработват само своя обхват от транзакции. Това е изключително трудна задача, особено от гледна точка на сигурността при сливането на шардове. Справедлив избор на случаен BP за целите на определяне на отговорните за конкретен шард, както при консенсусните алгоритми, също е задача на PVRB. В централизираните системи шардовете се присвояват от балансьор; ​​той просто изчислява хеша от заявката и го изпраща на необходимия изпълнител. В блокчейните способността да се влияе върху това присвояване може да доведе до атака срещу консенсуса. Например, съдържанието на транзакциите може да се контролира от нападател, той може да контролира кои транзакции отиват към шарда, който контролира, и да манипулира веригата от блокове в него. Можете да прочетете дискусия на проблема с използването на произволни числа за шардинг задачи в Ethereum тук
Шардингът е един от най-амбициозните и сериозни проблеми в областта на блокчейна; решението му ще позволи изграждането на децентрализирани мрежи с фантастична производителност и обем. PVRB е само един от важните блокове за решаването му.

Игри, икономически протоколи, арбитраж

Ролята на произволните числа в игралната индустрия е трудно да се надценява. Изричното използване в онлайн казината и косвеното използване при изчисляване на ефектите от действието на играча са изключително трудни проблеми за децентрализираните мрежи, където няма начин да се разчита на централен източник на произволност. Но произволният избор може също да реши много икономически проблеми и да помогне за изграждането на по-прости и по-ефективни протоколи. Да предположим, че в нашия протокол има спорове относно плащането на някои евтини услуги и тези спорове се случват доста рядко. В този случай, ако има безспорен PVRB, клиентите и продавачите могат да се споразумеят за разрешаване на спорове произволно, но с определена вероятност. Например с 60% вероятност клиентът печели, а с 40% вероятност продавачът печели. Този, на пръв поглед абсурден, подход позволява автоматично разрешаване на спорове с точно предвидим дял печалби/загуби, което устройва и двете страни, без участието на трета страна и излишна загуба на време. Освен това съотношението на вероятността може да бъде динамично и да зависи от някои глобални променливи. Например, ако една компания се справя добре, има нисък брой спорове и висока рентабилност, компанията може автоматично да измести вероятността за разрешаване на спор към ориентиране към клиента, например 70/30 или 80/20, и обратно, ако споровете отнемат много пари и са измамни или неадекватни, можете да изместите вероятността в другата посока.

Голям брой интересни децентрализирани протоколи, като регистри с курирани токени, пазари за прогнозиране, криви на свързване и много други, са икономически игри, в които доброто поведение се възнаграждава, а лошото се наказва. Те често съдържат проблеми със сигурността, за които защитите са в конфликт помежду си. Това, което е защитено от атака на „китове“ с милиарди токени („голям залог“), е уязвимо на атаки от хиляди акаунти с малки баланси („залог на сибила“) и мерки, предприети срещу една атака, като не- линейните такси, създадени, за да направят работата с голям дял нерентабилна, обикновено се дискредитират от друга атака. Тъй като говорим за икономическа игра, съответните статистически тегла могат да се изчислят предварително и просто да се заменят комисионните с рандомизирани с подходящото разпределение. Такива вероятностни комисионни се изпълняват изключително просто, ако блокчейнът има надежден източник на произволност и не изисква никакви сложни изчисления, което прави живота труден както за китовете, така и за сибилите.
В същото време е необходимо да продължите да помните, че контролът върху един бит в тази случайност ви позволява да мамите, намалявайки и увеличавайки вероятностите наполовина, така че честният PVRB е най-важният компонент на такива протоколи.

Къде да намеря правилния случаен?

На теория справедливият произволен избор в децентрализираните мрежи прави почти всеки протокол доказано защитен срещу тайни споразумения. Обосновката е доста проста - ако мрежата се съгласи с един бит 0 или 1 и по-малко от половината от участниците са нечестни, тогава при достатъчно повторения мрежата гарантирано ще постигне консенсус по този бит с фиксирана вероятност. Просто защото честен случаен избор ще избере 51 от 100 участници в 51% от случаите. Но това е на теория, защото... в реални мрежи, за да се осигури такова ниво на сигурност като в статиите, са необходими много съобщения между хостове, сложна многопроходна криптография и всяко усложнение на протокола незабавно добавя нови вектори на атака.
Ето защо все още не виждаме доказано устойчив PVRB в блокчейните, който би бил използван достатъчно време, за да бъде тестван от реални приложения, множество одити, зареждания и разбира се реални атаки, без които е трудно да се нарече продукт наистина безопасен.

Има обаче няколко обещаващи подхода, те се различават в много подробности и един от тях определено ще реши проблема. Със съвременните изчислителни ресурси, криптографската теория може да бъде доста умело преведена в практически приложения. В бъдеще ще се радваме да говорим за внедрявания на PVRB: сега има няколко от тях, всеки има свой собствен набор от важни свойства и функции за изпълнение и зад всеки стои добра идея. В рандомизацията не участват много екипи и опитът на всеки от тях е изключително важен за всички останали. Надяваме се, че нашата информация ще позволи на други отбори да се движат по-бързо, като вземат предвид опита на своите предшественици.

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