Sunday, March 2, 2014

The programming error that cost Mt Gox 2609 bitcoins

In October 2011, Mt Gox lost over 2609 bitcoins by accidentally creating transactions that can never be redeemed. (At the time, 2609 bitcoins were worth about $8000, but they would be worth almost $1.5 million dollars now.) The problem was discussed on the Bitcoin forum, but I think it's worth taking a closer look at it in light of Mt Gox's recent massive bitcoin loss and bankruptcy. This problem reveals how easy it is to lose bitcoins through software errors. It also reveals that Mt Gox has made careless and expensive programming errors before.

The problem

When you send bitcoins to an address, what happens inside the Bitcoin transaction is more complicated than you would expect. The transaction contains a tiny computer program in the Bitcoin Script language, and this program is executed to determine if the bitcoins can be spent. Normally the program requires a public key and signature in order to spend the bitcoins. The program checks that the public key matches the address you sent the bitcoins to, and the signature is valid, proving the spender of the bitcoins has the private key. If everything matches, the bitcoins can be spent.

You might wonder why Bitcoin uses such a complex system to validate transactions. The idea is that by providing a programming language, Bitcoin allows many different types of transactions, such as escrow transactions or more complex contracts.

Going into a bit more detail, a typical scriptPubKey program looks like:


This program is part of a transaction that sent bitcoins to the address 1P9LHy6K2c9cwbfSfdaaoYVAprqUYtcFnB (which in hex is the f2e633... value above). In order for that address to redeem the bitcoins, they must provide the public key for the address 1P9L... and provide the signature for the spending transaction (which proves they have the private key). Walking through the execution of the program, it first duplicates the provided public key, computes the 160-bit hash of it, and verifies that it is equal to the provided public key address. Then it checks the signature for validity. If all goes well, the bitcoins can be spent. If there is a problem, the transaction is rejected.

In Mt Gox's bad transactions, they made a small but costly error. The script is:

Note that in place of the destination address hash, this transaction has the byte 0, representing OP_0, which pushes an empty array of bytes. Since it's impossible for the 160-bit hash to match an empty array, it's impossible for this script to complete successfully, and the bitcoins can never be spent. (For more information on how these scripts work, see my article Bitcoins the hard way).

Why does Bitcoin permit broken transactions?

You might wonder why Bitcoin permits transactions that can never be spent. Unfortunately, it would be very difficult to determine if a script can be satisfied or not. Bitcoin is designed to give people a lot of flexibility with the Script language, even though it's easy to shoot yourself in the foot. In addition, a complex algorithm to reject transactions would be very dangerous - if clients and miners disagree on the validity of a transaction, a blockchain fork will result, causing chaos.

(The computer scientists are probably yelling "halting problem" at this point. However, that doesn't apply because the Bitcoin Script language doesn't have loops so it's guaranteed to halt. A non-terminating script would be a disaster since miners and clients would lock up, so the language prohibits looping.)

In addition, it's common to lose bitcoins by using an address when you don't have the private key, and there's no way software could detect that. Strangely, people often do this on purpose. Many transactions deliberately send tiny amounts of bitcoins to bad addresses to hide text and images in the blockchain. Other people have deliberately lost over a million dollars in bitcoins in a Counterpary proof-of-burn.

Gold coins from the Fishpool Hoard. Unlike lost bitcoins, lost gold coins can sometimes be recovered.

Another interesting script bug

While analyzing coinbase transactions, I came across another interesting bug that lost bitcoins. Some transactions have the meaningless and unredeemable script:

That script turns out to be the ASCII text script. Instead of putting the redemption script into the transaction, the P2Pool miners accidentally put in the literal word "script". The associated bitcoins are lost forever due to this error.


Losing bitcoins due to programming errors is very easy. Mt Gox has lost thousands of bitcoins in the past this way, as have others. I don't know what happened to Mt Gox recently (although I know it wasn't OP_PUSHDATA2 malleability), but based on history it is worth keeping programming errors in mind.

If you want some scary reading describing other major Bitcoin losses, take a look at List of Major Bitcoin Heists, Thefts, Hacks, Scams, and Losses.

Sunday, February 23, 2014

Bitcoin mining the hard way: the algorithms, protocols, and bytes

This article explains Bitcoin mining in details, right down to the hex data and network traffic. If you've ever wondered what really happens in Bitcoin mining, you've come to the right place. My previous article, Bitcoins the hard way described how I manually created a Bitcoin transaction and sent it into the system. In this article, I show what happens next: how a transaction gets mined into a block.

The purpose of mining

Bitcoin mining is often thought of as the way to create new bitcoins. But that's really just a secondary purpose. The primary importance of mining is to ensure that all participants have a consistent view of the Bitcoin data. Because Bitcoin is a distributed peer-to-peer system, there is no central database that keeps track of who owns bitcoins. Instead, the log of all transactions is distributed across the network.

The main problem with a distributed transaction log is how to avoid inconsistencies that could allow someone to spend the same bitcoins twice. The solution in Bitcoin is to mine the outstanding transactions into a block of transactions approximately every 10 minutes, which makes them official. Conflicting or invalid transactions aren't allowed into a block, so the double spend problem is avoided.

Although mining transactions into blocks avoid double-spending, it raises new problems: What stops people from randomly mining blocks? How do you decide who gets to mine a block? How does the network agree on which blocks are valid? Solving those problems is the key innovation of Bitcoin: mining is made very, very difficult, a technique called proof-of-work. It takes an insanely huge amount of computational effort to mine a block, but it is easy for peers on the network to verify that a block has been successfully mined.[1]

Each mined block references the previous block, forming an unbroken chain back to the first Bitcoin block. This blockchain ensures that everyone agrees on the transaction record. It also ensures that nobody can tamper with blocks in the chain since re-mining all the following blocks would be computationally infeasible.[2] As long as nobody has more than half the computational resources, mining remains competitive and nobody can control the blockchain.

As a side-effect, mining adds new bitcoins to the system. For each block mined, miners currently get 25 new bitcoins (currently worth about $15,000), which encourages miners to do the hard work of mining blocks. With the possibility of receiving $15,000 every 10 minutes, there is a lot of money in mining.

How mining works

Mining requires a task that is very difficult to perform, but easy to verify. Bitcoin mining uses cryptography, with a hash function called double SHA-256. A hash takes a chunk of data as input and shrinks it down into a smaller hash value (in this case 256 bits). With a cryptographic hash, there's no way to get a hash value you want without trying a whole lot of inputs. But once you find an input that gives the value you want, it's easy for anyone to verify the hash. Thus, cryptographic hashing becomes a good way to implement the Bitcoin "proof-of-work".

In more detail, to mine a block, you first collect the new transactions into a block. Then you hash the block to form a 256-bit block hash value. If the hash starts with enough zeros[3], the block has been successfully mined and is sent into the Bitcoin network and the hash becomes the identifier for the block. Most of the time the hash isn't successful, so you modify the block slightly and try again, over and over billions of times. About every 10 minutes someone will successfully mine a block, and the process starts over.

The diagram below shows the structure of a specific block, and how it is hashed. The yellow part is the block header, and it is followed by the transactions that go into the block. The first transaction is the special coinbase transaction that grants the mining reward to the miner. The remaining transactions are standard Bitcoin transactions moving bitcoins around. If the hash of the header starts with enough zeros[3], the block is successfully mined. For the block below, the hash is successful: 0000000000000000e067a478024addfecdc93628978aa52d91fabd4292982a50 and the block became block #286819 in the blockchain.

Structure of a Bitcoin block

Structure of a Bitcoin block

The block header contains a handful of fields that describe the block. The first field in the block is the protocol version. It is followed by the hash of the previous block in the blockchain, which ensures all the blocks form an unbroken sequence in the blockchain. (Inconveniently, the hash is reversed in the header.) The next field is the Merkle root,[4] a special hash of all the transactions in the block. This is also a key part of Bitcoin security, since it ensures that transactions cannot be changed once they are part of a block.[5] Next is a (moderately accurate) timestamp of the block, followed by the mining difficulty value bits.[3] Finally, the nonce is an arbitrary value that is incremented on each hash attempt to provide a new hash value. The tricky part of mining is finding a nonce that works.


ASIC Bitcoin Miner
Photo by Mirko Tobias Schaefer, (CC BY 2.0)

A short program to mine a block

I wrote a Python program that mines the above block. The program itself is pretty simple - the hardest part of the code is computing the difficulty target from bits.[3] Otherwise it's just a loop over different nonce values. Each iteration puts the data into a structure, hashes it, and tests the result.

The following table shows the hash obtained for selected nonce values. The key point is that each nonce generates a basically-random hash value. Every so often a "lucky" nonce will generate a hash starting with some zeroes. To get a lot of zeroes, you need to try an exponentially large number of nonces. For this block, the "winning" nonce is 856192328.


I should point out that I cheated by starting with a block that could be successfully mined. Most of the attempts to mine a block will fail entirely - none of the nonce values will succeed. In that case, you need to modify the block slightly and try again. The timestamp can be adjusted (which is why the timestamp in mined blocks is often wrong). New transactions can be added to the block, changing the Merkle hash. The coinbase transaction can be modified - this turns out to be very important for mining pools. Any of these changes will result in totally different hashes, so the nonce values can be tried again.

My Python program does about 42,000 hashes per second, which is a million times slower than the hardware used by real miners. My program would take about 11 million years on average to mine a block from scratch.

Mining is very hard

The difficulty of mining a block is astounding. At the current difficulty, the chance of a hash succeeding is a bit less than one in 1019. Finding a successful hash is harder than finding a particular grain of sand from all the grains of sand on Earth. To find a hash every ten minutes, the Bitcoin hash rate needs to be insanely large. Currently, the miners on the Bitcoin network are doing about 25 million gigahashes per second. That is, every second about 25,000,000,000,000,000 blocks gets hashed. I estimate (very roughly) that the total hardware used for Bitcoin mining cost tens of millions of dollars and uses as much power as the country of Cambodia.[6]

Note that finding a successful hash is an entirely arbitrary task that doesn't accomplish anything useful in itself. The only purpose of finding a small hash is to make mining difficult, which is fundamental to Bitcoin security. It seems to me that the effort put into Bitcoin mining has gone off the rails recently.

Mining is funded mostly by the 25 bitcoin reward per block, and slightly by the transaction fees (about 0.1 bitcoin per block). Since the mining reward currently works out to about $15,000 per block, that pays for a lot of hardware. Per transaction, miners are getting about $34 in mining reward and $0.10 in fees (stats).

FPGA Bitcoin mining setup with 41 Icarus

15 GH/s FPGA Bitcoin mining configuration with 41 Icarus. Photo by permission of Xiangfu Liu

Mining with a pool

Because mining is so difficult, it is typically done in mining pools, where a bunch of miners share the work and share the rewards. If you mine by yourself, you might successfully mine a block and get 25 bitcoin every few years. By mining as part of a pool, you could get a fraction of a bitcoin every day instead, which for most people is preferable.

Mining pools use an interesting technique to see how much work miners are doing. They send out a block to be mined, and get updates from a miner whenever a miner gets a partial solution. Each partial solution proves the miner is working hard on the problem and gives the miner a share in the final reward when someone succeeds in mining the block.

For instance, if Bitcoin mining requires a hash starting with 15 zeroes, the mining pool can ask for hashes starting with 10 zeroes, which is a million times easier. Depending on the power of their hardware, a miner might find such a solution every few seconds or a few times an hour. Eventually one of these solutions will start with not just 10 zeroes but 15 zeroes, successfully mining the block and winning the reward for the pool.[7] The reward is then split based on each miner's count of shares as a fraction of the total, and the pool operator takes a small percentage for overhead.[8]

Most of the time someone outside the pool will mine a block first. In that case, the pool operator sends out new data and the miners just start mining the new block. People in a pool can get edgy if a long time goes without a payout because of bad luck in mining.

Stratum: The communication between a pool and the miners

Next I'll look in detail at the communication between a miner and the mining pool. The communication between the pool and the miners is interesting. The pool must efficiently provide work to the miners and collect their results quickly. The pool must make sure miners aren't duplicating work. And the pool must make sure miners don't waste time working on a block that has already been mined.

An important issue for mining pools is how to support fast miners. The nonce field in the header is too small for fast miners since they will run through all the possible values faster than the pool can send blocks. The solution is to allow miners to update the coinbase transaction so they can put additional nonces there. This makes mining more complicated since after building the coinbase transaction the miner must recompute the Merkle hash tree and then try mining the block.

I'm going to look at the Stratum mining pool protocol that is used by many pools. (Some alternative protocols are the Getwork and Getblocktemplate protocols.) The following Python program uses the Stratum protocol to make a mining request to the GHash.IO mining pool and displays the results. (This program is a minimal demonstration; don't use this code for real mining.)

The information below is what the mining pool sends back over the network in response to the program above. Since the Stratum protocol uses JSON-RPC the results are readable ASCII rather than the binary packets used by most of Bitcoin. This provides all the data needed to start mining as part of the pool:


The first line is a response from the pool server with the subscription details. The first values are not too important. The value 4bc6af58 is the value extranonce1 that is used when building the block. Each client gets a unique value to ensure that all the mining clients generate unique blocks and don't duplicate work. The following value (4 bytes) is the length of the extranonce2_size value that the miner puts in the coinbase while mining.

The second line is a mining.set_difficulty message to our client. With a difficulty of 16, I can get a share every hour or two on my PC. In comparison, the Bitcoin mining difficulty is 3,129,573,174.52[3] - thus it's about 200 million times easier to get a share in this pool than to successfully mine a block independently. That's why people join pools.

The third line is a mining.notify notification to our client. This message defines that block for us to mine. There's a lot of data returned under "params", so I'll explain it field by field.

merkle_branch["ea9da84d55ebf07f47def6b9b35ab30fc18b6e980fc618f262724388f2e9c591", ...]

The job_id is used to identify this mining task if the miner reports back success.

Most of the fields are used in the block header. The prevhash is the hash of the previous block. Apparently mixing big-ending and little-endian isn't confusing enough so this hash value also has every block of 4 bytes reversed. The version is the block protocol version. The nbits indicates the difficulty[3] of the block. The timestamp ntime is not necessarily accurate.

The coinb1 and coinb2 fields allow the miner to build the coinbase transaction for the block. This transaction is formed by concatenating coinb1, the extranonce1 value obtained at the start, the extranonce2 that the miner has generated, and coinb2. The result is a transaction in Bitcoin protocol. The merkle_branch hash list lets the miner efficiently recompute the Merkle hash with the new coinbase transaction.

clean_jobs is used if the miner needs to restart the mining jobs.

After receiving this data, the miner can start generating coinbase transactions and mining blocks.

Butterfly Labs Jalapeño

Butterfly Labs Jalapeño ASIC miner, 7+ GH/s, by 0xF2, (CC BY-ND 2.0)

Creating a block for a pool

Once the miner has received the information from the pool, it is straightforward to form the coinbase transaction by joining the coinb1, extranonce1, extranonce2, and coinb2 to form a coinbase transaction. The diagram below shows how the combination of these four values forms a complete transaction, with the nonces in the middle of the coinbase script. (The block below is slightly different from the one described earlier.)

A coinbase transaction generated by the mining pool

A coinbase transaction generated by the mining pool

The structure of the coinbase transaction is similar to a regular transaction, but there are a few important differences. A normal transaction transfers bitcoins from inputs (usually source addresses) to outputs (usually destination addresses). A coinbase transaction is generating new bitcoins out of thin air, rather than doing a transfer, so the transaction is slightly different. The previous output hash and index are irrelevant for the coinbase transaction. the first script is the scriptSig which signs the transaction to prove ownership of the incoming bitcoins. In a coinbase transaction, this is irrelevant, so instead the field is called the coinbase and is mostly arbitrary data.[9] (Many miners hide messages in there.) The value field in the coinbase transaction is the 25 bitcoin mining reward plus any bitcoins left over from the other transactions (the left over bitcoins are treated as mining fees). Finally, both regular transactions and the coinbase transaction use the second script (scriptPubKey) to specify the recipients of the bitcoins.[10] For details on transactions, see my my previous article.

Once the coinbase transaction is created, the hash for this coinbase transaction is combined with the merkle_branch data from the pool to generate the Merkle hash[4] for the entire set of transactions. Because of the structure of the Merkle hash (explained below), this allows the hash for the entire set of transactions to be recomputed easily.

Finally, the block header is built from the new Merkle hash and the data provided by the pool, and the hash algorithm can iterate over the nonce values in the header, just like the Python program earlier. Once all the nonce values have been tried, the miner increments the extranonce2, generates a new coinbase transaction and continues.

A Bitcoin block header

A Bitcoin block header

Informing the mining pool of success

The difficulty[3] for a mining pool is set much lower than the Bitcoin mining difficulty (fewer leading zeros required), so it's much easier to get a share. When a block is hashed to the pool's difficulty, you send a simple JSON message to the mining pool to submit it:
{"method": "mining.submit", "params": ["kens.worker1", "58af8db7", "00000000", "53058d7b", "e8832204"], "id":4}
The parameters are the worker name, job id, extranonce2, time, and header nonce. This information is sufficient for the pool to build the matching coinbase transaction and header, and verify the block. If the hash meets the pool difficulty, you get a share. If the hash also meets the much, much harder Bitcoin difficulty, the block has been successfully mined. In this case the pool submits the block to the Bitcoin network and everyone with shares gets paid accordingly.

Bitcoin mining op

Bitcoin mining setup by Austin Davis-Richardson. (CC BY-NC-SA 2.0)

Mining for fun and profit

If you're curious about mining, it's surprisingly easy to try out mining yourself, although you'll be lucky to earn even a penny. Just create an account at a mining pool such as BTC Guild, download mining software such as cpuminer (minerd.exe), and run the software to start mining. For a pool with low difficulty, you should get shares in a few minutes; in a pool with a higher difficulty (such as GHash.IO), it may take you an hour or two to get a share, which is more frustrating.[3]

Example of Bitcoin mining

Unprofitable Bitcoin CPU mining on my PC

The screenshot above shows what mining looks like as you get shares and blocks get mined. I got lucky and it only took me a minute to successfully mine a share. A minute later someone successfully mined a block, so the pool tells everyone to start over. Another block was mined less than a minute after that - although blocks are 10 minutes apart on average, the times can vary widely. It took 12 minutes for my next share to be generated. After running for a while, I earned 0.00000043 BTC, which is a tiny fraction of a cent.

Bitcoin mining is an "arms race". Originally people could mine with the CPU on a regular PC, but that hasn't been practical for a while. Next mining was offloaded to GPUs. Now, mining is done with special-purpose ASIC hardware, which is rapidly increasing in speed. For-profit mining is very competitive, and you'll need to look elsewhere for information.

If you want to try out mining just for fun, you may prefer to mine a currency such as Dogecoin rather than Bitcoin. First, Dogecoin uses a different hash algorithm which doesn't work well with ASIC hardware, so you're not as disadvantaged compared to professional miners. Second, because dogecoins are worth much less than bitcoins, you'll end up with a much larger number of dogecoins, which seems more rewarding. For Dogecoin mining, I used the pool somewhat arbitrarily. The process is almost the same as Bitcoin mining, except you use the scrypt algorithm instead of sha256d. There are many other alternative cryptocurrencies to choose from.

Notes and references

[1] Bitcoin mining seems like a NP (nondeterministic polynomial) problem since a solution can be quickly verified. However, there are a couple of issues with making this rigorous. First, since hashes are a fixed size, mining can be done in constant time (but with a very large constant of 2^256). Thus, you'd need to consider an extended mining scheme where the difficulty can go to infinity. Second, mining would need to be turned into a decision problem - e.g. instead of finding a nonce, the problem would be "Is there a successful nonce less than k". (Note that if you can solve that problem, you can rapidly find the nonce with binary search.)

With these changes, the mining problem is in NP. The next question is if it is NP-complete. That is, can an arbitrary NP-complete problem be turned into a mining problem? I believe that is currently unknown.

[2] You might wonder what happens if two miners succeed in mining a block at approximately the same time. Has the problem of conflicting transactions has just been replaced by the problem of conflicting blocks?) The rule is that only the longest chain of valid blocks is used, and the other branch is ignored. Thus, when a miner extends the chain with one of the two parallel blocks, the other block becomes an orphan block and is ignored.

Orphan blocks are fairly common, roughly one a day. For this reason, the (somewhat arbitrary) recommendation is to wait for six confirmations (about one hour) before considering a transaction solidly confirmed.

[3] I've been describing a successful hash as starting with enough zeros, but there's an official definition of difficulty. A valid block must have a hash below a target value. (Since the target starts with a bunch of zeros, so will the valid hash.)

There are two different hard-to-understand ways of representing the target. The first, bits is a mantissa/exponent representation of the target in 32 bits. The second, difficulty is the ratio between a base target and the current target. A difficulty of N is N times as difficult as this base target. The base target is 0x00000000FFFF0000000000000000000000000000000000000000000000000000, which corresponds to approximately 1 in 232 or 1 in 4.2 billion hashes succeeding.

Difficulty changes approximately every two weeks to keep the block hash rate around 1 every 10 minutes. The difficulty value is 3,129,573,174.52, corresponding to a target of 00000000000000015f5300000000000000000000000000000000000000000000. Multiplying my PC's performance by the current difficulty shows it would take my PC about 35,000 years to mine a block.

The pool difficulty is important when using a mining pool. My PC can do about 12 million hashes/sec running cpuminer, so at a difficulty of 1 my PC could find a block every 6 minutes. The BTC Guild pool uses a difficulty of 2, so I get a share about every 12 minutes. GHash.IO has a minimum difficulty of 16 on the other hand, so I only get a share every hour or two on the average. (My overall earnings would be similar either way, since the shares per block scale inversely with the difficulty.)

[4] Instead of hashing all the transactions into the block directly, the transactions are first hashed together to yield a Merkle root. The Merkle root is the root of a binary Merkle tree. The idea is to start with all the transaction hashes. Pairs of hashes are hashed together to yield new hashes. The process is repeated on the new list of hashes and continues recursively until a single hash is obtained. This final root hash is the value used when computing the block. (See Wikipedia for more details.)

In the Merkle tree, each transaction is hashed. Then pairs of hashes are hashed together. Then pairs of the new hashes are hashed together, and so on, until a single hash remains. This allows the hash of a single transaction to be verified efficiently without recomputing all the hashes. One place this comes in useful is generating a new coinbase transaction for a mining pool.

The (patented) idea of a Merkle tree is if you need to modify or verify a single transaction, you don't need to recompute everything, but can just recompute the affected pairs. Personally, I think the Merkle tree is a pointless optimization for Bitcoin and for reasonable transaction numbers it would be faster to do a single large hash, rather than multiple hashes up the Merkle tree.

Here's some demonstration code to compute the Merkle root for the block I'm discussing. The 99 transaction hashes are hard-coded for convenience. The resulting Merkle root is 871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a29978a

[5] There are a few ways that third parties can modify transactions without invalidating the signature on the transaction. This is known as transaction malleability. These modifications change the hash of the transaction. Since the hash is part of the block, a transaction has a fixed hash and cannot be modified by malleability once it has been mined into a block. (Unless the whole block is orphaned, of course.)

[6] It's hard to estimate the cost of mining because the hardware is changing so rapidly and it's unclear what is actually in use, but I'll do a rough calculation. Looking at the Bitcoin mining hardware and Mining hardware comparison pages, the HashBlaster looks like the most efficient currently available at 375 MH/s/$ and 1818 MH/s/W. The Bitcoin network is 25 billion MH/s, which works out to about $70 million hardware cost and 15 MW. (This is about the total power consumption of Cambodia.) At $0.15/kWH, that would be about $50,000/day on electricity ($300 per block or $0.70 per transaction). Since mining generates about $140,000 per day, spending $50,000 per day on electricity seems like the right ballpark. Other estimates are at Hacker News.

[7] You might wonder why a miner doesn't cheat. If they successfully mine a block, why not submit it themselves so they can claim the full mining reward, rather than splitting it? The main reason is the coinbase transaction has the pool's address, not the miner's address. If the miner submits the block bypassing the pool, the reward still goes to the pool. And if the miner changes the address, the hash is no longer valid.

[8] There are several different reward systems used by mining pools. For instance, a pool can pay out the exact amount earned from a block or an average amount. Or a pool can pay a fixed amount per share. A pool can weight shares by time to avoid miners switching between pools mid-block. These different systems can balance risk between the miners and the pool operator and adjust the variance of payments. For details, see the Bitcoin wiki here or here.

[9] I've figured out a lot of the structure of the coinbase script above. First it contains the block height (0x046063 or 286819), which is required for version 2). Next is the string '/P2SH/' which indicates the miner supports Pay To Script Hash). This is followed by a timestamp. Next is 8 bytes of the two nonces. This is followed by apparently-random data and then the text "Happy NY! Yours GHash.IO".

[10] The typical coinbase script format has changed over time. Originally, the output scripts were all pay-to-pubkey, with the script: public_key OP_CHECKSIG. This script puts the public key itself in the script. However, now about 95% of coinbase transactions use the standard pay-to-pubkey-hash script: OP_DUP OP_HASH160 addr OP_EQUALVERIFY OP_CHECKSIG. This script only includes the public key hash (the address) and requires the redeemer to provide the public key. To see the difference, compare the output scripts in this transaction and this transaction.

Sunday, February 16, 2014

Hidden surprises in the Bitcoin blockchain and how they are stored: Nelson Mandela, Wikileaks, photos, and Python software

Every Bitcoin transaction is stored in the distributed database known as the Bitcoin blockchain. However, people have found ways to hack the Bitcoin protocol to store more than just transactions. I've searched through the blockchain and found many strange and interesting things - from images to source code in JavaScript, Python, and Basic. If you're running a Bitcoin client, you probably have all this data stored on your system.[1]

Nelson Mandela tribute

The Bitcoin blockchain contains this image of Nelson Mandela and the tribute text. Someone encoded this data into fake addresses in Bitcoin transactions, causing it to be stored in the Bitcoin system.

Image of Nelson Mandela found in the Bitcoin blockchain.

Nelson Mandela (1918-2013)
"I am fundamentally an optimist. Whether that comes from nature or nurture, I cannot say. Part of being optimistic is keeping one’s head pointed toward the sun, one’s feet moving forward. There were many dark moments when my faith in humanity was sorely tested, but I would not and could not give myself up to despair. That way lays defeat and death."
"I learned that courage was not the absence of fear, but the triumph over it. The brave man is not he who does not feel afraid, but he who conquers that fear."
"Difficulties break some men but make others. No axe is sharp enough to cut the soul of a sinner who keeps on trying, one armed with the hope that he will rise even in the end."
"It always seems impossible until it’s done."
"When a man has done what he considers to be his duty to his people and his country, he can rest in peace."
"Real leaders must be ready to sacrifice all for the freedom of their
"Everyone can rise above their circumstances and achieve success if they are dedicated to and passionate about what they do."
"Education is the most powerful weapon which you can use to change the world."
"For to be free is not merely to cast off one’s chains, but to live in a way that respects and enhances the freedom of others."
"There is no passion to be found playing small – in settling for a life that is less than the one you are capable of living."
“There is nothing like returning to a place that remains unchanged to find the ways in which you yourself have altered.” -Nelson Mandela

The data is stored in the blockchain by encoding hex values into the addresses. Below is an excerpt of one of the transactions storing the Mandela information. In this transaction, tiny amounts of bitcoins are being sent to fake addresses such as 15gHNr4TCKmhHDEG31L2XFNvpnEcnPSQvd. This address is stored in the blockchain as hex 334E656C736F6E2D4D616E64656C612E6A70673F. If you convert those hex bytes to Unicode, you get the string 3Nelson-Mandela.jpg?, representing the image filename. Similarly, the following addresses encode the data for the image. Thus, text, images, and other content can be stored in Bitcoin by using the right fake addresses.

Secret message in the first Bitcoin block

It is well known that the Genesis block, the very first block of data in Bitcoin contained a "secret" message. This message was stored in the coinbase[2], a part of a Bitcoin block that is filled in by the miner who mines a Bitcoin block. Along with the standard data, the original transaction also contains the message: 'The Times 03/Jan/2009 Chancellor on brink of second bailout for banks'[3]. Presumably this is a political commentary on Bitcoin compared to the insolvency of "real" banks.

Bitcoin logo

People rapidly figured out how to encode arbitrary content into the Bitcoin blockchain by using hex data in place of Bitcoin addresses.[4] One of the first uses of this technique was to store the Bitcoin logo in the blockchain. I extracted the following image from the blockchain, where it was hidden among normal transactions.[5]

Image found in the Bitcoin blockchain: Bitcoin logo

The Bitcoin logo, hidden in the blockchain.

Prayers from miners

Early on, the miner Eligius started putting Catholic prayers in English and Latin in the coinbase field of blocks they mined. Here are some samples:
Benedictus Sanguis eius pretiosissimus.
Benedictus Iesus in sanctissimo altaris Sacramento.
Ave Maria, gratia plena, Dominus tecum. Benedicta tu in mulieribus, ...
...and life everlasting, through the merits of Jesus Christ, my Lord and Redeemer.
O Heart of Jesus, burning with love for us, inflame our hearts with love for Thee.
Jesus, meek and humble of heart, make my heart like unto thine!
These prayers turned out to be surprisingly controversial, leading to insults being exchanged through the blockchain: "Oh, and god isn't real, sucka. Stop polluting the blockchain with your nonsense.", "FFS Luke-Jr leave the blockchain alone!", and a rickroll in response: "Militant atheists, -- happy now?".[6]

The codebase technique has since been used by many other miners as advertising. Typical messages are: Hi from, For Pierce and Paul, Mined at, EclipseMC: Aluminum Falcon?, Happy NY! Yours GHash.IO, Mined By ASICMiner, BTC Guild, Made in China, BitMinter, /bitparking, hi from poolserverj, /ozcoin/stratum/, /slush/.[7]

XSS demo

I've found JavaScript code in the blockchain that demonstrates a potential XSS attack. A common security hole on websites is cross-site scripting (XSS)[8], where an attacker can inject hostile JavaScript into a web page viewed by the victim. Surprisingly, such an attack was possible with Bitcoin. The transaction's output script was set to the hex corresponding to:
<script>window.alert("If this were an actual exploit, your mywallet would be empty.")</script>
Apparently some Bitcoin websites would fail to escape the tags, causing the script to run if you viewed the page. The above script just created a harmless dialog box, but a more malicious transaction could potentially steal the user's bitcoins stored on the website.

Len Sassaman Tribute

A tribute to cryptographer Len Sassaman was put in the Bitcoin blockchain a couple weeks after his death by Dan Kaminsky.[9]
:.: :.' ' ' ' ' : :
:.:'' ,,xiW,"4x, ''
:  ,dWWWXXXXi,4WX,
' dWWWXXX7"     `X,
 lWWWXX7   __   _ X
:WWWXX7 ,xXX7' "^^X
lWWWX7, _.+,, _.+.,
:WWW7,. `^"-" ,^-'
 WW",X:        X,
 "7^^Xl.    _(_x7'
 l ( :X:       __ _
 `. " XX  ,xxWWWWX7
  )X- "" 4X" .___.
,W X     :Xi  _,,_
WW X      4XiyXWWXd
"" ,,      4XWWWWXX
, R7X,       "^447^
R, "4RXk,      _, ,
TWk  "4RXXi,   X',x
lTWk,  "4RRR7' 4 XH
:lWWWk,  ^"     `4
::TTXWWi,_  Xll :..
Len was our friend.
A brilliant mind,
a kind soul, and
a devious schemer;
husband to Meredith
brother to Calvin,
son to Jim and
Dana Hartshorn,
coauthor and
cofounder and
Shmoo and so much
more.  We dedicate
this silly hack to
Len, who would have
found it absolutely
--Dan Kaminsky,
Travis Goodspeed
P.S.  My apologies,
BitCoin people.  He
also would have
LOL'd at BitCoin's
new dependency upon
: :.: ' ' ' ' : :':
:.:     _.__    '.:
:   _,^"   "^x,   :
'  x7'        `4,
 XX7            4XX
 XX              XX
 Xl ,xxx,   ,xxx,XX
( ' _,+o, | ,o+,"
 4   "-^' X "^-'" 7
 l,     ( ))     ,X
 :Xx,_ ,xXXXxx,_,XX
   4XXi,_   _iXX7'
  , `4XXXXXXXXX^ _,
  Xx,  ""^^^XX7,xX
W,"4WWx,_ _,XxWWX7'
Xwi, "4WW7""4WW7',W
TXXWw, ^7 Xk 47 ,WH
:TXXXWw,_ "), ,wWT:

A creature simulator in Basic

I found a simple character-based simulator in Basic. The idea is 5 creatures wander around the screen eating food blocks and breeding or dying. Unfortunately the code has a bunch of bugs and doesn't work.[10]

The original Bitcoin paper

In this transaction the Bitcoin blockchain contains the PDF for the original Bitcoin paper.

Thumbnail of the original Bitcoin paper.

Thumbnail of the original Bitcoin paper.


Rickrolling is a popular internet prank, and Bitcoin is not immune. One rickroll was described above as part of the prayer dispute.[6] The lyrics to Never Gonna Give You Up! are found in a second rickroll.[11]

A third rickroll has the song metadata and lyrics encoded in Base-64.[12]

Catagory: Poetry
Title: Never Gonna Give You Up
Performer: Rick Astley
Writer: Mike Stock, Matt Aitken, Pete Waterman
Label: RCA Records
Released: 27, July, 1987

We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy
I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up,
Never gonna let you down
Never gonna run around and desert you

Photographs in a messaging system

Recently someone has built a message/storage system on top of Bitcoin that allows a growing sequence of messages, text, and images to be stored in the blockchain.[13]

Among other things, this system contains text from the Bhagavad Gita, 1000 digits of pi, multiple JPG and PNG images, a Shel Silverstein poem, a Rumi poem, and quotes from a random party. Here are some of the images stored in the blockchain using this system:

EMBIICompressedLogo.png: Image found in the Bitcoin blockchain. KruseEMBII.jpg: Image found in the Bitcoin blockchain. EhrichWeAreStarStuff.jpg: Image found in the Bitcoin blockchain. DriveHugPuddle.jpg: Image found in the Bitcoin blockchain. ILoveYouMore.jpg: Image found in the Bitcoin blockchain.

Some images found in the Bitcoin blockchain.

Wikileaks cablegate data

A 2.5 megabyte Wikileak files ('cablegate-201012041811.7z') was embedded in the Bitcoin blockchain.[14] The data is followed by a message explaining how to access it.[15]
Wikileaks Cablegate Backup


Download the following transactions with Satoshi Nakamoto's download tool which
can be found in transaction 6c53cd987119ef797d5adccd76241247988a0a5ef783572a9972e7371c5fb0cc

Free speech and free enterprise! Thank you Satoshi!

... 128 lines of transaction ids deleted ...
Downloading the data from the blockchain is inconvenient since the download tool needs to be used on the 130 chunks of 20 KB separately. (It's much easier to download the file from the internet.)

Cablegate data stored in Bitcoin

The blockchain contains the source code for Python tools to insert data into the blockchain and to download it.[16] In a weird self-referential twist, the downloader can be used to download itself. The uploader/downloader puts data into the destination address, but extends the previous technique by using Bitcoin escrow / multi-sig to put three addresses in each destination. It also uses a checksum to make storage more reliable.

Here's the code in the blockchain to insert data into the blockchain. While it says it was written by Satoshi Nakamoto (the pseudonymous author of Bitcoin), that's probably not true.

And here's the code to extract data from the blockchain.
The download tool is slightly buggy - the crc32 has a signed-vs-unsigned problem which suggests it wasn't used extensively.

Leaked firmware key and illegal primes

This transaction has a link about a leaked private key, followed by 1K of hex bytes as text, which supposedly is the private key for some AMI firmware.

The change from that transaction was used for this transaction, which references the Wikipedia page on illegal primes, followed by two supposedly-illegal primes from that page.

The change from that transaction was then used for the Wikileaks Cablegate messages, implying the same person was behind all these messages. It looks like someone was trying to store a variety of dodgy stuff in the Bitcoin blockchain, either to cause trouble or to make some sort of political point.

Email from Satoshi Nakamoto

The following email message allegedly from Bitcoin inventor Satoshi Nakamoto appears in the blockchain.[17] (It's almost certainly not really from him.) It seems to be referring to the removal of some Script opcodes from the Bitcoin server earlier and making the corresponding change to the Electrum server. My guess is this message is someone pointing out a bug fix for Electrum in a joking way.
From a3a61fef43309b9fb23225df7910b03afc5465b9 Mon Sep 17 00:00:00 2001
From: Satoshi Nakamoto <>
Date: Mon, 12 Aug 2013 02:28:02 -0200

I removed this from Bitcoin in f1e1fb4bdef878c8fc1564fa418d44e7541a7e83
in Sept 7 2010, almost three years ago. Be warned that I have not
actually tested this patch.
 backends/bitcoind/ |    8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)

diff --git a/backends/bitcoind/ b/backends/bitcoind/
index 6620583..89b9b1b 100644
--- a/backends/bitcoind/
+++ b/backends/bitcoind/
@@ -280,10 +280,8 @@ opcodes = Enumeration("Opcodes", [
     "OP_WITHIN", "OP_RIPEMD160", "OP_SHA1", "OP_SHA256", "OP_HASH160",
-    ("OP_SINGLEBYTE_END", 0xF0),
-    ("OP_DOUBLEBYTE_BEGIN", 0xF000),

@@ -293,10 +291,6 @@ def script_GetOp(bytes):
         vch = None
         opcode = ord(bytes[i])
         i += 1
-        if opcode >= opcodes.OP_SINGLEBYTE_END and i < len(bytes):
-            opcode <<= 8
-            opcode |= ord(bytes[i])
-            i += 1

         if opcode <= opcodes.OP_PUSHDATA4:
             nSize = opcode

Text in Bitcoin addresses

Bitcoin addresses are 34 characters long, so it is possible to put something interesting in the text address, although there are limitations.

The first option for putting text into an address is to test millions or billions of private keys by brute force in the hope of randomly getting a few characters you want in the public address. This generates a "vanity" address which is a valid working Bitcoin address. An example is Bitcoin Armory, which uses the donation address 1ArmoryXcfq7TnCSuZa9fQjRYwJ4bkRKfv. Note that only six desirable characters were found, and the rest are random. You can use the vanitygen command-line tool or a website like bitcoinvanity to generate these addresses.

Many people have recently received tiny spam payments from vanity addresses with the prefixes 1Enjoy... and 1Sochi... addresses. These payments don't get confirmed by miners and the purpose of them is puzzling.

The second option is to use whatever ASCII address you want (starting with a 1 and ending with a six-character checksum). Since there is no known private key for this address, any bitcoins sent to this address are lost forever. Despite this, some addresses have received significant amounts: 1BitcoinEaterAddressDontSendf59kuE. has received over 1.6 bitcoins (over $1000). 1111111111111111111114oLvT2 (hex 0) has received almost 3 bitcoins.

A very strange activity is the large-scale deliberate "burning" of bitcoins by sending them to 1CounterpartyXXXXXXXXXXXXXXXUWLpVr, where nobody can ever use them. Amazingly, this address has received over 2,130 bitcoins (about $1.5 million dollars worth) that are now lost forever. The motivation is that Counterparty is issuing their own crypto-currency (XCP) in exchange for destroyed bitcoins. The idea is that "proof-of-burn" is a more fair way of distributing currency than mining.

Mysterious encrypted data in the blockchain

There are many mysterious things in the blockchain that I couldn't figure out, that appear to be encrypted data.

Between June and September 2011, there were thousands of tiny mystery transactions from a few addresses to hundreds of thousands of random addresses sorted in decreasing order. These transactions are for 1 to 45 Satoshis, and have never been redeemed. As far as I can tell, the data is totally random. But maybe there is a secret message in the addresses or in the amounts. In any case, somewone went to a lot of work to do this, so there must be some meaning. [20]

One interesting thing is that the change address from the cablegate description was then used for three 86 kilobyte GPG-encoded files.[18] From the "magic numbers" at the beginning of these files I know that these are GPG files encrypted using CAST5, but what is in these files is a mystery. Without the passphrase, they can't be decrypted.

By following the change addresses, we can see that after submitting the "Satoshi" uploader and downloader, the same person submitted the Bitcoin PDF. The same person then submitted five mysterious files.[19] These files appear entirely random, so they may contain encrypted data.

Valentine's day messages

There are a bunch of Valentine's day messages in the blockchain from a couple days ago. I assume someone set up a service to do this.

How to put your own message in the blockchain

It's pretty easy to put your own 20-character message into the blockchain. The following steps explain how.
  1. Take your 20-character string and convert it to hex. E.g. in Python:
  2. Convert the resulting hex string to an address. An easy way is online: hex value yields 1AXJnNiDijKUnY9UJZkV5Ggdgh36aWDBYj.
  3. Send bitcoins to that address and your message will show up in the blockchain when your transaction gets mined. Important: those bitcoins will be lost forever, so send a very small amount, like 10 cents. My test message can be seen at the end of blk00113 here.


People have found a variety of ways to store strange things in the Bitcoin blockchain. I have touched on some of them here, but undoubtedly there are many other hidden treasures.

The notes to this article provides hashes for the interesting transactions, in case anyone wants to investigate further.

ASCII image of Bernanke from the Bitcoin blockchain.

ASCII image of Bernanke from the Bitcoin blockchain.

Notes and references

[1] Clients store the 16-gigabyte blockchain in the data directory. On Windows, this is C:\Users\userid\AppData\Roaming\Bitcoin. The blocks are stored in a sequence of 128 megabyte files blknnnnnn.dat. Syncing these files is why a full Bitcoin client takes hours to start up.

An easy way to see the ASCII contents of the blockchain is to visit

[2] In the Bitcoin protocol, every mined block has a transaction that creates new bitcoins. Part of that transaction is an arbitrary coinbase field of up to 100 bytes in the Script language. Normally the coinbase field has data such as the block number, timestamp, difficulty, and an arbitrary nonce number.

The full coinbase in the genesis block is:

bits value (mining difficulty): FFFF001D
nonce value: 04
'The Times 03/Jan/2009 Chancellor on brink of second bailout for banks': 5468652054696D65732030332F4A616E2F32303039204368616E63656C6C6F72206F6E206272696E6B206F66207365636F6E64206261696C6F757420666F722062616E6B73

[3] The message in the Genesis block is slightly different from the actual newspaper article: Chancellor Alistair Darling on brink of second bailout for banks.

[4] A brief overview of Bitcoin addresses will make this technique easier to understand. Normally, you start with a random 256-bit private key, which is necessary to redeem Bitcoins. From this, you generate a public key, which is hashed to a 160-bit address. This address is displayed in ASCII using a technique called Base58Check encoding. This ASCII address, such as 1LLLfmFp8yQ3fsDn7zKVBHMmnMVvbYaAE6, is the address used for transferring Bitcoins. But inside the transaction, the address is stored as the 160-bit (20 byte) hex value.

In normal use, you have no control over the 20-byte hex value used as an address. The trick for storing data in the transaction is to replace the address with 20 bytes of data that you want to store. For instance, the string This is my test data turns into the hex data '54686973206973206d7920746573742064617461'. If you send some bitcoins to that address, the bitcoins are lost forever (since you don't have the private key matching that address), but your message is now recorded in the Bitcoin blockchain.

See my earlier article for details on how Bitcoin addresses are generated.

[5] The Bitcoin logo was hidden in two transactions: ceb1a7fb57ef8b75ac59b56dd859d5cb3ab5c31168aa55eb3819cd5ddbd3d806 and 9173744691ac25f3cd94f35d4fc0e0a2b9d1ab17b4fe562acc07660552f95518.

If you look at the first ScriptPubKey of the first transaction, the address is 3d79626567696e206c696e653d3132382073697a, which turns into the ASCII text =ybegin line=128 siz. If you do this for all the addresses, you get an ecoded file. This file turns out to be encoded in the obscure yEnc encoding, designed in 2001 for transmitting binaries on Usenet. I hacked together some code to extract and decode the file, resulting in the bitcoin.jpg file shown above. There was some discussion of this logo in 2011, but I don't know if anyone has actually extracted the image until now.

[6] The prayers can be found in blk00003 and blk00004. Eligius is appropriately named after Saint Eligius the patron saint of goldsmiths and coin collectors. The Rickroll is here.

[7] For a while, the mysterious message /P2SH/ appeared in the coinbase field over and over. This string is an indication that the miner supports the pay-to-script-hash Bitcoin feature. The purpose of this was to ensure that more than 50% of the miners supported the feature before it was rolled out.

[8] The XSS attack demo is in transaction 59bd7b2cff5da929581fc9fef31a2fba14508f1477e366befb1eb42a8810a000. The JavaScript for the attack was put in the transaction's output script. The website displays the contents of the output script, but apparently didn't escape it as HTML. Thus, the contents <script> would not be displayed as text, but would be executed as part of the page. The demo only popped up an alert box, rather than running malicious JavaScript. The creator of the attack describes it on Reddit.

[9] A talk presents some details on the tribute (here). The data is in transaction 930a2114cdaa86e1fac46d15c74e81c09eee1d4150ff9d48e76cb0697d8e1d72. This tribute cost 1 BTC, 0.01 BTC per line.

[10] The Basic code is in block 3a1c1cc760bffad4041cbfde56fbb5e29ea58fda416e9f4c4615becd65576fe7, and it is stored in "uploader" format, with a donation to Satoshi's genesis block address 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa.

Unfortunately the code is a mess with GOSUBs without RETURNs, broken loops, half-implemented ideas, and unused variables, so the code doesn't work, which is disappointing. It's a mystery why someone would put this BASIC code into the blockchain.

[11] The Rick Astley lyrics are in transaction d29c9c0e8e4d2a9790922af73f0b8d51f0bd4bb19940d9cf910ead8fbe85bc9b. This data is included using the OP_RETURN technique, which was later supported as a non-hacky way to put data into the blockchain.

[12] The third rickroll has the data encoded in a structured format, maybe from some music database. The data format is base-64 metadatabase-64 lyrics The transaction is 0b4efe49ea1454020c4d51a163a93f726a20cd75ad50bb9ed0f4623c141a8008.

[13] The messaging system references "AtomSea & EMBII", who I assume are the creators. The chain started with address 12KPNWdQ3sesPzMGHLMHrWbSkZvaeKZgHt with 0.269 BTC on 2013-12-01 23:54:35 Each output is 0.000055 bitcoins, just over the current network minimum of .0000546 bitcoin. The next transaction in the chain can be found by looking at each change address, which pays for the next block. The chain ended when it ran out of bitcoins, at address 1DQwj8BDLWy9BMzX8uUcDYze3hx8q7uBy4.

In total, the data chain has 85KB of data including images, random quotes, and HTML. The system embeds filenames, lengths, and the data. There are also a lot of transaction ids stored in the data, presumably serving as an index.

[14] The 2.5 megabyte Cablegate file was stored in 130 separate transactions each holding 20,000 bytes of data, transactions 5c593b7b71063a01f4128c98e36fb407b00a87454e67b39ad5f8820ebc1b2ad5 to 2663cfa9cf4c03c609c593c3e91fede7029123dd42d25639d38a6cf50ab4cd44#o6". Each transaction includes a trivial 0.00000001 bitcoin donation to the Wikileaks donation address 1HB5XMLmzFVj8ALj6mfBsbifRoD4miY36v. This data is stored in checksummed download tool format.

[15] The cablegate description is in 691dd277dc0e90a462a3d652a1171686de49cf19067cd33c7df0392833fb986a, and is stored in "uploader" format. It's a bit circular that this message describes where to find the download tool, but the message itself needs the download tool to be read. Fortunately it's not too hard to read the message without the tool.

[16] The uploader is in transaction 4b72a223007eab8a951d43edc171befeabc7b5dca4213770c88e09ba5b936e17". The downloader is in transaction 6c53cd987119ef797d5adccd76241247988a0a5ef783572a9972e7371c5fb0cc.

In a cute touch, these transactions both donate 0.00000001 bitcoins to address 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa, which is Satoshi Nakamoto's address from the Genesis Block.

[17] This transaction, 77822fd6663c665104119cb7635352756dfc50da76a92d417ec1a12c518fad69 has an unusual scriptPubKey: OP_IF OP_INVALIDOPCODE 4effffffff 1443 bytes of data OP_ENDIF.

[18] The encrypted GPG files are in transactions 7379ab5047b143c0b6cfe5d8d79ad240b4b4f8cced55aa26f86d1d3d370c0d4c#o448, d3c1cb2cdbf07c25e3c5f513de5ee36081a7c590e621f1f1eab62e8d4b50b635#o448, and cce82f3bde0537f82a55f3b8458cb50d632977f85c81dad3e1983a3348638f5c.

[19] To "follow the money", the PDF transaction put change into address 1HT8vpTV1wj2ck6jgW7my6vCtJQv14Cdp. This address funded the embedding of a 10KB mystery file in this transaction. The change from that was used for another file here, followed by this, this, and this. These uploaded file transactions all included 0.001 BTC donations to 1JVQw1siukrxGFTZykXFDtcf6SExJVuTVE, the address.

[20] Some addresses associated with the mystery transactions are: 18qr2srETSvQq4kP7yBYRqQ4LzmjhtRmcD, 1MaZAHzEFfinRJ2dwK6YtNDfvWMBkiAxDr, 1AgwESN7RKNZtaqzbqu6kPg3RS6C2qCgHi, 1AZUPm5PC5QguquNsBg7HhWUYz5dfm2nU9, and 1J1aR7ayNp9sma8QVyyWGF87PzDU1vp5BD.

Friday, February 14, 2014

The Bitcoin malleability attack graphed hour by hour

I have a new Bitcoin article: Hidden surprises in the Bitcoin blockchain
The Bitcoin network was subject to a strange attack this week. Up to 25% of the recorded transactions were modified using a technique called transaction malleability. By examining the Bitcoin blockchain, I've created an hour-by-hour look at the attack.

For details on how transaction malleability works, see my article Bitcoin transaction malleability: looking at the bytes. As a quick summary, the attacker takes a new Bitcoin transaction, modifies it in a trivial way that changes the transaction hash, and sends it back into the Bitcoin system. The modified transaction functions exactly the same (transferring the bitcoins between the same addresses), but results in two slightly different versions of the transaction in the system. However, if client software or exchange software depends on the transaction hash, temporarily having two different hashes for the transaction can cause a variety of problems.

The reason malleability is possible is that inside a Bitcoin transaction is a tiny program that provides the signature data. This script pushes the (hex) 48 byte signature by using the instruction 48. An attacker can change the script to use the OP_PUSHDATA2 instruction (4d) followed by a two-byte length (48 00). The modified transaction is still valid, since the script has exactly the same action.

Tracking the malleability attack

I created the graph below, which shows the hourly progress of the attack: the blue line is the total number of Bitcoin transactions, and the green line is the number of transactions that were modified by the malleability attack.

Graph of Bitcoin transactions suffering from malleability attack, Feb 2014.

Graph of Bitcoin transactions suffering from malleability attack, Feb 2014.

The attack started off affecting a fairly small number of transactions on Feb 9. The malleability attack itself appears to have started in block 284980 (Feb 9, 8:12 PST), which contains 36 modified transactions. Since the number of affected transactions in this block and following blocks was small, I wonder if this was a test phase for the attack.

The attack really took off the morning of February 10. At the peak, up to 25% of Bitcoin transactions were modified.

The attack ended fairly abruptly the morning of Feb 11. I made a bunch of transactions that evening, hoping to see a modified one, but I was disappointed that they all went through untouched.

A few modified transactions continued to trickle in for the next few days, with some even today (Feb 14). Some of these are older transactions that were mined very slowly because they didn't include any fees. For example, this transaction was modified on Feb 10, but not mined until Feb 14.

History of OP_PUSHDATA2 usage

I wanted to find out if there were any precursors to the malleability attack, or any similar attacks earlier. I scanned the entire blockchain looking for transactions using the OP_PUSHDATA2 opcode, which is used in the malleability attack. (As an aside, the Bitcoin data is a pain to parse for several reasons.)

Up until the attack, OP_PUSHDATA2 was very rare. I saw OP_PUSHDATA2 used in July 2013 here for a strange - but not modified (malleated?) - transaction. OP_PUSHDATA2 was used again in November 5 (here)when someone used OP_PUSHDATA to include a joke signature in the transaction: I should not run the washing machine while listening to WZBC. I managed to convince myself that the machine was slowly failing -- that a rythmic, squeaking noise it had been making had gotten a little worse. Ten minutes later, though, the machine had paused. But the noise was still there. All that text is stored inside the Bitcoin transaction. There are a bunch of ways to "hide" text messages in the blockchain, and this transaction used an unusual one.

On Feb 4, this transaction used OP_PUSHDATA2 in a strange broken transaction that wasted 0.001 BTC. Interestingly, the sibling transaction wasted 0.03201 BTC in a broken MULTISIG transaction with the "correct horse battery staple" public key. I conclude that someone was trying out strange things on Feb 4, including the rare OP_PUSHDATA2 instruction. Was this debugging for the malleability attack a few days later or was this unrelated experimentation?

Some conclusions

There has been some speculation that the malleability attack directed the modified transactions to a specific miner. However, I looked at the blocks containing these transactions, and they come from a variety of well-known miners. So there's nothing miner-specific about this attack. The attackers don't have their own mining pool.

There's a 100-millisecond sleep in the Bitcoin peer's message processing loop. There has been speculation that the attacker could beat regular peers by avoiding this loop: regular peers would wait 100ms to pass along messages, while the attacker could get a transaction, modify it, and send it to a miner immediately. This seems plausible to me.

One puzzle is that Mt.Gox announced their difficulties on Feb 7, and then explained Feb 10 that they were stopping withdrawals due to a malleability attack. Since the OP_PUSHDATA2 attack didn't start until Feb 9, this attack can't be responsible for the Feb 7 problems. One possibility is there was a different type of malleability attack that affected Mt.Gox. It would be interesting to get the hash for one of the affected transactions from before Feb 7, to see what was going on.

Around the same time as the malleability attack, many people received tiny payments from 1Enjoy and 1Sochi addresses. I believe all these payments were rejected by miners as junk and remain unconfirmed. As far as I know, there is no connection between these tiny spam payments and the malleability attack, but the timing is suspicious.

Thursday, February 13, 2014

Bitcoin transaction malleability: looking at the bytes

"Malleability" of Bitcoin transactions has recently become a major issue. This article looks at how transactions are modified, at the byte level.

I have a new article The malleability attack graphed hour-by-hour. Check it out too.

An attacker has been modifying Bitcoin transactions, causing them to have a different hash. Recently an attacker has been taking transactions on the Bitcoin peer-to-peer network, modifying them slightly, and rapidly sending them to a miner. The modified transaction often gets mined first, pre-empting the original transaction. The attacker can only make "trivial" changes to a transaction, so exactly the same Bitcoin transfer happens as was intended - the same amount is moved between the same addresses, so this attack seems entirely pointless. However, each transaction is identified by a cryptographic hash, and even a trivial change to the transaction causes the transaction hash to change. Changing the hash of a transaction can have unexpected effects on the Bitcoin system.

A very quick explanation of transactions

A Bitcoin transaction moves bitcoins from one address to another. A transaction must be signed with the private key corresponding to the address, so only the owner of the bitcoins can move them. (This signing process is surprisingly complex.) The signature is then put in the middle of the transaction. Finally, the entire transaction (including the signature) is cryptographically hashed, and this hash is used to identify the transaction in the Bitcoin system. The important data is protected by the signature and can't be modified by an attacker. But there are few ways the signature itself can be changed, but still remain valid.

(This is oversimplified. For more details, see Bitcoins the hard way.)

Looking at a modified transaction

To find a transaction suffering from malleability, I looked at the unconfirmed transactions page. If a transaction gets modified, only one version will get mined successfully (and actually transfer bitcoins), and the other will remain unconfirmed (and have no effect). Among the many conditions enforced in mined blocks, the same bitcoins can't be spent twice, so both transactions will never be mined. This is why having two versions of a transaction doesn't result in two payments.

I picked a random unconfirmed transaction from Feb 11 to examine. (Unfortunately this transaction has been discarded since I wrote this article, breaking my links. But you can look up a different one if you want.) helpfully includes a banner warning that something is wrong:

Warning! this transaction is a double spend of 112593804. You should be extremely careful when trusting any transactions to/from this sender.

Looking at the transactions, everything seems fine:

The confirmed transaction takes 0.01 BTC from 1JRQExbG6WAhPCWC5W5H7Rn1LannTx1Dix and transfers 0.0099 BTC to 1Hbum99G9Lp7PyQ2nYqDcN3jh5aw878bFt (the remainder is a mining fee of 0.001 BTC). This transaction has hash bba8c3d044828f099ae3bc5f3beaff2643e0202d6c121753b53536a49511c63f.

The unconfirmed transaction takes 0.01 BTC from 1JRQExbG6WAhPCWC5W5H7Rn1LannTx1Dix and transfers 0.0099 BTC to 1Hbum99G9Lp7PyQ2nYqDcN3jh5aw878bFt (the remainder is a mining fee of 0.001 BTC). This transaction has hash d36a0fcdf4b3ccfe114e882ef4159094d2012bc8b72dc6389862a7dc43dfa61c.

The scripts of both transactions appear identical:

Input Scripts
30450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d8701 046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44 OK
Output Scripts
OP_DUP OP_HASH160 b61c32ac39c63f919c4ce3a5df77590c5903d975 OP_EQUALVERIFY OP_CHECKSIG 
Both transactions look identical: the bitcoins are moving between the same accounts in both cases, the amounts are equal, and the scripts look identical. So why do they have different hashes? A clue is the unconfirmed transaction is 224 bytes and the confirmed transaction is 228 bytes.

Looking at the raw transactions also fails to show what is happening:

      "scriptSig":"30450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d8701 046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44"
      "scriptPubKey":"OP_DUP OP_HASH160 b61c32ac39c63f919c4ce3a5df77590c5903d975 OP_EQUALVERIFY OP_CHECKSIG"

Even though the scripts are mostly in hex in this raw display, they have been parsed slightly, which hides what is going on. We need to get the full scripts here and here.

The unconfirmed transaction has script:

The confirmed transaction has script:
There are a couple differences (highlighted in red). But what do they mean?

This script is the scriptSig, the signature of the transaction using the sender's private key. This signature proves the sender owns the bitcoins. However, the scriptSig isn't just a simple signature, but is actually a program written in Bitcoin's Script language. This program pushes the signature data onto the execution stack. The program from the unconfirmed script is interpreted as follows:

Y 00fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87
public key type04
Y 02b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44

The program from the confirmed script is interpreted as follows:

OP_PUSHDATA2 00484d 48 00
Y 00fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87
OP_PUSHDATA2 00414d 41 00
public key type04
Y 02b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44

Note the highlighted differences. The original transaction has a byte 0x48, which says to push (hex) 48 bytes of data. The modified transaction has a OP_PUSHDATA2 (0x4d), which says the next two bytes (48 00) are the number of bytes to push. In other words, both transactions do exactly the same thing (push the signature), but the original indicates this with 48, while the modified transaction indicates this with 4d 48 00. (Pushing the public key has a similar modification.) Since both scripts do exactly the same thing, both transactions are equally valid. However, since the data has changed, the transactions have two different hashes.

Why does malleability matter?

Transaction Malleability has been discussed for years and treated as a minor inconvenience. Both transactions have exactly the same effect, moving bitcoins between the same addresses. Only one transaction will be confirmed by miners, and the other will be discarded, so nobody gets paid twice even though there are two transactions.

There are, however, three problems that have turned up recently due to malleability.

First, the major Mt.Gox exchange stated they would stop processing bitcoin withdrawals until the Bitcoin network approves and standardizes on a new non-malleable hash. Apparently they were using the hash to track transactions, and would re-send bitcoins if the transaction didn't appear to go through. This is obviously a problem if the transaction did go through, but with a different hash.

Second, some wallet software would use both transactions to compute the balance, which caused it to show the wrong value.

Finally, due to the way Bitcoin handles change, malleability could cause a second transaction to fail. This requires a bit more explanation.

Failures due to change and malleability

The Bitcoin protocol doesn't really move bitcoins from address to address. Instead, it takes bitcoins from a set of inputs, and sends them to a set of outputs. Each output is an address (actually a script, but let's ignore that for now). Each input is an output from a previous transaction, and each input must be entirely spent.

As a result, if you have 3 bitcoins, and you want to spend one of them, the other two bitcoins get returned to you as change, sent to an address you control. If you then want to spend some of the change, your second transaction references the previous transaction that generates the change, referencing it by the hash of the first transaction. This is where malleability becomes a problem - if the first transaction's hash changed, the second transaction is not valid and the transaction will fail. Note that the change will still go to your proper address, so you can spend it as long as you use the correct (modified) transaction hash, so you don't lose any bitcoins. You just have the inconvenience of having a transaction rejected, and you'll need to redo it with the right hash.

The change problem only happens because some wallet software takes a shortcut, letting you (attempt to) spend the change before the transaction has been confirmed. The reasoning is that since it's your change from your transaction, you should be able to trust yourself. But that breaks down with malleability.

Malleability has been known for a long time

Transaction malleability has been known since 2011. The exact OP_PUSHDATA2 malleability used above was described four months ago here. There are many other types of malleability, which are explained here. The script code can be modified in several ways while leaving its operation unchanged. The signature itself can be encoded slightly differently. And interestingly, due to the mathematics of elliptic curves the numeric value of the signature can be negated, yielding a second valid signature.


Hopefully this has helped to make malleability more understandable. If you want to know more details of the Bitcoin protocol, including signing and hashing, see my previous article Bitcoins the hard way.