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                 :            : #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