CHIP 2021-07 UTXO Fastsync

CHIPs Standards Track
,
#71

yes,

so lets aim to make the fastsync actually capable of doing so. Because if we don’t then the vast majority of people that are indeed going to use SPV wallets can no longer use BitcoinCash as more and more fastsync nodes start popping up.

As I pointed out for some time, there is a logical error in your steps to get from the basic sync as the CHIP now states to actually being able to serve wallets. If you don’t believe me, then prove me wrong by building your suggestion in some proof of concept.

Arguing here makes no sense. This forum software is telling me I’ve commented enough on this thread. And, you know, its right. I’m not going to continue nicely trying to save you from the mistakes I see (for 18 months now) and you are not seeing.

Build it, saves us a lot of talk.

#72

BLISS Presentation: Committing to UTXOs with Calin Culianu

4 Likes
#73

It recently occurred to me that a SPV wallet doesn’t need the transactions and proofs from the timepoint before the UTXO snapshot. The node can just give the wallet the relevant UTXOS and the wallet is able to spend it by signing with SIGHASH_UTXOS.

This will simplify everything significantly since a node serving thin wallets don’t need the additional historical data.

4 Likes
#74

Yeah! In that case, no need for this:

You can safely assume that the UTXOs you were given are legitimate and try spend them with SIGHASH_UTXOS. If the TX fails, it can only be one of the 2 reasons:

  • The UTXO doesn’t exist (TXID:n doesn’t match any UTXO)
  • The UTXO exists but data is corrupt (TXID:n matches some UTXO, but you got the wrong contents for it)
1 Like
#75

It has come to my attention that Kaspa has already implemented UTXO commitments in block header and new nodes sync off headers and UTXO snapshots. I dug out a blog post by Yonatan Sompolinsky:

Accordingly, Kaspa nodes prune block data by default, and new nodes by default do not request historical data, rather, they sync in SPV mode, i.e., by downloading and verifying only block headers. I reiterate that this is not a stronger trust assumption than a history-verifying node, rather a different requirement. The node then requests the UTXO set from untrusted peers in the network, and verifies it against the UTXO commitment embedded inside the latest received header (technically, this is done against the latest pruning point). If those do not match, the node bans the sending peers, requests the UTXO set from new untrusted peers, and repeats the process. If those match, the node verifies that no unexpected inflation occurred by comparing the sum of UTXOs to the specified minting schedule, a comparison for which block headers suffice.

Not only that, but they’re not using EC multiset, but something else. I asked them about it and the said Muhash had better performance, and they were in fact using EC multiset and then replaced it by Muhash, as evident in this PR: Replace ECMH with Muhash by elichai · Pull Request #1624 · kaspanet/kaspad · GitHub

5 Likes
#76

Note I am aware of MuHash and we will evaluate it too. We already added it as a potential hasher to BCHN: src/crypto/muhash.h · master · Bitcoin Cash Node / Bitcoin Cash Node · GitLab

3 Likes
#77

You’re amazing, sir! Always ahead of the game!

#78

TIL BU/Nexa did it another way:

We use a compact bitwise prefix trie rather than a Merkle tree, so that miners commit only to the set of transactions each block. The order that transactions are added to the trie does matter. This trie structure then enables compact proofs that a coin is unspent.

– Peter Rizun on X

2 Likes
#79

Asked about trade-offs when compared to EC multiset:

EC multiset doesn’t enable compact membership proofs: you CAN prove you have the right set, but you can NOT prove that a given coin is a member of that set in a compact way.

The trade-off is that to get the compact membership proofs, the UTXO set must be stored in a specific structure (e.g., a compact bitwise prefix trie). It would be difficult to shoehorn that trie structure efficiently into LevelDB. So implementing EC multiset is easier.

We’d use a 256-bit commitment (same as Merkle root) so commitment size is small in both cases.

It scales a log(N), so each insert/delete costs a bit more the larger the UTXO set grows. But it never becomes unmanageable: even for very very large UTXO sets it’s less computationally than a single elliptic curve point multiplication.

You can roughly think of it as hashing one branch of the trie, from leaf to root, to update the commitment.

– source

May be worth the trade-off, log(N) for capability to make compact proof about any UTXO.
This would mean that contracts could “read” any UTXO without it having to be spent or referenced by the TX. The spender would provide the UTXO+proof as input script.

Speaking with @cculianu it’s probably NOT worth it, it would tie our hands for future scaling, having an irremovable O(log(N)) operation part of validation critical path. Even if the constants are low so time per UTXO is small even with a 1T set, still, an O(1) algo would outperform that. There’s also the question of parallelization. All those problems, for what benefit?

2 Likes
#80

Exactly. How useful is a UTXO proof? You know that at exactly height N, the moment block N was confirmed, UTXO U was unspent.

You do now know if has since been spent. (At least the proof itself provides you with no guarantees in that regard!! Think about it!).

For applications that truly care about this (I ask which ones care?) – you have no way to know if the UTXO is unspent without additional information and/or things you must do anyway.

For the lite wallet case, UTXO proofs are of limited use and do not really tell you more than you couldn’t have equally figured out with simple SPV proofs of txns which we have now.

A lite wallet also knows which UTXOs it has signed for and which it has not – so for it, receiving a simple SPV txn proof is enough for it to know the UTXO is still unspent – since it knows it never spent it!

So yeah, the UTXO proof is not that useful I think, in the real-world, and it comes with some burden.

Also – there are faster algos for multisets. EC Multiset is just one. Core is flirting with MuHash which is 10-100x faster per add/delete than EC Multiset. Just sayin’.

1 Like
#81

Yeah, Kaspa already implemented it for their UTXO commitments: CHIP 2021-07 UTXO Fastsync - #75 by bitcoincashautist

#82

Peter Rizun was talking about UTXO commitments on Bitcoin Takeover at 1:57:12. Elaborates a little on compact inclusion proofs.

1 Like
#83

Yeah I did a proof of concept using muhash in bchn.

Advantages; much faster

Disadvantage: the data blob for the set itself is not as compact as 33 bytes for ECMH — but rather is 384 bytes. Not huge but not tiny either. So if you wanted to actually embed the set itself into the blockchain (rather than its hash), it’s a bit heavy.

2 Likes
#84

First the obvious;
commitments can work just fine without it being part of the blockchain. LOADS of work to get that done anyway. So the idea to put it in the coinbase is premature by probably several years. I expect that we will never actually need this as software and bandwidth increase fast enough. Though its a cool idea to develop and make ready if I’m wrong.

But the main thing I’d like to point out in regards to the muhash idea is that you can still trivially add a hash in the client (or later in the coinbase) to prove the commitment. All you need to do is move that 384 bytes content to be included in the actual utxo download. Which will be 10GB or so, therefore the extra bytes will not matter.

4 Likes
#86

I would also add that MuHash provides a root hash as a candidate for committing to the UTXO set in a scalable way. This can be used in UTXO commitments because MuHash by itself doesn’t support Merkle-style proofs or direct filtering, UTXO commitments are still essential for upgrading RPA with ECDH-based one-time addresses (like Silent Payments, BIP352). Without them, wallets would need to scan the full UTXO set to detect incoming payments. A commitment scheme that supports inclusion proofs could allow more efficient filtering, making ECDH-based detection more scalable and usable for light clients.

#87

Wait – are you saying MuHash is more compatible with a merkle proof scheme somehow? Can you link me to any resources on this?

#88

Not at all, thanks to BCA for the correction. I’m saying MuHash can be used as a compact way to commit to the UTXO set. The idea is that if we had an auxiliary structure alongside MuHash (like a Merkle accumulator or an index), light clients could use that for proof-based lookups.

Here’s the Bitcoin Core PR using MuHash for compact UTXO commitment but without proofs:

And here’s Utreexo, a Merkle-like accumulator designed to enable UTXO membership proofs for light clients:

So, MuHash could be one example of a compact UTXO set commitment candidate not that MuHash alone supports Merkle proofs. It efficiently provides a root hash, but to enable filtering or inclusion proofs, you need additional proof structures like Merkle trees or accumulators (e.g., Utreexo) for UTXO Merkle-tree commitments.

#89

Given the impressive progress and standardization of zero-knowledge tech, and knowing that this allows to prove expensive computation in a trustless way, it has been suggested that ZKPs could be leveraged to get a proof for a recent UTXO set.

Instead of trusting peers for a checkpointed UTXO set or to require the protocol to enforce miners to provide a commitment to the current UTXO set, this could possibly be done in a trustless way without the protocol complexity just by leveraging ZKPs and the P2P network

I’d love to see some more discussion on this topic in 2026

5 Likes
#90

See this Tweet from Jason with more information about the ZKP for UTXO commit concept.

Seems like it’s the Starkware guys who are most interested in that. That team is in a weird place where they’ve definitely figured out BCH is far superior, but are still erring on the side of sticking to BTC due to either fear of backlash from BTC guys or for investor requirements.

In any case, I wouldn’t put a lot of stock in them actually coming through with BCH solutions (even if it would benefit everyone immensely, including themselves) so if that happens it’s more of a bonus. But realistically we’ll need to find some actual BCH aligned people to look into all this (hard to do because it’s so specialised of course).

1 Like
#91

I guess it is helpful to give a tad more understanding of the scope of fastsync.

The actual concept itself isn’t too big, some people have already done various test implementations and tried out the idea of a full download of the utxo set.
There are various approaches that makes sense and they can be tried in the basic idea of utxo sync.

But there are various parts of infrastructure that are needed to actually create any benefit to the bigger whole of bitcoin cash. And these are not small since they are so core to the full node design.

  1. The storage of the utxo set itself will have to be changed in order to allow something other than a full backup and share of the database. The incremental nature of the sync ID is to be taken into account here, probably some copy on write structure to allow to have multiple snapshots that can be shared via the p2p network.
  2. The block pruning concept as it is today is incompatible with full node duties of a fastsync node. The full node would need to follow something like the design from the whitepaper to avoid losing information on pruning.
  3. Other nodes should be able to get recent blocks that are partly pruned from any fastsync node, to allow the bitcoin cash p2p system to continue to run. This means a new historical block transfer method that can transfer pruned blocks with an intact merkle-proof.

My suggested approach to get fast sync coded is as a first phase to play with the (merkle) proof concepts of the utxo set itself, on a live full node. The ability for a normally synched full node to reach a utxo proof which is hardcoded in the full node at build time would be a powerful first step to allow the operational basic concepts to actually be tested in the real world.

A big release later of the full node this can be expanded.
The full node shipping a utxo set hash means the full node can be kick started from a downloaded utxo set. The caveat is that that full node would be similar to a pruned node today, it can’t be used for SPV servers (either bloom or fulcrum). So this again is a good step to get wider testing but production deployments will be waiting.
The fact that the actual utxo hash is hardcoded at the time of the full node release is a feature, not a bug. It means that every single release major changes are possible without disrupting existing installations. No need to be super specialized in your knowledge and art, a much wider group of people will be able to work on this. Mistakes in the actual utxo proof code won’t have a disrupting effect.

This alone is a LOT of work, as a result it gets more hazy after that as it is predicting an unwritten future. But the ability to have some actual p2p protocol for fast sync is well after these steps, some hash in a block is even harder to predict how we get to that.

ps. I’m not working on this as I did the math and I don’t expect this feature to ever be in need by the network, the growth of hardware and bandwidth, and improvements in software are enough to avoid IBD to become a real problem for bitcoin cash.