Shulou(Shulou.com)06/01 Report--

In this article, the editor introduces in detail the "Libra data structure and storage knowledge points", with detailed content, clear steps and proper handling of details. I hope that this article "what are the Libra data structure and storage knowledge points" can help you solve your doubts.

The validated data structure is implemented through the Merkle tree. If you are familiar with other blockchains, you may know that Merkle trees are used in most blockchains because of their special structure.

Stored data structure

As shown in the following figure, let's explain its stored data structure in detail:

(1) the cumulative account history represented by the Merkle tree. The root hash value of the Merkle tree is obtained by (2) the verifier's signature.

Whenever a transaction is submitted to the ledger, the TransactionInfo is submitted to the leaf node of the Merkle tree.

3 represents and this leaf node, which contains three parts:

Signed transactions (4).

The event Event (5) during the transaction is also represented by the Merkle tree.

There is also the account status (6) after transaction I is executed, which is represented by a Sparse Merkle tree, where its leaf node is account information.

Ledger history

For most blockchains, such as bitcoin, they store transactions and then form a block that contains transactions. The following block contains the hash value of the previous block.

The disadvantage of this is that if I know that a block B1 is accurate, then I want to verify the current block B2, then I must pull all transactions from B1 to B2, which is not efficient for the verification of the blockchain.

This has been improved in Libra. We use a single Merkle tree to provide a validated data structure that represents the history of the account.

As we can see in the figure above, TransactionInfo contains account status, events, and account information. In the Merkle tree, each TransactionInfo corresponds to a database version number I.

In Libra, we use incremental Merkle tree data structures, which are very helpful for building efficiency, because we only need to add new transactions to the old Merkle tree.

For the verification node, the new transaction is only related to the previous account status, so the verification node can actually delete the unneeded version of the account status to save space and efficiency.

Account book status

The account status Si represents the information of all accounts in version I. It can be thought of as a map of key value. Where key is the account address of 256bit, and value is the verified account.

Si is also represented by Merkle tree, and since key is 256bit, the entire Merkle tree can be represented as a 2256-size tree as follows:

It would be a waste of space to use 256 size directly, because we don't have so many accounts. Then we can make appropriate optimizations:

(1) represents the Merkle tree of the original state.

In (2), we represent all empty nodes with boxes. This leads to an imbalance in the tree because the leaf node is always at the lowest level of the tree. Then we can make appropriate optimizations as shown in (3).

When the state tree is updated, the previously unupdated account data can be reused so that multiple versions of the state tree can be stored in the verifier and the verification speed of the verification node can be accelerated.

Account

Logically, an account is a collection of resources and module and is stored in the address of the account.

Physically, the account stores the sorted access paths mapping. Access paths can be thought of as something like a file path.

Unlike other blockchains, in Libra, we encourage users to store resources in their own accounts. In the current version, we optimize small accounts, and in later versions we will also optimize and upgrade large accounts.

If all the resources are stored in the account, then the account information will become larger and larger over time, which will be a problem.

In order to solve this problem, Libra put forward the concept of space lease. To put it simply, the account is given an expiration time, after which the account cannot be accessed. Of course, Libra also provides a recovery mechanism for expired accounts, which only needs to pay a certain amount of Libra currency.

Event

Like accounts, events are stored using Merkle tree and are included in the TransactionInfo.

After reading this, the article "what are the knowledge points of Libra data structure and storage?" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself. If you want to know more about related articles, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.