Introduction to super-light clients: FlyClient
A properly designed light client protocol will prevent adversaries from including invalid (fake) blocks that could be used to deceive a light client into following an alternate chain of the same length (or difficulty) as that of the honest chain.
SPV proofs accomplish this by requiring verifiers to check all headers, but super-light client designs have been emerging. They allow for verification of a blockchain’s proof of work by checking only a fraction of the chain’s block headers.
This “sub-linear” verification of the work expended to produce a blockchain significantly compresses light client proof sizes, and don’t require trust in a 3rd party.
This article will introduce the second of two super-light client designs: FlyClient. For those that prefer video, check out this great talk by Benedikt Bünz.
Introducing FlyClient
FlyClient was introduced in a 2019 paper by Bünz, Kiffer, Luu, and Zamani. The FlyClient authors observe that in previous super-light client constructions, verifiers only download a small number of total blocks, which are not necessarily chained together. This design allows a malicious prover to deceive a verifier by presenting a mix of invalid blocks and honest blocks.
FlyClient closes this attack vector by requiring that miners commit to the entire accumulated blockchain history at each block. With this commitment, a prover can only provide valid blocks at expected positions in the chain.
A sampling of the blocks in this commitment are provided to super-light clients for verification. Full nodes can calculate a single proof (at a particular block height) and share it with many light clients. These light clients can in turn share the proof with other light clients, all of which can independently verify the integrity of the proof they receive.
FlyClient operation
FlyClient captures these block history commitments in an append-only data structure known as a Merkle Mountain Range or MMR. For more information about MMRs, check out these links: 1, 2, 3, 4.
“At every block height i, the prover appends the hash of the previous block, Bi−1, to the most recent MMR and records the new MMR root, Mi, in the header of Bi. As a result, each MMR root stored at every block height can be seen as a commitment to the entire blockchain”
FlyClient also prescribes that accumulated difficulty and accumulated time are included in each commitment to the MMR, meaning that each block header commits to 1) the sequence of all previous blocks and 2) total accumulated difficulty and time values.
By committing to difficulty and time data, difficulty transitions can be proven to have been executed correctly and verifiers can ensure that no difficulty raising attacks have been executed.
FlyClient proving process
Each prover begins by sending the header of the last block in its chain, which includes the latest MMR commitment (Mi). The verifier then samples a number of random blocks (logarithmic to chain length) from the prover based on a sampling distribution.
- Randomness is derived from a hash of the current block header:
“To make our probabilistic sampling protocol noninteractive, we apply the Fiat-Shamir heuristic to the protocol described so far. The randomness is generated from the hash of the head of the chain. The verifier now simply checks that the proof is correct and that the randomness was derived correctly.”
2. Sampling distribution is based on accumulated difficulty:
“we use the same sampling distribution g(x) but x now denotes the relative aggregate difficulty. For example, x = 1/2 refers to a point on the chain where half of the difficulty has been amassed, and g(1/2) is the probability that the block at that point is sampled by FlyClient.”
For every sampled block, the prover provides the corresponding block header and its Merkle path proving inclusion in the MMR root. This proves the block is located at the correct height in the chain as committed to in the MMR root. Additionally, the verifier checks that the MMR root stored in each sampled block header commits to valid subtree in the current MMR commitment (Mi).
If the proof-of-work solution or inclusion proofs for any blocks are invalid, the verifier rejects the proof. Otherwise, the provided block header is accepted as the latest block of the honest chain. Transaction inclusion is proven in the same process as an SPV proof, with a Merkle path to a transaction root and then a proof of that block’s inclusion in the current MMR commitment (Mi).
FlyClient Implementation Paths
Block Header Field
The MMR required for FlyClient has been implemented in the block header of Beam, Grin and is proposed for Zcash and Ethereum Classic.
State Commitment — Soft Fork
The FlyClient paper describes implementation through a soft fork, in which only blocks that contain a transaction committing to the MMR would be accepted.
State Commitment — Velvet Fork
In the FlyClient paper, implementation through a “velvet fork” is described for non-contentious deployment in existing blockchains. Similar to merge-mining, compliant miners would include FlyClient’s MMR data in the coinbase input and blocks that do not include this data would still be accepted.
FlyClient would treat blocks that do not include commitment data as part of the last committed block.
State Commitment — Transactions
A second non-contentious path for an existing chain is a commitment to the MMR value in contract state through transactions. This has been mentioned as a permissionless implementation of FlyClient for Ethereum Classic.
In Ethereum, the latest 256 block headers are accessible from a contract, the MMR root required by FlyClient could be built by submitting a contract transaction that reads previous block headers and adds them to the MMR. This implementation method does however require ongoing, timely processing of transactions.
Conclusion
FlyClient is a very promising design for a super-light client. It requires that miners commit to a blockchain’s history at each block and closes the attack vector present in the NIPoPoW super-light client design.
FlyClient is currently being used by Grin and Beam, planned for ZCash and under consideration for Ethereum Classic.
