This PR will not be updated anymore because the project is now split up into multiple pull requests. But I will use it to keep track of the projects PRs:

| Add Muhash and SHA256Writer (unused) | #19055 | Merged | notes | Add Muhash Python implementation (unused) | #19105 | Merged | notes | | Add hash_type NONE (Muhash code independent) | #19328 | Merged | - | | Add hash_type MUHASH | #19145 | Merged | ? | | Add ASM optimizations for MuHash | #19181 | Open | ? | | Add CoinStatsIndex | #19521 | Merged | ? | | Parallelize gettxoutsetinfo | | | | | Remove legacy UTXO set hash | | (future) | |

Since it's starting to get confusing I am trying to visualize the dependencies of the open PRs in this depency graph:

+--------------+   +-------------+   +----------+
|#19328        |   |#19105       |   |#19055    |
|hash_type NONE|   |Muhash Python|   |Muhash CPP|
+----+-----+---+   +------+------+   +-+----+---+
     ^     ^              ^            ^    ^
     |     |              |            |    |
     |     |    +---------+------+     |    |
     |     +----+#19145          +-----+    |
     |          |hash_type MUHASH|          |
     |          +----------------+          |
     |                               +------+---+
+----+--------+                      |#19181    |
|#19521       |                      |MuHash ASM|
|No hash Index|                      +----------+
+-------------+

This implements an index of coin statistics with the goal of making the response time of the gettxoutsetinfo RPC call dramatically faster. Currently, this RPC is scanning the full UTXO set every time it is called which makes it hard to use for users that want to continually check the coin supply or compare UTXO set hashes between different nodes. It is especially challenging in periods of multiple quickly mined blocks, even relatively fast machines.

Implementation overview:

• The current serialization of the UTXO set for the purpose of hashing is changed based on sipa's concept in proposed on the mailing list in 2017 and #10434
• The hashing algorithm in for the UTXO set is changed to Muhash, which was also implemented by sipa
• CoinStatsIndex is added which keeps an index of all values that would require gettxoutsetinfo to scan the UTXO set
• CoinStatsIndex can be activated through the flag -coinstatsindex

Todos/Open questions:

• The transactions count is currently not implemented as it seems not knowable ex-post without running a full IBD to build up the index. I am looking for a solution to this. Ideas are:
  • Require txindex and the transactions count from it
  • Remove transactions count or mark it as unreliable in a different way if coinstatsindex is enabled
• The transactions count question is also interesting because it seems to be the only obstacle to providing access to historical coin statistics, which may be a nice follow-up feature if transaction counts can be ignored somehow
• More benchmarking to evaluate potential switch from Muhash to ECMH as the hashing algorithm
• IBD benchmarking with the index enabled
• Tests could be improved

This is an extension to my rolling UTXO set hash proposal from last year.

Edit: 3c5c1ca should probably be squashed into the prior commits but I wanted to leave sipa's commits unchanged for the start.

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #18795 (Test: wallet issue with orphaned rewards by domob1812)
• #18354 (Protect wallet by using shared pointers by bvbfan)
• #17786 (refactor: Nuke policy/fees->mempool circular dependencies by hebasto)
• #13462 (Make SER_GETHASH implicit for CHashWriter and SerializeHash by Empact)
• #10443 (Add fee_est tool for debugging fee estimation code by ryanofsky)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

I'm reviewing and testing it right now but from some benchmarks I did, I saw how the time goes down by 50%. However the performance increases by 19% percent.

Regtest results only right now

On master (ef8e2cee9f5d157eeb3139b64e9c3a5fa4bf36f3):

$ time src/bitcoin-cli --regtest gettxoutsetinfo
...
> src/bitcoin-cli --regtest gettxoutsetinfo  0,00s user 0,00s system 23% cpu 0,014 total

With this PR

$ time src/bitcoin-cli --regtest gettxoutsetinfo
...
> src/bitcoin-cli --regtest gettxoutsetinfo  0,00s user 0,00s system 42% cpu 0,007 total

Can you say more about current use cases of the gettxoutsetinfo function and maybe future use cases if it's significantly faster with this change?

I think it's perfectly fine to drop the "transactions" statistics. It doesn't really mean anything; it just happened to be easy to compute pre-pertxout, but even now it's mostly a hack.

@emilengler Thanks for giving it a try! But I think the benchmarks you are comparing are not well suited in this case. I assume you are running a standard regtest network, maybe generated a few hundred blocks and made some transactions by hand. In this case the UTXO set is very small and iterating over it will be extremely fast, so that it would not surprise me if there is no measurable upside to using the index (maybe it will be even a little slower as you saw). But the goal of this index is that the time of the call will stay constant for a realistically sized UTXO set. So a better indicator would be to try it on a synced mainnet or testnet node, where gettxoutset currently takes several minutes without the index, even on pretty high powered hardware. @ryanofsky Sure, I will go along the different statistics the call provides to highlight which ones I think are more or less important:

• total_amount The total amount of the current bitcoin supply. Tracking this number on a continual basis allows users to detect potential inflation bugs, such as CVE-2018-17144 (Example: Bitmex Research). I think all users should be given the chance to continually check this, even on more affordable hardware. I am currently running a mainnet node on an Odroid HC2 and gettxoutsetinfo takes 7min 50s. Specs are roughly comparable to a Raspberry Pi 4, so it can keep up well with the chain otherwise. If I wanted to run a continual inflation detection on this hardware, I would not be able to do so when the UTXO set has grown another 20-25% (ignoring hashrate fluctuations).
• hash_serialized_2 The serialized hash of the UTXO set can be used for a quick comparison of the UTXO set between different notes. Essentially, it can be a stand-in for the latest blockhash and compared for sanity checks. BTCPayServer has been using it for their FastSync feature, which will probably be replaced with assume_utxo, where a UTXO set hash (not necessarily this one) will play a role as well. I still need to sync up with @jamesob about the latest plans for the hash and how this proposal can be compatible with his or even help/support it.
• txouts The total number of unspent outputs is an interesting number to track from an operations standpoint. Users can see if coins are being consolidated or at which rate the UTXO set is growing. Example: satoshi.info
• bogosize and disk_size might be also interesting to track but not as actionable, disc usage is probably much more efficient to collect from the OS
• transactions it seems to be a nice-to-have metric that does not serve any real purpose afaict, as @sipa also noted
• height and bestblock can be ignored since they are available from other RPCs, but are necessary to compare numbers between different machines

For future use cases (aside from integration with assume_utxo potentially) I don't have specific ideas yet, but it opens the door to track any other statistics of the UTXO set or block content in the index. So it may collect further metrics of interest where users currently parse the block data with their own custom software.

@fjahr I'm a bit confused now, I ran the tests again on a full chain and master is MUCH faster than this Pull Request (4 MINUTES faster) On master (2755b2b1092d0286022cf3cc3028e96f6bee2b34)

$ time src/bitcoin-cli --datadir=/media/emil/Files/Bitcoin/ gettxoutsetinfo
{
  "height": 614943,
  "bestblock": "0000000000000000000fa03a2ce4c6d7fb763e55402deac32371b898e8faba5e",
  "transactions": 38747934,
  "txouts": 65245740,
  "bogosize": 4903711195,
  "hash_serialized_2": "011d3eccd148b68a3bf039f0695bb4d77a23ba208dcd4d8ac073d867fd5bbef6",
  "disk_size": 4035082036,
  "total_amount": 18186617.32125282
}
src/bitcoin-cli --datadir=/media/emil/Files/Bitcoin/ gettxoutsetinfo  0,00s user 0,01s system 0% cpu 57,428 total

On fjahr:utxo-stats-index-rebase (663dbfbd1da60e91c9576629ace82b712d31668c)

$ time src/bitcoin-cli --datadir=/media/emil/Files/Bitcoin/ gettxoutsetinfo
{
  "height": 614937,
  "bestblock": "00000000000000000005973a14ac338b681e410922c7566e435107db1b1d807b",
  "transactions": 38745882,
  "txouts": 65244661,
  "bogosize": 4903634025,
  "utxo_set_hash": "87d3e7f807d6b428bf60e983a73137ef410cb510de1b5f4e650e081d044fc772",
  "disk_size": 4082447626,
  "total_amount": 18186542.32125282
}
src/bitcoin-cli --datadir=/media/emil/Files/Bitcoin/ gettxoutsetinfo  0,01s user 0,00s system 0% cpu 5:01,42 total

@ryanofsky Sure, I will go along the different statistics the call provides to highlight which ones I think are more or less important:

Thanks, this information is really clarifying. I wonder if some of it could be incorporated in the reference documentation (without mentioning specific CVE's or software projects), or maybe if it would be useful as part of some wiki. In any case, this definitely helps motivate the PR, so concept ACK from me

@emilengler did you actually start bitcoind with -coinstatsindex? I mention it briefly in the PR description, but as @ryanofsky already pointed out as well, I need to do a much better job at documenting the intent and current state of the proposal. It seems so because otherwise you could not test it that quickly, building up the index takes a quite long time and while the index is building up gettxoutsetinfo is responding with "unable to read UTXO set". In fact, on my machine, it is currently so slow that I might have to address it. But running a plain IBD is also incredibly slow right now so it could also be a local issue. What is probably happening is that you are running bitcoind without the flag and so the stats are still calculated by iterating over the UTXO set but the hash is using the new hashing algorithm (Muhash), which is slower and results in slower performance when not using the index.

@emilengler did you actually start bitcoind with -coinstatsindex?

no, sorry oversaw that

Hmmm I get this error message now:

error code: -32603
error message:
Unable to read UTXO set

the chain state is about ~2 days old

Hmmm I get this error message now:

error code: -32603
error message:
Unable to read UTXO set

the chain state is about ~2 days old

Yeah, that means the index is syncing at the moment. You should see the progress in the logs of bitcoind. Something like Syncing coinstatsindex with block chain from height XXXXX.

• benchmark: have you run gettxoutsetinfo with-and-without this PR on few UTXO sets across the years to check than performance holds linearly with utxo set growth (or a least give an intuition of it) ?

• assume-utxo: As security model of assume-utxo lays on public audit of a hardcoded hash of a utxo set, lowering the bar to compute it will increase review process trustworthiness with a higher number of participants. So IMO this point is worthy enough to Concept ACK this proposal (though @jamesob may already have work here?)

Quickly skimmed over the new code, it's clean enough if we want later to memory-isolate indexes in their own space. Don't have opinion on either MuHash or ECMH (but no lattice).

First of all, thanks for taking early looks and comments @ariard , @ryanofsky, @emilengler , @jnewbery (offline). Your comments should be mostly addressed in the latest code changes and in further information below. With the latest fixes and performance improvements, this should be now ready for real review and testing.

Short recap of changes (this changed slightly)

• Introduces MuHash3072 and TruncatedSHA256Writer implementations (code by Pieter Wuille)
• Uses above for MuHash hashing alogrithm for the UTXO set hash in gettxoutsetinfo
• Removed tracking of the transactions count statistic
• Introduces CoinStatsIndex class, an index for all the statistics in gettxoutsetinfo
• Allows activating the index using the flag -coinstatsindex. When activated gettxoutsetinfo responds within seconds after the initial sync phase. Otherwise it works as before but will be slower to parse the UTXO set due to the change in the hashing algorithm.

Benchmarking

• For reference, on my benchmarking server and my local machine, IBD takes around 18-19 hours
• I can provide more detailed numbers if required but so far I am pretty confident that it's not a bottleneck even for users on under-powered nodes.

How long does the sync of the CoinStatsIndex take?

• On my benchmarking server syncing the Coinstatsindex after IBD took between 8.5 and 9.5h hours
• On my local machine, I also synced testnet and it took 8h 20min.

How about the growth of the UTXO set (ariard's question above)?

• For the sync time of the index should actually not make much of a difference if the UTXO set shrinks or grows, it should rather grow linearly with the size of the blockchain.
• Instead, growth of the UTXO set causes gettxoutsetinfo without the index to run longer because it iterates over it every time and so it is one of the reasons why I think the index is worth integrating into core.

TBD

• Although its a lot of LOC I think the changes are still ok to be reviewed as one PR but if people would prefer me to split it into two or three smaller PRs that is easily doable.
• The newly introduced metric coins count that is only used in Assume UTXO is not in the index and I don't think there is a practical way to integrate it (similar problem to transaction count). That means it will probably not be possible to have this index running and create a new assume utxo set on the same node at the same time. I will need to discuss this with @jamesob to make sure this dealt with correctly one Assume UTXO is finished.

Rebased

Latest changes fixed/clarified lots of comments/documentation and finally made Travis happy (when it runs again).

Rebased.

Removed the last commit which was just a small test improvement that became redundant after a recently merged change.

Nice PR. I just tested this on my laptop (slow SSD, i7-6700HQ). No issue to report.

On master, gettxoutsetinfo takes 55s to complete. On this branch less than a second. The coinstatsindex thread took around 7h30mn to complete.

Another rebase, no code changes.

Thanks for testing @pierreN !

Concept ACK.

Is there any reference document for MuHash3072? If so, it would be good to link to that in the header file. In particular, does the (single) test vector exist anywhere else?

The mailinglist post you mentioned at the top also contains useful background.

This particular part of the post might be worth copying (leaving only the MuHash part):

Interestingly, both ECMH and MuHash not only support adding set elements in any order but also deleting in any order. As a result, we can simply maintain a running sum for the UTXO set as a whole, and add/subtract when creating/spending an output in it. In the case of MuHash it is slightly more complicated, as computing an inverse is relatively expensive. This can be solved by representing the running value as a fraction, and multiplying created elements into the numerator and spent elements into the denominator. Only when the final hash is desired, a single modular inverse and multiplication is needed to combine the two.

As the update operations are also associative, H(a)+H(b)+H(c)+H(d) can in fact be computed as (H(a)+H(b)) + (H(c)+H(d)). This implies that all of this is perfectly parallellizable: each thread can process an arbitrary subset of the update operations, allowing them to be efficiently combined later.

I can't speak to the cryptographic assumptions underlying MuHash, but at the least within the scope of this PR it's not used for anything security critical. As the mailinglist discussion pointed out, this feature is a good way to gain more experience with this type of hashing in a non consensus-critical manner.

I also can't say anything intelligent about the implementation, other than that it's nice and short. Maybe @practicalswift can add a fuzz harness?

b208dfd5712bdc658217c84d276d82e92cb2cf47 Add TruncatedSHA256Writer needs a test.

I think you can safely squash f59d2223199d26ef591d9a3fc3282b19a4cb833a into the original and make yourself Co-Authored-By? You're not changing the algorithm.

I'm currently running cf6ba169ae1999a98db831900d36e0571a9d933d and building a mainnet index on macOS 10.15.4. I'll update my comment with an example result from a recent block. I ran the first 100K blocks with --enable-debug, stopped and continued without debug.

Concept ACK on dropping transaction count from gettxoutsetinfo. "The number of transactions with unspent outputs" seems a useless metric. If someone does have a use case for it, hopefully we'll learn before the release. In that case it could be added to getblock.

I got very confused by the indexer code in 8e17009dcc4de977ced030e624b18ecc6ba19e63, sorry for any dumb questions...

If it's not too big a code change, adding a height argument to gettxoutsetinfo would unleash the power of this index, and also make it easier to compare hashes between reviewers. It also makes it easier to manually compare against the hash generated without an index (with something a bit more complex than the functional test).

Thanks for the review and the great questions!

Concept ACK.

Is there any reference document for MuHash3072? If so, it would be good to link to that in the header file. In particular, does the (single) test vector exist anywhere else?

I did a bit of research when I started the work on this but I am not aware of any reference document or official test vectors. Maybe @sipa knows if I missed something?

The mailinglist post you mentioned at the top also contains useful background.

This particular part of the post might be worth copying (leaving only the MuHash part):

Interestingly, both ECMH and MuHash not only support adding set elements in any order but also deleting in any order. As a result, we can simply maintain a running sum for the UTXO set as a whole, and add/subtract when creating/spending an output in it. In the case of MuHash it is slightly more complicated, as computing an inverse is relatively expensive. This can be solved by representing the running value as a fraction, and multiplying created elements into the numerator and spent elements into the denominator. Only when the final hash is desired, a single modular inverse and multiplication is needed to combine the two.

As the update operations are also associative, H(a)+H(b)+H(c)+H(d) can in fact be computed as (H(a)+H(b)) + (H(c)+H(d)). This implies that all of this is perfectly parallellizable: each thread can process an arbitrary subset of the update operations, allowing them to be efficiently combined later.

Added an adapted version of this text to muhash.h.

I can't speak to the cryptographic assumptions underlying MuHash, but at the least within the scope of this PR it's not used for anything security critical. As the mailinglist discussion pointed out, this feature is a good way to gain more experience with this type of hashing in a non consensus-critical manner.

I also can't say anything intelligent about the implementation, other than that it's nice and short. Maybe @practicalswift can add a fuzz harness?

Happy to work on a fuzz harness myself, I am trying to get some more experience with it :)

b208dfd Add TruncatedSHA256Writer needs a test.

I am currently a bit unsure of what the right way to go is for this. A first observation is that CHashWriter is also untested. I think both these classes are pretty thin wrappers of the actual hash functions they use, so a test might not provide much value. But TruncatedSHA256Writer does a bit more, so I think it could still be valuable to have a sanity check test. I was looking for any test vectors provided for SHA-512/256 and while there are is no official set, at least these could be enough for a sanity check. However, the problem is that for SHA-512/256 different initializers are used. We reuse SHA-512 for simplicity reasons, I guess. It's easy enough to add the other initializers. I am just not sure it worth the additional review effort. Another fact that I stumbled over, is that the serializer used here is writing the null character of a string into the hash, where I am not sure if that is a bug but it certainly makes working with test vectors hard.

So, I am not sure if adding SHA-512/256 is worth it. And I am also unsure if a test for TruncatedSHA256Writer would be valuable without test vectors and given the only limited logic inside the class.

I would be happy to get input from @sipa here.

I think you can safely squash f59d222 into the original and make yourself Co-Authored-By? You're not changing the algorithm.

done

I'm currently running cf6ba16 and building a mainnet index on macOS 10.15.4. I'll update my comment with an example result from a recent block. I ran the first 100K blocks with --enable-debug, stopped and continued without debug.

Concept ACK on dropping transaction count from gettxoutsetinfo. "The number of transactions with unspent outputs" seems a useless metric. If someone does have a use case for it, hopefully we'll learn before the release. In that case it could be added to getblock.

I got very confused by the indexer code in 8e17009, sorry for any dumb questions...

I will try to add more comments to make it easier to understand.

If it's not too big a code change, adding a height argument to gettxoutsetinfo would unleash the power of this index, and also make it easier to compare hashes between reviewers. It also makes it easier to manually compare against the hash generated without an index (with something a bit more complex than the functional test).

Done, I had planned to do this as a follow-up anyway and with the removal of some duplicate code, the number of LOC has hardly grown.

<!--cf906140f33d8803c4a75a2196329ecb-->

🐙 This pull request conflicts with the target branch and needs rebase.

Tested Concept and approach ACK 58cf819caabe98

This PR builds cleanly. I launched bitcoind with -coinstatsindex=1 to create the index, which runs in a separate thread and does not block the node. It regularly logs progress in the debug log.

The first 459k blocks took 19 hours (~400 blocks/minute) with debug build with many flags for reviewing.

I rebuilt without debug enabled and no flags and restarted bitcoind. The remaining blocks 459k-632k (173k blocks) took 3.5 hours (~800 blocks/minute).

The index was enabled when the debug log prints: "coinstatsindex is enabled at height 632059" and RPC gettxoutsetinfo then runs near-instantly.

In #19145 (missing in OP) you're adding a hash_type option to gettxoutsetinfo, which can be none. This makes an index immediately useful, even without MuHash. So you make a PR for that independently.

Adding MuHash to the index later might be annoying, however if the plan is to support different hash types, it sounds like MuHash should be in a separate index from the coin stats anyway?

In #19145 (missing in OP) you're adding a hash_type option to gettxoutsetinfo, which can be none. This makes an index immediately useful, even without MuHash. So you make a PR for that independently.

Adding MuHash to the index later might be annoying, however if the plan is to support different hash types, it sounds like MuHash should be in a separate index from the coin stats anyway?

I needed to reflect a bit on this but now do I think it would be good to offer the index already without the hash. But I think to keep the hash in a different index and letting users set these with separate settings might be too much responsibility for the users. I would suggest a more opinionated approach. Rather than having -coinstatsindex=none and -coinstatsindex=muhash later I would suggest it stays -coinstatsindex and at first there would be no hash and users would only get a fast response when they use hash_type=none, then muhash can be added to the index and users will then be receiving responses from the index with hash_type=none and hash_type=muhash. Personally I think we don't want to have a lot of hash types, too much unnecessary choice for the user. I think we use this now to support hash_serialized_2 for some time and maybe also to run ECMH in parallel but ideally we should be ending up at one hash_type that is the default and most of the other options can probably be removed.

I will prepare the alternate PRs with only hash_type=none and I hope I can make so people are not totally confused by all the different PRs. :)

PR 19105 is merged

Chart can be updated as PR #19055 and #19145 have been merged

Chart can be updated as PR #19055 and #19145 have been merged

Thanks for the reminder, done!

I don't mean to spam the PR, but the chart was updated incorrectly.

PR 19055 is merged but marked as open PR 19181 is open but marked as merged

Thank you for all your work!

I don't mean to spam the PR, but the chart was updated incorrectly.

PR 19055 is merged but marked as open PR 19181 is open but marked as merged

Thank you for all your work!

Thanks, I was too hastily. Fixed.

<!--13523179cfe9479db18ec6c5d236f789-->There hasn't been much activity lately and the patch still needs rebase. What is the status here?

• Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
• Is it no longer relevant? ➡️ Please close.
• Did the author lose interest or time to work on this? ➡️ Please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future.

@fjahr should this be closed? If #19181 is all that's left, it can just be its own PR.

Closing this as almost everything that was aimed for has been implemented by now. Thanks to everyone who supported this project with advice, code reviews, or just general words of encouragement!

There are still two open PRs that are related and could use some review:

• #19792 adds an RPC to export the coinstats to a CSV file
• #19181 adds ASM optimizations (in rebase at the moment)