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