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