Light clients, also known as Simple Payment Verification (SPV) clients, are nodes that only download a small portion of the data in a blockchain and use indirect means to verify that a given chain is valid. Typically, instead of validating block data, they assume that the chain favored by the blockchain's consensus algorithm only contains valid blocks and that the majority of block producers are honest.Mustafa Al-Bassam, Alberto Sonnino, Vitalik Buterin, arXiv:1809.09044 [cs.CR]
Note that although it is possible to present a Merkle proof from dataRooti to an individual share, it is important to note that a Merkle tree has 2x leaves, and the Merkle sub-trees for the row and column roots are constructed independently from dataRooti. Therefore it is necessary to have a wrapper function around VerifyMerkleProof called VerifyShareMerkleProof with the same parameters which takes into account how the underlying Merkle tree deals with an unbalanced number of leaves; this may involve calling VerifyMerkleProof twice for dierent portions of the path, or osetting the index.5 (cid:113) 1 2 dataLengthi. If we are only interested in the row and column roots of dataRooti, rather than the actual shares, then we can assume that dataRooti has 2matrixWidthi leaves when verifying a Merkle proof of a row or column root. The width of the matrix can be derived as matrixWidthi =
id: 8f960b25a6be8571219501a3cb843962 - page: 14
A light client or full node is able to reconstruct dataRooti from all the row and column roots by recomputing step 4. In order to gain data availability assurances, all light clients should at minimum download all the row and column roots needed to reconstruct dataRooti and check that step 4 was computed correctly, because as we shall see in Section 5.5, they are necessary to generate fraud proofs of incorrectly generated extended data. We nevertheless represent all of the row and column roots as a a single dataRooti to allow super-light clients which do not download the row and col5 For example, if the underlying tree simply repeats the last leaves to pad the tree to 2x leaves, then the wrapper function may be VerifyShareMerkleProof(e, {e 2 i)). r}, r, n, i) = VerifyMerkleProof(e, {e r}, r, n, i + (cid:98)i / (cid:113) 1 1 2 i(cid:99) (2(cid:100)log2( 2 i)(cid:101) (cid:113) 1
id: c56a1a00736bb28508dbf9c5945297d4 - page: 14
Fraud and Data Availability Proofs umn roots, but these clients cannot be assured of data availability and thus do not fully benet from the increased security of allowing fraud proofs.
id: 734a94466feec173a4ebd50b74c11f27 - page: 15
5.3 Random Sampling and Network Block Recovery In order for any share in the 2D Reed-Solomon matrix to be unrecoverable, then at least (k + 1)2 out of (2k)2 shares must be unavailable (see Theorem 1). Thus when light clients receive a new block header from the network, they should randomly sample 0 < s < (k + 1)2 distinct shares from the extended matrix, and only accept the block if they receive all shares. Additionally, light clients gossip shares that they have received to the network, so that the full block can be recovered by honest full nodes. The protocol between a light client and the full nodes that it is connected to works as follows: 1. The light client receives a new block header hi from one of the full nodes it is i , ..., i ). If the check root(R) connected to, and a set of row and column roots R = (rowRoot1 rowRoot2k i , columnRoot2 i = dataRooti is false, then the light client rejects the header. i , ..., columnRoot2k , columnRoot1 i , rowRoot2
id: 419bae728577c390f54dac182cc13a82 - page: 15