A yw'n bosibl cynhyrchu rhifau ar hap os nad ydym yn ymddiried yn ein gilydd? Rhan 1

Hei Habr!

Yn yr erthygl hon byddaf yn siarad am y genhedlaeth o rifau ffug-hap gan gyfranogwyr nad ydynt yn ymddiried yn ei gilydd. Fel y gwelwn isod, mae gweithredu generadur da “bron” yn eithaf syml, ond mae un da iawn yn anodd.

Pam y byddai angen cynhyrchu haprifau ymhlith cyfranogwyr nad ydynt yn ymddiried yn ei gilydd? Un maes cais yw ceisiadau datganoledig. Er enghraifft, bydd cais sy'n derbyn bet gan gyfranogwr ac sydd naill ai'n dyblu'r swm gyda thebygolrwydd o 49% neu'n tynnu tebygolrwydd o 51% yn gweithio dim ond os gall dderbyn rhif ar hap yn ddiduedd. Os gall ymosodwr ddylanwadu ar ganlyniad y generadur rhifau ar hap, a hyd yn oed gynyddu ychydig ar ei siawns o gael taliad allan yn y cais, bydd yn ei ddinistrio'n hawdd.

Pan fyddwn yn dylunio protocol cynhyrchu rhifau ar hap dosbarthedig, rydym am iddo gael tri phriodwedd:

1. Rhaid iddo fod yn ddiduedd. Mewn geiriau eraill, ni ddylai unrhyw gyfranogwr mewn unrhyw ffordd ddylanwadu ar ganlyniad y generadur haprifau.

2. Rhaid iddo fod yn anrhagweladwy. Mewn geiriau eraill, ni ddylai unrhyw gyfranogwr allu rhagfynegi pa rif fydd yn cael ei gynhyrchu (neu gasglu unrhyw un o'i briodweddau) cyn iddo gael ei gynhyrchu.

3. Rhaid i'r protocol fod yn hyfyw, hynny yw, gwrthsefyll y ffaith bod canran benodol o gyfranogwyr yn datgysylltu o'r rhwydwaith neu'n ceisio atal y protocol yn fwriadol.

Yn yr erthygl hon byddwn yn edrych ar ddau ddull: RANDAO + VDF a'r dull codau dileu. Yn y rhan nesaf, byddwn yn edrych yn fanwl ar y dull gweithredu yn seiliedig ar lofnodion trothwy.

Ond yn gyntaf, gadewch i ni edrych ar algorithm syml a ddefnyddir yn gyffredin sy'n hyfyw, yn anrhagweladwy, ond yn rhagfarnllyd.

RANDAO

Mae RANDAO yn ddull syml iawn ac felly a ddefnyddir yn eithaf cyffredin i gynhyrchu hap. Mae pob cyfranogwr rhwydwaith yn dewis rhif ffug yn lleol yn gyntaf, yna mae pob cyfranogwr yn anfon stwnsh o'r rhif a ddewiswyd. Nesaf, mae'r cyfranogwyr yn cymryd eu tro yn datgelu eu niferoedd dewisol ac yn perfformio gweithrediad XOR ar y niferoedd a ddatgelwyd, a daw canlyniad y llawdriniaeth hon yn ganlyniad i'r protocol.

Mae'r cam o gyhoeddi'r hashes cyn datgelu'r niferoedd yn angenrheidiol fel na all yr ymosodwr ddewis ei rif ar ôl iddo weld niferoedd y cyfranogwyr eraill. Byddai hyn yn caniatáu iddo fwy neu lai ar ei ben ei hun bennu allbwn y generadur haprifau.

Yn ystod y protocol, mae angen i gyfranogwyr ddod i benderfyniad cyffredin (consensws fel y'i gelwir) ddwywaith: pryd i ddechrau datgelu'r niferoedd a ddewiswyd, ac felly rhoi'r gorau i dderbyn hashes, a phryd i roi'r gorau i dderbyn y niferoedd a ddewiswyd a chyfrifo'r hap canlyniadol rhif. Nid yw gwneud penderfyniadau o'r fath rhwng cyfranogwyr nad ydynt yn ymddiried yn ei gilydd yn dasg hawdd ynddo'i hun, a byddwn yn dychwelyd ato mewn erthyglau yn y dyfodol; yn yr erthygl hon byddwn yn cymryd yn ganiataol bod algorithm consensws o'r fath ar gael i ni.

Pa eiddo a ddisgrifiwyd gennym uchod sydd gan RANDAO? Mae'n anrhagweladwy, mae ganddo'r un bywiogrwydd â'r protocol consensws sylfaenol, ond mae'n rhagfarnllyd. Yn benodol, gall ymosodwr arsylwi ar y rhwydwaith, ac ar ôl i gyfranogwyr eraill ddatgelu eu niferoedd, gall gyfrifo eu XOR, a phenderfynu a ddylid datgelu ei rif ai peidio i ddylanwadu ar y canlyniad. Er bod hyn yn atal yr ymosodwr rhag pennu allbwn y generadur haprifau ar ei ben ei hun, mae'n dal i roi 1 ychydig o ddylanwad iddo. Ac os yw ymosodwyr yn rheoli sawl cyfranogwr, yna bydd nifer y darnau y maent yn eu rheoli yn gyfartal â nifer y cyfranogwyr sydd o dan eu rheolaeth.

Gellir lleihau dylanwad ymosodwyr yn fawr trwy fynnu bod cyfranogwyr yn datgelu'r niferoedd mewn trefn. Yna bydd yr ymosodwr yn gallu dylanwadu ar y canlyniad dim ond os caiff ei agor ddiwethaf. Er bod y dylanwad yn sylweddol llai, mae'r algorithm yn dal i fod yn unochrog.

RANDAO+VDF

Un ffordd o wneud RANDAO yn ddiduedd yw hyn: ar ôl i'r holl rifau gael eu datgelu a'r XOR gael ei gyfrifo, mae ei ganlyniad yn cael ei fwydo i fewnbwn swyddogaeth, sy'n cymryd amser hir iawn i'w gyfrifo, ond sy'n eich galluogi i wirio cywirdeb y cyfrifiad yn gyflym iawn.

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

Gelwir y swyddogaeth hon yn Swyddogaeth Oedi Gwiriadwy, neu VDF. Os yw cyfrifo'r canlyniad terfynol yn cymryd mwy o amser na'r cam datgelu rhif, yna ni fydd yr ymosodwr yn gallu rhagweld effaith dangos neu guddio ei rif, ac felly bydd yn colli'r cyfle i ddylanwadu ar y canlyniad.

Mae datblygu VDFs da yn hynod o anodd. Bu sawl torri tir newydd yn ddiweddar, e.e. hyn и hwn, a wnaeth VDF yn fwy ymarferol yn ymarferol, ac mae Ethereum 2.0 yn bwriadu defnyddio RANDAO gyda VDF fel ffynhonnell rhif ar hap yn y tymor hir. Ar wahân i’r ffaith bod y dull hwn yn anrhagweladwy ac yn ddiduedd, mae ganddo’r fantais ychwanegol o fod yn hyfyw os oes o leiaf ddau gyfranogwr ar gael ar y rhwydwaith (gan dybio bod y protocol consensws a ddefnyddir yn ymarferol wrth ymdrin â nifer mor fach o gyfranogwyr).

Her fwyaf y dull hwn yw sefydlu'r VDF fel na fydd hyd yn oed cyfranogwr â chaledwedd arbenigol drud iawn yn gallu cyfrifo'r VDF cyn diwedd y cyfnod darganfod. Yn ddelfrydol, dylai'r algorithm hyd yn oed fod ag ymyl diogelwch sylweddol, dyweder 10x. Mae'r ffigur isod yn dangos ymosodiad gan actor sydd ag ASIC arbenigol sy'n caniatáu iddo redeg VDF yn gyflymach na'r amser a neilltuwyd i ddatgelu'r cadarnhad RANDAO. Gall cyfranogwr o'r fath barhau i gyfrifo'r canlyniad terfynol gan ddefnyddio ei rif ai peidio, ac yna, yn seiliedig ar y cyfrifiad, dewis a ddylid ei ddangos ai peidio.

Ar gyfer y teulu VDF a grybwyllir uchod, gall perfformiad ASIC pwrpasol fod 100+ gwaith yn uwch na chaledwedd confensiynol. Felly os yw'r cam defnyddio yn para 10 eiliad, yna rhaid i'r VDF a gyfrifir ar ASIC o'r fath gymryd mwy na 100 eiliad i gael ymyl diogelwch 10x, ac felly rhaid i'r un VDF a gyfrifir ar galedwedd nwyddau gymryd 100x 100 eiliad = ~3 awr.

Mae Sefydliad Ethereum yn bwriadu datrys y broblem hon trwy greu ei ASICs rhad ac am ddim sydd ar gael i'r cyhoedd. Unwaith y bydd hyn yn digwydd, gall pob protocol arall hefyd fanteisio ar y dechnoleg hon, ond tan hynny ni fydd y dull RANDAO+VDF mor ymarferol ar gyfer protocolau na allant fuddsoddi mewn datblygu eu ASICs eu hunain.

Mae llawer o erthyglau, fideos a gwybodaeth arall am VDF wedi'u casglu ymlaen y wefan hon.

Rydym yn defnyddio codau dileu

Yn yr adran hon, byddwn yn edrych ar brotocol cynhyrchu rhifau ar hap sy'n ei ddefnyddio dileu codau. Gall oddef hyd at ⅓ ymosodwyr tra'n parhau i fod yn hyfyw, ac mae'n caniatáu i hyd at ⅔ ymosodwyr fodoli cyn y gallant ragweld neu ddylanwadu ar y canlyniad.

Mae prif syniad y protocol fel a ganlyn. Er mwyn symlrwydd, gadewch i ni dybio bod union 100 o gyfranogwyr. Gadewch i ni hefyd dybio bod gan yr holl gyfranogwyr yn lleol rywfaint o allwedd breifat, ac mae allweddi cyhoeddus yr holl gyfranogwyr yn hysbys i'r holl gyfranogwyr:

1. Mae pob cyfranogwr yn lleol yn creu llinyn hir, yn ei dorri'n 67 rhan, yn creu codau dileu i gael 100 o gyfranddaliadau fel bod unrhyw 67 yn ddigon i adennill y llinyn, yn aseinio pob un o'r 100 cyfran i un o'r cyfranogwyr, ac yn eu hamgryptio gyda allwedd gyhoeddus yr un cyfranogwr. Yna caiff yr holl gyfranddaliadau wedi'u hamgodio eu cyhoeddi.

2. Mae cyfranogwyr yn defnyddio rhyw fath o gonsensws i ddod i gytundeb ar setiau wedi'u codio gan 67 o gyfranogwyr penodol.

3. Unwaith y ceir consensws, mae pob cyfranogwr yn cymryd y cyfrannau wedi'u hamgodio ym mhob un o'r 67 set sydd wedi'u hamgryptio â'u hallwedd gyhoeddus, yn dadgryptio pob cyfranddaliad o'r fath, ac yn cyhoeddi'r holl gyfranddaliadau sydd wedi'u dadgryptio.

4. Unwaith y bydd 67 o gyfranogwyr wedi cwblhau cam (3), gellir dadgodio ac ail-greu pob set y cytunwyd arni yn llwyr oherwydd priodweddau codau dileu, a gellir cael y rhif terfynol fel XOR o'r rhesi cychwynnol y dechreuodd y cyfranogwyr â nhw yn (1) .

Gellir dangos bod y protocol hwn yn ddiduedd ac yn anrhagweladwy. Mae'r rhif hap canlyniadol yn cael ei bennu ar ôl cyrraedd consensws, ond nid yw'n hysbys i unrhyw un nes bod ⅔ o'r cyfranogwyr yn dadgodio'r rhannau sydd wedi'u hamgryptio â'u hallwedd gyhoeddus. Felly, mae'r rhif hap yn cael ei bennu cyn cyhoeddi gwybodaeth ddigonol i'w ail-greu.

Beth sy'n digwydd os yng ngham (1) mae un o'r cyfranogwyr yn anfon cyfranddaliadau wedi'u hamgodio at y cyfranogwyr eraill nad ydynt yn god dileu cywir ar gyfer rhai llinyn? Heb newidiadau ychwanegol, ni fydd gwahanol gyfranogwyr naill ai'n gallu adennill y llinyn o gwbl, neu byddant yn adennill llinynnau gwahanol, a fydd yn arwain at wahanol gyfranogwyr yn derbyn rhif hap gwahanol. Er mwyn atal hyn, gallwch wneud y canlynol: mae pob cyfranogwr, yn ogystal â'r cyfranddaliadau wedi'u hamgodio, hefyd yn cyfrifo Merkla coeden pob cyfranogwr o'r fath, ac yn anfon y gyfran wedi'i hamgodio ei hun a gwreiddyn y mercwrn i bob cyfranogwr, a phrawf o gynnwys y gyfran yn y goeden meclawdd. Yn y consensws yng ngham (2), mae'r cyfranogwyr wedyn nid yn unig yn cytuno ar set o setiau, ond ar set o wreiddiau penodol o goed o'r fath (os yw rhai cyfranogwr yn gwyro oddi wrth y protocol, ac yn anfon gwreiddiau coed mercwl gwahanol at wahanol gyfranogwyr, a dau wreiddyn o'r fath yn cael eu dangos yn ystod consensws, ei y rhes yn cael ei gynnwys yn y canlyniad a osodwyd). O ganlyniad i'r consensws, bydd gennym 67 o linellau wedi'u hamgodio a gwreiddiau cyfatebol y goeden mercwl fel bod o leiaf 67 o gyfranogwyr (nid o reidrwydd yr un rhai a gynigiodd y llinellau cyfatebol), sydd â phob un o'r 67 llinell wedi cymryd rhan. neges gyda chyfran o'r cod dileu, a phrawf bod digwyddiad eu cyfran yn y goeden gyfatebol wedi pylu.

Pan fydd y cyfranogwr yng ngham (4) yn dehongli 67 curiad ar gyfer llinyn penodol ac yn ceisio ail-greu'r llinyn gwreiddiol ohonynt, mae un o'r opsiynau yn bosibl:

1. Mae'r llinyn yn cael ei adfer, ac os caiff ei amgodio dileu eto, a bod y goeden Merkle yn cael ei gyfrifo ar gyfer y cyfrannau a gyfrifwyd yn lleol, mae'r gwreiddyn yn cyd-fynd â'r un y daethpwyd i gonsensws arno.

2. Mae'r rhes yn cael ei hadfer, ond nid yw'r gwreiddyn a gyfrifwyd yn lleol yn cyfateb i'r un lle daethpwyd i gonsensws.

3. Nid yw'r rhes yn cael ei hadfer.

Mae’n hawdd dangos pe bai opsiwn (1) yn digwydd ar gyfer o leiaf un cyfranogwr uchod, yna bod opsiwn (1) wedi digwydd i’r holl gyfranogwyr, ac i’r gwrthwyneb, os digwyddodd opsiwn (2) neu (3) ar gyfer o leiaf un cyfranogwr, yna ar gyfer yr holl gyfranogwyr bydd opsiwn (2) neu (3) yn digwydd. Felly, ar gyfer pob rhes yn y set, naill ai bydd yr holl gyfranogwyr yn ei adennill yn llwyddiannus, neu bydd yr holl gyfranogwyr yn methu â'i adennill. Mae'r rhif hap dilynol wedyn yn XOR o ddim ond y rhesi y llwyddodd y cyfranogwyr i'w hadfer.

Llofnodion trothwy

Ymagwedd arall at hap yw defnyddio'r hyn a elwir yn lofnodion trothwy BLS. Mae gan gynhyrchydd rhifau ar hap sy'n seiliedig ar lofnodion trothwy'r un gwarantau yn union â'r algorithm sy'n seiliedig ar god dileu a ddisgrifir uchod, ond mae ganddo nifer asymptotig sylweddol is o negeseuon a anfonir dros y rhwydwaith ar gyfer pob rhif a gynhyrchir.

Mae llofnodion BLS yn ddyluniad sy'n caniatáu i gyfranogwyr lluosog greu un llofnod cyffredin ar gyfer neges. Defnyddir y llofnodion hyn yn aml i arbed lle a lled band trwy beidio â mynnu bod llofnodion lluosog yn cael eu hanfon allan. 

Cymhwysiad cyffredin ar gyfer llofnodion BLS mewn protocolau blockchain, yn ogystal â chynhyrchu rhifau ar hap, yw llofnodi bloc mewn protocolau BFT. Gadewch i ni ddweud bod 100 o gyfranogwyr yn creu blociau, ac mae bloc yn cael ei ystyried yn derfynol os yw 67 ohonyn nhw'n ei lofnodi. Gallant i gyd gyflwyno eu rhannau o'r llofnod BLS a defnyddio rhywfaint o algorithm consensws i gytuno ar 67 ohonynt ac yna eu huno yn un llofnod BLS. Gellir defnyddio unrhyw 67 (neu fwy) o rannau i greu’r llofnod terfynol, a fydd yn dibynnu ar ba 67 llofnod a gyfunwyd ac felly gall amrywio, er y bydd dewisiadau gwahanol gan y 67 cyfranogwr yn creu llofnod gwahanol, bydd unrhyw lofnod o’r fath yn ddilys. llofnod ar gyfer y bloc. Yna dim ond un llofnod y bloc y mae angen i'r cyfranogwyr sy'n weddill ei dderbyn a'i wirio, yn hytrach na 67, dros y rhwydwaith, sy'n lleihau'r llwyth ar y rhwydwaith yn sylweddol.

Mae'n ymddangos, os yw'r allweddi preifat y mae cyfranogwyr yn eu defnyddio yn cael eu cynhyrchu mewn ffordd benodol, yna ni waeth pa 67 llofnod (neu fwy, ond nid llai) sy'n cael eu hagregu, bydd y llofnod canlyniadol yr un peth. Gellir defnyddio hwn fel ffynhonnell hap: mae'r cyfranogwyr yn cytuno'n gyntaf ar ryw neges y byddant yn ei harwyddo (gallai hyn fod yn allbwn RANDAO neu stwnsh y bloc olaf yn unig, nid oes ots mewn gwirionedd cyn belled â'i fod yn newid bob tro ac yn gyson) a chreu llofnod BLS ar ei gyfer. Bydd canlyniad y genhedlaeth yn anrhagweladwy nes bod 67 o gyfranogwyr yn darparu eu rhannau, ac ar ôl hynny mae'r allbwn eisoes wedi'i bennu ymlaen llaw ac ni all ddibynnu ar weithredoedd unrhyw gyfranogwr.

Mae'r dull hwn o ymdrin â hap yn ymarferol cyn belled â bod o leiaf ⅔ o'r cyfranogwyr ar-lein yn dilyn y protocol, ac yn ddiduedd ac yn anrhagweladwy cyn belled â bod o leiaf ⅓ o'r cyfranogwyr yn dilyn y protocol. Mae'n bwysig nodi y gall ymosodwr sy'n rheoli mwy na ⅓ ond llai na ⅔ o'r cyfranogwyr atal y protocol, ond ni all ragweld na dylanwadu ar ei allbwn.

Mae llofnodion trothwy eu hunain yn bwnc diddorol iawn. Yn ail ran yr erthygl, byddwn yn dadansoddi'n fanwl sut maent yn gweithio, a sut yn union y mae angen cynhyrchu allweddi cyfranogwr fel y gellir defnyddio llofnodion trothwy fel generadur rhifau ar hap.

I gloi

Yr erthygl hon yw'r gyntaf mewn cyfres o erthyglau blog technegol GER. Mae NEAR yn brotocol blockchain a llwyfan ar gyfer datblygu cymwysiadau datganoledig gyda phwyslais ar rwyddineb datblygiad a rhwyddineb defnydd ar gyfer defnyddwyr terfynol.

Mae'r cod protocol ar agor, mae ein gweithrediad wedi'i ysgrifennu yn Rust, gellir ei ddarganfod yma.

Gallwch weld sut olwg sydd ar ddatblygiad ar gyfer NEAR ac arbrofi yn y DRhA ar-lein yma.

Gallwch ddilyn yr holl newyddion yn Rwsieg yn grŵp telegram a grŵp ar VKontakte, ac yn Saesneg yn y swyddogol twitter.

Welwn ni chi cyn bo hir!

Ffynhonnell: hab.com