Search for integrity assurance in blockchain

Search for integrity assurance in blockchain

Glossary

Term DefinitionADS (Authenticated Data Structure)A data structure used to verify the integrity of data stored on an untrusted server.BlockchainA distributed, immutable database maintained by multiple nodes.Smart ContractA computer program deployed on a blockchain that automatically executes the terms of an agreement.Cloud Service Provider (SP)A third-party company that provides cloud computing services, such as Amazon Web Services (AWS) and Google Cloud Platform (GCP).Merkle TreeA tree-like data structure in which each leaf node represents the hash value of a data block, and each non-leaf node represents the hash value of the hash value of its child nodes.Merkle B-Tree (MB Tree)Applies the concept of Merkle Tree to B-Tree to support authentication of hierarchical data.Suppressed Merkle B-Tree (SMB Tree)A modified Merkle B-Tree in which only the root hash value is kept and the internal nodes are calculated when needed. GEM2 Tree (Gas-Efficient Merkle Merge Tree) An ADS optimized for blockchain environments, designed to minimize maintenance costs. GEM2* Tree An optimized version of the GEM2 tree that uses a two-level index structure to further reduce maintenance costs. Verification Object (VO) Proof of query results, allowing clients to verify their correctness. Gas The unit of fee required to execute a transaction or smart contract on the Ethereum blockchain. Data Owner (DO) A party that owns and wants to store or manage data on the blockchain.

Short Answer Question

Briefly describe the blockchain hybrid storage architecture and its advantages.

The blockchain hybrid storage architecture stores small metadata on-chain and stores raw data in off-chain storage services such as cloud storage. The advantage of this architecture is that it can take advantage of both the security of the blockchain and the scalability and cost-effectiveness of off-chain storage.

Why are traditional authentication data structures (such as Merkle B-trees) inefficient in blockchain environments?

Traditional authentication data structures are inefficient in blockchain environments because they require a large number of write operations to maintain the tree structure. Due to the consensus mechanism of blockchain, write operations are very expensive, resulting in high gas costs.

Explain how the Suppressed Merkle B-Tree (SMB Tree) solves the efficiency problem of the traditional Merkle B-Tree.

The SMB Tree solves the efficiency problem by storing only the root hash value and dynamically calculating the internal nodes when needed. This approach reduces the number of write operations, thereby reducing the gas cost.

Describe the basic structure of the GEM2 tree and its components.

The GEM2 tree is an efficient Merkle merge tree that uses multiple SMB trees to store data and manages these trees using a partition index table and a key map. The partition index table stores the location range and root hash value of each SMB tree, while the key map stores the storage location of each search key.

How does the GEM2 tree handle data insertion operations?

The GEM2 tree inserts new data into the smallest SMB tree. When the SMB tree is full, it merges with the adjacent SMB tree into a larger SMB tree, and merges recursively until a predefined threshold is reached.

How does the GEM2 tree handle data update operations?

The GEM2 tree finds the location of the data to be updated through key mapping, and then updates the data and root hash value in the corresponding SMB tree.

How does the client use the GEM2 tree to verify the integrity of the query result?

The client retrieves the verified root hash value (VOchain) from the blockchain and reconstructs the root hash value of the tree using the proof (VOsp) received from the service provider. If the reconstructed root hash value matches the VOchain, the proof result is complete and has not been tampered with.

What are the main advantages of the GEM2 tree compared to the GEM2 tree? *

The GEM2* tree uses a two-level index structure to divide the search space into multiple regions, each corresponding to a GEM2 tree. This approach can further reduce maintenance costs and improve query efficiency.

What are the key principles to consider when designing authentication data structures for blockchains?

When designing authentication data structures for blockchains, the following principles should be considered: avoid maintaining long sorted lists, use more read operations instead of write operations, and adapt to databases of different sizes.

What are the potential application areas?

Suitable for blockchain systems that require data-wide search capabilities, such as supply chain management, healthcare, and the Internet of Things.