The problem

SetCompact as currently implemented interprets the compact number 0x01810000 as -1 instead of 0x81, because it is implemented using BN_mpi2bn, which interprets the highest bit in the first byte of its input as sign and this is not compensated for. — Currently this is not a problem as none of the bitcoin-implementations I've looked at generate compact numbers with the 0x00800000 bit set. Many contain a matching bug in their compact encoding routines.

Satoshi:

• CBigNum.GetCompact(0x81) => 0x02008100

• CBigNum.SetCompact(0x01810000) => -1

  Defensive encoding. Decoding results in negative number with highest bit stripped.

bitcoinj:

• No compact encoding.

• Utils.decodeCompactBits(0x01810000) => -1

  Decoding will lead to Block::getDifficultyTargetAsInteger() throwing a VerificationException.

bitcoinjs:

• encodeDiffBits(0x80) => 0x02008000

• decodeDiffBits(0x01810000) => 0x81 (OK)

  Defensive encoding and correct decoding

libbitcoin:

• big_number::compact(0x80) => 0x02008000

• big_number::set_compact(0x01810000) => -1

  Defensive encoding. Decoding results in block_work() returning 0 and validate_block::check_proof_of_work returning false.

This branch

The first commit adds several test cases for GetCompact() and SetCompact(), including one showcasing the erroneous decoding.

The second commit reimplements GetCompact() and SetCompact() using shifts instead of going through the MPI-representation.

GetCompact() now is careful not to generate compact numbers with the 0x00800000 bit set (GetCompact(0xff) yields 0x0200ff00 instead of 0x01ff0000). It results in identical compact numbers for positive inputs as the old code.

SetCompact now interprets the compact number 0x01810000 as 0x81 instead of -1.

Is there a standard for the compact number representation? (if there is, link please)

If there is not (and, actually, maybe even if there is), then I would argue the implementation of BN_mpi2bn is the "bitcoin standard."

Also, re-defining anything in the block or transaction data has to be done extremely carefully to avoid blockchain splits.

@gavinandresen The problem is not that it doesn't follow some specification (afaik Satoshi invented this compact format), the problem is that the encode and decode functions are inconsistent with each other.

I agree we should think about changing functions involved in block validation very carefully of course...

@sipa It is not even that bad: Currently SetCompact() produces negative results for compact numbers with 0x00800000 bit set, whereas other implementations leave the bit set in their interpretation of the compact number or fail during verification. If a Satoshi client get's such a compact number it will pass it to CBigNum.getuint256, which will ignore the sign and thus interpret the compact number 0x08812345 as 0x0123450000000000 instead of 0x8123450000000000.

However, none of the implementations I've looked at actually generates such compact numbers and my proposed rewrite still makes sure not to generate them either. The effect of the rewrite is that ''if'' a future implementation would produce such a number it would be interpreted in the most likely intended way instead of effectively stripping the bit in a convoluted way.

The reason for proposing this change is that I'm going through the bignum and base58 implementation extending the test-suite and simplifying the implementation. This weird behavior of SetCompact was the first to trip-up my tests.

If we come to the conclusion not to accept this change, I'll change the test-suite accordingly.

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/3f0e14f5d2dd9671b2aa60b3dd5e3593fe47b3cf for binaries and test log.

My current understanding is that backwards compatibility of the block chain is paramount, even in cases like this one where no known implementation would be incompatible, so I'm retracting this pull request in favor of Pull Request #1825: Bignum2