1. Merkle Tree
Generally speaking, first we hash the block (for example: using sha256 will make blocks of different sizes become 256 fixed lengths), then we will stitch the hash results of the two adjacent blocks, and then proceed Hash, this operation is repeated until there is only one top-level hash. Of course, there is a special case: if the number of blocks is odd (if there is L5 in the figure), you can add an L5 to calculate (the picture will become L1, L2, L3, L4, L5, L5 for pairing).
Merkle tree’s existing theory is relatively mature, and the mechanism principle is easier to understand. The problem is that the details of its application scenario are not explained. In addition, the mature commercial open source solution implemented by the Java language is still in a state of being rare.
2. Business needs
Recently, the InterValue R&D team is developing a fast sync function that needs to quickly synchronize the massive blocks of consensus nodes to the newly added nodes. There is a key task here: the nodes that need to synchronize the blocks can actively discover the problem blocks, and only need to re-download the problematic blocks after discovery (For example, if there are 100 blocks need to be downloaded together to the synchronization node, where 2 blocks have problems. It only needs to re-download the 2 problem blocks, do not need to re-download all, which improves the download efficiency.), and the size of the downloaded block verification data cannot rise exponentially.
3. InterValue implements the standard Merkle Tree in Java language
The source code has been released at:
4. How does the Merkle Tree be applied to the InterValue node check data block?
There are several key concepts that need to be known in advance:
NodeContent: A block or file block is considered NodeContent, which provides two key functions: Generate hash and compare functions.
FamedRootHash: The hash root of the Merkle tree of its own is calculated by the authoritative node.
MerklePath: It consists of a hash array and an index array (which specifies whether the same position hash value is the left value “l” or the right value “r”). For the above example, the hash array of L1 is {“hash0–1”, “hash1”}, and the index array of L1 is {“r”, “r”}.
CalculatedRootHash: The hash root computed from NodeContent and MerklePath, which is used to compare with FamedRootHash.
The fast synchronization verification process is:
5. Process pseudo-code
public void validateSyncBlock() {
INodeContent[] blocks = buildBlocks();
INodeContent[] tamperedBlocks = buildTamperedBlocks();
MerkleTree mt = MerkleTree.create(blocks);
Node root = mt.getRoot();
byte[] famedRootHash = root.getHash();// which is provided by 3rd famed host
MerklePath mp = mt.getMerklePath(blocks[2]);
INodeContent tamperedBlock = tamperedBlocks[2];
INodeContent integralBlock = blocks[2];
// ignore these processes:
// …….serialize (famedRootHash,mp,tamperedBlock,integralBlock)
// ……………………………………network transmission
// …..deserialize (famedRootHash,mp,tamperedBlock,integralBlock)
if (!mp.validate(tamperedBlock, famedRootHash)) {
System.out.println(“bad news 1: tampered item”);// this would be displayed.
}
if (!mp.validate(integralBlock, famedRootHash)) {
System.out.println(“bad news 2: tampered item”);// this wouldn’t be displayed.
}
}
protected INodeContent[] buildBlocks() {
INodeContent[] blocks = new INodeContent[3];
blocks[0] = new Block(“hello”, 1);
blocks[1] = new Block(“blockchain”, 2);
blocks[2] = new Block(“world”, 3);
return blocks;
}
protected INodeContent[] buildTamperedBlocks() {
INodeContent[] blocks = new INodeContent[3];
blocks[0] = new Block(“hello”, 1);
blocks[1] = new Block(“blockchain”, 2);
blocks[2] = new Block(“worlds”, 3);// tampered item
return blocks;
}
6. Introduction
Francis.Deng (francis_xiiiv@163.com), InterValue Blockchain Architect, one of the main contributors to the project source code.