Pagpapakilala
"Masyadong mahalaga ang random na pagbuo ng mga numero para ipaubaya sa pagkakataon."
Robert Cavue, 1970
Ang artikulong ito ay nakatuon sa praktikal na aplikasyon ng mga solusyon gamit ang collective random number generation sa isang hindi pinagkakatiwalaang kapaligiran. Sa madaling salita, paano at bakit random ang ginagamit sa mga blockchain, at kaunti tungkol sa kung paano makilala ang "mabuti" na random mula sa "masama". Ang pagbuo ng isang tunay na random na numero ay isang napakahirap na problema, kahit na sa isang computer, at matagal nang pinag-aralan ng mga cryptographer. Well, sa mga desentralisadong network, ang pagbuo ng mga random na numero ay mas kumplikado at mahalaga.
Nasa mga network kung saan ang mga kalahok ay hindi nagtitiwala sa isa't isa na ang kakayahang makabuo ng hindi mapag-aalinlanganang random na numero ay nagbibigay-daan sa amin na epektibong malutas ang maraming kritikal na problema at makabuluhang mapabuti ang mga kasalukuyang scheme. Bukod dito, ang pagsusugal at mga loterya ay hindi ang numero unong layunin dito, dahil ito ay tila sa una sa walang karanasan na mambabasa.
Random na pagbuo ng numero
Ang mga computer ay hindi makakabuo ng mga random na numero sa kanilang sarili; nangangailangan sila ng tulong sa labas upang magawa ito. Ang computer ay maaaring makakuha ng ilang random na halaga mula sa, halimbawa, mga paggalaw ng mouse, ang dami ng memory na ginamit, ligaw na alon sa mga pin ng processor, at marami pang ibang pinagmumulan na tinatawag na entropy sources. Ang mga halagang ito mismo ay hindi ganap na random, dahil ang mga ito ay nasa isang tiyak na saklaw o may predictable pattern ng mga pagbabago. Upang gawing tunay na random na numero ang mga naturang numero sa loob ng isang naibigay na hanay, ang mga cryptotransformation ay inilalapat sa mga ito upang makabuo ng pantay na ipinamahagi na pseudo-random na mga halaga mula sa hindi pantay na ipinamamahagi na mga halaga ng pinagmulan ng entropy. Ang mga resultang halaga ay tinatawag na pseudorandom dahil hindi sila tunay na random, ngunit deterministikong nagmula sa entropy. Anumang mahusay na cryptographic algorithm, kapag nag-encrypt ng data, ay gumagawa ng mga ciphertext na dapat na hindi matukoy sa istatistika mula sa isang random na pagkakasunud-sunod, upang makagawa ng randomness maaari kang kumuha ng isang mapagkukunan ng entropy, na nagbibigay lamang ng mahusay na repeatability at unpredictability ng mga halaga kahit na sa maliliit na saklaw, ang Ang natitirang bahagi ng trabaho ay nagkakalat at naghahalo ng mga piraso sa Ang resultang halaga ay kukunin ng algorithm ng pag-encrypt.
Upang makumpleto ang isang maikling programang pang-edukasyon, idaragdag ko na ang pagbuo ng mga random na numero kahit sa isang device ay isa sa mga haligi ng pagtiyak ng seguridad ng aming data. Ang mga nabuong pseudo-random na numero ay ginagamit kapag nagtatatag ng mga secure na koneksyon sa iba't ibang network, upang makabuo ng cryptographic key, para sa load balancing, integrity monitoring, at para sa marami pang application. Ang seguridad ng maraming mga protocol ay nakasalalay sa kakayahang makabuo ng isang maaasahang, panlabas na hindi mahulaan na random, iimbak ito, at hindi ibunyag ito hanggang sa susunod na hakbang ng protocol, kung hindi man ay makompromiso ang seguridad. Ang pag-atake sa isang pseudorandom value generator ay lubhang mapanganib at agad na nagbabanta sa lahat ng software na gumagamit ng randomness generation.
Dapat mong malaman ang lahat ng ito kung kumuha ka ng pangunahing kurso sa cryptography, kaya magpatuloy tayo tungkol sa mga desentralisadong network.
Random sa mga blockchain
Una sa lahat, pag-uusapan ko ang tungkol sa mga blockchain na may suporta para sa mga matalinong kontrata; sila ang mga ganap na maaaring samantalahin ang mga pagkakataon na ibinigay ng mataas na kalidad, hindi maikakaila na randomness. Dagdag pa, para sa maikli, tatawagin ko ang teknolohiyang ito na "Mga Random na Beacon na Nabe-verify ng Publikoβ o PVRB. Dahil ang mga blockchain ay mga network kung saan ang impormasyon ay maaaring ma-verify ng sinumang kalahok, ang pangunahing bahagi ng pangalan ay "Publicly Verifiable", i.e. Kahit sino ay maaaring gumamit ng mga kalkulasyon upang makakuha ng patunay na ang resultang numero na naka-post sa blockchain ay may mga sumusunod na katangian:
- Ang resulta ay dapat na may napatunayang pare-parehong pamamahagi, ibig sabihin, ay batay sa napatunayang malakas na cryptography.
- Hindi posible na kontrolin ang alinman sa mga piraso ng resulta. Bilang resulta, ang kinalabasan ay hindi mahulaan nang maaga.
- Hindi mo maaaring sabotahe ang generation protocol sa pamamagitan ng hindi pagsali sa protocol o sa pamamagitan ng overloading sa network ng mga mensahe ng pag-atake
- Ang lahat ng nasa itaas ay dapat na lumalaban sa pakikipagsabwatan ng isang pinahihintulutang bilang ng mga hindi tapat na kalahok sa protocol (halimbawa, 1/3 ng mga kalahok).
Ang anumang posibilidad ng isang nakikipagsabwatan na menor de edad na grupo ng mga kalahok na makagawa ng kahit na isang kontroladong even/odd random ay isang security hole. Ang anumang kakayahan ng grupo na ihinto ang pagpapalabas ng random ay isang butas ng seguridad. Sa pangkalahatan, maraming problema, at ang gawaing ito ay hindi madali...
Tila ang pinakamahalagang aplikasyon para sa PVRB ay iba't ibang mga laro, lottery, at sa pangkalahatan ay anumang uri ng pagsusugal sa blockchain. Sa katunayan, ito ay isang mahalagang direksyon, ngunit ang randomness sa mga blockchain ay may mas mahalagang mga aplikasyon. Tingnan natin sila.
Mga Algorithm ng Pinagkasunduan
Malaki ang papel ng PVRB sa pag-oorganisa ng consensus ng network. Ang mga transaksyon sa mga blockchain ay protektado ng isang elektronikong lagda, kaya ang "pag-atake sa isang transaksyon" ay palaging ang pagsasama/pagbubukod ng isang transaksyon sa isang bloke (o ilang mga bloke). At ang pangunahing gawain ng consensus algorithm ay sumang-ayon sa pagkakasunud-sunod ng mga transaksyong ito at ang pagkakasunud-sunod ng mga bloke na kinabibilangan ng mga transaksyong ito. Gayundin, ang isang kinakailangang pag-aari para sa mga tunay na blockchain ay finality - ang kakayahan ng network na sumang-ayon na ang chain hanggang sa finalized block ay pinal, at hinding-hindi isasama dahil sa hitsura ng isang bagong tinidor. Karaniwan, upang sumang-ayon na ang isang bloke ay wasto at, pinaka-mahalaga, pangwakas, ito ay kinakailangan upang mangolekta ng mga lagda mula sa karamihan ng mga block producer (mula dito ay tinutukoy bilang BP - block-producer), na nangangailangan ng hindi bababa sa paghahatid ng block chain sa lahat ng BP, at pamamahagi ng mga lagda sa pagitan ng lahat ng BP . Habang lumalaki ang bilang ng mga BP, ang bilang ng mga kinakailangang mensahe sa network ay lumalaki nang husto, samakatuwid, ang mga algorithm ng pinagkasunduan na nangangailangan ng finality, na ginagamit halimbawa sa consensus ng Hyperledger pBFT, ay hindi gumagana sa kinakailangang bilis, simula sa ilang dosenang BP, na nangangailangan isang malaking bilang ng mga koneksyon.
Kung mayroong isang hindi maikakaila at tapat na PVRB sa network, kung gayon, kahit na sa pinakasimpleng pagtatantya, ang isa ay maaaring pumili ng isa sa mga block producer batay dito at italaga siya bilang "pinuno" sa isang pag-ikot ng protocol. Kung meron tayo N block producer, kung saan M: M > 1/2 N ay tapat, huwag i-censor ang mga transaksyon at huwag i-fork ang kadena upang magsagawa ng "double spend" na pag-atake, pagkatapos ay ang paggamit ng pantay na ipinamahagi na hindi hinahamon na PVRB ay magbibigay-daan sa pagpili ng isang matapat na pinuno na may posibilidad M / N (M / N > 1/2). Kung ang bawat pinuno ay itinalaga ng kanyang sariling agwat ng oras kung saan makakagawa siya ng isang bloke at mapatunayan ang kadena, at ang mga agwat na ito ay pantay sa oras, kung gayon ang block chain ng mga matapat na BP ay magiging mas mahaba kaysa sa kadena na nabuo ng mga malisyosong BP, at ang pinagkasunduan. umaasa ang algorithm sa haba ng chain. itatapon lang ang "masamang". Ang prinsipyong ito ng paglalaan ng pantay na hiwa ng oras sa bawat BP ay unang inilapat sa Graphene (ang hinalinhan ng EOS), at nagbibigay-daan sa karamihan ng mga bloke na isara gamit ang isang pirma, na lubos na nakakabawas sa pagkarga ng network at nagbibigay-daan sa consensus na ito na gumana nang napakabilis at tuloy-tuloy. Gayunpaman, ang EOS network ay kailangan na ngayong gumamit ng mga espesyal na bloke (Last Irreversible Block), na kinumpirma ng mga lagda ng 2/3 BP. Ang mga bloke na ito ay nagsisilbi upang matiyak ang pagiging wakas (ang imposibilidad ng isang chain fork na nagsisimula bago ang huling Huling Irreversible Block).
Gayundin, sa mga totoong pagpapatupad, ang scheme ng protocol ay mas kumplikado - ang pagboto para sa mga iminungkahing bloke ay isinasagawa sa ilang mga yugto upang mapanatili ang network kung sakaling may mga nawawalang mga bloke at mga problema sa network, ngunit kahit na isinasaalang-alang ito, ang mga algorithm ng pinagkasunduan gamit ang PVRB ay nangangailangan makabuluhang mas kaunting mga mensahe sa pagitan ng mga BP, na ginagawang posible na gawing mas mabilis ang mga ito kaysa sa tradisyonal na PVFT, o sa iba't ibang pagbabago nito.
Ang pinakatanyag na kinatawan ng naturang mga algorithm: mula sa koponan ng Cardano, na sinasabing mathematically provable laban sa BP collusion.
Sa Ouroboros, ang PVRB ay ginagamit upang tukuyin ang tinatawag na "BP ββschedule" - isang iskedyul ayon sa kung saan ang bawat BP ay itinalaga ng sarili nitong time slot para sa pag-publish ng block. Ang malaking bentahe ng paggamit ng PVRB ay ang kumpletong "pagkakapantay-pantay" ng mga BP (ayon sa laki ng kanilang mga balanse). Tinitiyak ng integridad ng PVRB na hindi makokontrol ng mga nakakahamak na BP ang pag-iskedyul ng mga puwang ng oras, at samakatuwid ay hindi maaaring manipulahin ang chain sa pamamagitan ng paghahanda at pagsusuri ng mga tinidor ng chain nang maaga, at upang pumili ng isang tinidor sapat na ang umasa lamang sa haba ng chain, nang hindi gumagamit ng mga nakakalito na paraan upang kalkulahin ang "utility" ng BP at "weight" ng mga block nito.
Sa pangkalahatan, sa lahat ng kaso kung saan kailangang pumili ng random na kalahok sa isang desentralisadong network, ang PVRB ay halos palaging ang pinakamahusay na pagpipilian, sa halip na isang mapagpasyang opsyon batay sa, halimbawa, isang block hash. Kung walang PVRB, ang kakayahang maimpluwensyahan ang pagpili ng isang kalahok ay humahantong sa mga pag-atake kung saan ang umaatake ay maaaring pumili mula sa maraming hinaharap upang piliin ang susunod na tiwaling kalahok o ilan nang sabay-sabay upang matiyak ang mas malaking bahagi sa desisyon. Ang paggamit ng PVRB ay sumisira sa mga ganitong uri ng pag-atake.
Pag-scale at pagbabalanse ng load
Ang PVRB ay maaari ding maging malaking pakinabang sa mga gawain tulad ng pagbabawas ng load at pag-scale ng pagbabayad. Upang magsimula, makatuwiran na maging pamilyar sa iyong sarili Rivesta "Mga Electronic Lottery Ticket bilang Micropayments". Ang pangkalahatang ideya ay na sa halip na gumawa ng 100 1c na mga pagbabayad mula sa nagbabayad sa tatanggap, maaari kang maglaro ng isang tapat na lottery na may premyo na 1$ = 100c, kung saan ang nagbabayad ay nagbibigay sa bangko ng isa sa 1 sa kanyang "mga tiket sa lottery" para sa bawat isa. 100c pagbabayad. Ang isa sa mga tiket na ito ay nanalo ng isang garapon na $1, at ang tiket na ito ang maaaring itala ng tatanggap sa blockchain. Ang pinakamahalagang bagay ay ang natitirang 99 na mga tiket ay inilipat sa pagitan ng tatanggap at nagbabayad nang walang anumang panlabas na pakikilahok, sa pamamagitan ng isang pribadong channel at sa anumang nais na bilis. Ang isang mahusay na paglalarawan ng protocol batay sa scheme na ito sa Emercoin network ay mababasa .
Ang scheme na ito ay may ilang mga problema, tulad ng ang tatanggap ay maaaring huminto sa paglilingkod sa nagbabayad kaagad pagkatapos matanggap ang isang nanalong tiket, ngunit para sa maraming mga espesyal na aplikasyon, tulad ng bawat minutong pagsingil o mga elektronikong subscription sa mga serbisyo, ang mga ito ay maaaring mapabayaan. Ang pangunahing kinakailangan, siyempre, ay ang pagiging patas ng loterya, at para sa pagpapatupad nito ang isang PVRB ay talagang kinakailangan.
Napakahalaga din ng pagpili ng random na kalahok para sa sharding protocol, ang layunin nito ay pahalang na sukatin ang block chain, na nagpapahintulot sa iba't ibang BP na iproseso lamang ang kanilang saklaw ng mga transaksyon. Ito ay isang napakahirap na gawain, lalo na sa mga tuntunin ng seguridad kapag pinagsasama ang mga shards. Ang patas na pagpili ng isang random na BP para sa layunin ng pagtatalaga ng mga responsable para sa isang partikular na shard, tulad ng sa mga algorithm ng pinagkasunduan, ay ang gawain din ng PVRB. Sa mga sentralisadong sistema, ang mga shards ay itinalaga ng isang balancer; kinakalkula lamang nito ang hash mula sa kahilingan at ipinapadala ito sa kinakailangang tagapagpatupad. Sa mga blockchain, ang kakayahang maimpluwensyahan ang takdang-aralin na ito ay maaaring humantong sa isang pag-atake sa pinagkasunduan. Halimbawa, ang mga nilalaman ng mga transaksyon ay maaaring kontrolin ng isang umaatake, maaari niyang kontrolin kung aling mga transaksyon ang mapupunta sa shard na kinokontrol niya at manipulahin ang kadena ng mga bloke sa loob nito. Maaari kang magbasa ng talakayan tungkol sa problema ng paggamit ng mga random na numero para sa mga gawain sa sharding sa Ethereum
Ang Sharding ay isa sa mga pinaka-ambisyoso at seryosong problema sa larangan ng blockchain; ang solusyon nito ay magbibigay-daan sa pagbuo ng mga desentralisadong network ng kamangha-manghang pagganap at dami. Ang PVRB ay isa lamang sa mga mahahalagang bloke upang malutas ito.
Mga laro, pang-ekonomiyang protocol, arbitrasyon
Ang papel na ginagampanan ng mga random na numero sa industriya ng paglalaro ay mahirap i-overestimate. Ang tahasang paggamit sa mga online na casino, at ang tahasang paggamit kapag kinakalkula ang mga epekto ng aksyon ng isang manlalaro ay lahat ng napakahirap na problema para sa mga desentralisadong network, kung saan walang paraan upang umasa sa isang pangunahing pinagmumulan ng randomness. Ngunit ang random na pagpili ay maaari ding malutas ang maraming problema sa ekonomiya at makakatulong sa pagbuo ng mas simple at mas mahusay na mga protocol. Ipagpalagay na sa aming protocol ay may mga hindi pagkakaunawaan tungkol sa pagbabayad para sa ilang murang serbisyo, at ang mga hindi pagkakaunawaan na ito ay madalang mangyari. Sa kasong ito, kung mayroong hindi mapag-aalinlanganang PVRB, maaaring sumang-ayon ang mga customer at nagbebenta na lutasin ang mga hindi pagkakaunawaan nang random, ngunit may ibinigay na posibilidad. Halimbawa, na may 60% na posibilidad na manalo ang kliyente, at may 40% na posibilidad na manalo ang nagbebenta. Ang diskarte na ito, na walang katotohanan mula sa unang punto ng view, ay nagbibigay-daan sa iyong awtomatikong lutasin ang mga hindi pagkakaunawaan na may isang tiyak na predictable na bahagi ng mga panalo/pagkatalo, na nababagay sa parehong partido nang walang anumang partisipasyon ng isang third party at hindi kinakailangang pag-aaksaya ng oras. Bukod dito, ang probability ratio ay maaaring maging dynamic at depende sa ilang mga global variable. Halimbawa, kung ang isang kumpanya ay gumagana nang maayos, may mababang bilang ng mga hindi pagkakaunawaan at mataas na kakayahang kumita, ang kumpanya ay maaaring awtomatikong ilipat ang posibilidad ng paglutas ng isang hindi pagkakaunawaan patungo sa customer-centricity, halimbawa 70/30 o 80/20, at vice versa, kung ang mga pagtatalo ay tumatagal ng maraming pera at mapanlinlang o hindi sapat, maaari mong ilipat ang posibilidad sa kabilang direksyon.
Ang malaking bilang ng mga kawili-wiling desentralisadong protocol, tulad ng mga token curated registries, prediction market, bonding curves at marami pang iba, ay mga larong pang-ekonomiya kung saan ang mabuting pag-uugali ay ginagantimpalaan at ang masamang pag-uugali ay pinarusahan. Madalas na naglalaman ang mga ito ng mga problema sa seguridad kung saan ang mga proteksyon ay sumasalungat sa isa't isa. Ano ang protektado mula sa isang pag-atake ng "mga balyena" na may bilyun-bilyong mga token ("malaking taya") ay mahina sa mga pag-atake ng libu-libong mga account na may maliliit na balanse ("sybil stake"), at mga hakbang na ginawa laban sa isang pag-atake, tulad ng hindi- Ang mga linear na bayarin na ginawa upang gawing hindi kumikita ang pagtatrabaho sa isang malaking stake ay kadalasang sinisiraan ng isa pang pag-atake. Dahil pinag-uusapan natin ang tungkol sa isang pang-ekonomiyang laro, ang kaukulang mga istatistikal na timbang ay maaaring kalkulahin nang maaga, at palitan lamang ang mga komisyon ng mga randomized na may naaangkop na pamamahagi. Ang ganitong mga probabilistikong komisyon ay ipinatupad nang napakasimple kung ang blockchain ay may maaasahang pinagmumulan ng randomness at hindi nangangailangan ng anumang kumplikadong mga kalkulasyon, na nagpapahirap sa buhay para sa parehong mga balyena at sybil.
Kasabay nito, kinakailangang patuloy na tandaan na ang kontrol sa isang bit sa randomness na ito ay nagbibigay-daan sa iyo na manloko, bawasan at dagdagan ang mga probabilidad ng kalahati, kaya ang isang matapat na PVRB ay ang pinakamahalagang bahagi ng naturang mga protocol.
Saan mahahanap ang tamang random?
Sa teorya, ang patas na random na pagpili sa mga desentralisadong network ay ginagawang ligtas ang halos anumang protocol laban sa sabwatan. Ang katwiran ay medyo simple - kung ang network ay sumang-ayon sa isang solong 0 o 1 bit, at mas mababa sa kalahati ng mga kalahok ay hindi tapat, kung gayon, sa sapat na mga pag-ulit, ang network ay garantisadong maabot ang isang pinagkasunduan sa bit na iyon na may isang nakapirming posibilidad. Dahil lang sa isang matapat na random na pipili ng 51 sa 100 kalahok 51% ng oras. Ngunit ito ay nasa teorya, dahil... sa mga totoong network, upang matiyak ang antas ng seguridad tulad ng sa mga artikulo, maraming mensahe sa pagitan ng mga host, kailangan ang kumplikadong multi-pass cryptography, at anumang komplikasyon ng protocol ay agad na nagdaragdag ng mga bagong attack vector.
Iyon ang dahilan kung bakit hindi pa namin nakikita ang isang napatunayang lumalaban na PVRB sa mga blockchain, na gagamitin sana ng sapat na oras upang masuri ng mga tunay na aplikasyon, maraming pag-audit, pag-load, at siyempre, mga tunay na pag-atake, kung wala ito ay mahirap tumawag ng isang tunay na ligtas ang produkto.
Gayunpaman, mayroong maraming mga promising na diskarte, naiiba sila sa maraming mga detalye, at ang isa sa kanila ay tiyak na malulutas ang problema. Gamit ang mga modernong mapagkukunan ng computing, ang teorya ng cryptographic ay maaaring isalin nang matalino sa mga praktikal na aplikasyon. Sa hinaharap, ikalulugod naming pag-usapan ang tungkol sa mga pagpapatupad ng PVRB: mayroon na ngayong ilan sa mga ito, bawat isa ay may sariling hanay ng mahahalagang katangian at tampok sa pagpapatupad, at sa likod ng bawat isa ay may magandang ideya. Walang maraming mga koponan na kasangkot sa randomization, at ang karanasan ng bawat isa sa kanila ay napakahalaga para sa lahat. Umaasa kami na ang aming impormasyon ay magbibigay-daan sa iba pang mga koponan na kumilos nang mas mabilis, na isinasaalang-alang ang karanasan ng kanilang mga nauna.
Pinagmulan: www.habr.com