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.
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.
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.
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:
Obtain HRoot; in Symbol, this is stored in the block header.
Calculate HRoot’ creating a Merkle tree with all the transactions within the block in natural order.
Compare HRoot and HRoot’.
import { sha3_256 } from 'js-sha3';
import { MerkleTree } from 'merkletreejs/index';
import { QueryParams, RepositoryFactoryHttp, UInt64 } from 'symbol-sdk';
const example = async (): Promise<boolean> => {
// replace with node url
const nodeUrl = 'NODE_URL';
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();
};
A Merkle proof (also known as Merkle path) is the minimum number of nodes required to calculate the Merkle root again.
The following steps are taken to validate if an element belongs to a given block:
Calculate H(B); the hash of the element you want to validate if exists within a block.
Obtain HRoot; in Symbol, this is stored in the block header.
Request the merkleProof: H1, H7, H10.
Calculate HRoot’. Concatenate H(B) with the first unprocessed item from the merkleProof list as follows:
If item.position == left -> proofHash = sha_256(item.hash + proofHash).
If item.position == right -> proofHash = sha_256(proofHash+ item.hash).
Repeat 4. for every item in the MerkleProof list.
Compare if the HRoot’ equals to HRoot.
import { sha3_256 } from 'js-sha3';
import {
BlockRepository,
MerklePosition,
RepositoryFactoryHttp,
UInt64,
} from 'symbol-sdk';
const validateTransactionInBlock = async (
leaf: string,
height: UInt64,
blockHttp: BlockRepository,
): Promise<boolean> => {
// 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 = 'NODE_URL';
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),
);
