How to Cull the Blockchain

After doing a bit of digging on the topic, I have been unable to find any serious, detailed proposal of how to cull the blockchain. The Bitcoin whitepaper discusses using a Merkle tree to prune transactions but this method cannot be used to cull the blockchain, as such. That is, it cannot be used to move the Genesis block forward. The Bitcoin Core client utilizes pruning methods, internally, but these methods cannot be utilized to alter the blockchain itself because they are not secured by mining.

In this post, I want to lay out a proposal for how to cull the blockchain in a tamper-proof way. Note that the concept of culling does not rely on any particular technique or algorithm - culling is a protocol-level action. An objection to a particular detail of this proposal does not invalidate the proposal itself.

First, why do we need to cull? The blockchain is 140GB and, at max utilization of block weight, could grow at a sustained rate of 100GB per year but will almost certainly continue to grow at a rate of at least 50GB per year. Storage costs are not widely thought to be a serious problem but storage costs are not the primary problem with an ever-growing blockchain, anyway. Peer-to-peer networks are generally designed for lightweight join/leave operations. Every block added to the blockchain makes connection/disconnection more costly for peer nodes which mitigates against Bitcoin's peer-to-peer nature. In addition, relaying the raw blockchain is an O(n²) bandwidth problem because every byte added to the blockchain is added to every future relay of the blockchain. In general, O(n²) is not considered scalable. The steadily increasing size of the blockchain causes other problems, as well.

The reason for starting the blockchain at the Genesis block is that anybody trying to fabricate the blockchain would have to perform more hashing than the Bitcoin network has performed during its entire existence. This is a staggering amount of computation. Almost by definition, the full hashing capacity of the Bitcoin network can only do about 1 block's worth of hashing in 10 minutes. Fabricating more than 1 or 2 blocks back from the present block would be an astounding achievement - the full blockchain presently stands at around a half-million blocks. This is beyond overkill from a security perspective.

Conceptually, the blockchain regulates updates to an implied database called the UTXO-set (Unspent Transaction Output Set). You can use Bitcoin software to build the current UTXO-set from the blockchain. The software will scan the blockchain and update the UTXO-set for every transaction that has occurred, discarding old transaction information as previous UTXOs are spent. Here is an image depicting the conceptual UTXO-set as a pie chart, each slice identified by an associated witness.

A witness is the part of an unspent output that secures it. Each witness can take one of several forms: pay-to-pubkey-hash (P2PKH), pay-to-script-hash (P2SH), pay-to-witness-public-key-hash (P2WPKH), and so on.

Each block that is added to the blockchain is an implicit update of the current UTXO-set:

This fact, combined with the fact that blocks can only be added one-at-a-time, in a well-defined order, makes Bitcoin's UTXO-set an extremely well-behaved entity. It is a discrete-state system, where the state at time t_n is always just S_n.

To cull the blockchain, all we need to do is generate a snapshot of the UTXO-set at some time t_snapshot:

… make that snapshot itself part of the blockchain (playback), and then reset the Genesis block to be the block immediately prior to the snapshotted UTXO-set. This all might sound very dangerous because we are throwing out oodles of transactions and transaction-history all tangled into the parts of the blockchain we are culling. But it's not so bad. Let's look into the details.

The first thing we need to define is some kind of snapshot schedule. This is no harder to define than a coinbase mining award halving. Just set it and let it go. Every X blocks, there will be a snapshot.

Next, we need to define an encoding of the UTXO-set in a network-universal way. To do this, we list every single unspent output in the UTXO-set (transaction ID, witness and balance), sorted by transaction ID in lexicographic order:

Then we just hash this list to generate a UTXO-set snapshot hash. We chain this hash with the previous UTXO-set snapshot hash in the same way that blockchain blocks are connected in a hash chain[1]. Now, we include this hash in the block that is scheduled to kick off the snapshot. The entire flow is depicted here:

Now that the UTXO-set snapshot has been defined, we wait some number of blocks. This is designated as “consensus holdoff time1” in the drawing above. The purpose of the holdoff time is to ensure that the snapshot hash is really agreed upon by the rest of the network – the network should reject a block that was scheduled to kick off a snapshot but was mined with an incorrect UTXO-set hash. Since resetting the Genesis block has network-wide ramifications, lots of holdoff time should be given – 12,960 blocks would be about 3 months. A generous holdoff time will also provide room for emergency measures should something go drastically wrong.

Next, we begin “playback”. Playback works as follows. Assemble the snapshot UTXO-set (as originally hashed), break it into sectors X bytes in size, and require that miners include a UTXO-set sector, in order from 1-N (where N is snapshot-UTXO-set-size divided by X), with each block mined after playback begins. After N blocks, playback is finished and the entire UTXO-set is now encoded into the blockchain.

As we have described the process so far, there is an attack (it is far-fetched, but still an attack). Suppose we are part way through playback. Suppose a bad actor commanding significant mining hashrate has all of his UTXO's in the early sectors of the UTXO-set and decides to mount a hostile hardfork that will alter the remaining playback blocks and the final playback UTXO-set snapshot hash, perhaps eliminating some portion of the UTXO-set in order to deflate the total money supply, or whatever. The rest of the network could always just choose to ignore this bad actor but a well-coordinated attack might make users afraid or confused about what is happening. It is conceivable that a non-negligible part of the network could switch part way through playback onto this poisoned UTXO-set.

There is a tool that can be used to completely eliminate the possibility of such a "mid-playback fork": an all-or-nothing transform (AONT[2]). The idea is this. Before we begin playback itself, we first apply AONT to the snapshot UTXO-set, transforming it into a new file of the same size as the original UTXO-set. Now, we partition this file into N sectors, each X bytes in size. Because AONT is invertible and unkeyed, the original UTXO-set can be recovered simply by applying AONT again. Now, no one can benefit from interrupting the playback because the playback itself is meaningless until it is completed and, in addition, every sector of the playback is dependent upon the entire UTXO-set, so there is no way to "alter" the UTXO-set in such a way that some prefix of the AONT remains the same, enabling a mid-playback fork.

Once playback is complete, we wait for “consensus holdoff time2” before resetting the Genesis block. This holdoff time might be somewhat shorter, say 864 blocks (1 week), in order to allow nodes to begin culling their copies of the blockchain as soon as possible. In any case, the exact numbers given here are not important. The network should choose numbers that incorporate all the relevant factors.

Once the culling process is complete, the entire, correct UTXO-set can be reconstructed starting from the new Genesis block. A device/client that is offline for a very long time can still sync up with the network given nothing more than the UTXO-snapshot hash chain + the current blockchain.

Note that the security of the blockchain itself is never at risk during this entire process. The worst-case scenario is a soft-fork that foregoes resetting the Genesis block in the final step.

One objection that might be raised is that transmitting the UTXO-set over the blockchain only serves to bloat the blockchain itself and slow down the network. A serialized snapshot of the blockchain UTXO state should be about the same size as the internal UTXO-set representation utilized by the Bitcoin Core client. As I understand, this is less than a gigabyte in size (Correction: It is 2.8GiB as of this writing.) So, the UTXO set can be represented in 2% of the space of the full blockchain. Supposing this proportion holds and supposing the blockchain is culled once every 5 years, for example, this would allow the blockchain to be culled by as much as 500GB (suppose 100GB/year) at the cost of just 5GB in snapshot data. The savings would be 495GB, with payoff in disk space savings, connection time reduction, blockchain relay bandwidth reduction, and so on.

Note that this concept of "state playback" is inspired by hardware debug techniques. In general, we cannot simulate the hardware from clock cycle 0 (for a CPU, for example) because the simulator is just too slow. We also cannot directly observe the state inside the machine during a test. So, during a test, we will occasionally dump a snapshot of the entire state of the machine, allowing an external observation device (e.g. logic analyzer) to save that snapshot for replay. When the test fails on hardware, we load the last replay snapshot into the hardware simulator and then "step" the simulator forward to attempt to recreate the failure (in a reasonable amount of time, like a day or so). In the case of Bitcoin, we can observe the state of the blockchain (the implied UTXO-set) but we want to "forget" its past state in a tamper-proof way. Since we take it as a given that the blockchain is tamper-proof, the solution is obvious. Take a snapshot of the UTXO-set, play it back into the blockchain, and then cull the blockchain prior to the snapshot.

I would like to see this drafted into a BIP.

1) This hash could, in principle, be generated along with every block and inserted into a Merkle tree.

2) There is more than one way to define AONT - for the purposes of the present proposal, you could simply encrypt the snapshot UTXO-set using its hash as the key without loss of any required security property.