Proof-of-Proof-of-Work on the fingers. On the way to a sensible blockchain
Blockchain protocols should provide consensus among the nodes of the decentralized system. Perhaps the most well-known algorithm of consensus can be considered "retarded, but reliable, because the inhibited" algorithm is Proof-of-Work: each node, having a set of new transactions, enumerates a certain number of nonce, which is the field of the block. A block is considered valid if all transactions inside it are valid and the hash function of the block header has some generally accepted feature (for example, the number of zeros at the beginning, as in Bitcoin):
As you know, blockchain is a chain of blocks. It is a chain because inside each block there is an recorded id (usually a hash from the header) of the previous block. For the following reasoning, the blockchain in a simplified form can be represented as follows:
In the process of synchronizing the node with other nodes, it needs to carry out the validation of all the blocks that the neighbors sent to it - check the hashes and transactions of all the new blocks, and in the case of the first connection, to the very first block (genesis -block). It is not difficult to assume that this is a rather lengthy and costly process ...
')
There is an option to request the last few blocks from neighboring nodes and, trusting, to accept them as valid ones. But this option does not fit the spirit of security in an “environment where no one trusts anyone.”
The hash function of the block header is its id. As mentioned earlier, in the Bitcoin network, as in many other networks, a feature that determines the validity of a block is the number of zeros at the beginning of the id record. This number of zeros, known and common to all miners, is called the mining difficulty T (mining target). A valid hash with T zeros at the beginning may have more zeros at the beginning than T. More specifically, half of the blocks will have only T zeros at the beginning; half of the blocks will have T + 1 zero at the beginning; a quarter of blocks T + 2 zeros, etc. For example, this might look like a set of valid blocks for T = 5:
The number of zeros that exceeds T in the id of a block is called the level µ, and the blocks with the level µ are called µ - superblocks. If a block is a µ-superblock, then it is also
(µ -1) -superblock Thus, while not changing anything, but only in terms of the entered parameter µ, we can represent a chain of blocks in the following µ-level form:
The blocks are numbered for ease of description, the numbering does not carry a semantic load.
Now we will think about how we can use it. If we write in the header of each block not only the id of the previous block, but also the id of all the last blocks at each level, then we allow each block to refer to more “ancient” blocks than the previous one. The set of all the last blocks at each level will be called interlink (multiple link). For example, Interlink for block 8 looks like this:
What does this give us? Suppose we have connected a new node and now we want to synchronize it safely. As we have already said, in order to fully validate the new block, the node needs to “step through” to genesis - the block throughout the blockchain. However, if we have links to some “support” blocks in a validated block, we can “walk” to the genesis block, by requesting from other nodes not the whole blockchain, but only some proof (proof), which will contain a short route to first block. The route itself will be a valid hook of the blockchain itself, since the blocks of the hook are consistently linked to each other.
Proof is a set of headers of several previous blocks. Strictly speaking, the proof contains not only the “short route”, but also a few more headers from other blocks. This is done to verify the proof of the specified security parameters m, k, etc. (a detailed description is given in the original article, the link is at the end).
A node that does not store the entire blockchain, but only asks for proof from a full node that stores the entire history is called a PoPoW node. Theoretically, such a node can be deployed on a low-power computer, a smartphone.
Algorithm operation of the PoPoW protocol is as follows:
1. PoPoW-node requests proof for a block from a full node.
2. Full - a node (proover) forms a proof and sends it.
3. PoPoW-node (verifier) ​​verifies the evidence, compares with the evidence of other nodes and makes a conclusion about the validity of the block.
It is also worth noting that the complexity of creating PoPoW proofs is not inferior to the complexity of creating a complete chain of valid headers (the hash function of the header contains Interlink, so it would be necessary to “fake” blocks of dishonest nodes taking into account the µ-level hierarchy). Therefore, using evidence to validate a PoPoW unit does not entail a loss of security.
Algorithm NiPoPoW - Non-Interactive Proof-of-Proof-of-Work - includes advanced generation and verification of evidence, it is resistant to some attacks that are exposed to PoPoW. The link to the original article from the authors is also at the end.
With the help of these algorithms, two actual problems are solved: effective transaction verification and effective evidence for sidechains (Sidechains).
In the first case, this algorithm allows you to connect to the network "light" nodes that can quickly synchronize with the network.
In the second case, the algorithm allows you to store and refer to events that occurred in other blockchain networks, which is useful for clients and wallets working with several blockchains. PoPoW-proof is short enough so that you can put it in a transaction. For example, you can write smart contracts in blockchain A, which are based on some events in blockchain B.
This review was compiled freshly after participating in the Unblock Hackathon hackathon, where one of the tasks was to implement this protocol. The task's authors were hackathon partners from the Ergo platform , inside which this algorithm is used.
The text is based on the original articles.
PoPoW: Proofs of Proofs of Work with Sublinear Complexity. Aggelos Kiayias, Nikolaos Lamprou, and Aikaterini-Panagiota Stouka
NiPoPoW: Non-Interactive Proofs of Proof-of-Work. Aggelos Kiayias, Andrew Miller and Dionysis Zindros
Hash( Block{transaction,nonce,…} ) = 000001001... As you know, blockchain is a chain of blocks. It is a chain because inside each block there is an recorded id (usually a hash from the header) of the previous block. For the following reasoning, the blockchain in a simplified form can be represented as follows:
In the process of synchronizing the node with other nodes, it needs to carry out the validation of all the blocks that the neighbors sent to it - check the hashes and transactions of all the new blocks, and in the case of the first connection, to the very first block (genesis -block). It is not difficult to assume that this is a rather lengthy and costly process ...
')
There is an option to request the last few blocks from neighboring nodes and, trusting, to accept them as valid ones. But this option does not fit the spirit of security in an “environment where no one trusts anyone.”
PoPoW-nodes.
The hash function of the block header is its id. As mentioned earlier, in the Bitcoin network, as in many other networks, a feature that determines the validity of a block is the number of zeros at the beginning of the id record. This number of zeros, known and common to all miners, is called the mining difficulty T (mining target). A valid hash with T zeros at the beginning may have more zeros at the beginning than T. More specifically, half of the blocks will have only T zeros at the beginning; half of the blocks will have T + 1 zero at the beginning; a quarter of blocks T + 2 zeros, etc. For example, this might look like a set of valid blocks for T = 5:
000000101… (6 ) 000001110… (5 ) 000001111… (5 ) 000000010… (7 ) 000000101… (6 ) 000001110… (5 ) 000001111… (5 )
The number of zeros that exceeds T in the id of a block is called the level µ, and the blocks with the level µ are called µ - superblocks. If a block is a µ-superblock, then it is also
(µ -1) -superblock Thus, while not changing anything, but only in terms of the entered parameter µ, we can represent a chain of blocks in the following µ-level form:
The blocks are numbered for ease of description, the numbering does not carry a semantic load.
Now we will think about how we can use it. If we write in the header of each block not only the id of the previous block, but also the id of all the last blocks at each level, then we allow each block to refer to more “ancient” blocks than the previous one. The set of all the last blocks at each level will be called interlink (multiple link). For example, Interlink for block 8 looks like this:
What does this give us? Suppose we have connected a new node and now we want to synchronize it safely. As we have already said, in order to fully validate the new block, the node needs to “step through” to genesis - the block throughout the blockchain. However, if we have links to some “support” blocks in a validated block, we can “walk” to the genesis block, by requesting from other nodes not the whole blockchain, but only some proof (proof), which will contain a short route to first block. The route itself will be a valid hook of the blockchain itself, since the blocks of the hook are consistently linked to each other.
Proof is a set of headers of several previous blocks. Strictly speaking, the proof contains not only the “short route”, but also a few more headers from other blocks. This is done to verify the proof of the specified security parameters m, k, etc. (a detailed description is given in the original article, the link is at the end).
A node that does not store the entire blockchain, but only asks for proof from a full node that stores the entire history is called a PoPoW node. Theoretically, such a node can be deployed on a low-power computer, a smartphone.
Algorithm operation of the PoPoW protocol is as follows:
1. PoPoW-node requests proof for a block from a full node.
2. Full - a node (proover) forms a proof and sends it.
3. PoPoW-node (verifier) ​​verifies the evidence, compares with the evidence of other nodes and makes a conclusion about the validity of the block.
It is also worth noting that the complexity of creating PoPoW proofs is not inferior to the complexity of creating a complete chain of valid headers (the hash function of the header contains Interlink, so it would be necessary to “fake” blocks of dishonest nodes taking into account the µ-level hierarchy). Therefore, using evidence to validate a PoPoW unit does not entail a loss of security.
NiPoWPoW - algorithm
Algorithm NiPoPoW - Non-Interactive Proof-of-Proof-of-Work - includes advanced generation and verification of evidence, it is resistant to some attacks that are exposed to PoPoW. The link to the original article from the authors is also at the end.
What is all this for?
With the help of these algorithms, two actual problems are solved: effective transaction verification and effective evidence for sidechains (Sidechains).
In the first case, this algorithm allows you to connect to the network "light" nodes that can quickly synchronize with the network.
In the second case, the algorithm allows you to store and refer to events that occurred in other blockchain networks, which is useful for clients and wallets working with several blockchains. PoPoW-proof is short enough so that you can put it in a transaction. For example, you can write smart contracts in blockchain A, which are based on some events in blockchain B.
This review was compiled freshly after participating in the Unblock Hackathon hackathon, where one of the tasks was to implement this protocol. The task's authors were hackathon partners from the Ergo platform , inside which this algorithm is used.
The text is based on the original articles.
PoPoW: Proofs of Proofs of Work with Sublinear Complexity. Aggelos Kiayias, Nikolaos Lamprou, and Aikaterini-Panagiota Stouka
NiPoPoW: Non-Interactive Proofs of Proof-of-Work. Aggelos Kiayias, Andrew Miller and Dionysis Zindros
Source: https://habr.com/ru/post/353160/
All Articles