Generally, you need to have a client when connecting to the blockchain network. There are different types of nodes: full node, light node, mining node and relay node. In this article, we will focus on how a light client node works because not everyone can run a validator node (full node) in Libra since it is a permissioned blockchain. Instead of fully verifying all transactions and blocks, light clients only need to download block headers and verify if interested transactions are included in the block. Light clients are run by devices that do not have huge computation power and bandwidth.

Simplified Payment Verification

Next, we will introduce Simplified Payment Verification (SPV), which is proposed by Satoshi in Bitcoin whitepaper. SPV is a method for light client to verify a transaction without downloading the entire blockchain. The idea is to fetch block headers from the full node until the client finds interested transactions that are included in the block. Then, the light client will retrieve the merkle root and merkle branch associated with a particular block, and prove the transaction existing in the block.

Merkle Tree

Merkle tree is a data structure used to store data efficiently. We call the root of the merkle tree a merkle root. Each leaf node represents a hash of the data. And every non-leaf node is labelled with the cryptographic hash of its children nodes. Once we want to verify if the data is in a merkle tree, a secure and efficient verification can be realized. We will use the figure from Libra’s whitepaper to illustrate how it works.

From the above figure, each node is represented as a hash value where || denotes string concatenation. For example, h4 is the hash of the concatenation of h0 and h1, formulated as:

h4 = H(h0 || h1)

If we want to verify whether s2 is in the merkle tree, we can retrieve h3, h4 and a(i.e. merkle root). Then, we can simply verify if the merkle root a =? H(h4 || H(H(2 || s2) || h3)). Therefore, a SPV client only needs to query the merkle root and merkle branch from a particular block.

Noted that since the merkle root and the merkle branch are provided from the full node, the verification can be manipulated by a malicious full node, thus, fraud proof is required. But in Libra, the validator nodes are maintained by the Libra Association, so we assume we can trust the validator node here.

Transaction information

Before we start to go deep into Libra transaction verification by using SPV, we need to understand the format of the leaf in the tree.

RawTransaction

A Libra raw transaction is the basic transaction format and it consists of 6 fields:

1. sender — Account address of the sender of the transaction.
2. sequence number — An unsigned integer that must be equal to the sequence number stored under the sender’s account.
3. transaction payload — A transaction script that will be executed by virtual machine.
4. max gas amount — The maximum units of gas the transaction is allowed to consume.
5. max gas price — The amount the sender is willing to pay per unit of gas to execute the transaction.
6. expiration time — The time after which the transaction ceases to be valid.

SignedTransaction

After creating a raw transaction, client needs to sign the transaction to authorize the action. A signed transaction will look like:

1. raw transaction — The complete RawTransaction.
2. public key — The public key of the sender.
3. signature — The transaction signature signed by the sender.

TransactionInfo

When a signed transaction is sent to Libra node, it will be stored in the blockchain if passing the validation. A transaction info is the basic object that Libra adds to the transaction merkle tree. It consists of the transaction as well as the execution result of the transaction. The format of transaction info is:

1. signed transaction hash — The hash of a SignedTransaction.
2. state root hash — The root of the world state after executing this transaction.
3. event root hash — The root of all the events emitted during this transaction.
4. gas used — The total gas used by executing this transaction.
5. major status — The transaction execution result.

To sum up, following is a figure showing how the Libra transaction tree is formed.

Transaction accumulator

Since Libra doesn’t have the concept of a block explicitly, every transaction will be processed immediately when it passes validation and is sent to the network. Whenever a new transaction is added to the blockchain, the transaction will be put to the rightmost leaf in the merkle tree. Therefore, the value of the merkle root will change every time when a new transaction is committed and the merkle tree will grow with time. Given an ever growing tree, the transaction merkle tree is also named transaction accumulator.

Assume there is a merkle tree with 2 levels, the merkle root is calculated as the hash of the concatenation of h1 and h2.

There is a new transaction h3 executed successfully and added to the transaction accumulator. Since every non-leaf node is the hash of its two children, a default leaf node is needed. This default leaf node is a placeholder in order to maintain the rule of the merkle root calculation and will be replaced by the next transaction.

As the figure shows above, the value of the merkle root has changed after a new transaction was added. Also, in this case, the size of the tree has grown bigger.

It’s worth noting that because of the irreversible nature of blockchain the left side of the transaction accumulator is deemed to be finalized (h1, h2, and the parent). The value of these 3 nodes won’t be changed again in the event of new leaves being added so they could be saved to the disk.

When a node has all its descendants being non-placeholder — it becomes “Frozen”.

For writing to disk, Libra nodes write all the children of a node before the parent by their post-order position. In this way, the physical representation of the tree is append-only. Once written to physical storage, nodes won’t be either modified or deleted. Here, nodes with post-order position 1 to 3 are now frozen in the disk and the next node that will be written to the disk must be with position 4.

Now, another new transaction h4 arrives.

The placeholder was replaced by h4 and the merkle root has changed again. Also, the whole tree is now considered as frozen and the rest of the tree can be written to the disk in the order of post-order position.

---

There is a brief illustration of transaction accumulator from Libra technical whitepaper.

Libra transaction verification

When you get a transaction from a gRPC client it will show something like this:

version: 44767
signed_transaction {
  signed_txn: "..."
}
proof {
  ledger_info_to_transaction_info_proof {
    bitmap: 45055
    non_default_siblings: "..."
    non_default_siblings: "..."
    non_default_siblings: "..."
    ...
  }
  transaction_info {
    signed_transaction_hash: "..."
    state_root_hash: "..."
    event_root_hash: "..."
    major_status: 4001
  }
}
events {
  ...
}

version

Every transaction has a unique version. When a transaction is committed to the transaction accumulator, its version is determined at the same time. The version is its leaf position (not the post-order position) in the transaction accumulator. It can easily let us know whether the node along the path is the left node or the right node.

For example, a transaction’s version is 4 and its binary representation is 100. 0 means the direction is left and 1 means the direction is right. Therefore, we can simply find this transaction by going right once and going left twice from the root.

bitmap & non_default_siblings

From the comment in Libra source code, the definition of the bitmap is to tell which siblings are default.

The bitmap indicating which siblings are default. 1 means non-default and 0 means default. The LSB corresponds to the sibling at the bottom of the accumulator. The leftmost 1-bit corresponds to the sibling at the level just below root level in the accumulator, since this one is always non-default.

Since the transaction accumulator is growing larger, very often the tree is not a full binary tree. Therefore, as we mentioned before, a placeholder is needed to maintain the root calculation.

For example, the sibling in the right is the placeholder. The binary representation of the bitmap will be 101 or 5 in integer. Also, in this scenario, there should be exactly two non-default siblings provided by gRPC response.

In short, the number of 1 in the binary representation of bitmap should be correspondent with the number of non_default_siblings.

transaction_info

transaction_info encompasses the detail of this transaction. Note that major_status should be 4001 indicating EXECUTED by the node. And the gas_used is not shown for its value being zero.

events

events is the contract events emitted during the transaction. A normal peer-to-peer transaction will invoke one of a standard transaction scripts, peer_to_peer_transfer.mvir, and it will emit exactly two events (one sent event and one received event).

---

Finally, here is a Python code snippet to verify a Libra transaction merkle proof.https://medium.com/media/e5374e033497feee9ca1d00347738c78

Let’s break down some details.

info = TransactionInfo(
    tx_info.signed_transaction_hash,
    tx_info.state_root_hash,
    tx_info.event_root_hash,
    tx_info.gas_used,
    tx_info.major_status
)m = create_hasher()    m.update(create_hasher_prefix(b'TransactionInfo'))    m.update(info.serialize())
result = m.digest()

First, a leaf of the transaction accumulator is the hash of the transaction info. The serialization in Libra is called Libra Canonical Serialization (LCS). It’s similar to RLP serialization in Ethereum. If you are interested in the concept of LCS, you could find the document here.

The default hash function in Libra is sha3–256, which is different to keccak-256 used by Ethereum. Every Libra hasher would require a different prefix to prevent domain ambiguity and all the Libra hashers should add another prefix as well. For instance:

• The prefix for the hash of transaction info is

SHA3–256(b’TransactionInfo@@$$LIBRA$$@@’)

• The prefix for the hash of the transaction accumulator node is

SHA3–256(b'TransactionAccumulator@@$$LIBRA$$@@’)

Next, we verify the merkle proof of the transaction info. The LSB in version indicates the node is the left one or the right one. And the LSB in bitmap indicates whether the sibling is a placeholder or not.

while bitmap > 0:
    m = create_hasher()
    m.update(create_hasher_prefix(b'TransactionAccumulator'))
    if bitmap % 2 == 0:
        sibling = ACCUMULATOR_PLACEHOLDER
    else:
        sibling = siblings.pop()    if tx_version % 2 == 0:
        m.update(result)
        m.update(sibling)
    else:
        m.update(sibling)
        m.update(result)
    result = m.digest()    bitmap //= 2
    tx_version //= 2

The accumulator placeholder is defined as

b'ACCUMULATOR_PLACEHOLDER_HASH\000\000\000\000'

Last, the result should be equal to the root!

Conclusion

In this article, we explain how to verify a Libra transaction without running a full node. If you are interested in the complete codebase, please check this repository. We developed a LibraSwap MVP which allows clients to do unilateral atomic swaps between Libra and Ethereum. For more information about LibraSwap or the basic concept of Libra, please check here and here.

Hope this article is useful and informative. Cheers!

Reference

• https://developers.libra.org/docs/libra-protocol#transactions
• https://developers.libra.org/docs/assets/papers/the-libra-blockchain.pdf
• https://github.com/libra/libra

---

Thanks to AMIS徐粲邦. He provides this article.

Original Article