btc utreexo - utxo accumulator
2022-09-16 · 2 min read
- paper: https://eprint.iacr.org/2019/611.pdf
- github: https://github.com/mit-dci/utreexo
- related (2016 - delayed txo commitments): https://petertodd.org/2016/delayed-txo-commitments
- current compressed UTXO set size ~4 GiB
- btc full nodes would like to verify txns w/o storing full history + UTXO set (need to actually download more data though).
- instead, build UTXO set accumulator and have transactors present inclusion proofs for their txn inputs in the UTXO set, so you (the full node) can verify the txn.
- utreexo: use a dynamic accumulator to commit to the current UTXO set.
- log(n): forest of perfect merkle trees. log n trees, where n is # UTXOs
- dynamic: efficient batch removal
- different than merkle accumulator we used for txn history in diem (a merkle mountain range (MMR)), which was append-only with efficient inclusion, non-inclusion, and batch update proofs but no removals (used jellyfish sparse merkle tree for that).
- accumulator isn't commited to in consensus / block header / block. have to sync the whole thing from scratch lol.
- optimizes for min. persisted space vs max. bandwidth usage.
- per Tadge's words: "not a commitment", though you can certainly (ab)use it as one.
- new block producer (or bridge node) can add aggregated UTXO accumulator insert/remove ops to get utreexo nodes to verify block.
- transactors (or the full node they use to propagate) need to store the partial UTXO set accumulator, containing their UTXOs, so they can produce inclusion proofs.