Utreexo: A dynamic accumulator for Bitcoin state - A description of research by Thaddeus Dryja

Utreexo: A dynamic accumulator for Bitcoin state

One of the earliest-seen and most persistent problems with Bitcoin has been scalability.  Bitcoin takes the idea of "be your own bank" quite literally, with every computer on the bitcoin network storing every account of every user who owns money in the system.  In Bitcoin, this is stored as a collection of "Unspent transaction outputs", or "utxo"s, which are somewhat unintuitive, but provide privacy and efficiency benefits over the alternative "account" based model used in traditional finance.

It's important to distinguish between the transaction history and the current state of the system.  The transaction history in Bitcoin is currently 200GB, and contains every transaction since Bitcoin was launched early 2009.  The size of this history can of course only increase with time. The current system state, however, is much smaller, at under 4GB, and deals with only who owns what right now.  This state size has generally increased over time, but has in fact decreased a bit this year.

The history, despite its much larger size, is not in fact the scalability concern, as it is not used in any time-critical fashion; one can discard the history after processing with no loss of security.  The increasing state size, however, is a concern -- one which utreexo solves.

Utreexo is a novel hash based dynamic accumulator, which allows the millions of unspent outputs to be represented in under a kilobyte -- small enough to be written on a sheet of paper.  There is no trusted setup or loss of security; instead the burden of keeping track of funds is shifted to the owner of those funds.

Currently transactions specify inputs and outputs, and verifying an input requires you to know the whole state of the system.  With Utreexo, the holder of funds maintains a proof that the funds exist, and provides that proof at spending time to the other nodes.  These proofs are compact (under 1KB) but do represent the main downside in the utreexo model they present an additional data transmission overhead which allows much smaller state.

Utreexo pushes the costs of maintaining the network to the right place:  an exchange creating millions of transactions may need to maintain millions of proofs, while a personal account with only a few unspent outputs will only need to maintain a few kilobytes of proof data.  Utreexo also provides a long-term scalability solution as the accumulator size grows very slowly with increasing size of the underlying set (the accumulator size is logarithmic with the set size)