Blockchain and Proof of Work
Blockchain is a disruptive technology that has been applied in non-financial contexts, unlike what was initially thought in its initial conception. In my opinion, the most fantastic thing about blockchain is that it basically consists of a combination of different technologies already existing and consolidated, such as public key cryptography, hash functions, P2P, merkle tree, proof of work etc. All of these existing concepts are used in such a way that allows the creation of an ecosystem that provides reliability.
It is common to hear from people who report difficulty understanding blockchain. It really is an entirely different approach than we were used to. In my master’s research project, I studied different blockchains and other distributed ledger technologies. The focus of this article is to explain in a clear way, how a blockchain works, as well as to show in practice one of its main elements: the distributed consensus algorithm Proof of Work (PoW). For code lovers, I’ll explain PoW with a simple example in Java.
Initially, we will discuss the problem.
How do you create a system that people can trust to the point of paying for digital assets?
Let’s suppose you want to create a cryptocurrency. Then you develop the whole backend, implement mechanisms to ensure that transactions are executed, invest a good amount of money in marketing, and in the end, people don’t feel safe to buy your cryptocurrency. Why? Because the whole system is centralized in your hands and no matter how much you convince people that you are not going to commit fraud, you have the technical possibility to enter the database and change a value. That’s exactly where the blockchain proposal comes in: to be an impossible system to defraud, even if people want to. How is this possible? Let’s take a look.
The life cycle of a transaction
To use a blockchain, like Bitcoin, for example, you need to download the client software and create an account, which is basically a pair of keys. I will not delve into the usability issues as it is not the purpose of this article. Once wallet software is installed, a transaction can be sent to a target account. The user inputs some data into the wallet software, which in turn structures a transaction according to the blockchain specification, then the wallet software broadcasts the transaction to a pool. One of the input data is the amount the user is willing to pay as a reward for the miner who will place his transaction in a block. Once the blockchain is distributed as a P2P network, all users who have bitcoin client software enabled for the mining function will receive this transaction and several others. This transaction has not yet been confirmed, that is, it has not been inserted into the blockchain.
Miners select a set of transactions from the pool, first looking for the transactions that offer the highest reward, and then start the mining process. In the example above, the miner chose transactions TX A, TX E, and TX F to be mined. Here is a point where many doubts arise.
What is mining?
The answer is very simple. Mining is basically running the Proof of Work algorithm.
So far, a transaction has been sent by a wallet software, but it still appears with the status of “unconfirmed”. This means that some miner has not yet selected the transaction for mining because it has a very low reward value, or else a miner has already selected the transaction but has not yet solved the PoW puzzle. It is precisely this puzzle that we are going to talk about.
As the name implies, the intention of the PoW algorithm is to prove that a task was performed, it means proving that high processing was done with a cost of about 10 minutes, in the case of Bitcoin. Be patient, you will understand why this work is necessary to achieve the main objective of the system: reliability.
The basic premise of PoW is that it is very difficult to solve the puzzle but very easy to verify. So what is this puzzle that PoW needs to solve? The answer is very simple and we will see it in code to make it even easier. As mentioned, a miner selects a set of transactions from the pool and assembles a proposal for a block to be added to the chain. Then the miner executes the PoW, which basically concatenates data from the block that is being mined and then append an integer value to this data. This integer value added is called nonce.
A hash (actually some hash functions) is generated for the concatenated value. If the hash generated is less than a target number defined by the Bitcoin network, that is starts with a certain amount of bits 0, then the puzzle is solved. For each concatenation, a different hash is generated.
If the value does not satisfy this condition, the nonce is incremented and then tested again and the cycle is repeated until it is discovered which nonce is concatenated with the data of a block, generates a hash with some 0 bits at the beginning.
For example:
hash(previousBlockHash + merkleRootHash + ... + nonce) = resultHashLater I will explain previousBlockHash and merkleRootHash :)
Assuming the Bitcoin network’s difficulty level is set to find a hash starting with 5 zeros. Substituting the values, we would have:
hash(000006b19edd2 + 930cf0bc48 + … + 1) = ca83f47a6c521
hash(000006b19edd2 + 930cf0bc48 + … + 2) = be4c0d25e8aca
hash(000006b19edd2 + 930cf0bc48 + … + 3) = 920de8249b3d8
hash(000006b19edd2 + 930cf0bc48 + … + 4) = a310e1182407f
hash(000006b19edd2 + 930cf0bc48 + … + 5) = 725203274905d
hash(000006b19edd2 + 930cf0bc48 + … + 6) = 00000c514ce06 -> SolvedIn the example above, for the proposed block with the transactions selected by a miner, the nonce value concatenated to the block data in order to answer the challenge is the value 6. The miner then adds this value to the block and announces it to the rest of the network so that the mined block can be added to the chain. Once the nonce is added to the block, all other participants are able to confirm that this nonce is the correct for this block. It will not be necessary for each participant in the network to run PoW to validate. They already have all the data, so all they have to do is to generate a hash with this nonce and confirm that it starts with the amount of zeros required by the network.
If you want to see a real transaction with real data, use a block explorer such as BlockCypher, you can view all the transaction data, including the nonce.
Example of real transaction:
So you may be wondering, if the nonce is increasing in the same way by all the miners, then the miner who has the most processing power will always be the winner? No. One of the ones used in the concatenation is the merkle tree root hash. What does this mean? In short, it is a hash that represents all transactions in a block. The merkle tree is a data structure used to generate a short representation of a data tree. Basically, transaction pair hashes are recursively concatenated until a root hash is reached. Changing any of the transactions would invalidate the generated root hash. The following figure illustrates the generation of the root hash of a merkle tree for eight transactions.
In practice, even if two different miners selected the same transactions to mine a block, there would still be a different transaction. This is because in Bitcoin, the first transaction in a block is called coinbase transaction. This is the only transaction that can be created by a miner. The miner prepares this transaction to send the block reward to his own account. The reward of the block is the sum of the fees of all transactions with an amount of bitcoins generated by the system itself, agreed by the community. Once each miner has its different wallet address, each miner will run PoW with a different root hash. Thus, it is impossible for two miners to have the same data to find the nonce.
The following figure shows two miners who coincidentally selected the same transactions from the pool. Still, each will have a different root hash because the first transaction has a different destination address (miner address). This means that the nonce will be different for each miner.
What about reliability? As you saw before, one of the values used in the concatenation for PoW is the hash of the previous block. This implies that if there is any change in any transaction on the blockchain, it would invalidate the block, as the nonce announced in the block would no longer serve for the new changed data structure.
For example, let’s assume a blockchain with 50 blocks. The fraudster who changed block 30, must recalculate the nonce for this block, that is, execute PoW, however, block 31 contains a hash of block 30, which is no longer the same. Then the fraudster should also recalculate the hash of block 31 and so on until the end of the chain.
Even if the fraudster wanted to spend all of his computing resources to do this, there are thousands more of nodes with the legitimate copy of the blockchain. That’s where the magic is.
Next, we will see a code in java to show a PoW in practice.
You can download the code in my repository:
For some reason, Github is changing the code’s indentation. The code is a simple Java class that contains a main method.
To run, follow the steps:
git clone https://github.com/marcelohweb/proof-of-work-java.git
cd proof-of-work-java/src/
javac ProofOfWork.java
javac ProofOfWorkVerifier.javaMining
To view the PoW algorithm, just call the ProofOfWork class by passing a few arguments:
java ProofOfWork 00000 0000038b13568323e3886a7391f6346f555b247bb86f7d9532409874572c45bd 871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a2991234 1392872245The first argument passed is the level of difficulty, that is the number of leading zeros that the hash resulting from the concatenation must have. In this example, we pass 5 zeros. The second argument is the hash of the previous block. The third argument is the root hash of the merkle tree and the fourth argument is the timestamp of the mining moment in hexadecimal.
Result:
In the example above, the correct nonce to meet the requirement is 239327. One tip is to monitor CPU usage while the algorithm is running.
Validation
To validate the block, call the ProofOfWorkVerifier class by passing one more argument: nonce 239327.
java ProofOfWorkVerifier 00000 0000038b13568323e3886a7391f6346f555b247bb86f7d9532409874572c45bd 871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a2991234 1392872245 239327Result:
Note that unlike the execution of the algorithm, which took a while and cost a lot of processing, validation is simple and quick.
Try changing the difficulty level and monitor your computer’s processing.
Conclusion
In this article, we presented the operation of a blockchain with a focus on explaining the Proof of Work distributed consensus algorithm. Through an example code, it was possible to see the algorithm running. I hope that by reading this article, it will be possible to understand how blockchain manages to provide reliability to its users through the intelligent use of consolidated technologies. Cryptocurrencies have value because people believe it and people believe it because of the reliability provided by the entire system.
