8

Why this ugly looking formula to calculate 'target' from 'nBits' in block header: target = coefficient * 256**(exponent-3).

enter image description here

Why not? : target = coefficient * 256**(exponent). What is the need of subtracting 3. All we need is to be able to generate 256 bit long number and enough precision (which we already have with 3 bytes dedicated for coefficient)

Even better, why not? : target = coefficient * 2**(exponent)

8
+50

TL;DR The formula comes from turning an algorithm into a mathematical formula. nBits encodes the target with the first bytes as the size of the final target, followed by the 3 most significant bytes of that target. This can be converted into that crazy formula.


The formula is the mathematical representation of the actual algorithm that was used for the compression. To understand why the formula is as it is, we need to first take a look at the original code that encodes a 256 bit target as a 4 byte nBits. This is from 0.1.5 in the bitcoin/bitcoin source tree, but is the same in 0.1.0:

unsigned int GetCompact() const
{
    unsigned int nSize = BN_bn2mpi(this, NULL);
    std::vector<unsigned char> vch(nSize);
    nSize -= 4;
    BN_bn2mpi(this, &vch[0]);
    unsigned int nCompact = nSize << 24;
    if (nSize >= 1) nCompact |= (vch[4] << 16);
    if (nSize >= 2) nCompact |= (vch[5] << 8);
    if (nSize >= 3) nCompact |= (vch[6] << 0);
    return nCompact;
}

Now the first thing to look at is this BN_bn2pi function. Early versions of Bitcoin used OpenSSL's Bignum module for these calculations. So we need to look at the OpenSSL's docs for this function. From the docs, we read:

BN_bn2mpi() and BN_mpi2bn() convert BIGNUMs from and to a format that consists of the number's length in bytes represented as a 4-byte big-endian number, and the number itself in big-endian format, where the most significant bit signals a negative number (the representation of numbers with the MSB set is prefixed with null byte).

BN_bn2mpi() stores the representation of a at to, where to must be large enough to hold the result. The size can be determined by calling BN_bn2mpi(a, NULL).

This means that BN_bn2mpi will place into a buffer the Bignum in the format

<4 byte size> | <variable length number>

Calling BN_bn2mpi with NULL as the buffer will return the number of bytes that that buffer will need to be. This is useful to know how many bytes to allocate for the buffer.

So let's go back to the GetCompact function. We see BN_bn2mpi(this, NULL);. This means that nSize is now the size that is needed to encode the Bignum. Because this encoding also includes the size of the number itself, we later see nSize -= 4; which sets nSize to be the size of the actual number itself.

BN_bn2mpi(this, &vch[0]); now encodes the Bignum into vch which was set to the size specified by the first BN_bn2mpi call. It is important to remember that the first 4 bytes are the length of the number, so the actual number itself begins at index 4 (vch[4]).

Finally, the compact number itself is constructed. nSize << 24 is just to set the rightmost byte of nSize to be the leftmost byte of nCompact. Then the function is setting the rest of the compact number. Each byte is just being shifted to it's final position in the 4 byte int and OR'd with nCompact to set it. The if statements are for the case that the target is so low that it is encoded in fewer bytes than the compact size itself.

Looking at this function, we learn that the compact encoding is really just one byte indicating the length of the target, and 3 bytes for the 3 most significant bytes in that target. If you looked at the SetCompact function which takes a compact nBits and converts it into a Bignum, you would see that it is just the inverse of GetCompact, so I won't explain it.

Now the question is, how do we get to the crazy looking formula? How did we go from this code that strictly is just byte manipulation to a mathematical formula?

In your example, based on the above algorithm, we know that the final number is going to be 0x00ffff0000000000000000000000000000000000000000000000000000. We want the first 3 bytes, which we got from the nBits, to be by themselves, so let's divide this number by that:

0x00ffff0000000000000000000000000000000000000000000000000000 / 0x00ffff = 0x010000000000000000000000000000000000000000000000000000

Now 0x010000000000000000000000000000000000000000000000000000 is 26 bytes long, which we can see is because we've removed the first 3 bytes. Now how do we get this number from the nBits? We can take the first byte, representing the length of the full thing, and subtract 3 from it. Then to get that number, because there are 256 possible values in a byte, we do

256**(0x1d-3)

We can expand this further because 256 = 2**8 and some people like things represented as a power of 2. So this can become 2**(8*0x1d-3). Thus

0x010000000000000000000000000000000000000000000000000000 = 2**(8*0x1d-3)

Therefore:

0x00ffff0000000000000000000000000000000000000000000000000000 = 0x010000000000000000000000000000000000000000000000000000 * 0x00ffff = 2**(8*0x1d-3) * 0x00ffff

The final result is 2**(8*0x1d-3) * 0x00ffff. And, of course, this generalizes.


A semi-related question then is why does the Bignum encoding have a leading 0x00 byte? An encoding that represents this maximum target with a little bit more precision would have been 0x1cffffff so we could avoid this extraneous 0x00 byte.

That leading 0x00 byte is all because the Bignum is signed and the target is a positive integer. The most significant bit indicates whether it is negative. If the target had been encoded 0xffff...., then decoding this would mean that the target is negative, which is wrong. So the encoding puts a leading 0x00 so that the number remains positive.

| improve this answer | |
2

I'm only answering this question because I saw Murch had tweeted Andrew Chow's answer. I researched this a bit while writing my book, Programming Bitcoin, but it didn't make it into the book, so I thought this would be a good place to put it.

You can think of "bits" as a lossy compressed large base-256 number (that is, each 8-bit byte is a digit). The numbers we're talking about here are 32 digits as base-256 for a SHA256 (or HASH256) hash.

The "exponent" here is really just the length, in bytes, of the base-256 number we're compressing. The coefficient is the top three significant digits. As we want to be able to encode negative numbers, the top bit in particular is reserved to indicate a negative number. Thus, we put the 0-byte in front if the top bit is set (this is done, for example in the DER encoding).

Really, it's:

nBits = (top 3 digits) * 256^(digit length of base 256 number)

When you look at it that way, it's a little more logical.

| improve this answer | |
0

I don't know which paper you got this from, but I will attempt to answer your questions.

  1. The author simply decided to write 256 as a power of 2. This is a matter of preference. I haven't looked at the code itself, but either way, there should be very little overhead doing it this way. Perhaps, since this formula is in hexadecimal, it shouldn't have base-10 coefficients written in them as a matter of convention.
  2. The number 3 puts an upper bound on the hex digits h0 and h1. If it wasn't here, and h0 and h1 = 0xF (h0||h1 = 0xFF), the difficulty could reach such a high level that the developers never intended, and a block would never be found because it is nearly impossible to mine.
  3. 256 is the total number of combinations of a byte. Bitcoin doesn't work with values smaller than a byte, and it wouldn't gain any benefit from working at bit level, either. Making the difficulty target some power of 2 doesn't make a big difference since the network difficulty takes 2016 blocks to change, anyways. Working with bytes is easier in the code.
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.