Branch data Line data Source code
# 1 : : // Copyright (c) 2017-2020 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 : : #ifndef BITCOIN_CRYPTO_MUHASH_H # 6 : : #define BITCOIN_CRYPTO_MUHASH_H # 7 : : # 8 : : #if defined(HAVE_CONFIG_H) # 9 : : #include <config/bitcoin-config.h> # 10 : : #endif # 11 : : # 12 : : #include <serialize.h> # 13 : : #include <uint256.h> # 14 : : # 15 : : #include <stdint.h> # 16 : : # 17 : : class Num3072 # 18 : : { # 19 : : private: # 20 : : void FullReduce(); # 21 : : bool IsOverflow() const; # 22 : : Num3072 GetInverse() const; # 23 : : # 24 : : public: # 25 : : static constexpr size_t BYTE_SIZE = 384; # 26 : : # 27 : : #ifdef HAVE___INT128 # 28 : : typedef unsigned __int128 double_limb_t; # 29 : : typedef uint64_t limb_t; # 30 : : static constexpr int LIMBS = 48; # 31 : : static constexpr int LIMB_SIZE = 64; # 32 : : #else # 33 : : typedef uint64_t double_limb_t; # 34 : : typedef uint32_t limb_t; # 35 : : static constexpr int LIMBS = 96; # 36 : : static constexpr int LIMB_SIZE = 32; # 37 : : #endif # 38 : : limb_t limbs[LIMBS]; # 39 : : # 40 : : // Sanity check for Num3072 constants # 41 : : static_assert(LIMB_SIZE * LIMBS == 3072, "Num3072 isn't 3072 bits"); # 42 : : static_assert(sizeof(double_limb_t) == sizeof(limb_t) * 2, "bad size for double_limb_t"); # 43 : : static_assert(sizeof(limb_t) * 8 == LIMB_SIZE, "LIMB_SIZE is incorrect"); # 44 : : # 45 : : // Hard coded values in MuHash3072 constructor and Finalize # 46 : : static_assert(sizeof(limb_t) == 4 || sizeof(limb_t) == 8, "bad size for limb_t"); # 47 : : # 48 : : void Multiply(const Num3072& a); # 49 : : void Divide(const Num3072& a); # 50 : : void SetToOne(); # 51 : : void Square(); # 52 : : void ToBytes(unsigned char (&out)[BYTE_SIZE]); # 53 : : # 54 : 2501922 : Num3072() { this->SetToOne(); }; # 55 : : Num3072(const unsigned char (&data)[BYTE_SIZE]); # 56 : : # 57 : : SERIALIZE_METHODS(Num3072, obj) # 58 : 1348 : { # 59 [ + + ][ + + ]: 64704 : for (auto& limb : obj.limbs) { # 60 : 64704 : READWRITE(limb); # 61 : 64704 : } # 62 : 1348 : } # 63 : : }; # 64 : : # 65 : : /** A class representing MuHash sets # 66 : : * # 67 : : * MuHash is a hashing algorithm that supports adding set elements in any # 68 : : * order but also deleting in any order. As a result, it can maintain a # 69 : : * running sum for a set of data as a whole, and add/remove when data # 70 : : * is added to or removed from it. A downside of MuHash is that computing # 71 : : * an inverse is relatively expensive. This is solved by representing # 72 : : * the running value as a fraction, and multiplying added elements into # 73 : : * the numerator and removed elements into the denominator. Only when the # 74 : : * final hash is desired, a single modular inverse and multiplication is # 75 : : * needed to combine the two. The combination is also run on serialization # 76 : : * to allow for space-efficient storage on disk. # 77 : : * # 78 : : * As the update operations are also associative, H(a)+H(b)+H(c)+H(d) can # 79 : : * in fact be computed as (H(a)+H(b)) + (H(c)+H(d)). This implies that # 80 : : * all of this is perfectly parallellizable: each thread can process an # 81 : : * arbitrary subset of the update operations, allowing them to be # 82 : : * efficiently combined later. # 83 : : * # 84 : : * MuHash does not support checking if an element is already part of the # 85 : : * set. That is why this class does not enforce the use of a set as the # 86 : : * data it represents because there is no efficient way to do so. # 87 : : * It is possible to add elements more than once and also to remove # 88 : : * elements that have not been added before. However, this implementation # 89 : : * is intended to represent a set of elements. # 90 : : * # 91 : : * See also https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf and # 92 : : * https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html. # 93 : : */ # 94 : : class MuHash3072 # 95 : : { # 96 : : private: # 97 : : Num3072 m_numerator; # 98 : : Num3072 m_denominator; # 99 : : # 100 : : Num3072 ToNum3072(Span<const unsigned char> in); # 101 : : # 102 : : public: # 103 : : /* The empty set. */ # 104 : 394 : MuHash3072() noexcept {}; # 105 : : # 106 : : /* A singleton with variable sized data in it. */ # 107 : : explicit MuHash3072(Span<const unsigned char> in) noexcept; # 108 : : # 109 : : /* Insert a single piece of data into the set. */ # 110 : : MuHash3072& Insert(Span<const unsigned char> in) noexcept; # 111 : : # 112 : : /* Remove a single piece of data from the set. */ # 113 : : MuHash3072& Remove(Span<const unsigned char> in) noexcept; # 114 : : # 115 : : /* Multiply (resulting in a hash for the union of the sets) */ # 116 : : MuHash3072& operator*=(const MuHash3072& mul) noexcept; # 117 : : # 118 : : /* Divide (resulting in a hash for the difference of the sets) */ # 119 : : MuHash3072& operator/=(const MuHash3072& div) noexcept; # 120 : : # 121 : : /* Finalize into a 32-byte hash. Does not change this object's value. */ # 122 : : void Finalize(uint256& out) noexcept; # 123 : : # 124 : : SERIALIZE_METHODS(MuHash3072, obj) # 125 : 674 : { # 126 : 674 : READWRITE(obj.m_numerator); # 127 : 674 : READWRITE(obj.m_denominator); # 128 : 674 : } # 129 : : }; # 130 : : # 131 : : #endif // BITCOIN_CRYPTO_MUHASH_H