Bitcoin Core 28.99.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
17namespace {
18
22class arith_uint6144 : public base_uint<6144> {
23public:
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
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 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}
arith_uint256.h
FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition: FuzzedDataProvider.h:205
MuHash3072
A class representing MuHash sets.
Definition: muhash.h:100
MuHash3072::Finalize
void Finalize(uint256 &out) noexcept
Definition: muhash.cpp:551
MuHash3072::Remove
MuHash3072 & Remove(Span< const unsigned char > in) noexcept
Definition: muhash.cpp:581
MuHash3072::Insert
MuHash3072 & Insert(Span< const unsigned char > in) noexcept
Definition: muhash.cpp:576
Num3072
Definition: muhash.h:14
Num3072::ToBytes
void ToBytes(unsigned char(&out)[BYTE_SIZE])
Definition: muhash.cpp:525
Num3072::SetToOne
void SetToOne()
Definition: muhash.cpp:492
Num3072::Divide
void Divide(const Num3072 &a)
Definition: muhash.cpp:498
Num3072::Multiply
void Multiply(const Num3072 &a)
Definition: muhash.cpp:455
Span
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:98
Span::size
constexpr std::size_t size() const noexcept
Definition: span.h:187
Span::data
constexpr C * data() const noexcept
Definition: span.h:174
base_uint
Template base class for unsigned big integers.
Definition: arith_uint256.h:25
uint256
256-bit opaque blob.
Definition: uint256.h:201
WriteLE32
void WriteLE32(B *ptr, uint32_t x)
Definition: common.h:50
ReadLE32
uint32_t ReadLE32(const B *ptr)
Definition: common.h:27
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
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
test_vectors_musig2_generate.data
data
Definition: test_vectors_musig2_generate.py:98
tests_wycheproof_generate.out
string out
Definition: tests_wycheproof_generate.py:28
Serialize
void Serialize(Stream &, V)=delete
FUZZ_TARGET
FUZZ_TARGET(num3072_mul)
Definition: muhash.cpp:106
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
assert
assert(!tx.IsCoinBase())
Generated on Sat Feb 22 2025 20:00:12 for Bitcoin Core by doxygen 1.9.4