PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously

I Introduction

While Blockchain systems promise a host of new and exciting applications, such as digital cryptocurrency , industrial IoT , and healthcare management , their scalability remains a critical challenge . In fact, a well-known blockchain trilemma (see Figure 1) has been raised claiming that no decentralized ledger system can simultaneously achieve 1) security (against adversarial attacks), 2) decentralization (of computation and storage resources), and 3) scalability (of throughput with the network size). All existing major blockchains either achieve decentralization at the cost of efficiency, or efficiency at the cost of decentralization and/or security.

The focus of this paper is to formalize and study a version of the blockchain trilemma, in order to understand whether it is fundamental to blockchain systems. Corresponding to the three traits in the trilemma, we study the following performances measures of blockchain systems: security - measured as the number of malicious nodes the system can tolerate, decentralization - measured as the fraction of the block chain (or ledger) that is stored and processed by each node (we denote its inverse by storage efficiency), and scalability - measured as the total throughput of the system that is the number of computations performed in the system (e.g., number of transactions verified) in a unit period of time.

Within this context, let us first examine the current blockchain systems. Bitcoin and Ethereum are designed based on a full replication system, in which each network node stores the entire blockchain and replicates all the computations (e.g., transaction verifications), as demonstrated in Figure 2(a). This feature enables high security (of tolerating 49% adversarial nodes), however drastically limits the storage efficiency and throughput of the system: they stay constant regardless of the number of nodes $N$. For example, Bitcoin currently restricts its block size to 1 MB, and processing rate to 7 transactions/sec . In practice, the computational burden even increases with $N$ (e.g., mining puzzles get harder as time progresses and more users participate), causing the throughput to drop.

To scale out throughput and storage efficiency, the leading solution being discussed in the blockchain literature is via sharding . The key idea is to partition the blockchain into $K$ independent sub-chains, which are then replicated separately at $q=N/K$ nodes to yield $K$ smaller full-replication systems, a.k.a., shards (Figure 2(b)). This way, both storage efficiency and throughput are improved by a factor of $K$. However, to scale this improvement with network size, $K$ must increase linearly with $N$. Consequently, the number of nodes $q$ per shard has to be held constant, which allows an attacker to corrupt as few as $q/2$ nodes to compromise a shard. This yields a security level of $q/2$, which approaches zero as $N$ grows. Although various efforts have been made to alleviate this security issue (e.g., by periodically shuffling the nodes ), they are susceptible to powerful adversaries (e.g., who can corrupt the nodes after the shuffling), yet none scale security.

In summary, both full replication and sharding based blockchain systems make trade-offs between the scalability of throughput, storage efficiency, and security. However, such a trade-off is far from optimal from information theoretical point of view. Given the $N\times$ computation and $N\times$ storage resources across all the $N$ network nodes, the following information-theoretic upper bounds hold: $\textup{security}\leq\Theta(N)$; $\textup{throughput}\leq\Theta(N)$; $\textup{storage efficiency}\leq\Theta(N)$. It is intuitive that these bounds can be simultaneously achieved by a centralized system, allowing all the three metrics to scale. However, as pointed out by the trilemma, this has not been achieved by any existing decentralized system. This raises the following fundamental open problem:

Is there a blockchain design that simultaneously scales storage efficiency, security, and throughput? We answer this question affirmatively by introducing the concept of coded sharding. In particular, we propose PolyShard (polynomially coded sharding), a scheme that simultaneously achieves linear scaling in throughput, storage efficiency, and security (i.e., $\Theta(N)$). We show mathematically that Polyshard achieves all three information-theoretic upper bounds and enables a truly scalable blockchain system (see Table I).

PolyShard is inspired by recent developments in coded computing , in particular Lagrange Coded Computing , which provides a transformative framework for injecting computation redundancy in unorthodox coded forms in order to deal with failures and errors in distributed computing. The key idea behind PolyShard is that instead of storing and processing a single uncoded shard as done conventionally, each node stores and computes on a coded shard of the same size that is generated by linearly mixing uncoded shards (Figure 3), using the well-known Lagrange polynomial. This coding provides computation redundancy to simultaneously provide security against erroneous results from malicious nodes, which is enabled by noisy polynomial interpolation techniques (e.g., Reed-Solomon decoding).

While coding is generally applicable in many distributed computing scenarios, the following two salient features make PolyShard particularly suitable for blockchain systems.

Oblivious: The coding strategy applied to generate coded shards is oblivious of the verification function. That means, the same coded data can be simultaneously used for multiple verification items (examples: digital signature verification and balance checking in a payment system);

Incremental: PolyShard allows each node to grow its local coded shard by coding over the newest verified blocks, without needing to access the previous ones. This helps to maintain a constant coding overhead as the chain grows.

As a proof of concept, we simulate a payment blockchain system, which keeps records of balance transfers between accounts, and verifies new blocks by checking the senders’ fund sufficiency. We run experiments on this system for various combinations of network size and chain length, and measure/evaluate the throughput, storage, and security achieved by the full replication, sharding, and the PolyShard schemes. As we can see from the measurements plotted in Figure 4, PolyShard indeed achieves the throughput scaling with network size as the uncoded sharding scheme, improving significantly over the full replication scheme. These experiments provide an empirical verification of the theoretical guarantees of PolyShard in simultaneously scaling storage efficiency, security, and throughput.

To improve the number of supported shards, we also present iterative Polyshard in Appendix B. The key idea is to first represent verification functions as low-depth arithmetic circuits and then apply Polyshard iteratively to each layer of circuits.

In summary, the main contributions of this paper are as follows:

Formalizing and resolving a version of the blockchain trilemma by proposing a radically different design methodology called PolyShard that for the first time leverages coding in both storage and computation of blockchain systems.

Demonstrating that PolyShard simultaneously achieves linear scaling in throughput, storage efficiency, and security; hence meeting the information-theoretic limits.

Numerical evaluation of PolyShard in a payment blockchain system and demonstrating its scalaibility in terms of throughput, storage efficiency, and security.

Other related works. Prominent sharding proposals in the literature are . As an example, ELASTICO partitions the incoming transactions into shards, and each shard is verified by a disjoint committee of nodes in parallel. OmniLedger improved upon ELASTICO in multiple avenues, including new methods to assign nodes into shards with a higher security guarantee, an atomic protocol for cross-shard transactions, and further optimization on the communication and storage designs.

II Problem Formulation: Block Verification

A blockchain system manages a decentralized ledger of its clients’ transactions, over a large number of untrusted network nodes. The clients submit their transactions to the network nodes, who group the transactions into blocks that to be included in the system. The accepted blocks are organized into a chain where each block contains a hash pointer to its predecessor. The chain structure provides high security guarantee since for an adversary to tamper the contents of any block, it has to re-grow the entire chain afterwards, which is extremely expensive in computation power. Here we consider a sharded blockchain system whose grand ledger is partitioned into $K$ independent shards, each of which maintains a disjoint sub-chain that records the transactions between the accounts associated with the same shard. We focus on transactions that are verifiable intra-shard for the sake of clarity. Extensions such as cross-shard transactions and their verification is an added complexity yet complementary to the contributions of this paper. For instance, the atomic payment and locking mechanisms of can be naturally incorporated with the ideas in this paper. At a high level, at each time epoch, every shard proposes one block of transactions, and verifies it over the current state of its sub-chain. Once the block passes the verification, it will be appended to the corresponding sub-chain. We now define the system in more details.

Balance checking: to check each transaction has more input values than those spent in its outputs; and also check that the transactions in a block contain sufficient funds to pay the transaction fees/mining rewards.

Signature checking: to verify that a payment transaction spending some funds in an account is indeed submitted by the owner of that account. This often involves computing cryptographic hashes using the account’s public key, and verifying the results with the digital signature.

II-B Networking model

The above blockchain system is implemented distributedly over $N$ untrusted nodes. We consider a homogeneous and synchronous network, i.e., all nodes have similar process power, and the delay of communication between any pair of nodes is bounded by some known constant. A subset $\mathcal{M}\subset\{1,\ldots,N\}$ of the nodes may be corrupted, and are subject to Byzantine faults, i.e., they may compute and communicate arbitrary erroneous results during block verification. We aim to design secure verification schemes against the following strong adversary model:

The adversaries can corrupt a fixed fraction of the network node, i.e., the number of malicious nodes grows linearly with $N$.While here the adversary model is defined in a permissioned setting, the model and the proposed solution can directly extend to a permissionless setting where e.g., in a PoW system, the adversaries can control a fixed fraction of the entire hashing power.

If a conventional sharding solution were employed, the adversaries know the allocation of nodes to the shards, and are able to adaptively select the subset $M$ of nodes to attack.

We note that under this adversary model, the random shard rotation approach is no longer secure since the adversaries can focus their power to attack a single shard after knowing which nodes are assigned into this shard. Next, we present the networking protocol that will be followed by the honest nodes. Note that adversarial nodes are not required to follow this protocol.

Verification. Given the $K$ proposed blocks $\{X_{k}(t)\}_{k=1}^{K}$, one for each shard, the goal of block verification is to compute $\{f^{t}(X_{k}(t),Y_{k}^{t-1}\}_{k=1}^{K}$ distributedly over untrusted nodes. We implement this verification process in two steps. In the first step, each node $i$ computes an intermediate result $g_{i}^{t}$ using some function $\rho_{i}^{t}$ on the proposed blocks and its local storage, such that $g_{i}^{t}=\rho_{i}^{t}(X_{1}(t),\ldots,X_{K}(t),Z_{i}^{t-1})$, and then broadcasts the result $g_{i}^{t}$ to all other nodes.

II-C Performance metrics

We denote a block verification scheme by $S$, defined as a sequence of collections of the functions, i.e., $S=(\{\phi_{i}^{t},\rho_{i}^{t},\psi_{i}^{t},\chi_{i}^{t}\}_{i=1}^{N})_{i=1}^{\infty}$. We are interested in the following three performance metrics of $S$.

Storage efficiency. Denoted by $\gamma_{S}$, it is defined as the ratio between the size of the entire block chain and the size of the data stored at each node, i.e.,

The above definition also applies to a probabilistic formulation where the blockchain elements $Y_{k}(j)$s and the storage elements $Z_{i}(j)$s are modelled as i.i.d. random variables with uniform distribution in their respective fields, where the storage efficiency is defined using the entropy of the random variables.

Security. We say $S$ is $b$-secure if the honest nodes can recover all the correct verification results under the presence of up to $b$ malicious nodes. More precisely, for any subset $\mathcal{M}\subset\{1,\ldots,N\}$ of malicious nodes with $|\mathcal{M}|\leq b$, and each node $i\notin\mathcal{M}$, a $b$-secure scheme will guarantee that $(\hat{h}^{t}_{1i},\ldots,\hat{h}^{t}_{Ki})=(h^{t}_{1},\ldots,h^{t}_{K})$, for all $t=1,2,\ldots$. We define the security of $S$, denoted by $\beta_{S}$, as the maximum $b$ it could achieve:

Throughput. We measure throughput of the system by taking into account the number of blocks verified per epoch and the associated computational cost. We denoted by $c(f)$ the computational complexity of a function $f$, which is the number of additions and multiplications performed in the domain of $f$ to evaluate $f$.

We define the throughput of $S$, denoted by $\lambda_{S}$, as the average number of blocks that are correctly verified per unit discrete round, which includes all the computations performed at all $N$ nodes to verify the incoming $K$ blocks. That is,

The above three metrics correspond to the three traits in the blockchain trilemma, and all current blockchain systems have to trade off one for another. The goal of this paper is to understand the information-theoretic limits on these metrics, and design verification schemes that can simultaneously achieve the limits, hence settling the trilemma.

III Baseline Performance

We first present the information-theoretic upper bounds on the three performance metrics for any blockchain. We then study the performance of two state-of-the-art blockchain schemes and comment on the gaps with respect to the upper bounds.

Information-theoretic upper bounds. In terms of security, the maximum number of adversaries any verification scheme can tolerate cannot exceed half of the number of network nodes $N$. Thus, the security $\beta\leq\frac{N}{2}$. In terms of storage, for the verification to be successful, the size of the chain should not exceed the aggregated storage resources of the $N$ nodes. Otherwise, the chain cannot be fully stored. We thus have $\gamma\leq N$. Finally, to verify the $K$ incoming blocks, the verification function $f^{t}$ must be executed at least $K$ times in total. Hence, the system throughput $\lambda\leq\frac{K}{K/N}=N$. Therefore, the information-theoretic upper bounds of security, storage efficiency, and throughput all scale linearly with the network size $N$.

Full replication. In terms of storage efficiency, since each node stores all the $K$ shards of the entire blockchain, full replication scheme yields $\gamma_{\text{full}}=1$. Since every node verifies all the $K$ blocks, the throughput of the full replication scheme is $\lambda_{\text{full}}=\frac{K}{NKc(f^{t})/(Nc(f^{t}))}=1$. Thus the full replication scheme does not scale with the network size, as both the storage and the throughput remain constant as $N$ increases. The advantage is that the simple majority-rule will allow the correct verification and update of every block as long as there are less than $N/2$ malicious nodes. Thus, $\beta_{\text{full}}=N/2$.

Uncoded sharding scheme. In conventional sharding, the blockchain consists of $K$ disjoint sub-chains known as shards. The $N$ nodes are partitioned into $K$ groups of equal size $q=N/K$, and each group of nodes manage a single shard; this is a full replication system with $K^{\prime}=1$ shard and $N^{\prime}=q$ nodes. Since each node stores and verifies a single shard, the storage efficiency and throughput become $\gamma_{\textup{sharding}}=K$ and $\lambda_{\textup{sharding}}=\frac{K}{Nc^{t}/(Nc^{t})}=K$, respectively. For these two metrics to scale linearly with $N$, it must be true that $K=\Theta(N)$. Consequently, the group size $q$ becomes a constant. Hence, compromising as few as $q/2$ nodes will corrupt one shard and the chain. Thus, this scheme only has a constant security of $\beta_{\text{sharding}}=q/2=O(1)$. Although system solutions such as shard rotations can help achieve linearly scaling security guarantees, they are only secure when the adversary is non-adaptive (or very slowly adaptive). When the adversary is dynamic, it can corrupt all nodes belonging to a particular shard instantaneously after the shard assignment has been made. Under this model, the security reduces to a constant.

In summary, neither full replication nor the above sharding scheme exempts from the blockchain trilemma, and has to make tradeoff in scaling towards the information-theoretic limits. Motivated by the recent advances on leveraging coding theory to optimize the performance of distributed computation (see, i.e., ), we propose PolyShard (polynomially coded sharding) to achieve all of the three upper bounds simultaneously. Using PolyShard, each node stores coded data of the blockchain, and computes verification functions directly on the coded data.

IV PolyShard for balance checking

This function is linear in its input, and has computational complexity $c(f^{t})=O(t)$. We claim the block $X_{k}(t)$ valid (i.e., $e_{k}^{t}=1$) if no entry in the function’s output vector is negative, and invalid (i.e., $e_{k}^{t}=0$) otherwise. After computation, we have the verified block $Y_{k}(t)=(Y_{k}^{\textup{send}}(t),Y_{k}^{\textup{receive}}(t))=e_{k}^{t}X_{k}(t)$. We note that this balance checking can be alternatively implemented by having each shard simply store a dimension-$M$ vector that records the aggregated balances of all associated accounts, and the storage and the verification complexity will stay constant as time progresses. However, important transaction statistics including how many transactions occur in each block, and the input/output values in each transaction, and how these statistics evolve over time will be lost in this simplified implementation. Moreover, storing a single block in each shard without the protection of a long chain makes the shard more vulnerable to malicious tampering, compromising the security guarantee. Therefore, we stick to the chain structure where all past transactions are kept in the ledger.

We consider operating this sharded payment blockchain over a network of $N$ nodes, with a maximum $\mu$ fraction of which are corrupted by quickly-adaptive adversaries. For this system, we propose a coded transaction verification scheme, named PolyShard, which simultaneously scales the storage efficiency, security, and throughput with the network size.

We note that this polynomial is designed such that $u_{m}(\omega_{k})=Y_{k}(m)$ for all $k=1,\ldots,K$.

IV-B Coded verification

At epoch $t$, each shard $k$ proposes and broadcasts a new block $X_{k}(t)$ to be added to the sub-chain after balance checking. PolyShard scheme verifies these blocks in three steps.

Each node $i$ carries out $\Theta(t)$ operations to compute $g_{i}^{t}$, and broadcasts it to all other nodes.

Step 3: decoding. It is easy to see that $f^{t}(v_{t}(z),u_{1}(z),\ldots,u_{t-1}(z))$ is a univariate polynomial of degree $K-1$, and $g_{i}^{t}$ can be viewed as evaluating this polynomial at $\alpha_{i}$. Given the evaluations at $N$ distinct points $g_{1}^{t},\ldots,g_{N}^{t}$, each node can recover the coefficients of $f^{t}(v_{t}(z),u_{1}(z),\ldots,u_{t-1}(z))$ following the process of decoding a Reed-Solomon code with dimension $K$ and length $N$ (see, e.g., ). In order for this decoding to be robust to $\mu N$ erroneous results (i.e., achieving security $\beta_{\textup{{\tt PolyShard}}}=\mu N$), we must have $2\mu N\leq N-K$. In other words, a node can successfully decode $f^{t}(v_{t}(z),u_{1}(z),\ldots,u_{t-1}(z))$ only if the number of shards $K$ is upper bounded by $K\leq(1-2\mu)N$. Based on this constraint, we set the number of shards of the PolyShard scheme, $K_{\textup{{\tt PolyShard}}}=\lfloor(1-2\mu)N\rfloor$, which scales linearly with network size $N$.

The complexity of decoding a length-$N$ Reed-Solomon code at each node is $O(N\log^{2}N\log\log N)$, and the total complexity of the decoding step is $O(N^{2}\log^{2}N\log\log N)$.

The sub-chain update process in PolyShard is incremental, i.e., appending a coded block to a coded sub-chain is equivalent to appending uncoded blocks to the uncoded sub-chains, and then encoding from the updated sub-chains. This commutativity between sub-chain growth and shard encoding allows each node to update its local sub-chain incrementally by accessing only the newly verified blocks instead of the entire block history.

IV-C Performance of PolyShard

So far, we have shown that PolyShard achieves a storage efficiency $\gamma_{\textup{{\tt PolyShard}}}=K_{\textup{{\tt PolyShard}}}=\Theta(N)$, and it is also robust against $\mu N=\Theta(N)$ quickly-adaptive adversaries. The total number of operations during the verification and the sub-chain update processes is $O(NK)+N\Theta(t)+O(N^{2}\log^{2}N\log\log N)$, where the term $O(NK)+O(N^{2}\log^{2}N\log\log N)$ is the additional coding overhead compared with the uncoded sharding scheme. Since $K_{\textup{{\tt PolyShard}}}\leq N$, the coding overhead reduces to $O(N^{2}\log^{2}N\log\log N)$. The throughput of PolyShard for balance checking is computed as

We can see that since the complexities of the encoding and decoding operations of PolyShard do not scale with $t$, the coding overhead becomes irrelevant as the chain grows. The PolyShard scheme simultaneously achieves information-theoretically optimal scaling on security, storage efficiency, and throughput.

We note that when the verification function is linear with the block data, codes designed for distributed storage (see, e.g., ) can be used to achieve similar scaling as PolyShard. However, PolyShard is designed for a much more general class of verification functions including arbitrary multivariate polynomials, which cannot be handled by state-of-the-art storage codes.

V PolyShard for general verification functions

In this section, we describe the PolyShard scheme for a more general class of verification functions $f^{t}$ that can be represented as a multivariate polynomial with maximum degree of $d$. Cryptographic hash functions, which are extensively used in computing account addresses, validating transaction Merkle trees, and verifying digital signatures, are often evaluated as polynomials of its input data. For example, the Zémor-Tillich hash function is computed by multiplying $2\times 2$ matrices in a finite field of characteristic $2$, whose degree is proportional to the number of input bits . On the other hand, for hash functions that are based on bit mixing, and often lack algebraic structures (e.g., SHA-2, and Keccak ), we can represent the corresponding Boolean verification functions (indicating whether the block is valid or not) as polynomials using the following result : any Boolean function $\{0,1\}^{n}\rightarrow\{0,1\}$ can be represented by a polynomial of degree $\leq n$ with at most $2^{n-1}$ terms. The explicit construction of this polynomial is described in Appendix A.

While it is fairly clear that PolyShard achieves storage efficiency $\gamma_{\textup{{\tt PolyShard}}}=K_{\textup{{\tt PolyShard}}}=\Theta(N)$ and security $\beta_{\textup{{\tt PolyShard}}}=\mu N=\Theta(N)$ for a dergee-$d$ verification function, the throughput of PolyShard is

When $c(f^{t})$ grows with $t$, (e.g., $c(f^{t})=\Theta(t)$ for the above balance checking function that scans the entire sub-chain to find sufficient funds), the throughput of ${\tt PolyShard}$ becomes $\lambda_{\textup{{\tt PolyShard}}}=K_{\textup{{\tt PolyShard}}}=\Theta(N)$. We summarize the scaling results of the PolyShard scheme in the following theorem.

Consider a sharded blockchain whose blocks in each shard are verified by computing a multivariate polynomial of degree $d$ on the blocks in that shard. When implementing this blockchain over $N$ network nodes, up to $\mu$ (for some constant $0\leq\mu<\frac{1}{2}$) fraction of which may be corrupted by quickly-adptive adversaries, the proposed ${\tt PolyShard}$ scheme supports secure block verification from up to $K_{\textup{{\tt PolyShard}}}=\lfloor\frac{(1-2\mu)N-1}{d}+1\rfloor=\Theta(N)$ shards, and simultaneously achieves the following performance metrics,

when computational complexity of the verification function grows with the length of the sub-chain in each shard. Therefore, PolyShard simultaneously achieves the information-theoretically optimal storage efficiency, security, and throughput to within constant multiplicative gaps.

The number of shards supported by Polyshard decreases as degree of polynomial increases. One can remove such limitation by using Polyshard iteratively. The main idea of iterative Polyshard is to represent the verification function as a low-depth arithmetic circuit which can be implemented iteratively by computing low-degree polynomials, and then apply Polyshard to the low-degree polynomial iteratively. We show that the number of supported shards can be independent of the degree of function by the following theorem. (see details in Appendix B).

Consider a sharded blockchain whose blocks in each shard are verified by computing a multivariate polynomial of degree $d$ on the blocks in that shard. When implementing this blockchain over $N$ network nodes, up to $\mu$ (for some constant $0\leq\mu<\frac{1}{2}$) fraction of which may be corrupted by quickly-adptive adversaries, the proposed iterative ${\tt PolyShard}$ scheme supports secure block verification from up to $K_{\textup{{\tt Iterative}}}=\lfloor\frac{(1-2\mu)N+1}{2}\rfloor$.

The shard encoding and computation decoding schemes of PolyShard are developed based on the coded computation techniques proposed in , which are used for distributed computing multivariate polynomials subject to arbitrary computation errors. Speficically, it is proposed in to create coded data batches using Lagrange polynomial interpolation, and perform computations directly on coded data. However, in contrast to the scenario of one-shot computation on static data in , the locally stored data at each node is growing in a blockchain system, as more verified blocks are appended to the chain. The requirement of dynamically updating the local coded sub-chain that is compatible with the upcoming coded verification poses new challenges on the design of the PolyShard scheme. Utilizing the data structure of the blockchain, and the algebraic properties of the encoding strategy, we propose a simple incremental sub-chain update policy for PolyShard that requires accessing the minimum amount of data.

The additional coding overhead, including the operations required to encode the incoming blocks, decode verification results, and update the coded shards, does not scale with the length of the sub-chain $t$. When the complexity of computing $f^{t}$, i.e., $c(f^{t})$, grows with $t$, the coding overhead becomes negligible as the chain grows, and the throughput of PolyShard scales linearly with the network size. However, on the other hand, when $c(f^{t})$ is independent of chain length (e.g., verifying digital signature that only requires data from the current block), the coding overhead will dominate the local computation. In this case, while PolyShard still achieves scalability on storage and security, its throughput remains constant as the network grows.

VI Simulation Results

We perform detailed simulations to assess the performance of PolyShard for balance checking described in Section IV. The blockchain system keeps records of all the balance transfers between accounts, and verifies new blocks by comparing them with the sum of the previously verified blocks (i.e., computing the verification function in (4)). More specifically, the system contains $K$ shards, each managing $M$ accounts. At each time epoch $t$, each shard $k$ proposes a block of transactions for verification. On a single computer, we simulate this blockchain system over $N$ network nodes, using full replication, uncoded sharding, and PolyShard schemes respectively. During the simulation, we execute a serial program that performs the local computations of the nodes one after another, and measure each of these computation times in serial. All node instances share the same memory, so the communication delay between nodes is negligible.

We compute the throughput of each scheme under different values of $N$ and $t$ to understand its scalability. Throughput is defined as the number of blocks verified per time unit, and is computed by dividing $K$ (the number of blocks proposed per epoch) by the average computation time (measured during simulation) of the $N$ nodes. For PolyShard, the computation time also includes the time each node spends on encoding the blocks. However, since the encoding time is a constant, whilst the balance summation time increases with $t$ as the chain becomes longer, it is expected that the encoding time is becoming negligible. We note that the storage efficiency and security level of each scheme are decided by system parameters and, thus, do not need measurements.

We simulate this system for $t=1000$ epochs, using different number of shards $K\in$. Each shard manages $M=2000$ accounts. We fix the ratio $N/K=3$. Thus, the number of nodes is $N\in$. We plot the complete relationship between $N$, $t$, and throughput of the three schemes in Figure 6. For a closer look, We plot the relationship between the sub-chain length $t$ and throughput when $N=150$ in Figure 7, and the relationship between the network size $N$ and throughput when $t=1000$ in Figure 4 in Section I.

Throughput: As expected, PolyShard provides the same throughput as uncoded sharding, which is about $K$ times of the throughput of full replication. From Figure 7, we observe that the throughput of all three schemes drops as the time progresses. This is because that the computational complexity of verifying a block increases as more blocks are appended to each shard. In terms of scalability, Fig. 4 indicates that the throughput of PolyShard and uncoded sharding both increases linearly with the network size $N$ (and $K$), whilst the throughput of full replication almost stays the same.

Storage: It is straightforward to see that PolyShard provides the same storage gain over full replication as uncoded sharding, with a factor of $K$. Thus, PolyShard and uncoded sharding are scalable in storage, but full replication is not (Table IIa).

Security: As we have analyzed, full replication can tolerate up to 50% of malicious nodes, achieving the maximum security level $\beta_{\textup{full}}=\frac{N}{2}$. The error-correcting process of PolyShard provides robustness to $\beta_{{\tt PolyShard}}=\frac{N-K}{2}=\frac{N-N/3}{2}=\frac{N}{3}$ malicious nodes. In contrast, under uncoded sharding, each shard is only managed by $3$ nodes. Thus, its security level is only $1$ regardless of $N$, which is not scalable (Table IIb).

In summary, PolyShard outperforms both full replication and uncoded sharding because it is the only scheme that can simultaneously 1) alleviate the storage load at each node; and 2) boost the verification throughput by scaling out the system, and 3) without sacrificing the safety requirement even when the number of adversaries also grows with network size.

VII Discussion

In this section, we discuss how PolyShard fits into the overall architecture of a contemporary blockchain system.

Integration into blockchain systems. We note that Polyshard has so far been described in a simple setting where each shard produces one block in lock-step. We highlight one instantiation of how Polyshard could fit into the architecture of an existing blockchain system, which combines a standard sharding method for proposal followed by Polyshard for finalization. The $K$ shards are obtained by assigning users to shards via a user-assignment algorithm. The $N$ nodes are partitioned into $K$ shards using a standard sharding system (see ). Inside of the shard, the nodes run a standard blockchain along with a finalization algorithm to get a locally finalized version of the block.

Beyond the aforementioned issues, there may be cross-shard transactions present in the system, which are payments or smart contracts with inputs and outputs distributed across multiple shards. In such a case, we will use a locking-based method, which locks the payment at the source shard and produces a certificate to the destination shard so that the amount can be spent; this idea has been proposed as well as implemented in Elastico and Omniledger .

Relationship to verifiable computing. An alternative paradigm for accelerating computing in blockchain is verifiable computing , where a single node executes a set of computations (for example, payment validation) and integrity of these computations are then cryptographically certified. A major difference between our framework and verifiable computing is that our scheme is information-theoretically secure against a computationally unbounded adversary as against the computational security offered by verifiable computing schemes. However, verifiable computing schemes can provide zero-knowledge proofs, whereas our scheme does not offer zero-knowledge capability. Finally, verifiable computing is relevant in an asymmetric setting, where one computer is much more powerful than the others, unlike Polyshard that is designed for a symmetric setup comprising of equally powerful and decentralized nodes.

Future research directions. Polyshard currently works with polynomials whose degree scales sub-linearly with the number of nodes. An interesting direction of future work is to remove this limitation. In particular, computations that can be represented as low-depth arithmetic circuits can be implemented iteratively using low-degree polynomials. Another important direction of future research is the design of validation schemes that can be represented as low-degree polynomials or low-depth arithmetic circuits.

References

Appendix A Field extension for general Boolean functions

For general blockchain systems that verify incoming blocks based on the most recent $0\leq P\leq t-1$ verified blocks, we can generally model each incoming block $X_{k}(t)$, and each verified block $Y_{k}(m)$ as a binary bit stream of length $T$, and the verification function $f^{t}:\{0,1\}^{T(P+1)}\rightarrow\{0,1\}$ as a Boolean function that indicates whether $X_{k}(t)$ is valid or not.

Using the construction of [37, Theorem 2], we can represent any arbitrary Boolean function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ whose inputs are $n$ binary variables as a multivariate polynomial $p$ of degree $n$ as follows. For each vector $\mathbf{a}=(a_{1},\ldots,a_{n})\in\{0,1\}^{n}$, we define $h_{\mathbf{a}}=z_{1}z_{2}\cdots z_{n}$, where $z_{i}=x_{i}$ if $a_{i}=1$, and $z_{i}=y_{i}$ if $a_{i}=0$. Next, we partition $\{0,1\}^{n}$ into two disjoint subsets $S_{0}$ and $S_{1}$ as follows.

The polynomial $p$ is then constructed as

We note that this model applies to verifying the digital signatures, where the verification does not depend on past blocks, i.e., $P=0$. Utilizing the above technique, we can transfer any non-polynomial computations like inversions and cryptographic hash functions (e.g., SHA-2) into polynomial evaluations.

Appendix B Iterative Polyshard

In Section V, we show that the number of shards can be supported by Polyshard is up to $K_{\textup{{\tt PolyShard}}}=\lfloor\frac{(1-2\mu)N-1}{d}+1\rfloor$, which decreases as the degree of polynomial increases. To remove this limitation, we propose iterative Polyshard which can work with polynomials whose degree is high. The main idea of iterative Polyshard is to represent the verification function as a low-depth arithmetic circuit which can be implemented iteratively by computing low-degree polynomials, and then apply the Polyshard scheme to the low-degree polynomial of each iteration.

Before applying iterative Polyshard to the verification functions, we model functions to some arithmetic circuits. An arithmetic circuit is a directed acyclic graph that can be used to compute a polynomial of inputs over certain field. Nodes of the graph are referred to as gates. Every node with zero indegree is an input gate and is labeled by either a variable or an element of the underlying field. Every other node is either a addition gate or a multiplication gate labeled by $+$ and $\times$, respectively. Gate $u$ is a child of gate $v$ if there is a directed edge from $v$ to $u$ in the graph. Each addition (multiplication) gate computes the sum (product) of the polynomials computed by their parent gates. See Figure 8 for an example of an arithmetic circuit that computes the polynomial $f(x_{1},x_{2})=x_{1}^{2}x_{2}+x_{1}x_{2}$. To model verification functions, we consider the class of arithmetic circuits in which each layer satisfies the following conditions:

Each addition gate has arbitrary number of inputs.

Each layer consists of addition gates followed by multiplication gates.

Edges within each layer are only from addition gates to multiplication gates.

The outputs of multiplication gates are the inputs of addition gates in the following layer.

For any polynomial with degree $d$, there exists an arithmetic circuit satisfying the above conditions with $\lceil\log{d}\rceil+1$ layers. It implies that the arithmetic circuits of verification function can be low-depth.

For the arithmetic function of verification function $f^{t}$, we define the following terms. For each layer $l\in[1:L]$ ($L$ is the number of layers), we denote the number of multiplication gates by $A_{l}$. In layer $l$, there are $A_{l}$ intermediate polynomials (outputs of multiplication gates) denoted by $f^{t}_{(l,1)},\ldots,f^{t}_{(l,A_{l})}$. The inputs of layer $l$ are denoted by $(X^{l}_{1}(t),\ldots,X^{l}_{K}(t))$. For layer $1$, we have $X^{1}_{k}(t)=\{X_{k}(t),Y^{t-1}_{k}\}$. Because of the structure of arithmetic circuits we consider, for each layer $l\in[2:L]$, we have $X^{l}_{k}(t)=\{f^{t}_{(l-1,1)}(X^{l-1}_{k}(t)),\ldots,f^{t}_{(l-1,A_{l-1})}(X^{l-1}_{k}(t))\}$. Then, the outputs of multiplication gates in layer $L$ is the computation of verification function, i.e., $f^{t}(X_{k}(t),Y_{k}^{t-1})=(f^{t}_{(L,1)}(X^{l}_{k}(t)),\ldots,f^{t}_{(L,A_{L})}(X^{l}_{k}(t)))$.

Let’s illustrate the arithmetic circuits through the following example.

Example. We consider verification function

An arithmetic circuit satisfying the above conditions that computes $f^{t}$ is depicted in Figure 9. The arithmetic circuit for function $f^{t}$ consists two layers. The input of the first layer is $(X^{1}_{1}(t),\ldots,X^{1}_{K}(t))$, where $X^{1}_{k}(t)=X_{k}=(x_{k1},\ldots,x_{k5})$, for each $k\in[1:K]$. At the end of the first layer, $f^{t}_{(1,1)}(X_{k}),f^{t}_{(1,2)}(X_{k}),f^{t}_{(1,3)}(X_{k})$ for each $k\in[1:K]$ are computed. The inputs of layer $2$ is $(X^{2}_{1}(t),\ldots,X^{2}_{K}(t))$, where $X^{2}_{k}(t)=(f^{t}_{(1,1)}(X_{k}),f^{t}_{(1,2)}(X_{k}),f^{t}_{(1,3)}(X_{k}))$. At the end of the layer $2$, $f^{t}_{(2,1)}(X^{2}_{k}(t))=f^{t}_{(2,1)}(f^{t}_{(1,1)}(X_{k}),f^{t}_{(1,2)}(X_{k}),f^{t}_{(1,3)}(X_{k}))=f(X_{k})$, for each $k\in[1:K]$ are computed.

B-B Iterative coded verification

The block verification process of iterative PolyShard has $L$ iterations. Each iteration $l\in[1:L]$ has the following three steps.

Step 3: decoding. Since each intermediate function $f^{t}_{(l,a)}$ is a polynomial of degree $2$ over the inputs of layer $l$. To decode $f^{t}_{(l,1)},\ldots,f^{t}_{(l,A_{l})}$ from $g^{t}_{(l,1)},\ldots,g^{t}_{(l,N)}$, each node needs to decode a Reed-Solomon code with dimension $2(K-1)+1$ and length $N$. To successfully decode the results, it requires the number of errors $\mu N\leq(N-2(K-1)-1)/2$. That is, the maximum number of shards $K$ that can be securely supported is $K_{\textup{{\tt Iterative}}}=\lfloor\frac{(1-2\mu)N+1}{2}\rfloor$.

B-C Performance of iterative Polyshard

As shown in Theorem 2, we have that the maximum number of shards supported by iterative Polyshard is independent of the degree of verification function. Moreover, iterative PolyShard achieves a storage efficiency $\gamma_{\textup{{\tt Iterative}}}=\gamma_{\textup{{\tt Polyshard}}}=\Theta(N)$, and it is also robust against $\mu N=\Theta(N)$ quickly-adaptive adversaries. Then, the total number of operations during the verification and the sub-chain update processes is $O(NK)+Nc(f^{t})+O(N^{2}\log^{2}N\log\log N)$. The coding overhead reduces to $O(N^{2}\log^{2}N\log\log N)$ since $K_{\textup{{\tt Iterative}}}\leq N$. The throughput of iterative PolyShard is computed as

When $c(f^{t})$ grows with $t$, the throughput of iterative ${\tt PolyShard}$ becomes $\lambda_{\textup{{\tt Iterative}}}=\Theta(N)$, i.e., iterative PolyShard simultaneously achieves the information-theoretically optimal storage efficiency, security, and throughput to within constant multiplicative gaps.