Abstract. Light clients, also known as Simple Payment Verification(SPV) clients, are nodes which only download a small portion of the datain a blockchain, and use indirect means to verify that a given chain isvalid. Typically, instead of validating block data, they assume that thechain favoured by the blockchain’s consensus algorithm only containsvalid blocks, and that the majority of block producers are honest. By al-lowing such clients to receive fraud proofs generated by fully validatingnodes that show that a block violates the protocol rules, and combiningthis with probabilistic sampling techniques to verify that all of the datain a block actually is available to be downloaded, we can eliminate thehonest-majority assumption for block validity, and instead make muchweaker assumptions about a minimum number of honest nodes that re-broadcast data. Fraud and data availability proofs are key to enablingon-chain scaling of blockchains (e.g., via sharding or bigger blocks) whilemaintaining a strong assurance that on-chain data is available and valid.We present, implement, and evaluate a novel fraud and data availabilityproof system.
FraudandDataAvailabilityProofs17VerifyCodecFraudProof(blockHashi,axisRootji,axisRootjidataRooti,j,(roworcolumnroot)axis,(roworcolumnindicator)((sh0,pos0,ax0),(sh1,pos1,ax1),...,(shk,posk,axk)),(shares)(sh0dataRooti,sh1dataRooti,...,shkdataRooti))true,falseLetrecoverbeafunctionthattakesalistofsharesandtheirpositionsintheroworcolumn((sh0,pos0),(sh1,pos1),...,(shk,posk)),andthelengthoftheoriginalroworcolumnk.Thefunctionoutputsthefullrecoveredshares(sh0,sh1,...,sh2k)orerrifthesharesareunrecoverable.recover(((sh0,pos0),(sh1,pos1),...,(shk,posk)),k)(sh0,sh1,...,sh2k),errVerifyCodecFraudProofreturnstrueifallofthefollowingconditionsaremet:1.blockHashicorrespondstoablockheaderhithattheclienthasdownloadedandstored.2.Ifaxis=0(rowroot),VerifyMerkleProof(axisRootji,axisRootjidataRooti,dataRooti,2matrixWidthi,j)returnstrue.3.Ifaxis=1(col.root),VerifyMerkleProof(axisRootji,axisRootjidataRooti,dataRooti,2matrixWidthi,1 c1ck+1c2krk+1r1r2kunavailable k - 1
id: 0420c0a4c2aabbd9004b3cb6b0f3e9e4 - page: 17
5:GraphicalinterpretationofTheorem1.Dataisunrecoverableifatleastk+1columns(orrows)haveeachatleastk+1unavailableshares.MinimumUnavailableSharesforUnrecoverabilityTheorem1statesthatdataisunrecoverableifamaliciousblockproposerwithholdsk+1sharesofatleastk+1columnsorrows;whichmakesatotalof(k+1)2sharestowithhold.Theorem1.Givena2k2kmatrixEasshowinFigure4,dataisunrecov - erableifatleastk+1columnsorrowshaveeachatleastk+1unavailableshares.Inthatcase,theminimumnumberofsharesthatmustbeunrecoverableis(k+1)2.Proof.SupposeamaliciousblockproducerwantstomakeunrecoverableashareEi,jofthe2k2kmatrixE.RecallthatReed - Solomonencodingallowtorecoverall2ksharesfromanykshares;theblockproducerwillhaveto(i)makeunre - coverableatleastk+1sharesfromtherowEi,,and(ii)makeunrecoverableatleastk+1sharesfromthecolumnE,j.Letusstartfrom(i);theblockproducerwithholdsatleastk+1sharesfromrowEi,.However,eachofthesek+1withheldshares(Ei,c1,...,Ei,ck+1)Ei,canberecoveredfromtheavailablesharesoftheirrespectivecolumnsE,c1,E,c2...,E,c
id: fd91d5409a91454f85a827b0ab211e0d - page: 18
Therefore,theblockproducerwillalsohavetowithholdatleastk+1sharesfromeachofthesecolumns.Thisgivesatotalof(k+1)(k+1)=(k+1)2sharestowithhold.Notethatatthispoint,therearenotenoughsharesleftinthematrixtorecoveranyofthe(k+1)2sharesofcolumns(E,c1,...E,ck+1).Letusnowconsider(ii);theblockproducerwithholdsatleastk+1sharesfromthecolumnE,jtomakeunrecoverabletheshareEi,j.Asbefore,eachshares(Er1,j,...,Erk+1,j)E,jcanberecoveredfromtheavailablesharesoftheirrespectiverowEr1,,Er2,,...,Erk+1,.Therefore,theblockproducerwillalsohavetowithholdatleastatleastk+1sharesfromeachoftheserows.Asbefore,thisalsogivesatotalof(k+1)(k+1)=(k+1)2sharestowithhold.
id: 20830c25b9424497664e621ea7ef4935 - page: 18
18MustafaAl - Bassam,AlbertoSonnino,andVitalikButerin FraudandDataAvailabilityProofs19However,(i)isequivalentto(ii)bythesymmetryofthematrix,andareactuallyoperatingonthesameshares;executing(i)onmatrixEisequivalenttoexecuting(ii)onthetransposeofmatrixE. UnrecoverableBlockDetectionTheorem2statestheprobabilitythatasinglelightclientwillsampleatleastoneunavailableshareinamatrixwiththeminimumunavailablesharesforunrecoverability,thusdetectingthatablockmaybeunrecoverable.Theorem2.Givena2k2kmatrixEasshowninFigure4,where(k+1)2sharesareunavailable.Ifoneplayerrandomlysamples0<s<(k+1)2sharesfromE,theprobabilityofsamplingatleastoneunavailableshareis:p1(X1)=1s1i=01(k+1)2 4k2i(1)Proof.Westartbyassumingthatthe2k2kmatrixEcontainsqunavailableshares;Iftheplayerperformsmtrials(0<s<(k+1)2),theprobabilityofndingexactlyzerounavailablesharesis:p1(X=0)=4k2qs
id: 8f5cbe01ba99687f33130e19dba436b6 - page: 18