Created at 9pm, Mar 16
furkanCrypto
1
Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities
y-f8tWLHgRx9v1RnCeI70LYEYxs5Zn54N9UEcda3kL0
File Type
PDF
Entry Count
92
Embed. Model
jina_embeddings_v2_small_en
Index Type
hnsw

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
How to Retrieve?
# Search

curl -X POST "https://search.dria.co/hnsw/search" \
-H "x-api-key: <YOUR_API_KEY>" \
-H "Content-Type: application/json" \
-d '{"rerank": true, "top_n": 10, "contract_id": "y-f8tWLHgRx9v1RnCeI70LYEYxs5Zn54N9UEcda3kL0", "query": "What is alexanDRIA library?"}'
        
# Query

curl -X POST "https://search.dria.co/hnsw/query" \
-H "x-api-key: <YOUR_API_KEY>" \
-H "Content-Type: application/json" \
-d '{"vector": [0.123, 0.5236], "top_n": 10, "contract_id": "y-f8tWLHgRx9v1RnCeI70LYEYxs5Zn54N9UEcda3kL0", "level": 2}'