"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


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


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


1 Like

Utreexo demonstration release


Is the accumulator used in utreexo safe enough? I think It has not been well proved.

If it’s the Merkle root of a tree or forest with a cryptographically secure hash function (and to be safe, no confusion between leaves and internal nodes) then it’s considered rather safe.

1 Like

I only now found the utreexo thread so I’ll link my other thread I created a few days ago. I suspect if we ever went this route, we wouldn’t need the utreexo accumulator because we can use the output PMMR and the bitmap MMR to achieve the things that utreexo brings. I’m not 100% sure but I described how to do that here Constant size fully validating node

I don’t think we will need this any time soon. Kernel aggregation and dropping rangeproofs will be good enough for a long time.


1 Like