# Proof-of-work

Proof-of-work was the first fully functional blockchain consensus mechanism ever created. It is still in use by Bitcoin and many other blockchains. It requires its users to mine to get a chance to earn a reward for validating blocks of transactions. In this chapter, we will look into the technical side of things and how mining works.

We will see that blockchain technology is a brilliant assembly of cryptographic technical bricks that already existed for many years or even several decades for some. The beauty of the blockchain is to have been able to organize these bricks in a coherent way to create a decentralized and secure data exchange system.

## Hash​

Let's start with the basics: the hash. A hash is a hexadecimal number calculated from a set of data. In a way, it is similar to a unique fingerprint used to identify the initial data quickly. There are several hash functions. The most common is SHA256, used among others by Bitcoin. The SHA256 algorithm transforms any string of characters into a hexadecimal number of 64 characters (or 256 bits). For example, fig. 1 shows the hash of the small string "Cake" and fig. 2 shows the hash of a longer string. Note that the two hashes are completely different, but both are 64 characters long.

In the same way, you could enter all the books from a library or nothing at all (empty string), and you would still get a hash of 64 hexadecimal characters. Note that you will always have the same hash for two identical strings. You will always have two different hashes for two different strings except for very few statistically improbable collisions. This allows you to quickly verify that the initial data has not been modified, or else the hash would have changed.

FIGURE 1: The hash of a small string of characters

FIGURE 2: The hash of a large string

You have probably already used a hash in your life without knowing it. Indeed, when you download a file on your computer, some browsers check the hash of the downloaded file and compare it to the hash announced by the source before download. If the two hashes match, it means that the file you have downloaded is a perfect match to the one intended to be sent by the source. If the hashes don't match, your download has been corrupted. You can try this out manually by downloading the latest release of Ubuntu, computing the hash of the downloaded file, and comparing it to the one announced on their website.

## Block​

A block is simply a structure containing:

• its block number
• some data
• an arbitrary number called NONCE (diminutive of Number used ONCE )
• and the hash of all these data

Fig. 3 shows an example of a block. Notice that the hash of the block starts with "d8ca". So far, this block is considered invalid. There are different rules for validating a block depending on the chosen blockchain. Most blockchains use Proof-of-Work, which consists in proving that validation's work has been done on the block.

FIGURE 3: The hash of DATA, NONCE and block number does not start with 000: The block is invalid.

For example, a widely used validation rule is that the hash must start with 000. Therefore, the block will have to be "mined"; that is to say, it will be necessary to find a suitable NONCE such that the hash of the block (including the NONCE) starts with 000. Note that this problem is arbitrary. Other consensus mechanisms choose to use a hash starting with 123 or that the hash in base 10 is lower than 1000 (in the case of Ethereum). You just need a rule that proves that a validation work has been done on the block and that allows for the finding of one validator in the world (i.e., the first one to find a valid NONCE). When the rule is validated, the block is then valid.

In fig. 4, we have repeatedly incremented NONCE and calculated the hash of the block until we got a hash starting with "000". The duration of this process can vary significantly because each NONCE is equally probable. In this case, we have incremented the NONCE up to 29258. The block is now valid.

FIGURE 4: The hash of DATA, NONCE and block number starts with 000, the block is signed

As a miner, you might want to try out random NONCE instead of incrementing it. As everyone in the world is in competition, anyone with a faster machine would always beat you to it. But when using random guesses, your chances are proportional to the amount of hashing power you have compared to the rest of the world.

Therefore, mining consists in calculating the hash of a block repeatedly until the validation rule is validated. This is why it is possible to create ASICs (Application Specific Integrated Circuit) optimized for mining. For Bitcoin, ASICs integrate chips specifically designed to do only SHA256 and to find NONCE very quickly [5].

Finally, note that if you try to modify anything in a validated block, it loses its validity because you change the hash of the block, and you would have to mine the block again to find a new hash starting with "000".

## Blockchain​

You now have all the elements to understand what a blockchain is. It is simply a list of blocks where each block contains a reference to the previous block: a hash. They are, therefore, "chained". In fig. 5, you can see that block #2 contains all previously mentioned information in addition to PREVH, the hash of the previous block, i.e., the hash of block #1. To validate block #2, you have to mine it to find a hash starting with "000"; then this hash is used in "PREVH" in block #3, etc.

FIGURE 5: A valid blockchain (all blocks are signed)

If we change anything in a block, this block and all the following blocks lose their validity. Why? Because, if I change "good" by "bad" in block #2, the hash of block #2 changes, which changes "PREVH" inside block #3, changing its own hash; would in turn changes "PREVH" in block #4, changing its hash, and so on... This invalidates the whole blockchain after block #2. Therefore, it is straightforward to know if any information on a blockchain has been changed and in which block.

FIGURE 6: An invalid blockchain (some blocks are not signed because of the data modification)

Now you may be wondering: why not re-hash all the invalidated blocks? It is indeed possible to re-mine these blocks from the last valid block and revalidate the entire chain (see fig. 7).

FIGURE 7: A valid blockchain again (all the blocks following the modification have been signed again)

So can the blockchain be altered? No. Why?

• Firstly, because mining a block requires a lot of computing power. For Bitcoin, it would take several years for your desktop computer to mine a few blocks, and the more you go back in time and modify an old block, the more blocks you would have to mine. Remember the previous chapter on data structure here.

• Secondly, and most importantly, the distributed nature of the blockchain makes it statistically impossible to rewrite its history: You would need to control more than half of the BFT network and go against the MAD property (see previous chapter).

## Distributed​

Any blockchain needs to be distributed to be secured; that is to say that all the valid blocks have to be replicated on enough network nodes.

Like everyone else, you can use your computer as a node and mine with it. To do this, you need to download all the valid blocks so far. For Bitcoin, this already represents more than 330GB [6].

When any node in the world validates a new block (first to find a valid NONCE), it is added to the blockchain of all the other nodes using a gossip protocol[7], so every node has an up-to-date blockchain. There are many nodes in the world, and they all have a complete copy of the blockchain.

Let's consider what happens when a node decides to fraudulently modify a block. Fig. 8 shows a network of 3 nodes (A, B, and C), which all have a copy of the blockchain. If "C " decides to modify some data on the blockchain, this can be seen immediately by the other nodes (A and B), because the hash of the last block in their chain (000969...) is different from the hash of the last block of "C" (dec59db...).

FIGURE 8: The blockchain is identical on all the nodes of the network except when a hacker tries to modify it. We see here that node "C" tries to modify the data of block #2

Even if node "C" validated all of its blocks again as shown in fig. 9, the final hash (0004de...) is still different from the other nodes (000969...). There is no way to change the data of a block while preserving the same final hash as the rest of the network. The incorrect blockchain no longer corresponds to the majority of the other nodes. This block will become an orphan and will not be integrated into the general ledger.

FIGURE 9: Even if "C" re-mines all its block following its modification, the hash of the latest block still does not match the rest of the network.

The only known way to corrupt Proof-of-Work is through the infamous "51% attack" [8], which consists, for an attacker, to obtain more than 50% of the world's mining power, allowing him to rewrite the history (the technical details are explained here).

Fortunately, getting 51% of the world's mining power for a popular blockchain is very difficult. For instance, it would cost several billion dollars in the case of Bitcoin. However, for less popular blockchains (with fewer nodes), this is quite doable and happens quite regularly [9]. Some blockchains are trying to solve this problem by implementing different consensus algorithms. This is the case for Tezos, as we will show in the following chapters.

## Transactions' immutable history​

When we talk about "blockchains", we do not necessarily talk about "cryptocurrencies". "Blockchain" has been used for many non-financial applications [10]. Note that until now, the data stored in the blocks of our examples were simple strings. You can store any type of data: identities, electronic documents, insurance contracts, etc. Whenever it is necessary to have an immutable record, or a system of secure exchanges between parties without trust, or on an unsecured network, you should ask yourself whether or not a blockchain can and should be used.

In the case of a crypto-currency, we use the "DATA" field to store financial transactions, among other things. Figures 10 and 11 respectively show a block and a blockchain with transactions in "TX" instead of "DATA" (e.g., $13 from John to Chris). By "$", we denote a monetary value that is not necessarily dollars, but which could be any "coin" or "token", such as Bitcoin (BTC), Ethereum (ETH), etc.

FIGURE 10: A block containing financial transactions (this is a simplified representation)

FIGURE 11: A blockchain containing financial transactions

FIGURE 12: Block A gives a coinbase of $100 to Chris, which allows him to spend it in the next block Note that the first block has no previous hash. Thus the PREVH is set to a series of zeros. The first block of any blockchain is called the genesis block. There is still one big issue in our blockchain schema so far. Please take a minute and try to identify it. [...] Did you find it? Consider how the transactions are authenticated. [...] Knowing that Chris has a positive balance of$100, could Jane add the transaction "$40 from Chris to Jane" herself in a new block without Chris ever giving his consent? At this point of the chapter, anyone seems to be able to spend anyone else's money! ## Keys inside Transactions inside Blocks​ It is essential for the proper functioning of the crypto-money that only Chris can send the transaction "$40 from Chris to Jane". For that, we need to use one of the bases of modern cryptography, the Public Key Cryptography or Asymmetric Key Algorithm, which consists in a private key and a public key.

Fig. 13 shows a pair of keys. The private key is a very long, randomly generated number (you could create that number yourself by flipping a coin randomly a large number of times). A public key is a hexadecimal number that is calculated from the private key. It is possible to calculate the public key from the private key, but it is practically impossible to find the private key from the public key.

As the name suggests, the private key must be kept private. You should never share it with anyone. On the other hand, the public key can be accessible to anyone that wants to send you money (but keep in mind that this public key can then be linked to your data. You should use other generated public keys whenever possible).

FIGURE 13: A private key that has been randomly generated and its associated public key computed from the asymetric key algorithm

## Signatures inside Transactions inside Blocks​

Now what's great with a private key is that you can sign a message that can be authenticated using only your public key and signature. Indeed, fig. 14 shows first a signature generated by our private key for the message "I like cake!". Notice that if we change the message, the signature changes.

FIGURE 14: Signing some data with a private key

Let's send our message and signature to someone. That person can verify the authenticity of the message simply by finding our public key and applying the cryptographic verification algorithm on the message and its signature.

Remember that the person does not have access to the private key, but using only the public key, the cryptographic algorithm will tell this person (see fig. 15): "Yes, this message has been written by the person that owns the private key, and the message has not been altered in any way".

Or, in case of attempted identity theft or corrupted message (see fig. 16): "No, the signature is invalid, meaning that either the message has been altered or it's not the person that owns the corresponding private key that signed this message".

FIGURE 15: Thanks to the public key and the signature, anyone can verify that this data has indeed been sent by the holder of the private key associated with this public key...

FIGURE 16: ... Or inversely, that the data has been altered or does not come from the holder of the private key associated with this public key.

## Transaction Data​

Instead of using a simple string of characters in the "DATA" field, let's use transactions and public keys. So, from now on, note that instead of using names, our transactions will use the public key of the sender, and the public key of the recipient. Instead of "$50 from Chris to Jane", we now have "$ 50 from 0x4cf6... to 0x2f1f...".

The sender then signs the transaction with his private key. See fig. 17 as an example.

FIGURE 17: We sign our transaction with our private key

Miners can now verify that the private key owner has indeed sent a transaction and that the amount and recipient have not been altered by any third party (fig. 18). Otherwise, the signature would be invalid.

FIGURE 18: Miners verify that this transaction has been sent by the owner of the private key

Note that transactions do not actually use public keys in the from and to fields. They use addresses, which are hashed versions of the public keys. Because the public key is made up of an extremely long string of numbers, it is compressed and shortened to form the public address. That way, it is more easily readable and more secured as nobody can know your public key from your address.

To sum up, the private key generates the public key, which, in turn, generates the public address.

## Complete PoW blockchain​

Let's now modify our "insecure" blockchain diagram fig. 10 and add the signatures of each sender to their transaction.

If a hacker tries to change anything, e.g., the value of the amount of a transaction, two things happen:

• the block is no longer valid because the hash has changed, as seen previously

• the signature is no longer valid

The hacker could mine the block again to make it valid. However, he has no way of signing the transaction again without the private key of the sender.

This is how transactions in the blockchain are protected by only allowing the sender to sign their transactions, and it works perfectly.

To recap, here is a complete schema of a block, a blockchain, and a blockchain network.

FIGURE 19: A complete block

FIGURE 20: A complete blockchain

FIGURE 21: A complete and distributed blockchain network

## Conclusion​

You can now understand why a PoW blockchain works so well for a fully secured system without the need for a bank or any centralized entity. All you need is a random number to create a private key and then a public key, and start receiving money. Note that public keys are pseudonymous and not anonymous: compare them to bank accounts numbers. We can still associate them with your official identity at some point. For instance, you will need to associate your public key or address with your identity documents if you want to exchange a cryptocurrency for fiat and transfer some money to your bank account.