Plasma Cash blockchain status data structures
Hello, dear users! This article is about web 3.0 - the Internet with decentralization. Web 3.0 introduces the concept of decentralization as the basis for the modern Internet, many computer systems and networks need security features and decentralization for their needs. The decentralization solution is called distributed registry or blockchain technology.
Blockchain is a distributed registry. It can be considered as a huge database that lives forever and does not change in history, the blockchain is used as a basis for decentralized web applications or services.
In fact, the blockchain is not only a database, it is an opportunity to increase trust between network members with the ability to execute business logic on the network.
')
Byzantine consensus increases network reliability solves the problem of consistency
The scalability that DLT introduces is changing existing business networks.
Blockchain offers new very important benefits:
Opporty PoE is a project whose goal is to research cryptographic protocols and improve existing DLT and blockchain solutions.
Most public distributed registry systems do not have scalability properties — their throughput is rather low. For example, ethereum processes only ~ 20 tx / s.
Many solutions were created to increase the scalability property and not to lose decentralization (as you know, only 2 out of 3 can be: scalability, security, decentralization).
One of the most effective is a sidechain solution.
The concept is that the root chain handles a small number of commits from child chains, so that the root chain acts as the most secure and final layer for storing all intermediate states. Each subsidiary chain functions as its blockchain with its own consensus algorithm, but there are several important caveats.
Validators have economic incentives to act honestly, and send commitments to the root chain - the final settlement transaction layer.
As a result, dapp users working in the child chain should not interact with the root chain at all. In addition, they can put their money in the root chain whenever they want, even if the child chain is hacked. These exits from the child chain allow users to securely store their funds with Merkle proofs confirming ownership of a certain amount of funds.
The main advantages of a plasma are related to its ability to significantly ease the calculations that currently overload the main chain. In addition, the Ethereum blockchain can handle more extensive and more parallel data sets. The time that is removed from the root chain is also transferred to Ethereum nodes, which receive lower processing and storage requirements.
Plasma Cash is a design that gives online tokens unique serial numbers that turn them into unique tokens. The advantages of this include no need for confirmations, simpler support for all types of tokens (including Non-fungible tokens), and mitigation against mass exits from the child chain.
The plasma problem is related to the concept of “mass exits” from the child chain. In this scenario, coordinated withdrawal from a child chain at the same time could potentially lead to a lack of computing power to withdraw all funds. As a result, users may lose funds.
Basic plasma has a lot of options for implementation.
The main differences are:
The main variations of plasma:
The purpose of this article is to explain the data structures used in the Plasma Cash blockchain.
In order to understand exactly how commitments work, it is necessary to clarify the concept of the Merkle tree.
Merkle trees are an extremely important data structure in the blockchain world. In essence, Merkle trees give us the ability to capture a certain set of data in a way that hides the data, but allows users to prove that some of the information was in the set. For example, if I have ten numbers, I can create proof for these numbers, and then prove that one particular number was in this set of numbers. This proof has a small constant size, which makes it cheap to publish in Ethereum.
You can use this for a set of transactions. You can also prove that a particular transaction is in this transaction set. This is exactly what the operator is doing. Each block consists of a set of transactions that turn into a Merkle tree. The root of this tree is proof, which is published in Ethereum along with each plasma block.
Users should be able to withdraw their funds from the plasma chain. When users want to exit the plasma chain, they send an “exit” transaction to Ethereum.
Plasma Cash use special Merkle Tree which makes it possible not to validate the whole block, but to validate only those branches that correspond to the user's token.
That is, to transfer a token, you need to go through the history and scan only those tokens that are needed by a certain user, when transferring a token, the user simply transfers the entire history to another user and he can already authenticate the entire history - and most importantly do it very quickly.
Nevertheless, it is necessary to use only some merkla trees, because it is necessary to obtain proof of inclusion as well as evidence of non-inclusion of the transaction in the block, for example -
Opporty has implemented its Sparse Merkle Tree and Patricia Trie implementations.
A sparse Merkle tree is similar to a standard Merkle tree, except that the data it contains is indexed and each data point is placed on a sheet that corresponds to the index of this data point.
Suppose we have a four-leaf merkle tree. We will fill this tree with several letters (A, D) for demonstration. The letter A is the first letter of the alphabet, so we must put it on the first sheet. Similarly, we can put D on the fourth sheet.
So what happens in the second and third leaves? We just leave them empty. More precisely, a special value is placed (for example, zero) instead of placing a letter.
The tree eventually looks like this:
The proof of inclusion works in the same way as in a normal merkle tree. What happens if we want to prove that C is not part of this Merkle tree? It's simple! We know that if C were part of a tree, it would be on the third sheet. If C is not part of the tree, then the third sheet must be zero.
All that is needed is the standard proof of Merkle's inclusion, showing that the third sheet is zero.
The best part of the sparse Merkle tree is that they really represent the keysto-value repositories inside the Merkle tree!
Here is part of the PoE protocol code that implements the construction of the Sparse Merkle Tree
This code is quite trivial. We have a key-value repository with proof of inclusion / non-inclusion.
In each iteration, a specific level of the final tree is filled, starting with the most recent one. Depending on which key of the current sheet is even or odd, we take two adjacent sheets and count the hash of the current level. If we reach the end, we write a single merkleRoot - a common hash.
You must understand that this tree is already filled with initially empty values! And if we store a huge amount of IDS token. we have a huge tree size and it is generated for a very long time!
There are many solutions to this non-optimization, but Opporty decided to change this tree to Patricia Trie.
Patricia Trie is a connection from Radix Trie and Merkle Trie.
Radix Trie data key will store the data path itself! This allows you to create an optimized data structure for the memory!
That is, we go through recursively and build separate left and right subtrees. At the same time building the key as the path in this tree!
This solution is even more trivial and works faster while being quite optimized! In fact, the Patricia tree should still be more optimized by introducing new node types — extension node, branch node, and so on, as done in the ethereum protocol, but this implementation satisfies all of our conditions — we got a fast and memory-optimized data structure.
By implementing these data structures, Opporty made Plasma Cash scaling possible as it allows you to check the history of the token and enable the non-inclusion of the token in the tree! That allows you to greatly accelerate the validation of the blocks and the Plasma Child Chain itself.
Blockchain is a distributed registry. It can be considered as a huge database that lives forever and does not change in history, the blockchain is used as a basis for decentralized web applications or services.
In fact, the blockchain is not only a database, it is an opportunity to increase trust between network members with the ability to execute business logic on the network.
')
Byzantine consensus increases network reliability solves the problem of consistency
The scalability that DLT introduces is changing existing business networks.
Blockchain offers new very important benefits:
- Prevent costly mistakes.
- Transparent transactions.
- Digitization for real goods.
- Smart contracts.
- Speed ​​and security of payments.
Opporty PoE is a project whose goal is to research cryptographic protocols and improve existing DLT and blockchain solutions.
Most public distributed registry systems do not have scalability properties — their throughput is rather low. For example, ethereum processes only ~ 20 tx / s.
Many solutions were created to increase the scalability property and not to lose decentralization (as you know, only 2 out of 3 can be: scalability, security, decentralization).
One of the most effective is a sidechain solution.
Plasma concept
The concept is that the root chain handles a small number of commits from child chains, so that the root chain acts as the most secure and final layer for storing all intermediate states. Each subsidiary chain functions as its blockchain with its own consensus algorithm, but there are several important caveats.
- Smart contracts are created in the root chain and act as a checkpoint of the child chain in the root chain.
- A subsidiary chain is created, which functions as its own blockchain with its own consensus. All states in the chain of child processes are protected by fraud proofs, which ensure that all state transitions are valid and apply a withdrawal protocol.
- Smart contracts specific to the dapp or child chain (application logic) can then be deployed in the child chain.
- The necessary funds can be transferred from the root chain to the child chain.
Validators have economic incentives to act honestly, and send commitments to the root chain - the final settlement transaction layer.
As a result, dapp users working in the child chain should not interact with the root chain at all. In addition, they can put their money in the root chain whenever they want, even if the child chain is hacked. These exits from the child chain allow users to securely store their funds with Merkle proofs confirming ownership of a certain amount of funds.
The main advantages of a plasma are related to its ability to significantly ease the calculations that currently overload the main chain. In addition, the Ethereum blockchain can handle more extensive and more parallel data sets. The time that is removed from the root chain is also transferred to Ethereum nodes, which receive lower processing and storage requirements.
Plasma Cash is a design that gives online tokens unique serial numbers that turn them into unique tokens. The advantages of this include no need for confirmations, simpler support for all types of tokens (including Non-fungible tokens), and mitigation against mass exits from the child chain.
The plasma problem is related to the concept of “mass exits” from the child chain. In this scenario, coordinated withdrawal from a child chain at the same time could potentially lead to a lack of computing power to withdraw all funds. As a result, users may lose funds.
Plasma Implementation Options
Basic plasma has a lot of options for implementation.
The main differences are:
- storing information about the method of storage and presentation of the state,
- types of tokens (divisible indivisible),
- transaction security
- type of consensus algorithm, etc.
The main variations of plasma:
- UTXO based - each transaction consists of inputs and outputs: a transaction can be performed and spent, the list of transactions not spent is the state of the child chain itself.
- Account based - simply contains a reflection of each account-account and its balance, this type is used in ethereum, since each account can be of two types - a user account and a smart contract account. The advantage of this type of state storage is its simplicity, and the minus is that this option is not scalable (the special nonce property is used so that the transaction is not performed twice).
The purpose of this article is to explain the data structures used in the Plasma Cash blockchain.
In order to understand exactly how commitments work, it is necessary to clarify the concept of the Merkle tree.
Merkle Trees their use in Plasma
Merkle trees are an extremely important data structure in the blockchain world. In essence, Merkle trees give us the ability to capture a certain set of data in a way that hides the data, but allows users to prove that some of the information was in the set. For example, if I have ten numbers, I can create proof for these numbers, and then prove that one particular number was in this set of numbers. This proof has a small constant size, which makes it cheap to publish in Ethereum.
You can use this for a set of transactions. You can also prove that a particular transaction is in this transaction set. This is exactly what the operator is doing. Each block consists of a set of transactions that turn into a Merkle tree. The root of this tree is proof, which is published in Ethereum along with each plasma block.
Users should be able to withdraw their funds from the plasma chain. When users want to exit the plasma chain, they send an “exit” transaction to Ethereum.
Plasma Cash use special Merkle Tree which makes it possible not to validate the whole block, but to validate only those branches that correspond to the user's token.
That is, to transfer a token, you need to go through the history and scan only those tokens that are needed by a certain user, when transferring a token, the user simply transfers the entire history to another user and he can already authenticate the entire history - and most importantly do it very quickly.
Plasma Cash data structures for state and history storage
Nevertheless, it is necessary to use only some merkla trees, because it is necessary to obtain proof of inclusion as well as evidence of non-inclusion of the transaction in the block, for example -
- Sparse merkle tree
- Patricia trie
Opporty has implemented its Sparse Merkle Tree and Patricia Trie implementations.
A sparse Merkle tree is similar to a standard Merkle tree, except that the data it contains is indexed and each data point is placed on a sheet that corresponds to the index of this data point.
Suppose we have a four-leaf merkle tree. We will fill this tree with several letters (A, D) for demonstration. The letter A is the first letter of the alphabet, so we must put it on the first sheet. Similarly, we can put D on the fourth sheet.
So what happens in the second and third leaves? We just leave them empty. More precisely, a special value is placed (for example, zero) instead of placing a letter.
The tree eventually looks like this:
The proof of inclusion works in the same way as in a normal merkle tree. What happens if we want to prove that C is not part of this Merkle tree? It's simple! We know that if C were part of a tree, it would be on the third sheet. If C is not part of the tree, then the third sheet must be zero.
All that is needed is the standard proof of Merkle's inclusion, showing that the third sheet is zero.
The best part of the sparse Merkle tree is that they really represent the keysto-value repositories inside the Merkle tree!
Here is part of the PoE protocol code that implements the construction of the Sparse Merkle Tree
class SparseTree { //... buildTree() { if (Object.keys(this.leaves).length > 0) { this.levels = [] this.levels.unshift(this.leaves) for (let level = 0; level < this.depth; level++) { let currentLevel = this.levels[0] let nextLevel = {} Object.keys(currentLevel).forEach((leafKey) => { let leafHash = currentLevel[leafKey] let isEvenLeaf = this.isEvenLeaf(leafKey) let parentLeafKey = leafKey.slice(0, -1) let neighborLeafKey = parentLeafKey + (isEvenLeaf ? '1' : '0') let neighborLeafHash = currentLevel[neighborLeafKey] if (!neighborLeafHash) { neighborLeafHash = this.defaultHashes[level] } if (!nextLevel[parentLeafKey]) { let parentLeafHash = isEvenLeaf ? ethUtil.sha3(Buffer.concat([leafHash, neighborLeafHash])) : ethUtil.sha3(Buffer.concat([neighborLeafHash, leafHash])) if (level == this.depth - 1) { nextLevel['merkleRoot'] = parentLeafHash } else { nextLevel[parentLeafKey] = parentLeafHash } } }) this.levels.unshift(nextLevel) } } } } This code is quite trivial. We have a key-value repository with proof of inclusion / non-inclusion.
In each iteration, a specific level of the final tree is filled, starting with the most recent one. Depending on which key of the current sheet is even or odd, we take two adjacent sheets and count the hash of the current level. If we reach the end, we write a single merkleRoot - a common hash.
You must understand that this tree is already filled with initially empty values! And if we store a huge amount of IDS token. we have a huge tree size and it is generated for a very long time!
There are many solutions to this non-optimization, but Opporty decided to change this tree to Patricia Trie.
Patricia Trie is a connection from Radix Trie and Merkle Trie.
Radix Trie data key will store the data path itself! This allows you to create an optimized data structure for the memory!
Opporty implementation
buildNode(childNodes, key = '', level = 0) { let node = {key} this.iterations++ if (childNodes.length == 1) { let nodeKey = level == 0 ? childNodes[0].key : childNodes[0].key.slice(level - 1) node.key = nodeKey let nodeHashes = Buffer.concat([Buffer.from(ethUtil.sha3(nodeKey)), childNodes[0].hash]) node.hash = ethUtil.sha3(nodeHashes) return node } let leftChilds = [] let rightChilds = [] childNodes.forEach((node) => { if (node.key[level] == '1') { rightChilds.push(node) } else { leftChilds.push(node) } }) if (leftChilds.length && rightChilds.length) { node.leftChild = this.buildNode(leftChilds, '0', level + 1) node.rightChild = this.buildNode(rightChilds, '1', level + 1) let nodeHashes = Buffer.concat([Buffer.from(ethUtil.sha3(node.key)), node.leftChild.hash, node.rightChild.hash]) node.hash = ethUtil.sha3(nodeHashes) } else if (leftChilds.length && !rightChilds.length) { node = this.buildNode(leftChilds, key + '0', level + 1) } else if (!leftChilds.length && rightChilds.length) { node = this.buildNode(rightChilds, key + '1', level + 1) } else if (!leftChilds.length && !rightChilds.length) { throw new Error('invalid tree') } return node } That is, we go through recursively and build separate left and right subtrees. At the same time building the key as the path in this tree!
This solution is even more trivial and works faster while being quite optimized! In fact, the Patricia tree should still be more optimized by introducing new node types — extension node, branch node, and so on, as done in the ethereum protocol, but this implementation satisfies all of our conditions — we got a fast and memory-optimized data structure.
By implementing these data structures, Opporty made Plasma Cash scaling possible as it allows you to check the history of the token and enable the non-inclusion of the token in the tree! That allows you to greatly accelerate the validation of the blocks and the Plasma Child Chain itself.
Useful links:
Source: https://habr.com/ru/post/456374/
All Articles