Re: [bitcoindev] [BIP Draft] P2P UTXO Set Sharing

[Anthony Towns <aj@erisian.com.au>]

On Tue, May 05, 2026 at 03:36:04PM +0000, 'Fabian' via Bitcoin Development Mailing List wrote:
> #### Chunk Merkle Tree
> The serialized UTXO set (header + body) is split into chunks of exactly 3,900,000 bytes (3.9 MB). The
> last chunk contains the remaining bytes and may be smaller.

> ### Messages
> `getutxotree block_hash`
> `utxotree block_hash version data_length num_chunks chunk_hashes`
> `getutxoset block_hash chunk_index`
> `utxoset block_hash chunk_index data`

Had a bit more of a look at this, I'd like to suggest some changes:

 * hard code a basic summary for the snapshot block in chainparams, eg at
   height 935,000:

```
{
  "network": "main",
  "base_blockhash": "0000000000000000000147034958af1652b2b91bba607beacc5e72a56f0fb5ee",
  "coins_count": 164241311,
  "data_length": 9387990306,
  "merkle_root": "278d5f18f035129f43849322801d16731d8154f80ed97ee48a88b355dc42f3a8"
}
```

 * identify the utxo set by merkle_root, which commits to both the number
   of chunks and the size and contents of each chunk. use tagged hashes to
   avoid ambiguity between leaf and internal nodes. include the txoutset
   header in the merkle tree, not just the coins, so the base_blockhash
   and network are committed to too.

 * have each chunk/leaf be 65,536 bytes (except for the last) -- power
   of 2, so they aligns with filesystem pages when stored, and small
   enough so that you're not wasting much data if a chunk is bad or
   truncated or whatever. you calculate number of chunks directly from
   data_length.

 * deal with chunks in sets of 2048: 2048 64kB chunks is 128MB, so a
   reasonable file size; and 2048 32B hashes is 64kB so an equally
   reasonable message size

 * as far as syncing goes, get the chunk hashes in sets of 2048 (about
   70 requests needed on mainnet):
     `getutxohashes merkle_root index`
     `utxohashes index path_to_merkle_root hashes...`
   by providing the path to the merkle root in addition to the hashes
   (~300 bytes on mainnet) each message is verifiable on its own,
   without much overhead compared to the 64kB of hashes

 * then you have the hash for each leaf, and can request them in parallel,
   validating each one as it's received:
     `getutxoset merkle_root index`
     `utxoset merkle_root index txoutsetdata`
   with each response verified against the previously verifed chunk/leaf
   hash

I think keeping messages small is better for the the net subsystem in
general, and beyond that, dealing with 64kB chunks would probably also
allow for more aggressive retries without wasting as much bandwidth,
if you want to avoid getting stalled due to a slow peer. Grabbing the
chunk hashes in batches also makes the approach remain viable even if
the utxo set grows absurdly large.

I've got a little vibe-coded exploratory tool based on that set of ideas:

https://github.com/ajtowns/bitcoin/blob/202610-auto-utxo-snap/contrib/utxo-tools/utxo_snapshot_chunks.py

You can use it like this:

 * bitcoin-cli -rpcclienttimeout=0 -named dumptxoutset path=utxos-965000 rollback=00000000000000000001595977e6000ce56129f5c9b4073e31ccc30b90b97da9
   - get the dump

 * bitcoin-cli gettxoutsetinfo muhash 965000
   - get info at that block (if you have coinstatsindex enabled)

 * ./utxo_snapshot_chunks.py split utxos-965000.dat snap/
   - split it up, calculate metadata, merkle root

 * ./utxo_snapshot_chunks.py summary snap/
   - get the "basic summary" info mentioned above

 * ./utxo_snapshot_chunks.py verify snap/ --muhash 470693633245ed8224580c7ccc8676a279336abd83a71b02f8345d1cb3861b77 --total-amount 20077898.00887204 --bitcoin-util ../../build/bin/bitcoin-util
   - verify the utxo set's hashes, and (optionally) check it has the
     expected muhash and spendable amount as well

 * ./utxo_snapshot_chunks.py init dupe $(./utxo_snapshot_chunks.py summary snap/  | jq -r '.network, .base_blockhash, .coins_count, .data_length, .merkle_root')
   - initialize a copy from the summary information

 * for a in `seq 0 25`; do ./utxo_snapshot_chunks.py getleafhash snap/ $a | ./utxo_snapshot_chunks.py addleafhash dupe/; done
   - populate the hashes, one set of 2048 at a time (simulating
     getutxohashes/utxohashes messages; assumes there's 26 sets total)

 * for a in `seq 0 51`; do ./utxo_snapshot_chunks.py getleaf snap/ ${a}000 ${a}999 | ./utxo_snapshot_chunks.py addleaf dupe/; done
   - populate the chunks, 1000 at a time (simulating getutxoset/utxoset
     messages; assumes there's 52000 total)

The "verify" step relies on a new bitcoin-util subcommand, particularly
for the muhash and total-amount checks. Run directly, it looks like:

```
$ time ../../build_rel/bin/bitcoin-util -muhash txoutsetsummary < utxos-935000.dat 2>/dev/null
{
  "bestblock": "0000000000000000000147034958af1652b2b91bba607beacc5e72a56f0fb5ee",
  "txouts": 164241311,
  "total_amount": 19984148.03206779,
  "hash_serialized_3": "e4b90ef9eae834f56c4b64d2d50143cee10ad87994c614d7d04125e2a6025050",
  "merkle_root": "278d5f18f035129f43849322801d16731d8154f80ed97ee48a88b355dc42f3a8",
  "muhash": "1ea5b8ebafcd8929fbedc23b180333a9a1610e2f13b88daedafa53af0fea3b35"
}

real    1m11.944s
user    13m35.131s
sys     0m3.513s
```

Or you can use the split up files:

```
$ time cat snap-935000/txout00*.dat | ../../build_rel/bin/bitcoin-util -nomuhash txoutsetsummary 2>/dev/null
{
  "bestblock": "0000000000000000000147034958af1652b2b91bba607beacc5e72a56f0fb5ee",
  "txouts": 164241311,
  "total_amount": 19984148.03206779,
  "hash_serialized_3": "e4b90ef9eae834f56c4b64d2d50143cee10ad87994c614d7d04125e2a6025050",
  "merkle_root": "278d5f18f035129f43849322801d16731d8154f80ed97ee48a88b355dc42f3a8"
}

real    0m58.223s
user    2m7.628s
sys     0m14.686s
```

Skipping calculating the muhash doesn't save much wall time for me,
but does save a lot of cpu time. YMMV.

> **3.9 MB chunk size:** The number balances round trips (~2,560 for a ~10 GB set) against memory usage
> for buffering and verifying a single chunk. Smaller chunks would increase protocol overhead;

I don't think the increase in overhead from ~4MB chunks to 64kB chunks
is very significant. The metadata store for keeping track of 143k chunks
at height 935000 is only about 4MB:

-rw-rw-r-- 1 aj aj 4602001 Oct 15 16:10 snap-935000/meta.dat

That's about 0.05% of the 9GB of utxo data, or compares against ~80kB
of metadata for ~4MB chunks (which would be 0.001%).

If we want to later allow disk-constrained nodes to also participate,
then FEC encoding and storing 1/16th to 3/16th of the utxo set (so
630MB to 1900MB rather than 10GB) should be plausible, but because you
can only validate hashes after combining shards, having each chunk be
smaller (64kB chunks with 16-shards per chunk means each shard is 4kB)
is probably better. I think it would be possible to do a leveldb snapshot,
then calculate the data needed to serve FEC shards reasonably efficiently.
I think every node would store all the hashes (the 4MB meta.dat/utxohashes
response data), and only reduce the size of the 10GB txoutset*.dat data
via FEC encoding.

If we wanted to be more bittorrent-y, and in particular allow nodes
who've only partially downloaded the utxoset to provide chunks to other
nodes also downloading it, I think we'd need an additional message to
indicate which chunks a node actually has available for download. Would
probably also want to provide some sort of custom "addr" sharing to
help such nodes find each other, since they almost certainly won't yet
be participating in ordinary addr relay due to not having completed IBD.

Cheers,
aj

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/atCSAVprBE-tAnN3%40erisian.com.au.