Data Validation

Symbol uses tree structures to store large data associated with a block that cannot be retrieved directly from the block header. This allows light clients to verify if an element (e.g. transaction, receipt statement) exists without demanding the entire ledger history.

Merkle tree

graph TD A --> H1["H1 = H(A)"] B --> H2["H2 = H(B)"] C --> H3["H3 = H(C)"] D --> H4["H4 = H(D)"] E --> H5["H5 = H(E)"] H1 --> H6["H6 = H(H1 +H2)"] H2 --> H6 H3 --> H7["H7 = H(H3 + H4)"] H4 --> H7 H5 --> H8["H8 = H(H5+H5)"] H6 --> H9["H9 = H(H6+H7)"] H7 --> H9 H8 --> H10["H10 = H(H8+H8)"] H9 --> R["HRoot = H(H9+H10)"] H10 --> R

Diagram of a Binary Merkle Tree

A Merkle tree is a structure of nodes labeled by hashes. Pictured above is the simplest form of a Merkle tree, the binary Merkle tree. In particular, Symbol generates two Merkle Trees per block:

  • Transactions Merkle Tree: Stores all the transactions included in the block.
  • Receipts Merkle Tree: Stores all the receipt statements linked to a block.

Leaf nodes

A leaf node of the tree contains the SHA3-256 hash of an element attached to the block. The leaves are ordered by index as they appear on the block. A Merkle tree is built by hashing together two hashes, from left to right, repeating the process until a singular hash is created.

Note

If there is a layer with an odd number of hashes (and the number is different to 1), the last hash is doubled.

Merkle root

The hash at the bottom of the tree is called the Merkle root. The Merkle root hashes for receipts and transactions are included in block headers to summarize the data linked.

The following example shows how to verify that a block is composed of all its transactions:

  1. Obtain HRoot; in Symbol, this is stored in the block header.
  2. Calculate HRoot’ creating a Merkle tree with all the transactions within the block in natural order.
  3. Compare HRoot and HRoot’.
View Code
import {sha3_256} from 'js-sha3';
import {MerkleTree} from 'merkletreejs/index';
import {QueryParams, RepositoryFactoryHttp, UInt64} from 'symbol-sdk';

const example = async () => {
    // replace with node url
    const nodeUrl = 'http://api-01.us-east-1.096x.symboldev.network:3000';
    const repositoryHttp = new RepositoryFactoryHttp(nodeUrl);
    const blockHttp = repositoryHttp.createBlockRepository();
    // replace with block height
    const height = UInt64.fromUint(1);

    // 1. Obtain HRoot; in Symbol, this is stored in the block header.
    const HRoot = (await blockHttp.getBlockByHeight(height).toPromise()).blockTransactionsHash;
    // 2. Calculate HRoot' creating a Merkle tree with all the transactions within the block in natural order.
    // Note: This code snippet assumes that the block has less than 100 transactions.
    const queryParams = new QueryParams({pageSize: 100})
    const transactions = await blockHttp.getBlockTransactions(height, queryParams).toPromise();
    const leaves = transactions
        .sort((n1, n2) => n1.transactionInfo!.index - n2.transactionInfo!.index)
        .map((transaction) => transaction.transactionInfo!.hash);
    const tree = new MerkleTree(leaves, sha3_256, {
        duplicateOdd: true,
        hashLeaves: false,
        sort: false,
        sortLeaves: false,
        sortPairs: false,
        isBitcoinTree: false});
    const HRoot0 = tree.getRoot().toString('hex');
    // 3. Compare HRoot and HRoot'.
    return HRoot.toUpperCase() === HRoot0.toUpperCase();
};

Merkle proof

A Merkle proof (also known as Merkle path) is the minimum number of nodes required to calculate the Merkle root again.

graph TD style B stroke:#333,stroke-width:4px style H1 stroke:#333,stroke-width:4px style H7 stroke:#333,stroke-width:4px style H10 stroke:#333,stroke-width:4px A --> H1["H1 = H(A)"] B --> H2["H2 = H(B) (target)"] C --> H3["H3 = H(C)"] D --> H4["H4 = H(D)"] E --> H5["H5 = H(E)"] H1 --> H6["H6 = H(H1 +H2)"] H2 --> H6 H3 --> H7["H7 = H(H3 + H4)"] H4 --> H7 H5 --> H8["H8 = H(H5+H5)"] H6 --> H9["H9 = H(H6+H7)"] H7 --> H9 H8 --> H10["H10 = H(H8+H8)"] H9 --> R["HRoot = H(H9+H10)"] H10 --> R

The nodes highlighted belongs to the Merkle proof of B.

The following steps are taken to validate if an element belongs to a given block:

  1. Calculate H(B); the hash of the element you want to validate if exists within a block.
  2. Obtain HRoot; in Symbol, this is stored in the block header.
  3. Request the merkleProof: H1, H7, H10.
  4. Calculate HRoot’. Concatenate H(B) with the first unprocessed item from the merkleProof list as follows:
  1. If item.position == left -> proofHash = sha_256(item.hash + proofHash).
  2. If item.position == right -> proofHash = sha_256(proofHash+ item.hash).

Repeat 4. for every item in the MerkleProof list.

  1. Compare if the HRoot’ equals to HRoot.
View Code
import {sha3_256} from 'js-sha3';
import {BlockRepository, MerklePosition, RepositoryFactoryHttp, UInt64} from 'symbol-sdk';

const validateTransactionInBlock = async (leaf: string, height: UInt64, blockHttp: BlockRepository) => {
    // 2. Obtain HRoot; in Symbol, this is stored in the block header.
    const HRoot = (await blockHttp.getBlockByHeight(height).toPromise()).blockTransactionsHash;
    // 3. Request the merkleProof: H1, H7, H10
    const merkleProof = (await blockHttp.getMerkleTransaction(height, leaf).toPromise()).merklePath!;
    // 4. Calculate HRoot'.
    if (merkleProof.length === 0) {
        // There is a single item in the tree, so HRoot' = leaf.
        return leaf.toUpperCase() === HRoot.toUpperCase();
    }
    const HRoot0 = merkleProof
        .reduce( (proofHash, pathItem) => {
            const hasher = sha3_256.create();
            if (pathItem.position === MerklePosition.Left) {
                return hasher.update(Buffer.from(pathItem.hash + proofHash, 'hex')).hex();
            } else {
                return hasher.update(Buffer.from(proofHash + pathItem.hash, 'hex')).hex();
            }
        }, leaf);
    // 5. Compare if the HRoot' equals to HRoot.
    return HRoot.toUpperCase() === HRoot0.toUpperCase();
};

const nodeUrl = 'http://api-01.us-east-1.096x.symboldev.network:3000';
const repositoryHttp = new RepositoryFactoryHttp(nodeUrl);
const blockHttp = repositoryHttp.createBlockRepository();
// Define block height
const height = UInt64.fromUint(1);
// 1. Calculate H(B); the hash of the element you want to validate if exists within a block.
const leaf = '1F4B55D42C9C91805E73317319DDDA633667D5E44EB0F03678FF7F130555DF4B'.toLowerCase();
validateTransactionInBlock(leaf, height, blockHttp).then((result) => console.log(result));

Continue: Consensus Algorithm.