Notable Works in Blockchain Scaling

Scaling
,
1

Systematization of Knowledge:

  • SoK: Consensus in the Age of Blockchains.

    • Citation: https://arxiv.org/pdf/1711.03936.pdf. Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, George Danezisa
    • Summary: This SoK presents a systematic and comprehensive study of consensus protocols. The authors describe protocols based on proof-of-work(PoW), proof-of-X (PoX) protocols that replace PoW with more energy-efficient alternatives and hybrid protocols that are compositions or variations of classical consensus protocols.
    • This paper compares many consensus designs, not just on performance (real/simulated throughput), but also on safety assumptions and permissions through a classical consensus lens. It captures the boom in proposals for Proof-of-Stake protocols in replacement of PoW. This is interesting to compare in hindsight with live implementations and the current state of the art in cryptocurrencies.
    • Tags: bft, consensus, proof-of-work, proof-of-stake

  • SoK: Research perspectives and challenges for Bitcoin and cryptocurrencies

    • Citation: https://www.ieee-security.org/TC/SP2015/papers-archived/6949a104.pdf. Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, Edward W. Felten
    • Summary: This paper is a comprehensive introduction to Bitcoin and cryptocurrency tools, theories, and the ecosystem.
    • This paper was the first systematic study of Bitcoin, bridging the gap between nascent research on blockchains and their live implementation, which, surprisingly for researchers, “worked so far”. They focus on many parts of the protocol and ecosystem, with a special interest in privacy and disintermediation (decentralization).
    • Tags: consensus, proof-of-work

  • SoK: Layer-Two Blockchain Protocols

    • Citation: https://eprint.iacr.org/2019/360.pdf. Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, Patrick McCorry, Arthur Gervais
    • Summary: This SoK provides a systematic overview of Layer-Two systems since the inception of cryptocurrencies, and identifies the complete set of proposed Layer-Two protocol types, which are channels, commit-chains, and protocols for refereed delegation. It also studies the associated synchronization and routing protocols along with their privacy and security aspects.
    • Tags: scalability, layer-2, payment-channel, rollups

Scalability studies and comparisons:

  • On Scaling Decentralized Blockchains

    • Citation: https://www.initc3.org/files/Scaling2016.pdf. K. Croman, C. Decker, I. Eyal, A.E. Gencer, A. Juels, A. Kosba, A. Miller, P. Saxena, E. Shi, E. G. Sirer, D. Song and R. Wattenhofer
    • Summary: This paper analyzes bottlenecks in Bitcoin’s ability to scale to higher throughputs and lower latencies. They look into many parts of the system, among them the network, consensus, and storage, to conclude that a change of parameters is only the first step and not enough for scalability.
    • The paper explores how the current network could achieve higher scalability. For example, they measure the impact big blocks could have and propose sustainable new parameters. They also emphasize how new designs are needed and where the research could focus to do so.
    • Tags: scalability, consensus

  • Information Propagation in the Bitcoin Network

    • Citation: https://www.gsd.inesc-id.pt/~ler/docencia/rcs1314/papers/P2P2013_041.pdf. Christian Decker; Roger Wattenhofer
    • Summary: This paper analyzes how information travels through the Bitcoin network from one peer to another. They formalize the link between network propagation and fork occurrence. This was the first major study of the Bitcoin underlying peer-to-peer network. It gave insight into how a low propagation speed can cause wasting computations and increase attacker relative power.
    • Tags: scalability, network-security, proof-of-work

  • BLOCKBENCH: A Framework for Analyzing Private Blockchains

    • Citation: https://arxiv.org/pdf/1703.04057.pdf. Tien Tuan Anh Dinh, Ji Wang, Gang Chen, Rui Liu, Beng Chin Ooi, Kian-Lee Tan
    • Summary: BLOCKBENCH is a benchmarking framework to understand and compare the performance of permissioned blockchains. Drawing inspiration from database literature, it proposes smart contract use cases to stress test latency, throughput, scalability, and fault tolerance.
    • The authors built a test framework and benchmarked Ethereum, Parity, and Hyperledger implementations. It gives a unified ground to evaluate different consensus configurations, in the permissioned setting, which is a complex task and uncommon in blockchain research.
    • Tags: simulation, scalability, consensus

  • On the Security and Performance of Proof of Work Blockchains

    • Citation: https://eprint.iacr.org/2016/555.pdf. Arthur Gervais, Ghassan O. Karame, Karl Wüst, Vasileios Glykantzis, Hubert Ritzdorf, and Srdjan Capkun
    • Summary: In this paper, the authors study the relationship between the security and the performance implications of various consensus and network parameters of PoW blockchains. Using this framework, they capture the security properties of existing chains (Bitcoin, Ethereum, Litecoin, and Dogecoin) as well as other possible instantiations subject to different consensus and network parameters.
    • This paper gives insight into the impact of the parameters of a PoW blockchain on scalability and security. It gives a framework to assess how a re-parametrization would perform. They also devise the number of confirmations to wait for a block to be notarized on the blockchain based on attacker power.
    • Tags: scalability, network-security, proof-of-work, simulation

Blockchain design proposals:

  • Secure High-Rate Transaction Processing in Bitcoin.

    • Citation: https://fc15.ifca.ai/preproceedings/paper_30.pdf. Yonatan Sompolinsky, Aviv Zohar
    • Summary: This paper proposes an alternative to the longest-chain rule called GHOST, that changes the conflict-resolution procedure for the blockchain. At each fork in the chain, GHOST selects the heaviest subtree rooted at the fork. A variant of GHOST is the base of uncle blocks in Ethereum that permit a much lower block time than Bitcoin. The authors first recall the impact of increasing throughput by increasing the block size or reducing the block time: more forks.
    • GHOST uses those forks that naturally appear in the network to choose the main chain. Even though the content of the forks will not be used, they are Proof of Work that can be counted toward the main chain security.
    • Tags: scalability, consensus, proof-of-work

  • Bitcoin-NG: A Scalable Blockchain Protocol.

    • Citation: https://www.usenix.org/system/files/conference/nsdi16/nsdi16-paper-eyal.pdf. Ittay Eyal, Adem Efe Gencer, Emin GĂźn Sirer, and Robbert van Renesse
    • Summary: This paper tackles the throughput limitations of Bitcoin through decoupling of two important phases: leader election and transaction serialization. Once a leader is elected, she can order and confirm transactions as she pleases until the next leader election.
    • This paper is important because it shows that Bitcoin bundles many operations into one and that by carefully dividing those steps, one can improve the performance without introducing new security assumptions.
    • Tags: scalability, consensus, proof-of-work

  • OmniLedger: A Secure, Scale-out, Decentralized Ledger via Sharding

    • Citation: https://eprint.iacr.org/2017/406.pdf. Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford
    • Summary: This paper introduces horizontal scaling “à la” database scaling, through sharding while retaining decentralization and security. It introduces several contributions to avoid security pitfalls such as DoS attacks or scalability bottlenecks like cross-shard commitments and communication.
    • Tags: consensus, bft, proof-of-work, proof-of-stake

  • Scaling Nakamoto Consensus to Thousands of Transactions per Second

    • Citation: https://arxiv.org/pdf/1805.03870.pdf. Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, and Andrew Yao
    • Summary: This protocol goes a step further than the GHOST protocol and Ethereum’s uncles. It uses transactions from forks that naturally occur when there is no conflict to increase throughput. This scheme gives a total order of the transactions from the directed acyclic graph (DAG), instead of a chain of blocks.
    • Tags: scalability, consensus

  • Serialization of Proof-of-work Events: Confirming Transactions via Recursive Elections (SPECTRE)

    • Citation: https://eprint.iacr.org/2016/1159.pdf. Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar
    • Summary: This paper introduces a DAG to Bitcoin that includes all blocks on the ledger. Using blocks as votes on previous and recent blocks, hence the DAG, they can order each pair of blocks. The one with the majority’s aggregate vote becomes irreversible very quickly. This gives a partial order such that conflicting transactions can be rejected from the notarized history.
    • Tags: scalability, consensus

Layer 2 approaches:

  • The Bitcoin Lightning Network

    • Citation: https://www.bitcoinlightning.com/wp-content/uploads/2018/03/lightning-network-paper.pdf. Joseph Poon and Thaddeus Dryja
    • Summary: This paper describes the main approach to scalability in the Bitcoin protocol using a separate network, a Layer-Two, of payment channels. The Lightning Network enables two users to open, update, and close trustless-ly bi-directional channels to do micropayments off-chain with extensive use of Multisig, Timelocks, and HTLCs (Hash Time locked Contracts). Only the opening and the closing transactions end up on-chain. Leveraging those channels, one user can find a path to transfer satoshis to another user, thus creating a network of payment channels.
    • Tags: scalability, layer-2, payment-channel

  • A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels

    • Citation: https://tik-db.ee.ethz.ch/file/716b955c130e6c703fac336ea17b1670/duplex-micropayment-channels.pdf. Christian Decker and Roger Wattenhofer
    • Summary: This paper presents a duplex micropayment channel protocol, another L2 scaling solution for Bitcoin. It is interesting because it proposes another way of using HTLC, Timelocks, and Multisig to create a network of channels like the Lightning protocol. The tx are organized in a tree-like structure, called the invalidation tree, where the most recent tx have the lowest timelock and hence can be redeemed before older tx/state.
    • Tags: scalability, layer-2, payment-channel

  • Teechain: A Secure Payment Network with Asynchronous Blockchain Access

    • Citation: https://arxiv.org/pdf/1707.05454.pdf. Joshua Lind, Oded Naor, Ittay Eyal, Florian Kelbert, Peter Pietzuch, and Emin GĂźn Sirer
    • Summary: Teechain is an L2 scaling protocol using trusted execution environments (TEEs). This paper presents a payment network that executes off-chain transactions asynchronously, harnessing the power of TEEs, to establish off-chain payment channels between parties. It uses committees of TEEs to prevent theft or loss of funds and removes the requirement to access the underlying blockchain under a bounded time. Teechain can function correctly even in the presence of a compromised or failing subset of TEEs.
    • Tags: scalability, layer-2, payment-channel

  • Plasma: Scalable Autonomous Contracts

    • Citation: https://www.plasma.io/plasma-deprecated.pdf. Joseph Poon and Vitalik Buterin
    • Summary: Plasma is an L2 proposal for a smart contract chain that aims to increase blockchain scalability by only publishing Root hashes of the off-chain Merkle tree to the L1 blockchain. The plasma chains can be organized in a Merkle tree hierarchy of parent-children chains. Disputes can be resolved by users on any of the parent chains or directly to the L1 chain.
    • Tags: scalability, layer-2

  • Arbitrum: Scalable, private smart contracts

    • Citation: https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf. Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, and Edward W. Felten
    • Summary: This paper describes an Optimistic Rollup, an L2 scaling solution for smart contracts. This protocol uses mechanism design to reach an agreement off-chain on the VM execution. Malicious behavior is penalized by a loss of deposit after a challenge is resolved in a multi-round game. Honest parties can advance the VM state on-chain.
    • Tags: scalability, layer-2, rollups

  • An Incomplete Guide to Rollups

    • Citation: An Incomplete Guide to Rollups. Vitalik Buterin
    • Summary: This is a blog post that presents an overview of scaling blockchains, specifically Ethereum, through Rollups. It gives a quick definition of state channel and plasma scaling, before expanding on the general design of Rollups and the main two flavors: Optimistic and ZK-based. It concludes with the current unsolved issues, such as cross-rollup transactions.
    • Tags: scalability, layer-2, rollups
5 Likes