Mining a Block

In this article, we learn about the PoW consensus algorithm, target representation, and retargeting on the Bitcoin protocol.

Table of contents.

  1. Introduction.
  2. Proof of Work(PoW) Algorithm.
  3. Target Representation and Retargeting.
  4. Summary.
  5. References.

Introduction

In this article, we learned how transactions are aggregated into a block. A candidate block is a temporary block created using transactions selected from the memory pool. Mining nodes select transactions from their memory pool to form candidate blocks.

Remember candidate blocks are not valid blocks. They need to have a valid PoW(Proof of Work). A candidate block is validated only if a miner can successfully solve the cryptographic puzzle specified by bitcoin, A process referred to as mining.

In this article, we learn how a candidate block is validated, the proof of work algorithm, target representation, and retargeting to adjust the difficulty of the cryptographic puzzle. We will also determine what success looks like when mining a block and how the new block is validated by other miners.

The proof of work (PoW) is a consensus mechanism used by Bitcoin and Ethereum that requires miners to put in 'work' or effort in mining a block. This not only serves to incentivize them but also keeps malicious participants from misusing the system.
Miners compete to find a nonce that when hashed with the block header is less than the target. This takes a lot of time since computers cycle through trillions of numbers to find it.

Proof of Work(PoW) Algorithm.

Bitcoin mining uses the SHA256 hashing algorithm. It takes an arbitrary length of data and produces a fixed-length unique string(digital fingerprint of the input). This means that for any given input, the length does not matter, the resulting hash when the input is passed through a hashing function will be a fixed-length string.
Hashing functions should have minimum collision, be easy to compute, and have a high load factor and a high gain factor.

The following example hashes an arbitrary text to produce a fixed-length string;

import hashlib

text = "Bitcoin mining uses the SHA256 hashing algorithm"
text_hash = hashlib.sha256(text.encode('utf-8')).hexdigest()

print(text_hash)

Above, the resulting 256-bit string is the hash of the message digest of the input. If a single letter in the input is changed, we expect the resulting hash to be different. Also, we expect that no other text hashes to this same digest.

The following example demonstrates Bitcoin's Proof-of-Work algorithm;

import hashlib

text = "Bitcoin mining uses the SHA256 hashing algorithm"

def findNonce(text):
    for nonce in range(20):
        n = text + str(nonce)
        hash = hashlib.sha256(n.encode('utf-8')).hexdigest()
        print(f'{nonce} : {hash}')

findNonce(text)

Above, we use a nonce, this is a number only used once. We make a challenge out of this by trying to find a hash starting with zero. In our case we have such a hash number 15:02f4e1ac21c54c02a8459ba52dd66404f59fe2f0cc8c8672b63090b1bc648d3c, this is produced by the original text + number 15, 'Bitcoin mining uses the SHA256 hashing algorithm15'. It took use 15 attempts to find it.

If the output of the hash function is evenly distributed, we expect to find a result with a starting 0 once after every 14 hashes.
Numeriaclly, we want to find a hash that is less than 0x1000000000000000000000000000000000000000000000000000000000000000.
This threshold is referred to as the target and the goal is to find a hash that is numerically less than the target, meaning that if we decrease the target, the task of finding a hash less than the target increases in difficulty and the computational resources needed to find it.

This means that we can estimate the amount of work it takes to succeed from the imposed difficulty by a target. The PoW algorithm is based on a deterministic hashing function - SHA256 whereby the input consists of proof that a certain amount of work was done to produce the result that is less than the target.

From our example, 15 is the winning nonce, anyone can confirm this independently by adding the number 15 as a suffix to the input phrase 'Bitcoin mining uses the SHA256 hashing algorithm' and computing the hash verifying that it is less than the target.
The lower the target the higher the difficulty level, in this case, more calculations and computing power is needed to find an appropriate nonce but a single one to verify this be all other nodes. We can also estimate the difficulty and know how much work went into finding such a nonce.

In the previous article, we had already constructed a candidate block filled with transactions, the next step involves the miner calculating the ahs of the block header to see if it is smaller than the current target. If it is greater, the miner modifies the nonce by incrementing it by 1 and tries again. Currently, miners try quadrillions of times before finding a nonce resulting in a block header hash less than the target.

The following python code demonstrates this concept;

def proof_of_work(header, difficulty_bits, max_nonce):
    target = 2 ** (256-difficulty_bits) # difficulty target

    for nonce in range(max_nonce):
        to_hash = (str(header) + str(nonce)).encode('utf-8')
        hashed = hashlib.sha256(to_hash).hexdigest()
        if int(hashed, 16) < target: # valid result less than target
            print(f"### SUCCESS ### {nonce}")
            print(f"Nonce: {nonce}\nHashed Result: {hashed}")
            return (hashed, nonce)

    print(f"### FAILED after {nonce} (max_nonce) tries ###")
    return nonce

def solve(nonce, hashed):
    for difficulty_bits in range(32): # difficulty from 0 - 31 bits
        difficulty = 2 ** difficulty_bits
        
        print("### Mining Started...")
        print(f"Difficulty: {difficulty} ({difficulty_bits} bits)")

        start = time.time()
        block = 'Random test block header with transactions' + hashed
        max_nonce = 2 ** 32 # 4 billion
        hashed, nonce = proof_of_work(block, difficulty_bits, max_nonce) # get valid nonce
        end = time.time()

        elapsed_time = end - start
        print(f"Took: {elapsed_time:.4f} seconds")

        if elapsed_time > 0:
            hash_power = float(int(nonce) / elapsed_time) # hashes/second
            print(f"Hashing Power: {hash_power} hashes/second")
            print()

if __name__ == '__main__':
    solve(0, '')

We have the following output;

### Mining Started...
Difficulty: 1 (0 bits)
### SUCCESS ### 0
Nonce: 0
Hashed Result: 17bab590292d3ef6a09f27fe082a565da28826e0a5b2e515076e85e27a0b4bf6
Took: 0.0000 seconds
Hashing Power: 0.0 hashes/second

### Mining Started...
Difficulty: 2 (1 bits)
### SUCCESS ### 1
Nonce: 1
Hashed Result: 7831affddf03d63e6efef483e7015083ac226eab09d0dee5a6341a7e7dcc633c
Took: 0.0000 seconds
Hashing Power: 36472.208695652174 hashes/second

### Mining Started...
Difficulty: 4 (2 bits)
### SUCCESS ### 6
Nonce: 6
Hashed Result: 10fc867221e1e7d54d7ae1589026b736a18a7fe19ceff629fbe4a37e87155cc7
Took: 0.0000 seconds
Hashing Power: 186413.51111111112 hashes/second

### Mining Started...
Difficulty: 8 (3 bits)
### SUCCESS ### 0
Nonce: 0
Hashed Result: 0fdee6276566040d79b41e914fc806e499606b0f0f076cbe39a4059085f4f225
Took: 0.0000 seconds
Hashing Power: 0.0 hashes/second

### Mining Started...
Difficulty: 16 (4 bits)
### SUCCESS ### 11
Nonce: 11
Hashed Result: 0ed4c1ce83ae33fd5dcef5caa0a3cd22c6d849c38b5ede4c34043f6e00e23872
Took: 0.0001 seconds
Hashing Power: 183084.6984126984 hashes/second

At some point during the generation of nonces, the system is overwhelmed with the amount of processing needed to find it. This is how Bitcoin maintains the 10-minute block generation. As the algorithm proceeds to find the solution gets harder and harder and takes a lot of time and computing resources.

Target Representation and Retargeting.

A block contains the target - target bits. This is used to express the Proof-of-Work target as a coefficient/exponent format with the first two hexadecimal digits for the exponent and the rest as the coefficient.
To get the difficulty target from this we use the following formula;
target = coefficient * 2 ^ (8 * (exponent - 3 ))

For example, given the difficulty bits 0x1903a30c, we have the following difficulty target;

target = 0x03a30c * 2^(0x08 * (0x19 - 0x03))^

in decimal we have the following;

target = 238348 * 2^176^

We can represent the result in hexadecimal form as shown below;

0x0000000000000003A30C00000000000000000000000000000000000000000000

The above indicates that a valid block at a specific height is the one with a block header hash less than the above target. In binary format, the number has more than 60 leading bits set to zero. In this case, a single miner processing 1 trillion hashes per second would only find a solution once after every 8,496 blocks(once every 59 days).

The target determines the difficulty, therefore affects how long it takes to find a solution to the Proof-of-Work algorithm. This means that to keep block generation time at 10 minutes the difficulty hash to be adjusted to account for these changes. Why 10 minutes? This is because after every 10 minutes a bitcoin block is generated. This is what underpins the frequency of currency issuance and the speed of transaction settlement. It should remain constant over many decades or at least all 21 million Bitcoins have been mined.

The Proof-of-Work target is adjusted to meet a 10-minute block interval goal. Simply it is set to the current mining power resulting in a 10-minute block interval. This is referred to as retargeting.
Retargeting occurs automatically on every node independently. After every 2016 block, all nodes retarget the PoW. Generally, if the network is finding blocks faster than expected, the difficulty increases(target decreases) and if finding blocks is slower the difficulty decreases(target increases). This is summarized using the following formula;

New Target = Old Target * (Actual Time of Last 2016 Blocks / 20160 minutes)

The folliwing code is used in the Bitcoin Core client for retargeting:

unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nFirstBlockTime, const Consensus::Params& params)
{
    if (params.fPowNoRetargeting)
        return pindexLast->nBits;

    // Limit adjustment step
    int64_t nActualTimespan = pindexLast->GetBlockTime() - nFirstBlockTime;
    if (nActualTimespan < params.nPowTargetTimespan/4)
        nActualTimespan = params.nPowTargetTimespan/4;
    if (nActualTimespan > params.nPowTargetTimespan*4)
        nActualTimespan = params.nPowTargetTimespan*4;

    // Retarget
    const arith_uint256 bnPowLimit = UintToArith256(params.powLimit);
    arith_uint256 bnNew;
    bnNew.SetCompact(pindexLast->nBits);
    bnNew *= nActualTimespan;
    bnNew /= params.nPowTargetTimespan;

    if (bnNew > bnPowLimit)
        bnNew = bnPowLimit;

    return bnNew.GetCompact();
}

We can confirm this here

In conclusion, the mining difficulty is closely related to the cost of electricity and bitcoin's exchange rate - the currency used to pay for electricity. Mining rigs convert electricity into hashing computation the primary influence being the price of a single kilowatt/hr of electricity in bitcoin. This is what determines the mining profitability of Bitcoin.

Summary

Each attempt produces a random outcome, this means we can calculate the probability of any possible outcome in advance. The outcome of a specific difficulty constitutes the proof of a specified amount of work done.
The difficulty of mining a bitcoin block takes 10 minutes of processing power for the entire network. This is based on the time it took to mine the previous 2016 blocks.
It is achieved by lowering or increasing the target.

References

Bitcoin PoW Implementation