Blockchain Light Client

Published in

CodeChain

15 min readFeb 3, 2020

Photo by Miltiadis Fragkidis on Unsplash

Blockchains, in short, provide a system that can record transactions permanently with a decentralized consensus mechanism. The node that creates the block after collecting user transactions and adds that block to the actual chain is rewarded. Due to this reward, nodes are always incentivised to work. If a new block is agreed to be added, that block will remain in the chain permanently, and so will the transactions in the block. All transactions on blockchains must go through this arduous process.

However, users who want to trade tokens and other assets through the blockchain have no interest in block creation/consensus. They only want to know a fraction of the protocols included, such as whether the transaction they requested has become a part of the chain or how much their account balance is. Fortunately, it’s possible to quickly verify the information that these general users would like to know with a “light client.”

In order to understand what I’ll explain from here, you must have knowledge of PoW, PoS, and Merkle proof. If you are not familiar with these concepts, I suggest you study them before reading further.

Goal

A ‘full node’ exists by default in a blockchain. The full node stores all the necessary information about the blockchain on the local computer, performs the transaction through it, and plays an important role in proposing/validating new blocks in the chain. Full nodes have the necessary transactions/states in complex data structures, so they are quite large and execute numerous transactions directly.

To use blockchains in real life, it is a serious problem to have these full nodes running at all times. It’s also impossible to run them on your smartphone. The good news is that end users don’t verify blocks. It is sufficient to simply check the transactions or states with which they are involved in, and in this case, a full node may not be needed. The light client aims for much smaller operations and usage by eliminating those undesired features. They can be summarized as follows:

Even if the client is ‘light’, the verification power should not be lacking. In other words, it must be possible to verify transactions and states in a cryptographically reliable manner.
Must only store a small portion of information of the blockchain.
It shouldn’t know how the state is changing in the blockchain, such as transactions or staking.
It should be possible to ask the full nodes for specific information, but it need not trust them.

Blockchain’s Structure

The data sections that constitute a blockchain can be divided into the headers, transactions, states, and cache. If you think about them as a collection of cumulative sets, each one has its own unique characteristics.

Header — The header is the structure of the smallest unit that forms a ‘chain’. It contains basic information such as the hash of the previous block, timestamp, etc. It also contains the Merkle root of transactions and states. The light client is highly relevant to the header, but to put it shortly, the goal of the light client is to verify the header. This is because just by verifying the headers, it will verify all information in the Merkle tree. The light client therefore verifies/archives the header chain (chain of headers).
Header + Transaction — The set of headers plus transactions become what we call the ‘blockchain’ itself. Nodes that propose or mine a block publish ‘blocks’, and the other nodes verify those ‘blocks’. As the basic unit used in actual chains, it is the minimum set of information that can represent the entire network since it is possible to deduce the state of the entire blockchain from just a chain of headers and transactions.
Header + Transaction + State — When state is added to the previous data set, it is the maximum range that can be verified by the header. It is also the largest set that is formally ensured by the protocol that all nodes have exactly the same value. The full node has this data set and updates it. It is also the minimum amount of information needed to validate an entire block. Therefore, we need the data set explained so far to validate and vote on the newly proposed block.
… + Cache — From here, each node can have any value, regardless of protocol. This is data that depends on the implementation, and there’s no reason to verify it, nor is it possible to do so.

Header Verification

If you understand the chain structure described above, you must have realized the importance of headers. The header can verify transactions and states as long as it has the merkle root. Thus, if the header is trustworthy, all preparations are complete. So how can we verify the header?

In the case of PoW:

Verify basic things such as previous hashes, timestamps, formats, etc.
Check the nonce written in the header to complete the proof of work.

Since there is no need to check the transaction or state at all, you can complete the verification process if you have the previous header. (The discussion regarding the length of the chain will be skipped for now.)

It is simple with PoS as well, but there’s a bit more to do:

Verify basic things including previous hashes, timestamps, formats.
Verify validator set information.
Verify votes.
Check whether those votes are over two-thirds of the shares.

Unlike PoW, it requires ‘validator set information’ that is part of the state, but it’s still simple. However, this process alone cannot solve the long range attack, which is a chronic problem even for the full nodes in PoS networks. This article does not consider long range attacks.

Algorithm

In order for a light client to verify a transaction or state, it can simply ask the surrounding full nodes for the merkle proof and test it by using the merkle root of the verified header. Consequently, the header should also be verified and the procedure itself is straightforward as described above, but if you read carefully, there is something particular about the other data that you need to verify a header: their dependance on the previous block. For example, the “previous hash” can be known only by verifying the header of the previous block, and the “validator set information” can be known only by verifying the state of the previous block. So how is it possible to verify the information about the previous block needed to verify the header of interest? The answer is simple. You verify them recursively using the same method. In other words, the procedure for verifying one header can be presented inductively and neatly, and both PoW and PoS will be described separately in that respect.

PoW

Bitcoin, the representative of PoW, introduced the concept of Simplified Payment Verification (SPV). In fact, it’s just a name for what the light client will do, and since Bitcoin doesn’t specifically manage the state in the header, it’s only possible to verify payments(transactions), and that was specifically called SPV. Of course, as with Ethereum, if the Merkle roots are stored in the respective headers, it would be possible to verify the state.

The overall algorithm is as follows:

The node gets a header for the block containing the transaction you want to verify. Let’s call it H. You can ask other nodes around you to get it, or you can pick a node that you have on your local computer that hasn’t been verified yet.
If H is already verified, go to step 6. Let’s call verified H, H’. This can happen if H is the header of the Genesis block, a header that the node has already verified before, or a header provided by a trusted node.
Receive the previous header of H. Let’s call it H_p.
H_p is verified by recursion of all of these processes. Let’s call this H_p’. As mentioned earlier, the verification process for the light client is inductive. In order to ultimately verify the header of interest, the previous header must be verified, which can be solved simply by recursion of steps 1–6. The base case is described in step 2.
Use H_p ’to verify H. Let’s call this H’. The method of verifying the header with the previous header is as described above: 1. Verify the basic information of the header, including the previous hash, and 2. Verify the nonce, which is the result of the proof of work. In this case, H_p’ is needed to figure out the ‘previous hash’.
If the header of the block containing the transaction/state that the node wanted to verify first is H ‘, go to step 7. This means you are at the top of the stack after completing the recursion process! If not, return recursion to step 4.
Let T be the transaction/state that the node wants to verify. Verifying T means checking if T is actually spent in a block. Fortunately, we already have a proven header H’ of the block where T exists. In the final step, ask the full node for the Merkle proof (the other nodes that exist on the path to the Merkle root) needed to verify T.
Check whether the chain you are currently viewing is the longest blockchain. PoW agrees on the longest (one with the most computation) chain. What the light client is seeing is not exactly a blockchain, but a chain of headers; however, considering PoW’s principle, making a chain of headers as long as possible is as difficult and time-consuming as making a chain of blocks as long as possible. Therefore, simply checking the length of the chain headers can verify that they are the headers of the longest blockchain actually agreed upon.
This is the final step. Calculate T and its Merkle proof to see if it is the same as the Merkle root written in H’.

PoS

PoS light clients are somewhat more complicated than PoW. This is because in order to verify a header, you must not only verify the previous header, but the previous state as well.

The overall picture is somewhat complicated, but it is easy to understand by looking at the arrows and the components one by one.

Header, Transactions, State: Elements that are parts of the blockchain structure described at the beginning of this article. They exist in both PoW and PoS.
Votes: Votes are signed by validators in PoS. In PoS, the block is confirmed by the vote of the participant with stakes, so this must be confirmed before the block can be verified. In the Tendermint algorithm used by the CodeChain, this is called ‘pre-commit’. CodeChain holds onto the votes in the header of the next block, but this is just an implementation detail and the algorithm described below shows that the storage location is not important.
Voting behavior: Cumulative information about voting in headers up to this point. A set of information that abstracts the behavior of a validator set, and may not actually exist in an implementation. CodeChain, for example, sends validators who have not participated in a vote for a certain period of time, a policy that is deduced from a cumulative header (contains voting information) during that period. However, special actions, such as reporting, may be involved in transactions, not here.

The arrows signify the following:

Previous Hash (purple): Signifies that you have a hash of the entire block. Required for verifying headers as in PoW.
Merkle tree (light green): Signifies that the merkle tree is composed and its root is written. As with PoW, the information you want to verify with the header must have this connection.
Proves validness (red): An additional step required in PoS, this indicates the dependencies required to verify the information of the validators who agreed on the committed block.
Deduces (black): Signifies that the arrow’s output can be deduced with only the arrow’s input. For example, with all headers (information on whether validators have been voting diligently thus far), transactions, and the previous state, it is possible to deduce the next state. However, the light client doesn’t have to know about this deduction process at all, because it only needs to get the next pre-deduced state from the full node and verify it with the Merkle proof. (Think about the conditions of the light client earlier in the article!)

Data are classified as follows.

Current Step (magenta): It signifies the header to be verified. PoS is also recursive, so it can be said to represent the current recursion step.
You wanna verify these (sky blue): Data that the node actually wants to verify. To verify, you must have a verified Merkle root, which is in the header corresponding to the current step.
You need these (orange): these elements have a ‘previous hash’ or ‘proves validness’. In other words, they are what you need to verify first in order to verify the header.

The algorithm is as follows: (Similar parts as the PoW case have been omitted.)

The node gets the header of the block containing the transaction to be verified. Let’s call it H.
If H is already verified go to step 9. Verified H is called H’.
Retrieve the previous header of H. Let’s call it H_p.
Validator set data, which is part of the previous state, is obtained from the full node. Let’s call it S_p. This is necessary to calculate the validity and stake of the votes cast on H. These calculations will require not only a list of the validators, but also their mandates, ban status, and imprisonment records.
Collect votes for H (pre-commit in Tendermint). Let’s call it C. Voting is done for a particular block, and because it is signed with a private key, it is not possible to tamper with which validator voted for which block. This can be simply verified with the public key and vote summary, so it doesn’t even matter where or who you received it from. If you combine the signature value, the voting source (or information that can deduce it), and the voter’s public key as C, then C is verified as is. Let’s call this C’. In the case of CodeChain, we put C in the next block header. As explained, C is verified just by its existence, so the next block header that corresponds to the source does not need to be verified, even if the block is fake. (C can be retrieved from literally anywhere.)
H_p is verified by recursion of all of these processes. Let’s call it H_p.
Use H_p ’to verify S_p. Let’s call this S_p’. This is simple. Since the header contains the merkle root regarding the entire state, you can retrieve the merkle proof from the full node to verify it.
Use H_p ’, S_p’, and C ’to verify H. Let’s call this H’. Similar to PoW, after checking the basics of the header and the previous hash, the combination of S_p ‘and C’ verifies that the members of the valid validator set voted on H and verifies that more than 2/3 of the total when the stakes are counted. The important thing here is that you don’t have to know the staking rules for each chain, for example, when to ban and when to send to jail, and when and how to elect validators. That’s because S_p has been provided by the full node with all of those changes already applied and verified by H_p’.
If the header of the block containing the transaction/state that the node wanted to verify first is H’, go to step 10. If not, return recursion to step 6.
Let T be the transaction/state that the node wants to verify. In the final step, ask the full node for the Merkle proof needed to verify T.
Now the final step: calculate T and its Merkle proof to see if it is the same as the Merkle root written on H’.

What one should consider for the above algorithm is that the maximum amount of recursion steps depends on the amount of past states that the other full nodes store. Depending on the implementation, nodes can keep saving everything, or it can erase blocks before a certain point. In the former case, even if the recursion happens up to the genesis block, there are full nodes that are ready to always give information regarding the state at that point, so it’s okay to continue the recursion until the end. On the other hand, in the latter case, the full nodes store the past state S_p only up to a certain point, so before going beyond the range, the light node must meet S_p’, which has been verified before, and exit recursion. In other words, before the light client is too far behind, it needs to periodically apply the new block in its verified local header chain. In the worst case, where all the full nodes erase the old states immediately, they can’t catch up again if the light node misses the header of the new block even once. This is because recursion needs to be done more than once, but there is no full node to respond to that.

Optimization

The techniques described thus far are praiseworthy. This is a simple, fast and lightweight solution that only verifies the headers and accepts the rest from the full node to verify the merkle proof. However, what if you can optimize even further? Perhaps the most expensive part of the process is the manual verification of the headers. This requires the recursion of previous headers as we saw earlier. The depth of recursion depends on whether there is a reliable node that will provide the appropriate past headers, or if there are headers that have already been verified before, and in the worst case, it can go all the way to the base case, which is the genesis block. Skipping this process quickly is the main goal of optimization. In this regard, we will look at two techniques that can be applied in PoS.

The first step is to create a checkpoint. If blocks are created frequently by protocol design, you can have a period of time without changing the validator set after each block. That point is called a ‘checkpoint’, and the checkpoint can additionally contain a hash of the previous checkpoint and the validator set information of the next checkpoint. Then the light client can jump between checkpoints. For example, if there are checkpoints every 100 blocks and the header we are interested in is block 412, we will verify 4 checkpoints from the genesis block to checkpoint 400, then verify each of the 12 blocks one by one. This whole process is finished with just 16 verifications, which is way less than 412.

The second step is to trust the header validator sets that have already been verified and skip the verification process entirely. In PoW, the penalty for participating in the wrong chain is just wasted CPU computations and nothing more. PoS, on the other hand, you actually lose the deposit on the main chain if you join the wrong chain. Users who report this during this process receive a certain amount of compensation. This feature allows for unusual optimizations by just taking the risk that you’re looking at the wrong block.

For example, suppose you have a header H1 that has already been verified and you want to verify H2. If there is not much difference between H1’s validator set and H2’s validators who voted, H2’s list of validator set can be considered to be already verified. Since we do not know the valid validator set of H2, we do not know whether the votes cast at H2 are valid or not. However, if the voting participants are similar to H1’s validator set (the Tendermint team proposed a standard, which is a change of less than 1/3), most of the votes cast on H2 are probably from the members of H1 that have already been verified, making it possible to know that they are people who actually paid the deposits. (Of course, there is a problem to consider regarding how long the deposit was held.) So even if there is a risk, you can be sure that if you are really wrong, most people who voted there will have lost their deposit as well. Of course, if you are lucky, you can receive a reward by being the first one to report it. So if speed matters, we can implement this optimization with the trust that not everyone would have paid the deposit only to deceive you.

In addition, if there is a large disparity between the validator sets of H1 and H2, you can choose another block’s H3 between them as a stepping stone via binary division. Of course, if the difference between H1 and H3, or H3 and H2, is large, you can recursively minimize this gap.

Conclusion

Apart from consensus and the addition of new blocks to the chain, verifying data that has already been added is quite important and happens quite frequently, and an algorithm that handles it well and efficiently is essential. The light client designed for this purpose looks complicated, but has the simple principle of recursively verifying headers and verifying the desired transaction/state by using a verified header’s merkle root. Not only can this be applied to both PoW and PoS, but it can also be used to optimize various detailed protocols, and it can be applied to various other areas just by separating the function that verifies headers.

Light clients also play an important role in IBC. (Relationship between IBC and light clients)

CodeChain currently plans to participate in IBC and is developing a light client for it.

Thank you.