"Utreexo: A dynamic accumulator for bitcoin state" by Tadge Dryja

Overview: https://dci.mit.edu/utreexo

Presented over the weekend at MIT Bitcoin Expo 2019

Paper: https://eprint.iacr.org/2019/611

2 Likes

Related: Benedikt Bünz's UTXO commitments / RSA Accumulators

I need to read more about utreexo but my understanding is this is basically using something along the lines of Merkle proofs.

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.

So they may be “compact” but they do increase the tx size significantly.
You trade smaller chain state for larger txs.

1 Like

via @goldenMetteyya in /dev:


It seems like Utreexo is still a Merkle tree construction that is reshuffled to be kept compact with an impact on having to update all merkle proofs in the client (Tadge thinks it’s not that big of a deal).

@antioch as I understand it, the way the PMMRs are used in Grin, we don’t need to rewrite any proofs, right?

Paper has now been published (thanks @mably!) https://eprint.iacr.org/2019/611

2 Likes

Notes from the coredev.tech Amsterdam 2019 meeting on Utreexo:

http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2019-06-06-utreexo/

1 Like