crypto: Fix MuHash3072 division by itself #36286

pull fjahr wants to merge 1 commits into bitcoin:master from fjahr:2026-09-mush-div-fix changing 3 files +11 −1

fjahr commented at 11:59 AM on September 17, 2026: contributor

MuHash3072::operator/= multiplies the numerator by the divisor's denominator and then the denominator by the divisor's numerator. But as it is currently implemented the divisor could be the MuHash object itself. When that is the case, the second step reads the numerator that the first step already updated, so x /= x actually leaves 1/D instead of the empty set. This only goes unnoticed when the denominator is 1, which is the case in our existing fuzz target and benchmark. No code in the node/index divides MuHash objects by themselves, so runnings nodes are not affected.

Fixes the code by not using the potentially changed nominator, adds a test that reproduces the issue and updates the fuzz test to not always use denominator 1.
DrahtBot added the label Utils/log/libs on Sep 17, 2026
DrahtBot commented at 11:59 AM on September 17, 2026: contributor



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



Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/36286.



Reviews

See the guideline and AI policy for information on the review process.

Type Reviewers

ACK furszy, sedited, sipa

If your review is incorrectly listed, please copy-paste <code></code> into the comment that the bot should ignore.
sedited requested review from sipa on Sep 17, 2026
in src/test/fuzz/muhash.cpp:202 in d345603242 outdated
```
 198 | @@ -199,6 +199,7 @@ FUZZ_TARGET(muhash)
 199 |          },
 200 |          [&] {
 201 |              // Test that dividing a MuHash by itself brings it back to its initial state
 202 | +            muhash.Remove(data);
```
furszy commented at 2:21 PM on September 17, 2026:

A comment here would be good. Could say "make denominator not one".

Also, we could keep the previous coverage too by doing:

if (fuzzed_data_provider.ConsumeBool()) muhash.Remove(data);
fjahr commented at 6:33 PM on September 17, 2026:

I've added the comment. The bool case for the previous coverage doesn't seem that appealing to me because it runs the trivial version in 50% of the time but it's the same code path, so I left this part as is.
in src/crypto/muhash.cpp:576 in d345603242 outdated
```
 568 | @@ -569,8 +569,9 @@ MuHash3072& MuHash3072::operator*=(const MuHash3072& mul) noexcept
 569 |  
 570 |  MuHash3072& MuHash3072::operator/=(const MuHash3072& div) noexcept
 571 |  {
 572 | +    const Num3072 div_numerator{div.m_numerator}; // div may alias *this
 573 |      m_numerator.Multiply(div.m_denominator);
 574 | -    m_denominator.Multiply(div.m_numerator);
 575 | +    m_denominator.Multiply(div_numerator);
 576 |      return *this;
 577 |  }
```
furszy commented at 2:32 PM on September 17, 2026:

Not a blocker but the downside of this is that we are copying the numerator on every division. An alternative could be a quick equals check early on? (if being quicker there is possible)

if (*this == div) { m_numerator.SetToOne(); m_denominator.SetToOne(); return *this; }

Or.. think about disallowing division for itself with an Assume early on.
fjahr commented at 6:33 PM on September 17, 2026:

I ran the MuHashDiv benchmark on both versions and couldn't see a measurable difference in performance, so I left this as is.

I thought about disallowing the division by itself as well but since allowing it to happen correctly doesn't make the code more complex, I opted for that. But if people prefer to disallow I am open to adopt that approach anyway.
furszy commented at 2:35 PM on September 17, 2026: member

ACK d34560324296cd17619b561d1b044cf505a7a092
crypto: Fix MuHash3072 division by itself b388f9bd0d
fjahr force-pushed on Sep 17, 2026
fjahr commented at 6:34 PM on September 17, 2026: contributor

Added the comment improvement suggested by @furszy , thanks for the review!
furszy commented at 8:48 PM on September 17, 2026: member

utACK b388f9bd0d2bcc259d488638d479ba09a30ba040
sedited approved
sedited commented at 8:50 PM on September 17, 2026: contributor

ACK b388f9bd0d2bcc259d488638d479ba09a30ba040
sipa commented at 1:25 PM on September 18, 2026: member

utACK b388f9bd0d2bcc259d488638d479ba09a30ba040
sedited merged this on Sep 18, 2026
sedited closed this on Sep 18, 2026

Type	Reviewers
ACK	furszy, sedited, sipa

Contributors

Labels

crypto: Fix MuHash3072 division by itself #36286

Code Coverage & Benchmarks

Reviews