difficulty – Why this ugly looking formula to calculate ‘target’ from ‘nBits’ in block header: target = coefficient * 256**(exponent-3)

[ad_1]

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

0x010000000000000000000000000000000000000000000000000000 is a 1 followed by 26 bytes of 0, so it’s 256**26 (256 since there are 256 possible values in a byte). 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.

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.

[ad_2]

Source link


Posted

in

by

Tags:

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *