The second part of this series describes the Proof of Work (PoW) algorithm.
After reading this article, you should have a basic understanding of one key consensus mechanism behind blockchains like Bitcoin, which will help you understand the concepts featured in the following articles in this series.
¶ Prerequisites
Before you start reading, watch this!
Bitcoin visual demo by Anders Brownworth
¶ What is 'mining' and why is it useful?
Much like lines on a page are designed to be filled with words, a space in each block in a blockchain is designed to be filled with transaction information. A page has space limits (the number of rows or the paper size) just as a block in a blockchain does (the maximum number of bytes per block).
- A block can have a maximum serialized size of 1 megabyte of non-segwit data, where blocks can have a maximum of 4 million weight units of data in total (weight units can also be converted to "vbytes" at a rate of 4 weight units per vbytes).
- https://en.bitcoin.it/wiki/Weight_units
When one piece of paper is full, but a story is not finished, the writer must continue writing on a new piece of paper. Blockchains work similarly: when one block is full, it has to be signed and then cryptographically joined to the previous block, so they sit one after another, just like a train's cars in sequence behind the locomotive. This chaining is done by adding further information to the block header of a new block by miners, which you can think of as naming the block. These miners essentially compete for the right to name new blocks - see Block Header.
- Mining, miners, and nodes: Mining is the process by which blockchain transactions are validated and new PoW-based blocks named, using various types of processors. The people who do this are called miners. In the early days of blockchain (2015), a lot of miners had a local node set up, thus creating the needed effect of decentralization. These days (2021), many independent miners connect to pools and do not need to operate their own nodes. Many node operators do not mine. A node is not an equivalent of a non-blockchain server but takes care of similar tasks. The blockchain is assembled by a network of nodes, which run their own version of the blockchain software, deterministically following the rules for reaching the same state across all other nodes in the network.
Each existing (mined) block has its name given by the miners, and we will refer to this identifier as a block header hash. The block header hash aka "block hash" is a double-SHA256 hash of the block header, and is used to identify the previous block in the next block that is mined. In the world of blockchain, everything is named in a specific alphanumeric code called a "hash", which is a mix of letters and numbers that form a string.
In the blockchain context, hashes:
- represent a user wallet address
- store the information about peer-to-peer (P2P) transactions between several blockchain users (transactions aren't always between two users. A transaction can be from one address to another owned by the same user. or from a user to a smart contract. etc)
- are used to name blockchain blocks (such as Bitcoin)
So, instead of a standard name, such as John Doe, blockchain uses the inputs of a mathematical one-way cryptographic hashing function.
Here’s a quick overview of hashes:
- They protect data integrity by hiding and encoding the original message to a unique string, and thus create, in a way, the element of best pseudonyms on the blockchain while allowing everything to remain transparent.
- They represent the compressed amount of input data in, for example, 32 bytes (even if the original message would be 2 million bytes long). The data compression is provided by the compression function of the particular hashing function. The amount of bytes data gets compressed down to by a hash function depends on the function. SHA-1 hashing algorithm produces a 20-byte string.
- For example, they look like:
“00000000000000027e7ba6fe7bad39faf3b5a83daed765f05f7d1b71a1632249” - They are outputs of hashing functions, such as : SHA-1, SHA-2, MD5
- What they stand for in PoW:
- Hashes do not carry information per se, but they hide the original information (no matter how long that information is) in an alphanumeric string. This information can be revealed only by providing a keyword.
Example:
The SHA-256 hash of the word "apple" is: 3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1
To revert this back to its original form I just need to tell you the word. - The hashes are one-way functions - You can produce a hash and reveal its original message if and only if you have the correct inputs.
- In the case of PoW, the input for proof of work is everything that is required to produce a valid proof of work: the block header (hash), transactions (hashes), and a nonce (required for the PoW-related mining that produces hashes).
- Hashes do not carry information per se, but they hide the original information (no matter how long that information is) in an alphanumeric string. This information can be revealed only by providing a keyword.
For more on hashes, wait for the next part of this series: Hashing function.
¶ PoW binds the blocks together
The header of each block contains information about the previous block (except for the genesis block, the first block ever mined in the blockchain) in a linear sequence of blocks that form a blockchain. This means that, for example, the third block has encoded information in its block header that binds it to the second block in the sequence.
Take a look at this Bitcoin block example and pay attention to the "previousblockhash" attribute.
|
{ "size" : 43560, "version" : 2, "previousblockhash" : "00000000000000027e7ba6fe7bad39faf3b5a83daed765f05f7d1b71a1632249", "merkleroot" : "5e049f4030e0ab2debb92378f53c0a6e09548aea083f3ab25e1d94ea1155e29d", "time" : 1388185038, "difficulty" : 1180923195.25802612, "nonce" : 4215469401, "tx" : [ "257e7497fb8bc68421eb2c7b699dbab234831600e7352f0d9e6522c7cf3f6c77", #[... other transactions omitted ...] "05cfd38f6ae6aa83674cc99e4d75a1458c165b7ab84725eda41d018a09176634" ] } |
This is essential for making the Bitcoin blockchain resilient and the transaction data, recorded in these blocks, safe. The block header of block #3 is a combination of the block #2 block header hash, featured in a block under the “previousblockhash” tag, mixed with a unique set of characters we call the nonce (number only used once). The nonce is the secret sauce applied in the process of naming a Bitcoin blockchain block and is the thing miners are mining for (more on this later in this chapter). Pairing two adjacent blocks together using their block header is like the blocks holding “digital hands” to create a strong chain.
This also ensures that Bitcoin is getting even more resilient over time. The longer the chain of blocks is, the better protected the older blocks are.
Example:
If somebody tried to modify block #2, it would result in a change of the block #3 block and all block headers that follow, since they are connected using the “previousblockhash” information. As you can remember from the introduction video, the change in block number #2 would need to be followed by re-mining off all blocks that follow.
Analogy 1 - Egypt pyramids
We know that a blockchain is a linear structure, but imagine a man trying to pull one stone block from the middle of a pyramid in Egypt. The weight of all the upper levels will be severely limiting for such an action. As a reminder from the earlier paragraph, actually, the most recent block is the easiest one to change/remove. To follow on with the pyramid metaphor: imagine you are building a pyramid from the ground up. The last block you put on is the easiest one to remove, right? Because it doesn't have any weight built on top of it yet. In the same way as somebody who would like to remove a stone block of a pyramid to change its structure, cause damage, or just get inside and steal, the same hidden approach would be chosen by someone trying to recreate part of the blockchain. This approach would most likely be made in secret and without anybody noticing it. In the matter of blockchain fraud, the moment when this "someone" would be willing to reveal their privately prepared version of the chain (and you know about this from the 51% Attack Part) would be once they are sure that their chain is heavy enough to overtake the current chain. This would instantly cause a blockchain reorganization. Depending on the length of the re-org, it could definitely get people's attention!
Analogy 2 - Dog-piling the blocks
Block #3 dog-piling on top of block #2, and block #4 dog-piling on top of block #3, etc etc. This makes the dog-pile heavier and heavier with each new block that gets added on, making it more and more difficult to change a block the further down the dog-pile it is buried (since you first have to remove, and then re-add, all blocks on top of the block you're trying to change).
¶ PoW and the naming of a new Bitcoin block
To demonstrate adding a new block to a blockchain, we’ll use Bitcoin as an example. Note that other chains work differently!
Before a block can be connected to the preceding one and form the 'chain of blocks,' miners have to find a proper "name" for the new block. It is similar to a journalist writing a blog post, since finding a proper heading for the article can sometimes be challenging (Wiki authors know this very well). However, finding an appropriate name for the block is even harder.
So far, we have three elements:
- A new unsigned (unnamed) block that needs to be named with a block header
- The block header of the previous block
- The need to establish the correct nonce
Combining the correct nonce with the block header of the previous block solves the puzzle and generates the name of the new block. The blockchain's cryptographic `one-way` hashing function performs the `nonce + the rest of the block header for the current block` computation to form this new block's block header (name). Nevertheless, there is one more requirement that makes this whole process difficult. The outcome of this hashing function, which is a 32-characters-long alphanumeric string, needs to start with specific characters. For example, with three sequential leading zeros (a 000 prefix).
¶
The Poisson process
The puzzle-solving mentioned above may seem like "brute force nonce guessing", followed by pairing the nonce with the rest of the block header for the current block for obtaining a mathematically satisfactory hash result. Even though it sounds like pure randomness that spews forth haphazard numbers, there actually is a mathematical principle behind this called the Poisson process, which separates the PoW from complete randomness. The Poisson process works with the Poisson discrete distribution (for the cardinality of outcomes from 1 to infinity) to describe the number of events occurring in a fixed time interval or region of opportunity. A major feature of this distribution is that it requires only one parameter: the expected number of events per time interval, lambda.
There are subtle but critical reasons why blocks have a targeted time (ten minutes) to be mined and difficulty adjustments (up and down) in blockchain block mining. This information tells the miners that a new block needs to be added in a certain amount of time. The miners want to find as many blocks as possible, as fast as possible, so they can earn the most block rewards, as long as it is profitable. The difficulty adjustments keep them in check by constantly adjusting the difficulty to target ten minute block times, more difficult if blocks during the last difficulty period take on average less than ten minutes to be mined, and less difficult if blocks during the last difficulty period take on average more than ten minutes to be mined. The network's total hash power is an attribute of the blockchain network that is the same for all participating miners.
- Miners are working on the same problem all at once; to be clear they are each working on the problem separately, in competition with each other (except for miners that are part of the same mining pool).
The current task can be resolved by providing a new valid block header for the new block.
¶ Hashing function for solving the new block name
The output of the hashing function is designed to produce an output that looks like a randomly generated string of characters, but there is not such a thing as randomness in the hashing function. The Sovryn Dojo describes the hashing and hashing function in more detail in a future episode. Let us look at the following example, where we will be transmuting three numbers into a cryptographic hash to provide you with a general idea.
Then, the phenomenon you can see in Figure 1 below is called the Avalanche effect. It is a fact that even a simpler string of characters is coded into a long alphanumeric output. Now, imagine how secure all of your passwords would be if each of them would look like this? On the other hand, these are not easy to remember. The next thing to mention with the hashing function is that a simple digit change of the input totally changes the final hash output. See the picture below:
Figure 1: Note that even a simple change from 001 to 010 would cause an entirely different output to be generated. If somebody were to modify a singular bit in the Bitcoin block, it would cause an avalanche effect that would completely change the appearance of the hash. Assuming that the change was either invalid (possibly fraudulent) or that the change was outweighed by a more difficult valid blockchain. The hash alteration would then cause the current block state to be labeled as invalid, resulting in a rejection of the fraudulent activity. This is because many copies of the blockchain, stored in other blockchain nodes (servers), would not possess this hash activity in their chain, so the strong consensus of the many would ultimately reject the singular faulty node's chain.
- Node: A server or storage device that stores the entire blockchain data and runs a blockchain client software that peruses all transaction data and the blockchain to check if they conform to the block validation rules.
In this example, we skipped the use of the nonce (but will be mentioned in Fig 2) that is added to the input during the process of 'mining.' In practice, miners replace the input from this example with the rest of the block header for the current block. Then, using the process of "trial and error," they find a cryptographic hash that is prefixed by three zeros:
00019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
Now, if you want to go deeper down the rabbit hole to know more about these leading zeros, watch this video by George Levy: "Why Are There So Many Zeros in a Bitcoin Block Hash?"
¶ Blockchain block naming summary
What miners need to do now is to guess an alphanumeric string using the Poisson process that, after mixing with the rest of the block header for the current block, provides a new hash that ends with three zeros - this all in time and difficulty set by a current state of a blockchain network. The possibility that a miner will succeed with their first guess is like finding one tiny specific grain of sand on the Sahara desert. It's like winning the lottery with a billion participants. That's why the miners need to guess many variants, very quickly. After all, it is a highly rewarding competition. The miner who guesses the right nonce will produce a new name for the block in the form of a block header hash and sign the block with this name. Signed blocks can be added into a linear sequence of other blocks and create the blockchain. Excellent, the miner signed a block and got 6.25 bitcoin as a reward for their hard work. From here, it is easy to deduce why this process is called the Proof of Work algorithm. The method of generating random numbers to solve an equation is called brute force enhanced with the mathematical principles of the Poisson effect. And that's what miners do. They use brute force, the guessing of hashes to solve the puzzle in the dedicated time. This guessing requires a phenomenal amount of computation power (work) and creates the famous Proof of Work label.
¶ PoW as a Sybil control mechanism
Sybil attacks are an Achilles’ heel for decentralized protocols during which the attacker subverts the reputation system of network service by creating a large number of pseudonymous identities and uses them to gain a disproportionately large influence.
- Sybil Attacks run multiple malicious nodes on a network that can then refuse to allow new blocks to enter a blockchain.
- Don't change this for the 51% Attack, which allows malicious entities to withhold majority control of a network and use it to revert the transaction history of the latest block to cover the tracks after performing a double-spend. (This topic will be covered in part 4: 51%)
To be straight and honest, the PoW algorithm does not prevent Sybil attacks per se. However, PoW by design makes a Sybil attack very expensive and extremely impractical for an attacker by applying a set of rules for the generation process of a new block. The PoW protection literally relies on the upfront cost to prevent Sybil attacks.
Let run through an example with Bitcoin:
Protection rule number 1
- The ability to create a block must be proportional to the total processing power of the Proof of Work mechanism. That means that an attacker would carry out a non-arbitrary and equal amount of computational work required for new block creation (very difficult and costly for an attacker), thus being rewarded. Bitcoin mining is a very intense competition that is designed to motivate Bitcoin miners to remain honest.
Protection rule number 2
- Every Sybil identity must perform as much work as every honest identity, thus making a Sybil attack prohibitively expensive.
¶ Repetition is the mother of all wisdom
Before we move forward, let's summarize what we already know and put some more technical background into it!
The guessed 'nonce' (already mentioned in the above paragraph) is an abbreviation for "number only used once," which is a number added to a hashed block in a blockchain. The 'nonce' is the number that blockchain 'miners' are solving for. PoW miners are guessing the unique 'nonce' suffix (since it is the last field in the block header) of the block's identifier hash. The 'nonce' with the rest of the block header for the current block is the input we have to put in the hashing function, which generates a new candidate hash: the new block's block header (see Figure 2 below).
Figure 2: This candidate must meet predefined criteria, specified by the rules encoded in the full node software that a user of the blockchain runs on their computer. If the new candidate does not meet the predefined criteria, the 'nonce' has to be modified (guessed again), and the process repeated. Otherwise, the new block is successfully signed and added to the blockchain. Finding a correct 'nonce' for each hash is arduous because it requires finding the correct string of characters that will alter the outputs of a 256-bit number (the most basic unit of computation), which is usually represented in the hexadecimal number system with 64 characters for human-readability, which is necessary when confirming transactions to the protocol.
I explain this phenomenon later in part 3: "Why does blockchain need a hashing function?"
Currently, We are way beyond any computer being able to solve the current Bitcoin difficulty alone. Using a single simple computer, a miner can solve this in a year if they are extremely (impossibly) lucky, but as we already know, miners do not have that much time.
- The difficulty target is billions of times more difficult than a single computer could solve within a ten-minute period of time.
What if solo miners were to use 100 computers at once and join the forces? The process of finding a correct 'nonce' is time and power-consuming, but with enough computing power, maybe they can collectively get the required 'nonce' for the new block much faster. The miners' collaboration in what they call mining pools is about assembling big mining farms, compounds of thousands of powerful ASIC chips (Bitcoin miners), intending to improve their chances and multiplying their time and cost-effectiveness in brute-force guessing race, enhanced by the mathematical principles of the Poisson process.
- Bitcoin miners use ASIC chips since the GPUs and CPUs are no longer effective for mining BTC (but usable for Ethereum and others).
Finding the correct nonce is how the block is named, which means the block can be finally added to a blockchain. They are rewarded with that chain's native cryptocurrency for their effort; miners operate on the basis that this amount covers the cost of the electricity consumed and more. Today, one bitcoin (1 BTC) is equal to ~$33,000 USD. The current block reward amount is 6.25 BTC (this will be halved to 3.175 BTC in the 2024 ‘halving’). ~$312,500 sounds like a decent reward for all that hassle! Then, the only method this can be done is the one in which a miner produces a unique alphanumeric string by brute-force guessing, which affects what a 24-characters-long hash looks like (and yes, those hashes have to look exactly like that since that's how the math behind it works), this process can take a long time.
“Basically, Proof of Work is a lottery system where a ‘miner’ tries to guess a random number as quickly as possible in an environment with heavy competition.” - Mickey
Yes :), the author just quoted himself. Well done, You!
¶ Miners, mining, and nodes
Finding a proper name for a block is not the only responsibility of the miners. They also verify transactions made on the network, similarly to full nodes. Miners have to verify transactions so that they do not include an invalid transaction in their block. Miners do this using full node software. Other non-mining users run full node software alone to verify transactions and store their own copy of the blockchain - “Don’t trust, verify”.
For example:
- When Honey Badger sends 20 SOV tokens as a way of thanks for the song Wolverine wrote about him, this transaction first needs to be validated by miners. For every transaction they help to verify, they get a fee if and, if the miner wins the nonce naming race, the block reward for the block that a given transaction was included in.
¶ Explaining the difference between a centralized network with intermediaries and a blockchain peer to peer network without intermediaries (sending FIAT vs sending bitcoin)
Finally, to get a complete understanding of the importance of miners, imagine an example in which Company A wants to send money to Company B:
The financial institution behind the account of Company A has to create a communication order, and their servers take care of this transaction. However, there are no servers like this in the world of PoW-based blockchain, also called a peer-to-peer (P2P) network. Instead of company servers, any computer connected to the blockchain network can act as a blockchain node. Those nodes can substitute these servers for the effort of moving money around. Now, let us include miners connected to the blockchain network with all that powerful hardware. The only reason miners require this amount of computation power is to compete with other miners and, as hashrates and miners increase over time, so too does the power required to compete. Artfully, the blockchain uses this competition of computation for processing transactions and securing the chain exponentially. Proof of Work simultaneously solves the problem of how nodes determine which blockchain is "the" master blockchain in a situation with multiple valid blockchains to choose from. Then, they will go with the heaviest valid chain with the most cumulative proof of work (measured in difficulty).
Meanwhile, while the miners are brawling with each other, the money from company A arrives at its destination. And yes, except for the receiving process, which is not that hard, company B is doing nothing during the whole example. The information about this transaction is most likely stored only on the servers of Company A and B. No external party can verify the transaction occurred and must instead rely on both companies to handle the transaction fairly.
With a Bitcoin transaction from one Bitcoin wallet to another using a blockchain, the related transaction information is relayed throughout the network - passed from node to node (from server to server) until it is transmitted and stored in all nodes participating in the blockchain network.
¶ The technical round-up
Proof of Work is the area where mining (the ever-beating heart of the blockchain) does its kung-fu; it is the backbone of the main cryptocurrency, Bitcoin, as well as many other blockchains. Miners are people who run the ASIC machines (Application-Specific Integrated Circuit customized for a particular use) or powerful computer systems with powerful hardware (CPUs, GPUs), which they use for brute-force number guessing (mining). Those numbers are then used to validate transactions and to sign a full block.
The more rewards there are to be obtained, the more computational power will be spent to obtain the rewards. But be careful, the number of transactions that can be processed is completely unrelated to how much hashpower a miner has. If a particular miner forges a new block by mining its hash, they are rewarded with cryptocurrency tokens. For every transaction, a sender must incentivize the miners to process its transaction by paying them a fee.
Proof of work is the most environmentally friendly way to solve the specific problem that Bitcoin solves: censorship-resistant money, uncensorable by large corporations and governments alike. Bitcoin also incentivizes miners to find the cheapest energy, and it just happens that this is often from clean energy sources, but not always. Recently, many mining operations have begun to utilize clean energy from sources that would otherwise go to waste. For example, hydroelectric and geothermal energy sources (like the El-Salvadorian volcano mining operation) would typically remain unused due to being geographically too far from conventional use cases, like powering towns. Miners only require an internet connection to economically transfer their computational power from source to productivity, meaning PoW networks like bitcoin can, and will be, an extremely clean means of transaction.
"There could be a lot of wasted computation potential in this competition," somebody might say. From one technical point of view, the energy consumed by mining is wasted; however, it isn't wasted from an economic point of view. The computation power means that there is a cost involved. The effort is rewarded by tokens, capturing the value. That value needs to outweigh the costs to make the process economically viable. Since participating in mining is open to anyone, the difference between the cost and reward will always be limited. As an example, if a miner only needs 100 USD to mine 500 USD worth of tokens, more people would get involved in mining. This raises the total computation power involved in the competition for a block, thus raising the average cost required to mine a block. The higher the cost to mine a block, the more security that block has against malicious actors. In the case of Bitcoin, the constantly adjusting difficulty rate ensures every block takes the target 10 minutes to mine, meaning the amount of computation required increases as more mining capacity enters the network, further increasing the security of the network.
¶ Something more to think about:
- PoW and Practical Byzantine Fault-Tolerant (PBFT) algorithms attempt to provide a solution for byzantine fault tolerance (only in very different ways).
- PoW by itself can be used to thwart spam, as initially proposed by Dwork and Naor.
- PoW doesn't get you an agreement; it gets you rate limiting.
- PoW, by itself, isn't a consensus mechanism. To reach the consensus a valid chain with the most cumulative proof of work is also needed. This chain was also called the longest or heaviest in recent history. In the Bitcoin network, PoW works with the longest/heaviest chain selection rule to achieve consensus.
Congratulations. You made the second step in becoming a blockchain expert.
¶ Want to know more?
- Do you want to know more about mining and miners? Read two following bonus articles and mine the knowledge out of the miner's minds!
- Article One - Introduction, theory summarization, Set of three interviews with 'miners' of all kinds and levels of expertise.
- Article Two - Continuation of the story from the first episode, another two interviews, guides, and manuals for 'mining'.
Originally post on Hackernoon -July 2th, 2021
¶ Navigation
- Part 1: Determinism
- Part 2 : Mining, Miners, and the Proof of Work algorithm
- Part 3: Hashing Functions
- Part 4: The 51% Attack
- Part 5: Forks
- Part 6: Blockchain Transactions
- Part 7: Inside a Bitcoin Block
- Part 8: Smart Contracts
- Part 9: Blockchain's impact on the world
- Back to Sovryn Dojo