Pagpapakilala

function getAbsolutelyRandomNumer() {
        return 4; // returns absolutely random number!
}

Tulad ng konsepto ng isang ganap na malakas na cipher mula sa cryptography, ang tunay na "Publicly Verifiable Random Beacon" (simula dito ay PVRB) na mga protocol ay sinusubukan lamang na makalapit hangga't maaari sa perpektong pamamaraan, dahil sa mga totoong network ay hindi ito naaangkop sa dalisay nitong anyo: kinakailangang sumang-ayon nang mahigpit sa isang piraso, dapat mayroong maraming mga pag-ikot, at ang lahat ng mga mensahe ay dapat na ganap na mabilis at palaging naihatid. Siyempre, hindi ito ang kaso sa mga totoong network. Samakatuwid, kapag nagdidisenyo ng mga PVRB para sa mga partikular na gawain sa mga modernong blockchain, bilang karagdagan sa imposibilidad ng pagkontrol sa nagreresultang randomness at lakas ng cryptographic, marami pang puro arkitektura at teknikal na mga problema ang lumitaw.

Para sa PVRB, ang blockchain mismo ay mahalagang isang medium ng komunikasyon kung saan ang mga mensahe = mga transaksyon. Binibigyang-daan ka nitong bahagyang abstract mula sa mga problema sa network, hindi paghahatid ng mga mensahe, mga problema sa middleware - lahat ng mga panganib na ito ay ipinapalagay ng desentralisadong network, at ang pangunahing halaga nito para sa PVRB ay ang kawalan ng kakayahan na bawiin o sirain ang isang naipadala na transaksyon - ginagawa nito hindi pinapayagan ang mga kalahok na tumanggi na lumahok sa protocol, maliban kung nagsagawa sila ng matagumpay na pag-atake sa pinagkasunduan. Ang antas ng seguridad na ito ay katanggap-tanggap, kaya ang PVRB ay dapat na lumalaban sa sabwatan ng mga kalahok sa eksaktong kaparehong lawak ng pangunahing blockchain chain. Gayundin, ito ay nagpapahiwatig na ang PVRB ay dapat maging bahagi ng pinagkasunduan kung ang network ay sumang-ayon sa pangunahing blockchain, kahit na ito ay sumasang-ayon din sa tanging patas na resultang random. O, ang PVRB ay isang standalone na protocol lamang na ipinatupad ng isang matalinong kontrata na gumagana nang asynchronously may kinalaman sa blockchain at mga block. Ang parehong mga pamamaraan ay may kanilang mga pakinabang at disadvantages, at ang pagpili sa pagitan ng mga ito ay lubhang hindi mahalaga.

Dalawang paraan para ipatupad ang PVRB

Ilarawan natin nang mas detalyado ang dalawang opsyon para sa pagpapatupad ng PVRB - ang standalone na bersyon, na gumagana gamit ang isang matalinong kontrata na hiwalay sa blockchain, at ang consensus-integrated na bersyon, na binuo sa protocol, ayon sa kung saan ang network ay sumasang-ayon sa blockchain at ang mga transaksyon na isasama. Sa lahat ng kaso, ang ibig kong sabihin ay mga sikat na blockchain engine: Ethereum, EOS, at lahat ng katulad nila sa paraan ng pagho-host at pagproseso ng mga smart contract.

Nakapag-iisang kontrata

Sa bersyong ito, ang PVRB ay isang matalinong kontrata na tumatanggap ng mga transaksyon ng mga random na producer (mula rito ay tinutukoy bilang RP), pinoproseso ang mga ito, pinagsasama-sama ang mga resulta, at, bilang resulta, nakakarating sa isang tiyak na halaga na maaaring matanggap ng sinumang user mula sa kontratang ito. Ang halagang ito ay maaaring hindi direktang iimbak sa kontrata, ngunit sa halip ay kinakatawan lamang ng data kung saan ang isa at isang halaga lamang ng resultang random ay maaaring tiyak na makuha. Sa pamamaraang ito, ang mga RP ay mga gumagamit ng blockchain, at sinuman ay maaaring payagang lumahok sa proseso ng pagbuo.

Ang opsyon na may standalone na kontrata ay mabuti:

• portability (maaaring i-drag ang mga kontrata mula sa blockchain patungo sa blockchain)
• kadalian ng pagpapatupad at pagsubok (ang mga kontrata ay madaling isulat at subukan)
• kaginhawahan sa pagpapatupad ng mga scheme ng ekonomiya (madaling gumawa ng sarili mong token, na ang lohika ay nagsisilbi sa mga layunin ng PVRB)
• posibilidad ng paglulunsad sa mga gumagana nang blockchain

Mayroon din itong mga disadvantages:

• malakas na limitasyon sa mga mapagkukunan ng pag-compute, dami ng transaksyon at imbakan (sa madaling salita, cpu/mem/io)
• mga paghihigpit sa mga operasyon sa loob ng kontrata (hindi lahat ng mga tagubilin ay magagamit, mahirap ikonekta ang mga panlabas na aklatan)
• kawalan ng kakayahan upang ayusin ang pagmemensahe nang mas mabilis kaysa sa mga transaksyon na kasama sa blockchain

Ang pagpipiliang ito ay angkop para sa pagpapatupad ng isang PVRB na kailangang patakbuhin sa isang umiiral na network, hindi naglalaman ng kumplikadong cryptography at hindi nangangailangan ng malaking bilang ng mga pakikipag-ugnayan.

Pinagsama-sama ang pinagkasunduan

Sa bersyong ito, ipinapatupad ang PVRB sa blockchain node code, built-in o tumatakbo kasabay ng pagpapalitan ng mga mensahe sa pagitan ng mga blockchain node. Direktang isinulat ang mga resulta ng protocol sa mga ginawang bloke, at ipinapadala ang mga mensahe ng protocol sa p2p network sa pagitan ng mga node. Dahil ang protocol ay nagreresulta sa mga numero na isusulat sa mga bloke, ang network ay dapat maabot ang isang pinagkasunduan sa mga ito. Nangangahulugan ito na ang mga mensahe ng PVRB, tulad ng mga transaksyon, ay dapat na ma-validate ng mga node at kasama sa mga bloke upang ma-validate ng sinumang kalahok sa network ang pagsunod sa protocol ng PVRB. Ito ay awtomatikong humahantong sa amin sa malinaw na solusyon - kung ang network ay sumang-ayon sa isang pinagkasunduan tungkol sa isang bloke at mga transaksyon sa loob nito, ang PVRB ay dapat na bahagi ng pinagkasunduan, at hindi isang stand-alone na protocol. Kung hindi man, posibleng valid ang isang block mula sa consensus point of view, ngunit hindi sinusunod ang PVRB protocol, at mula sa PVRB point of view ay hindi matatanggap ang block. Kaya't kung pipiliin ang opsyong "pinagsama-samang pinagkasunduan", ang PVRB ay magiging isang mahalagang bahagi ng pinagkasunduan.

Kapag inilalarawan ang mga pagpapatupad ng PVRB sa antas ng pinagkasunduan ng network, hindi maiiwasan ng isa sa anumang paraan ang mga isyu ng finality. Ang finality ay isang mekanismong ginagamit sa mga deterministikong consensus na nagla-lock sa isang bloke (at ang chain na humahantong dito) na pangwakas at hinding-hindi itatapon, kahit na may magkatulad na tinidor. Halimbawa, sa Bitcoin walang ganoong mekanismo - kung mag-publish ka ng isang chain ng mas kumplikado, papalitan nito ang anumang hindi gaanong kumplikado, anuman ang haba ng mga chain. At sa EOS, halimbawa, ang mga pinal ay ang tinatawag na Last Irreversible Blocks, na lumalabas sa average bawat 432 block (12*21 + 12*15, pre-vote + pre-commit). Ang prosesong ito ay mahalagang naghihintay para sa 2/3 ng mga block-producer (mula rito ay tinutukoy bilang BP) na mga lagda. Kapag lumitaw ang mga tinidor na mas luma kaysa sa huling LIB, itatapon lang ang mga ito. Ginagawang posible ng mekanismong ito na garantiya na ang transaksyon ay kasama sa blockchain at hindi na ibabalik, kahit na anong mga mapagkukunan ang mayroon ang umaatake. Gayundin, ang mga huling bloke ay mga bloke na nilagdaan ng 2/3 BP sa Hyperledger, Tendermint at iba pang mga pinagkasunduan na nakabatay sa pBFT. Gayundin, makatuwirang gumawa ng protocol para sa pagtiyak ng finality na isang add-on sa consensus, dahil maaari itong gumana nang asynchronously sa produksyon at paglalathala ng mga block. Narito ang isang magandang artikulo tungkol sa finality sa Ethereum.

Napakahalaga ng finality para sa mga user, na kung wala ito ay maaaring maging biktima ng "double spend" na pag-atake, kung saan "hinahawakan" ng BP ang mga ito, at ini-publish ang mga ito pagkatapos na "makita" ng network ang isang magandang transaksyon. Kung walang finality, pinapalitan ng na-publish na fork ang block ng isang "maganda" na transaksyon sa isa pa, mula sa isang "masamang" fork, kung saan ang parehong mga pondo ay inililipat sa address ng attacker. Sa kaso ng PVRB, ang mga kinakailangan para sa finality ay mas mahigpit, dahil ang pagbuo ng mga tinidor para sa PVRB ay nangangahulugan ng pagkakataon para sa isang attacker na maghanda ng ilang mga random na opsyon upang mai-publish ang pinaka-pinakinabangang isa, at ang paglilimita sa oras ng isang posibleng pag-atake ay isang magandang solusyon.

Samakatuwid, ang pinakamagandang opsyon ay pagsamahin ang PVRB at finality sa isang protocol - pagkatapos ay ang finalized block = finalized random, at ito mismo ang kailangan naming makuha. Ngayon ang mga manlalaro ay makakatanggap ng garantisadong random sa loob ng N segundo, at makatitiyak na imposibleng ibalik ito o i-replay muli.

Ang opsyon na pinagsama-sama ng pinagkasunduan ay mabuti:

• ang posibilidad ng asynchronous na pagpapatupad na may kaugnayan sa paggawa ng mga bloke - ang mga bloke ay ginawa gaya ng dati, ngunit kahanay nito, ang PVRB protocol ay maaaring gumana, na hindi gumagawa ng randomness para sa bawat bloke
• ang kakayahang magpatupad ng kahit na mabigat na cryptography, nang walang mga paghihigpit na ipinataw sa mga matalinong kontrata
• ang kakayahang ayusin ang pagpapalitan ng mga mensahe nang mas mabilis kaysa sa mga transaksyon ay kasama sa blockchain, halimbawa, ang bahagi ng protocol ay maaaring gumana sa pagitan ng mga node nang hindi namamahagi ng mga mensahe sa network

Mayroon din itong mga disadvantages:

• Mga kahirapan sa pagsubok at pag-unlad - kakailanganin mong tularan ang mga error sa network, mga nawawalang node, mga hard forks sa network
• Ang mga error sa pagpapatupad ay nangangailangan ng network hardfork

Ang parehong paraan ng pagpapatupad ng PVRB ay may karapatang mabuhay, ngunit ang pagpapatupad sa mga matalinong kontrata sa modernong blockchain ay medyo limitado pa rin sa mga mapagkukunan ng pag-compute, at ang anumang paglipat sa seryosong cryptography ay kadalasang imposible. At kakailanganin namin ng seryosong cryptography, tulad ng ipapakita sa ibaba. Kahit na ang problemang ito ay malinaw na pansamantala, ang seryosong cryptography sa mga kontrata ay kailangan upang malutas ang maraming mga problema, at ito ay unti-unting lumilitaw (halimbawa, mga kontrata ng system para sa zkSNARKs sa Ethereum)

Ang Blockchain, na nagbibigay ng isang transparent at maaasahang channel ng pagmemensahe ng protocol, ay hindi ginagawa ito nang libre. Ang anumang desentralisadong protocol ay dapat isaalang-alang ang posibilidad ng isang pag-atake ng Sybil; anumang aksyon ay maaaring gawin ng pinagsama-samang puwersa ng maraming mga account, samakatuwid, kapag nagdidisenyo, kinakailangang isaalang-alang ang kakayahan ng mga umaatake na lumikha ng isang di-makatwirang bilang ng protocol. kalahok na kumikilos sa sabwatan.

PVRB at block variable.

Hindi ako nagsinungaling noong sinabi kong wala pang nagpapatupad ng magandang PVRB, na sinubok ng maraming application sa pagsusugal, sa mga blockchain. Saan nanggagaling ang napakaraming application ng pagsusugal sa Ethereum at EOS? Ito ay sorpresa sa akin gaya ng nakakagulat sa iyo, saan sila nakakuha ng napakaraming "persistent" na random sa isang ganap na deterministikong kapaligiran?

Ang paboritong paraan upang makakuha ng randomness sa blockchain ay ang kumuha ng ilang uri ng "hindi mahuhulaan" na impormasyon mula sa block at gumawa ng random batay dito - sa pamamagitan lamang ng pag-hash ng isa o higit pang mga halaga. Magandang artikulo tungkol sa mga problema ng naturang mga scheme dito. Maaari mong kunin ang alinman sa mga "hindi mahuhulaan" na mga halaga sa block, halimbawa, ang block hash, ang bilang ng mga transaksyon, pagiging kumplikado ng network, at iba pang mga halaga na hindi alam nang maaga. Pagkatapos ay i-hash ang mga ito, isa o higit pa, at, sa teorya, dapat kang makakuha ng isang tunay na random. Maaari mo ring idagdag sa whitipaper na ang iyong scheme ay "post-quantum secure" (dahil mayroong quantum-proof hash functions :)).

Ngunit kahit na ang post-quantum secure na mga hash ay hindi sapat, sayang. Ang sikreto ay nasa mga kinakailangan para sa PVRB, hayaan mo akong ipaalala sa iyo ang mga ito mula sa nakaraang artikulo:

1. Ang resulta ay dapat na may napatunayang pare-parehong pamamahagi, ibig sabihin, ay batay sa napatunayang malakas na cryptography.
2. Hindi posible na kontrolin ang alinman sa mga piraso ng resulta. Bilang resulta, ang kinalabasan ay hindi mahulaan nang maaga.
3. 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
4. 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).

Sa kasong ito, ang kinakailangan 1 lamang ang natutugunan, at ang kinakailangan 2 ay hindi natutugunan. Sa pamamagitan ng pag-hash ng mga hindi mahuhulaan na halaga mula sa bloke, makakakuha tayo ng pare-parehong pamamahagi at magagandang random. Ngunit may opsyon man lang ang BP na "i-publish ang block o hindi." Kaya, ang BP ay maaaring pumili ng hindi bababa sa DALAWANG random na mga pagpipilian: "sa sarili nito" at ang isa na lalabas kung ibang tao ang gumawa ng block. Maaaring "i-snoop" ng BP nang maaga kung ano ang mangyayari kung mag-publish siya ng isang block, at magpasya lang na gawin ito o hindi. Kaya, kapag naglalaro, halimbawa, “even-odd” o “red/black” sa roulette, maaari lang siyang mag-publish ng block kung makakita siya ng panalo. Ginagawa rin nito ang diskarte ng paggamit, halimbawa, ng block hash na "mula sa hinaharap" na hindi gumagana. Sa kasong ito, sinasabi nila na "random ang gagamitin, na nakuha sa pamamagitan ng pag-hash ng kasalukuyang data at ang hash ng isang hinaharap na bloke na may taas na, halimbawa, N + 42, kung saan ang N ay ang kasalukuyang taas ng bloke. Medyo pinalalakas nito ang scheme, ngunit pinapayagan pa rin ang BP, kahit na sa hinaharap, na piliin kung hahawakan ang block o i-publish.

Ang software ng BP sa kasong ito ay nagiging mas kumplikado, ngunit hindi gaanong. Simple lang, kapag nagpapatunay at nagsasama ng isang transaksyon sa isang bloke, mayroong isang mabilis na pagsusuri upang makita kung magkakaroon ng panalo, at, posibleng, pagpili ng isang parameter ng transaksyon upang makakuha ng mataas na posibilidad na manalo. Kasabay nito, halos imposible na mahuli ang isang matalinong BP para sa gayong mga manipulasyon; sa bawat oras na maaari kang gumamit ng mga bagong address at manalo nang paunti-unti nang hindi pumupukaw ng hinala.

Kaya ang mga pamamaraan na gumagamit ng impormasyon mula sa block ay hindi angkop bilang isang unibersal na pagpapatupad ng PVRB. Sa isang limitadong bersyon, na may mga paghihigpit sa mga laki ng taya, mga paghihigpit sa bilang ng mga manlalaro at/o pagpaparehistro ng KYC (upang pigilan ang isang manlalaro na gumamit ng maraming address), ang mga scheme na ito ay maaaring gumana para sa maliliit na laro, ngunit wala nang iba pa.

PVRB at commit-reveal.

Okay, salamat sa pag-hash at hindi bababa sa kamag-anak na unpredictability ng block hash at iba pang mga variable. Kung malulutas mo ang problema ng mga front-running miners, dapat kang makakuha ng mas angkop. Idagdag natin ang mga user sa scheme na ito - hayaang maimpluwensyahan din nila ang pagiging random: sasabihin sa iyo ng sinumang empleyado ng teknikal na suporta na ang pinaka-random na bagay sa mga IT system ay ang mga aksyon ng mga user :)

Ang isang walang muwang na pamamaraan, kapag ang mga gumagamit ay nagpapadala lamang ng mga random na numero at ang resulta ay kinakalkula bilang, halimbawa, isang hash ng kanilang kabuuan, ay hindi angkop. Sa kasong ito, makokontrol ng huling manlalaro, sa pamamagitan ng pagpili ng sarili niyang random, kung ano ang magiging resulta. Ito ang dahilan kung bakit ginagamit ang napakalawak na ginagamit na pattern ng commit-reveal. Ang mga kalahok ay unang nagpapadala ng mga hash mula sa kanilang mga random (nag-commit), at pagkatapos ay buksan ang mga random mismo (nagpapakita). Ang yugto ng "paghahayag" ay magsisimula lamang pagkatapos makolekta ang mga kinakailangang commit, upang maipadala ng mga kalahok ang eksaktong random na hash kung saan sila nagpadala nang mas maaga. Ngayon, ilagay natin ang lahat ng ito kasama ang mga parameter ng isang bloke, at mas mahusay kaysa sa isa na kinuha mula sa hinaharap (ang randomness ay matatagpuan lamang sa isa sa mga hinaharap na bloke), at voila - handa na ang randomness! Ngayon ang sinumang manlalaro ay nakakaimpluwensya sa nagresultang randomness, at maaaring "matalo" ang malisyosong BP sa pamamagitan ng pag-override nito sa kanyang sarili, hindi alam nang maaga, randomness... Maaari ka ring magdagdag ng proteksyon laban sa pagsasabotahe sa protocol sa pamamagitan ng hindi pagbubukas nito sa yugto ng pagbubunyag - simpleng sa pamamagitan ng pag-aatas ng isang tiyak na halaga na ilakip sa transaksyon kapag gumawa ng — isang depositong panseguridad, na ibabalik lamang sa panahon ng paghahayag na pamamaraan. Sa kasong ito, ang paggawa at hindi paglalahad ay magiging hindi kapaki-pakinabang.

Ito ay isang magandang pagtatangka, at ang mga ganitong scheme ay umiiral din sa gaming DApps, ngunit sayang, ito ay muli ay hindi sapat. Ngayon hindi lamang ang minero, kundi pati na rin ang sinumang kalahok sa protocol ay maaaring makaimpluwensya sa resulta. Posible pa ring kontrolin ang halaga mismo, na may mas kaunting pagkakaiba-iba at sa isang gastos, ngunit, tulad ng sa kaso ng minero, kung ang mga resulta ng pagguhit ay mas mahalaga kaysa sa bayad para sa pakikilahok sa PVRB protocol, kung gayon ang random Ang -producer(RP) ay maaaring magpasya kung ihahayag at maaari pa ring pumili mula sa hindi bababa sa dalawang random na pagpipilian.
Ngunit naging posible na parusahan ang mga gumawa at hindi nagbubunyag, at ang pamamaraang ito ay magiging kapaki-pakinabang. Ang pagiging simple nito ay isang seryosong kalamangan - ang mas seryosong mga protocol ay nangangailangan ng mas malakas na mga kalkulasyon.

PVRB at mga deterministikong lagda.

May isa pang paraan para pilitin ang RP na magbigay ng pseudo-random na numero na hindi nito maimpluwensyahan kung ito ay bibigyan ng "preimage" - ito ay isang deterministikong lagda. Ang nasabing lagda ay, halimbawa, RSA, at hindi ECS. Kung ang RP ay may isang pares ng mga susi: RSA at ECC, at pinirmahan niya ang isang tiyak na halaga gamit ang kanyang pribadong susi, kung gayon sa kaso ng RSA ay makakakuha siya ng ISA AT ISANG pirma LAMANG, at sa kaso ng ECS ​​maaari siyang bumuo ng anumang bilang ng iba't ibang wastong lagda. Ito ay dahil kapag lumilikha ng isang pirma ng ECS, isang random na numero ang ginagamit, pinili ng lumagda, at maaari itong mapili sa anumang paraan, na nagbibigay ng pagkakataon sa pumirma na pumili ng isa sa ilang mga lagda. Sa kaso ng RSA: “one input value” + “one key pair” = “one signature”. Imposibleng mahulaan kung anong pirma ang makukuha ng isa pang RP, kaya ang isang PVRB na may mga deterministikong lagda ay maaaring ayusin sa pamamagitan ng pagsasama-sama ng mga lagda ng RSA ng ilang kalahok na pumirma sa parehong halaga. Halimbawa, ang nakaraang random. Ang scheme na ito ay nakakatipid ng maraming mapagkukunan, dahil Ang mga lagda ay parehong kumpirmasyon ng tamang pag-uugali ayon sa protocol at isang pinagmulan ng randomness.

Gayunpaman, kahit na may mga deterministikong lagda, ang pamamaraan ay mahina pa rin sa problema ng "huling aktor". Ang huling kalahok ay maaari pa ring magpasya kung i-publish ang lagda o hindi, sa gayon ay makokontrol ang kalalabasan. Maaari mong baguhin ang scheme, magdagdag ng mga block hashes dito, gumawa ng mga pag-ikot upang ang resulta ay hindi mahulaan nang maaga, ngunit ang lahat ng mga diskarteng ito, kahit na isinasaalang-alang ang maraming mga pagbabago, ay iniiwan pa rin ang hindi nalutas na problema ng impluwensya ng isang kalahok sa kolektibo. magreresulta sa isang hindi pinagkakatiwalaang kapaligiran at maaari lamang gumana sa ilalim ng mga hadlang sa ekonomiya at oras. Bilang karagdagan, ang laki ng mga RSA key (1024 at 2048 bits) ay medyo malaki, at ang laki para sa mga transaksyon sa blockchain ay isang napakahalagang parameter. Tila walang simpleng paraan upang malutas ang problema, magpatuloy tayo.

PVRB at mga pamamaraan ng lihim na pagbabahagi

Sa cryptography, may mga scheme na maaaring magpapahintulot sa network na sumang-ayon sa isa at isa lamang na halaga ng PVRB, habang ang mga naturang scheme ay lumalaban sa anumang malisyosong pagkilos ng ilang kalahok. Ang isang kapaki-pakinabang na protocol na nagkakahalaga ng pamilyar sa iyong sarili ay ang lihim na pamamaraan ng pagbabahagi ni Shamir. Nagsisilbi itong hatiin ang isang lihim (halimbawa, isang lihim na susi) sa ilang bahagi, at ipamahagi ang mga bahaging ito sa N kalahok. Ang sikreto ay ipinamahagi sa paraang M na bahagi ng N ay sapat na upang mabawi ito, at ang mga ito ay maaaring maging anumang M na bahagi. Kung sa mga daliri, pagkatapos ay mayroong isang graph ng isang hindi kilalang function, ang mga kalahok ay nagpapalitan ng mga puntos sa graph, at pagkatapos makatanggap ng mga puntos ng M, ang buong function ay maaaring maibalik.
Isang magandang paliwanag ang ibinigay sa wiki ngunit ang paglalaro nito sa praktikal na paraan upang i-play ang protocol sa iyong ulo ay kapaki-pakinabang para sa demo pahina.

Kung ang pamamaraan ng FSSS (Fiat-Shamir Secret Sharing) ay naaangkop sa dalisay nitong anyo, ito ay magiging isang hindi masisira na PVRB. Sa pinakasimpleng anyo nito, maaaring ganito ang hitsura ng protocol:

• Ang bawat kalahok ay bumubuo ng kanilang sariling random at namamahagi ng mga pagbabahagi mula dito sa iba pang mga kalahok
• Ang bawat kalahok ay nagpapakita ng kanyang bahagi ng mga lihim ng iba pang mga kalahok
• Kung ang isang kalahok ay may higit sa M na pagbabahagi, kung gayon ang bilang ng kalahok na ito ay maaaring kalkulahin, at ito ay magiging kakaiba, anuman ang hanay ng mga nahayag na kalahok
• Ang kumbinasyon ng mga inihayag na random ay ang nais na PVRB

Dito, ang isang indibidwal na kalahok ay hindi na nakakaimpluwensya sa mga resulta ng protocol, maliban sa mga kaso kung saan ang pagkamit ng randomness disclosure threshold ay nakasalalay lamang sa kanya. Samakatuwid, ang protocol na ito, kung mayroong kinakailangang proporsyon ng mga RP na nagtatrabaho sa protocol at magagamit, ay gumagana, nagpapatupad ng mga kinakailangan para sa lakas ng cryptographic, at lumalaban sa problema ng "huling aktor".

Ito ay maaaring isang mainam na opsyon, ang PVRB scheme na ito batay sa lihim na pagbabahagi ng Fiat-Shamir ay inilarawan halimbawa sa ito artikulo. Ngunit, tulad ng nabanggit sa itaas, kung susubukan mong ilapat ito nang direkta sa blockchain, lilitaw ang mga teknikal na limitasyon. Narito ang isang halimbawa ng isang pagsubok na pagpapatupad ng protocol sa EOS smart contract at ang pinakamahalagang bahagi nito - pagsuri sa na-publish na kalahok sa bahagi: kodigo. Makikita mo mula sa code na ang proof validation ay nangangailangan ng ilang scalar multiplications, at ang mga numerong ginamit ay napakalaki. Dapat itong maunawaan na sa mga blockchain, ang pag-verify ay nangyayari sa sandaling pinoproseso ng block-producer ang transaksyon, at sa pangkalahatan, ang sinumang kalahok ay dapat na madaling i-verify ang kawastuhan ng protocol, kaya ang mga kinakailangan para sa bilis ng pag-verify ng function ay napakaseryoso. . Sa pagpipiliang ito, ang opsyon ay naging hindi epektibo, dahil ang pag-verify ay hindi magkasya sa limitasyon ng transaksyon (0.5 segundo).

Ang kahusayan sa pag-verify ay isa sa pinakamahalagang kinakailangan para sa paggamit ng, sa pangkalahatan, ng anumang mga advanced na cryptographic scheme sa blockchain. Paglikha ng mga patunay, paghahanda ng mga mensahe - ang mga pamamaraang ito ay maaaring alisin sa kadena at isagawa sa mga computer na may mataas na pagganap, ngunit hindi maaaring lampasan ang pag-verify - ito ay isa pang mahalagang kinakailangan para sa PVRB.

PVRB at mga lagda ng threshold

Sa pagiging pamilyar sa pamamaraan ng lihim na pagbabahagi, natuklasan namin ang isang buong klase ng mga protocol na pinagsama ng keyword na "threshold". Kapag ang pagsisiwalat ng ilang impormasyon ay nangangailangan ng partisipasyon ng M matapat na kalahok mula sa N, at ang hanay ng mga tapat na kalahok ay maaaring maging isang arbitrary na subset ng N, nagsasalita kami ng mga "threshold" na mga scheme. Sila ang nagpapahintulot sa amin na harapin ang problema ng "huling aktor", ngayon kung hindi ibunyag ng umaatake ang kanyang bahagi ng lihim, isa pa, matapat na kalahok ang gagawa para sa kanya. Ang mga scheme na ito ay nagbibigay-daan sa pagsang-ayon sa isa at isa lamang na kahulugan, kahit na ang protocol ay sinasabotahe ng ilan sa mga kalahok.

Ang kumbinasyon ng mga deterministikong lagda at mga iskema ng threshold ay naging posible na bumuo ng isang napaka-maginhawa at promising na pamamaraan para sa pagpapatupad ng PVRB - ito ay mga deterministikong lagda ng threshold. Dito artikulo tungkol sa iba't ibang gamit ng mga lagda ng threshold, at narito ang isa pang magandang longread galing ni Dash.

Inilalarawan ng huling artikulo ang mga lagda ng BLS (Ang BLS ay nangangahulugang Boneh-Lynn-Shacham, dito artikulo), na may napakahalaga at lubos na maginhawang kalidad para sa mga programmer - pampubliko, lihim, pampublikong mga susi at mga lagda ng BLS ay maaaring pagsamahin sa isa't isa gamit ang mga simpleng operasyong matematika, habang ang kanilang mga kumbinasyon ay nananatiling wastong mga susi at pirma, na nagbibigay-daan sa iyong madaling pagsama-samahin ang marami. mga lagda sa isa at maraming pampublikong susi sa isa. Ang mga ito ay deterministic din at gumagawa ng parehong resulta para sa parehong data ng input. Dahil sa kalidad na ito, ang mga kumbinasyon ng mga pirma ng BLS ay mga wastong susi mismo, na nagbibigay-daan para sa pagpapatupad ng isang opsyon kung saan ang M ng N kalahok ay gumagawa ng isa at isang pirma lamang na deterministiko, pampublikong mabe-verify, at hindi mahuhulaan hanggang sa ito ay buksan ng Mth kalahok.

Sa isang scheme na may mga lagda ng threshold ng BLS, ang bawat kalahok ay pumipirma ng isang bagay gamit ang BLS (halimbawa, ang nakaraang random), at ang karaniwang pirma ng threshold ay ang gustong random. Ang mga cryptographic na katangian ng mga lagda ng BLS ay nakakatugon sa mga kinakailangan para sa random na kalidad, ang threshold na bahagi ay nagpoprotekta laban sa "huling aktor", at ang natatanging pagkakaisa ng mga susi ay ginagawang posible na magpatupad ng mas maraming kawili-wiling mga algorithm na nagbibigay-daan, halimbawa, mahusay na pagsasama-sama ng mga mensahe ng protocol .

Kaya, kung ikaw ay nagtatayo ng PVRB sa iyong blockchain, malamang na mapupunta ka sa BLS threshold signatures scheme, ilang mga proyekto na ang gumagamit nito. Halimbawa, DFinity (dito benchmark na nagpapatupad ng circuit, at dito halimbawa ng pagpapatupad ng nabe-verify na lihim na pagbabahagi), o Keep.network (narito ang kanilang random na beacon dilaw na papelat dito halimbawa matalinong kontrata na naghahatid ng protocol).

Pagpapatupad ng PVRB

Sa kasamaang palad, wala pa rin kaming nakikitang nakahanda na protocol na ipinatupad sa mga PVRB blockchain na napatunayan ang seguridad at katatagan nito. Kahit na ang mga protocol mismo ay handa na, ang teknikal na paglalapat ng mga ito sa mga umiiral na solusyon ay hindi madali. Para sa mga sentralisadong sistema, walang saysay ang PVRB, at ang mga desentralisado ay mahigpit na limitado sa lahat ng mapagkukunan ng pag-compute: CPU, memorya, imbakan, I/O. Ang pagdidisenyo ng isang PVRB ay isang kumbinasyon ng iba't ibang mga protocol upang lumikha ng isang bagay na nakakatugon sa lahat ng mga kinakailangan para sa hindi bababa sa ilang mabubuhay na blockchain. Ang isang protocol ay nagkalkula nang mas mahusay, ngunit nangangailangan ng higit pang mga mensahe sa pagitan ng mga RP, habang ang isa ay nangangailangan ng napakakaunting mga mensahe, ngunit ang paglikha ng isang patunay ay maaaring isang gawain na tumatagal ng sampu-sampung minuto, o kahit na oras.

Ililista ko ang mga salik na kailangan mong isaalang-alang kapag pumipili ng de-kalidad na PVRB:

• Lakas ng cryptographic. Ang iyong PVRB ay dapat na mahigpit na hindi karaniwan, na walang kakayahang kontrolin ang isang bit. Sa ilang mga scheme hindi ito ang kaso, kaya tumawag sa isang cryptographer
• Ang problema ng "huling aktor".. Ang iyong PVRB ay dapat na lumalaban sa mga pag-atake kung saan ang isang umaatake na kumokontrol sa isa o higit pang mga RP ay maaaring pumili ng isa sa dalawang resulta.
• Protocol sabotage problema. Ang iyong PVRB ay dapat na lumalaban sa mga pag-atake kung saan ang isang umaatake na kumokontrol sa isa o higit pang mga RP ay nagpapasya kung ito ay random o hindi at maaaring magagarantiyahan o may ibinigay na posibilidad na maimpluwensyahan ito.
• Bilang ng mga mensahe problema. Ang iyong mga RP ay dapat magpadala ng pinakamababang mensahe sa blockchain at iwasan ang magkasabay na pagkilos hangga't maaari gaya ng mga sitwasyon tulad ng "Nagpadala ako ng ilang impormasyon, naghihintay ako ng tugon mula sa isang partikular na kalahok." Sa mga network ng p2p, lalo na sa mga nakakalat sa heograpiya, hindi ka dapat umasa sa isang mabilis na tugon
• Ang problema ng computational complexity. Ang pag-verify ng anumang yugto ng PVRB on-chain ay dapat na napakadali, dahil ginagawa ito ng lahat ng buong kliyente ng network. Kung ang pagpapatupad ay tapos na gamit ang isang matalinong kontrata, kung gayon ang mga kinakailangan sa bilis ay napakahigpit
• Ang problema ng accessibility at liveness. Dapat magsikap ang iyong PVRB na maging matatag sa mga sitwasyon kung saan ang bahagi ng network ay nagiging hindi magagamit sa loob ng isang yugto ng panahon at ang bahagi ng RP ay humihinto na lamang sa paggana
• Ang problema ng pinagkakatiwalaang setup at paunang pamamahagi ng key. Kung ang iyong PVRB ay gumagamit ng pangunahing setup ng protocol, ito ay isang hiwalay na malaki at seryosong kuwento. Dito halimbawa. Kung ang mga kalahok ay dapat sabihin sa isa't isa ang kanilang mga susi bago simulan ang protocol, ito rin ay isang problema kung ang komposisyon ng mga kalahok ay nagbabago
• Mga problema sa pag-unlad. Availability ng mga library sa mga kinakailangang wika, ang kanilang seguridad at pagganap, publisidad, kumplikadong mga pagsubok, atbp.

Halimbawa, ang mga lagda ng threshold ng BLS ay may malaking problema - bago magsimulang magtrabaho, dapat ipamahagi ng mga kalahok ang mga susi sa isa't isa, na mag-organisa ng isang grupo kung saan gagana ang threshold. Nangangahulugan ito na hindi bababa sa isang round ng palitan sa isang desentralisadong network ang kailangang maghintay, at dahil ang nabuong rand, halimbawa, ay kinakailangan sa mga laro, halos sa totoong oras, nangangahulugan ito na ang sabotahe ng protocol ay posible sa yugtong ito. , at ang mga pakinabang ng threshold scheme ay nawala . Ang problemang ito ay mas simple kaysa sa mga nauna, ngunit nangangailangan pa rin ng pagbuo ng isang hiwalay na pamamaraan para sa pagbuo ng mga grupo ng threshold, na kailangang protektahan sa ekonomiya, sa pamamagitan ng mga deposito at pag-withdraw ng mga pondo (slashing) mula sa mga kalahok na hindi sumusunod sa protocol. Gayundin, ang pag-verify ng BLS na may katanggap-tanggap na antas ng seguridad ay sadyang hindi akma, halimbawa, sa isang karaniwang transaksyong EOS o Ethereum - sadyang walang sapat na oras para sa pag-verify. Ang code ng kontrata ay WebAssembly o EVM, na isinasagawa ng isang virtual machine. Ang mga cryptographic function ay hindi natively na ipinapatupad (pa), at gumagana nang sampu-sampung beses na mas mabagal kaysa sa mga nakasanayang cryptographic na library. Maraming mga protocol ang hindi nakakatugon sa mga kinakailangan batay lamang sa key volume, halimbawa 1024 at 2048 bits para sa RSA, 4-8 beses na mas malaki kaysa sa karaniwang lagda ng transaksyon sa Bitcoin at Ethereum.

Ang pagkakaroon ng mga pagpapatupad sa iba't ibang mga programming language ay gumaganap din ng isang papel - kung saan kakaunti, lalo na para sa mga bagong protocol. Ang opsyon na may integration sa consensus ay nangangailangan ng pagsulat ng protocol sa wika ng platform, kaya kailangan mong maghanap ng code sa Go for geth, sa Rust for Parity, sa C++ para sa EOS. Ang lahat ay kailangang maghanap ng JavaScript code, at dahil ang JavaScript at cryptography ay hindi partikular na malapit na magkaibigan, ang WebAssembly ay makakatulong, na ngayon ay tiyak na sinasabing ang susunod na mahalagang pamantayan sa Internet.

Konklusyon

Umaasa ako sa nauna Artikulo Nagawa kong kumbinsihin ka na ang pagbuo ng mga random na numero sa blockchain ay kritikal para sa maraming aspeto ng buhay ng mga desentralisadong network, at sa artikulong ito ay ipinakita ko na ang gawaing ito ay lubhang ambisyoso at mahirap, ngunit mayroon nang magagandang solusyon. Sa pangkalahatan, ang panghuling disenyo ng protocol ay posible lamang pagkatapos magsagawa ng napakalaking pagsubok na isinasaalang-alang ang lahat ng aspeto mula sa pag-setup hanggang sa fault emulation, kaya malamang na hindi ka makakahanap ng mga handa na recipe sa mga whitepaper at artikulo ng team, at tiyak na hindi namin gagawin. magpasya sa susunod na taon o dalawang isulat ang "gawin ito sa paraang ito, eksaktong tama."

Bye, para sa aming PVRB sa blockchain na binuo Haya, nagpasya kami sa paggamit ng mga lagda ng threshold ng BLS, plano naming ipatupad ang PVRB sa antas ng pinagkasunduan, dahil hindi pa posible ang pag-verify sa mga matalinong kontrata na may katanggap-tanggap na antas ng seguridad. Posible na gumamit kami ng dalawang scheme nang sabay-sabay: una, mahal na lihim na pagbabahagi upang lumikha ng pangmatagalang random_seed, at pagkatapos ay ginagamit namin ito bilang batayan para sa high-frequency na random na henerasyon gamit ang mga deterministikong threshold na mga lagda ng BLS, marahil ay lilimitahan lamang namin ang aming sarili isa sa mga scheme. Sa kasamaang palad, imposibleng sabihin nang maaga kung ano ang magiging protocol; ang tanging magandang bagay ay, tulad ng sa agham, sa mga problema sa engineering, isang negatibong resulta din ang resulta, at ang bawat bagong pagtatangka upang malutas ang problema ay isa pang hakbang para sa. ang pagsasaliksik ng lahat ng kasangkot sa problema. Upang matugunan ang mga kinakailangan sa negosyo, nilulutas namin ang isang partikular na praktikal na problema - ang pagbibigay ng mga application sa paglalaro na may mapagkakatiwalaang pinagmumulan ng entropy, kaya kailangan din naming bigyang pansin ang mismong blockchain, lalo na ang mga isyu ng finality ng chain at pamamahala ng network.

At kahit na hindi pa tayo nakakakita ng isang napatunayang lumalaban na PVRB sa mga blockchain, na gagamitin sana ng sapat na oras upang masuri ng mga tunay na aplikasyon, maramihang pag-audit, pag-load, at siyempre, mga tunay na pag-atake, ngunit ang bilang ng mga posibleng landas ay nagpapatunay na isang solusyon ang umiiral, at kung ano -sa mga algorithm na ito ang malulutas sa huli ang problema. Ikalulugod naming ibahagi ang mga resulta at pasalamatan ang iba pang mga koponan na gumagawa din sa isyung ito para sa mga artikulo at code na nagpapahintulot sa mga inhinyero na huwag tumapak sa parehong rake nang dalawang beses.

Kaya, kapag nakilala mo ang isang programmer na nagdidisenyo ng desentralisadong random, maging matulungin at nagmamalasakit, at magbigay ng sikolohikal na tulong kung kinakailangan :)

Pinagmulan: www.habr.com