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