Случајни бројеви и децентрализоване мреже: практичне примене

Увод

„Генерисање случајних бројева је превише важно да би се препустило случају.”
Роберт Цавуе, 1970

Овај чланак је посвећен практичној примени решења коришћењем колективног генерисања случајних бројева у непоузданом окружењу. Укратко, како и зашто се насумично користи у блокчејновима, и мало о томе како разликовати „добро“ насумично од „лошег“. Генерисање заиста случајног броја је изузетно тежак проблем, чак и на једном рачунару, и криптографи су га дуго проучавали. Па, у децентрализованим мрежама, генерисање случајних бројева је још сложеније и важније.

Управо у мрежама у којима учесници немају поверења једни у друге, способност генерисања неоспорног случајног броја нам омогућава да ефикасно решимо многе критичне проблеме и значајно побољшамо постојеће шеме. Штавише, коцкање и лутрија овде нису циљ број један, како се на први поглед чини неискусном читаоцу.

Генерисање случајних бројева

Рачунари не могу сами да генеришу насумичне бројеве; за то им је потребна спољна помоћ. Рачунар може да добије неку насумичне вредности из, на пример, покрета миша, количине коришћене меморије, залуталих струја на пиновима процесора и многих других извора који се називају извори ентропије. Ове вредности саме по себи нису сасвим насумичне, јер су у одређеном опсегу или имају предвидљив образац промена. Да би се такви бројеви претворили у заиста насумичан број унутар датог опсега, на њих се примењују криптотрансформације да би се произвеле равномерно распоређене псеудослучајне вредности из неравномерно распоређених вредности извора ентропије. Резултирајуће вредности се називају псеудослучајне јер нису заиста насумичне, већ су детерминистички изведене из ентропије. Сваки добар криптографски алгоритам, када шифрује податке, производи шифроване текстове који би требало да се статистички не разликују од насумичне секвенце, тако да за производњу случајности можете узети извор ентропије, који обезбеђује само добру поновљивост и непредвидивост вредности чак и у малим распонима, остатак посла је дисперговање и мешање битова у Резултујућу вредност ће преузети алгоритам шифровања.

Да завршим кратак едукативни програм, додаћу да је генерисање случајних бројева чак и на једном уређају један од стубова обезбеђења безбедности наших података.Генерисани псеудослучајни бројеви се користе приликом успостављања безбедних веза у различитим мрежама, за генерисање криптографски кључеви, за балансирање оптерећења, праћење интегритета и за многе друге апликације. Безбедност многих протокола зависи од способности да се генерише поуздан, споља непредвидив случајни случај, да се сачува и не открије до следећег корака протокола, иначе ће безбедност бити угрожена. Напад на генератор псеудослучајних вредности је изузетно опасан и одмах угрожава сав софтвер који користи генерисање случајности.

Све ово би требало да знате ако сте похађали основни курс криптографије, па хајде да наставимо са децентрализованим мрежама.

Насумично у блокчејновима

Пре свега, говорићу о блокчејновима са подршком за паметне уговоре; они су ти који могу у потпуности да искористе могућности које пружа висококвалитетна, неоспорна случајност. Даље, ради краткоће, назваћу ову технологију „Јавно проверљиви насумични светионици” или ПВРБ. Пошто су блокчејн мреже у којима било који учесник може да верификује информације, кључни део назива је „Публицли Верифиабле”, тј. Свако може да користи калкулације да добије доказ да резултујући број објављен на блокчејну има следећа својства:

• Резултат мора да има доказиво уједначену дистрибуцију, тј. да буде заснован на доказиво јакој криптографији.
• Није могуће контролисати било који од битова резултата. Као последица тога, исход се не може унапред предвидети.
• Не можете саботирати протокол генерисања тако што ћете не учествовати у протоколу или преоптеретити мрежу порукама о нападу
• Све наведено мора бити отпорно на договарање дозвољеног броја непоштених учесника у протоколу (нпр. 1/3 учесника).

Свака могућност да мања група учесника у дослуху произведе чак и контролисане паран/непаран случајни случај је сигурносна рупа. Свака способност групе да заустави издавање насумице је сигурносна рупа. Генерално, има много проблема, а овај задатак није лак...

Чини се да је најважнија апликација за ПВРБ разне игре, лутрије и уопште било која врста коцкања на блокчејну. Заиста, ово је важан правац, али случајност у блокчејновима има још важније примене. Хајде да их погледамо.

Алгоритми консензуса

ПВРБ игра огромну улогу у организовању мрежног консензуса. Трансакције у блоцкцхаин-у су заштићене електронским потписом, тако да је „напад на трансакцију“ увек укључивање/искључивање трансакције у блок (или неколико блокова). А главни задатак алгоритма консензуса је да се договори о редоследу ових трансакција и редоследу блокова који укључују ове трансакције. Такође, неопходно својство за стварне блокчејнове је коначност – способност мреже да се сложи да је ланац до финализованог блока коначан и никада неће бити искључен због појаве нове виљушке. Обично, да би се договорили да је блок валидан и, што је најважније, коначан, потребно је прикупити потписе већине произвођача блокова (у даљем тексту БП - произвођачи блокова), што захтева бар испоруку ланца блокова. свим БП, и расподелу потписа између свих БП. Како број БП расте, број потребних порука у мрежи расте експоненцијално, стога алгоритми консензуса који захтевају коначност, који се користе на пример у Хиперледгер пБФТ консензусу, не раде потребном брзином, почевши од неколико десетина БП, захтевајући огроман број веза.

Ако у мрежи постоји неоспоран и поштен ПВРБ, онда се, чак иу најједноставнијој апроксимацији, на основу њега може изабрати један од произвођача блокова и именовати га за „лидера“ током једне рунде протокола. Ако имамо N произвођачи блокова, од којих M: M > 1/2 N су поштени, не цензуришу трансакције и не рачвајте ланац да би извршили напад „двоструке потрошње“, онда ће коришћење равномерно распоређеног неоспорног ПВРБ-а омогућити избор поштеног лидера са вероватноћом M / N (M / N > 1/2). Ако је сваком лидеру додељен сопствени временски интервал током којег може да произведе блок и потврди ланац, а ови интервали су временски једнаки, онда ће ланац блокова поштених БП бити дужи од ланца који формирају злонамерни БП, а консензус алгоритам се ослања на дужину ланца, једноставно ће одбацити онај „лош“. Овај принцип додељивања једнаких делова времена сваком БП-у је први пут примењен у Грапхене-у (претходнику ЕОС-а) и омогућава да се већина блокова затвори једним потписом, што у великој мери смањује оптерећење мреже и омогућава да овај консензус функционише изузетно брзо и постојано. Међутим, ЕОС мрежа сада мора да користи посебне блокове (Ласт Ирреверсибле Блоцк), који су потврђени потписима 2/3 БП. Ови блокови служе да обезбеде коначност (немогућност да ланчана виљушка почне пре последњег последњег неповратног блока).

Такође, у стварним имплементацијама, шема протокола је компликованија - гласање за предложене блокове се спроводи у неколико фаза како би се мрежа одржала у случају недостајућих блокова и проблема са мрежом, али чак и узимајући то у обзир, алгоритми консензуса који користе ПВРБ захтевају знатно мање порука између БП-а, што их чини бржим од традиционалног ПВФТ-а, или његових различитих модификација.

Најистакнутији представник таквих алгоритама: оуроборос из Цардано тима, за који се каже да је математички доказив против БП дослуха.

У Оуроборосу, ПВРБ се користи за дефинисање такозваног „БП распореда“ - распореда према којем се сваком БП-у додељује сопствени временски слот за објављивање блока. Велика предност коришћења ПВРБ-а је потпуна „једнакост“ БП-а (према величини њихових биланса). Интегритет ПВРБ-а обезбеђује да злонамерни БП не могу да контролишу заказивање временских слотова, па стога не могу да манипулишу ланцем припремајући и анализирајући виљушке ланца унапред, а да бисте изабрали виљушку, довољно је да се једноставно ослоните на дужину ланца. ланца, без употребе лукавих начина за израчунавање „корисности“ БП-а и „тежине“ његових блокова.

Уопштено говорећи, у свим случајевима када је потребно изабрати случајног учесника у децентрализованој мрежи, ПВРБ је скоро увек најбољи избор, а не детерминистичка опција заснована на, на пример, хеш блока. Без ПВРБ-а, могућност утицаја на избор учесника доводи до напада у којима нападач може да бира између више будућности да одабере следећег корумпираног учесника или неколико одједном како би обезбедио већи удео у одлуци. Употреба ПВРБ-а дискредитује ове врсте напада.

Скалирање и балансирање оптерећења

ПВРБ такође може бити од велике користи у задацима као што су смањење оптерећења и скалирање плаћања. За почетак, има смисла упознати се чланак Ривеста „Улазнице за електронске лутрије као микро плаћања”. Општа идеја је да уместо 100 1ц плаћања од платиоца примаоцу, можете играти поштену лутрију са наградом од 1$ = 100ц, где платилац даје банци једну од 1 својих „лутријских листића“ за сваку 100ц плаћање. Једна од ових тикета осваја теглу од 1 долара, а прималац може да сними у блоцкцхаин. Најважније је да се преосталих 99 тикета преноси између примаоца и платиоца без икаквог спољног учешћа, приватним каналом и жељеном брзином. Може се прочитати добар опис протокола заснованог на овој шеми на мрежи Емерцоин овде.

Ова шема има неколико проблема, на пример, прималац може да престане да услужује уплатитеља одмах након што добије добитну карту, али за многе посебне апликације, као што је наплата по минуту или електронске претплате на услуге, они се могу занемарити. Главни услов је, наравно, правичност лутрије, а за њено спровођење је ПВРБ апсолутно неопходан.

Избор случајног учесника је такође изузетно важан за протоколе за дијељење, чија је сврха да хоризонтално скалирају ланац блокова, омогућавајући различитим БП-има да обрађују само свој обим трансакција. Ово је изузетно тежак задатак, посебно у смислу безбедности приликом спајања фрагмената. Праведан избор насумичне БП у сврху додељивања одговорних за конкретан шард, као у консензус алгоритмима, такође је задатак ПВРБ-а. У централизованим системима, шардове додељује балансер; он једноставно израчунава хеш из захтева и шаље га потребном извршиоцу. У блокчејновима, могућност утицаја на овај задатак може довести до напада на консензус. На пример, садржај трансакција може да контролише нападач, он може да контролише које трансакције иду у део који контролише и да манипулише ланцем блокова у њему. Можете прочитати дискусију о проблему коришћења насумичних бројева за задатке шардирања у Етхереуму овде
Схардинг је један од најамбициознијих и најозбиљнијих проблема у области блоцкцхаина; његово решење ће омогућити изградњу децентрализованих мрежа фантастичних перформанси и обима. ПВРБ је само један од важних блокова за његово решавање.

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

Улогу насумичних бројева у индустрији игара тешко је преценити. Експлицитна употреба у онлајн коцкарницама и имплицитна употреба приликом израчунавања ефеката акције играча су изузетно тешки проблеми за децентрализоване мреже, где се не може ослонити на централни извор случајности. Али случајни одабир такође може решити многе економске проблеме и помоћи у изградњи једноставнијих и ефикаснијих протокола. Претпоставимо да у нашем протоколу постоје спорови око плаћања неких јефтиних услуга, а ти спорови се јављају прилично ретко. У овом случају, ако постоји неоспоран ПВРБ, купци и продавци могу да се договоре да решавају спорове насумично, али са датом вероватноћом. На пример, са вероватноћом од 60% побеђује клијент, а са вероватноћом од 40% побеђује продавац. Овакав приступ, који је са прве тачке гледишта апсурдан, омогућава вам да аутоматски решавате спорове са тачно предвидљивим уделом победа/губитака, што одговара обема странама без икаквог учешћа треће стране и непотребног губљења времена. Штавише, однос вероватноће може бити динамичан и зависи од неких глобалних варијабли. На пример, ако компанија добро послује, има мали број спорова и високу профитабилност, компанија може аутоматски померити вероватноћу решавања спора ка клијенту, на пример 70/30 или 80/20, и обрнуто, ако спорови захтевају много новца и лажни су или неадекватни, можете померити вероватноћу у другом правцу.

Велики број занимљивих децентрализованих протокола, као што су регистри курирани токенима, тржишта предвиђања, криве везивања и многи други, су економске игре у којима се добро понашање награђује, а лоше понашање кажњава. Често садрже безбедносне проблеме за које се заштите међусобно сукобљавају. Оно што је заштићено од напада „китова“ са милијардама токена („велики улог“) подложно је нападима хиљада налога са малим билансима („сибил улог“) и мерама предузетим против једног напада, као што је не- линеарне накнаде створене да би рад са великим улогом био неисплатив обично се дискредитују другим нападом. Пошто је реч о економској игри, одговарајуће статистичке тежине се могу израчунати унапред, и једноставно заменити провизије са рандомизованим са одговарајућом расподелом. Такве вероватноће провизије се спроводе изузетно једноставно ако блокчејн има поуздан извор случајности и не захтева никакве сложене прорачуне, што отежава живот и китовима и сибилама.
У исто време, потребно је и даље запамтити да вам контрола над једним битом у овој насумичности омогућава варање, смањујући и повећавајући вероватноће за половину, тако да је поштен ПВРБ најважнија компонента таквих протокола.

Где пронаћи прави случајни случај?

У теорији, правичан случајни одабир у децентрализованим мрежама чини скоро сваки протокол доказано сигурним од дослуха. Образложење је прилично једноставно - ако се мрежа сложи око једног бита 0 или 1, а мање од половине учесника је непоштено, онда, с обзиром на довољно итерација, мрежа гарантовано постиже консензус о том биту са фиксном вероватноћом. Једноставно зато што ће поштени случајни одабир изабрати 51 од 100 учесника 51% времена. Али ово је у теорији, јер... у стварним мрежама, да би се обезбедио такав ниво безбедности као у чланцима, потребно је много порука између хостова, сложена вишепролазна криптографија, а свака компликација протокола одмах додаје нове векторе напада.
Због тога још не видимо доказано отпоран ПВРБ у блок-чејновима, који би био коришћен довољно времена да га тестирају стварне апликације, вишеструке ревизије, оптерећења и, наравно, стварни напади, без којих је тешко назвати производ заиста безбедан.

Међутим, постоји неколико приступа који обећавају, они се разликују у многим детаљима, а један од њих ће дефинитивно решити проблем. Са савременим рачунарским ресурсима, криптографска теорија се може прилично паметно превести у практичне примене. У будућности ћемо радо разговарати о ПВРБ имплементацијама: сада их има неколико, свака има свој скуп важних својстава и карактеристика имплементације, а иза сваке стоји добра идеја. Нема много тимова укључених у рандомизацију, а искуство сваког од њих је изузетно важно за све остале. Надамо се да ће наше информације омогућити и другим тимовима да се крећу брже, узимајући у обзир искуство својих претходника.

Извор: ввв.хабр.цом