PaperlayerView exact revision on arXiv

Source-linked AI summary

PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously

Songze Li, Mingchao Yu, Chien-Sheng Yang, A. Salman Avestimehr, Sreeram Kannan, Pramod Viswanath

arXiv:1809.10361v2cs.CRcs.DCcs.ITmath.IT

TL;DR

Existing blockchain designs trade off scaling efficiency against security, even though information-theoretic bounds allow all three measures to scale linearly. PolyShard uses polynomially coded sharding; the paper reports simultaneous scaling and payment-blockchain simulations in which throughput grows with network size. Its stated scope excludes cross-shard transactions.

  • Problem

    Existing blockchain designs trade off throughput and storage scaling against security, although the information-theoretic upper bounds for throughput, storage efficiency, and security are each Θ(N).

    Source: §I · p. 2

  • Method

    PolyShard introduces polynomially coded sharding, with verification-independent coding and incremental shard growth.

    Source: §I · p. 2

  • Results

    PolyShard and uncoded sharding throughput both increase linearly with network size N, while full replication stays nearly constant; PolyShard throughput is about K times full replication.

    Source: §VI · p. 8

  • Takeaways & Limitations

    Payment-blockchain simulations provide empirical verification of PolyShard's theoretical guarantees for scaling storage efficiency, security, and throughput.

    Source: §I · p. 3, §VI · p. 9

    The paper focuses on intra-shard transactions; cross-shard transactions and their verification are outside its scope.

    Source: A. Computation model · p. 3

Abstract

from arXiv · show

Today's blockchain designs suffer from a trilemma claiming that no blockchain system can simultaneously achieve decentralization, security, and performance scalability. For current blockchain systems, as more nodes join the network, the efficiency of the system (computation, communication, and storage) stays constant at best. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. In this paper, we settle the trilemma by demonstrating a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: ``polynomially coded sharding'' scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

I. INTRODUCTION

The introduction asks whether a decentralized blockchain can escape the trade-off among security, decentralization, and scalability. It proposes PolyShard, a coded-sharding design, and reports linear scaling across throughput, storage efficiency, and security.

I. INTRODUCTION

  • Full replication keeps storage efficiency and throughput constant as N grows, while sharding's K-fold gains require shrinking shards whose security falls toward zero.With K shards, each has q = N/K nodes, and an attacker can compromise a shard by corrupting as few as q/2 nodes.Source: §I · pp. 1–2
  • PolyShard is presented as simultaneously attaining linear scaling and information-theoretic upper bounds in throughput, storage efficiency, and security.The paper frames this as addressing whether the blockchain trilemma is fundamental to decentralized systems.Source: §I · p. 2
  • PolyShard replaces uncoded shards with same-size shards formed by linearly mixing the originals, using polynomial coding to add redundancy against malicious verification results.Noisy polynomial interpolation techniques, such as Reed-Solomon decoding, support security against erroneous results from malicious nodes.Source: §I · p. 2
  • Its coding is oblivious to the verification function, so the same coded data can serve multiple checks, and incremental updates keep coding overhead constant as the chain grows.Nodes can code over newly verified blocks without accessing previous blocks.Source: §I · p. 2
  • In payment-blockchain simulations, PolyShard throughput scales with network size like uncoded sharding, significantly improving over full replication.The simulations evaluate throughput, storage, and security across full replication, sharding, and PolyShard.Source: Figure 4 · p. 3, §I · p. 3

iterative Polyshard

PolyShard applies coding to both storage and computation to address the blockchain trilemma. The section frames verification as checking proposed shard blocks against current sub-chain state, while focusing on intra-shard transactions.

iterative Polyshard

  • PolyShard represents verification functions as low-depth arithmetic circuits and applies the scheme iteratively to each circuit layer.This is the stated approach for iterative PolyShard.Source: iterative Polyshard · p. 3
  • PolyShard proposes coding in both storage and computation and claims linear scaling in throughput, storage efficiency, and security, meeting the information-theoretic limits.The paper presents this design as formalizing and resolving a version of the blockchain trilemma.Source: iterative Polyshard · p. 3

II. PROBLEM FORMULATION: BLOCK VERIFICATION

  • At each epoch, a proposed block is verified against its shard’s current sub-chain state before a verified block is appended to that sub-chain.The verification function operates on the proposed block and the current state; invalid blocks are represented by an all-zero block.Source: §II · p. 3, A. Computation model · p. 3

A. Computation model

  • For cryptocurrency block verification, examples include balance checking and signature checking.Balance checking tests funds and fees, while signature checking verifies that a payment was submitted by the account owner.Source: A. Computation model · p. 3
  • The formulation focuses on intra-shard transactions; cross-shard transactions add complexity but are described as complementary extensions.The paper notes that atomic payment and locking mechanisms of can be incorporated.Source: A. Computation model · p. 3

B. Networking model

The networking model considers synchronous nodes with bounded communication delay and Byzantine faults. Nodes exchange intermediate computations, decode verification results, and update local storage, with incremental coding intended to limit update overhead.

B. Networking model

  • The model assumes homogeneous, synchronous nodes with bounded pairwise communication delay and allows Byzantine nodes to return arbitrary erroneous results.The adversary can corrupt a fixed fraction of nodes and adaptively choose which nodes to attack when shard assignments are known.Source: B. Networking model · p. 4
  • Nodes compute intermediate results on proposed blocks and local storage, broadcast them, then use decoded verification results to update local storage.The described process includes decoding results for all shards before computing verified blocks.Source: B. Networking model · p. 4
  • Incremental storage updates create a coded block from newly verified shard blocks and append it without revisiting earlier blocks.The stated benefit is reduced computational and storage complexity.Source: B. Networking model · p. 4
  • The adversary model is defined for a permissioned setting and is stated to extend to permissionless systems where adversaries control a fixed fraction of hashing power.The paper gives proof-of-work as an example.Source: B. Networking model · p. 4

C. Performance metrics

The paper defines storage efficiency, security, and throughput as performance measures corresponding to the blockchain trilemma. It aims to find their information-theoretic limits and design schemes that achieve them simultaneously.

C. Performance metrics

  • Storage efficiency is the ratio of the entire blockchain’s size to the data stored at each node.The scheme is introduced as a sequence of function collections.Source: C. Performance metrics · p. 4
  • A scheme’s security is the maximum number of malicious nodes it can tolerate while honest nodes recover correct verification results.The definition requires correctness for every malicious-node subset up to the stated bound.Source: C. Performance metrics · p. 4
  • Throughput is the average number of correctly verified blocks per discrete round, accounting for computation across all nodes.The paper measures function computational complexity by the number of additions and multiplications needed for evaluation.Source: C. Performance metrics · p. 4

III. BASELINE PERFORMANCE

The baseline comparison shows that conventional full replication and uncoded sharding trade off throughput, storage efficiency, and security. PolyShard uses coded storage and computation, including in a payment-chain design where nodes store coded sub-chains.

III. BASELINE PERFORMANCE

  • Security, storage efficiency, and throughput each have information-theoretic upper bounds that scale linearly with network size N.Full replication keeps storage efficiency and throughput constant, while uncoded sharding scales both by increasing the number of shards and leaves security constant under dynamic adversaries.Source: §III · p. 5
  • PolyShard stores coded blockchain data at each node and computes verification functions directly on that coded data to target all three upper bounds.The approach is motivated by the trade-offs of full replication and conventional sharding.Source: §III · p. 5

IV. POLYSHARD FOR BALANCE CHECKING

  • For balance checking, each shard's transactions are checked against prior balances, and a block is valid when the output has no negative entries.The paper retains the ledger's chain structure rather than storing only aggregate balances, which would discard transaction statistics and weaken protection against tampering.Source: §IV · p. 5

A. Coded sub-chain

  • Lagrange interpolation generates each node's coded block by mixing the verified blocks from all K shards for that epoch.Each node stores the polynomial evaluation at its assigned point, using coefficients that do not depend on time.Source: A. Coded sub-chain · pp. 5–6
  • Each coded sub-chain is K times smaller than the entire blockchain, giving PolyShard storage efficiency γPolyShard = K.The encoding is independent of the verification function, so the same coded sub-chain can serve multiple verification items, including digital signatures and smart contracts.Source: A. Coded sub-chain · p. 6

B. Coded verification

PolyShard verifies proposed blocks by encoding them across nodes, computing the verification function on coded data, and decoding the results. Reed-Solomon decoding sets the shard count according to the desired tolerance of erroneous results.

B. Coded verification

  • Each node linearly combines the K proposed blocks using the same encoding coefficients to form its coded block.This encoding step requires O(NK) operations across the network.Source: B. Coded verification · p. 6
  • Each node applies the verification function to its coded block and locally stored coded sub-chain, then broadcasts the intermediate result.Source: B. Coded verification · p. 6
  • Nodes decode the degree-(K − 1) polynomial from evaluations at N distinct points using Reed-Solomon decoding.The decoded polynomial is evaluated at the shard points to recover the verification results.Source: B. Coded verification · p. 6
  • To decode robustly against µN erroneous results (security βPolyShard = µN), a node requires 2µN ≤ N − K; PolyShard sets KPolyShard = ⌊(1 − 2µ)N⌋, scaling linearly with network size N.Source: B. Coded verification · p. 6

C. Performance of PolyShard

PolyShard achieves information-theoretically optimal scaling in security, storage efficiency, and throughput under the stated chain-growing verification setting. Its coding overhead does not grow with chain length, but its generality distinguishes it from storage codes for linear verification functions.

C. Performance of PolyShard

  • The verification and sub-chain update operations add O(NK) and O(N^2 log2 N log log N) coding overhead beyond uncoded sharding.The paper notes that the latter term bounds the coding overhead when KPolyShard ≤ N.Source: C. Performance of PolyShard · pp. 6–7
  • PolyShard simultaneously achieves information-theoretically optimal scaling in security, storage efficiency, and throughput.Encoding and decoding overhead does not scale with chain length, so it becomes irrelevant as the chain grows.Source: C. Performance of PolyShard · p. 7
  • For verification functions linear in block data, distributed-storage codes can achieve similar scaling, but PolyShard also handles arbitrary multivariate polynomials.The cited passage says state-of-the-art storage codes cannot handle that more general class of verification functions.Source: C. Performance of PolyShard · p. 7

V. POLYSHARD FOR GENERAL VERIFICATION FUNCTIONS

For general verification functions represented by multivariate polynomials, PolyShard applies coded block verification and Reed-Solomon decoding. The shard count depends on polynomial degree in the basic scheme, while iterative PolyShard is proposed to remove that dependence; throughput scaling also depends on verification cost growing with chain length.

V. POLYSHARD FOR GENERAL VERIFICATION FUNCTIONS

  • PolyShard applies its coded verification process to multivariate polynomial functions, with Reed-Solomon decoding dimension determined by polynomial degree and shard count.The supported shard count is KPolyShard = ⌊(1−2µ)N−1 over d + 1⌋ as specified in the passage.Source: §V · p. 7
  • For degree-d verification, PolyShard achieves Θ(N) storage efficiency and security, while throughput is Θ(N) when verification cost grows with chain length.The paper gives balance checking, whose cost is Θ(t), as an example of a chain-growing verification function.Source: §V · p. 7
  • Iterative PolyShard represents verification as a low-depth arithmetic circuit and applies PolyShard iteratively to low-degree polynomials.The paper proposes this approach so the supported shard count can be independent of the verification function's degree.Source: §V · p. 7
  • The coding and decoding design is paired with an incremental sub-chain update policy that accesses only newly verified blocks.The authors describe this update policy as addressing the challenge of dynamically growing local coded sub-chains.Source: §V · p. 8
  • When verification cost is independent of chain length, coding overhead dominates and throughput remains constant as the network grows, although storage and security still scale.Source: §V · p. 8

VI. SIMULATION RESULTS

The simulations compare throughput, storage efficiency, and security across full replication, uncoded sharding, and PolyShard. PolyShard combines sharding-like throughput and storage gains with security that grows with network size; the discussion outlines an integration path and practical trade-offs.

VI. SIMULATION RESULTS

  • The simulations use serial computation on one computer, with shared memory making inter-node communication delay negligible.They vary network size and chain length; throughput is blocks verified per time unit, based on proposed blocks and average computation time.Source: §VI · p. 8
  • As the chain grows, all three schemes’ throughput falls; with increasing network size, PolyShard and uncoded sharding scale throughput linearly while full replication stays nearly constant.The reported decline reflects the increased complexity of verifying blocks as more blocks are appended.Source: §VI · p. 8, Figure 7 · p. 9
  • PolyShard matches uncoded sharding’s throughput and K-fold storage gain while tolerating (N−K)/3 malicious nodes, unlike uncoded sharding’s fixed tolerance of one.The paper concludes that PolyShard scales throughput and verification safety without sacrificing storage load reduction.Source: §VI · pp. 8–9

VII. DISCUSSION

  • The proposed integration uses standard shards for block proposal and local finalization, then PolyShard for global coded validation of locally finalized blocks.Users can wait for global finalization for higher trust or use local finalization for shorter latency.Source: §VII · p. 9
  • Cross-shard payments or contracts may use source-shard locking and a certificate sent to the destination shard.The passage identifies this approach as proposed and implemented in Elastico and Omniledger.Source: §VII · p. 9
  • PolyShard currently supports polynomials with degree scaling sub-linearly in node count; removing this limit and designing low-degree or low-depth validation functions remain future directions.The discussion contrasts PolyShard’s information-theoretic security with verifiable computing’s computational security and notes that PolyShard does not provide zero-knowledge proofs.Source: §VII · p. 9

APPENDIX A FIELD EXTENSION FOR GENERAL BOOLEAN FUNCTIONS

The appendix describes representing blockchain verification as polynomial computation, including Boolean functions over binary data. It then motivates iterative PolyShard for higher-degree functions and models verification with low-depth arithmetic circuits.

APPENDIX A FIELD EXTENSION FOR GENERAL BOOLEAN FUNCTIONS

  • A verification function can treat each incoming block and up to P previously verified blocks as binary streams, returning whether the incoming block is valid.For digital-signature verification, P=0; the construction also transfers non-polynomial computations such as inversions and SHA-2 into polynomial evaluations.Source: Appendix A · pp. 10–11
  • Boolean verification polynomials can be encoded over an extension field large enough to supply N distinct evaluation points, and the embedding preserves the verification result.The construction embeds binary elements into F2^m with 2^m ≥ N before selecting distinct field elements.Source: Appendix A · p. 11

APPENDIX B ITERATIVE POLYSHARD

  • Iterative PolyShard addresses the shard-count limit imposed by polynomial degree by applying PolyShard to low-degree polynomials computed across iterations of a low-depth verification circuit.The appendix identifies removing the degree limitation as a motivation for this approach.Source: Appendix B · p. 11

A. Arithmetic circuit modeling for verification functions

  • The verification circuits use addition and two-input multiplication gates in layers, with multiplication outputs feeding addition gates in the next layer.Any degree-d polynomial has a circuit of this form with ⌈log d⌉+1 layers, so verification circuits can be low-depth.Source: A. Arithmetic circuit modeling for… · p. 11

B. Iterative coded verification

Iterative coded verification processes a block through repeated encoding, coded computation, and decoding. Each iteration operates on the circuit’s intermediate polynomials, while Reed–Solomon decoding sets the shard and error tolerance.

B. Iterative coded verification

  • Each iteration encodes blocks as linear combinations using the scheme’s coefficients, requiring O(NK) operations across the network.Each of N nodes computes a linear combination of K blocks.Source: B. Iterative coded verification · p. 12
  • Nodes apply the circuit’s intermediate functions directly to their coded inputs and broadcast the results to all other nodes.The per-node computation follows the arithmetic circuit for the verification function.Source: B. Iterative coded verification · p. 12
  • Decoding each intermediate function uses Reed–Solomon codes of dimension 2(K−1)+1 and length N, with the error bound constraining how many shards can be supported.After L iterations, nodes evaluate the verification function at the designated points, recover the verified blocks, and append coded blocks to their sub-chains at O(NK) cost.Source: B. Iterative coded verification · p. 12

C. Performance of iterative Polyshard

Iterative PolyShard removes the shard-count dependence on verification-function degree and retains scaling in storage and security. When computation cost grows with chain length, its throughput scales linearly with network size, meeting the stated information-theoretic bounds within constant factors.

C. Performance of iterative Polyshard

  • The maximum number of supported shards is independent of verification-function degree, while storage efficiency is Θ(N) and robustness covers µN=Θ(N) quickly-adaptive adversaries.The total verification and sub-chain update work is O(NK)+Nc(f^t)+O(N^2 log^2 N log log N).Source: C. Performance of iterative Polyshard · p. 12
  • When c(f^t) grows with t, iterative PolyShard achieves Θ(N) throughput and simultaneously reaches information-theoretic optimal storage efficiency, security, and throughput within constant multiplicative gaps.The throughput expression accounts for the supported shard count and coding overhead relative to computation cost.Source: C. Performance of iterative Polyshard · p. 12
Loading 1809.10361v2…