Breakthroughs in Layer-2 Scaling and Interoperability#
“The bitcoin protocol can encompass the global financial transaction volume in all electronic payment systems today, without a single custodial third party holding funds.” – Joseph Poon and Thaddeus Dryja, The Bitcoin Lightning Network, 2016
Every full node verifies every transaction, so adding nodes adds copies of the work, not capacity: a blockchain processes no more than one node can. The ideas below keep the chain’s security while moving most of the work elsewhere: payment and state channels, where two parties update a balance privately and the chain only judges disputes; child chains and rollups, which post commitments or compressed data instead of executing everything; sharding, which splits the work among groups of nodes; and data-availability sampling, which lets light clients check that the data behind a block exists without downloading it. Two of these tools, hash time-locks and light clients, also move value between chains, and bridges that do without them have been the costliest failures in the field. Breakthroughs in Replicated Execution covers the hash time-locked contract itself, and Breakthroughs in Authenticated Data Structures the Merkle proofs and light clients that much of this page builds on.
Every channel output here is a blockchainkit.vm.systems.script
program, judged by verify_script();
the contracts run on World.
Exact conventions and model boundaries lists where the models depart from deployed systems.
1960 – Reed and Solomon’s Polynomial Codes#
A communication line that loses or corrupts symbols needs redundancy, and
Reed and Solomon found a code that tolerates as much damage as any code of
its length and rate can. They read k symbols of a finite field as the
coefficients of a polynomial of degree below k and transmitted its
values at n points. Two different polynomials of degree below k
agree on at most k - 1 points, since their difference has at most
k - 1 roots. So any k received values determine the polynomial, and
two codewords differ in at least \(n - k + 1\) places. A decoder can
therefore fill in up to \(n - k\) lost symbols, and correct a wrong
symbol at the price of two lost ones, as long as
Decoding errors efficiently took longer; Berlekamp and Welch (1986) reduced
it to linear algebra, by solving for an error-locator polynomial. With
\(n = 2k\), any half of the n values rebuilds the data, which is
what data-availability sampling relies on.
Implementation: blockchainkit.channels.systems.reed_solomon.rs_encode(),
rs_recover() and
rs_decode() (Berlekamp-Welch),
over the integers modulo 65,537 by default. Codes are systematic: the data
are the polynomial’s values at 0, ..., k - 1, as in data-availability
schemes, rather than its coefficients, as in Reed and Solomon’s paper.
References: I. S. Reed and G. Solomon, Polynomial codes over certain finite fields, Journal of the Society for Industrial and Applied Mathematics 8(2), 300–304 (1960). DOI; L. R. Welch and E. R. Berlekamp, Error correction for algebraic block codes, US Patent 4,633,470 (1986).
Reed-Solomon codes: recovering lost and corrupted symbols (1960)
2013 – Spilman and Hearn’s One-Way Micropayment Channels#
Paying a few satoshis per second for a service, one transaction per
payment, costs more in fees than it pays. Jeremy Spilman described a
channel that needs two transactions for any number of payments. The payer
locks the channel’s capacity in an output that only both parties’ signatures
can spend. Before doing so, the payer gets the payee’s signature on a
refund that returns everything after a lock time, so a payee who vanishes
cannot hold the coins hostage. Each payment is a new, unpublished
transaction from that output, signed by the payer and paying the payee a
little more than the last. The payee could countersign and publish any of
them, but the last pays it the most, so it publishes only that one. Mike
Hearn implemented the scheme in bitcoinj the same year. For m payments,
only funding and closing reach the chain,
and the payee must close before the lock time, or the payer can take everything back with the refund.
Implementation: blockchainkit.channels.systems.micropayment.SpilmanChannel,
whose funding output is a 2-of-2 Script checked by
verify_script(). The interpreter has
no OP_CHECKMULTISIG, so the two signatures are checked one after the
other. Before segregated witness, the refund signed a funding transaction
whose identifier could be malleated; the model has no malleability.
References: J. Spilman, Anti DoS for tx replacement, bitcoin-development mailing list (April 2013); M. Hearn, micropayment channels in bitcoinj (2013), and Contract, Bitcoin Wiki.
Spilman and Hearn’s one-way micropayment channels (2013)
2013 – Tier Nolan’s Atomic Cross-Chain Swaps#
Two people who trade coins on different chains each want the other to pay
first, and neither chain can see the other to enforce the deal. Tier
Nolan’s protocol ties the two payments to one secret s, known only to
Alice. Alice locks her coins on chain A to Bob behind h = SHA256(s),
refundable to her at \(T_A\); Bob, seeing this, locks his on chain B to
Alice behind the same h, refundable to him at \(T_B\). Alice
claims on B by revealing s, and Bob reads it from chain B and claims on
A. Either both payments happen or neither does. Alice must claim on B
before \(T_B\), or Bob takes his coins back, so s is public by
\(T_B\) at the latest; Bob then needs time to use it on A before Alice
can refund there. Nobody can lose if
With the timeouts reversed, \(T_A < T_B\), Alice could wait until \(T_A\), refund on A, and still claim on B.
Implementation: blockchainkit.channels.systems.swaps.AtomicSwap,
two htlc_locking() outputs whose
claims and refunds run through Script. Both chains share one block height,
and neither has fees or confirmation delays; the free option the protocol
gives Alice is left to the exercise.
References: T. Nolan, Alt chains and atomic transfers, Bitcointalk forum (May 2013).
2015 – Decker and Wattenhofer’s Duplex Micropayment Channels#
A Spilman channel pays one way and is spent once. Decker and Wattenhofer
combined two, one per direction, and reset the pair whenever one side ran
dry, re-funding both from the current balances. Each reset leaves older
pairs signed and publishable, and nothing punishes a party who publishes
one, so the protocol must make sure the newest pair always reaches the
chain first. An invalidation tree of time-locked transactions sees to
that. Each reset replaces a node of the tree with a copy whose lock time
is \(\delta\) lower. Where an old and a new branch part, both spend the
same parent output, and the new branch becomes valid first, so it spends
that output and the old branch can never confirm. Lock times only go down,
so a tree of depth d with s lock-time values per level allows
\(s^d\) resets before it runs out. At worst every level still has its
highest lock time, and closing waits for up to
The paper also built a payment network from these channels, routing over several hops with hash time-locks.
Implementation: blockchainkit.channels.systems.duplex.DuplexChannel,
invalidation_locktimes() and
first_confirmed(). The channel
is a state machine without transactions or signatures. Lock times are
relative, counted from each parent’s confirmation, so closing takes their
sum; with absolute lock times a channel also has a fixed lifetime.
References: C. Decker and R. Wattenhofer, A fast and scalable payment network with Bitcoin duplex micropayment channels, Stabilization, Safety, and Security of Distributed Systems (SSS 2015), LNCS 9212, 3–18 (2015). DOI.
Decker and Wattenhofer’s duplex micropayment channels (2015)
2016 – Poon and Dryja’s Lightning Network: Revocation and Penalties#
An invalidation tree runs out of lock times, so a duplex channel allows only so many resets. Lightning stops old states from being published by deterrence instead: publishing one costs the cheater everything, and since no lock time is used up, a channel can be updated without limit. Each party holds its own commitment transaction, signed by the other. It pays the counterparty at once, but its holder only after a delay, and during that delay the holder’s output can also be taken with a revocation key. To move to a new state, each party hands over the secret behind its previous commitment’s revocation key. From then on, a party that publishes that old commitment loses its whole balance to a counterparty who is watching, because the counterparty can sweep it with the revocation key before the delay ends. The key must be unusable until handed over, so it is split: it combines the holder’s per-commitment point \(S_n = s_n G\) with the counterparty’s base point \(B = b G\),
The counterparty knows only b and the holder only \(s_n\), so
neither can sign with \(r_n\) until the holder reveals \(s_n\). The
paper also linked channels into a network with hash time-locked contracts.
Implementation: blockchainkit.channels.systems.lightning.LightningChannel,
whose commitments, sweeps and penalties are Script spends of a 2-of-2
funding output and a revocable output. Per-commitment secrets are a hash
chain used backwards, as in Lightning’s shachain, so the counterparty
stores one secret. Script here lacks OP_CHECKSEQUENCEVERIFY: the delay
is checked by OP_CHECKLOCKTIMEVERIFY against the commitment’s age, and
the revocation key adds the points without the hashed tweaks that stop a
party from cancelling the other’s.
References: J. Poon and T. Dryja, The Bitcoin Lightning Network: Scalable off-chain instant payments, white paper (January 2016).
Poon and Dryja’s Lightning Network: revocation and penalties (2016)
2016 – BTC Relay: a Light-Client Bridge in a Smart Contract#
A contract on one chain cannot see another, so it cannot tell whether a
payment there happened. BTC Relay, launched on Ethereum in 2016, ran a
Bitcoin light client inside a contract. Relayers submitted Bitcoin block
headers; the contract checked that each linked to a stored header and met
its proof-of-work target, and followed the chain with the most cumulative
work. A header whose hash needs difficulty leading zero bits takes
\(2^{\text{difficulty}}\) hashes on average, so a chain’s work is
A contract could then accept a Merkle proof that a Bitcoin transaction was in a block of that chain under enough confirmations, enabling trustless ether-for-bitcoin swaps. Faking such a proof means building a heavier chain of headers than honest Bitcoin miners, so the relay is safe as long as no attacker can out-mine them: the light-client assumption of Nakamoto’s simplified payment verification.
Implementation: blockchainkit.channels.systems.relay.BTCRelay
on World, storing
BlockHeader objects mined
by mine_header() and verifying
MerkleTree proofs. The
teaching chain has no difficulty retargeting, so the relay demands a fixed
minimum difficulty instead, and relayers earn no fees.
References: J. Chow, BTC Relay, ConsenSys, github.com/ethereum/btcrelay (2016).
BTC Relay: a Bitcoin light client in an Ethereum contract (2016)
2017 – Sprites and General State Channels#
On a chain with contracts, a channel can be judged by a contract instead of enforced by pre-signed transactions. An adjudicator contract holds the deposits; the parties sign successive numbered versions of any state, balances or the position of a game; and either can submit the latest. The other has a dispute period to answer with a newer version, and the contract settles on the highest, so publishing an old version gains nothing.
Sprites also shortened multi-hop payments. In Lightning, a payment over
n hops locks amount \(a_i\) on hop i until an expiry
\(\Delta\) later than the next hop’s: each hop learns the preimage only
when the next one claims, and needs time \(\Delta\) to claim in turn.
Expiries thus grow towards the sender. Sprites added a global preimage
manager, a contract where anyone can publish the preimage. Every hop
settles by asking it whether the preimage was published by one common
deadline, so no hop waits for the next, and collateral is locked for the
same time on every hop,
Implementation: blockchainkit.channels.systems.state_channels.StateChannel
and PreimageManager,
contracts on World, with
htlc_expiries(),
sprites_expiries() and
collateral_time(). The
adjudicator decides disputes by version number alone; Sprites and later
designs also let a party advance an application’s state on chain when the
other stops responding.
References: A. Miller, I. Bentov, S. Bakshi, R. Kumaresan and P. McCorry, Sprites and state channels: payment networks that go faster than Lightning, Financial Cryptography and Data Security (2019); arXiv:1702.05812 (2017).
Sprites and general state channels (Miller et al., 2017)
2017 – Plasma: Child Chains with Exit Games#
Channels serve a fixed set of parties; Poon and Buterin’s Plasma moved whole chains off the main one. An operator runs a child chain and posts only its block roots to a root-chain contract, which cannot check the transactions behind them. Coins stay safe because their owners can always exit: prove ownership on the root chain and wait out a challenge period, in which anyone may prove the exit invalid. In Plasma Cash (2018) every coin has a slot in each block’s sparse Merkle tree, so its history is a chain of transfers, each proved by a Merkle branch. An exit names the coin’s last transfer, to the exiter, and the one before it; a challenger cancels it by showing
The first proves the exiter has already given the coin away; the second, that the coin left the previous owner before the exiter’s transfer, so that transfer was a double spend. Exits only work while users can see the blocks. An operator who withholds them can hide invalid transactions, so every user must exit, and the root chain may not have room for them all: the data-availability problem that rollups later solved by posting the data.
Implementation: blockchainkit.channels.systems.plasma.PlasmaChain
with sign_transfer(), on
SparseMerkleTree.
The root-chain contract is a Python object rather than a contract on
World, and Plasma Cash’s
invalid-history challenge and bonds are omitted.
References: J. Poon and V. Buterin, Plasma: scalable autonomous smart contracts, white paper (August 2017); V. Buterin, Plasma Cash: Plasma with much less per-user data checking, ethresear.ch (March 2018).
Plasma: child chains secured by exit games (Poon and Buterin, 2017)
2018 – eltoo: Channel Updates without Penalties#
Lightning’s penalty punishes an honest mistake, such as publishing a stale
backup, as hard as theft. eltoo replaces punishment with replacement. Each
state is an update transaction, which may spend the funding output or any
earlier update, and a settlement, which pays out after a delay. If a
party publishes an old update, the other answers within the delay with a
newer one that spends it, so only the last update settles and nobody needs
to be punished. This needs two properties. First, the latest update must be
able to spend whichever earlier update appears, which a normal signature
cannot do, since it commits to the exact output spent. Updates are
therefore signed with SIGHASH_NOINPUT, which omits the spent output.
Second, an old update must not be able to spend a newer one, so each update
output requires the spending transaction’s lock time to exceed its own state
number, and update m carries lock time m:
Implementation: blockchainkit.channels.systems.eltoo.EltooChannel,
whose update outputs are Script with both branches checked by
verify_script(). A signature over a
message without the spent output stands in for SIGHASH_NOINPUT
(BIP 118, not yet active on Bitcoin), and the settlement delay is checked
with OP_CHECKLOCKTIMEVERIFY against the update’s age.
References: C. Decker, R. Russell and O. Osuntokun, eltoo: a simple layer2 protocol for Bitcoin, white paper (2018).
eltoo: channel updates without penalties (Decker, Russell and Osuntokun, 2018)
2018 – OmniLedger and Sharding#
Splitting validators into shards multiplies throughput, but each shard is
as weak as its own committee. OmniLedger reshuffles validators every epoch
using unbiasable randomness (RandHound), so an adversary with a fraction of
all validators cannot gather them in one shard. A committee runs Byzantine
agreement, which fails once a third or more of its members are malicious.
A committee of m drawn at random from N validators, M of them
malicious, reaches that point with the hypergeometric probability
which falls exponentially with m while \(M/N\) stays below a third.
A payment whose inputs live on several shards must not succeed on some and
fail on others, so OmniLedger uses Atomix: every input shard locks its
input, then the output shard commits the payment if all accepted, or every
input is unlocked.
Implementation: blockchainkit.channels.systems.sharding.shard_failure_probability(),
assign_shards(),
compromised_epochs() and
atomix_transfer(). A seeded
shuffle stands in for RandHound, and shards’ acceptances are taken on
trust rather than as signed proofs from each committee.
References: E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta and B. Ford, OmniLedger: a secure, scale-out, decentralized ledger via sharding, IEEE Symposium on Security and Privacy (2018), 583–598. DOI.
OmniLedger and sharding (Kokoris-Kogias et al., 2018)
2018 – zk-Rollups: Validity Proofs for Batched Transactions#
Plasma kept data off chain and paid for it with exit games. A rollup posts
its transactions, compressed, to the chain, so anyone can rebuild its
state, and Barry Whitehat’s roll_up and Buterin’s proposal of 2018 added
a succinct proof that the posted state root follows from them. The contract
verifies the proof at a fixed cost \(G_{\text{verify}}\) and never
re-executes, so in a batch of n transactions of b bytes each, at 16
gas per byte of calldata, the gas per transaction tends to the cost of its
data:
A sound proof system admits no proof of a false state root, so a batch is final as soon as it is accepted, with no challenge period.
Implementation: blockchainkit.channels.systems.rollups.ZKRollup,
with batch_gas() and
state_root(). There is no
proof system: a ValidityProof
states what it proves, and verification re-executes the batch, standing in
for a SNARK verifier. Invalid transactions are skipped, as rollups do.
References: Barry Whitehat, roll_up, github.com/barryWhiteHat/roll_up (2018); V. Buterin, On-chain scaling to potentially ~500 tx/sec through mass tx validation, ethresear.ch (September 2018).
zk-rollups: validity proofs for batched transactions (2018)
2018 – Al-Bassam, Sonnino and Buterin: Fraud Proofs and Data-Availability Sampling#
Fraud proofs let a light client reject an invalid block once an honest full
node objects, but only if the block’s data is available: a producer can
publish a header and withhold the data, and then nobody can prove fraud.
Al-Bassam, Sonnino and Buterin extend the data with a Reed-Solomon code and
commit to the shares, so that any half rebuilds the block. Withholding a
few shares then hides nothing: to keep any data out of reach, the producer
must withhold a fraction \(f > 1/2\) of the shares. Each share a client
samples at random is then missing with probability f, so a client that
samples s of them notices with probability
A producer could instead publish shares that are not a valid codeword, so that different halves rebuild different blocks; any node that rebuilds the data catches this with an encoding fraud proof. Once enough clients’ samples are published, together they rebuild the block.
Implementation: blockchainkit.channels.systems.data_availability.extend(),
simulate_sampling(),
encoding_fraud_proof()
and verify_encoding_fraud_proof(),
on reed_solomon and
MerkleTree. The code is
one-dimensional, so a fraud proof holds k + 1 shares rather than the
paper’s single row of a two-dimensional square.
References: M. Al-Bassam, A. Sonnino and V. Buterin, Fraud and data availability proofs: maximising light client security and scaling blockchains with dishonest majorities, arXiv:1809.09044 (2018).
Fraud proofs and data-availability sampling (Al-Bassam, Sonnino and Buterin, 2018)
2019 – Optimistic Rollups and Fraud-Proof Challenge Windows#
Validity proofs were expensive to generate for general computation. An
optimistic rollup, as Adler and Quintyne-Collins proposed in 2019, posts
batches and state roots without proofs, and a root becomes final once a
challenge window has passed with no fraud proven. Re-executing a whole
batch on chain to settle a dispute would cost what the rollup saves, so the
dispute is narrowed by bisection, as in Arbitrum. Asserter and challenger
agree on the state before the batch and disagree on the state after it.
The asserter posts the state root at the midpoint; the challenger says
which half it disputes, and that half is split in turn, until they disagree
about one transaction, which the chain re-executes. A batch of n
transactions takes
Any one honest watcher can win the game, so one suffices; the price is that withdrawals wait for the window.
Implementation: blockchainkit.channels.systems.rollups.OptimisticRollup
and bisect(). The bisection
game runs in one call rather than as alternating transactions, and the
challenger’s own bond and the censorship of challenges are not modelled.
References: J. Adler and M. Quintyne-Collins, Building scalable decentralized payment systems, arXiv:1904.06441 (2019); H. Kalodner, S. Goldfeder, X. Chen, S. M. Weinberg and E. W. Felten, Arbitrum: scalable, private smart contracts, 27th USENIX Security Symposium (2018).
Optimistic rollups and fraud-proof challenge windows (2019)
2019 – Watchtowers and PISA: Guarding Offline Channel Parties#
A Lightning party is safe only while it watches the chain: a revoked
commitment must be answered within its delay. A watchtower watches for
it. After each update the party gives the tower half the revoked
commitment’s transaction identifier as a hint, and a presigned penalty
encrypted under the whole identifier (Dryja, 2016). The tower watches for
a transaction whose identifier starts with the hint; until one appears it
cannot decrypt the penalty and learns nothing about the channel, and then
it can publish only a penalty that pays the party. PISA made towers
accountable: a tower signs a receipt for each appointment and locks a
deposit, which the party claims if the revoked commitment named in the
receipt was published and its funds were taken by the cheater. A party
that checks the chain every T blocks, with a delay of d blocks,
misses a cheat published at a random time with probability
\(1 - d/T\) when \(d < T\), and loses only if the tower also fails:
Implementation: blockchainkit.channels.systems.watchtowers.Watchtower,
make_appointment(),
verify_receipt() and
tower_liable(), guarding a
LightningChannel. The
blob is encrypted with a SHA-256 keystream rather than an authenticated
cipher, and PISA’s recourse is a function rather than its arbitration
contract for general state channels.
References: P. McCorry, S. Bakshi, I. Bentov, S. Meiklejohn and A. Miller, Pisa: arbitration outsourcing for state channels, ACM Conference on Advances in Financial Technologies (AFT 2019). DOI; T. Dryja, Unlinkable outsourced channel monitoring, Scaling Bitcoin, Milan (2016).
Watchtowers and PISA: guarding offline channel parties (McCorry et al., 2019)
2019 – Balance Probing and Payment Privacy in Lightning#
Lightning announces each channel’s capacity but hides how it is split, and so how much each side has paid. Herrera-Joancomartí and co-authors showed that anyone with a channel can learn the split. The prober routes a payment through the target channel with a payment hash nobody can claim: if the channel cannot forward the amount, the error comes from that hop; if it can, the payment fails at the recipient with a different error. Either way no money moves, and each probe answers one question: is the balance at least the amount? Halving the range of possible balances each time, a binary search finds the balance of a channel of capacity \(C\), one of \(C + 1\) values, exactly in
Repeated over time, probing reveals payments themselves.
Implementation: blockchainkit.channels.systems.probing.probe_balance()
over ChannelNetwork, which
routes hash time-locked payments over a
Graph, with fees and
expiries computed hop by hop from the recipient. Errors return in the
clear; the deployed protocol wraps them in onion encryption, which hides
nothing from the sender, who is the prober.
References: J. Herrera-Joancomartí, G. Navarro-Arribas, A. Ranchal-Pedrosa, C. Pérez-Solà and J. Garcia-Alfaro, On the difficulty of hiding the balance of Lightning Network channels, ACM Asia Conference on Computer and Communications Security (AsiaCCS 2019). DOI.
Balance probing and payment privacy in Lightning (Herrera-Joancomartí et al., 2019)
2022 – Bridge Failures: the Ronin and Wormhole Exploits#
Most bridges do not verify the other chain at all: a committee signs
withdrawals, and the bridge is as safe as its keys and the code that checks
their signatures. In February 2022, Wormhole’s Solana program accepted an
account supplied by the caller as evidence that the guardians’ signatures
had been checked; an attacker supplied a forged one, skipped the check, and
minted 120,000 wrapped ether. In March, Ronin, which released funds on 5 of
9 validator signatures, lost 173,600 ether and 25.5 million USDC. One
company ran four validators and still held permission to sign for a fifth,
so breaking into that one company yielded all five signatures. For n
independent keys each compromised with probability p, a t-of-n
bridge falls with
which is tiny for small p and large t. But keys held by one party
are not independent: they fall together, and Ronin’s five signatures took
a single breach.
Implementation: blockchainkit.channels.systems.bridges.ValidatorBridge,
GuardianVerifier,
WormholeBridge and
ForgedVerifier, contracts on
World. Solana’s accounts
become a caller-supplied verifier contract, and minting and redeeming
wrapped ether happen in one contract instead of on two chains.
References: Ronin Network, Community alert: Ronin validators compromised (29 March 2022); Wormhole, Wormhole incident report (February 2022); S.-S. Lee, A. Murashkin, M. Derka and J. Gorzny, SoK: not quite water under the bridge: review of cross-chain bridge hacks, arXiv:2210.16209 (2022).
Bridge failures: the Ronin and Wormhole exploits (2022)