[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

## Leave a Reply