Add MuHash3072 implementation #19055

Reviewers: This PR is being discussed in the review club at https://bitcoincore.reviews/19055

(A Review club tag for this PR would be helpful to indicate that review notes and discussion are available there.)

Some history for the context:

• https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html
• based on #10434

Concept ACK - this is so cool!

Regarding approaches (i.e. which hash function) I looked at your comparison in this doc, and have a question about the “rolling-ness” consideration and why it’s important. It also seems that ECMH (which is noted as non-rolling) performed better and has a maintainability plus since it’s part of Secp256k1.

From what I’ve gathered:

• incremental hashing is efficient with arbitrary additions/deletions from a large set, at any point in the data
• rolling hash functions have this same efficiency idea but are particularly optimized for adding/popping at the ends (i.e. like a “rolling” window) (Please correct me if I’m mistaken here, since you’ve definitely spent more time with this. I also understand that they aren’t mutually exclusive).

Since the UTXO set is not spent in any particular order and you can’t sort it ahead of time, I definitely see (theoretically as well as from the tangible performance wins) why an incremental hash is better, but I fail to understand why rolling is particularly important?

@gzhao408 I think there is a bit of a miscommunication. The term “rolling” here just means efficient addition as well as deletion from the set being hashed. There is no actual window, as sets are unordered. Perhaps the term was chosen badly (which would be my fault).

All of LtHash, MuHash, and ECMH support incremental addition and deletion. The “non-rolling” mention in @fjahr’s document refers to the fact that he hasn’t implemented continuous UTXO set hashing with these functions, only a from scratch computation. It has nothing to do with what these functions can or can’t do.

The primary difference between MuHash and ECMH is caching:

• ECMH is more CPU time overall, but the time is mostly in computing the “effect” of a set of additions/deletions; applying that effect to the overall hash is extremely cheap. Furthermore, a 64-byte precomputed “patch” per set of additions/deletions can be created, which means a patch could be cached per-transaction, and then very cheaply applied when the transaction confirms. So it allows doing most of the work ahead of time (before the block arrives).

• MuHash is cheaper overall, but the time is mostly in applying the changes to the overall hash. This means caching isn’t very useful (and also the caches would be 768 bytes, which is pretty large). If the intent is computing things in the background, or at block connection time, then this is a better (and simpler) approach.

AaaAHhhh, thank you @sipa for the clarification!

The term “rolling” here just means efficient addition as well as deletion from the set being hashed. The “non-rolling” mention in @fjahr’s document refers to the fact that he hasn’t implemented continuous UTXO set hashing with these functions

This makes a lot more sense; I had thought he meant the hash function itself is rolling/non-rolling. I didn’t have much info but was super interested and went for a textbook definition 😅 now I feel embarrassed. This information is super helpful, thanks!

It also seems that ECMH (which is noted as non-rolling) performed better and has a maintainability plus since it’s part of Secp256k1.

Please also note that there is an implementation of ECMH that is an open pull request to Secp256k1 but it is not merged and has been stale for some time. So the work to get it merged is more or less the same and I don’t think there is a big difference in maintainability between having it in core or secp.

@fjahr I’ve written a Python implementation of MuHash3072, so it can be more easily tested: sipa/bitcoin@202005_muhash_python (commits) (no tests are included, but I’ve verified it matches the C++ code in a few simple examples).

Awesome, I have just pulled it in here and will build further tests on top of it.

Concept ACK / partial ACK 4438aed. Code review. Did not yet compare the C++ MuHash implementation to the Python one or look for other implementations to verify with. Built, ran tests, ran benchmarks. Verified that minor mutations to muhash.cpp duly broke the new unit test. Tested the new RPC gettxoutsetinfo help and boolean. Some comments:

• This PR essentially makes gettxoutsetinfo too slow to be useable in testnet and mainnet (it times out and raises after 15 minutes); for that reason, until the -coinstatsindex in #18000 is merged, the MuHash algorithm should be opt-in for rpc gettxoutsetinfo and not the default

• What are your plans regarding ECMH?

• it looks like TruncatedSHA512Writer could use unit tests (perhaps just sanity checks if not viable to use test vectors, CHashWriter is also not tested directly but used by other unit tests: addrman, hash, sighash)

• a fuzz harness would be ideal

• do you plan to add tests using the just-added Python MuHash3072 implementation?

• 06ae4ab0 commit message s/256/512/?

• 04d088da commit message could mention the renaming of hash_serialized_2 to utxo_set_hash and why it was changed (I didn’t see any explanation anywhere)

• 04d088da and a6cf0df ought to be squashed to one commit; keeping them separate unnecessarily complicates reviewing – I squashed them locally in order to see the relevant diff, as ApplyStats() is weird enough to review already

• at some point you’ll want to add a release note

• some nits below; feel free to ignore

 0$ src/bench/bench_bitcoin -filter=MuHash*.*
 1# Benchmark, evals, iterations, total, min, max, median
 2MuHash, 5, 5000, 0.287426, 7.45603e-06, 1.72302e-05, 1.08339e-05
 3MuHashAdd, 5, 5000, 0.243778, 7.93741e-06, 1.17234e-05, 9.61388e-06
 4MuHashDiv, 5, 100, 8.62069, 0.0146344, 0.0216452, 0.0169485
 5MuHashPrecompute, 5, 5000, 0.0557224, 1.55965e-06, 4.40565e-06, 1.65373e-06
 6
 7$ src/bench/bench_bitcoin -filter=MuHash*.* -evals=10
 8# Benchmark, evals, iterations, total, min, max, median
 9MuHash, 10, 5000, 0.286697, 5.3029e-06, 6.24744e-06, 5.78305e-06
10MuHashAdd, 10, 5000, 0.227103, 4.1665e-06, 5.39662e-06, 4.52542e-06
11MuHashDiv, 10, 100, 12.7459, 0.0106584, 0.0182222, 0.0120859
12MuHashPrecompute, 10, 5000, 0.096089, 1.67035e-06, 2.37696e-06, 1.89207e-06
13
14$ src/bench/bench_bitcoin -filter=MuHash*.* -evals=50
15# Benchmark, evals, iterations, total, min, max, median
16MuHash, 50, 5000, 1.92384, 6.04054e-06, 1.34205e-05, 7.3487e-06
17MuHashAdd, 50, 5000, 1.26626, 3.9807e-06, 5.9453e-06, 5.61147e-06
18MuHashDiv, 50, 100, 59.2743, 0.00950589, 0.0151357, 0.011696
19MuHashPrecompute, 50, 5000, 0.386586, 1.4394e-06, 1.66618e-06, 1.55641e-06

Note to reviewers: you’ll need to build #18000 to build the index and test performance, as it contains the -coinstatsindex that this PR does not yet implement.

Also verified that, like your added test in rpc_blockchain.py, only utxo_set_hash varies between gettxoutsetinfo in -regtest with each algo.

 0$ bitcoin-cli -regtest gettxoutsetinfo
 1{
 2  "height": 15599,
 3  "bestblock": "6e535bc570f9be1b86d21711b23391e4e8f001682b5c6243883744879cdc4f84",
 4  "transactions": 3216,
 5  "txouts": 3219,
 6  "bogosize": 234987,
 7  "utxo_set_hash": "c4926481130f6689950e07e0e1f2060277d349b106a94b83145d577d3db4d225",
 8  "disk_size": 226234,
 9  "total_amount": 14949.99998350
10}
11$ bitcoin-cli -regtest gettxoutsetinfo true
12{
13  "height": 15599,
14  "bestblock": "6e535bc570f9be1b86d21711b23391e4e8f001682b5c6243883744879cdc4f84",
15  "transactions": 3216,
16  "txouts": 3219,
17  "bogosize": 234987,
18  "utxo_set_hash": "1883e99e56927fd5e3b82ccb9e08acd1be7ed0256d4cafe142626ae2fb66ffb4",
19  "disk_size": 226234,
20  "total_amount": 14949.99998350
21}

nit: “separate” is misspelled in the commit title of cda20f3f897ff88337756cb0c0345b41cec9014e

It might be nice to split this in two PRs: One which adds MuHash, and one which updates gettxoutsetinfo to support it. I would definitely at least rebase/squash to put all the MuHash additions first and then layer the functionality changes on top.

Edited to add thought: The next PR could add rolling as well, so this way we don’t have an interim state where gettxoutsetinfo is even slower than it is now.

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #20828 (fuzz: Introduce CallOneOf helper to replace switch-case by MarcoFalke)
• #19145 (Add hash_type MUHASH for gettxoutsetinfo by fjahr)

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.

It looks like you removed a bunch of code, and the functional tests, in the last push? If yes, review effort is being thrown away, and perhaps the PR description needs to be updated.

Yes, I am writing an update at the moment

nit: “separate” is misspelled in the commit title of cda20f3

done

• This PR essentially makes gettxoutsetinfo too slow to be useable in testnet and mainnet (it times out and raises after 15 minutes); for that reason, until the -coinstatsindex in #18000 is merged, the MuHash algorithm should be opt-in for rpc gettxoutsetinfo and not the default

Will do so in the follow-up that adds the option to the RPC.

• What are your plans regarding ECMH?

I don’t have plans for it unless there is a reason to reconsider it as the algorithm of choice over Muhash. The branch with the ECMH implementation in secp256k1 is still there if people want to play with it.

• it looks like TruncatedSHA512Writer could use unit tests (perhaps just sanity checks if not viable to use test vectors, CHashWriter is also not tested directly but used by other unit tests: addrman, hash, sighash)

I have laid out some thoughts on it [here]( #18000 (comment)) why it is hard to add meaningful unit tests. I am still thinking about a better solution and might add an implementation of SHA512/256. There is a single sanity check at the bottom of the Muhash test at least.

• a fuzz harness would be ideal

Yeah, as I mention in my answer to Sjors, I would like to add it as a follow-up.

• do you plan to add tests using the just-added Python MuHash3072 implementation?

Yes

• 06ae4ab commit message s/256/512/?

done

• 04d088d commit message could mention the renaming of hash_serialized_2 to utxo_set_hash and why it was changed (I didn’t see any explanation anywhere)

I was going back and forth on this, which is probably why it is not mentioned. Initially it was named muhash, then I thought it should be more general name that makes more sense to the user. But now my tendency is back to naming it muhash, since we want to keep hash_serialized_2 for longer and there is no guarantee that there will not be another algo used some time in the future which would mean we would probably need to rename it again in order to avoid confusion.

• 04d088d and a6cf0df ought to be squashed to one commit; keeping them separate unnecessarily complicates reviewing – I squashed them locally in order to see the relevant diff, as ApplyStats() is weird enough to review already

Yes, done in follow-up pr

• at some point you’ll want to add a release note

yepp

I think it’d be easier to review this code if the PR didn’t include the ASM implementation.

Yeah, I can split that out easily as well.

@gmaxwell I assume it’s SHA512 because of my original code used that. I’ve pointed out to @fjahr that we should benchmark if SHA256 isn’t faster these days (on x86_64, I expect it to be). I hadn’t thought of the possibility of parallellizing; that should shift things even further in favor of SHA256.

FWIW, the original reason was that for typical UTXOs, only one SHA512 compression is enough (it’d be over 55 bytes but below 119), and at the time this was first written, a SHA256 compression on x86_64 was less than twice as fast as a SHA512 one.

I finally got around to run these benchmarks and it appears that Truncated512 is still significantly faster on my hardware (Intel(R) Core(TM) i5-6287U CPU @ 3.10GHz). But I have seen some strange benchmarks before on this machine, so it would be great if others could run them as well. I pushed the code in a new commit, I can remove it again if it is not valuable enough to keep.

SHA256 results (100 bytes):

0$ src/bench/bench_bitcoin -filter=SHA256_100b -evals=50
1# Benchmark, evals, iterations, total, min, max, median
2SHA256_100b, 50, 1000000, 38.3667, 6.93112e-07, 9.39267e-07, 7.40312e-07
3SHA256_100b, 50, 1000000, 38.4717, 6.93757e-07, 1.08095e-06, 7.47834e-07
4SHA256_100b, 50, 1000000, 40.7169, 7.07437e-07, 1.11799e-06, 8.01852e-07

TruncatedSHA512Writer results (100 bytes):

0$ src/bench/bench_bitcoin -filter=TruncatedSHA512_100b -evals=50
1# Benchmark, evals, iterations, total, min, max, median
2TruncatedSHA512_100b, 50, 1000000, 21.6684, 4.17094e-07, 4.98784e-07, 4.30721e-07
3TruncatedSHA512_100b, 50, 1000000, 22.3288, 4.17564e-07, 5.26341e-07, 4.46433e-07
4TruncatedSHA512_100b, 50, 1000000, 21.9103, 4.17407e-07, 5.02515e-07, 4.33787e-07

@fjahr It seems the benchmarking framework isn’t calling the SHA256AutoDetect() function, which would enable hardware-accelerated versions of SHA256. See #19214 for a fix.

With that fixed, I get (on my SHA-NI enabled machine):

0$ ./src/bench/bench_bitcoin -filter='.*100b' -evals=50
1# Benchmark, evals, iterations, total, min, max, median
2SHA256_100b, 50, 1000000, 4.73236, 9.27549e-08, 1.35582e-07, 9.35812e-08
3TruncatedSHA512_100b, 50, 1000000, 18.3907, 3.63877e-07, 3.88716e-07, 3.67614e-07

And on a machine without SHA-NI (but with AVX2):

0$ ./src/bench/bench_bitcoin -filter='.*100b.*' -evals=50
1# Benchmark, evals, iterations, total, min, max, median
2SHA256_100b, 50, 1000000, 30.8421, 6.10718e-07, 6.40862e-07, 6.14576e-07
3TruncatedSHA512_100b, 50, 1000000, 28.2434, 5.57851e-07, 5.87092e-07, 5.62717e-07

So it seems @gmaxwell’s intuition above was right, that non-parallel SHA256 is only preferable on SHA-NI enabled machines. If we’d consider parallellizing updates (e.g. cache up 8 added/deleted UTXOs in the MuHash object itself, and then processing them all at once), SHA256 is probably a win over SHA512 on most modern x86_64 systems.

Concept ACK. I’m still worried about a lack of test vectors.

It would be useful to rebase #18000 whenever individual PRs are close to merge-ready. It allows reviewers to sanity check that the end result still produces a blazing fast gettxoutsetinfo and that the index builds in reasonable time.

I’m copying the discussion about TruncatedSHA256Writer unit tests here (if only to get it in the merge commit):

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.

And your comment above:

I am still thinking about a better solution and might add an implementation of SHA512/256. There is a single sanity check at the bottom of the Muhash test at least.

The performance discussion above suggests dropping 0104b7f33230f8bde09c5a2fb1d8ef4243f2ab1d entirely, which would render the above discussion moot. I’ll wait with reviewing until that’s settled.

From the PR Review club minutes: https://bitcoincore.reviews/19055.html#l-195

sipa to fjahr: if you’re going to cache the hash for every block… that’s actually an argument in favor of ECMH, as the minimal “state” to keep for ECMH is 33 bytes only, while for MuHash it’s 384 bytes

And above:

The primary difference between MuHash and ECMH is caching:

• ECMH is more CPU time overall, but the time is mostly in computing the “effect” of a set of additions/deletions; applying that effect to the overall hash is extremely cheap. Furthermore, a 64-byte precomputed “patch” per set of additions/deletions can be created, which means a patch could be cached per-transaction, and then very cheaply applied when the transaction confirms. So it allows doing most of the work ahead of time (before the block arrives).
• MuHash is cheaper overall, but the time is mostly in applying the changes to the overall hash. This means caching isn’t very useful (and also the caches would be 768 bytes, which is pretty large). If the intent is computing things in the background, or at block connection time, then this is a better (and simpler) approach.

We should probably clarify what’s meant with “caching”.

With -coinstatsindex we store the UTXO set hash for every height. This makes the RPC blazing fast. With MuHash it uses ~500 MB for the current chain vs 39 MB with ECMH. The latter is so small I can see us turning that on by default one day (assuming ECMH calculation adds negligible overhead to IBD). But 500 MB isn’t unacceptable for an advanced user who needs gettxoutsetinfo (disclaimer: yours truly needs the index, but has no use for any hash).

When you don’t have the index enabled, MuHash is faster than ECMH, but both are unacceptably slow for anyone using the feature more than once. So in practice I expect anyone who needs this feature to turn on the index.

Assuming this feature is mostly used with an index, then ECMH seems the better option in terms of storage.

Conceptionally I find MuHash very simple and we have all the ingredients here. We might as well use it for the initial -coinstatsindex, and add ECMH later, as well as any briljant other ideas.

With -coinstatsindex we store the UTXO set hash for every height. This makes the RPC blazing fast. With MuHash it uses ~500 MB for the current chain vs 39 MB with ECMH. The latter is so small I can see us turning that on by default one day (assuming ECMH calculation adds negligible overhead to IBD). But 500 MB isn’t unacceptable for an advanced user who needs gettxoutsetinfo (disclaimer: yours truly needs the index, but has no use for any hash).

When you don’t have the index enabled, MuHash is faster than ECMH, but both are unacceptably slow for anyone using the feature more than once. So in practice I expect anyone who needs this feature to turn on the index.

Assuming this feature is mostly used with an index, then ECMH seems the better option in terms of storage.

There is no real difference in storage because I am not saving the MuHash3072 object for every block but the finalized hash. I didn’t even think about storage when I made that decision tbh. Intuitively this made more sense to me because if we access historical blocks to get their stats all we would do with the MuHash is finalize it anyway. So we save a little bit of CPU every time we do it. There is currently only one MuHash3072 object maintained at the tip and if there is a reorg I am rolling back the reorged blocks. This takes longer than accessing a stored MuHash3072 object of course but that trade-off seemed worth it to me even without storage because we don’t see too many reorgs these days and it’s really not that long to roll back a block and add another.

On my current mainnet node the whole indexes/coinstats folder is 83 MB large. That includes all the stats, not just the hash. Was the 500 MB number a theoretical calculation or did you see this in practice? If your folder is that large I would need to investigate.

My calculation was based on 768 bytes of cache, but that’s off by a factor 2. A finalised MuHash3072 uses 3072 bits. So for 640,000 blocks that’s 234 MB.

I suppose you could store just the sha256 hash for historical blocks, only keep 3072 bits for the most recent block, and use that to move forward or roll back. In that case storage is the same as with ECMH. I can’t think of a use case for the full 3072 bits. Initially I was thinking of it as a set, so you potentially query it for the presence of a UTXO, but that’s not actually how it works. So perhaps there really is no point in keeping the full 3072 bits for historical blocks.

ACK 5675d28

Most of the code in muhash.cpp is for basic 3072 bit modular arithmetic (Num3072). It’s nice that Python handles that out of the box in #19105, which gives some confidence the c++ code is correct. I assume @sipa didn’t find a generic BigInt library that can do the job? Well, we can always split it into a library ourselves one day…

a bigint library for the C++ side

That’s what I meant. I agree adding all of GMP is overkill.

Sorry, some theory crypto stuff ahead…

I find the claim that the EC alternative does not introduce a new cryptographic assumption implausible: You can’t break a discrete log by finding a number of random points that you do not know the discrete log of that add to a selected point.

Oh, in the (programmable) random oracle model, you can! It’s in fact straight forward and it’s buried in the proof of Lemma 3.1 in the MuHash paper. I missed that this Lemma relies on programming the random oracle when I wrote #19055 (review). It’s not immediately obvious because they split the proof in Lemma 3.1 (reducing collisions to balance problem) and Lemma B.2 (reducing balance problem to DL). Say you’re given an algorithm C that finds collisions in MuHash, and it needs to access the prehashing function H as a random oracle. Then when C asks you for H(q_i) for some query q_i, you can draw a random r_i, set a_i = r_i*G, and reply with H(q_i) = a_i. Then you know the DL of all the a_i, and you can continue from that.

However this requires modeling the prehashing function as a programmable random oracle. In our case, this function is ChaCha20-3072-bits(key=SHA256(.)). This means that we should really have a closer look at this function. I still believe that this is as good as a random oracle if we assume SHA256 is a random oracle and ChaCha20 is an ideal cipher, and this may very well be clear to someone who has worked on random oracle indifferentiability and the ideal cipher model but I haven’t, so I’d need to do some reading or ask people who are more familiar with this stuff.

However this requires modeling the prehashing function as a programmable random oracle. In our case, this function is ChaCha20-3072-bits(key=SHA256(.)). This means that we should really have a closer look at this function. I still believe that this is as good as a random oracle if we assume SHA256 is a random oracle and ChaCha20 is an ideal cipher, and this may very well be clear to someone who has worked on random oracle indifferentiability and the ideal cipher model but I haven’t, so I’d need to do some reading or ask people who are more familiar with this stuff.

Okay, this is indeed pretty direct from the ideal cipher model, which is not less a stretch than the random oracle model in the end. In the ideal cipher model, the cipher is modeled as a function E(k,x), which is a perfectly random permutation for every key k, and by giving the attacker oracle access to this function (and it’s inverse). So it’s very similar to the random oracle model for some hash function H and you can play the same programming tricks. That is, if you get a query H(q_i), you can use a random H(q_i) and program E(H(q_i), 0)|| … ||E(H(x), 5) = r_i * G. (Note here that 3072/512 = 6, where 512 is the bitsize of the ChaCha permutation.) And if you get a query E(k, x) / E^-1(k, x) for some key k* you’ve never seen before, just give a random answer, the attacker will find a preimage of H that maps to k* only with negligible probability.

tl;dr (or if I lost you): If you believe in provable security of cryptographic constructions, and we compare to the common assumptions we already need for working consensus, then

• ECMH (= MuHash on secp256k1) needs the additional assumption that ChaCha20 is a good PRG.
• MuHash3072 needs the additional assumption that ChaCha20 is a good PRG and that either i) the finite field discrete logarithm is hard in 3072-bit fields or ii) Wagner’s algorithm is the best method to find collisions here.

As I all these assumptions are fine. However, there’s indeed a difference, so

If this functionality will ever be used in relation with chain validation, one should keep this in mind.

That’s what I meant. I agree adding all of GMP is overkill.

Also mind that GMP is not license-compatible with bitcoin (it’s LGPL). So, that’s another stumbling block besides our desire to limit third-party dependencies.

As I all these assumptions are fine. However, there’s indeed a difference, so

I have a hard time reading how serious your concerns are. So to be clear: in your opinion, this is not a blocker for merging this?

I have a hard time reading how serious your concerns are. So to be clear: in your opinion, this is not a blocker for merging this?

Sorry if my posts are confusing. I don’t have serious concerns at all and no, I don’t believe this is a blocker.

Let me try to explain. After I looked at the details, I believe that both MuHash3072 and ECMH (= MuHash on secp256k1) are very solid choices and we do not need to worry about either. What I was pointing out is that ECMH is a slightly more conservative choice if you look at the cryptographic assumptions because ECMH is better aligned with the assumptions that we already make in Bitcoin. But this is just a very small point in all the tradeoffs discussed between MuHash3072 and ECMH, and it’s perfectly reasonable that we prefer performance over being super conservative here, in particular because MuHash is intended for gettxoutsetinfo, which serves merely as a sanity check. I believe if MuHash was planned to be used in the consensus implementation, then we might come to the conclusion that we prefer being a little more conservative over getting a little bit more performance out of it. But as far as I understand, there are currently no plans to use MuHash in consensus, so this is not relevant currently.

Could rebase on top of #19286 and add fuzzing of the MuHash3072 class to the src/test/fuzz/crypto.cpp fuzzing harness in order to demonstrate (some level of) code robustness (more specifically: absence of warnings from ASan, MSan and UBSan when processing malformed/unexpected inputs)? :)

Done. I am still learning more about fuzzing so looking forward to your feedback. :)

Thanks a lot for adding a fuzzer! Great!

Fuzzing harness specific review follows :)

Code review ACK bb3098bbaf1305aa9091ee5e3cd92f2973e04c68 I have reviewed everything but the MuHash implementation in detail, and looked broadly at the MuHash code but could not follow all the specifics.

Let’s try to get #18071 in first (for the first commit)

Mind that there doesn’t seem to be agreement on that PR yet.

Let’s try to get #18071 in first (for the first commit)

It’s closed now in favor of #19601.

Didn’t fully dig into Multiply() and Square(), but they seem reasonable. The referenced paper for Inverse() seems to be behind a paywall, and there’s more exponentiation than I can follow unguided, so no review of that, but the fact the test cases pass seems promising at least.

I think there’s a bug in both IsOverflow and serialization (see above); everything else is nits. Would be nice to have more test vectors checking that the c++ and python code end up with the same results. ACK otherwise.

Thanks a lot for the review @ajtowns . I hope I have addressed all of your feedback.

Would be nice to have more test vectors checking that the c++ and python code end up with the same results. ACK otherwise.

There are more tests like this coming in the follow-up #19145 . Unless you disagree I would prefer to keep the scope of this PR were it is :)