Hey Habr!
Di vê gotarê de ez ê li ser nifşkirina hejmarên pseudo-random ji hêla beşdarên ku ji hev bawer nakin biaxivim. Wekî ku em ê li jêr bibînin, pêkanîna jeneratorek "hema" baş pir hêsan e, lê yekî pir baş dijwar e.
Çima pêdivî ye ku di nav beşdarên ku ji hev bawer nakin de hejmarên rasthatî werin çêkirin? Yek qada serîlêdanê sepanên nenavendî ye. Mînakî, serîlêdanek ku behîsê ji beşdarekî qebûl dike û bi îhtimaleke %49 mîqdarê ducar dike an jî bi îhtimalek %51 jê digire, tenê heke bikaribe bêalî jimareyek rasthatî bistîne dê bixebite. Ger êrîşkarek bikaribe bandorê li ser encamên hilberînerê hejmarên bêserûber bike, û tewra hinekî şansê wergirtina dravdanê di serîlêdanê de zêde bike, ew ê bi hêsanî wê hilweşîne.
Dema ku em protokolek hilberîna hejmarên bêserûber ên belavbûyî dîzayn dikin, em dixwazin ku ew xwediyê sê taybetmendiyan be:
Divê ew bêalî be. Bi gotineke din, divê tu beşdar bi tu awayî bandorê li ser encama hilberînerê hejmarên rasthatî neke.
Divê ew bêpêşbîn be. Bi gotinek din, divê tu beşdar nikaribe pêşbîn bike ka dê kîjan hejmar çêbibe (an yek ji taybetmendiyên wê derxe) berî ku were çêkirin.
Pêdivî ye ku protokol domdar be, ango, li hember vê yekê berxwedêr be ku rêjeyek diyarkirî ya beşdaran ji torê qut dibin an bi qestî hewl didin ku protokolê rawestînin.
Di vê gotarê de em ê li du nêzîkatiyan binêrin: RANDAO + VDF û nêzîkatiya kodên jêbirinê. Di beşa paşîn de, em ê nêzîkatiyek li ser bingeha îmzeyên bordûmanê bikin.
Lê pêşî, bila em li algorîtmayek hêsan û bi gelemperî ku bikêrhatî, nepêşbînîkirî, lê alîgir e binihêrin.
RANDAO
RANDAO nêzîkatiyek pir hêsan e û ji ber vê yekê pir bi gelemperî tê bikar anîn ji bo hilberîna bêserûberiyê. Hemî beşdarên torê pêşî li herêmî hejmarek pseudorandom hildibijêrin, dûv re her beşdar jimareyek bijartî dişîne. Dûv re, beşdar bi dorê hejmarên xwe yên bijartî eşkere dikin û li ser hejmarên diyarkirî operasyonek XOR dikin, û encama vê operasyonê dibe encama protokolê.
Pêngava weşandina haşeyan berî eşkerekirina jimareyan pêdivî ye ku êrîşkar nikaribe hejmara xwe hilbijêre piştî ku hejmarên beşdarên din dît. Ev ê bihêle ku ew hema hema bi yekdestî derana hilberînerê hejmarên rasthatî diyar bike.
Di dema pêvajoya protokolê de, pêdivî ye ku beşdaran du caran bi biryarek hevbeş (ku jê re tê gotin lihevhatin) werin: kengê dest bi eşkerekirina hejmarên hilbijartî bikin, û ji ber vê yekê dev ji pejirandina haşeyan berdin, û kengê dev ji pejirandina hejmarên hilbijartî rawestînin û encamên rasthatî hesab bikin. jimare. Biryarên weha di navbera beşdarên ku ji hev bawer nakin bi serê xwe ne karekî hêsan e, û em ê di gotarên pêşerojê de vegerin ser wê yekê ku em ê texmîn bikin ku algorîtmayek wiha lihevhatî ji me re heye.
Kîjan ji wan taybetmendiyên ku me li jor diyar kir RANDAO heye? Ew nayê pêşbînîkirin, xwedan heman zindîtiya protokola lihevhatinê ya bingehîn e, lê ew alîgir e. Bi taybetî, êrîşkarek dikare torê bişopîne, û piştî ku beşdarên din hejmarên xwe eşkere bikin, ew dikare XOR-a xwe bihejmêre, û biryarê bide ka hejmara xwe eşkere bike an na da ku bandorê li encamê bike. Digel ku ev rê li ber êrîşker digre ku bi yekdestî derana hilberînerê hejmarên bêserûber destnîşan bike, ew dîsa jî 1 bit bandorê dide wî. Û eger êrîşkar çend beşdaran kontrol bikin, wê hingê dê hejmara bit ku ew kontrol dikin bi hejmara beşdarên di bin kontrola wan de be.
Bandora êrîşkaran dikare pir kêm bibe bi daxwazkirina ku beşdaran jimareyan bi rêz eşkere bikin. Dûv re êrîşkar dê bikaribe bandorê li encamê bike tenê heke ew dawî were vekirin. Digel ku bandor bi girîngî kêmtir e, algorîtma hîn jî alîgir e.
RANDAO+VDF
Rêyek ku meriv RANDAO-yê bêalî bike ev e: piştî ku hemî jimar têne eşkere kirin û XOR tê hesibandin, encama wê dikeve nav têketina fonksiyonek, ku hesabkirina wê demek pir dirêj digire, lê dihêle hûn rastbûna fonksiyonê kontrol bikin. hesabkirin pir zû.
(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстроJi vê fonksiyonê re tê gotin Fonksiyona Derengiya Verastkirî, an jî VDF. Ger hesabkirina encama dawîn ji qonaxa eşkerekirina hejmarê dirêjtir bigire, wê hingê êrîşkar dê nikaribe bandora nîşandana an veşartina hejmara xwe pêşbîn bike, û ji ber vê yekê ew ê fersendê winda bike ku bandorê li encamê bike.
Pêşxistina VDF-yên baş pir dijwar e. Di van demên dawî de gelek serkeftin çêbûn, wek mînak. и ku VDF di pratîkê de pratîktir kir, û Ethereum 2.0 plan dike ku RANDAO bi VDF-ê re di demek dirêj de wekî çavkaniyek jimareyek rasthatî bikar bîne. Ji xeynî vê yekê ku ev nêzîkatî bêpêşbînîkirin û bêalî ye, feydeya wê ya zêde heye ku bikêrhatî be ger bi kêmî ve du beşdar li ser torê hebin (bihesibînin ku protokola lihevkirinê ya ku tê bikar anîn dema ku bi hejmareke piçûk a beşdaran re mijûl dibe guncan e).
Zehmetiya herî mezin a vê nêzîkatiyê sazkirina VDF-ê ye bi vî rengî ku tewra beşdarek xwedan hardwareya pispor a pir biha jî dê nikaribe VDF-ê berî dawiya qonaxa vedîtinê hesab bike. Bi îdeal, divê algorîtma jî xwedan marjîneyek ewlehiyê ya girîng be, bêje 10x. Nîgara jêrîn êrîşek ji hêla lîstikvanek ku xwedan ASICek pispor e nîşan dide ku destûrê dide wî ku VDF-yek zûtir ji dema hatî veqetandin ji bo eşkerekirina pejirandina RANDAO-yê bimeşîne. Beşdarek wusa hîn jî dikare encama dawîn bi karanîna an ne karanîna hejmara xwe hesab bike, û dûv re, li ser bingeha hesabkirinê, hilbijêre ka wê nîşan bide an na.
Ji bo malbata VDF ya ku li jor hatî behs kirin, performansa ASIC-ya veqetandî dikare 100+ carî ji hardware ya kevneşopî bilindtir be. Ji ber vê yekê heke qonaxa eşkerekirinê 10 saniye bidome, wê hingê divê VDF-ya ku li ser ASICek wusa tê hesibandin zêdetirî 100 saniyeyan bigire da ku xwedan margîneyek ewlehiyê 10x be, û bi vî rengî heman VDF-ya ku li ser hardware ya hilberê tête hesibandin divê 100x 100 çirk = ~ 3 demjimêran bigire.
Weqfa Ethereum plan dike ku vê pirsgirêkê çareser bike bi afirandina ASIC-ên xwe yên gelemperî, belaş. Dema ku ev çêbibe, hemî protokolên din jî dikarin ji vê teknolojiyê sûd werbigirin, lê heya wê hingê nêzîkatiya RANDAO + VDF dê ji bo protokolên ku nikaribin veberhênanê di pêşvebirina ASIC-ên xwe de veberhênan bikin, ne guncan be.
Gelek gotar, vîdyoy û agahdariyên din ên di derbarê VDF de hatine berhev kirin .
Em kodên jêbirinê bikar tînin
Di vê beşê de, em ê li protokola hilberîna hejmarên rasthatî ya ku bikar tîne binêrin . Ew dikare heya ⅓ êrîşkaran tehemûl bike dema ku zindî bimîne, û dihêle ku heya ⅔ êrîşkar hebin berî ku ew bikarin encam pêşbîn bikin an bandor bikin.
Fikra sereke ya protokolê wiha ye. Ji bo sadebûnê, em bihesibînin ku tam 100 beşdar hene. Werin em her weha texmîn bikin ku hemî beşdarên herêmî xwedan mifteyek taybet in, û mifteyên giştî yên hemî beşdaran ji hemî beşdaran re têne zanîn:
Her beşdarvanek herêmî bi rêzek dirêj tê, wê dike 67 beş, kodên jêbirinê diafirîne da ku 100 parveyan bi dest bixe ku her 67 ji bo vegerandina rêzê bes in, her yek ji 100 parveyan ji yek ji beşdaran re destnîşan dike, û wan bi şîfre dike. mifteya giştî ya heman beşdar. Dûv re hemî parvekirinên kodkirî têne weşandin.
Beşdar cûreyek lihevhatinekê bikar tînin da ku bigihîjin rêkeftinekê li ser komên kodkirî yên ji 67 beşdarên taybetî.
Dema ku lihevhatinek pêk tê, her beşdar di her yek ji 67 setên ku bi mifteya xweya giştî ve hatî şîfrekirin de parvekirinên kodkirî digire, hemî parvekirinên weha deşîfre dike, û hemî parvekirinên weha yên deşîfre diweşîne.
Dema ku 67 beşdaran qonaxa (3) qedandin, hemî komên lihevkirî ji ber taybetmendiyên kodên jêbirinê dikarin bi tevahî werin deşîfrekirin û ji nû ve ava kirin, û hejmara paşîn dikare wekî XORek rêzikên destpêkê yên ku beşdaran di (1) de dest pê kirine, were bidestxistin. .
Ev protokol dikare bêalî û bêpêşbînîkirî were nîşandan. Hejmara random a encam piştî ku lihevhatin pêk tê tê destnîşan kirin, lê ji kesî re nayê zanîn heya ku ⅔ ji beşdaran beşên ku bi mifteya xwe ya giştî hatine şîfrekirin deşîfre nekin. Ji ber vê yekê, berî ku agahdariya ku têra ji nû ve avakirina wê were weşandin, jimareya random tê destnîşankirin.
Ger di gava (1) de yek ji beşdaran parvekirinên kodkirî ji beşdarên din re bişîne ku ji bo hin rêzikan koda jêbirinê ya rast ne, dê çi bibe? Bêyî guheztinên zêde, beşdarên cihêreng an dê nikaribin rêzê bi tevahî vegerînin, an jî ew ê rêzikên cihêreng vegerînin, ku dê di encamê de beşdarên cihê jimareyek random cûda werbigirin. Ji bo pêşîlêgirtina vê yekê, hûn dikarin jêrîn bikin: her beşdar, ji bilî parvekirinên kodkirî, di heman demê de hesab dike. hemî parve dike, û ji her beşdarekî re hem parvekirina kodkirî bi xwe û hem jî koka dara merkleyê, hem jî delîlên tevlêbûna parê di dara merkleyê de dişîne. Di lihevhatina gavê (2) de, beşdar ne tenê li ser komek koman, lê li ser komek kokên taybetî yên darên weha li hev dikin (eger hin beşdar ji protokolê dûr ketin, û rehên darên merkle yên cihêreng ji beşdarên cihê re şandin, û du rehên weha di dema lihevhatinê de têne xuyang kirin, rêza wî di berhevoka encamê de ne tê de). Di encama lihevkirinê de, em ê 67 xêzên kodkirî û rehên têkildar ên dara merkleyê hebin ku bi kêmî ve 67 beşdar hebin (ne hewce ne ku heman kesên ku xetên têkildar pêşniyar kirine), ku ji bo her 67 rêzan hene. peyamek bi parvekirina koda jêbirinê, û delîlek peydabûna para wan di dara têkildar de winda bû.
Dema ku di gava (4) de beşdar 67 lêdanan ji bo rêzek diyar deşîfre dike û hewl dide ku rêza orîjînal ji wan ji nû ve ava bike, yek ji vebijarkan gengaz e:
Rêz tê vegerandin, û heke ew dûv re dîsa were jêbirin-kodkirin, û dara Merkleyê ji bo parvekirinên herêmî yên hesabkirî were hesibandin, kok bi ya ku li ser lihevhatin pêk hatiye re hevûdu dike.
Rêz tê vegerandin, lê koka herêmî ya hesabkirî bi ya ku tê de lihevhatin pêk hatiye hev nagire.
Rêz nayê vegerandin.
Hêsan e ku meriv nîşan bide ku heke vebijarka (1) bi kêmî ve ji bo beşdarek li jor qewimî, wê hingê vebijarka (1) ji bo hemî beşdaran qewimî, û berevajî, heke vebijarka (2) an (3) ji kêmasî ve ji bo beşdarek pêk hat, wê hingê ji bo hemî beşdaran vebijarka (2) an (3) dê bibe. Bi vî rengî, ji bo her rêzek di setê de, an dê hemî beşdar bi serfirazî wê vegerînin, an jî hemî beşdar dê bisernekevin. Dûv re hejmara rasthatî ya ku tê encamdan XORek tenê rêzikên ku beşdaran karîbûn vegerînin e.
Îmzeyan berbend
Nêzîktêdayînek din a rasthatiniyê ev e ku meriv tiştên ku jê re îmzeyên sînorê BLS tê gotin bikar bînin. Hilberînerek hejmarên tesadufî ku li ser bingeha îmzayên boriyê ye, tam heman garantiyên ku algorîtmaya kod-based paqijkirinê ya ku li jor hatî destnîşan kirin heye, lê ji bo her hejmarek hatî çêkirin hejmarek asîmptotîk a peyamên ku li ser torê têne şandin heye.
Îmzeyên BLS sêwiranek e ku dihêle gelek beşdaran ji bo peyamek yek îmzeyek hevpar biafirînin. Van îmzeyan bi gelemperî têne bikar anîn da ku cîh û firehiya bandê xilas bikin bi ne hewcedariya şandina gelek îmzeyan.
Serlêdanek hevpar a ji bo îmzeyên BLS di protokolên zincîra blokê de, ji bilî hilberîna hejmarên bêserûber, di protokolên BFT de îmzekirina blokê ye. Em bêjin 100 beşdar blokan çêdikin, û blokek bi dawî tê hesibandin heke 67 ji wan wê îmze bikin. Ew hemî dikarin beşên xwe yên îmzeya BLS radest bikin û hin algorîtmaya lihevhatinê bikar bînin ku li ser 67 ji wan li hev bikin û dûv re wan di yek îmzeyek BLS de bikin yek. Her 67 (an jî zêdetir) beş dikarin werin bikar anîn da ku îmzeya dawîn çêbikin, ku dê bi kîjan 67 îmzeyan ve girêdayî ye ve girêdayî be û ji ber vê yekê dibe ku cûda bibe, her çend bijarteyên cûda yên 67 beşdaran dê îmzeyek cûda biafirînin, her îmzeyek weha dê derbasdar be. îmze ji bo blokê. Dûv re beşdarên mayî tenê hewce ne ku her blokek, li şûna 67, li ser torê, tenê yek îmzeyekê bistînin û verast bikin, ku ev yek bi girîngî barkirina torê kêm dike.
Derdikeve holê ku ger mifteyên taybet ên ku beşdaran bikar tînin bi rengekî diyar werin çêkirin, wê hingê kîjan 67 îmze (an bêtir, lê ne kêmtir) werin berhev kirin, dê îmzeya encam yek be. Ev dikare wekî çavkaniyek bêserûberiyê were bikar anîn: beşdaran pêşî li ser hin peyamek ku ew ê îmze bikin li hev dikin (ev dibe ku derketina RANDAO an tenê haşa bloka paşîn be, bi rastî ne girîng e ku ew her carê diguhezîne û hevgirtî ye) û ji bo wê îmzeyek BLS biafirînin. Encama nifşê dê neyê pêşbînîkirin heya ku 67 beşdar beşên xwe nedin, û piştî wê yekê encam ji berê ve hatî diyar kirin û nikare bi kiryarên tu beşdaran ve girêdayî be.
Ev nêzîkatiya rasthatiniyê heya ku bi kêmî ve ⅔ ji beşdarên serhêl hem protokolê bişopînin, hem jî bêalî û nepêşbînbar e heya ku bi kêmî ve ⅓ ji beşdaran protokolê bişopînin. Girîng e ku were zanîn ku êrîşkarek ku ji ⅓ zêdetir lê kêmtir ji ⅔ beşdaran kontrol dike, dikare protokolê rawestîne, lê nikare pêşbînî bike an bandorê li hilberîna wê bike.
Îmzeya bend bi xwe mijarek pir balkêş e. Di beşa duyemîn a gotarê de, em ê bi hûrgulî analîz bikin ka ew çawa dixebitin, û bi rastî çawa hewce ye ku bişkojkên beşdaran biafirînin da ku îmzayên sînor wekî hilberînerek hejmarên bêserûber werin bikar anîn.
Di encamê de
Ev gotar di rêze gotarên blogê yên teknîkî de yekem e . NEAR protokol û platformek blokek e ku ji bo pêşkeftina serîlêdanên nenavendî bi giranî li ser asaniya pêşkeftinê û hêsaniya karanîna ji bo bikarhênerên dawîn e.
Koda protokolê vekirî ye, pêkanîna me di Rust de hatî nivîsandin, ew dikare were dîtin .
Hûn dikarin bibînin ka pêşkeftina NEAR çawa xuya dike û di IDE-ya serhêl de biceribînin .
Hûn dikarin hemû nûçeyên bi rûsî li ser bişopînin û di , û bi Îngilîzî di fermî de .
Demek nêzik te bibînim!
Source: www.habr.com
