A Circuit Approach to Constructing Blockchains on Blockchains

Ertem Nusret Tas, David Tse, Yifei Wang

Abstract

This paper introduces a formal "circuit" framework for constructing highly secure overlay blockchains by composing multiple existing underlay blockchains. Inspired by Claude Shannon’s seminal work on switching circuits, the authors define modular "gates"—specifically serial and triangular compositions—to achieve optimal tradeoffs between safety and liveness. By treating individual chains as modular components, the framework allows for decoupled security guarantees, enabling the creation of protocols that are more resilient than the sum of their parts. The authors prove the optimality of these constructions through matching impossibility results in distributed computing.

Introduction

We currently live in a "multi-chain world" where hundreds of independent blockchains exist, each with its own set of validators and security assumptions. A critical question for developers is: How can we build a new protocol that is more secure than the sum of its parts? Existing solutions like interchain timestamping or "Trustboost" offer some answers, but they are often rigid, typically coupling safety (the ledger won't fork) and liveness (new transactions will keep being added) together. This paper provides a generalized, mathematical framework to construct overlay chains with precise, decoupled security guarantees tailored to specific needs.

Methods: The Blockchain Circuit Analogy

The authors draw a brilliant analogy to switching circuits to define how blockchains can be composed. By treating blockchain security properties as boolean states, they define two fundamental "gates" or compositional operations:

  1. Serial Composition (The "Safety OR" Gate): Based on interchain timestamping. If you compose two chains serially, the resulting overlay is safe if at least one of the two is safe, but it is only live if both are live.
  2. Triangular Composition (The "Liveness Majority" Gate): Using an Omission-Fault Tolerant (OFT) protocol across three chains. This overlay is safe only if all three underlay chains are safe, but it remains live if any two of them are live.
Comparison between classical switching circuits and the proposed blockchain circuit framework.

By recursively combining these serial and triangular gates, the authors show they can construct "blockchain circuits" that achieve any mathematically possible tradeoff between the number of safe underlay chains ($s$) and live underlay chains ($l$) required for the overlay to function.

Key Insights

  • Decoupling Safety and Liveness: By separating these two properties, the authors show you can build an overlay that is extremely resilient to safety attacks (requiring only one honest underlay) even if it has stricter liveness requirements, or vice versa.
  • Accountable Safety: If an overlay's safety depends strictly on the safety of the underlays, any safety violation on the overlay can be traced back to specific "Byzantine" validators on the underlay chains, enabling forensic accountability.
  • Optimality: The paper doesn't just provide a construction; it provides matching impossibility results, proving that the security boundaries identified are the best possible under the laws of distributed computing.

Key Results

The authors identify the exact "achievable region" for $(k, s, l)$ tuples, where $k$ is the number of underlay chains. Under partial synchrony, an overlay is achievable if $s \ge 2(k - l) + 1$. This approach provides strictly stronger security guarantees than previous models. For example, it can achieve a "2/3-safe, 2/3-live" overlay that remains secure even if different sets of chains lose safety or liveness, whereas previous models required the same 2/3 of chains to be perfectly healthy.

The achievable region for safety and liveness tradeoffs in blockchain circuits.

Limitations and Future Work

While theoretically sound, recursive compositions can lead to "exponentially many sub-circuits," which might introduce significant latency and communication overhead in practice. Furthermore, the current serial composition requires underlay chains to be "certificate-generating" (e.g., Tendermint). Future work involves extending native support for "longest-chain" protocols like Bitcoin and optimizing the engineering of high-performance circuit-based bridges using light clients.

Summary updated

BibTeX
@inproceedings{tas2024circuit,
  author = {Ertem Nusret Tas and David Tse and Yifei Wang},
  title = {{A Circuit Approach to Constructing Blockchains on Blockchains}},
  booktitle = {AFT},
  year = {2024},
  doi = {10.4230/lipics.aft.2024.8},
}
Figure