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             : #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 __SIZEOF_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           0 :     Num3072() { this->SetToOne(); };
      55             :     Num3072(const unsigned char (&data)[BYTE_SIZE]);
      56             : 
      57           0 :     SERIALIZE_METHODS(Num3072, obj)
      58             :     {
      59           0 :         for (auto& limb : obj.limbs) {
      60           0 :             READWRITE(limb);
      61             :         }
      62           0 :     }
      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           0 :     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           0 :     SERIALIZE_METHODS(MuHash3072, obj)
     125             :     {
     126           0 :         READWRITE(obj.m_numerator);
     127           0 :         READWRITE(obj.m_denominator);
     128           0 :     }
     129             : };
     130             : 
     131             : #endif // BITCOIN_CRYPTO_MUHASH_H