VeriSync - A Fast and VERIfiable SYNC Method for Blockchains
Full block synchronization consumes lots of time and space in CodeChain. The required amount of resources increases as the size of the blockchain grows, and this is an inevitable problem due to the fundamental property of the blockchain. Many other projects introduced a feature that mitigates this problem, which allows the blockchain nodes to start from the “snapshot” in the middle of the history so that they don’t have to execute a full block synchronization to catch up to the current status. CodeChain (and also CodeChain foundry) also tried to introduce this solution to mitigate the full-sync problem, and the detailed specification can be found in this research article.
VeriSync is the name of our new sync method that is fast and verifiable. A node that is using the VeriSync method downloads the state of a specific block (called snapshot) and starts from there. The node does not receive blocks before the snapshot block. What makes VeriSync special is that it can verify a snapshot incrementally, making CodeChain resilient to DoS attacks that give invalid snapshots.
The shape of the snapshot
A snapshot of VeriSync consists of chunks. A chunk contains descendants of a chunk root and their depth is less than the depth of root plus D (D is a constant). The Merkle root of a chunk is always the chunk root.
We call nodes at the end of a path in a chunk ‘terminal nodes’ (red ones in the figure) and the others, ‘non-terminal nodes’ (blue ones in the figure). A node in a Merkle tree is either a Branch node or a Leaf node. A Leaf node is a node that doesn’t have a child. Therefore, all non-terminal nodes are Branch nodes, but a terminal node can be either a Leaf or a Branch.
Download the snapshot
When a CodeChain program downloads a snapshot, it first downloads a chunk whose root is the root of the total state tree. After receiving the root chunk, there should be some branch terminal nodes. The children of the terminal branch nodes are new chunk roots that should be downloaded. Here is the pseudo-code of the algorithm:
While downloading chunks, we can verify each chunk individually by reconstructing the Merkle tree of the chunk and comparing its Merkle root with the known Merkle root. Since we verify chunks from the trusted root to the leaves, we can extend the trust all the way towards the leaves. In other words, you can verify the entire state incrementally.
Benchmark results
We benchmarked our VeriSync implementation in our test network, Corgi. The time required for the full synchronization is 10h 40m. The snapshot synchronization took 3m 46s on the same setting, so we can say we got 169x faster in time/efficiency for the initial setup. The database constructed with the full block synchronization required 29GB of space, and the initial database constructed with the snapshot synchronization required 2.8MB of space.
In conclusion, we designed a fast and verifiable sync method, called VeriSync. The main idea is splitting a state tree with verifiable chunks. Our VeriSync implementation reduces the initial setup time from 10h 40m to 3m 46s, which is 169 times faster. Also note that these numbers get better as the blockchain’s size grows, so the numbers will be far better than now as time goes on.
For specific implementation details, go to the below GitHub links:
by Joonmo Yang, Seongchan Lee and Park Juhyung
