Title: 《LOCUS CHAIN TECH SERIES 5: Verifiable Pruning Chapter 1.》

Author: LOCUS CHAIN FOUNDATION

Compiled by: ChainCatcher

Utilizing Data Locality: Ledger Sharding and Verifiable Pruning
Sharded Data Locality: Ledger Sharding

In the traditional sense, a blockchain is a single chain of ledgers. Each node must retain all ledger data to verify the integrity of the data, including existing and new data.

However, the holding-all-ledger model does not apply to sharded ledgers. Essentially, each independent shard should have zero knowledge of other shards. Nodes only validate transactions contained within the current shard. Shard consensus only processes transactions issued by accounts within the shard.

This property also means that nodes can safely delete (or "prune") data related to other shards. While communication such as inter-shard transactions will transfer data about other shards to a node, this data is temporary and does not need to be stored locally for the long term.

Ledger sharding effectively reduces the size of local storage for each node, decreasing the number of shards.

Interest-Based Data Locality

The integrity of data (such as transactions and blocks) is checked against the ledger. In practice, verification requires a (very) small portion of the ledger data. For example, each new piece of data is verified only against the most recently validated data on the chain. Older data remains secure in the chain, but once the integrity of the latest data is protected, they are primarily inactive.

This property raises an interesting question: what if we could temporarily delete old data? Locus Chain articulates this issue as the concept of verifiable pruning. Through verifiable pruning, Locus Chain nodes can delete (or prune) most of the uninteresting transactions and blocks from local storage.

Verifiable Pruning

Verifiable pruning is a technique for deleting (pruning) previous data from a local environment over a certain period without affecting the blockchain's data verification capabilities.
If a node deletes a data block and later retrieves it again, the node must also re-verify the data. In the traditional sense of blockchain, verifying a block of data requires all processed blocks on the chain, which demands significant computation.

Locus Chain's verifiable pruning is about effectively verifying data blocks without scanning all previous data blocks. Verifiable Pruning uses a Hierarchical Skewed Merkle Tree (H-SMT), a patented unique data structure that exponentially reduces the overhead of data verification. With verifiable pruning, verifying a data block requires only a small number of previous data blocks, approximately log10(N). The amount of required data is minimal, allowing all necessary blocks to be verified in less than a second.

For example, when a Locus Chain node identifies an uninteresting old transaction, the node can identify a set of other transactions required to verify that transaction. The transaction set may be small enough to be retrieved and verified before the next consensus round.

Verifiable pruning can save ledger storage space. Additionally, verifiable pruning supports the rapid startup of nodes. In Locus Chain, nodes only use a small portion of previous blocks to verify the integrity of the current head. New nodes can participate in sharding within a few rounds of consensus.

Data Ownership and Responsibility

Verifiable pruning can prune uninteresting data. In other words, nodes must not prune data of interest. Typical non-prunable data includes transactions related to the node owner's account and orphaned accounts.

Each node has an owner account. Nodes may have orphaned accounts for unoperated nodes. Nodes must track data related to relevant accounts and provide that data to other nodes when needed.

Pruning is a fundamental operation for all nodes. Particularly, low-capacity nodes such as IoT modules can benefit from pruning. On the other hand, nodes with sufficient storage can contribute as achievement nodes for other nodes.