Minimizing Bitcoin transactions using Utreexo (Part 1)

Every time a user transfers Bitcoins, new addresses or unspent transactions (UTXOs) [1] are created to take the remainder of the sender’s Bitcoins. Every full-node on the networks is constantly updating their own UTXO sets such that everyone can know which address have what amount of money. Due to the growth of Bitcoin, UTXOs have grown massively. Currently, there are over 60 million UTXOs which accounts for 3 GB of storage needed by each full node running the Bitcoin protocol. If we assume that Bitcoin’s transactions will grow, then this will become a major problem. In order for Bitcoin to be decentralized and gain mass adoption, anyone should be able to easily store and verify this state on their own laptops or even mobile devices. Therefore, it’s important to find ways to shrink the size of the UTXO set, or at least decrease the growth rate. There are various efforts to solve this problem, from solutions such as lightning network which decreases the total number of transactions that needs to be stored on the blockchain, to ideas such as “segregated witness.” However, these solutions by themselves may not be enough. It would be great to be able to have a system which can decrease UTXOs to either constant size or at least logarithmic in size. This is how research into accumulators to Bitcoin began.

Currently, research into accumulators is focused on two approaches. 1) RSA based accumulators and 2) Hash-based accumulators. The following section presents a review of the two forms of accumulators.

Accumulators

Cryptographic Accumulators was first introduced by Josh Benaloh and Michael de Mare in 1993 in their paper, “One-way Accumulators: A decentralized alternative to digital signatures”[2]. This design enabled a person to provide membership proofs for a set without revealing information about the entire set. This is achieved through algebraic one way functions that have the following prop- ertyz=h(h(···h(h(x,y1),y2),···,ym−1)ym)where a user can prove that it is in the set at a later time by providing h(zj,yj) through a quasi-commutative function h such that h(h(x, y1), y2) = h(h(x, y2), y1), where x is a random value and yi is a value from the users.

In general, accumulators have the following set of functions:

• Acc ← Gen(Items)
• Acc′, Proof ← Add(Acc, Item)
• Acc′, Proof ← Delete(Acc, Item)
• Result←Verify(Acc, Item, Proof)

Accumulators can be used in variety of places, from a decentralized certificate authority to searching through encrypted data. Recently, accumulators were used within decentralized cryptocurrencies such as in Zerocoin in providing a zero-knowledge proof and public variability that someone owns currency, without revealing anything other than the person knows a secret value within a set thus concealing their identity while still maintaining while still enabling them to prove ownership of coins [7]. One of the key benefits of using accumulators is the size of the proofs required. For RSA accumulators this can be constant sized.

This is critical, because it enables faster computation and for the system to scale in the number of users and transactions.

NOTE: This review is a summary of the works of Thaddeus Dryja from MIT and Aurel.

Reference:
[1] Lightning Network:
https://en.wikipedia.org/wiki/Lightning_Network

[2] SegWit: https://en.wikipedia.org/wiki/SegWit