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.

Untitled

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.

noncehash
05c56c2883435b38aeba0e69fb2e0e3db3b22448d3e17b903d774dd5650796f76
128902a23a194dee94141d1b70102accd85fc2c1ead0901ba0e41ade90d38a08e
2729577af82250aaf9e44f70a72814cf56c16d430a878bf52fdaceeb7b4bd37f4
38491452381016cf80562ff489e492e00331de3553178c73c5169574000f1ed1c
3903fd5ff1048668cd3cde4f3fb5bde1ff306d26a4630f420c78df1e504e24f3c7
9900001e3a4583f4c6d81251e8d9901dbe0df74d7144300d7c03cab15eca04bd4bb
521170000642411733cd63264d3bedc046a5364ff3c77d2b37ca298ad8f1b5a9f05ba
181315200000c94a85b5c06c9b06ace1ba7c7f759e795715f399c9c1b1b7f5d387a319f
19745650000000cdccf49f13f5c3f14a2c12a56ae60e900c5e65bfe1cc24f038f0668a6c
2439898010000000ce99e2a00633ca958a16e17f30085a54f04667a5492db49bcae15d190
8561923280000000000000000e067a478024addfecdc93628978aa52d91fabd4292982a50

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:
{"id":1,"result":[[["mining.set_difficulty","b4b6693b72a50c7116db18d6497cac52"],["mining.notify","ae6812eb4cd7735a302a8a9dd95cf71f"]],"4bc6af58",4],"error":null}

{"id":null,"params":[16],"method":"mining.set_difficulty"}

{"id":null,"params":["58af8d8c","975b9717f7d18ec1f2ad55e2559b5997b8da0e3317c803780000000100000000","01000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4803636004062f503253482f04428b055308","2e522cfabe6d6da0bd01f57abe963d25879583eea5ea6f08f83e3327eba9806b14119718cbb1cf04000000000000000000000001fb673495000000001976a91480ad90d403581fa3bf46086a91b2d9d4125db6c188ac00000000",["ea9da84d55ebf07f47def6b9b35ab30fc18b6e980fc618f262724388f2e9c591","f8578e6b5900de614aabe563c9622a8f514e11d368caa78890ac2ed615a2300c","1632f2b53febb0a999784c4feb1655144793c4e662226aff64b71c6837430791","ad4328979dba3e30f11c2d94445731f461a25842523fcbfa53cd42b585e63fcd","a904a9a41d1c8f9e860ba2b07ba13187b41aa7246f341489a730c6dc6fb42701","dd7e026ac1fff0feac6bed6872b6964f5ea00bd8913a956e6b2eb7e22363dc5c","2c3b18d8edff29c013394c28888c6b50ed8733760a3d4d9082c3f1f5a43afa64"],"00000002","19015f53","53058b41",false],"method":"mining.notify"
{"id":2,"result":true,"error":null}
{"id":null,"params":[16],"method":"mining.set_difficulty"}
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.

job_id58af8d8c
prevhash975b9717f7d18ec1f2ad55e2559b5997b8da0e3317c803780000000100000000
coinb10100000001000000000000000000000000000000000000000000000000000000
0000000000ffffffff4803636004062f503253482f04428b055308
coinb22e522cfabe6d6da0bd01f57abe963d25879583eea5ea6f08f83e3327eba9806b
14119718cbb1cf04000000000000000000000001fb673495000000001976a914
80ad90d403581fa3bf46086a91b2d9d4125db6c188ac00000000
merkle_branch["ea9da84d55ebf07f47def6b9b35ab30fc18b6e980fc618f262724388f2e9c591", ...]
version00000002
nbits19015f53
ntime53058b41
clean_jobsfalse

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 GHash.io mining pool

A coinbase transaction generated by the GHash.io 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 dogepool.pw 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 https://blockchain.info/stats 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.

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, http://bit.ly/naNhG2 -- happy now?".[6]

The codebase technique has since been used by many other miners as advertising. Typical messages are: Hi from 50BTC.com, For Pierce and Paul, Mined at GIVE-ME-COINS.com, 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]
---BEGIN TRIBUTE---
#./BitLen
:::::::::::::::::::
:::::::.::.::.:.:::
:.: :.' ' ' ' ' : :
:.:'' ,,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 "rabbi" SASSAMA
     1980-2011
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
hilarious.
--Dan Kaminsky,
Travis Goodspeed
P.S.  My apologies,
BitCoin people.  He
also would have
LOL'd at BitCoin's
new dependency upon
   ASCII BERNANKE
:'::.:::::.:::.::.:
: :.: ' ' ' ' : :':
:.:     _.__    '.:
:   _,^"   "^x,   :
'  x7'        `4,
 XX7            4XX
 XX              XX
 Xl ,xxx,   ,xxx,XX
( ' _,+o, | ,o+,"
 4   "-^' X "^-'" 7
 l,     ( ))     ,X
 :Xx,_ ,xXXXxx,_,XX
  4XXiX'-___-`XXXX'
   4XXi,_   _iXX7'
  , `4XXXXXXXXX^ _,
  Xx,  ""^^^XX7,xX
W,"4WWx,_ _,XxWWX7'
Xwi, "4WW7""4WW7',W
TXXWw, ^7 Xk 47 ,WH
:TXXXWw,_ "), ,wWT:
::TTXXWWW lXl WWT:
----END TRIBUTE----

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.

Rickrolls

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

cablegate-201012041811.7z

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!

5c593b7b71063a01f4128c98e36fb407b00a87454e67b39ad5f8820ebc1b2ad5
221d900b5ac701028f9dfab7dfba326f608308386d45c05432e721b7c122cba7
... 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 <[email protected]>
Date: Mon, 12 Aug 2013 02:28:02 -0200
Subject:[PATCH] Remove (SINGLE|DOUBLE)BYTE

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/deserialize.py |    8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)

diff --git a/backends/bitcoind/deserialize.py b/backends/bitcoind/deserialize.py
index 6620583..89b9b1b 100644
--- a/backends/bitcoind/deserialize.py
+++ b/backends/bitcoind/deserialize.py
@@ -280,10 +280,8 @@ opcodes = Enumeration("Opcodes", [
     "OP_WITHIN", "OP_RIPEMD160", "OP_SHA1", "OP_SHA256", "OP_HASH160",
     "OP_HASH256", "OP_CODESEPARATOR", "OP_CHECKSIG", "OP_CHECKSIGVERIFY", "OP_CHECKMULTISIG",
     "OP_CHECKMULTISIGVERIFY",
-    ("OP_SINGLEBYTE_END", 0xF0),
-    ("OP_DOUBLEBYTE_BEGIN", 0xF000),
     "OP_PUBKEY", "OP_PUBKEYHASH",
-    ("OP_INVALIDOPCODE", 0xFFFF),
+    ("OP_INVALIDOPCODE", 0xFF),
 ])


@@ -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
--
1.7.9.4

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, someone 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:
    '//righto.com/bc'.encode('hex')
    
  2. Convert the resulting hex string to an address. An easy way is online: https://blockchain.info/q/hashtoaddress/your 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.

Summary

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 bitcoinstrings.com.

[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:

PUSHDATA: 04
bits value (mining difficulty): FFFF001D
PUSHDATA: 01
nonce value: 04
PUSHDATA: 45
'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 blockchain.info 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 50BTC.com address.

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

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.

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.) Blockchain.info 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:

{
  "hash":"bba8c3d044828f099ae3bc5f3beaff2643e0202d6c121753b53536a49511c63f",
  "ver":1,
  "vin_sz":1,
  "vout_sz":1,
  "lock_time":0,
  "size":228,
  "in":[
    {
      "prev_out":{
        "hash":"3ceafb1d6864091a6c40f0f0fa7d4072d71a909820444ac307dcaa7a2d4b88d4",
        "n":1
      },
      "scriptSig":"30450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d8701 046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44"
    }
  ],
  "out":[
    {
      "value":"0.00990000",
      "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:

4830450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d870141046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44
The confirmed transaction has script:
4d480030450220539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1022100fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87014d4100046c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc402b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44
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:

PUSHDATA 4848
signature
(DER)
sequence30
length45
integer02
length20
X539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1
integer02
length21
Y 00fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87
SIGHASH_ALL01
PUSHDATA 4141
public key type04
X6c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc4
Y 02b47574d6ce5c6c5d66db0845c7dabcb5d90d0d6ca9b703dc4d02f4501b6e44

The program from the confirmed script is interpreted as follows:

OP_PUSHDATA2 00484d 48 00
signature
(DER)
sequence30
length45
integer02
length20
X539901ea7d6840eea8826c1f3d0d1fca7827e491deabcf17889e7a2e5a39f5a1
integer02
length21
Y 00fe745667e444978c51fdba6981505f0a68619f0289e5ff2352acbd31b3d23d87
SIGHASH_ALL01
OP_PUSHDATA2 00414d 41 00
public key type04
X6c4ea0005563c20336d170e35ae2f168e890da34e63da7fff1cc8f2a54f60dc4
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.

Conclusion

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.

Bitcoins the hard way: Using the raw Bitcoin protocol

All the recent media attention on Bitcoin inspired me to learn how Bitcoin really works, right down to the bytes flowing through the network. Normal people use software[1] that hides what is really going on, but I wanted to get a hands-on understanding of the Bitcoin protocol. My goal was to use the Bitcoin system directly: create a Bitcoin transaction manually, feed it into the system as hex data, and see how it gets processed. This turned out to be considerably harder than I expected, but I learned a lot in the process and hopefully you will find it interesting.

(Feb 23: I have a new article that covers the technical details of mining. If you like this article, check out my mining article too.)

This blog post starts with a quick overview of Bitcoin and then jumps into the low-level details: creating a Bitcoin address, making a transaction, signing the transaction, feeding the transaction into the peer-to-peer network, and observing the results.

A quick overview of Bitcoin

I'll start with a quick overview of how Bitcoin works[2], before diving into the details. Bitcoin is a relatively new digital currency[3] that can be transmitted across the Internet. You can buy bitcoins[4] with dollars or other traditional money from sites such as Coinbase or MtGox[5], send bitcoins to other people, buy things with them at some places, and exchange bitcoins back into dollars.

To simplify slightly, bitcoins consist of entries in a distributed database that keeps track of the ownership of bitcoins. Unlike a bank, bitcoins are not tied to users or accounts. Instead bitcoins are owned by a Bitcoin address, for example 1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa.

Bitcoin transactions

A transaction is the mechanism for spending bitcoins. In a transaction, the owner of some bitcoins transfers ownership to a new address.

A key innovation of Bitcoin is how transactions are recorded in the distributed database through mining. Transactions are grouped into blocks and about every 10 minutes a new block of transactions is sent out, becoming part of the transaction log known as the blockchain, which indicates the transaction has been made (more-or-less) official.[6] Bitcoin mining is the process that puts transactions into a block, to make sure everyone has a consistent view of the transaction log. To mine a block, miners must find an extremely rare solution to an (otherwise-pointless) cryptographic problem. Finding this solution generates a mined block, which becomes part of the official block chain.

Mining is also the mechanism for new bitcoins to enter the system. When a block is successfully mined, new bitcoins are generated in the block and paid to the miner. This mining bounty is large - currently 25 bitcoins per block (about $19,000). In addition, the miner gets any fees associated with the transactions in the block. Because of this, mining is very competitive with many people attempting to mine blocks. The difficulty and competitiveness of mining is a key part of Bitcoin security, since it ensures that nobody can flood the system with bad blocks.

The peer-to-peer network

There is no centralized Bitcoin server. Instead, Bitcoin runs on a peer-to-peer network. If you run a Bitcoin client, you become part of that network. The nodes on the network exchange transactions, blocks, and addresses of other peers with each other. When you first connect to the network, your client downloads the blockchain from some random node or nodes. In turn, your client may provide data to other nodes. When you create a Bitcoin transaction, you send it to some peer, who sends it to other peers, and so on, until it reaches the entire network. Miners pick up your transaction, generate a mined block containing your transaction, and send this mined block to peers. Eventually your client will receive the block and your client shows that the transaction was processed.

Cryptography

Bitcoin uses digital signatures to ensure that only the owner of bitcoins can spend them. The owner of a Bitcoin address has the private key associated with the address. To spend bitcoins, they sign the transaction with this private key, which proves they are the owner. (It's somewhat like signing a physical check to make it valid.) A public key is associated with each Bitcoin address, and anyone can use it to verify the digital signature.

Blocks and transactions are identified by a 256-bit cryptographic hash of their contents. This hash value is used in multiple places in the Bitcoin protocol. In addition, finding a special hash is the difficult task in mining a block.

Bitcoin statistic coin ANTANA

Bitcoins do not really look like this. Photo credit: Antana, CC:by-sa

Diving into the raw Bitcoin protocol

The remainder of this article discusses, step by step, how I used the raw Bitcoin protocol. First I generated a Bitcoin address and keys. Next I made a transaction to move a small amount of bitcoins to this address. Signing this transaction took me a lot of time and difficulty. Finally, I fed this transaction into the Bitcoin peer-to-peer network and waited for it to get mined. The remainder of this article describes these steps in detail.

It turns out that actually using the Bitcoin protocol is harder than I expected. As you will see, the protocol is a bit of a jumble: it uses big-endian numbers, little-endian numbers, fixed-length numbers, variable-length numbers, custom encodings, DER encoding, and a variety of cryptographic algorithms, seemingly arbitrarily. As a result, there's a lot of annoying manipulation to get data into the right format.[7]

The second complication with using the protocol directly is that being cryptographic, it is very unforgiving. If you get one byte wrong, the transaction is rejected with no clue as to where the problem is.[8]

The final difficulty I encountered is that the process of signing a transaction is much more difficult than necessary, with a lot of details that need to be correct. In particular, the version of a transaction that gets signed is very different from the version that actually gets used.

Bitcoin addresses and keys

My first step was to create a Bitcoin address. Normally you use Bitcoin client software to create an address and the associated keys. However, I wrote some Python code to create the address, showing exactly what goes on behind the scenes.

Bitcoin uses a variety of keys and addresses, so the following diagram may help explain them. You start by creating a random 256-bit private key. The private key is needed to sign a transaction and thus transfer (spend) bitcoins. Thus, the private key must be kept secret or else your bitcoins can be stolen.

The Elliptic Curve DSA algorithm generates a 512-bit public key from the private key. (Elliptic curve cryptography will be discussed later.) This public key is used to verify the signature on a transaction. Inconveniently, the Bitcoin protocol adds a prefix of 04 to the public key. The public key is not revealed until a transaction is signed, unlike most systems where the public key is made public.

How bitcoin keys and addresses are related

How bitcoin keys and addresses are related

The next step is to generate the Bitcoin address that is shared with others. Since the 512-bit public key is inconveniently large, it is hashed down to 160 bits using the SHA-256 and RIPEMD hash algorithms.[9] The key is then encoded in ASCII using Bitcoin's custom Base58Check encoding.[10] The resulting address, such as 1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa, is the address people publish in order to receive bitcoins. Note that you cannot determine the public key or the private key from the address. If you lose your private key (for instance by throwing out your hard drive), your bitcoins are lost forever.

Finally, the Wallet Interchange Format key (WIF) is used to add a private key to your client wallet software. This is simply a Base58Check encoding of the private key into ASCII, which is easily reversed to obtain the 256-bit private key. (I was curious if anyone would use the private key above to steal my 80 cents of bitcoins, and sure enough someone did.)

To summarize, there are three types of keys: the private key, the public key, and the hash of the public key, and they are represented externally in ASCII using Base58Check encoding. The private key is the important key, since it is required to access the bitcoins and the other keys can be generated from it. The public key hash is the Bitcoin address you see published.

I used the following code snippet[11] to generate a private key in WIF format and an address. The private key is simply a random 256-bit number. The ECDSA crypto library generates the public key from the private key.[12] The Bitcoin address is generated by SHA-256 hashing, RIPEMD-160 hashing, and then Base58 encoding with checksum. Finally, the private key is encoded in Base58Check to generate the WIF encoding used to enter a private key into Bitcoin client software.[1] Note: this Python random function is not cryptographically strong; use a better function if you're doing this for real.

Inside a transaction

A transaction is the basic operation in the Bitcoin system. You might expect that a transaction simply moves some bitcoins from one address to another address, but it's more complicated than that. A Bitcoin transaction moves bitcoins between one or more inputs and outputs. Each input is a transaction and address supplying bitcoins. Each output is an address receiving bitcoin, along with the amount of bitcoins going to that address.

A sample Bitcoin transaction. Transaction C spends .008 bitcoins from Transactions A and B.

A sample Bitcoin transaction. Transaction C spends .008 bitcoins from Transactions A and B.

The diagram above shows a sample transaction "C". In this transaction, .005 BTC are taken from an address in Transaction A, and .003 BTC are taken from an address in Transaction B. (Note that arrows are references to the previous outputs, so are backwards to the flow of bitcoins.) For the outputs, .003 BTC are directed to the first address and .004 BTC are directed to the second address. The leftover .001 BTC goes to the miner of the block as a fee. Note that the .015 BTC in the other output of Transaction A is not spent in this transaction.

Each input used must be entirely spent in a transaction. If an address received 100 bitcoins in a transaction and you just want to spend 1 bitcoin, the transaction must spend all 100. The solution is to use a second output for change, which returns the 99 leftover bitcoins back to you.

Transactions can also include fees. If there are any bitcoins left over after adding up the inputs and subtracting the outputs, the remainder is a fee paid to the miner. The fee isn't strictly required, but transactions without a fee will be a low priority for miners and may not be processed for days or may be discarded entirely.[13] A typical fee for a transaction is 0.0002 bitcoins (about 20 cents), so fees are low but not trivial.

Manually creating a transaction

For my experiment I used a simple transaction with one input and one output, which is shown below. I started by bying bitcoins from Coinbase and putting 0.00101234 bitcoins into address 1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5, which was transaction 81b4c832.... My goal was to create a transaction to transfer these bitcoins to the address I created above, 1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa, subtracting a fee of 0.0001 bitcoins. Thus, the destination address will receive 0.00091234 bitcoins.

Structure of the example Bitcoin transaction.

Structure of the example Bitcoin transaction.

Following the specification, the unsigned transaction can be assembled fairly easily, as shown below. There is one input, which is using output 0 (the first output) from transaction 81b4c832.... Note that this transaction hash is inconveniently reversed in the transaction. The output amount is 0.00091234 bitcoins (91234 is 0x016462 in hex), which is stored in the value field in little-endian form. The cryptographic parts - scriptSig and scriptPubKey - are more complex and will be discussed later.

version01 00 00 00
input count01
inputprevious output hash
(reversed)
48 4d 40 d4 5b 9e a0 d6 52 fc a8 25 8a b7 ca a4 25 41 eb 52 97 58 57 f9 6f b5 0c d7 32 c8 b4 81
previous output index00 00 00 00
script length
scriptSigscript containing signature
sequenceff ff ff ff
output count01
outputvalue62 64 01 00 00 00 00 00
script length
scriptPubKeyscript containing destination address
block lock time00 00 00 00

Here's the code I used to generate this unsigned transaction. It's just a matter of packing the data into binary. Signing the transaction is the hard part, as you'll see next.

How Bitcoin transactions are signed

The following diagram gives a simplified view of how transactions are signed and linked together.[14] Consider the middle transaction, transferring bitcoins from address B to address C. The contents of the transaction (including the hash of the previous transaction) are hashed and signed with B's private key. In addition, B's public key is included in the transaction.

By performing several steps, anyone can verify that the transaction is authorized by B. First, B's public key must correspond to B's address in the previous transaction, proving the public key is valid. (The address can easily be derived from the public key, as explained earlier.) Next, B's signature of the transaction can be verified using the B's public key in the transaction. These steps ensure that the transaction is valid and authorized by B. One unexpected part of Bitcoin is that B's public key isn't made public until it is used in a transaction.

With this system, bitcoins are passed from address to address through a chain of transactions. Each step in the chain can be verified to ensure that bitcoins are being spent validly. Note that transactions can have multiple inputs and outputs in general, so the chain branches out into a tree.

How Bitcoin transactions are chained together.

How Bitcoin transactions are chained together.[14]

The Bitcoin scripting language

You might expect that a Bitcoin transaction is signed simply by including the signature in the transaction, but the process is much more complicated. In fact, there is a small program inside each transaction that gets executed to decide if a transaction is valid. This program is written in Script, the stack-based Bitcoin scripting language. Complex redemption conditions can be expressed in this language. For instance, an escrow system can require two out of three specific users must sign the transaction to spend it. Or various types of contracts can be set up.[15]

The Script language is surprisingly complex, with about 80 different opcodes. It includes arithmetic, bitwise operations, string operations, conditionals, and stack manipulation. The language also includes the necessary cryptographic operations (SHA-256, RIPEMD, etc.) as primitives. In order to ensure that scripts terminate, the language does not contain any looping operations. (As a consequence, it is not Turing-complete.) In practice, however, only a few types of transactions are supported.[16]

In order for a Bitcoin transaction to be valid, the two parts of the redemption script must run successfully. The script in the old transaction is called scriptPubKey and the script in the new transaction is called scriptSig. To verify a transaction, the scriptSig executed followed by the scriptPubKey. If the script completes successfully, the transaction is valid and the Bitcoin can be spent. Otherwise, the transaction is invalid. The point of this is that the scriptPubKey in the old transaction defines the conditions for spending the bitcoins. The scriptSig in the new transaction must provide the data to satisfy the conditions.

In a standard transaction, the scriptSig pushes the signature (generated from the private key) to the stack, followed by the public key. Next, the scriptPubKey (from the source transaction) is executed to verify the public key and then verify the signature.

As expressed in Script, the scriptSig is:

PUSHDATA
signature data and SIGHASH_ALL
PUSHDATA
public key data
The scriptPubKey is:
OP_DUP
OP_HASH160
PUSHDATA
Bitcoin address (public key hash)
OP_EQUALVERIFY
OP_CHECKSIG

When this code executes, PUSHDATA first pushes the signature to the stack. The next PUSHDATA pushes the public key to the stack. Next, OP_DUP duplicates the public key on the stack. OP_HASH160 computes the 160-bit hash of the public key. PUSHDATA pushes the required Bitcoin address. Then OP_EQUALVERIFY verifies the top two stack values are equal - that the public key hash from the new transaction matches the address in the old address. This proves that the public key is valid. Next, OP_CHECKSIG checks that the signature of the transaction matches the public key and signature on the stack. This proves that the signature is valid.

Signing the transaction

I found signing the transaction to be the hardest part of using Bitcoin manually, with a process that is surprisingly difficult and error-prone. The basic idea is to use the ECDSA elliptic curve algorithm and the private key to generate a digital signature of the transaction, but the details are tricky. The signing process has been described through a 19-step process (more info). Click the thumbnail below for a detailed diagram of the process.

The biggest complication is the signature appears in the middle of the transaction, which raises the question of how to sign the transaction before you have the signature. To avoid this problem, the scriptPubKey script is copied from the source transaction into the spending transaction (i.e. the transaction that is being signed) before computing the signature. Then the signature is turned into code in the Script language, creating the scriptSig script that is embedded in the transaction. It appears that using the previous transaction's scriptPubKey during signing is for historical reasons rather than any logical reason.[17] For transactions with multiple inputs, signing is even more complicated since each input requires a separate signature, but I won't go into the details.

One step that tripped me up is the hash type. Before signing, the transaction has a hash type constant temporarily appended. For a regular transaction, this is SIGHASH_ALL (0x00000001). After signing, this hash type is removed from the end of the transaction and appended to the scriptSig.

Another annoying thing about the Bitcoin protocol is that the signature and public key are both 512-bit elliptic curve values, but they are represented in totally different ways: the signature is encoded with DER encoding but the public key is represented as plain bytes. In addition, both values have an extra byte, but positioned inconsistently: SIGHASH_ALL is put after the signature, and type 04 is put before the public key.

Debugging the signature was made more difficult because the ECDSA algorithm uses a random number.[18] Thus, the signature is different every time you compute it, so it can't be compared with a known-good signature.

Update (Feb 2014): An important side-effect of the signature changing every time is that if you re-sign a transaction, the transaction's hash will change. This is known as Transaction Malleability. There are also ways that third parties can modify transactions in trivial ways that change the hash but not the meaning of the transaction. Although it has been known for years, malleability has recently caused big problems (Feb 2014) with MtGox (press release).

With these complications it took me a long time to get the signature to work. Eventually, though, I got all the bugs out of my signing code and succesfully signed a transaction. Here's the code snippet I used.

The final scriptSig contains the signature along with the public key for the source address (1MMMMSUb1piy2ufrSguNUdFmAcvqrQF8M5). This proves I am allowed to spend these bitcoins, making the transaction valid.

PUSHDATA 4747
signature
(DER)
sequence30
length44
integer02
length20
X2c b2 65 bf 10 70 7b f4 93 46 c3 51 5d d3 d1 6f c4 54 61 8c 58 ec 0a 0f f4 48 a6 76 c5 4f f7 13
integer02
length20
Y 6c 66 24 d7 62 a1 fc ef 46 18 28 4e ad 8f 08 67 8a c0 5b 13 c8 42 35 f1 65 4e 6a d1 68 23 3e 82
SIGHASH_ALL01
PUSHDATA 4141
public key type04
X14 e3 01 b2 32 8f 17 44 2c 0b 83 10 d7 87 bf 3d 8a 40 4c fb d0 70 4f 13 5b 6a d4 b2 d3 ee 75 13
Y 10 f9 81 92 6e 53 a6 e8 c3 9b d7 d3 fe fd 57 6c 54 3c ce 49 3c ba c0 63 88 f2 65 1d 1a ac bf cd

The final scriptPubKey contains the script that must succeed to spend the bitcoins. Note that this script is executed at some arbitrary time in the future when the bitcoins are spent. It contains the destination address (1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa) expressed in hex, not Base58Check. The effect is that only the owner of the private key for this address can spend the bitcoins, so that address is in effect the owner.

OP_DUP76
OP_HASH160a9
PUSHDATA 1414
public key hashc8 e9 09 96 c7 c6 08 0e e0 62 84 60 0c 68 4e d9 04 d1 4c 5c
OP_EQUALVERIFY88
OP_CHECKSIGac

The final transaction

Once all the necessary methods are in place, the final transaction can be assembled. The final transaction is shown below. This combines the scriptSig and scriptPubKey above with the unsigned transaction described earlier.

version01 00 00 00
input count01
inputprevious output hash
(reversed)
48 4d 40 d4 5b 9e a0 d6 52 fc a8 25 8a b7 ca a4 25 41 eb 52 97 58 57 f9 6f b5 0c d7 32 c8 b4 81
previous output index00 00 00 00
script length8a
scriptSig47 30 44 02 20 2c b2 65 bf 10 70 7b f4 93 46 c3 51 5d d3 d1 6f c4 54 61 8c 58 ec 0a 0f f4 48 a6 76 c5 4f f7 13 02 20 6c 66 24 d7 62 a1 fc ef 46 18 28 4e ad 8f 08 67 8a c0 5b 13 c8 42 35 f1 65 4e 6a d1 68 23 3e 82 01 41 04 14 e3 01 b2 32 8f 17 44 2c 0b 83 10 d7 87 bf 3d 8a 40 4c fb d0 70 4f 13 5b 6a d4 b2 d3 ee 75 13 10 f9 81 92 6e 53 a6 e8 c3 9b d7 d3 fe fd 57 6c 54 3c ce 49 3c ba c0 63 88 f2 65 1d 1a ac bf cd
sequenceff ff ff ff
output count01
outputvalue62 64 01 00 00 00 00 00
script length19
scriptPubKey76 a9 14 c8 e9 09 96 c7 c6 08 0e e0 62 84 60 0c 68 4e d9 04 d1 4c 5c 88 ac
block lock time00 00 00 00

A tangent: understanding elliptic curves

Bitcoin uses elliptic curves as part of the signing algorithm. I had heard about elliptic curves before in the context of solving Fermat's Last Theorem, so I was curious about what they are. The mathematics of elliptic curves is interesting, so I'll take a detour and give a quick overview.

The name elliptic curve is confusing: elliptic curves are not ellipses, do not look anything like ellipses, and they have very little to do with ellipses. An elliptic curve is a curve satisfying the fairly simple equation y^2 = x^3 + ax + b. Bitcoin uses a specific elliptic curve called secp256k1 with the simple equation y^2=x^3+7. [25]

Elliptic curve formula used by Bitcoin.

Elliptic curve formula used by Bitcoin.

An important property of elliptic curves is that you can define addition of points on the curve with a simple rule: if you draw a straight line through the curve and it hits three points A, B, and C, then addition is defined by A+B+C=0. Due to the special nature of elliptic curves, addition defined in this way works "normally" and forms a group. With addition defined, you can define integer multiplication: e.g. 4A = A+A+A+A.

What makes elliptic curves useful cryptographically is that it's fast to do integer multiplication, but division basically requires brute force. For example, you can compute a product such as 12345678*A = Q really quickly (by computing powers of 2), but if you only know A and Q solving n*A = Q is hard. In elliptic curve cryptography, the secret number 12345678 would be the private key and the point Q on the curve would be the public key.

In cryptography, instead of using real-valued points on the curve, the coordinates are integers modulo a prime.[19] One of the surprising properties of elliptic curves is the math works pretty much the same whether you use real numbers or modulo arithmetic. Because of this, Bitcoin's elliptic curve doesn't look like the picture above, but is a random-looking mess of 256-bit points (imagine a big gray square of points).

The Elliptic Curve Digital Signature Algorithm (ECDSA) takes a message hash, and then does some straightforward elliptic curve arithmetic using the message, the private key, and a random number[18] to generate a new point on the curve that gives a signature. Anyone who has the public key, the message, and the signature can do some simple elliptic curve arithmetic to verify that the signature is valid. Thus, only the person with the private key can sign a message, but anyone with the public key can verify the message.

For more on elliptic curves, see the references[20].

Sending my transaction into the peer-to-peer network

Leaving elliptic curves behind, at this point I've created a transaction and signed it. The next step is to send it into the peer-to-peer network, where it will be picked up by miners and incorporated into a block.

How to find peers

The first step in using the peer-to-peer network is finding a peer. The list of peers changes every few seconds, whenever someone runs a client. Once a node is connected to a peer node, they share new peers by exchanging addr messages whenever a new peer is discovered. Thus, new peers rapidly spread through the system.

There's a chicken-and-egg problem, though, of how to find the first peer. Bitcoin clients solve this problem with several methods. Several reliable peers are registered in DNS under the name bitseed.xf2.org. By doing a nslookup, a client gets the IP addresses of these peers, and hopefully one of them will work. If that doesn't work, a seed list of peers is hardcoded into the client. [26]

nslookup can be used to find Bitcoin peers.

nslookup can be used to find Bitcoin peers.

Peers enter and leave the network when ordinary users start and stop Bitcoin clients, so there is a lot of turnover in clients. The clients I use are unlikely to be operational right now, so you'll need to find new peers if you want to do experiments. You may need to try a bunch to find one that works.

Talking to peers

Once I had the address of a working peer, the next step was to send my transaction into the peer-to-peer network.[8] Using the peer-to-peer protocol is pretty straightforward. I opened a TCP connection to an arbitrary peer on port 8333, started sending messages, and received messages in turn. The Bitcoin peer-to-peer protocol is pretty forgiving; peers would keep communicating even if I totally messed up requests.

Important note: as a few people pointed out, if you want to experiment you should use the Bitcoin Testnet, which lets you experiment with "fake" bitcoins, since it's easy to lose your valuable bitcoins if you mess up on the real network. (For example, if you forget the change address in a transaction, excess bitcoins will go to the miners as a fee.) But I figured I would use the real Bitcoin network and risk my $1.00 worth of bitcoins.

The protocol consists of about 24 different message types. Each message is a fairly straightforward binary blob containing an ASCII command name and a binary payload appropriate to the command. The protocol is well-documented on the Bitcoin wiki.

The first step when connecting to a peer is to establish the connection by exchanging version messages. First I send a version message with my protocol version number[21], address, and a few other things. The peer sends its version message back. After this, nodes are supposed to acknowledge the version message with a verack message. (As I mentioned, the protocol is forgiving - everything works fine even if I skip the verack.)

Generating the version message isn't totally trivial since it has a bunch of fields, but it can be created with a few lines of Python. makeMessage below builds an arbitrary peer-to-peer message from the magic number, command name, and payload. getVersionMessage creates the payload for a version message by packing together the various fields.

Sending a transaction: tx

I sent the transaction into the peer-to-peer network with the stripped-down Python script below. The script sends a version message, receives (and ignores) the peer's version and verack messages, and then sends the transaction as a tx message. The hex string is the transaction that I created earlier.

The following screenshot shows how sending my transaction appears in the Wireshark network analysis program[22]. I wrote Python scripts to process Bitcoin network traffic, but to keep things simple I'll just use Wireshark here. The "tx" message type is visible in the ASCII dump, followed on the next line by the start of my transaction (01 00 ...).

A transaction uploaded to Bitcoin, as seen in Wireshark.

A transaction uploaded to Bitcoin, as seen in Wireshark.

To monitor the progress of my transaction, I had a socket opened to another random peer. Five seconds after sending my transaction, the other peer sent me a tx message with the hash of the transaction I just sent. Thus, it took just a few seconds for my transaction to get passed around the peer-to-peer network, or at least part of it.

Victory: my transaction is mined

After sending my transaction into the peer-to-peer network, I needed to wait for it to be mined before I could claim victory. Ten minutes later my script received an inv message with a new block (see Wireshark trace below). Checking this block showed that it contained my transaction, proving my transaction worked. I could also verify the success of this transaction by looking in my Bitcoin wallet and by checking online. Thus, after a lot of effort, I had successfully created a transaction manually and had it accepted by the system. (Needless to say, my first few transaction attempts weren't successful - my faulty transactions vanished into the network, never to be seen again.[8])

A new block in Bitcoin, as seen in Wireshark.

A new block in Bitcoin, as seen in Wireshark.

My transaction was mined by the large GHash.IO mining pool, into block #279068 with hash 0000000000000001a27b1d6eb8c405410398ece796e742da3b3e35363c2219ee. (The hash is reversed in inv message above: ee19...) Note that the hash starts with a large number of zeros - finding such a literally one in a quintillion value is what makes mining so difficult. This particular block contains 462 transactions, of which my transaction is just one.

For mining this block, the miners received the reward of 25 bitcoins, and total fees of 0.104 bitcoins, approximately $19,000 and $80 respectively. I paid a fee of 0.0001 bitcoins, approximately 8 cents or 10% of my transaction. The mining process is very interesting, but I'll leave that for a future article.

Untitled

Bitcoin mining normally uses special-purpose ASIC hardware, designed to compute hashes at high speed. Photo credit: Gastev, CC:by

Conclusion

Using the raw Bitcoin protocol turned out to be harder than I expected, but I learned a lot about bitcoins along the way, and I hope you did too. My code is purely for demonstration - if you actually want to use bitcoins through Python, use a real library[24] rather than my code.

Notes and references

[1] The original Bitcoin client is Bitcoin-qt. In case you're wondering why qt, the client uses the common Qt UI framework. Alternatively you can use wallet software that doesn't participate in the peer-to-peer network, such as Electrum or MultiBit. Or you can use an online wallet such as Blockchain.info.

[2] A couple good articles on Bitcoin are How it works and the very thorough How the Bitcoin protocol actually works.

[3] The original Bitcoin paper is Bitcoin: A Peer-to-Peer Electronic Cash System written by the pseudonymous Satoshi Nakamoto in 2008. The true identity of Satoshi Nakamoto is unknown, although there are many theories.

[4] You may have noticed that sometimes Bitcoin is capitalized and sometimes not. It's not a problem with my shift key - the "official" style is to capitalize Bitcoin when referring to the system, and lower-case bitcoins when referring to the currency units.

[5] In case you're wondering how the popular MtGox Bitcoin exchange got its name, it was originally a trading card exchange called "Magic: The Gathering Online Exchange" and later took the acronym as its name.

[6] For more information on what data is in the blockchain, see the very helpful article Bitcoin, litecoin, dogecoin: How to explore the block chain.

[7] I'm not the only one who finds the Bitcoin transaction format inconvenient. For a rant on how messed up it is, see Criticisms of Bitcoin's raw txn format.

[8] You can also generate transaction and send raw transactions into the Bitcoin network using the bitcoin-qt console. Type sendrawtransaction a1b2c3d4.... This has the advantage of providing information in the debug log if the transaction is rejected. If you just want to experiment with the Bitcoin network, this is much, much easier than my manual approach.

[9] Apparently there's no solid reason to use RIPEMD-160 hashing to create the address and SHA-256 hashing elsewhere, beyond a vague sense that using a different hash algorithm helps security. See discussion. Using one round of SHA-256 is subject to a length extension attack, which explains why double-hashing is used.

[10] The Base58Check algorithm is documented on the Bitcoin wiki. It is similar to base 64 encoding, except it omits the O, 0, I, and l characters to avoid ambiguity in printed text. A 4-byte checksum guards against errors, since using an erroneous bitcoin address will cause the bitcoins to be lost forever.

[11] Some boilerplate has been removed from the code snippets. For the full Python code, see my repository shirriff/bitcoin-code on GitHub. You will also need the ecdsa cryptography library.

[12] You may wonder how I ended up with addresses with nonrandom prefixes such as 1MMMM. The answer is brute force - I ran the address generation script overnight and collected some good addresses. (These addresses made it much easier to recognize my transactions in my testing.) There are scripts and websites that will generate these "vanity" addresses for you.

[13] For a summary of Bitcoin fees, see bitcoinfees.com. This recent Reddit discussion of fees is also interesting.

[14] The original Bitcoin paper has a similar figure showing how transactions are chained together. I find it very confusing though, since it doesn't distinguish between the address and the public key.

[15] For details on the different types of contracts that can be set up with Bitcoin, see Contracts. One interesting type is the 2-of-3 escrow transaction, where two out of three parties must sign the transaction to release the bitcoins. Bitrated is one site that provides these.

[16] Although Bitcoin's Script language is very flexible, the Bitcoin network only permits a few standard transaction types and non-standard transactions are not propagated (details). Some miners will accept non-standard transactions directly, though.

[17] There isn't a security benefit from copying the scriptPubKey into the spending transaction before signing since the hash of the original transaction is included in the spending transaction. For discussion, see Why TxPrev.PkScript is inserted into TxCopy during signature check?

[18] The random number used in the elliptic curve signature algorithm is critical to the security of signing. Sony used a constant instead of a random number in the PlayStation 3, allowing the private key to be determined. In an incident related to Bitcoin, a weakness in the random number generator allowed bitcoins to be stolen from Android clients.

[19] For Bitcoin, the coordinates on the elliptic curve are integers modulo the prime2^256 - 2^32 - 2^9 -2^8 - 2^7 - 2^6 -2^4 -1, which is very nearly 2^256. This is why the keys in Bitcoin are 256-bit keys.

[20] For information on the historical connection between elliptic curves and ellipses (the equation turns up when integrating to compute the arc length of an ellipse) see the interesting article Why Ellipses Are Not Elliptic Curves, Adrian Rice and Ezra Brown, Mathematics Magazine, vol. 85, 2012, pp. 163-176. For more introductory information on elliptic curve cryptography, see ECC tutorial or A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography. For more on the mathematics of elliptic curves, see An Introduction to the Theory of Elliptic Curves by Joseph H. Silverman. Three Fermat trails to elliptic curves includes a discussion of how Fermat's Last Theorem was solved with elliptic curves.

[21] There doesn't seem to be documentation on the different Bitcoin protocol versions other than the code. I'm using version 60002 somewhat arbitrarily.

[22] The Wireshark network analysis software can dump out most types of Bitcoin packets, but only if you download a recent "beta release - I'm using version 1.11.2.

[24] Several Bitcoin libraries in Python are bitcoin-python, pycoin, and python-bitcoinlib.

[25] The elliptic curve plot was generated from the Sage mathematics package:

var("x y")
implicit_plot(y^2-x^3-7, (x,-10, 10), (y,-10, 10), figsize=3, title="y^2=x^3+7")

[26] The hardcoded peer list in the Bitcoin client is in chainparams.cpp in the array pnseed. For more information on finding Bitcoin peers, see How Bitcoin clients find each other or Satoshi client node discovery.