Bitcoin Core 31.0.0
P2P Digital Currency
Loading...
Searching...
No Matches
muhash.cpp
Go to the documentation of this file.
1// Copyright (c) 2020-present 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
17namespace {
18
22class arith_uint6144 : public base_uint<6144> {
23public:
24 arith_uint6144(uint64_t x) : base_uint{x} {}
25
28 arith_uint6144(std::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(std::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
52constexpr 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
91const arith_uint6144 ZERO{0};
92const arith_uint6144 ONE{1};
93const arith_uint6144 MODULUS{MODULUS_BYTES};
94
96void Reduce(arith_uint6144& value)
97{
98 arith_uint6144 tmp = value;
99 tmp /= MODULUS;
100 tmp *= MODULUS;
101 value -= tmp;
102}
103
104} // namespace
105
106FUZZ_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
136FUZZ_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
168FUZZ_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 its initial state
202 muhash /= muhash;
203 muhash.Finalize(out);
204 out2 = initial_state_hash;
205 },
206 [&] {
207 // Test that removing all added elements brings the object back to its initial state
208 muhash.Remove(data);
209 muhash.Remove(data2);
210 muhash.Finalize(out);
211 out2 = initial_state_hash;
212 });
213 assert(out == out2);
214}
arith_uint256.h
FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition FuzzedDataProvider.h:205
MuHash3072
A class representing MuHash sets.
Definition muhash.h:103
MuHash3072::Finalize
void Finalize(uint256 &out) noexcept
Definition muhash.cpp:552
MuHash3072::Insert
MuHash3072 & Insert(std::span< const unsigned char > in) noexcept
Definition muhash.cpp:577
MuHash3072::Remove
MuHash3072 & Remove(std::span< const unsigned char > in) noexcept
Definition muhash.cpp:582
Num3072::ToBytes
void ToBytes(unsigned char(&out)[BYTE_SIZE])
Definition muhash.cpp:526
Num3072::SetToOne
void SetToOne()
Definition muhash.cpp:493
Num3072::Divide
void Divide(const Num3072 &a)
Definition muhash.cpp:499
Num3072::Multiply
void Multiply(const Num3072 &a)
Definition muhash.cpp:456
base_uint
Template base class for unsigned big integers.
Definition arith_uint256.h:26
uint256
256-bit opaque blob.
Definition uint256.h:195
WriteLE32
void WriteLE32(B *ptr, uint32_t x)
Definition common.h:50
ReadLE32
uint32_t ReadLE32(const B *ptr)
Definition common.h:27
FUZZ_TARGET
#define FUZZ_TARGET(...)
Definition fuzz.h:35
Serialize
void Serialize(Stream &, V)=delete
CallOneOf
size_t CallOneOf(FuzzedDataProvider &fuzzed_data_provider, Callables... callables)
Definition util.h:35
ConsumeRandomLengthByteVector
std::vector< B > ConsumeRandomLengthByteVector(FuzzedDataProvider &fuzzed_data_provider, const std::optional< size_t > &max_length=std::nullopt) noexcept
Definition util.h:57
Ticks
constexpr auto Ticks(Dur2 d)
Helper to count the seconds of a duration/time_point.
Definition time.h:73
assert
assert(!tx.IsCoinBase())
fuzzed_data_provider
FuzzedDataProvider & fuzzed_data_provider
Definition fees.cpp:38
Generated on Thu Apr 16 2026 09:42:38 for Bitcoin Core by doxygen 1.10.0