diff --git a/src/config/CMakeLists.txt b/src/config/CMakeLists.txt --- a/src/config/CMakeLists.txt +++ b/src/config/CMakeLists.txt @@ -5,6 +5,7 @@ include(CheckIncludeFiles) include(CheckSymbolExists) +include(CheckTypeSize) include(CheckCXXSymbolExists) include(CheckCXXSourceCompiles) @@ -255,5 +256,7 @@ set(HAVE_SYSTEM 1) endif() +check_type_size(__int128 __INT128) + # Generate the config configure_file(bitcoin-config.h.cmake.in bitcoin-config.h ESCAPE_QUOTES) diff --git a/src/config/bitcoin-config.h.cmake.in b/src/config/bitcoin-config.h.cmake.in --- a/src/config/bitcoin-config.h.cmake.in +++ b/src/config/bitcoin-config.h.cmake.in @@ -88,4 +88,6 @@ /* Define if QtDBus support should be enabled */ #cmakedefine USE_DBUS 1 +#cmakedefine HAVE___INT128 1 + #endif // BITCOIN_BITCOIN_CONFIG_H diff --git a/src/crypto/CMakeLists.txt b/src/crypto/CMakeLists.txt --- a/src/crypto/CMakeLists.txt +++ b/src/crypto/CMakeLists.txt @@ -10,6 +10,7 @@ hkdf_sha256_32.cpp hmac_sha256.cpp hmac_sha512.cpp + muhash.cpp poly1305.cpp ripemd160.cpp sha1.cpp diff --git a/src/crypto/muhash.h b/src/crypto/muhash.h new file mode 100644 --- /dev/null +++ b/src/crypto/muhash.h @@ -0,0 +1,129 @@ +// Copyright (c) 2017-2020 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_CRYPTO_MUHASH_H +#define BITCOIN_CRYPTO_MUHASH_H + +#if defined(HAVE_CONFIG_H) +#include +#endif + +#include +#include +#include + +#include + +class Num3072 { +private: + void FullReduce(); + bool IsOverflow() const; + Num3072 GetInverse() const; + +public: +#ifdef HAVE___INT128 + typedef unsigned __int128 double_limb_t; + typedef uint64_t limb_t; + static constexpr int LIMBS = 48; + static constexpr int LIMB_SIZE = 64; +#else + typedef uint64_t double_limb_t; + typedef uint32_t limb_t; + static constexpr int LIMBS = 96; + static constexpr int LIMB_SIZE = 32; +#endif + limb_t limbs[LIMBS]; + + // Sanity check for Num3072 constants + static_assert(LIMB_SIZE * LIMBS == 3072, "Num3072 isn't 3072 bits"); + static_assert(sizeof(double_limb_t) == sizeof(limb_t) * 2, + "bad size for double_limb_t"); + static_assert(sizeof(limb_t) * 8 == LIMB_SIZE, "LIMB_SIZE is incorrect"); + + // Hard coded values in MuHash3072 constructor and Finalize + static_assert(sizeof(limb_t) == 4 || sizeof(limb_t) == 8, + "bad size for limb_t"); + + void Multiply(const Num3072 &a); + void Divide(const Num3072 &a); + void SetToOne(); + void Square(); + + Num3072() { this->SetToOne(); }; + + SERIALIZE_METHODS(Num3072, obj) { + for (auto &limb : obj.limbs) { + READWRITE(limb); + } + } +}; + +/** + * A class representing MuHash sets + * + * MuHash is a hashing algorithm that supports adding set elements in any + * order but also deleting in any order. As a result, it can maintain a + * running sum for a set of data as a whole, and add/remove when data + * is added to or removed from it. A downside of MuHash is that computing + * an inverse is relatively expensive. This is solved by representing + * the running value as a fraction, and multiplying added elements into + * the numerator and removed elements into the denominator. Only when the + * final hash is desired, a single modular inverse and multiplication is + * needed to combine the two. The combination is also run on serialization + * to allow for space-efficient storage on disk. + * + * As the update operations are also associative, H(a)+H(b)+H(c)+H(d) can + * in fact be computed as (H(a)+H(b)) + (H(c)+H(d)). This implies that + * all of this is perfectly parallellizable: each thread can process an + * arbitrary subset of the update operations, allowing them to be + * efficiently combined later. + * + * Muhash does not support checking if an element is already part of the + * set. That is why this class does not enforce the use of a set as the + * data it represents because there is no efficient way to do so. + * It is possible to add elements more than once and also to remove + * elements that have not been added before. However, this implementation + * is intended to represent a set of elements. + * + * See also https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf and + * https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html. + */ +class MuHash3072 { +private: + static constexpr size_t BYTE_SIZE = 384; + + Num3072 m_numerator; + Num3072 m_denominator; + + Num3072 ToNum3072(Span in); + +public: + /* The empty set. */ + MuHash3072() noexcept {}; + + /* A singleton with variable sized data in it. */ + explicit MuHash3072(Span in) noexcept; + + /* Insert a single piece of data into the set. */ + MuHash3072 &Insert(Span in) noexcept; + + /* Remove a single piece of data from the set. */ + MuHash3072 &Remove(Span in) noexcept; + + /* Multiply (resulting in a hash for the union of the sets) */ + MuHash3072 &operator*=(const MuHash3072 &mul) noexcept; + + /* Divide (resulting in a hash for the difference of the sets) */ + MuHash3072 &operator/=(const MuHash3072 &div) noexcept; + + /* Finalize into a 32-byte hash. Does not change this object's value. */ + void Finalize(uint256 &out) noexcept; + + SERIALIZE_METHODS(MuHash3072, obj) { + READWRITE(obj.m_numerator); + READWRITE(obj.m_denominator); + } +}; + +#endif // BITCOIN_CRYPTO_MUHASH_H diff --git a/src/crypto/muhash.cpp b/src/crypto/muhash.cpp new file mode 100644 --- /dev/null +++ b/src/crypto/muhash.cpp @@ -0,0 +1,375 @@ +// Copyright (c) 2017-2020 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include + +#include +#include +#include + +#include +#include +#include + +namespace { + +using limb_t = Num3072::limb_t; +using double_limb_t = Num3072::double_limb_t; +constexpr int LIMB_SIZE = Num3072::LIMB_SIZE; +constexpr int LIMBS = Num3072::LIMBS; +/** + * 2^3072 - 1103717, the largest 3072-bit safe prime number, is used as the + * modulus. + */ +constexpr limb_t MAX_PRIME_DIFF = 1103717; + +/** + * Extract the lowest limb of [c0,c1,c2] into n, and left shift the number by 1 + * limb. + */ +inline void extract3(limb_t &c0, limb_t &c1, limb_t &c2, limb_t &n) { + n = c0; + c0 = c1; + c1 = c2; + c2 = 0; +} + +/** [c0,c1] = a * b */ +inline void mul(limb_t &c0, limb_t &c1, const limb_t &a, const limb_t &b) { + double_limb_t t = (double_limb_t)a * b; + c1 = t >> LIMB_SIZE; + c0 = t; +} + +/* [c0,c1,c2] += n * [d0,d1,d2]. c2 is 0 initially */ +inline void mulnadd3(limb_t &c0, limb_t &c1, limb_t &c2, limb_t &d0, limb_t &d1, + limb_t &d2, const limb_t &n) { + double_limb_t t = (double_limb_t)d0 * n + c0; + c0 = t; + t >>= LIMB_SIZE; + t += (double_limb_t)d1 * n + c1; + c1 = t; + t >>= LIMB_SIZE; + c2 = t + d2 * n; +} + +/* [c0,c1] *= n */ +inline void muln2(limb_t &c0, limb_t &c1, const limb_t &n) { + double_limb_t t = (double_limb_t)c0 * n; + c0 = t; + t >>= LIMB_SIZE; + t += (double_limb_t)c1 * n; + c1 = t; +} + +/** [c0,c1,c2] += a * b */ +inline void muladd3(limb_t &c0, limb_t &c1, limb_t &c2, const limb_t &a, + const limb_t &b) { + double_limb_t t = (double_limb_t)a * b; + limb_t th = t >> LIMB_SIZE; + limb_t tl = t; + + c0 += tl; + th += (c0 < tl) ? 1 : 0; + c1 += th; + c2 += (c1 < th) ? 1 : 0; +} + +/** [c0,c1,c2] += 2 * a * b */ +inline void muldbladd3(limb_t &c0, limb_t &c1, limb_t &c2, const limb_t &a, + const limb_t &b) { + double_limb_t t = (double_limb_t)a * b; + limb_t th = t >> LIMB_SIZE; + limb_t tl = t; + + c0 += tl; + limb_t tt = th + ((c0 < tl) ? 1 : 0); + c1 += tt; + c2 += (c1 < tt) ? 1 : 0; + c0 += tl; + th += (c0 < tl) ? 1 : 0; + c1 += th; + c2 += (c1 < th) ? 1 : 0; +} + +/** + * Add limb a to [c0,c1]: [c0,c1] += a. Then extract the lowest + * limb of [c0,c1] into n, and left shift the number by 1 limb. + */ +inline void addnextract2(limb_t &c0, limb_t &c1, const limb_t &a, limb_t &n) { + limb_t c2 = 0; + + // add + c0 += a; + if (c0 < a) { + c1 += 1; + + // Handle case when c1 has overflown + if (c1 == 0) { + c2 = 1; + } + } + + // extract + n = c0; + c0 = c1; + c1 = c2; +} + +/** in_out = in_out^(2^sq) * mul */ +inline void square_n_mul(Num3072 &in_out, const int sq, const Num3072 &mul) { + for (int j = 0; j < sq; ++j) { + in_out.Square(); + } + in_out.Multiply(mul); +} + +} // namespace + +/** Indicates wether d is larger than the modulus. */ +bool Num3072::IsOverflow() const { + if (this->limbs[0] <= std::numeric_limits::max() - MAX_PRIME_DIFF) { + return false; + } + for (int i = 1; i < LIMBS; ++i) { + if (this->limbs[i] != std::numeric_limits::max()) { + return false; + } + } + return true; +} + +void Num3072::FullReduce() { + limb_t c0 = MAX_PRIME_DIFF; + limb_t c1 = 0; + for (int i = 0; i < LIMBS; ++i) { + addnextract2(c0, c1, this->limbs[i], this->limbs[i]); + } +} + +Num3072 Num3072::GetInverse() const { + // For fast exponentiation a sliding window exponentiation with repunit + // precomputation is utilized. See "Fast Point Decompression for Standard + // Elliptic Curves" (Brumley, Järvinen, 2008). + + // p[i] = a^(2^(2^i)-1) + Num3072 p[12]; + + p[0] = *this; + + for (int i = 0; i < 11; ++i) { + p[i + 1] = p[i]; + for (int j = 0; j < (1 << i); ++j) { + p[i + 1].Square(); + } + p[i + 1].Multiply(p[i]); + } + + Num3072 out; + + out = p[11]; + + square_n_mul(out, 512, p[9]); + square_n_mul(out, 256, p[8]); + square_n_mul(out, 128, p[7]); + square_n_mul(out, 64, p[6]); + square_n_mul(out, 32, p[5]); + square_n_mul(out, 8, p[3]); + square_n_mul(out, 2, p[1]); + square_n_mul(out, 1, p[0]); + square_n_mul(out, 5, p[2]); + square_n_mul(out, 3, p[0]); + square_n_mul(out, 2, p[0]); + square_n_mul(out, 4, p[0]); + square_n_mul(out, 4, p[1]); + square_n_mul(out, 3, p[0]); + + return out; +} + +void Num3072::Multiply(const Num3072 &a) { + limb_t c0 = 0, c1 = 0, c2 = 0; + Num3072 tmp; + + /* Compute limbs 0..N-2 of this*a into tmp, including one reduction. */ + for (int j = 0; j < LIMBS - 1; ++j) { + limb_t d0 = 0, d1 = 0, d2 = 0; + mul(d0, d1, this->limbs[1 + j], a.limbs[LIMBS + j - (1 + j)]); + for (int i = 2 + j; i < LIMBS; ++i) { + muladd3(d0, d1, d2, this->limbs[i], a.limbs[LIMBS + j - i]); + } + mulnadd3(c0, c1, c2, d0, d1, d2, MAX_PRIME_DIFF); + for (int i = 0; i < j + 1; ++i) { + muladd3(c0, c1, c2, this->limbs[i], a.limbs[j - i]); + } + extract3(c0, c1, c2, tmp.limbs[j]); + } + + /* Compute limb N-1 of a*b into tmp. */ + assert(c2 == 0); + for (int i = 0; i < LIMBS; ++i) { + muladd3(c0, c1, c2, this->limbs[i], a.limbs[LIMBS - 1 - i]); + } + extract3(c0, c1, c2, tmp.limbs[LIMBS - 1]); + + /* Perform a second reduction. */ + muln2(c0, c1, MAX_PRIME_DIFF); + for (int j = 0; j < LIMBS; ++j) { + addnextract2(c0, c1, tmp.limbs[j], this->limbs[j]); + } + + assert(c1 == 0); + assert(c0 == 0 || c0 == 1); + + /** + * Perform up to two more reductions if the internal state has already + * overflown the MAX of Num3072 or if it is larger than the modulus or + * if both are the case. + */ + if (this->IsOverflow()) { + this->FullReduce(); + } + if (c0) { + this->FullReduce(); + } +} + +void Num3072::Square() { + limb_t c0 = 0, c1 = 0, c2 = 0; + Num3072 tmp; + + /* Compute limbs 0..N-2 of this*this into tmp, including one reduction. */ + for (int j = 0; j < LIMBS - 1; ++j) { + limb_t d0 = 0, d1 = 0, d2 = 0; + for (int i = 0; i < (LIMBS - 1 - j) / 2; ++i) { + muldbladd3(d0, d1, d2, this->limbs[i + j + 1], + this->limbs[LIMBS - 1 - i]); + } + if ((j + 1) & 1) { + muladd3(d0, d1, d2, this->limbs[(LIMBS - 1 - j) / 2 + j + 1], + this->limbs[LIMBS - 1 - (LIMBS - 1 - j) / 2]); + } + mulnadd3(c0, c1, c2, d0, d1, d2, MAX_PRIME_DIFF); + for (int i = 0; i < (j + 1) / 2; ++i) { + muldbladd3(c0, c1, c2, this->limbs[i], this->limbs[j - i]); + } + if ((j + 1) & 1) { + muladd3(c0, c1, c2, this->limbs[(j + 1) / 2], + this->limbs[j - (j + 1) / 2]); + } + extract3(c0, c1, c2, tmp.limbs[j]); + } + + assert(c2 == 0); + for (int i = 0; i < LIMBS / 2; ++i) { + muldbladd3(c0, c1, c2, this->limbs[i], this->limbs[LIMBS - 1 - i]); + } + extract3(c0, c1, c2, tmp.limbs[LIMBS - 1]); + + /* Perform a second reduction. */ + muln2(c0, c1, MAX_PRIME_DIFF); + for (int j = 0; j < LIMBS; ++j) { + addnextract2(c0, c1, tmp.limbs[j], this->limbs[j]); + } + + assert(c1 == 0); + assert(c0 == 0 || c0 == 1); + + /** + * Perform up to two more reductions if the internal state has already + * overflown the MAX of Num3072 or if it is larger than the modulus or + * if both are the case. + */ + if (this->IsOverflow()) { + this->FullReduce(); + } + if (c0) { + this->FullReduce(); + } +} + +void Num3072::SetToOne() { + this->limbs[0] = 1; + for (int i = 1; i < LIMBS; ++i) { + this->limbs[i] = 0; + } +} + +void Num3072::Divide(const Num3072 &a) { + if (this->IsOverflow()) { + this->FullReduce(); + } + + Num3072 inv{}; + if (a.IsOverflow()) { + Num3072 b = a; + b.FullReduce(); + inv = b.GetInverse(); + } else { + inv = a.GetInverse(); + } + + this->Multiply(inv); + if (this->IsOverflow()) { + this->FullReduce(); + } +} + +Num3072 MuHash3072::ToNum3072(Span in) { + Num3072 out{}; + uint256 hashed_in = (CHashWriter(SER_DISK, 0) << in).GetSHA256(); + uint8_t tmp[BYTE_SIZE]; + ChaCha20(hashed_in.data(), hashed_in.size()).Keystream(tmp, BYTE_SIZE); + for (int i = 0; i < LIMBS; ++i) { + if (sizeof(limb_t) == 4) { + out.limbs[i] = ReadLE32(tmp + 4 * i); + } else if (sizeof(limb_t) == 8) { + out.limbs[i] = ReadLE64(tmp + 8 * i); + } + } + return out; +} + +MuHash3072::MuHash3072(Span in) noexcept { + m_numerator = ToNum3072(in); +} + +void MuHash3072::Finalize(uint256 &out) noexcept { + m_numerator.Divide(m_denominator); + // Needed to keep the MuHash object valid + m_denominator.SetToOne(); + + uint8_t data[384]; + for (int i = 0; i < LIMBS; ++i) { + if (sizeof(limb_t) == 4) { + WriteLE32(data + i * 4, m_numerator.limbs[i]); + } else if (sizeof(limb_t) == 8) { + WriteLE64(data + i * 8, m_numerator.limbs[i]); + } + } + + out = (CHashWriter(SER_DISK, 0) << data).GetSHA256(); +} + +MuHash3072 &MuHash3072::operator*=(const MuHash3072 &mul) noexcept { + m_numerator.Multiply(mul.m_numerator); + m_denominator.Multiply(mul.m_denominator); + return *this; +} + +MuHash3072 &MuHash3072::operator/=(const MuHash3072 &div) noexcept { + m_numerator.Multiply(div.m_denominator); + m_denominator.Multiply(div.m_numerator); + return *this; +} + +MuHash3072 &MuHash3072::Insert(Span in) noexcept { + m_numerator.Multiply(ToNum3072(in)); + return *this; +} + +MuHash3072 &MuHash3072::Remove(Span in) noexcept { + m_numerator.Divide(ToNum3072(in)); + return *this; +} diff --git a/src/test/crypto_tests.cpp b/src/test/crypto_tests.cpp --- a/src/test/crypto_tests.cpp +++ b/src/test/crypto_tests.cpp @@ -8,6 +8,7 @@ #include #include #include +#include #include #include #include @@ -16,6 +17,7 @@ #include #include +#include #include #include @@ -1769,4 +1771,145 @@ "d894b86261436362e64241e61f6b3e6589daf64dc641f60570c4c0bf3b1f2ca3"); } +static MuHash3072 FromInt(uint8_t i) { + uint8_t tmp[32] = {i, 0}; + return MuHash3072(tmp); +} + +BOOST_AUTO_TEST_CASE(muhash_tests) { + uint256 out; + + for (int iter = 0; iter < 10; ++iter) { + uint256 res; + int table[4]; + for (int i = 0; i < 4; ++i) { + table[i] = g_insecure_rand_ctx.randbits(3); + } + for (int order = 0; order < 4; ++order) { + MuHash3072 acc; + for (int i = 0; i < 4; ++i) { + int t = table[i ^ order]; + if (t & 4) { + acc /= FromInt(t & 3); + } else { + acc *= FromInt(t & 3); + } + } + acc.Finalize(out); + if (order == 0) { + res = out; + } else { + BOOST_CHECK(res == out); + } + } + + MuHash3072 x = FromInt(g_insecure_rand_ctx.randbits(4)); // x=X + MuHash3072 y = FromInt(g_insecure_rand_ctx.randbits(4)); // x=X, y=Y + MuHash3072 z; // x=X, y=Y, z=1 + z *= x; // x=X, y=Y, z=X + z *= y; // x=X, y=Y, z=X*Y + y *= x; // x=X, y=Y*X, z=X*Y + z /= y; // x=X, y=Y*X, z=1 + z.Finalize(out); + + uint256 out2; + MuHash3072 a; + a.Finalize(out2); + + BOOST_CHECK_EQUAL(out, out2); + } + + MuHash3072 acc = FromInt(0); + acc *= FromInt(1); + acc /= FromInt(2); + acc.Finalize(out); + BOOST_CHECK_EQUAL(out, uint256S("10d312b100cbd32ada024a6646e40d3482fcff1036" + "68d2625f10002a607d5863")); + + MuHash3072 acc2 = FromInt(0); + uint8_t tmp[32] = {1, 0}; + acc2.Insert(tmp); + uint8_t tmp2[32] = {2, 0}; + acc2.Remove(tmp2); + acc2.Finalize(out); + BOOST_CHECK_EQUAL(out, uint256S("10d312b100cbd32ada024a6646e40d3482fcff1036" + "68d2625f10002a607d5863")); + + // Test MuHash3072 serialization + MuHash3072 serchk = FromInt(1); + serchk *= FromInt(2); + std::string ser_exp = + "1fa093295ea30a6a3acdc7b3f770fa538eff537528e990e2910e40bbcfd7f6696b1256" + "901929094694b56316de342f593303dd12ac43e06dce1be1ff8301c845beb15468fff0" + "ef002dbf80c29f26e6452bccc91b5cb9437ad410d2a67ea847887fa3c6a65533099468" + "80fe20db2c73fe0641adbd4e86edfee0d9f8cd0ee1230898873dc13ed8ddcaf045c80f" + "aa082774279007a2253f8922ee3ef361d378a6af3ddaf180b190ac97e556888c36b3d1" + "fb1c85aab9ccd46e3deaeb7b7cf5db067a7e9ff86b658cf3acd6662bbcce37232daa75" + "3c48b794356c020090c831a8304416e2aa7ad633c0ddb2f11be1be316a81be7f7e4720" + "71c042cb68faef549c221ebff209273638b741aba5a81675c45a5fa92fea4ca821d7a3" + "24cb1e1a2ccd3b76c4228ec8066dad2a5df6e1bd0de45c7dd5de8070bdb46db6c554cf" + "9aefc9b7b2bbf9f75b1864d9f95005314593905c0109b71f703d49944ae94477b51dac" + "10a816bb6d1c700bafabc8bd86fac8df24be519a2f2836b16392e18036cb13e48c5c01" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000"; + CDataStream ss_chk(SER_DISK, PROTOCOL_VERSION); + ss_chk << serchk; + BOOST_CHECK_EQUAL(ser_exp, HexStr(ss_chk.str())); + + // Test MuHash3072 deserialization + MuHash3072 deserchk; + ss_chk >> deserchk; + uint256 out3; + serchk.Finalize(out); + deserchk.Finalize(out3); + BOOST_CHECK_EQUAL(HexStr(out), HexStr(out3)); + + // Test MuHash3072 overflow, meaning the internal data is larger than the + // modulus. + CDataStream ss_max( + ParseHex( + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffffffffffffff010000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000"), + SER_DISK, PROTOCOL_VERSION); + MuHash3072 overflowchk; + ss_max >> overflowchk; + + uint256 out4; + overflowchk.Finalize(out4); + BOOST_CHECK_EQUAL( + HexStr(out4), + "3a31e6903aff0de9f62f9a9f7f8b861de76ce2cda09822b90014319ae5dc2271"); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/test/functional/test_framework/muhash.py b/test/functional/test_framework/muhash.py --- a/test/functional/test_framework/muhash.py +++ b/test/functional/test_framework/muhash.py @@ -89,13 +89,15 @@ def insert(self, data): """Insert a byte array data in the set.""" + data_hash = hashlib.sha256(data).digest() self.numerator = ( - self.numerator * data_to_num3072(data)) % self.MODULUS + self.numerator * data_to_num3072(data_hash)) % self.MODULUS def remove(self, data): """Remove a byte array from the set.""" + data_hash = hashlib.sha256(data).digest() self.denominator = ( - self.denominator * data_to_num3072(data)) % self.MODULUS + self.denominator * data_to_num3072(data_hash)) % self.MODULUS def digest(self): """Extract the final hash. Does not modify this object.""" @@ -108,14 +110,15 @@ class TestFrameworkMuhash(unittest.TestCase): def test_muhash(self): muhash = MuHash3072() - muhash.insert([0] * 32) - muhash.insert([1] + [0] * 31) - muhash.remove([2] + [0] * 31) + muhash.insert(b'\x00' * 32) + muhash.insert((b'\x01' + b'\x00' * 31)) + muhash.remove((b'\x02' + b'\x00' * 31)) finalized = muhash.digest() # This mirrors the result in the C++ MuHash3072 unit test self.assertEqual( finalized[::-1].hex(), - "a44e16d5e34d259b349af21c06e65d653915d2e208e4e03f389af750dc0bfdc3") + "10d312b100cbd32ada024a6646e40d3482fcff103668d2625f10002a607d5863" + ) def test_chacha20(self): def chacha_check(key, result):