Увядзенне
"Генерацыя выпадковых лікаў занадта важная, каб пакідаць яе на волю выпадку"
Роберт Каўю, 1970
Гэты артыкул прысвечаны практычнаму прымяненню рашэнняў, якія выкарыстоўваюць калектыўную генерацыю выпадковых лікаў у недавераным асяроддзі. Калі коратка - як і для чаго выкарыстоўваецца рандом ў блокчейнах, і трохі пра тое, як адрозніць "добры" рандом ад "дрэннага". Генерацыя сапраўды выпадковага ліку з'яўляецца вельмі няпростай праблемай нават на асобным кампутары, і даўно вывучаецца крыптаграфіі. Ну а ў дэцэнтралізаваных сетках генерацыя выпадковых лікаў яшчэ больш складаная і важная.
Менавіта ў сетках, дзе ўдзельнікі не давяраюць адзін аднаму, магчымасць згенераваць бясспрэчны выпадковы лік дазваляе эфектыўна вырашаць мноства найважнейшых задач і значна палепшыць ужо існуючыя схемы. Прычым азартныя гульні і латарэі тут зусім не з'яўляюцца мэтай нумар адзін, як спачатку можа здацца неспрактыкаванаму чытачу.
Генерацыя выпадковых лікаў
Кампутары не ўмеюць самі вырабляць выпадковыя лікі, для гэтага ім патрабуецца дапамога звонку. Кампутар можа атрымліваць некаторае выпадковае значэнне выкарыстоўваючы, да прыкладу, рухі мышшу, колькасць скарыстанай памяці, паразітныя токі на кантактах працэсара і мноства іншых крыніц, званых крыніцамі энтрапіі. Самі гэтыя значэнні не зусім выпадковыя, бо знаходзяцца ў вызначаным дыяпазоне ці маюць прадказальны характар змен. Каб ператварыць такія лікі ў сапраўды выпадковы лік у зададзеным дыяпазоне, да іх ужываюць крыптаўтварэнні, каб з нераўнамерна размеркаваных значэнняў крыніцы энтрапіі атрымаць раўнамерна размеркаваныя псеўдавыпадковыя значэнні. Атрыманыя значэнні называюць псеўдавыпадковымі, бо яны не з'яўляюцца праўдзіва выпадковымі, а дэтэрміністычна зроблены з энтрапіі. Любы добры крыптаалгарытм, зашыфроўваючы дадзеныя вырабляе шыфратэксты, якія статыстычна павінны быць неадрозныя ад выпадковай паслядоўнасці, так што для вытворчасці рандома можна браць крыніцу энтрапіі, які забяспечвае толькі добрую непаўторнасць і непрадказальнасць значэнняў нават у невялікіх дыяпазонах, астатнюю частку працы па рассейванні. выніковым значэнні возьме на сябе алгарытм шыфравання.
Каб завяршыць кароткі лікбез, дадам, што генерацыя выпадковых лікаў нават на адной прыладзе - адзін са слупоў забеспячэння бяспекі нашых з вамі дадзеных, згенераваныя псеўдавыпадковыя лікі выкарыстоўваюцца пры ўсталяванні абароненых злучэнняў у розных сетках, для генерацыі крыптаграфічных ключоў, для балансавання нагрузкі, кантролю цэласнасці, і яшчэ для мноства ужыванняў. Бяспека шматлікіх пратаколаў залежыць ад магчымасці згенераваць надзейны, непрадказальны звонку рандом, захаваць яго, і не расчыняць яго да наступнага кроку пратаколу, інакш бяспека будзе пастаўлена пад пагрозу. Атака на генератар псеўдавыпадковых значэнняў з'яўляецца вельмі небяспечнай і ставіць пад пагрозу адразу ўсё ПА, якое выкарыстоўвае генерацыю рандомаў.
Усё гэта вы павінны ведаць, калі праходзілі базавы курс па крыптаграфіі, таму працягнем пра дэцэнтралізаваныя сеткі.
Рандом у блокчэйнах
У першую чаргу я буду казаць пра блокчейны з падтрымкай смарт-кантрактаў, менавіта яны могуць у поўнай меры выкарыстаць магчымасці, якія прадстаўляюцца якасным бясспрэчным рандом. Далей, для сцісласці, я буду называць гэтую тэхналогію”Publicly Verifiable Random Beacons” ці PVRB. Паколькі блокчейны - гэта сеткі, інфармацыю ў якой можа праверыць любы ўдзельнік, ключавой часткай назвы з'яўляецца "Publicly Verifiable", г.зн. любы жадаючы можа пры дапамозе вылічэнняў атрымаць доказ таго, што атрыманы лік, размешчанае ў блокчейне, валодае такімі ўласцівасцямі:
- Вынік павінен мець даказальна раўнамернае размеркаванне, г.зн. заснаваны на даказальна стойкай крыптаграфіі.
- Немагчыма кантраляваць ніводны з бітаў выніку. Як следства, вынік не можа быць загадзя прадказаны.
- Нельга сабатаваць пратакол генерацыі за рахунак няўдзелу ў пратаколе ці шляхам перагрузкі сеткі атакавалымі паведамленнямі
- Усё вышэйпералічанае павінна быць устойлівым да змоваў дапушчальнай колькасці несумленных удзельнікаў пратаколу (напрыклад 1/3 удзельнікаў).
Любая магчымасць змоўленай мінорнай групы ўдзельнікаў вырабіць нават кантраляваны цотны/няцотны рандом - дзірка ў бяспецы. Любая магчымасць групы спыніць выдачу рандома - дзірка ў бяспецы. Увогуле, праблем шмат, і гэтая задача не з лёгкіх…
Здаецца, што найбольш важнае прымяненне для PVRB, гэта розныя гульні, латарэі, і наогул любыя ўвазе gambling-а на блокчейне. Сапраўды, гэты важны кірунак, але ў рандома ў блокчейнах ёсць ужыванні і больш важныя. Разгледзім іх.
Алгарытмы кансэнсусу
PVRB для арганізацыі сеткавага кансэнсусу гуляе велізарнае значэнне. Транзакцыі ў блокчэйнах абаронены электронным подпісам, таму "атака на транзакцыю" гэта заўсёды ўключэнне/выключэнне транзакцыі ў блок (або ў некалькі блокаў). А галоўнай задачай алгарытму кансэнсусу з'яўляецца дамовіцца аб парадку гэтых транзакцый і аб парадку блокаў, якія ўключаюць у сябе гэтыя транзакцыі. Таксама, неабходнай уласцівасцю для рэальных блокчейнов з'яўляецца фінальнасць - магчымасць сеткі дамовіцца аб тым, што ланцужок да фіналізаванага блока з'яўляецца канчатковай, і ніколі не будзе выключана з-за з'яўлення новага форка. Звычайна, каб дамовіцца аб тым, што блок з'яўляецца валідным і, галоўнае, фінальным, патрабуецца сабраць подпісы з большасці вытворцаў блокаў (далей BP - block-producers), што патрабуе як мінімум даставіць ланцужок блокаў на ўсе BP, а подпісы распаўсюдзіць паміж усімі BP . Пры росце ліку BP, колькасць неабходных паведамленняў у сетцы экспанентна расце, таму, алгарытмы кансэнсусу, якія патрабуюць фінальнасць, выкарыстоўваныя напрыклад у pBFT-кансенсусе Hyperledger, не працуюць з патрэбнай хуткасцю, пачынальна ўжо з некалькіх дзясяткаў BP, патрабуючы велізарнай колькасці злучэнняў.
Калі ў сетцы маецца бясспрэчны і сумленны PVRB, то, нават у самым простым набліжэнні, можна на падставе яго выбіраць аднаго з block producers і прызначаць яго "лідэрам" на працягу аднаго раунда пратакола. Калі ў нас ёсць N block producer-ов, з якіх M: M > 1/2 N з'яўляюцца сумленнымі, не цэнзуруюць транзакцыі і не будуюць форкі ланцужкі з мэтай правядзення нападу "double spend", то выкарыстанне раўнамерна размеркаванага бясспрэчнага 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 schedule" – раскладу, паводле якога кожнаму BP прызначаецца свой часавы слот для публікацыі блока. Вялікай перавагай выкарыстання PVRB з'яўляецца поўнае "раўнапраўе" BP (згодна з памерамі іх балансаў). Сумленнасць PVRB гарантуе, што шкодныя BP не могуць кантраляваць расклад часавых слотаў, і, таму не могуць маніпуляваць ланцужком, загадзя падрыхтоўваючы і аналізуючы форкі ланцужкі, а для выбару форка дастаткова спадзявацца проста на даўжыню ланцужкі, не аперуючы хітрымі спосабамі "вагі" яго блокаў.
Наогул ва ўсіх выпадках, калі ў дэцэнтралізаванай сетцы трэба абраць выпадковага ўдзельніка, амаль заўсёды лепшым выбарам будзе PVRB, а не дэтэрміністычны варыянт на аснове, да прыкладу, хеша блока. Без PVRB магчымасць паўплываць на выбар удзельніка вядзе да з'яўлення нападаў, у якіх атакавалы можа, выбіраючы з некалькіх варыянтаў будучыні, выбіраць наступнага карумпаванага ўдзельніка ці адразу некалькіх, каб забяспечыць больш важкую дзель у прыняцці рашэння. Выкарыстанне PVRB дыскрэдытуе гэтыя тыпы нападаў.
Маштабаванне і балансіроўка нагрузкі
PVRB можа прынесці сур'ёзную карысць таксама ў задачах для зніжэння нагрузкі, маштабавання плацяжоў. Для пачатку мае сэнс азнаёміцца са Рывеста "Electronic Lottery Tickets as Micropayments". Агульная сутнасць такая, што замест таго каб рабіць 100 плацяжоў па 1c ад плацельшчыка атрымальніку, можна згуляць у сумленную латарэю з прызам 1 $ = 100c, дзе плацельшчык пры кожным плацяжы ў 1c перадае банку адзін са 100 сваіх "латарэйных білетаў". Адзін з гэтых білетаў выйграе банку 1$, і менавіта гэты білет атрымальнік можа фіксаваць у блокчейне. Самае важнае, што астатнія 99 білетаў перадаюцца паміж атрымальнікам і плацельшчыкам без усялякага знешняга ўдзелу, па прыватным канале і з любой патрэбнай хуткасцю. Добрае апісанне пратакола на базе гэтай схемы ў сетцы Emercoin можна прачытаць .
У гэтай схемы ёсць некалькі праблем, напрыклад атрымальнік можа перастаць абслугоўваць плацельшчыка адразу ж пасля атрымання выйгрышнага білета, але для мноства асаблівых ужыванняў, накшталт пахвіліннай тарыфікацыі або электронных падпісак на сэрвісы, імі можна занядбаць. Галоўным жа патрабаваннем, вядома, з'яўляецца сумленнасць якая праводзіцца латарэі, а для яе правядзення цалкам неабходны PVRB.
Выбар выпадковага ўдзельніка вельмі важны таксама для пратаколаў шардынгу, мэтай якіх з'яўляецца гарызантальнае маштабаванне ланцужка блокаў, дазваляючы розным BP працэсіць толькі свой scope транзакцый. Гэта вельмі складаная задача, асабліва ў пытаннях бяспекі пры аб'яднанні шардаў. Сумленны выбар выпадковага BP з мэтай прызначэння яго адказных за пэўны шард, як і ў алгарытмах кансэнсусу – таксама задача PVRB. У цэнтралізаваных сістэмах шарды прызначаюцца балансавальнікам, ён проста вылічае хэш ад запыту і адпраўляе неабходнаму выканаўцу. У блокчейнах, магчымасць уплываць на гэтае прызначэнне можа весці да нападу на кансэнсус. Напрыклад, змесціва транзакцый можа кантралявацца атакавалым, ён можа кантраляваць якія транзакцыі пападаюць у кантраляваны ім шард і маніпуляваць ланцужком блокаў у ім. Абмеркаванне праблемы выкарыстання выпадковых лікаў для задач шардынгу ў Ethereum можна пачытаць
Шардынг - гэта адна з самых амбіцыйных і сур'ёзных задач у галіне блокчейн, яе рашэнне дазволіць будаваць дэцэнтралізаваныя сеткі фантастычнай прадукцыйнасці і аб'ёму. PVRB - гэта толькі адзін з важных блокаў, для яе вырашэння.
Гульні, эканамічныя пратаколы, арбітраж
Ролю выпадковых лікаў у гульнявой індустрыі складана пераацаніць. Відавочнае выкарыстанне ў анлайн казіно, і няяўнае пры разліку эфектаў таго ці іншага дзеяння гульца - усё гэта вельмі складаныя праблемы для дэцэнтралізаваных сетак, дзе няма магчымасці пакласціся на цэнтральную крыніцу выпадковасці. Але выпадковы выбар можа вырашаць і многія эканамічныя праблемы і дапамагаць будаваць больш простыя і эфектыўныя пратаколы. Выкажам здагадку ў нашым пратаколе маюць месца дыспуты наконт аплаты якіх-небудзь недарагіх паслуг, і гэтыя дыспуты адбываюцца досыць рэдка. У гэтым выпадку, калі ёсць бясспрэчны PVRB, кліенты і прадаўцы могуць дамовіцца аб выпадковым дазволе дыспутаў, але з зададзенай верагоднасцю. Напрыклад з верагоднасцю 60% перамагае кліент, а з верагоднасцю 40% - прадавец. Такі, з першага пункта гледжання абсурдны, падыход дазваляе аўтаматычна вырашаць дыспуты з сапраўды прадказальнай дзеллю выйгрышаў/пройгрышаў, які задавальняе абодва бакі без усялякага ўдзелу трэцяга боку і непатрэбнага марнавання часу. Больш за тое, суадносіны верагоднасцяў можа быць дынамічным і залежаць ад некаторых глабальных зменных. Да прыкладу, калі ў кампаніі справы ідуць добра, адзначаецца нізкая колькасць дыспутаў і высокая прыбытковасць, кампанія можа аўтаматычна зрушваць верагоднасць дазволу дыспуту ў бок кліент-арыентаванасці, да прыкладу 70/30 ці 80/20, і наадварот, калі дыспуты адымаюць шмат сродкаў і з'яўляюцца ашуканскімі ці неадэкватнымі, можна зрушваць верагоднасць у іншы бок.
Вялікая колькасць цікавых дэцэнтралізаваных пратаколаў, такіх як token currated registries, prediction markets, bonding curves і многія іншыя ўяўляюць сабой эканамічныя гульні, у якіх узнагароджваюцца добрыя паводзіны, і штрафуецца дрэннае. У іх часта сустракаюцца праблемы бяспекі, абароны ад якіх супярэчаць адна адной. Тое, што абаронена ад нападу "кітоў" з мільярдамі токенаў ("big stake"), уразліва да нападаў тысячамі акаўнтаў з невялікімі балансамі ("sybil stake"), і меры, якія прымаюцца супраць адной атакі, напрыклад нелінейныя камісіі, створаныя для таго, каб зрабіць працу вялікім стейкам нявыгаднай, звычайна дыскрэдытуюцца іншай атакай. Бо гаворка ідзе аб эканамічнай гульні, якія адпавядаюць статыстычныя вагі можна разлічыць загадзя, і проста замяніць камісіі на рандомизированные з адпаведным размеркаваннем. Такія імавернасныя камісіі рэалізуюцца вельмі проста, калі ў блокчейне ёсць надзейная крыніца рандома і не патрабуюць ніякіх складаных вылічэнняў, ускладняючы жыццё і кітам і sybil-ам.
Пры гэтым неабходна працягваць памятаць, што кантроль над адзіным бітам у гэтым рандоме дазваляе падманваць, памяншаючы і павялічваючы верагоднасці ўдвая, так што сумленны PVRB - найважнейшы складнік такіх пратаколаў.
Дзе знайсці правільны рандом?
У тэорыі, сумленны выпадковы выбар у дэцэнтралізаваных сетках дазваляе забяспечыць даказальную бяспеку амаль любога пратакола ад змовы. Абгрунтаванне даволі простае - калі сетка дамаўляецца аб адным біце 0 або 1, і сярод удзельнікаў менш за палову з'яўляюцца несумленнымі, то, пры дастатковай колькасці ітэрацый, сетка гарантавана прыйдзе да кансенсусу адносна гэтага біта з фіксаванай верагоднасцю. Проста таму што сумленны рандом будзе выбіраць 51 са 100 удзельнікаў у 51% выпадкаў. Але гэта ў тэорыі, т.я. у рэальных сетках, для забеспячэння такога ўзроўня бяспекі, як у артыкулах, патрабуецца мноства паведамленняў паміж хастамі, складаная шматхадовая крыптаграфія, а любое ўскладненне пратакола адразу ж дадае новыя вектары нападаў.
Менавіта таму мы пакуль не бачым у блокчейнах даказана ўстойлівага PVRB, які выкарыстоўваўся б ужо досыць чакай, каб мінуць выпрабаванні сапраўднымі прыкладаннямі, множнымі аўдытамі, нагрузкамі, і вядома, жа, рэальнымі нападамі, без якіх цяжка назваць прадукт па сучаснасці бяспечным.
Тым не менш, ёсць адразу некалькі перспектыўных падыходаў, яны адрозніваюцца мноствам дэталяў, і нейкая з іх сапраўды вырашыць праблему. Пры сучасных вылічальных рэсурсах, крыптаграфічная тэорыя здольная даволі спрытна ператварацца ў практычныя ўжыванні. У далейшым, мы з задавальненнем раскажам аб імплементацыях PVRB: іх зараз некалькі, кожная валодае сваім наборам важных уласцівасцяў і асаблівасцяў у рэалізацыі, і за кожнай стаіць добрая ідэя. Рандом займаецца не так шмат каманд, і вопыт кожнай з іх вельмі важны для ўсіх астатніх. Спадзяемся, што наша інфармацыя дазволіць астатнім камандам рухацца хутчэй, з улікам досведу папярэднікаў.
Крыніца: habr.com