Trustless Bridging

At Composable, we agree that trusted bridges operated via multisigs are not desirable long-term solutions. However, we think it is too early to draw the conclusion that trustless bridging is impossible. Theoretically, it is possible to relay the canonical true state of one network to another, if we can agree on the true states of two networks on-chain and resolve the different forks that may arise. Getting two networks to communicate in a trustless way may be a bold ambition — intra-network communications such as XCM in Polkadot or IBC in Cosmos are still being rolled out and optimized; but this is an area we need to solve to bring about a seamless cross-chain future. Without trustless bridging, we are left with silos in liquidity, information, and technical development.

Highly efficient light client protocols are crucial in enabling the decentralization and mainstream adoption of blockchain protocols. It does this by allowing environments with computation and memory resource constraints (e.g. mobile, on-chain contracts) to verify the latest blockchain state without the need to execute & store the full block data and state. Light clients instead track block headers instead of tracking the full blocks and executing transactions to arrive at the latest state. It is important to note that blocks are really just the header & transactions:

The size of the transactions in a block might vary, but headers have a fixed size, usually no more than 1kb. Fun fact: bitcoin header size is actually 80bytes, while ethereum is 508bytes.

Light client protocols consist of a combination of transaction merkle proofs, state proofs, consensus proofs and finality proofs all of which are usually included in the block headers except for finality proofs. This is because finality proofs may differ from the consensus proof and require data that is an extension of the header. Let’s look into each one of them in more detail.

This is the merkle root of all transactions that have been executed in this block. This merkle root can be seen as a kind of cryptographic compression that allows us to trustlessly verify if some data was part of the original data that was compressed by way of a merkle proof.

Such that the merkle proof required to check if some element was included in the root would be log2(n) hashes which are usually 32bytes. In the diagram above, we only need 4 hashes outlined in blue to prove or otherwise reconstruct the original root hash that K was indeed part of the original merkle tree. Where: n = 16, log2(16) = 4. This enables light clients to efficiently check which transactions were executed in a block without needing to download the full block that may potentially contain thousands of transactions and have to scan this list linearly.

The state root of a blockchain is similar to the transactions root in that it is the output of the cryptographic compression of data. However, where the transaction root is a compression of a list of transaction data, the state root can be seen as the compression of a list of keys & values.

Hence, the keys and values are the data stored on the blockchain by contracts or core blockchain subsystems like the consensus protocol storing the list of authorities and their stakes. By compressing this data into a kind of merkle root, we retain the ability to check the existence of some key, value against the root hash and a merkle proof, without needing to maintain the full blockchain state but still have the same trussless guarantees as a full node.

The consensus proof that a block is valid is usually included in its header and its format is entirely dependent on the consensus protocol of the blockchain. For proof of work (PoW) systems, the consensus proof is a nonce that satisfies the equation:

As you can see above, finding a value that satisfies this equation would require a significant amount of computation as the hash functions cannot be brute-forced, but verifying this consensus proof is cheap and quick.

Meanwhile, the consensus proof for a proof of stake (PoS) protocol is usually the output of a verifiable random function where:

For most blockchain protocols, Their consensus mechanisms usually only guarantee liveness¹, hence verifying these consensus proofs only tell us if this block is valid. It does not, however, tell us if this block should be considered as final. In the case of PoS, blocks that are not signed by a public key in the known authority set are not considered to be valid. Consensus proofs provide trust guarantees about a block to the nodes on the network pending finalization, as competing blocks for the same block height may arise in a byzantine system. It is entirely up to the finalization protocol to provide safety² guarantees.

(Fun fact Polkadot uses a hybrid consensus protocol where Babe³ guarantees liveness¹, while Grandpa⁴ guarantees safety²)

For light clients to verify that events are happening on chain, they need finality proof, aka a cryptographic proof that the transactions in a block are final and that the block can never be reverted. These proofs could be a part of the headers or could be requested alongside the header from full nodes.

For proof of work blockchains, this “finality proof” is actually embedded in the headers, as the proof of work nonce. But this by itself is not enough to guarantee finality. Rather, we need a certain threshold of also valid headers that reference this header as its parent in order to be truly convinced of its finality. As you can imagine this increases the storage requirements for light clients that want to be convinced of finality because they have to store n headers to verify the finality of n-1 header.

Even then the finality is entirely probabilistic and dependent on the security of the hash functions used in deriving the proof of work nonce.

For proof of stake blockchains, the finality proof is usually not included in the header but is optionally available to light clients to request alongside the headers. The finality proof will usually consist of the signatures of the known authority set, who have staked their tokens on the network and sign essentially what they think is the latest block in the network. The finality proof in this system are signatures of this data from 2/3 + 1 of the known authority set, under security assumptions that less than a third of the authority set is malicious.

Unfortunately, most finality proofs require light clients to be aware of the full chain of headers that have been finalized in order to follow the finality protocol. To enable trustless bridging between two networks via light clients which run in smart contract environments and have even worse computation & memory constraints than mobile devices we need smaller sized ancestry proofs which do not require us to be aware of every header in the blockchain.

We can attempt to achieve this using merkle trees, where a light client simply tracks the merkle root of all block headers seen so far. This would enable us to use merkle proofs to prove finality about any header to a light client that only knows the merkle root of all finalized blocks. However, because of the structure of merkle trees, we would have to recalculate the full tree structure from the genesis block all the way to the latest block, for every new block!

Some quick math:

A mind-blowing 2,097,151 nodes would need to be recalculated for every new block for blockchain that already has a million blocks. What we need is a tree structure that preserves the log2(n) proof sizes of a merkle tree but also re-uses in some way previous hash computation on older nodes in the tree whenever new data is added to the tree. Let’s take a quick detour into merkle-mountain-range trees and how they enable highly efficient ancestry proofs.

Merkle mountain ranges(‘MMR’) are a special kind of merkle tree that is itself, composed of perfectly sized binary subtrees in descending order of height. For example, an MMR tree with 1,000,000 leaves will be composed of 8 perfect subtrees of heights: 19, 18, 17, 16, 14, 9 & 6

A key feature of MMR is that we can re-use the previous computation (root hashes) whenever we add new leaves to the tree. The rules for adding new leaves to an existing MMR tree require us to merge any two subtrees of the same height (pink section and blue section merged to the hash in blue), so we only ever have one subtree per height level.

Merkle mountain ranges are also very efficient with proofs where the tree itself is composed of subtrees. Since MMR subtrees come in descending height, the first subtree is typically the heaviest to compute. This also means that as the list grows, new leaves are actually cheaper to insert and prove.

In our tree, the subtree that requires the most proof items is the first subtree, 4 + 2 (peak nodes of the other 2 subtrees) = 6 proof nodes. The beauty of the MMR is that when adding new leaves, we never need to recalculate the hashes of the first subtree, only the more recent ones.

The Beefy light client is a step towards building out the Centauri bridge which connects DotSama and Cosmos. At a high level, the bridge consists of three parts: light clients on both networks to prove finality on the other network, and a relayer that relays ibc packets and light client proofs. We have completed the development of the Beefy light client to be merged on the Cosmos side (pending reviews), and the other two components are in development.

Summary

We are building Centauri, a trustless bridge between Picasso, our parachain on Kusama and the Cosmos ecosystem. The key challenge is to reach consensus on the finality of the two networks in a trustless manner, which guarantees the correctness and security of cross-chain bridging. This is achieved with several pieces of new technologies: firstly, the light clients allow nodes to verify blockchain state without downloading the full block data, thus ensuring light computing requirements and decentralization; secondly, Merkle Mountain Range allows new block headers to be hashed in an ‘append-only’ manner, which is more suited for use in consensus subsystems than other Merkle trees; finally, the Beefy finality gadget makes use of Merkle Mountain Range to produce finality proofs for parachains in a more efficient way. The Composable team is currently contributing to the core Beefy systems as well as reviewing an IBC Light Client for Cosmos — once merged with IBC upon further audits, this will allow Cosmos chains to directly communicate with Substrate chains on Dotsama.

Related posts:

The idea is to interrupt thorough HDMI a signal. Currently there are two apps running on android box 6.0 PRO. The box is connected with a Screen via an HDMI Cable. App A is a music app (.mp3) and App…