Posible bang bumuo ng mga random na numero kung hindi tayo nagtitiwala sa isa't isa? Bahagi 1

Hoy Habr!

Sa artikulong ito ay magsasalita ako tungkol sa henerasyon ng mga pseudo-random na numero ng mga kalahok na hindi nagtitiwala sa isa't isa. Tulad ng makikita natin sa ibaba, ang pagpapatupad ng isang "halos" magandang generator ay medyo simple, ngunit ang isang napakahusay ay mahirap.

Bakit kailangang bumuo ng mga random na numero sa mga kalahok na hindi nagtitiwala sa isa't isa? Ang isang lugar ng aplikasyon ay mga desentralisadong aplikasyon. Halimbawa, ang isang application na tumatanggap ng taya mula sa isang kalahok at dinodoble ang halaga na may 49% na posibilidad o nag-aalis na may 51% na posibilidad ay gagana lamang kung ito ay makakatanggap ng walang kinikilingan na random na numero. Kung maimpluwensyahan ng isang umaatake ang kinalabasan ng generator ng random na numero, at kahit na bahagyang tumaas ang kanyang pagkakataon na makatanggap ng payout sa application, madali niyang sisirain ito.

Kapag nagdidisenyo kami ng distributed random number generation protocol, gusto naming magkaroon ito ng tatlong katangian:

1. Siya ay dapat na walang kinikilingan. Sa madaling salita, walang kalahok ang dapat sa anumang paraan makaimpluwensya sa resulta ng random number generator.

2. Dapat unpredictable siya. Sa madaling salita, walang kalahok ang dapat na mahulaan kung anong numero ang bubuo (o ipahiwatig ang alinman sa mga katangian nito) bago ito mabuo.

3. Ang protocol ay dapat na mabubuhay, iyon ay, lumalaban sa katotohanan na ang isang tiyak na porsyento ng mga kalahok ay nagdiskonekta mula sa network o sadyang subukang ihinto ang protocol.

Sa artikulong ito titingnan natin ang dalawang diskarte: RANDAO + VDF at ang diskarte sa mga erasure code. Sa susunod na bahagi, susuriin natin nang detalyado ang diskarte batay sa mga lagda ng threshold.

Ngunit una, tingnan natin ang isang simple at karaniwang ginagamit na algorithm na mabubuhay, hindi mahuhulaan, ngunit may kinikilingan.

RANDAO

Ang RANDAO ay isang napaka-simple at samakatuwid ay medyo karaniwang ginagamit na diskarte sa pagbuo ng randomness. Ang lahat ng kalahok sa network ay unang pumili ng isang pseudorandom na numero, pagkatapos ay ang bawat kalahok ay magpapadala ng hash ng napiling numero. Susunod, ang mga kalahok ay humalili sa pagbubunyag ng kanilang mga napiling numero at pagsasagawa ng XOR operation sa mga nahayag na numero, at ang resulta ng operasyong ito ay nagiging resulta ng protocol.

Ang hakbang ng pag-publish ng mga hash bago ihayag ang mga numero ay kinakailangan upang hindi mapili ng umaatake ang kanyang numero pagkatapos niyang makita ang mga numero ng iba pang kalahok. Ito ay magpapahintulot sa kanya na halos mag-isa na matukoy ang output ng random number generator.

Sa panahon ng protocol, ang mga kalahok ay kailangang dumating sa isang karaniwang desisyon (tinatawag na consensus) nang dalawang beses: kung kailan magsisimulang ibunyag ang mga napiling numero, at samakatuwid ay ihinto ang pagtanggap ng mga hash, at kung kailan ihihinto ang pagtanggap ng mga napiling numero at pagkalkula ng resultang random numero. Ang paggawa ng mga ganoong desisyon sa pagitan ng mga kalahok na hindi nagtitiwala sa isa't isa ay hindi isang madaling gawain sa sarili nito, at babalikan namin ito sa mga susunod na artikulo; sa artikulong ito ay ipagpalagay namin na ang naturang consensus algorithm ay magagamit sa amin.

Alin sa mga katangiang inilarawan namin sa itaas ang mayroon ang RANDAO? Ito ay hindi mahuhulaan, may parehong sigla gaya ng pinagbabatayan na protocol ng pinagkasunduan, ngunit ito ay may kinikilingan. Sa partikular, maaaring obserbahan ng isang attacker ang network, at pagkatapos ibunyag ng ibang mga kalahok ang kanilang mga numero, maaari niyang kalkulahin ang kanilang XOR, at magpasya kung ipapakita o hindi ang kanyang numero upang maimpluwensyahan ang resulta. Bagama't pinipigilan nito ang umaatake na mag-isa na matukoy ang output ng generator ng random na numero, nagbibigay pa rin ito sa kanya ng 1 kaunting impluwensya. At kung kinokontrol ng mga umaatake ang ilang kalahok, ang bilang ng mga bit na kinokontrol nila ay magiging katumbas ng bilang ng mga kalahok na nasa ilalim ng kanilang kontrol.

Ang impluwensya ng mga umaatake ay maaaring lubos na mabawasan sa pamamagitan ng pag-aatas sa mga kalahok na ipakita ang mga numero sa pagkakasunud-sunod. Pagkatapos ay maimpluwensyahan lamang ng umaatake ang kinalabasan kung huling binuksan ito. Bagama't mas mababa ang impluwensya, bias pa rin ang algorithm.

RANDAO+VDF

Ang isang paraan upang gawing walang kinikilingan ang RANDAO ay ito: pagkatapos maihayag ang lahat ng mga numero at kalkulahin ang XOR, ang resulta nito ay ilalagay sa input ng isang function, na tumatagal ng napakahabang oras upang makalkula, ngunit nagbibigay-daan sa iyong suriin ang kawastuhan ng napakabilis ng pagkalkula.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Ang function na ito ay tinatawag na Verifiable Delay Function, o VDF. Kung ang pagkalkula ng huling resulta ay mas matagal kaysa sa yugto ng pagsisiwalat ng numero, hindi mahuhulaan ng umaatake ang epekto ng pagpapakita o pagtatago ng kanyang numero, at samakatuwid ay mawawalan siya ng pagkakataong maimpluwensyahan ang resulta.

Ang pagbuo ng magagandang VDF ay napakahirap. Mayroong ilang mga tagumpay kamakailan, hal. ito и ito, na ginawang mas praktikal ang VDF sa pagsasanay, at plano ng Ethereum 2.0 na gamitin ang RANDAO kasama ang VDF bilang random na pinagmulan ng numero sa mahabang panahon. Bukod sa katotohanan na ang diskarteng ito ay hindi mahuhulaan at walang kinikilingan, mayroon itong karagdagang benepisyo ng pagiging mabubuhay kung hindi bababa sa dalawang kalahok ang magagamit sa network (ipagpalagay na ang consensus protocol na ginamit ay mabubuhay kapag nakikitungo sa napakaliit na bilang ng mga kalahok).

Ang pinakamalaking hamon ng diskarteng ito ay ang pagse-set up ng VDF na kahit na ang isang kalahok na may napakamahal na espesyal na hardware ay hindi makakakalkula ng VDF bago matapos ang yugto ng pagtuklas. Sa isip, ang algorithm ay dapat magkaroon ng isang makabuluhang margin ng kaligtasan, sabihin 10x. Ang figure sa ibaba ay nagpapakita ng pag-atake ng isang aktor na may espesyal na ASIC na nagbibigay-daan sa kanya na magpatakbo ng VDF nang mas mabilis kaysa sa oras na inilaan upang ipakita ang RANDAO confirmation. Maaari pa ring kalkulahin ng naturang kalahok ang huling resulta gamit o hindi gamit ang kanyang numero, at pagkatapos, batay sa pagkalkula, piliin kung ipapakita ito o hindi.

Para sa pamilyang VDF na nabanggit sa itaas, ang pagganap ng isang nakatuong ASIC ay maaaring 100+ beses na mas mataas kaysa sa kumbensyonal na hardware. Kaya kung ang yugto ng pagsisiwalat ay tumatagal ng 10 segundo, ang VDF na nakalkula sa naturang ASIC ay dapat tumagal ng higit sa 100 segundo upang magkaroon ng 10x na margin sa kaligtasan, at sa gayon ang parehong VDF na nakalkula sa commodity hardware ay dapat tumagal ng 100x 100 segundo = ~3 oras.

Plano ng Ethereum Foundation na lutasin ang problemang ito sa pamamagitan ng paglikha ng sarili nitong magagamit sa publiko, mga libreng ASIC. Kapag nangyari ito, maaari ding samantalahin ng lahat ng iba pang protocol ang teknolohiyang ito, ngunit hanggang sa panahong iyon, hindi magiging kasing-viable ang diskarte ng RANDAO+VDF para sa mga protocol na hindi maaaring mamuhunan sa pagbuo ng sarili nilang mga ASIC.

Maraming mga artikulo, video at iba pang impormasyon tungkol sa VDF ang nakolekta sa ang site na ito.

Gumagamit kami ng mga erasure code

Sa seksyong ito, titingnan natin ang isang random na number generation protocol na gumagamit pagbubura ng mga code. Maaari nitong tiisin ang hanggang ⅓ na umaatake habang nananatiling mabubuhay, at nagbibigay-daan sa hanggang ⅔ na umaatake na umiral bago nila mahulaan o maimpluwensyahan ang resulta.

Ang pangunahing ideya ng protocol ay ang mga sumusunod. Para sa pagiging simple, ipagpalagay natin na may eksaktong 100 kalahok. Ipagpalagay din natin na ang lahat ng kalahok sa lokal ay may ilang pribadong susi, at ang mga pampublikong susi ng lahat ng kalahok ay kilala ng lahat ng kalahok:

1. Ang bawat kalahok ay lokal na gumagawa ng mahabang string, hinati-hati ito sa 67 na bahagi, gumagawa ng mga erasure code para makakuha ng 100 shares upang ang alinmang 67 ay sapat upang mabawi ang string, italaga ang bawat isa sa 100 share sa isa sa mga kalahok, at i-encrypt ang mga ito gamit ang pampublikong susi ng parehong kalahok. Ang lahat ng naka-encode na bahagi ay nai-publish.

2. Gumagamit ang mga kalahok ng ilang uri ng consensus upang maabot ang kasunduan sa mga naka-code na set mula sa partikular na 67 kalahok.

3. Kapag naabot na ang pinagkasunduan, kukunin ng bawat kalahok ang mga naka-encode na bahagi sa bawat isa sa 67 set na naka-encrypt gamit ang kanilang pampublikong key, ide-decrypt ang lahat ng naturang pagbabahagi, at ini-publish ang lahat ng naturang na-decrypt na bahagi.

4. Kapag nakumpleto na ng 67 kalahok ang hakbang (3), ang lahat ng napagkasunduang set ay maaaring ganap na ma-decode at mabuo muli dahil sa mga katangian ng erasure code, at ang huling numero ay maaaring makuha bilang XOR ng mga unang hilera na sinimulan ng mga kalahok sa (1) .

Ang protocol na ito ay maaaring ipakita na walang kinikilingan at hindi mahuhulaan. Ang resultang random na numero ay tinutukoy pagkatapos na maabot ang pinagkasunduan, ngunit hindi alam ng sinuman hanggang ⅔ ng mga kalahok ay nagde-decode ng mga bahaging naka-encrypt gamit ang kanilang pampublikong key. Kaya, ang random na numero ay tinutukoy bago ang impormasyong sapat upang muling buuin ito ay nai-publish.

Ano ang mangyayari kung sa hakbang (1) ang isa sa mga kalahok ay nagpadala ng mga naka-encode na bahagi sa iba pang mga kalahok na hindi tamang erasure code para sa ilang string? Kung walang karagdagang mga pagbabago, ang iba't ibang kalahok ay maaaring hindi mabawi ang string, o sila ay magre-recover ng iba't ibang mga string, na magreresulta sa iba't ibang kalahok na makatanggap ng ibang random na numero. Upang maiwasan ito, maaari mong gawin ang mga sumusunod: ang bawat kalahok, bilang karagdagan sa mga naka-encode na pagbabahagi, ay kinakalkula din Puno ng Merkla lahat ng naturang pagbabahagi, at ipinapadala sa bawat kalahok ang parehong naka-encode na bahagi mismo at ang ugat ng puno ng merkle, at patunay ng pagsasama ng bahagi sa puno ng merkle. Sa pinagkasunduan sa hakbang (2), ang mga kalahok ay hindi lamang sumasang-ayon sa isang hanay ng mga hanay, ngunit sa isang hanay ng mga tiyak na ugat ng naturang mga puno (kung ang ilang kalahok ay lumihis sa protocol, at nagpadala ng iba't ibang mga ugat ng merkle tree sa iba't ibang kalahok, at dalawang ganoong mga ugat ang ipinapakita sa panahon ng pinagkasunduan, ang kanyang hilera ay hindi kasama sa set ng resulta). Bilang resulta ng pinagkasunduan, magkakaroon tayo ng 67 na naka-encode na linya at ang kaukulang mga ugat ng merkle tree na kung saan mayroong hindi bababa sa 67 kalahok (hindi kinakailangang pareho ang mga nagmungkahi ng kaukulang mga linya), na para sa bawat isa sa 67 na linya ay mayroong isang mensahe na may bahagi ng erasure code, at isang patunay na ang paglitaw ng kanilang bahagi sa kaukulang puno ay kupas.

Kapag sa hakbang (4) ang kalahok ay nag-decipher ng 67 beats para sa isang partikular na string at sinubukang buuin muli ang orihinal na string mula sa kanila, ang isa sa mga opsyon ay posible:

1. Ang string ay naibalik, at kung ito ay pagkatapos ay burahin muli, at ang Merkle tree ay kinakalkula para sa mga lokal na kalkuladong pagbabahagi, ang ugat ay tumutugma sa isa kung saan naabot ang pinagkasunduan.

2. Ang row ay naibalik, ngunit ang lokal na kinakalkula na ugat ay hindi tumutugma sa kung saan naabot ang pinagkasunduan.

3. Hindi naibalik ang row.

Madaling ipakita na kung ang opsyon (1) ay nangyari para sa hindi bababa sa isang kalahok sa itaas, ang opsyon (1) ay nangyari para sa lahat ng kalahok, at vice versa, kung ang opsyon (2) o (3) ay nangyari para sa hindi bababa sa isang kalahok, kung gayon para sa lahat ng kalahok opsyon (2) o (3) ang mangyayari. Kaya, para sa bawat hilera sa set, alinman sa lahat ng kalahok ay matagumpay na mabawi ito, o lahat ng mga kalahok ay mabibigo na mabawi ito. Ang resultang random na numero ay XOR lamang ng mga row na nabawi ng mga kalahok.

Mga lagda ng threshold

Ang isa pang diskarte sa randomness ay ang paggamit ng tinatawag na BLS threshold signatures. Ang isang random na generator ng numero batay sa mga pirma ng threshold ay may eksaktong kaparehong mga garantiya gaya ng algorithm na nakabatay sa code sa pagbura na inilarawan sa itaas, ngunit may makabuluhang mas mababang bilang ng mga mensaheng asymptotic na ipinadala sa network para sa bawat nabuong numero.

Ang mga lagda ng BLS ay isang disenyo na nagbibigay-daan sa maraming kalahok na lumikha ng isang karaniwang lagda para sa isang mensahe. Ang mga lagda na ito ay kadalasang ginagamit upang makatipid ng espasyo at bandwidth sa pamamagitan ng hindi pag-aatas ng maramihang mga lagda upang maipadala. 

Ang isang karaniwang aplikasyon para sa mga lagda ng BLS sa mga protocol ng blockchain, bilang karagdagan sa pagbuo ng mga random na numero, ay ang pag-block ng pag-sign sa mga protocol ng BFT. Sabihin nating 100 kalahok ang lumikha ng mga bloke, at ang isang bloke ay itinuturing na pinal kung 67 sa kanila ang pumirma nito. Lahat sila ay maaaring magsumite ng kanilang mga bahagi ng BLS signature at gumamit ng ilang consensus algorithm upang sumang-ayon sa 67 sa kanila at pagkatapos ay pagsamahin ang mga ito sa isang BLS signature. Anumang 67 (o higit pa) na bahagi ay maaaring gamitin upang lumikha ng panghuling lagda, na magdedepende kung aling 67 pirma ang pinagsama at samakatuwid ay maaaring mag-iba, bagama't ang iba't ibang mga pagpipilian ng 67 kalahok ay lilikha ng ibang pirma , anumang naturang lagda ay magiging wasto lagda para sa bloke. Ang natitirang mga kalahok ay kailangan lamang tumanggap at mag-verify ng isang pirma lamang sa bawat bloke, sa halip na 67, sa network, na makabuluhang binabawasan ang pagkarga sa network.

Lumalabas na kung ang mga pribadong key na ginagamit ng mga kalahok ay nabuo sa isang tiyak na paraan, kung aling 67 pirma (o higit pa, ngunit hindi bababa) ang pinagsama-sama, ang magreresultang lagda ay magiging pareho. Ito ay maaaring gamitin bilang isang mapagkukunan ng randomness: sumang-ayon muna ang mga kalahok sa ilang mensahe na kanilang pipirmahan (maaaring ito ay ang output ng RANDAO o ang hash lamang ng huling bloke, hindi ito mahalaga basta ito ay nagbabago sa bawat oras at pare-pareho) at lumikha ng pirma ng BLS para dito. Ang resulta ng henerasyon ay hindi mahuhulaan hanggang 67 kalahok ang magbigay ng kanilang mga bahagi, at pagkatapos nito ay paunang natukoy na ang output at hindi maaaring umasa sa mga aksyon ng sinumang kalahok.

Ang diskarte na ito sa randomness ay mabubuhay hangga't hindi bababa sa ⅔ ng mga kalahok online ang parehong sumusunod sa protocol, at walang kinikilingan at hindi mahuhulaan hangga't hindi bababa sa ⅓ ng mga kalahok ang sumusunod sa protocol. Mahalagang tandaan na ang isang umaatake na kumokontrol ng higit sa ⅓ ngunit mas mababa sa ⅔ ng mga kalahok ay maaaring huminto sa protocol, ngunit hindi mahuhulaan o maimpluwensyahan ang output nito.

Ang mga pirma mismo ng threshold ay isang napaka-kawili-wiling paksa. Sa ikalawang bahagi ng artikulo, susuriin namin nang detalyado kung paano gumagana ang mga ito, at kung paano eksaktong kinakailangan upang makabuo ng mga key ng kalahok upang ang mga lagda ng threshold ay magagamit bilang isang random na generator ng numero.

Sa pagtatapos

Ang artikulong ito ay ang una sa isang serye ng mga teknikal na artikulo sa blog NEAR. Ang NEAR ay isang blockchain protocol at platform para sa pagbuo ng mga desentralisadong application na may diin sa kadalian ng pagbuo at kadalian ng paggamit para sa mga end user.

Ang protocol code ay bukas, ang aming pagpapatupad ay nakasulat sa Rust, ito ay matatagpuan dito.

Maaari mong makita kung ano ang hitsura ng pag-unlad para sa NEAR at mag-eksperimento sa online na IDE dito.

Maaari mong sundin ang lahat ng mga balita sa Russian sa grupo ng telegrama at grupo sa VKontakte, at sa Ingles sa opisyal twitter.

Hanggang sa muli!

Pinagmulan: www.habr.com