Light Clients in Tendermint Consensus

Alongside the core consensus engine, we are building a large set of tooling for the Tendermint ecosystem and the Cosmos Network. Since the release of basecoin 0.6 in June 2017, we have a complete and working implementation of our light client protocol, which allows a client to get cryptographic proofs of the state and transactions without syncing all blocks or even all headers.

This gives a light client all the security of a full node while minimizing bandwidth requirements. In fact, this light client protocol is so secure we can use it as the basis of Cosmos IBC. And the minimal amount of bandwidth required allows developers to build fully secure, efficient and usable mobile apps.

Let us look at how other chains think about light clients before delving into how our protocol works.

How Bitcoin Verifies Transactions

Run a full node or trust the proxy:

If you want to participate in the network, you are expected to run a non-mining full node. Running a full node involves receiving a mined block roughly every 10 minutes and then applying the latest Unspent Transaction Outputs (UTXOs) to your local state machine.

Following the Bitcoin blockchain once a full node is synced with the network is a simple task. Over a day, a full node downloads a little over ~170MB of data, or about a quarter of a million simple transactions. The larger problem arises for new nodes that want to join the network and have to sync the entire blockchain after it has been running for some years. It currently takes 3–4 days with a stable and fast connection to synchronize the 174GB (and growing) Bitcoin blockchain.

Due to the high barrier to entry for individuals to verify their own transactions, users usually rely on trusted third parties that act as gateways. Although forgery on the p2p layer is near impossible, it is possible for a trusted proxy to deceive you. This reliance on a third party fundamentally negates one of the core advantages of decentralized protocols in the first place.

How Ethereum Verifies Transactions

Just follow the headers:

Ethereum introduced many innovations to the blockchain space. The most notable was the addition of smart contracts. This allows users to upload and execute “arbitrary” code as part of the state transition. It also makes transactions much larger and more expensive to execute, as they must be run by the Ethereum Virtual Machine (EVM) and normally require more than a few atomic operations, as is the case in Bitcoin.

Ethereum circumvents this issue by storing the entire state in a Patricia Tree, allowing the construction of Merkle proofs, which trace any key-value pair in the store with only a few KB. This root hash is stored in the block header. Given a proper block header, a client can verify any key-value pair in the corresponding block. Thus, an Ethereum light client just has to synchronize and verify all headers in the blockchain. Then a client can query any key in the current state. Furthermore it is able to verify the result of the query without having to run a single transaction or trust any node.

Even though it is a major step forward, it still involves downloading all headers, which is a non-trivial amount of data.

How Tendermint Verifies Transactions

Just follow the validator changes:

Tendermint, like Ethereum, stores a Merkle root hash in each block header to prove its state in an efficient manner. Although Tendermint uses a slightly different data structure (an IAVL+ tree rather than a Patricia Tree), the effect is similar. If a client has a correct header, then it can verify any key-value pair for a block at that height.

The difference is that with Tendermint’s throughput of 1 block per second, even following the headers can become a time-consuming task, especially if a client does not have a persistent connection. For example, you might turn off your phone while sleeping and when you turn it back on you must download 30,000 headers. However, there is an elegant solution which is tied to Tendermint’s instant finality property (meaning it never forks).

Using a Byzantine fault-tolerant consensus algorithm, Tendermint achieves instant finality. As long as less than two-thirds of the validators are malicious, a client can trust any header that is signed by a known validator set (VS). If the VS is static, a client only has to securely receive the genesis file with the static VS and can then check the signatures of any header. If the header was signed by over two-thirds of the static VS, the client can be certain that it is a valid block that has been included in the chain.

The validator set in the Cosmos Network is not static but rather changes over time as new validators receive a larger economic stake or old validators are punished. With a dynamic validator set, a client has to keep track of the changes to the validator set. For this reason, any time there is a change in that set, the client has to download a new header, verify the validator set change is valid, and update the local validator set. The Tendermint Proof-of-Stake algorithm introduces a three week unbonding period in order to avoid long-range nothing-at-stake attacks. This means that as long as the last trusted header was more recent than the unbonding period, a client is secure.

Real world example — how changing the validator set works:

If there are 10 validators that a client trusts on block A, and only 9 of those validators signed block B, a client is certain that it was a valid change, since a super-majority (> ⅔) of the validators that the client trusted before this block, signed it. If the current block was signed by only 6 of the trusted validators (from the previous block) along with 4 completely new validators, the client will reject this block as invalid as it has not been signed by a super-majority. In Tendermint, as in any other BFT algorithm, over two-thirds of the validating nodes have to be honest. If an attacker controls over two-thirds, they can fool anyone, including full nodes.

Real world example — how a light client works in practice:

On Friday evening your phone has a snapshot of the currently trusted set of validators. You decide to turn it off for the night. On Saturday morning your phone connects again. In this stage, your client only has to download the most recent header, which is about 2KB. If the validator set did not change overnight, or if it did change, but only by less than one-third of the total from the previous set, your phone will immediately trust the new set. At this point, your phone can verify any state from the blockchain as described above (proof of state and transactions) and can interact with the blockchain in a fully secure manner. Very notably, you just skipped over Ethereum’s requirement of downloading and validating 30,000 intervening block headers.

If the validator set did change considerably in the time a client was offline, it still does not have to download all headers. Instead, it can find a path of intermediate headers. The requirement for this path for any two consecutive headers is that the validator set changes by less than one-third.

At 06:00 the validator set consists of validators A, B, C, D. At 09:00 the validator set consists of validators A, B, C, E.
At 12:00 the validator set consists of validators A, B, E, F.

A light-client (phone) trusts the validator set at 06:00 (A, B, C, D) (for example by manually checking that it is correct). It now goes offline and only comes back at 12:00. It will receive the new validator set (A, B, E, F). Here 50% changed which is an unsafe change, because the light-client cannot verify that >2/3 of the validators it trust (from the set at 06:00) signed off on that change. This means that it might have received a byzantine packet.

The phone however can ask for an earlier header (from 09:00). Here the validator set (A, B, C, E) has changed by <1/3. This is a trusted change in the validator set and the phone now has an updated trusted validator set( A, B, C, E). From here it can update to the most recent validator set (A, B, E, F), because between ABCE and ABEF is <1/3 change.

Overall, the change in the validator set can be much larger. This shows that even if there are large changes in the validator set, a light client still only has to do a minimal amount of work in order to securely update its validator set.

Tendermint — From Theory to Practice

As of basecoin 0.6, Tendermint ships with a fully functional light client. Basecoin is the server, and basecli is a client designed for your laptop. If you want to connect to the testnet, you will have to initialize the client one time with the trusted validator set (from the genesis file). After that, it will automatically update itself and ask for all the proofs it needs to verify any information it receives from a node. If the node gives an invalid proof, it will present an error.

Got questions? Ask them in Riot Chat.

Or join the discussion on Telegram: t.me/cosmosproject