Bitcoin’s fixed monetary supply – 21,000,000 bitcoins – is a fairly well-known fact these days, but there was a time when this wasn’t the case. In fact, until 2014 there was a major bug in Bitcoin that would have caused its supply to inflate forever.

If you read the hilarious and short BIP-42 you can get a little bit of insight into what the infinite inflation bug was:

As is well known, Satoshi was a master programmer whose knowledge of C++ was surpassed only by his knowledge of Japanese culture. The code below:

    int64_t nSubsidy = 50 * COIN;
    // Subsidy is cut in half every 210,000 blocks
    // which will occur approximately every 4 years.
    nSubsidy >>= (nHeight / 210000);

is carefully written to rely on undefined behaviour in the C++ specification – perhaps so it can be hardware accelerated in future.

While witty, this leaves less technical readers with a few outstanding questions. First, do we really have evidence of Satoshi’s mastery of Japaenese culture? Second, what is “undefined behaviour”? Finally, what is the “undefined behaviour” that is being relied on in this code? I thought I’d take a short post to answer these interesting questions. Along the way we’ll learn a bit about C++.

Undefined Behavior

The syntax and semantics of the C and C++ languages have for many decades now been defined by standards documents. A great laundry list of links to free drafts of C++ standards can be found here. These standards define the meaning of the various components of the C++ language. However, it is not uncommon for certain expressions in these programming languages to produce a class of behaviors dubbed “undefined”. Undefined behaviors are typically unambiguously bugs – things like accessing an array out of bounds or shifting an integer value beyond its bit range.

When such undefined behaviors are encountered by a compiler, it is left to the compiler writer’s discretion to determine how best to handle them. This means the program is technically allowed to do anything from crashing to opening a web socket and downloading a YouTube video when it encounters undefined behavior. Thankfully, most compiler writers are reasonable, and instead they usually attempt to keep your program functioning in the presence of these unsavory expressions.

The primary problem with writing programs that exhibit undefined behavior is that they immediately become non-portable. Since the standard does not define how the behavior could be handled, different compilers and even different versions of the same compiler or the same compiler targeting different platforms could all handle the behavior in completely different ways. This means that the program writer cannot know in advance what effect their code will have.

However, despite this lack of guarantee, there is often enough conformance between compilers that programmers can get the sense that such behavior is actually well-defined.

The Infinite Inflation Bug

So what was the undefined behavior exhibited by the inflation bug? We can demonstrate it to ourselves by writing a quick C++ program:

// satoshis_infinite_inflation_bug.cpp

#include <iostream>
#include <iomanip>
#include <stdint.h>
using namespace std;

int main(int argc, char* argv[]) {
  int64_t minerReward = INT64_MAX;

  for (int32_t shift = 0; shift < 128; shift++) {
    cout << "#"
         << std::dec << std::setw(3) << std::setfill('0')
         << shift
         << ": "
         << std::hex << std::setw(16) << std::setfill('0')
         << (minerReward >> shift) << endl;
  }

  return 0;
}

This program takes the largest possible 64-bit integer value and continually right shifts the value up to 128 bits. Since it only has 64 bits, this behavior is undefined once we shift more than 63 bits. You can then compile this against a C++ standard available at the time like so:

gcc -std=c++98 satoshis_infinite_inflation_bug.cpp -o satoshis_infinite_inflation_bug

Running the resulting program produces the following output:

#000: 7fffffffffffffff
#001: 3fffffffffffffff
#002: 1fffffffffffffff
#003: 0fffffffffffffff
#004: 07ffffffffffffff
#005: 03ffffffffffffff
#006: 01ffffffffffffff
#007: 00ffffffffffffff
#008: 007fffffffffffff
#009: 003fffffffffffff
#010: 001fffffffffffff
#011: 000fffffffffffff
#012: 0007ffffffffffff
... snip ...
#061: 0000000000000003
#062: 0000000000000001
#063: 0000000000000000
#064: 7fffffffffffffff
#065: 3fffffffffffffff
#066: 1fffffffffffffff
#067: 0fffffffffffffff
#068: 07ffffffffffffff
... snip ...

As you can see, once we completely shift out all of the bits at the 63rd right shift the behavior of this particular compiler (Apple LLVM version 9.1.0 (clang-902.0.39.2)) is to start over from the original value. In Bitcoin terms, this starts the inflation schedule all over again (whoops!).

We can prove to ourselves that this behavior is undefined by looking it up in the relevant C++98 standard. What we find in section 5.8 “Shift operators” is the following:

The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

And so, there we have it, by writing code that potentially shifts more than 63 bits to the right, Satoshi was eventually causing the program to exhibit undefined behavior. It’s likely that Satoshi imagined the behavior was similar to that of other systems and languages that handle this particular error by continuing to return 0 when over-shifted.

Thankfully BIP-42 found and fixed this error, ensuring that Bitcoin would run its monetary experiment with a fixed supply.

I hope you’ve enjoyed this brief tour and have learned a bit about why you should never rely on undefined behavior 🙂