Blockchain Research Newsletter #3: NiPoPow and FlyClient

By Mikerah and John Adler

In this edition of the Blockchain Research Newsletter, we summarize two proposals for developing trust-minimized light-clients for proof-of-work blockchains: Non-Interactive Proofs of Proof of Work (NIPoPoWs) and FlyClient. NIPoPoWs were introduced in 2017 by IOHK researchers, Kiayias et al. They haven’t been widely deployed in practice yet but are planned to be leveraged with the Cardano project. FlyClient, first introduced by Benedikt Bünz at Scaling Bitcoin 2018, has been proposed in a ZIP for the Zcash blockchain and is currently also being considered for the Ethereum blockchain.

Motivation

Blockchains require that all nodes in the network validate any state changes that occur. In other words, all nodes have to check the validity of every transaction and thus every block that gets sent across the network. Additionally, nodes have to download the entire blockchain in order to ensure its validity. For fully validating nodes (including miners), this isn’t a problem. However, smaller devices like mobile phones cannot handle downloading and processing the entire history of the blockchain. This is where light-clients come in. Light clients enables less powerful devices to access the state of the blockchain that is relevant to them. They don’t need to validate the entire chain but instead validate only block headers. Applications such as wallets can use light clients in order to easily access blockchain data and interact with the blockchain.

Historical light client designs relied on the honesty of miners and having to store every block header. This can be a bottleneck for light clients, as storage is now linear in the number of block headers — -especially problematic is low blocktimes are used. Practically, this means that a light client might end up storing gigabytes of data which is still a lot of for low-power devices such as cell phones.

Non-Interactive Proofs of Proof of Work

Non-Interactive Proofs of Proof of Work (NIPoPoWs) is a light client proposal, originally published in 2017 by Kiayias et al. It builds upon Kiayias’s previous work on Proofs of Proof of Work (PoPoWs) by making this construction non-interactive.

Model

In the model use to present NIPoPoWs, we consider three actors: light clients, full nodes, and miners. In cryptography speak, the light clients are verifiers and the full nodes are provers. Full nodes need to prove the validity of blocks and block headers to light clients that verify these proofs. We assume a synchronous network model. Moreover, we model the proof of work process as a random oracle. In plain English, miners query a fair oracle with “may I produce the next block,” with the oracle randomly assigning a block producer. The model assumes that the difficulty is constant, i.e., the difficulty stays the same throughout the lifetime of the network.

Overview

The underlying data structure that support NIPoPoWs is the interlink. It is a skip-list that allows for a sparse sampling of a sequence of block headers. Specifically, links to superblocks (i.e., blocks that satisfy a higher difficulty target that necessary) are contained within the interlink, which is stored in block headers. This can be implemented via a fork, including a velvet fork; details of this fork procedure can be found in the paper.

Given a difficulty target of d leading zeroes, a superblock hashes to more than d leading zeroes. In expectations, half of all mined blocks will have d+1 leading zeros, a quarter will have d+2 leading zeros, and so on. This information is stored in the interlink as levels, as shown in the figure below. Level 0 of the interlink contains links to blocks that at least meet difficulty d, level 1 contains links to blocks that at least meet difficulty d+1, and so on.

A NIPoPoW can be constructed as follows, shown in the figure below:

1. Start at the highest level with at least m blocks. In this example, level 2. We don’t want levels with fewer than m blocks to prevent freak outliers from influencing the proof.
2. From this level, choose the last m blocks, appending them to the proof.
3. Go down one level, then choose all blocks ahead of the earliest block chosen previously, appending them to the proof.
4. Repeat step 3 until there are no more levels.

To non-interactively verify proofs: given multiple proofs, select the one with the highest score (we assume that at least one proof is honest). Scores are calculated as follows:

1. For each level, calculate the number of blocks meeting at least the difficulty target of the level.
2. Return the maximum of the above.

Note that the parameter m must be carefully chosen. Longer proofs are more secure and resilient to a larger adversarial hashrate, but are longer.

FlyClient

FlyClient is a light client proposal for PoW blockchains such as Bitcoin and Ethereum proposed by Bünz et al. in 2019. It makes use of a variant of Merkle trees called Merkle Mountain Ranges (MMRs). It only needs to store a logarithmic number of block headers and provides strong mechanisms for ensuring the validity of these block headers.

Background: Merkle Mountain Ranges (MMRs)

Before we dive into the FlyClient protocol, let’s go over the MMR data structure. MMRs are an extension of Merkle trees that allow for each append operations. They were first introduced for Bitcoin in 2016 by Bitcoin Core developer Peter Todd. However, earlier uses of MMR have been proposed by Cosby and Wallace in the context of tamper-eviden logging.

Merkle trees are ubiquitous in blockchain systems. They are a form of authenticated data structure with logarithmic proofs of inclusion. However, they are not without shortcomings, such as when we want to insert an extra leaf into the tree. A previously-balanced Merkle tree would become unbalanced, resulting in larger proof sizes. Rebalancing the tree to keep proof sizes with logarithmic worst-case performance results in significant computational overhead, as many hashes must be re-computed.

In order to get over the shortcomings of plain Merkle trees, Merkle Mountain Ranges (MMRs) were devised. They enable us to append new data to a Merkle tree without having to regenerate it constantly, and keep the resulting tree somewhat balanced.

Visualization of Merkle Mountain Range append operations.

The update process for MMRs work as follows:

1. Line up all the leaf nodes.
2. Starting from the left, create a Merkle tree using as many nodes as possible (this will be a power of 2).
3. Using the remaining nodes, create as many maximal Merkle trees as possible with the remaining leaves (step 2).
4. Now, we have several Merkle trees. Notice that in the picture above, we see that these Merkle trees have a mountain range-like structure with multiple peaks.
5. Starting from the rightmost tree, hash the roots of 2 consecutive trees together.
6. Repeat step 5 as in the usual Merkle tree construction.

Overview

The FlyClient protocol uses three main building blocks: Merkle Mountain Ranges, probabilistic sampling, and the Fiat-Shamir heuristic. In the protocol, a light client has to decide between two chains provided by two full nodes, one of which provides an honest chain. In cryptography language, the light client is known as the verifier and the two full nodes are known as provers. The goal is to have the verifier correctly guess which prover is giving the client the honest chain.

The FlyClient protocol requires changes that can be added through a soft fork or a hard fork. Block headers need to include a Merkle root to a MMR that contains commitments to all the previous block headers of the chain.

The protocol works as follows:

1. Both full nodes send the latest block header to the light client.
2. Iterate j times, where j is bounded logarithmically by the number of block headers:
3. The light client queries k random block headers from each full node, where k is determined by a fraction of the honest chain’s computing power. In order to sample blocks, we observe the following: A malicious full node can only mine a subset of the blocks due to limited computing power. Thus, there will be a fork point at which an honest node’s chain and a malicious node’s chain will differ.
4. For every block header, a full node provides a MMR proof that this block is included in its chain at a particular position
5. The light client checks the MMR proof and proof of work done for each block header. If any of these checks are incorrect, the light client rejects the full node that provided the invalid block header.
6. If the full node has not been rejected, then the light client accepts that full node’s chain as correct.

In practice, step 2 is in fact a hash of the block header at each iteration. This is an instantiation of the Fiat-Shamir heuristic. So, we now have a non-interactive protocol instead of an interactive one.

Comparison

Both proposals aim to tackle the light client problem using different security assumptions and cryptographic primitives. NIPoPoW assumes a constant difficulty, synchronous network. On the other hand, FlyClient uses more realistic assumptions on network conditions, i.e., a variable difficulty, partially synchronous network. Both are designed to have a light client only store a logarithmic number of block headers instead of a linear number of block headers. In terms of efficiency, both protocols offer reasonably efficient proof sizes, with FlyClient providing shorter proof sizes than NIPoPoW. The authors of FlyClient show that FlyClient can provide up to a 40% improvement over NIPoPoW in this aspect.

One major difference is NIPoPoW’s reliance on superblocks. This means that NIPoPoWs cannot be applied to PoS blockchains or more generally, Sybil resistance mechanisms that don’t have an equivalent notion of work. Moreover, the reliance on the rarity of superblocks makes NIPoPoW-based light clients susceptible to bribing attacks. An attacker can pay miners to withhold their blocks in favor of broadcasting superblocks. FlyClient on the other hand, only uses randomness after a block has been mined, as light client randomly samples already-mined blocks. Thus, NIPoPoW is only efficient when there are no adversaries, but remains secure in the presence on an adversarial minority.

Conclusion

In this edition, we have presented two different light client proposals, FlyClient and Non-Interactive Proofs of Proof of Work. Both provide an efficient means to enable low-power devices to send and verify transactions to blockchains, and have applications in cross-chain communications protocols. If you want to read both papers in-depth, you can the read the FlyClient paper here and NIPoPoW paper here.

If you like what you have read, you can subscribe to the Blockchain Research Newsletter.