This thesis presents the design, implementation, and evaluation of techniques to scale the base layers of decentralized blockchain networks, where transactions are directly posted on the chain. The key challenge is to scale the base layer without sacrificing properties such as decentralization, security, and public verifiability. It proposes Chainspace, a blockchain sharding system where nodes process and reach consensus on transactions in parallel, thereby scaling block production and increasing on-chain throughput. In order to make the actions of consensus-participating nodes efficiently verifiable despite the increase of on-chain data, a system of fraud and data availability proofs is proposed so that invalid blocks can be efficiently challenged and rejected without the need for all users to download all transactions, thereby scaling block verification.Al Bassam, Mustafa; (2020) Securely Scaling Blockchain Base Layers. Doctoral thesis (Ph.D), UCL (University College London).
For simplicity, we will only consider two-dimensional Reed-Solomon encoding in this paper, but our scheme can be generalised to higher dimensions. In the sections below, we proceed to describe the details of the full data avail101 dataRoot data data data data extended extended extended rowRoots original tx c1ckc2kr1rkr2k columnRoots 4.5. Data Availability Proofs 102 Figure 4.4: Diagram showing a 2D Reed-Solomon encoding. The original data is initially arranged in a k k matrix, which is then extended to a 2k 2k matrix applying multiple times Reed-Solomon encoding. ability scheme. 4.5.3 2D Reed-Solomon Encoded Merkle Tree Construction In this section we describe how to compute a dataRooti for block header i using a
id: 30c67314555b89f301022bb01c52f54b - page: 101
2D Reed-Solomon code. Let extend be a function that takes in a list of k shares, and returns a list of 2k shares that represent the extended shares encoded using a standard 1D ReedSolomon code. extend(sh1, sh2, ..., shk) = (sh1, sh2, ..., sh2k) The rst k shares that are returned are the same as the input shares, and the latter k are the coded shares. Recall that all 2k shares can be recovered with knowledge of any k of the 2k shares. A 2D Reed-Solomon Encoded Merkle tree can then be constructed as follows from a block of data: 4.5. Data Availability Proofs 103 1. Split the original data into shares of size shareSize each, and arrange them into a k k matrix Oi; apply padding if the last share is not exactly of size shareSize, or if there are not enough shares to complete the matrix. In the next step, we extend this k k matrix to a 2k
id: 9d10b72fc4b6108e60ed5f27618d924d - page: 102
2k matrix Mi with Reed-Solomon encoding. 2. For each row in the original k k matrix Oi, pass the k shares in that row to extend(sh1, sh2, ..., shk) and append the extra shares outputted (shk+1, ..., sh2k) to the row to create an extended row of length 2k, thus extending the matrix horizontally. Repeat this process for the columns in Oi to extend the matrix vertically, so that each original column now has length 2k. This creates an extended 2k 2k matrix with the upper-right and lower-left quadrants lled, as shown in Figure 4.4. Then nally apply Reed-Solomon encoding horizontally on each row of the vertically extended portion of the matrix to complete the bottom-right quadrant of the 2k 2k matrix. This results in the extended
id: f72be539fc1b81b820c78a84fbae8bfb - page: 103
3. Compute the root of the Merkle tree for each row and column in the 2k i = root((M j,1 )), where Mx,y matrix, where each leaf is a share. We have rowRoot j , ..., M2k, j ..., M j,2k i i )) and columnRoot j i = root((M1, j , M2, j i i i i 2k , M j,2 i , represents the share in row x, column y in the matrix. 4. Compute the root of the Merkle tree of the roots computed in step 3 and use this as dataRooti. We have dataRooti = root((rowRoot1 rowRoot2k i , columnRoot2 i , columnRoot1 i , ..., columnRoot2k i )).
id: f0bd8135eedad8d40d74b2e6e64a19ab - page: 103