Alex NorthA blockchain light client is a node which does not store the chain’s state or messages, only the block headers. A light client queries other nodes for specific transactions or state when needed, and can validate these against the commitments contained in block headers. A light client requires far less storage and compute resources than a full node, but can still interact with peers in meaningful ways.
A light client validates header-only information on a chain, such as checking that a block’s parent hash is correctly computed from the parent headers, and checking the producer’s signature. But without the blockchain state and messages, a light client cannot validate the state root commitment proposed by a new block. Instead, it relies on the producers of subsequent blocks to validate the claimed state transition when they propose new blocks that build on older ones. A new block built on an older one functions a bit like a vote in favour of that base block being correctly computed.
But there’s a catch for proof-of-stake blockchains, or chains like Filecoin where the proof of work is not absolute and self-evident, but relative to other nodes. Without state, a light client doesn’t know who has the right to produce the next block or cast a vote.
Recursive validation of power
In order to trust a block at epoch N+1 as a validation of its parents at epoch N, a light client needs to verify that the producer at N+1 has the requisite stake (or, in Filecoin, power). However, we can’t use the power table committed by the state after epoch N as the basis for checking validity of a block at N+1 because we’re trying to use the block at N+1 to validate that the state after epoch N was correctly computed in the first place. If we did use the state at epoch N then a malicious block producer could wait until they legitimately win an election, then produce a block with a power table (invalid) that gives them all the power, and then reliably produce blocks at N+1, N+2 etc that appear to validate this state transition. They wouldn’t fool a fully validating node, but could fool any light client. A light client, if it managed to observe both chains, would have no basis to distinguish which side of the fork is valid.
Happily, Filecoin already incorporates the trick we need here as part of its standard validation rules. The state from which the power table is drawn to validate epoch N is drawn from a lookback at epoch N-900 (Filecoin sets a soft finality window of 900 epochs, or 7.5 hours). So a block producer which fakes a state transition cannot generate subsequent blocks as votes unless they legitimately win the block election many, many times.
Supporting light clients
In order for Filecoin to support light clients, those clients need easy access to a commitment to the power table. Here’s a sketch of modifications to Filecoin that could support that.
- Add a new power table commitment to the block header. The power table commitment is the root of a simple Merkle tree over a vector of tuples
(producer ID, worker address, power, eligibility), ordered by miner ID. The first entry in this vector is(0, 0x0, total-power, false)(or alternatively add the total power to the block header directly). These values are drawn from (duplicated) from the Filecoin chain state. The eligibility value is a boolean encapsulating the prior-epoch eligibility checks that form part of block validation (the producer is not in fee debt or a consensus-fault window, or other such checks as they arise in the future). A block producer must compute this commitment and its correctness forms part of full block validation rules. - Add a new proof of power to the block header. This comprises
- for the power table commitment at epoch N-900, a merkle inclusion proof of a tuple with a producer ID corresponding to the header’s producer ID, and worker address corresponding to the header’s signer, and the producer’s power at that lookback
- for the power table commitment at epoch N-1, a merkle inclusion proof of a tuple with the same producer ID, any non-zero power, and
eligibility=true.
These modifications support a light client block verification algorithm. In addition to simple header-only validation rules (right epoch, parent hashes etc), a light client verifies the producer’s right to produce the block by:
- Verifying the DRAND beacons (which is independent of state)
- Verifying the proof of power against the power table commitment at the lookback epoch
- Verifying proof of eligibility against the power table commitment at the immediately prior epoch
- Verifying the election ticket is validly constructed from the beacon and worker address
- Verify the election ticket gives a win count ≥1, given the producer’s share of total power
Filecoin’s existing soft finality is taken to be sufficient protection against long range attacks. The lookback value is outside the finality window.
Utility for cross-chain interoperability
The above computations seem cheap enough to perform in a “normal” light client, running on a mobile device or similar. Are they cheap enough to perform in a smart contract on another chain? Maybe.
Filecoin produces many blocks per epoch, and the epochs tick by quickly. Running this computation for the whole chain may be expensive and unnecessary. A couple of ideas to reduce costs further:
- Some kind of snapshot scheme that supports skipping over large gaps in the chain of block headers. Perhaps a client could validate only every 900 epochs? This is made very difficult by the prior-epoch eligibility checks.
- Validating a batch of blocks (like a tipset) or epochs (many tipsets) in one go with a SNARK.
There are other approaches to cross-chain messaging too, such as those based on snapshot chains or state proofs. I’ll write these up separately. They are often less useful for general light client usage due to long delays.
