Understanding Band Oracle #3 — Lite Client Verification

This article is the last part of a series in which we will explore how Band’s oracle system operates and its constituents.

This series consist of three main components:

1. Data Sources and Oracle Scripts
We will explore the two main components of Band’s oracle system; data sources and oracle scripts. Specifically, we will define the two concepts as well as going over how they relate and operate interdependently with each other.

2. Requesting Data on BandChain
Once we have defined what data sources and oracle scripts are, we will examine the actual flow that occurs when someone submits a data request to BandChain and how the two components fit in. This section will cover both the individual processes that make up the flow and how anyone can make such requests permissionlessly with no barrier to entry.

3. BandChain Lite Client Verification
Finally, to tie everything together in the Understanding Band Oracle series, we will explore how data can be sent from BandChain to be used and verified in other blockchains. In particular, we will explore the process that makes up BandChain’s lite client verification protocol and how a data requester can use it to verify the validity of the result they received from BandChain.

Introduction

At Band Protocol, we provide a way for dApps to access off-chain information through our decentralized oracle. As part of that offering, we also provide a lite client for anyone who requested data from our oracle to verify the validity of the result they received. An instance of this client exists on each of the blockchains to which Band has integrated with.

In this article, we examine the verification process performed by our lite client on EVM-compatible blockchains with Solidity. When someone submits a verification request to our lite client, they must also send in the encoded result they got from our oracle. That result is not just the data they requested, but also contains information on the request itself as well as the associated response.

The lite client’s purpose is then to use that information to show that the data the user requested exists on BandChain, thus verifying the oracle result’s validity. Before looking more into how the client does that, let’s take a step back and examine the oracle data request flow that precedes it.

Data Request Flow using Band’s Oracle

We can break down the flow that occurs when someone requests data from Band’s oracle into 4 steps:

1. An external party requests data from our oracle on BandChain
2. Once the transaction resulting from the request is confirmed on BandChain, the chain’s validators proceed to fetch the requested oracle data from the external source
3. BandChain then uses the results retrieved by the validators to compute a final result and stores that result on the chain
4. Finally, BandChain returns a proof to the requester showing that the result now exists on the chain, which they then proceed to submit to an Ethereum smart contract

Now we can start to examine the actual verification process.

Lite Client Verification Process

Once the smart contract receives the oracle result, they proceed to verify that the result actually comes from BandChain. They do this by submitting a verification request to the lite client. The aim of this process is to ensure that the data received is actually part of BandChain’s state and is signed by a sufficient number of BandChain’s block validators.

More specifically, the lite client’s goal is to prove 3 statements:

1. that the proof received in the request can be used to construct a valid block header
2. that using the constructed block header, it can recover a valid set of validator addresses who signed on the block
3. that those validators have sufficient total voting power relative to the system total

The diagram below illustrates the above steps.

Before looking at each of them in more detail, let’s first look at the concepts that we will use. As Band’s BandChain is built on top of the Cosmos SDK, these concepts are from the SDK, as well as the underlying Tendermint framework.

A Primer on Key Tendermint and Cosmos Concepts

Tendermint Block Header

As of version 0.33.0, a Tendermint blocker header contains 14 pieces of information about the block. Two that are of particular importance to us are the appHash and the lastCommitHash.

• appHash represents the state of our application after the transactions from the last block.
• lastCommitHash represents the commits on the previous blocks, as well as the signatures of the validators who signed on that block.

More information on the block header and its contents can be found here.

Hash Tree Representation

We can also represent the block header as a hash, where that hash is the root of a Merkle Tree with 14 leaf nodes. Those leaf nodes are the hashed value of each of the block header contents mentioned above.

As with other Merkle Trees, any non-leaf node in this block header tree is the hash of its two children nodes. The block header hash (i.e., the blockHash), being the tree's root node, is the hash of all the data in the tree, and thus can be used as a representation of the state of the entire block. Similarly, any changes to a non-root node will propagate up the tree, eventually changing the blockHash as well.

As a slight aside, a consequence of this “upward propagation” is that anyone can ensure that the block data is correct by just looking at the block header, rather than having to navigate through the entire structure of the tree. This is because an attempt to alter a node will propagate upwards and lead to an inconsistency up the tree.

For example, in the example below, if we changed the rightmost leaf node, that change causes a chain reaction of changes up the tree, ultimately changing the blockHash as well. Then, from a block signer’s point of view, they will quickly notice that the blockHash has changed and is no longer what they expect without needing any information about the other nodes below.

What’s more important in our case, however, is the fact that if a change in one of the root nodes caused an unexpected change to the blockHash, we will no longer be able to recover the other block information from it correctly. We will revisit this point later in the article. Let’s now take a look at the appHash in more detail.

AppHash

As previously stated, the appHash represents the state of our application after the transactions from the previous block. Structure-wise, appHash can be thought of as a root node of another Merkle Tree, where the leaf nodes are the various Cosmos modules, also known as stores, found in our application. For example, the above diagram shows the structure of our BandChain application.

One unique property of the appHash is that it is application-specific, meaning an appHash can only be generated by its corresponding application alone. This uniqueness allows for application-specific proofs about the state of the application.

Tendermint iAVL Trees

In our Merkle tree model, we represent each of the modules/stores as Tendermint iAVL trees.

This tree structure differs from a traditional Merkle tree in that the layout of the tree results from a variant of the AVL algorithm. Similar to a regular AVL tree, the heights of the two children subtrees of any node differ by at most one.

This results in the main benefits of this structure: all operations have an efficient O(log(n)) runtime. Specifically, in our case, this means we can efficiently compute the Merkle hash of the tree.

As for the differences, as well as the potential downsides, please see Cosmos’ whitepaper.

Band Protocol Lite Client Verification

Now that we have covered the basics, we can now return to looking to prove the 3 statements, which as a reminder are:

• that the proof the client received along with the verification request can be used to construct a valid block header
• that using the constructed block header, the client can recover a valid set of validator addresses who signed on the block
• that those validators have sufficient total voting power relative to the system total

The diagram below shows the details of these steps. Let’s look at each of them in detail.

Constructing the blockHash

The steps for constructing the blockHash are as follows:

• Use the proof sent it to construct the oracle store’s root hash
• Combine the oracle store hash with the hashes of the other stores in our application to compute the appHash
• Finally, use the appHash, in combination with other block information hashes, to compute the blockHash

Let’s go over each of them one-by-one.

Constructing the Oracle Store

Oracle Store Tree Contents

As previously mentioned, each store in our application is an iAVL tree root node. The bottom of these store trees is then the byte representation of the data in that module. In our case of the oracle store root, two data pieces that we will be looking at are the requestPacket and responsePacket.

The requestPacket encodes the oracle request sent from other blockchains to BandChain. It contains information such as the identifier of the oracle script requested and the number of validators that are requested to respond to this request, among others. On the other hand, responsePacket is the encoded oracle response from BandChain to the requester. This response includes the number of validators that actually responded to the request, the timestamp of when the request was sent and when it was resolved to a final result, along with the actual final result itself if the request was successful. A full and more detailed breakdown of the packets’ contents, please see our GitHub repository.

By also returning contextual information on the request and response, in addition to the actual result itself, we aim to give as much information as possible for the user to use in their application or for any further verification they might want to perform.

Constructing the oracle store leaf node

Using requestPacket and responsePacket, we can combine their hashes to get an intermediary hash value, which we called the dataHash. If we then encode and hash this appended by other information such as the version (i.e., the latest block height that the data node was updated), and the request ID of the request, we arrive at the leaf node of the oracle store tree, also known as the resultHash

After we have the leaf node, we then need to use that node to gradually climb up the tree to reach the store’s root node. To help us do so, we use an additional piece of information in the proof; the merklePaths.

Computing the oracle store root hash

The merklePaths we mentioned is a Merkle proof that shows how the dataHash leaf we just computed is part of the larger oracle tree. The proof’s content is the list of “Merkle paths” from the leaf to the root of the tree. Each of these paths or proof components themselves consist of:

• isDataOnRight: whether the data is on the right subtree of this internal node
• subtreeHeight: the height of this subtree
• subtreeVersion: the latest block height that this subtree has been updated
• siblingHash: hash of the other child subtree

Using this information, we can compute the parent hash of our dataHash. If we then repeat this process, we can gradually climb up the store tree, finally getting the oracle store root hash we want.

Computing the appHash and the blockHash

After we have the oracle store root, we can begin to iteratively combine it with the hashes of the other stores in our application to compute the appHash. However, note that we do not need all of the leaf node hashes of the appHash tree. Due to the nature of a Merkle tree, we only need the branch nodes [A], [B], [C], and [L], alongside the params node. The appHash tree structure is shown again below, with the hashes we require highlighted in red.

We can then use that appHash to finally compute the blockHash using the same method as above. But this time, as we want to validate the correctness of our appHash at this blockHeight we only need the branch nodes [D], [F], [G], [K], as well as the height, time, and appHash values.

Recovering Signer Addresses

After we have constructed a blockHash, we can move on to prove its validity by attempting to use it to recover the addresses of the validators who signed on this block using Ethereum’s ecrecover opcode. To ensure that the addresses we extracted are valid, we check to make sure that each address we extract is unique.

As we recover each signer, we also add each extracted validator’s voting power to a counting tally, which we will use later.

Checking Total Voting Power

Once we have extracted all of the validators and ensure that the extracted order is correct, we proceed to check if the tallied voting power is sufficient; specifically, that the tallied value is at least two-thirds of the system’s total voting power. This threshold check is to ensure that we reach consensus.

If the tallied voting power exceeds the two-third threshold, we have successfully proven that the proof is valid. Our lite client can then decode the result and return it to the requester to either use or further validate themselves.

Wrapping Up

In this article, we outlined the steps that make up our lite client’s verification process. For those who are looking for more details, along with the actual implementation, feel free to check out our EVM Bridge repository, in particular Bridge.sol, for an example written in Solidity.

bandprotocol/bandchain

Conclusion

Throughout this series, we have explored the ways in which BandChain enables trustworthy decentralized applications to be built. From the data sources and oracle scripts in which we can receive the data from to BandChain itself which acts as the trusted platform in which to aggregate and process data to the lite client that allows for the verification of the result.

About Band Protocol

Band Protocol is a cross-chain data oracle platform that aggregates and connects real-world data and APIs to smart contracts. Blockchains are great at immutable storage and deterministic, verifiable computations — however, they cannot securely access data available outside the blockchain networks. Band Protocol enables smart contract applications such as DeFi, prediction markets, and games to be built on-chain without relying on the single point of failure of a centralized oracle. Band Protocol is backed by a strong network of stakeholders including Sequoia Capital, one of the top venture capital firms in the world, and the leading cryptocurrency exchange, Binance.

Website | Whitepaper | Telegram | Medium | Twitter | Reddit | Github