Bitcoin Core  29.1.0
P2P Digital Currency
muhash.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020-2021 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <arith_uint256.h>
6 #include <crypto/muhash.h>
7 #include <span.h>
8 #include <uint256.h>
9 #include <test/fuzz/FuzzedDataProvider.h>
10 #include <test/fuzz/fuzz.h>
11 #include <test/fuzz/util.h>
12 
13 #include <algorithm>
14 #include <array>
15 #include <vector>
16 
17 namespace {
18 
22 class arith_uint6144 : public base_uint<6144> {
23 public:
24  arith_uint6144(uint64_t x) : base_uint{x} {}
25 
28  arith_uint6144(Span<const uint8_t> bytes) : base_uint{}
29  {
30  assert(bytes.size() % 4 == 0);
31  assert(bytes.size() <= 768);
32  for (unsigned i = 0; i * 4 < bytes.size(); ++i) {
33  pn[i] = ReadLE32(bytes.data() + 4 * i);
34  }
35  }
36 
39  void Serialize(Span<uint8_t> bytes) {
40  assert(bytes.size() % 4 == 0);
41  assert(bytes.size() <= 768);
42  for (unsigned i = 0; i * 4 < bytes.size(); ++i) {
43  WriteLE32(bytes.data() + 4 * i, pn[i]);
44  }
45  for (unsigned i = bytes.size() / 4; i * 4 < 768; ++i) {
46  assert(pn[i] == 0);
47  }
48  };
49 };
50 
52 constexpr std::array<const uint8_t, 768> MODULUS_BYTES = {
53  155, 40, 239, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
54  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
55  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
56  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
57  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
58  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
59  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
60  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
61  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
62  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
63  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
64  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
65  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
66  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
67  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
68  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
69  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
70  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
71  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
72  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
73  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
74  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
75  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
76  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
77  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
78  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
79  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
80  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
81  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
82  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
83  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
84  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
85  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
86  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
87  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
88  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
89 };
90 
91 const arith_uint6144 ZERO{0};
92 const arith_uint6144 ONE{1};
93 const arith_uint6144 MODULUS{MODULUS_BYTES};
94 
96 void Reduce(arith_uint6144& value)
97 {
98  arith_uint6144 tmp = value;
99  tmp /= MODULUS;
100  tmp *= MODULUS;
101  value -= tmp;
102 }
103 
104 } // namespace
105 
106 FUZZ_TARGET(num3072_mul)
107 {
108  // Test multiplication
109  FuzzedDataProvider provider{buffer.data(), buffer.size()};
110 
111  // Read two 3072-bit numbers from fuzz input, and construct arith_uint6144
112  // and Num3072 objects with the read values.
113  uint16_t data_a_len = provider.ConsumeIntegralInRange(0, 384);
114  uint8_t data_a[384] = {0};
115  provider.ConsumeData(data_a, data_a_len);
116  arith_uint6144 a_uint{data_a};
117  Num3072 a_num{data_a};
118 
119  uint8_t data_b[384] = {0};
120  provider.ConsumeData(data_b, 384);
121  arith_uint6144 b_uint{data_b};
122  Num3072 b_num{data_b};
123 
124  // Multiply the first number with the second, in both representations.
125  a_num.Multiply(b_num);
126  a_uint *= b_uint;
127  Reduce(a_uint);
128 
129  // Serialize both to bytes and compare.
130  uint8_t buf_num[384], buf_uint[384];
131  a_num.ToBytes(buf_num);
132  a_uint.Serialize(buf_uint);
133  assert(std::ranges::equal(buf_num, buf_uint));
134 }
135 
136 FUZZ_TARGET(num3072_inv)
137 {
138  // Test inversion
139 
140  FuzzedDataProvider provider{buffer.data(), buffer.size()};
141 
142  // Read a 3072-bit number from fuzz input, and construct arith_uint6144
143  // and Num3072 objects with the read values.
144  uint8_t data[384] = {0};
145  provider.ConsumeData(data, 384);
146  Num3072 num{data};
147  arith_uint6144 uint{data};
148 
149  // Bail out if the number has no inverse.
150  if ((uint == ZERO) || (uint == MODULUS)) return;
151 
152  // Compute the inverse of the Num3072 object.
153  Num3072 inv;
154  inv.SetToOne();
155  inv.Divide(num);
156 
157  // Convert the computed inverse to arith_uint6144.
158  uint8_t buf[384];
159  inv.ToBytes(buf);
160  arith_uint6144 uint_inv{buf};
161 
162  // Multiply the original and the inverse, and expect 1.
163  uint *= uint_inv;
164  Reduce(uint);
165  assert(uint == ONE);
166 }
167 
168 FUZZ_TARGET(muhash)
169 {
170  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
171  std::vector<uint8_t> data{ConsumeRandomLengthByteVector(fuzzed_data_provider)};
172  std::vector<uint8_t> data2{ConsumeRandomLengthByteVector(fuzzed_data_provider)};
173 
174  MuHash3072 muhash;
175 
176  muhash.Insert(data);
177  muhash.Insert(data2);
178 
179  constexpr uint256 initial_state_hash{"dd5ad2a105c2d29495f577245c357409002329b9f4d6182c0af3dc2f462555c8"};
180  uint256 out;
181  uint256 out2;
182  CallOneOf(
183  fuzzed_data_provider,
184  [&] {
185  // Test that MuHash result is consistent independent of order of operations
186  muhash.Finalize(out);
187 
188  muhash = MuHash3072();
189  muhash.Insert(data2);
190  muhash.Insert(data);
191  muhash.Finalize(out2);
192  },
193  [&] {
194  // Test that multiplication with the initial state never changes the finalized result
195  muhash.Finalize(out);
196  MuHash3072 muhash3;
197  muhash3 *= muhash;
198  muhash3.Finalize(out2);
199  },
200  [&] {
201  // Test that dividing a MuHash by itself brings it back to it's initial state
202 
203  // See note about clang + self-assignment in test/uint256_tests.cpp
204  #if defined(__clang__)
205  # pragma clang diagnostic push
206  # pragma clang diagnostic ignored "-Wself-assign-overloaded"
207  #endif
208 
209  muhash /= muhash;
210 
211  #if defined(__clang__)
212  # pragma clang diagnostic pop
213  #endif
214 
215  muhash.Finalize(out);
216  out2 = initial_state_hash;
217  },
218  [&] {
219  // Test that removing all added elements brings the object back to it's initial state
220  muhash.Remove(data);
221  muhash.Remove(data2);
222  muhash.Finalize(out);
223  out2 = initial_state_hash;
224  });
225  assert(out == out2);
226 }
Num3072
Definition: muhash.h:13
FUZZ_TARGET
FUZZ_TARGET(num3072_mul)
Definition: muhash.cpp:106
assert
assert(!tx.IsCoinBase())
FuzzedDataProvider.h
test_vectors_musig2_generate.data
data
Definition: test_vectors_musig2_generate.py:98
mp::Serialize
value Serialize(wrapper)
Span::size
constexpr std::size_t size() const noexcept
Definition: span.h:187
base_uint
Template base class for unsigned big integers.
Definition: arith_uint256.h:24
miniscript::internal::ONE
static const auto ONE
A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric co...
Definition: miniscript.h:335
Num3072::Divide
void Divide(const Num3072 &a)
Definition: muhash.cpp:498
ConsumeRandomLengthByteVector
std::vector< B > ConsumeRandomLengthByteVector(FuzzedDataProvider &fuzzed_data_provider, const std::optional< size_t > &max_length=std::nullopt) noexcept
Definition: util.h:57
ReadLE32
uint32_t ReadLE32(const B *ptr)
Definition: common.h:27
WriteLE32
void WriteLE32(B *ptr, uint32_t x)
Definition: common.h:50
Num3072::Multiply
void Multiply(const Num3072 &a)
Definition: muhash.cpp:455
tests_wycheproof_generate.out
string out
Definition: tests_wycheproof_generate.py:28
miniscript::internal::ZERO
static const auto ZERO
A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in num...
Definition: miniscript.h:331
MuHash3072::Remove
MuHash3072 & Remove(Span< const unsigned char > in) noexcept
Definition: muhash.cpp:581
MuHash3072::Finalize
void Finalize(uint256 &out) noexcept
Definition: muhash.cpp:551
Num3072::ToBytes
void ToBytes(unsigned char(&out)[BYTE_SIZE])
Definition: muhash.cpp:525
uint256
256-bit opaque blob.
Definition: uint256.h:201
Span::data
constexpr C * data() const noexcept
Definition: span.h:174
MuHash3072
A class representing MuHash sets.
Definition: muhash.h:99
CallOneOf
size_t CallOneOf(FuzzedDataProvider &fuzzed_data_provider, Callables... callables)
Definition: util.h:35
Span
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:97
FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition: FuzzedDataProvider.h:205
MuHash3072::Insert
MuHash3072 & Insert(Span< const unsigned char > in) noexcept
Definition: muhash.cpp:576
Num3072::SetToOne
void SetToOne()
Definition: muhash.cpp:492
arith_uint256.h
Generated on Wed Sep 3 2025 12:00:00 for Bitcoin Core by   doxygen 1.8.14