CHIP 2021-07 UTXO Fastsync

[yashasvi911]

@joshmg

UTXO Buckets

Instead of downloading and serving the entire UTXO commitment snapshot as a single multi-gigabyte-sized file, each commitment is distributed into multiple buckets.
The generation of these buckets is canonical and parallelizable.
Each bucket’s EC multiset public key is defined by its contents.
The sum of the bucket’s EC multiset public key sums to the overall commitment’s public key.
The rules specifying the buckets is convention only, and is not enforced by mining nodes.
Peers with incompatible bucket definitions ignore the commitment breakdown after recognizing its incompatibility.
The current convention recommends 128 buckets; using a different convention could render snapshots incompatible between implementations.

Each UTXO is placed in its canonical bucket by taking the first 7 bits of the first byte of a single Sha256 hash of the following preimage, and interpreting the resulting bits as an integer index:

1. the commitment’s block hash**, as little endian
2. the UTXO’s transaction hash, as little endian
3. the UTXO’s output index, as a 4-byte integer, little endian

Do you think it would make sense to split the UTXO buckets using sorting based on locking script instead?

I’m not very sure of the possible implementation, but something where the UTXO set would be sorted by their locking script and then split such that all 128 buckets are of uniform size or close to it.

Here, the snapshot SubBucket Metadata may then look like:

Field Name	Byte Count	Format	Description
public key	33	public key, big endian	The secp256k1 point of the EC multiset for this UTXO snapshot sub-bucket.
start lockingScriptByteCount	1-4	compact variable length integer	The number of bytes in the starting** locking script of the SubBucket (as a compact variable length integer).
start lockingScript	?	big endian	The starting** locking script of the SubBucket (“scriptPubKey”, “pk_script”).
byte count	8	integer, little endian	The number of bytes within this UTXO snapshot sub-bucket. The sum of these must equal the byte count of the snapshot bucket.

** The ending lockingScript of a SubBucket is the starting lockingScript of the next.

Advantages:

• This can foster a new kind of light wallet that can easily query their UTXO set from nodes. The wallet can query extra SubBuckets or SubBuckets from different nodes to circumvent nodes omitting UTXOs by not following the ordering. By checking the ordering in the SubBucket and its EC mutliset, the wallet can determine if the node follows the UTXO ordering.
• The wallet may maintain the privacy of the user by downloading extra SubBuckets to obfuscate the intended locking script query. These extra SubBuckets can also be used to check the UTXO ordering of the node.
• Such wallets won’t have to build a history of transactions over the blockchain or query the entire UTXO set. This gets even safer if the EC multiset is committed to the block header.
• Since such UTXO set is generated once per block, a node does not need to generate additional filters for each wallet subscribing to a locking script (or maybe my understanding of SPV is at fault).

Disadvantages:

• Will add overhead of splitting the UTXO algorithmically. However, clever schemes of passing UTXO sets from one SubBucket to another can leverage the O(n) operation of generating EC multiset.
• Nodes may not follow the UTXO ordering so closely, and will lead to omission of UTXOs.
• Increases the size of P2P UTXO Commitments (“utxocmts”) message.
• The UTXO set may be flooded by UTXO with the same locking script to make the ordering and SubBucket formation difficult.

[BitcoinCashPodcast]

I don’t know what the current state of these UTXO committment ideas are, but Tadje Dryja of Lightning Network fame did a whole talk about block size increases and a “proof of inclusion” UTXO system to scale on-chain on BTC. Interesting idea to observe.

Baltic Honeybadger 2023 conference livestream day 2

[tom]

@BitcoinCashPodcast

don’t know what the current state of these UTXO committment ideas are

there are some pretty big problems that need solving and nobody is working on them.

1. The basic concept of compressing the entire UTXO set to a single hash is stalled, the approaches tested have proven to be not good enough. The resource usage would be too great.
2. starting a full node from a committment is useless with the current state of pruning. That node would not be able to share historical blocks, it would not be able to serve as an SPV node (or fulcrum backend) and it would not be much use for anything else than a private wallet or mining node.

Should all this get solved and the system works well, I would still suggest running it permissionlessly for maybe a year by selected miners before adding the commitment should be included in the blockheader (somehow) in some mandatory fashion.

[joshmg]

@tom

The basic concept of compressing the entire UTXO set to a single hash is stalled, the approaches tested have proven to be not good enough. The resource usage would be too great.

I’ve been out of the loop for a little while, but getting back into it, so forgive me if the answer to this question is somewhere above and I just missed it. That being said, where did your assertion come from? I don’t think I saw anything about the ec multiset being too expensive. Did BCHN do a test and that was their conclusion, or am I misunderstanding?

@tom

starting a full node from a committment is useless with the current state of pruning. That node would not be able to share historical blocks, it would not be able to serve as an SPV node (or fulcrum backend) and it would not be much use for anything else than a private wallet or mining node.

Fast synced nodes are pruned nodes, so I think what you’re saying is that pruned nodes are worthless, so therefore fast-sync is worthless. Is that a correct interpretation of your opinion? If so, I think it’s not quite a fair conclusion; Bitcoin Verde can run its explorer with a pruned node (which obviously omits pruned data but is useful for address balance-checking and transaction review/inspection). Additionally, pruned nodes can serve most requests needed on the electrum API; the only downside is you won’t be able to get a list of your historical spent outputs. However, I think that’s perfectly acceptable in the scheme of long-term scaling. Let me know if you’re thinking of things I am not.

[tom]

Hi Josh,

things have not changed since this post.

What you write that is possible with such pruned nodes I acknowledge in the post you reply to, just in different words.

For a permissionless idea, its fine. It works for private nodes, you can trust it and point your wallet to it. Most of the time it will work. Just don’t import a seed or sync a BCMR, or anything else which requires historical transactions.

The point is that pruning as defined in the whitepaper is about removing only data that is no longer relevant because it has been spent. This is not yet implemented in any software. Pruning we actually have is less subtle, it deletes entire blocks at a time. Which includes unspent transaction outputs.

Pruning can be fixed to only delete the spent outputs, this together with merkle-proofs means you can still do SPV trustless. Because the node can provide historical transactions AND their merkle-proofs as long as said transactions are unspent.
Instead a pruned node is incapable of generating a merkle-proof of unspent transactions. Because it doesn’t have the merkle-tree for that block at all. The entire block is removed.

So, sure, you can spin up a full node that is pruned, but people can’t get the proofs needed from it, they need to trust your node. And that misses the point for the wider network.

So, please don’t take this as criticism towards Verde. The fact that this is on this website was the assumption that this is about the interoperability of multiple nodes, of perhaps moving this to the consensus layer. And this is the basis of my comments.

Bottom line is, if most nodes being spun up start using this commitment method, it will stop all wallets of actual users being able to do their thing.

[tom]

@joshmg

That being said, where did your assertion come from?

I’ve been spending more time looking, but I can’t find anyone reporting otherwise. I can’t find a single report of CPU time or data-processing time. I can’t find any results stating it is “good enough”.

If you have actual information stating otherwise, some amount of milliseconds used to process a block of N transactions (or outputs), that would help us determine that it is in fact good enough.

In my world, if nobody publishes their success, there is no succes and further research is needed. Apologies if that is naive, I just don’t have time to implement the algo myself to test if its good enough. I assume if others reach success that they will say so out loud and proud…

[bitcoincashautist]

@tom

I’ve been spending more time looking, but I can’t find anyone reporting otherwise. I can’t find a single report of CPU time or data-processing time. I can’t find any results stating it is “good enough”.

Because there is none, yet. The “Implementations costs and risks” and “Ongoing costs and risks” sections are still marked “TODO”, which is why this hasn’t moved forward for a while. Someone™ has to do the necessary work, and it hasn’t happened yet.

@tom

In my world, if nobody publishes their success, there is no succes and further research is needed.

Agreed. However, I think we can also make a preliminary analysis from first principles. Based on that, the expectation is that it will be proven performant once performance tests do get done, else this would all be a waste of time. Let’s do the preliminary analysis here step by step.

First we have to make one thing clear, because it impacts everything downstream. This proposal is NOT using Merkle tree commitments, and it is NOT using Utreexo like what ZeroSync for BTC would. This proposal is using EC Multiset as the building block - which has the feature we want: O(1) insertion and removal.

The trade-off is that it can’t be used to verify that a single element belongs to the set. It can only be used to verify that the whole set matches the commitment - and that’s OK, because it is the only thing that we want from it: be able to verify the whole UTXO state at some height N, obtained from some untrusted source.

Let’s say you have commitment N and UTXO database state at height N, and you want to generate a commitment for UTXO database state at height N+X, what do?

To get the database state, you do what you do anyway - delete and insert UTXOs from / into the database as you process each TX in a block, right? That’s the O(1) operation nodes already do.
At the same time, you can delete and insert from / into the commitment, which would be just another O(1) operation performed for each UTXO spent / created by a TX, and one such that it doesn’t require disk i/o (unlike actual UTXO db ops). Updating the commitment to add or remove a single UTXO is an operation that fundamentally requires a single hash operation and a single EC addition or subtraction - much cheaper than a sigop which requires an EC mul.
This wouldn’t change the O(N) scaling law for block validation - it would only slightly increase the cost per transaction.

I found something related that could give us an idea of what to expect:

On the other hand, we demonstrate a highly-efficient software implementation of ECMH, which our thorough empirical evaluation shows to be capable of processing over 3 million set elements per second on a 4 GHz Intel Haswell machine at the 128-bit security level—many times faster than previous practical methods.

– Maitin-Shepard, Jeremy, et al. “Elliptic Curve Multiset Hash” (2016)

[tom]

Thanks you for confirming my point, it looks like the problem may be smaller than I thought, but still not exactly solved. So my short update wasn’t wrong, but more details is good. Although its not a short update anymore

On the multiset approach.

This approach has a bit of a problem in that it has no intermediate state. What I mean with that is that you may end up modifying this 33 bytes array until the end of time and the cost of validating it will continue to rise as the utxo set itself grows.
This naturally goes hand in hand with the actual UTXO set itself growing in size.

Most systems have something like a checksum they apply to a much smaller section of the data, fail fast is a first principles design approach.

This reminds me of the design I applied in the UTXO-database that is part of Flowee the Hub. Instead of having one huge database, it is instead split into a bunch of databases based on the very real statistic that utxo spending tapers off as the output gets older. If you were to plot the age of a utxo you’ll see it starting with very short lifetime and as you add on years it very significantly drops steadily.

The effect of this is that if you were to design a database that holds only the first N years (or first M-million utxo entries), it will see less and less updates to it as time moves on.

In Flowee the Hub you’ll find it creates some 20 databases as it syncs the chain from zero. With less and less changes to each database as new ones are added.

This same could be done with multi-sets. You could have a new multi-set every 6 months. With a multitude of benefits. Least of all is that it makes downloads much less risky as those sets now each can be a separate download.

[bitcoincashautist]

@tom

the cost of validating it will continue to rise as the utxo set itself grows

Only the node that’s performing IBD from a snapshot must validate it by adding the whole UTXO set to a {}-commitment, and doing that will take O(N), where N is the number of UTXOs in the snapshot. This is much faster than parsing the whole blockchain from 0 to construct the UTXO set at the same height. Instead of doing that, you’d get a snapshot for height N from whatever untrusted source, do the O(N), and compare it with the value written to associated coinbase message. Then, you only need the new blocks on top of that and never have to download the history (unless you want/need it).

For nodes that are in sync, they’d just be performing incremental updates to the last verified commitment. The size of the set compressed in the hash doesn’t matter - additions and deletions are O(1).

If you have a commitment to a set of N elements, and you have to update it to a set of M elements, you only need the N commitment and a “diff” between states N and M: some k elements that were added and j elements that were removed, and the update will take O(j+k) operations, regardless of N and M sizes.

[tom]

All you write is true, nothing you wrote invalidates the detected problem or improvement suggestions.

The problem I stated still exists, today it requires a 10GB download or so of the UTXO which then needs to be validated in total, if one byte is off you have no way to detect which byte in that entire set is incorrect.
If we move to a 100GB UTXO this is still true and a bigger issue still.

The idea I wrote solves that and additionally adds a lot of opportunity for more optimizations.

@bitcoincashautist

Only the node that’s performing IBD from a snapshot must validate it

Nitpicking, this is not true. If we assume that one day miners will include such commitments, they too will build it the hard way at least once.

[BitcoinCashPodcast]

I will need to read up on the details far more heavily, but intuitively I think this idea about the most frequent updates & changes happening on the most recent UTXOs and therefore some kind of bucketing system which helps to prioritise ease of updates there even if it means trading off some performance on the other chunks may make sense in some kind of bucketing system.

I can imagine a world where your pruned node comes online in chunks, starting with the most critical 10% of “UTXOs from the last month”, which are the ones also most likely to be respent, and then filling in each of the following 10% chunks which change progressively less and less often.

[bitcoincashautist]

@tom

if one byte is off you have no way to detect which byte in that entire set is incorrect.

Not at consensus level, no, but it doesn’t prevent the P2P layer from partitioning the dataset and having a way to verify integrity of each partition, using commitments to partitions (Josh calls it “buckets”). What’s nice is that you can add / subtract partition’s commitment from the top commitment without having the data that made the commitment. So even if your full snapshot is 100 GB and is not matching, but you find that a chunk of 1 GB is at fault, you only need to download some alternative chunk’s commitment, EC-subtract the faulty one then EC-add the supposedly good one, test the result against commitment in coinbase, and if good proceed to download the 1 GB. Once finished, just compute the 1 GB and verify against partition’s commitment and you’re good.

@tom

If we assume that one day miners will include such commitments, they too will build it the hard way at least once.

Sure, but the first snapshot can be built up before activation date. This problem is really implementation-specific, although it has to be handled in a performant manner for smooth activation.

Consider this method:

1. Get upgraded software 6 months ahead of the time to embed
2. Restart node to run it, it quickly resumes as if nothing much changed
3. The new version spawns an async process, parsing the stored blockchain linearly from disk, and adding/removing items to / from the commitment, and eventually it catches up to current height, and you have your commitment for some height N. It’s similar to calculating an average really… new_commitment = old_commitment + item; or new_commitment = old_commitment - item for removal, where - and + are EC ops. You don’t need to store the item, just gotta be sure you don’t skip any as you process the chain.
4. When activation time comes, you just have to add / remove whatever diff happened between N and 1st snapshot’s height N+x.

Minimal node implementation doesn’t need to generate, serve or download the UTXO snapshots.
It can just stream-process the UTXOs it pops/adds to be ready to verify the coinbase commitments.

Service that generates and serves UTXO snapshots can be independent, outside the node’s critical path!

[Jonas]

I’ve just been skimming this topic (and more importantly haven’t read the proposal closely), so please correct me if I’m wrong.

but you find that a chunk of 1 GB is at fault, you only need to download some alternative chunk’s commitment, EC-subtract the faulty one then EC-add the supposedly good one, test the result against commitment in coinbase, and if good proceed to download the 1 GB.

The problem is that you can’t verify if one specific bucket is “at fault” until you have verified all of them together. Sure, you can verify it against a P2P-level merkel tree of buckets on a non-consensus layer but there is no way of knowing if that merkel root matches the consensus level EC-Multiset commitment.

[bitcoincashautist]

@Jonas

The problem is that you can’t verify if one specific bucket is “at fault” until you have verified all of them together. Sure, you can verify it against a P2P-level merkel tree of buckets on a non-consensus layer but there is no way of knowing if that merkel root matches the consensus level EC-Multiset commitment.

Ah ok, but you don’t need to download the actual data in order to know which buckets you need, so you’d need to keep asking fast-sync servers for sub-commitments (how big is this, 33 bytes x number of buckets?) until you get a combination which when added up will match the top commitment embedded in a coinbase message. THEN you ask for the partitions, and you can verify each against a sub-commitment.

[Jonas]

@bitcoincashautist

Ah ok, but you don’t need to download the actual data in order to know which buckets you need, so you’d need to keep asking fast-sync servers for sub-commitments (how big is this, 33 bytes x number of buckets?) until you get a combination which when added up will match the top commitment embedded in a coinbase message. THEN you ask for the partitions, and you can verify each against a sub-commitment.

After reading the doc and some discussions on TG I understand your point.

One thing I would note is the fixed number of buckets in the Snapshot Metadata message (128). I would prefer to add a field bucket count that specifies the number of buckets for this snapshot. The value 128 could very well be marked as a recommended value and client implementations are free to reject any commitment that has a bucket count value that differs from 128. This way there is a freedom to roll out new recommended values in the future without needing a new utxocmts P2P message version.

On a related note the there is one fixed layer of SubBuckets in this message and those could theoretically be further divided into SubSubBuckets, SubSubSubBuckets and so on. Instead of the sub-buckets field in the Snapshot Bucket Metadata being of the type Snapshot SubBucket Metadata it could be recursive with a Snapshot Bucket Metadata type along with a SubBucket Depth field describing how deep the buckets are.
Note: the cost of inserting a transaction into such a structure is O(L) where L is the height of the tree.

[Jonas]

@joshmg

The generation of these buckets is canonical and parallelizable

How can a client verify this before the entire UTXO set is downloaded?
Let’s say a (bad-behaving) node moves one transaction from the first bucket to the last and then refuses to serve the last bucket.
A client would have to connect to a new (well-behaving) node and fetch the metadata, but the pubkey for each bucket would differ from what was fetched from bad node and thus needs to download the entire set again.

[tom]

This still seems unclear to people.

• UTXOs, as restored by the CHIP, contain enough to allow a full node to sync. Allows a full node to build on top of the restored UTXO.

• Wallets don’t use UTXOs, walles use transactions.
  A UTXO set is not useful to them. No wallet exists that will take a UTXO as a historical ‘state’.
  More to the point, there is no way to prove to that thin wallet that the historical transaction is actually valid.

So for wallets such a full node, restored from fastsync, is only useful for full transactions received after the sync point. It can not have any, really any history on its owned addresses before the sync point.

This is the current state of the tech, as is the case in software, this can be changed because software can be changed.

But before that is the case, I will object to any consensus changes because I consider this feature to not be finished yet.

[Jonas]

I do agree with what you are saying above. UTXO fast-sync (with or without UTXO commitments) are indeed only useful for full nodes to be able to fully validate the blockchain from the point of synchronization. Any wallet can thus only fetch history from that point and forward.

I think it is important to talk about what the benefits of such functionality might be.
One use-case from the top of my head:
Let’s say that there is a CashToken launched called DummyCoin with genesis at block X. DummyCoin gains a lot of popularity with an entire eco-system around it with independently developed DummyCoin mobile wallets, DummyCoin merchant checkout services and so on. Each user/service/organization that wishes to launch a fully validating node exclusively for DummyCoin would be uninterested in whatever happened before block X and wouldn’t need to spend the time and storage of processing decades of redundant data.
For those the ability to quickly launch a node from, or slightly before, block X gains real value since there will be more fully validating nodes that can serve all DummyCoin SPV wallets with history.

This is not mutually exclusive for nodes with history going back from genesis.

[Jonas]

I know this has been a somewhat controversial subject in the past and many people don’t agree with me, but…
I think synchronizing wallet history from genesis will eventually be a premium service. Without UTXO commitments I’m afraid that getting recent history will also come at a (monetary) cost.
There simply isn’t incentives for keeping public nodes open for everyone when the cost rises.

[bitcoincashautist]

I described one of the benefits during a brainstorm session on Telegram: trustlessly bootstarting historyless SPV-serving nodes:

1. download block headers, verify them
2. get SPV proof for latest coinbase TX that has utxo commitment in it, verify that
3. get UTXO snapshot, verify that against the commitment
4. ask SPV serving nodes for proof for each UTXO in the set
5. sync up normally from there

With this you not only get a 100% verified UTXO snapshot, you also gather SPV proofs for each of them. With this you can be sure you have all the UTXOs at height N and all the proofs for them.
This pruned node can serve UTXO snapshot to other nodes, too.

Imagine some hypothetical future where blocks are 32 MB, history is 10 TB, and UTXO state is 30 GB. At 10k blocks interval, fast-sync would require a download of 30 GB + 32 MB * 10000 == 350 GB. Not so much compared to a full download of 10 TB. If you had 4MB/s fast-sync would take roughly a day, and full IBD would take roughly a month.

Then, if you really need it, you can fill in the spent history at your convenience.

We should separate the fast-sync and commitment CHIPs, or should I say - we should make a standalone commitments CHIP to hash things out since only the fast-sync CHIP now exists.
The commitments are the minimum consensus change needed to enable fast-sync to be trustless (they’re possible now but you need a trusted commitment, which Verde already implemented, and there’s been some work on BCHN too).
Fast-sync is the tech stack to make use of the commitments and capture the benefits of having consensus-validated commitments: trustless bootstarting from a snapshot.

@joshmg put it well in recent hangouts on X: “So that’s the difference between fast-syncing and UTXO commitments, UTXO commitments are actually making it a part of the rules that make a block valid, and fast-syncing is the benefit you get from having a UTXO commitment.”