CN114723444A - A Data Sharding Method for Parallel Voting Consensus - Google Patents

Abstract

The invention is suitable for the technical improvement field of block chains, and provides a data fragmentation method for parallel voting consensus, wherein an erasure code is used for carrying out a batch segmentation method of a block group, each node only stores one small fragment of original data, and the original data can be recovered at any time point; the fragments are interactively started at each node according to the storage cumulant, the fragments can be started in a plurality of groups of data in parallel, and the safety of the system at the time point of starting the fragments can be ensured; and realizing block group caching according to cold and hot data division and realizing search optimization of transactions by utilizing a bloom filter. The blockchain node can only store one fragment of the original data, and the fragment occupies the original data at least in a proportion equal to the number of normal nodes in the system setting.

Description

A Data Sharding Method for Parallel Voting Consensus

technical field

The invention belongs to the field of block chain technology improvement, and in particular relates to a data fragmentation method for parallel voting consensus.

Background technique

With the technological revolution and industrial transformation in the global information technology field, the Internet has gradually developed from the "information Internet" to the "value Internet". In the era of "Information Internet", the information on the Internet is open and transparent, but it is also untrustworthy because it can be tampered with at will, requiring a third-party organization to provide trust guarantees. Once the third-party platform that provides trust collapses, the trust provided by it will become a bubble. In order to solve the trust problem arising from the development of the Internet, blockchain technology came into being.

Blockchain technology is an integrated application mode of distributed data storage system, point-to-point transmission, consensus mechanism, encryption algorithm and other technologies, which can realize trust and value transfer on the Internet that cannot be achieved by traditional Internet. It is based on the principle of cryptography rather than the characteristics of credit, so that any two parties who reach an agreement can directly trade without the participation of a third-party intermediary. On the other hand, there is almost no single point of failure in the blockchain, and the data on the chain is stored on countless machine nodes around the world, making the data "stable", "trustworthy" and "immutable", which re-empowers the network data a value that can be trusted.

Each node of the blockchain stores a copy of the complete blockchain locally, so nodes can independently complete transactions such as transaction lookup and account balance calculation. However, as the amount of data contained in the virtual currency blockchain continues to increase, the size of the blockchain continues to increase. For example, as of December 2019, the virtual currency blockchain occupies about 260GB of storage space. The excessive size of the virtual currency blockchain has evolved into a scalability problem, resulting in an increase in the synchronization time of blank nodes. At the same time, the heavy storage burden increases the cost of maintaining a full node.

This scheme designs an interactive block group sharding scheme for parallel voting consensus, and uses erasure codes to ensure that complete data can be recovered at any time. It ensures fast transaction location and fast query of block group data.

In 2008, Nakamoto proposed virtual currency. In the virtual currency blockchain system, users can upload their own transactions. The essence of the transaction is to transfer the virtual currency in one account to another account. A transaction may have multiple inputs and multiple outputs. Legal transactions are packaged into blocks with a maximum size of 1MB. A block consists of a block header and a block body. The block header mainly includes the hash value pointing to the previous block, the root value of the transaction Merkle tree, a timestamp and a random number, etc. The block body mainly includes the generated transaction. .

The virtual currency includes both full nodes and light nodes. Light nodes are also called SPV (Simplified Payment Verification) nodes. They do not store blockchain transaction data, but only have a wallet function, which can reduce storage pressure. The full node stores all block data, which can be used to verify transactions, provide data for other nodes, and have complete node functions. For devices with less storage resources, the virtual currency white paper introduces that the SPV node only downloads the block header during the initialization synchronization process, and then requests data from the full node according to its own needs. The storage size required for such a node is only linearly related to the block height, independent of the block size. Each block header is 80B, and the space is only 4.2MB a year, which greatly reduces the storage pressure.

The main advantages of virtual currency light nodes are that, first, the storage space of nodes is greatly reduced, making it possible for clients with weak storage capabilities to join the network; second, light nodes rely on full nodes and can make payments quickly and accurately For verification, there is no need to download all payment data.

The above-mentioned light node scheme also has certain defects. First of all, as the amount of data increases, the number of light nodes increases, the number of full nodes decreases, the degree of decentralization of the blockchain system is weakened, and the security and stability of data decreases; light nodes reduce data storage, but increase the size of the network. Bandwidth pressure, does not contribute to the system in terms of data storage and data sharing.

Payment Channels is a two-layer structure running on the virtual currency network, allowing both parties involved to directly establish peer-to-peer payment channels between each other. Participants can securely maintain and update each other's private ledger so that their transactions within the channel do not need to be written to the blockchain. It should be pointed out that during the transaction process, the intermediate state of the payment channel can also be written into the virtual currency ledger at any time. The payment channel avoids transacting directly on the virtual currency, so it can significantly increase capacity, scalability, transaction throughput. The transaction processing rate within the channel is only limited by the network bandwidth of the participants, regardless of the congestion of the virtual currency network. Another advantage of payment channels is that they do not require direct services from virtual currency miners, so they can be performed with extremely low transaction fees, and micropayments between virtual currency users can be performed economically.

Lightning Network, first proposed by Joseph Poon and Thaddeus Dryja, is currently the most promising and influential payment channel. The Lightning Network allows participating users to perform virtual currency off-chain payments, relying on punishment mechanisms to promote honest behavior of users. If a node broadcasts a malicious transaction, then honest participants can legally claim all funds within the relevant Lightning Network, which strongly guarantees that multiple parties can conduct transactions in a fair and just manner.

The main advantages of this method are that, firstly, it greatly reduces the node storage space caused by small transactions; secondly, it speeds up the processing speed of virtual currency and prevents small transactions from slowing down the overall performance.

The above scheme also has certain drawbacks. First of all, this scheme relies on the trustworthiness of both parties, otherwise assets may be lost, so it is only suitable for small-value transactions; at the same time, this scheme is only suitable for transfer of one type of transaction, which is not universal, and does not fundamentally Reduce the amount of data storage on the node.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a data sharding method for parallel voting consensus, which aims to solve the core technical problem of how to perform block data compression to improve the scalability of the stage system without affecting the data security.

The present invention is implemented as follows: a data sharding method for parallel voting consensus, the data sharding method for parallel voting consensus includes the following steps:

S1. The master node of the current cycle is responsible for monitoring the volume of the block group after the last fragmentation;

S2. Determine whether the volume of the monitored block body is greater than the storage factor M. When the volume sum is greater than M, initiate a <split,l,r,signature> transaction to the network, and when the volume sum is less than M, continue to execute S2;

S3. After node i receives the split transaction, it needs to wait to obtain all block groups in the range from l to r;

并广播一条交易

S4. The node independently obtains the corresponding fragment code

and broadcast a transaction

S5. After the n nodes in the system have clearly responded, the nodes can independently delete the block groups in the range from l to r and keep only

Among them, l is the serial number of the block group at the beginning of this fragmentation, and r is the serial number of the block group at the end of this fragmentation.

的哈希值是确保每个节点都拥有数据片的摘要信息，以用于获取数据片时进行正确性验证。A further technical solution of the present invention is: in the step S4, calculating

The hash value is to ensure that each node has the summary information of the data piece, which is used for correctness verification when obtaining the data piece.

即可获取到需要的数据。A further technical solution of the present invention is: after data fragmentation is saved, when node i needs to restore the block group data with height h, it broadcasts a query request <query,h,i,signature> to the whole network, and is still alive After receiving the request, the node in the state will reply to the corresponding shard, and node i will execute it after collecting any n-2f-1 blocks.

The required data can be obtained.

A further technical solution of the present invention is that: a node needs to save the digest of each fragment when calculating fragments, and compares the digests when obtaining fragments of other nodes.

A further technical solution of the present invention is: data query after fragmentation divides the block group into three state intervals of hot, warm and cold according to the time line, and uses different caching strategies in each state interval.

A further technical solution of the present invention is: the latest block group set stored in the hot state interval is frequently queried, and should be stored on each node, so as to reduce the cost of large-scale data slice acquisition. The network bandwidth and processing pressure define the length of the Hot state interval as L _h , the height of the latest block is h _max , and the block group whose height is (h _max -L _h , h _max ] is located in this state interval.

A further technical solution of the present invention is that: the Warm state interval saves newer block groups, and the block group request used for the correctness check of the block group is not used frequently, and the block group does not need to be saved On each node, it is only stored on n _w nodes, where (1 <= n _w <= 2f+1); when n _w nodes are all down, block group query uses RSCode for batch recovery ; Define the length of the Warm space as L _w , and the block group whose height is (h _max -L _h -L _w , h _max -L _h ] is located in the state interval.

A further technical solution of the present invention is: use a Bloom filter at the node to record the transaction existence information of each block group, quickly locate the block group information at the exchange during transaction query, and the length of the Bloom filter increases Reduce the false positive rate.

A further technical solution of the present invention is: the Cold state interval saves very old block groups and the probability of being queried is very low, and will be frequently accessed when a new node joins the network; the Cold state interval merges multiple block group shards into a One block and recalculating the block hash reduces the storage space for the digest generated by the block group fragmentation, and the block group with a height of [0,h _max -L _h -L _w ] is located in this state interval.

A further technical solution of the present invention is: when a new node just joins the network and needs to acquire all block groups in full, the hash amount of the shards to be verified by the new node will be reduced.

The beneficial effect of the present invention is that the blockchain node can only store one fragment of the original data, and the fragment only accounts for at least the proportion of the original data equal to the number of normal nodes in the system. At the same time, the new and old block groups are divided into time lines and different caching strategies are adopted in exchange for fast query of block groups and transactions.

Description of drawings

FIG. 1 is a flowchart of a data sharding method for parallel voting consensus provided by an embodiment of the present invention.

FIG. 2 is a schematic diagram of a working process of block group sharding provided by an embodiment of the present invention, taking a scenario of four nodes with one malicious node as an example.

FIG. 3 is a schematic diagram of a cache model based on a timeline provided by an embodiment of the present invention.

Detailed ways

As shown in Figure 1, the data fragmentation method for parallel voting consensus provided by the present invention is described in detail as follows:

In the blockchain network, each node of the blockchain stores a complete copy of the entire blockchain locally, so the nodes can independently perform block verification, transaction query and other behaviors. However, the blockchain is the ledger data that is continuously increasing and cannot be deleted, which poses a great challenge to the storage capacity of nodes. For example, as of December 2019, the virtual currency blockchain accounted for about 260GB. How to compress block data without compromising security is the core issue to improve the scalability of the stage system.

The present invention provides a method for parallel voting consensus data sharding, and proposes a batch segmentation method of block grouping by using erasure codes in a parallel voting consensus network, each node only stores a small shard of the original data, And it can ensure that the original data can be recovered at any point in time; the sharding process of block group data is proposed, and the sharding can be started interactively at each node according to the storage accumulation, and the sharding can be started in parallel in multiple groups of data. At the same time, it can ensure that the system is safe at the time of starting the sharding. Different caching strategies of hot and cold data combined with Bloom filter are proposed to realize the search optimization of block groups and transactions.

Data Fragmentation Based on Erasure Code

Erasure codes do not require all shards to recover all the original data. This feature is very suitable for Byzantine environments with malicious and faulty nodes. Usually the access query frequency of the block group generated in the early stage is extremely low, but each node still needs to store the full amount of block group transaction data. The storage scheme combined with erasure codes allows nodes to store only one shard of the transaction set, and can restore the complete block group transaction information in real time when needed.

The Reed-Solomon erasure code can be represented by a <k,m> two-tuple, the original data M is divided into k data blocks, and the matrix operation is used to generate m check blocks. For any d blocks, the original data can be recovered when d∈k∪m&d≥k. Therefore, the RS Code can guarantee the security of the original data when at most m blocks are lost or temporarily unavailable.

For a parallel voting consensus network with f malicious nodes, at most 2f nodes will not respond in the system. Assuming that there are n nodes in the system, and there are at least n-2f active nodes at any time, in order to ensure that the original data can be recovered at any time, the system should use the (n-2f, 2f) configuration of RS coding.

其中包括n-2f个数据块

以及 2f个检验块

每个记账节点只存储一个块，并当必要的时候请求其他任意2f-1块即可恢复区块组体本身，这样每个节点理论上只需要保存原始数据的1/n-2f，也即系统理论下正常节点的数量。Considering that the metadata in the block group header is frequently accessed, this algorithm only shards the block group BGB that stores the transaction, and BGB _j represents the block group with height j. For any block group, RS code encoding generates a total of n blocks

which includes n-2f blocks of data

and 2f check blocks

Each accounting node only stores one block, and when necessary, requests any other 2f-1 block to restore the block group itself, so that each node theoretically only needs to save 1/n-2f of the original data, and also That is, the number of normal nodes under the system theory.

This scheme uses transactions for interactive sharding. It is expensive to generate a shard transaction for each block. Instead, sharding is performed regularly. Before encoding, each block group needs to be divided into n-2f parts in equal proportions, and each data block is a collection of all block groups in the same position.

定义Split(l,r,i)表示对从l到r的区块组体进行RS编码，并保留记账节点i对应的块

表示使用任意n-2f个分片恢复出l-r范围内的区块组体。In order to make the correspondence between shards and nodes as random as possible, the sequence number of shards stored by accounting node i

Defining Split(l,r,i) means performing RS encoding on the block group from l to r, and retaining the block corresponding to the accounting node i

Indicates that a block group within the range of lr is recovered using any n-2f shards.

Data sharding process

In this scheme, the sharding scheme is driven by transactions. There is a storage factor M in the system. When the sum of the volume of the block groups in a certain range is greater than M, the system will start the sharding of these block groups. The existence of the storage factor avoids frequent sharding, resulting in excessive computational pressure on nodes.

The master node of the current cycle is responsible for monitoring the volume of the block group after the last fragmentation, and when the sum of the volume is greater than M, initiates a <split,l,r,signature> transaction to the network, where l is the current fragmentation The starting block group sequence number, and r is the block group sequence number at the end of this sharding. The current master node may be malicious and deliberately does not initiate sharding, because the malicious node has an upper limit f, and the system will start this sharding after at most f consensus cycles. The sharding is started in parallel, and the master node can start this sharding without waiting for the end of the previous sharding.

并广播一条交易

计算

的哈希值的目的是保证所有节点确实收到了对应的区块组并进行了相同的分片。当系统中的所有n个节点都明确进行了回复后，节点可以独立的将l到r范围内的区块组体删除并只保留

After node i receives the split transaction, it needs to wait to obtain all block groups in the range from l to r. After that, the node independently obtains the corresponding fragment code

and broadcast a transaction

calculate

The purpose of the hash value is to ensure that all nodes have indeed received the corresponding block group and performed the same sharding. When all n nodes in the system have responded explicitly, the nodes can independently delete the block groups in the range from l to r and keep only

This scheme uses a strong synchronization assumption, and f nodes that are down in the system will eventually start at a certain time and acquire all block groups and execute sharding. Otherwise, it is assumed that the currently surviving 2f+1 nodes in the system have performed sharding calculations and deleted the corresponding block group, then the f downtime nodes are restored and the f normal nodes in the previous 2f+1 are down. At this time, as long as the remaining f malicious nodes remain silent, only f nodes have the block data of the block group, so that the previous block group cannot be recovered. We think this strong synchronization assumption is reasonable, because the nodes will eventually be valid and the nodes do not need to be online at the same time, and the shards are started in parallel, which can quickly compensate for the time difference caused by node downtime.

When node i needs to restore the block group data of height h, it broadcasts a message to the whole network

即可获取到需要的数据。考虑到节点有可能是恶意的因此它发送的分片有可能是被修改的，节点在计算分片时任需要保存每个分片的摘要，并当获取到其他节点的分片时进行摘要比较。<query,h,i,signature> query request, the node in the surviving state will reply to the corresponding fragment after receiving the request, node i will execute it after collecting any n-2f-1 blocks

The required data can be obtained. Considering that the node may be malicious, the shards it sends may be modified, the node needs to save the digest of each shard when calculating shards, and compare the digests when obtaining shards of other nodes. .

Data query optimization

While the design of sharding optimizes storage, it leads to the problem of low query efficiency. If the system needs to use the RS code to restore data every time it is queried, it will have a great impact on the query performance. This scheme uses a timeline to divide the block group into three state intervals: hot, warm, and cold, and uses different caching strategies respectively.

In a blockchain network, query requests usually include block group queries and transaction queries. Block group query refers to querying the corresponding block group (including block group header and block group body) information by specifying a height. Transaction query refers to querying all the information of the corresponding transaction by specifying the transaction hash. Transaction queries usually use the indexing mechanism provided by databases (such as MongoDB and LevelDB) to quickly find corresponding transactions. The sharding mechanism requires additional mechanisms to quickly determine where transactions correspond.

According to the principle of locality of program access, the newer block groups have a higher probability of being accessed, so they should appear on every node, while the older block groups are accessed very infrequently, only when needed data can be restored.

The hot space saves the latest block group set, and block group queries and transaction queries are high-frequency within this range. So whether blockgroups are sharded or not, they should be cached on every node. The length of the Hot space is defined as L _h , and the height of the latest block is h _max , then the block group whose height is (h _max -L _h , h _max ] is located in this space.

Newer block groups are stored in the Warm space. This space is more for block group requests for correctness verification of the block group. The transactions in the block group are relatively expired, so they are The frequency used is not high. The block group does not have to be stored on each node, but only needs to be stored on n nodes, where (1<= _nw <=2f+1). When n _w nodes are all down, block group query uses RS Code for batch recovery. The length of the Warm space is defined as L _w , then the block group whose height is (h _max -L _h -L _w ,h _max -L _h ] is located in this space.

After the transaction is fragmented, it is necessary to quickly locate the block group it is in. First, the node uses the Bloom filter to record the transaction existence information of each block group. When the transaction is queried, it can quickly locate the block where the transaction is likely to be located. group information. Considering the false positive problem of the Bloom filter, appropriately increasing the length of the Bloom filter can reduce the false positive rate.

Cold space saves very old block groups, the probability of transaction query and block query is very low, but these data will be frequently accessed when new nodes join the network. Cold space merges multiple block group shards into a single block and recalculates the block hash. This reduces the storage space for digests produced by block group shards. When a new node has just joined the network and needs to obtain all block groups in full, the amount of shard hashes that the new node needs to verify will also decrease. Block groups with heights in [0,h _max -L _h -L _w ] are located in this space.

At this time, the Bloom filter records the transaction existence information of each shard, reducing the number of comparisons of the Bloom filter during transaction query, so as to realize the rapid positioning of transactions. At the same time, each shard will be randomly and redundantly saved to n _c nodes, n _c can be a relatively small value that can be equal to 0, and the data will be recovered using the check block when n _c caches are invalid.

The technical solution of the present invention can make the blockchain node only store one fragment of the original data, and the fragment only accounts for at least the proportion of the original data equal to the number of normal nodes in the system setting. At the same time, the new and old block groups are divided into time lines and different caching strategies are adopted in exchange for fast query of block groups and transactions.

This scheme proposes a batch segmentation method of block groups using erasure codes in a parallel voting consensus network, and stores each transaction in a group of blocks in only one node, and each node only stores a small portion of the original data. Fragmentation, and can guarantee that the original data can be recovered at any point in time.

This scheme proposes the sharding process of block group data, interactively starts sharding at each node according to the storage accumulation, and can start sharding in multiple groups of data in parallel, and can ensure that the system starts sharding at the same time. point is safe.

This scheme proposes a hot and cold number caching strategy combined with Bloom filters to optimize the search and optimization of block groups and transactions under sharding.

The above descriptions are only preferred embodiments of the present invention and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention shall be included in the protection of the present invention. within the range.

Claims (10)

1. A data fragmentation method for parallel voting consensus, characterized in that the data fragmentation method for parallel voting consensus comprises the following steps: S1. The master node of the current cycle is responsible for monitoring the volume of the block group after the last fragmentation; S2. Determine whether the volume of the monitored block body is greater than the storage factor M. When the volume sum is greater than M, initiate a <split,l,r,signature> transaction to the network, and when the volume sum is less than M, continue to execute S2; S3. After node i receives the split transaction, it needs to wait to obtain all block groups in the range from l to r; S4. The node independently obtains the corresponding fragment code

and broadcast a transaction

S5. After the n nodes in the system have clearly responded, the nodes can independently delete the block groups in the range from l to r and keep only

Among them, l is the serial number of the block group at the beginning of this fragmentation, and r is the serial number of the block group at the end of this fragmentation. 2. The data sharding method for parallel voting consensus according to claim 1, wherein in the step S4, calculating

The hash value is to ensure that each node has the summary information of the data piece, which is used for correctness verification when obtaining the data piece. 3. The data fragmentation method for parallel voting consensus according to claim 2, characterized in that, after the data fragmentation is saved, when node i needs to restore the block group data of height h, it sends the data to the whole network. Broadcast a <query,h,i,signature> query request, the node in the surviving state will reply to the corresponding fragment after receiving the request, and node i will execute it after collecting any n-2f-1 blocks

The required data can be obtained. 4. The data sharding method for parallel voting consensus according to claim 3, wherein the node needs to save the abstract of each shard when calculating shards, and performs the sharding when obtaining the shards of other nodes. Abstract comparison. 5. The data sharding method for parallel voting consensus according to claim 4, wherein the data query after sharding divides the block group into three state intervals: hot, warm, and cold according to the time line. Each state interval uses different caching strategies. 6. The data sharding method for parallel voting consensus according to claim 5, characterized in that, the latest block group set saved in the hot state interval is frequently queried and should be saved in the hot state interval. On each node, in order to reduce the network bandwidth and processing pressure when obtaining large-scale data slices, the length of the Hot state interval is defined as L _h , the height of the latest block is h _max , and the height is (h _max -L _h , The block group of h _max ] is located in this state interval. 7. The data sharding method for parallel voting consensus according to claim 6, characterized in that, what is stored in the Warm state interval is a newer block group, an area used for the correctness check of the block group Block group requests are not frequently used. Block groups do not have to be stored on every node, but only on n _w nodes, where (1<=n _w <=2f+1); when n _w nodes When both are in the down state, the block group query uses RS Code for batch recovery; the length of the Warm space is defined as L _w , and the block group whose height is (h _max -L _h -L _w ,h _max -L _h ) is located at within this state. 8. The data sharding method for parallel voting consensus according to claim 7, wherein the node uses a Bloom filter to record the transaction existence information of each block group, and quickly locates the transaction during transaction query. The information of the block group in which the Bloom filter length is increased reduces the false positive rate. 9. The data sharding method for parallel voting consensus according to claim 8, characterized in that, the Cold state interval saves very old block groups and the probability of being queried is very low, and only when a new node joins the network will it meet. Frequently accessed; the Cold state interval merges multiple block group shards into one block and recalculates the block hash to reduce the storage space of block group shards to generate digests, and the height is in [0,h _max -L _h -L _w ] is within this state interval. 10. The data sharding method for parallel voting consensus according to claim 9, characterized in that when a new node just joins the network and needs to acquire all block groups in full, the shard hash that the new node needs to verify amount will decrease.

Images