Вовед
„Генерирањето на случајни броеви е премногу важно за да се остави на случајноста“.
Роберт Кавју, 1970 година
Оваа статија е посветена на практичната примена на решенија користејќи колективно генерирање на случаен број во недоверлива средина. Накратко, како и зошто рандомот се користи во блокчејн, и малку за тоа како да се разликува „доброто“ случајно од „лошото“. Генерирањето навистина случаен број е исклучително тежок проблем, дури и на еден компјутер, и долго време го проучуваат криптографите. Па, во децентрализираните мрежи, генерирањето на случајни броеви е уште покомплексно и поважно.
Токму во мрежите каде што учесниците не си веруваат едни на други, способноста да генерираме неоспорен случаен број ни овозможува ефективно да решиме многу критични проблеми и значително да ги подобриме постоечките шеми. Згора на тоа, коцкањето и лотариите не се цел број еден овде, како што на неискусниот читател може да му изгледа на почетокот.
Генерирање на случаен број
Компјутерите не можат сами да генерираат случајни броеви; тие бараат надворешна помош за тоа. Компјутерот може да добие некоја случајна вредност од, на пример, движењата на глувчето, количината на меморија што се користи, заскитаните струи на игличките на процесорот и многу други извори наречени извори на ентропија. Самите овие вредности не се сосема случајни, бидејќи се во одреден опсег или имаат предвидлива шема на промени. За да се претворат таквите броеви во навистина случаен број во даден опсег, на нив се применуваат криптотрансформации за да се произведат рамномерно распределени псевдо-случајни вредности од нерамномерно распределените вредности на изворот на ентропија. Добиените вредности се нарекуваат псевдослучајни затоа што не се навистина случајни, туку детерминистички се изведени од ентропија. Секој добар криптографски алгоритам, при шифрирање на податоци, произведува шифрирани текстови кои треба статистички да не се разликуваат од случајна секвенца, така што за да се произведе случајност можете да земете извор на ентропија, кој обезбедува само добра повторливост и непредвидливост на вредностите дури и во мали опсези. остатокот од работата е дисперзирање и мешање на битови во Добиената вредност ќе биде преземена од алгоритамот за шифрирање.
За комплетирање на кратка едукативна програма, ќе додадам дека генерирањето случајни броеви дури и на еден уред е еден од столбовите за обезбедување на безбедноста на нашите податоци.Генерираните псевдослучајни броеви се користат при воспоставување безбедни врски во различни мрежи, за генерирање криптографски клучеви, за балансирање на оптоварување, следење на интегритетот и за многу други апликации. Безбедноста на многу протоколи зависи од способноста да се генерира сигурен, надворешно непредвидлив случаен случај, да се складира и да не се открие до следниот чекор од протоколот, инаку безбедноста ќе биде загрозена. Нападот на генератор на псевдослучајни вредности е крајно опасен и веднаш го загрозува целиот софтвер што користи генерирање случајност.
Сето ова треба да го знаете доколку сте посетувале основен курс за криптографија, па да продолжиме со децентрализираните мрежи.
Случајно во блокчејн
Пред сè, ќе зборувам за блокчејнови со поддршка за паметни договори; тие се оние кои можат целосно да ги искористат можностите што ги дава висококвалитетната, непобитна случајност. Понатаму, за краткост, оваа технологија ќе ја наречам „Јавно проверливи случајни светилници” или PVRB. Бидејќи блокчејновите се мрежи во кои информациите може да бидат потврдени од кој било учесник, клучниот дел од името е „Јавно проверлив“, т.е. Секој може да користи пресметки за да добие доказ дека добиениот број објавен на блокчејн ги има следните својства:
- Резултатот мора да има докажливо униформа дистрибуција, т.е. да се заснова на докажано силна криптографија.
- Не е можно да се контролира ниту еден дел од резултатот. Како последица на тоа, исходот не може да се предвиди однапред.
- Не можете да го саботирате протоколот за генерирање со тоа што не учествувате во протоколот или со преоптоварување на мрежата со пораки за напад
- Сите горенаведени мора да бидат отпорни на договарање на дозволен број нечесни учесници во протоколот (на пример, 1/3 од учесниците).
Секоја можност на помала група учесници во дослух да произведе дури и контролирана пар/непар случаен избор е безбедносна дупка. Секоја способност на групата да го запре издавањето по случаен избор е безбедносна дупка. Генерално, има многу проблеми, а оваа задача не е лесна...
Се чини дека најважната апликација за PVRB се разни игри, лотарии и генерално секаков вид на коцкање на блокчејн. Навистина, ова е важна насока, но случајноста во блокчејновите има уште поважни апликации. Ајде да ги погледнеме.
Алгоритми за консензус
PVRB игра огромна улога во организирањето на мрежниот консензус. Трансакциите во блокчејновите се заштитени со електронски потпис, така што „напад на трансакција“ секогаш е вклучување/исклучување на трансакција во блок (или неколку блокови). А главната задача на алгоритмот за консензус е да се договори за редоследот на овие трансакции и редоследот на блоковите што ги вклучуваат овие трансакции. Исто така, неопходен имот за вистински блокчејн е конечноста - способноста на мрежата да се согласи дека синџирот до финализираниот блок е конечен и никогаш нема да биде исклучен поради појавата на нова вилушка. Обично, за да се согласиме дека блокот е валиден и што е најважно, конечен, потребно е да се соберат потписи од мнозинството производители на блокови (во натамошниот текст БП - блок-производители), што бара барем доставување на блок синџирот до сите БП и дистрибуција на потписи меѓу сите БП. Како што расте бројот на BP, бројот на потребни пораки во мрежата расте експоненцијално, затоа, консензусните алгоритми кои бараат конечност, што се користат на пример во Hyperledger pBFT консензусот, не работат со потребната брзина, почнувајќи од неколку десетици BP, барајќи огромен број на врски.
Ако има непобитен и искрен PVRB во мрежата, тогаш, дури и во наједноставно приближување, може да се избере еден од производителите на блок врз основа на него и да се назначи за „водач“ во текот на еден круг од протоколот. Ако имаме N блок-производители, од кои M: M > 1/2 N се чесни, не цензурирајте трансакции и не го раздвојувајте ланецот за да извршите напад со „двојно трошење“, а потоа користењето рамномерно распределено неоспорено PVRB ќе овозможи избор на чесен лидер со веројатност M / N (M / N > 1/2). Ако на секој лидер му се додели свој временски интервал за време на кој може да произведе блок и да го потврди ланецот, а овие интервали се еднакви временски, тогаш блок синџирот на чесни БП ќе биде подолг од синџирот формиран од злонамерните БП и консензусот Алгоритмот се потпира на должината на синџирот, едноставно ќе го отфрли „лошиот“. Овој принцип на доделување на еднакви делови од време на секој BP првпат беше применет во Graphene (претходникот на EOS) и дозволува повеќето блокови да се затворат со еден потпис, што во голема мера го намалува оптоварувањето на мрежата и овозможува овој консензус да работи исклучително брзо и стабилно. Сепак, мрежата EOS сега мора да користи специјални блокови (Последен неповратен блок), кои се потврдени со потписите на 2/3 BP. Овие блокови служат за да се обезбеди конечност (неможност вилушка со синџир да започне пред последниот Последни неповратен блок).
Исто така, во реални имплементации, шемата на протоколот е посложена - гласањето за предложените блокови се врши во неколку фази за одржување на мрежата во случај на исчезнати блокови и проблеми со мрежата, но дури и земајќи го предвид ова, алгоритмите за консензус што користат PVRB бараат значително помалку пораки помеѓу BP, што овозможува да се направат побрзи од традиционалните PVFT или неговите различни модификации.
Најистакнатиот претставник на ваквите алгоритми: од тимот на Кардано, за кој се вели дека е математички докажлив против дослухот на БП.
Во Ouroboros, PVRB се користи за дефинирање на таканаречениот „распоред на BP“ - распоред според кој на секој BP му е доделен сопствен временски простор за објавување блок. Големата предност на користењето на PVRB е целосната „еднаквост“ на BP (според големината на нивните биланси). Интегритетот на PVRB гарантира дека злонамерните BP не можат да го контролираат распоредот на временските слотови и затоа не можат да манипулираат со ланецот со подготовка и анализа на вилушките на ланецот однапред, а за да изберете вилушка, доволно е едноставно да се потпрете на должината на синџир, без користење на незгодни начини за пресметување на „корисноста“ на БП и „тежината“ на неговите блокови.
Општо земено, во сите случаи кога треба да се избере случаен учесник во децентрализирана мрежа, PVRB е скоро секогаш најдобриот избор, наместо детерминистичка опција заснована, на пример, на блок хаш. Без PVRB, способноста да се влијае на изборот на учесникот води до напади во кои напаѓачот може да избере од повеќе фјучерси да го избере следниот корумпиран учесник или неколку одеднаш за да обезбеди поголем удел во одлуката. Употребата на PVRB ги дискредитира овие типови на напади.
Скалирање и балансирање на оптоварување
PVRB може да биде од голема корист и во задачи како што се намалување на оптоварувањето и скалирање на плаќање. За почеток, има смисла да се запознаете Ривеста „Влезници за електронска лотарија како микроплаќања“. Општата идеја е дека наместо да вршите уплати од 100 1c од исплатувачот до примачот, можете да играте чесна лотарија со награда од 1$ = 100c, каде што исплатувачот и дава на банката еден од 1 од неговите „лотарии“ за секој 100c плаќање. Еден од овие тикети добива тегла од 1 долар, а токму тој билет може да го сними примачот во блокчејнот. Најважно е што преостанатите 99 билети се префрлаат помеѓу примачот и исплатувачот без никакво надворешно учество, преку приватен канал и со која било посакувана брзина. Може да се прочита добар опис на протоколот заснован на оваа шема на мрежата Емеркоин .
Оваа шема има неколку проблеми, како на пример, примачот може да престане да му служи на исплатувачот веднаш по добивањето добитен тикет, но за многу специјални апликации, како што се наплата во минута или електронски претплати на услуги, тие може да се занемарат. Главниот услов, се разбира, е интегритетот на лотаријата, а за нејзино спроведување PVRB е апсолутно неопходен.
Изборот на случаен учесник е исто така исклучително важен за протоколите за споделување, чија цел е хоризонтално да го размери блок синџирот, дозволувајќи им на различни BP да го обработуваат само нивниот опсег на трансакции. Ова е исклучително тешка задача, особено во однос на безбедноста при спојување на парчиња. Правичен избор на случаен БП со цел да се назначат одговорните за одреден дел, како во алгоритмите за консензус, исто така е задача на PVRB. Во централизираните системи, фрагментите се доделуваат од страна на балансерот; тој едноставно го пресметува хашот од барањето и го испраќа до потребниот извршител. Во блокчејновите, способноста да се влијае на оваа задача може да доведе до напад на консензус. На пример, содржината на трансакциите може да ја контролира напаѓачот, тој може да контролира кои трансакции одат во фрагментот што тој го контролира и да манипулира со синџирот на блокови во него. Можете да прочитате дискусија за проблемот со користење на случајни броеви за споделување задачи во Ethereum
Sharding е еден од најамбициозните и најсериозните проблеми во областа на blockchain; неговото решение ќе овозможи изградба на децентрализирани мрежи со фантастични перформанси и волумен. PVRB е само еден од важните блокови за негово решавање.
Игри, економски протоколи, арбитража
Улогата на случајните броеви во индустријата за игри е тешко да се прецени. Експлицитната употреба во онлајн казина и имплицитната употреба при пресметување на ефектите од акцијата на играчот се сите исклучително тешки проблеми за децентрализираните мрежи, каде што не постои начин да се потпреме на централен извор на случајност. Но, случаен избор може да реши и многу економски проблеми и да помогне да се изградат поедноставни и поефикасни протоколи. Да претпоставиме дека во нашиот протокол има спорови за плаќање за некои евтини услуги, а овие спорови се случуваат доста ретко. Во овој случај, ако постои неоспорен PVRB, клиентите и продавачите можат да се согласат да ги решат споровите по случаен избор, но со дадена веројатност. На пример, со 60% веројатност победува клиентот, а со 40% веројатност победува продавачот. Овој пристап, кој е апсурден од прва гледна точка, ви овозможува автоматски да ги решавате споровите со прецизно предвидлив удел на победи/порази, што им одговара на двете страни без никакво учество на трето лице и непотребно губење време. Покрај тоа, односот на веројатност може да биде динамичен и да зависи од некои глобални променливи. На пример, ако една компанија работи добро, има мал број спорови и висока профитабилност, компанијата може автоматски да ја префрли веројатноста за решавање на спорот кон клиент-центричност, на пример 70/30 или 80/20, и обратно, ако споровите бараат многу пари и се лажни или несоодветни, можете да ја префрлите веројатноста во друга насока.
Голем број интересни децентрализирани протоколи, како што се токени курирани регистри, пазари за предвидување, криви за поврзување и многу други, се економски игри во кои доброто однесување се наградува, а лошото однесување се казнува. Тие често содржат безбедносни проблеми за кои заштитата е во конфликт една со друга. Она што е заштитено од напад од „китови“ со милијарди токени („голем влог“) е ранливо на напади од илјадници сметки со мали салда („сибилски удел“) и мерки преземени против еден напад, како што се не- Линеарните такси создадени за да се направи работата со голем удел непрофитабилна обично се дискредитираат со друг напад. Бидејќи зборуваме за економска игра, соодветните статистички тежини може да се пресметаат однапред, и едноставно да се заменат провизиите со рандомизирани со соодветна распределба. Ваквите веројатни провизии се спроведуваат исклучително едноставно ако блокчејнот има сигурен извор на случајност и не бара никакви сложени пресметки, што го отежнува животот и на китовите и на сибилите.
Во исто време, неопходно е да продолжиме да запомнуваме дека контролата над еден бит во оваа случајност ви овозможува да измамите, намалувајќи ги и зголемувајќи ги веројатностите за половина, така што искрениот PVRB е најважната компонента на таквите протоколи.
Каде да се најде вистинскиот случаен избор?
Теоретски, фер случаен избор во децентрализирани мрежи го прави речиси секој протокол докажливо безбеден од дослух. Образложението е прилично едноставно - ако мрежата се согласи за еден 0 или 1 бит, а помалку од половина од учесниците се неискрени, тогаш, со оглед на доволно повторувања, мрежата е загарантирана да постигне консензус за тој бит со фиксна веројатност. Едноставно затоа што искрен случаен избор ќе избере 51 од 100 учесници 51% од времето. Но, ова е во теорија, бидејќи ... во реални мрежи, за да се обезбеди такво ниво на безбедност како во написите, потребни се многу пораки помеѓу домаќините, сложена криптографија со повеќе премини, а секоја компликација на протоколот веднаш додава нови вектори за напад.
Затоа сè уште не гледаме докажано отпорно PVRB во блокчејновите, кое би се користело доволно време за да се тестира со реални апликации, повеќекратни ревизии, оптоварувања и секако, вистински напади, без кои е тешко да се нарече производ навистина безбеден.
Сепак, постојат неколку ветувачки пристапи, тие се разликуваат во многу детали, а еден од нив дефинитивно ќе го реши проблемот. Со современите компјутерски ресурси, криптографската теорија може доста паметно да се преведе во практични апликации. Во иднина, со задоволство ќе зборуваме за имплементации на PVRB: сега има неколку од нив, секој има свој сет на важни својства и карактеристики за имплементација, а зад секоја има добра идеја. Нема многу тимови вклучени во рандомизацијата, а искуството на секој од нив е исклучително важно за сите други. Се надеваме дека нашите информации ќе им овозможат на другите тимови да се движат побрзо, земајќи го предвид искуството на нивните претходници.
Извор: www.habr.com