Bitcoin Core  21.99.0
P2P Digital Currency
Public Member Functions | Private Member Functions | Private Attributes | List of all members
MuHash3072 Class Reference

A class representing MuHash sets. More...

#include <muhash.h>

Collaboration diagram for MuHash3072:
[legend]

Public Member Functions

 MuHash3072 () noexcept
 
 MuHash3072 (Span< const unsigned char > in) noexcept
 
MuHash3072Insert (Span< const unsigned char > in) noexcept
 
MuHash3072Remove (Span< const unsigned char > in) noexcept
 
MuHash3072operator*= (const MuHash3072 &mul) noexcept
 
MuHash3072operator/= (const MuHash3072 &div) noexcept
 
void Finalize (uint256 &out) noexcept
 
 SERIALIZE_METHODS (MuHash3072, obj)
 

Private Member Functions

Num3072 ToNum3072 (Span< const unsigned char > in)
 

Private Attributes

Num3072 m_numerator
 
Num3072 m_denominator
 

Detailed Description

A class representing MuHash sets.

MuHash is a hashing algorithm that supports adding set elements in any order but also deleting in any order. As a result, it can maintain a running sum for a set of data as a whole, and add/remove when data is added to or removed from it. A downside of MuHash is that computing an inverse is relatively expensive. This is solved by representing the running value as a fraction, and multiplying added elements into the numerator and removed elements into the denominator. Only when the final hash is desired, a single modular inverse and multiplication is needed to combine the two. The combination is also run on serialization to allow for space-efficient storage on disk.

As the update operations are also associative, H(a)+H(b)+H(c)+H(d) can in fact be computed as (H(a)+H(b)) + (H(c)+H(d)). This implies that all of this is perfectly parallellizable: each thread can process an arbitrary subset of the update operations, allowing them to be efficiently combined later.

MuHash does not support checking if an element is already part of the set. That is why this class does not enforce the use of a set as the data it represents because there is no efficient way to do so. It is possible to add elements more than once and also to remove elements that have not been added before. However, this implementation is intended to represent a set of elements.

See also https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf and https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html.

Definition at line 94 of file muhash.h.

Constructor & Destructor Documentation

◆ MuHash3072() [1/2]

MuHash3072::MuHash3072 ( )
inlinenoexcept

Definition at line 104 of file muhash.h.

◆ MuHash3072() [2/2]

MuHash3072::MuHash3072 ( Span< const unsigned char >  in)
explicitnoexcept

Definition at line 308 of file muhash.cpp.

Member Function Documentation

◆ Finalize()

void MuHash3072::Finalize ( uint256 out)
noexcept

Definition at line 313 of file muhash.cpp.

Here is the caller graph for this function:

◆ Insert()

MuHash3072 & MuHash3072::Insert ( Span< const unsigned char >  in)
noexcept

Definition at line 338 of file muhash.cpp.

Here is the caller graph for this function:

◆ operator*=()

MuHash3072 & MuHash3072::operator*= ( const MuHash3072 mul)
noexcept

Definition at line 324 of file muhash.cpp.

◆ operator/=()

MuHash3072 & MuHash3072::operator/= ( const MuHash3072 div)
noexcept

Definition at line 331 of file muhash.cpp.

◆ Remove()

MuHash3072 & MuHash3072::Remove ( Span< const unsigned char >  in)
noexcept

Definition at line 343 of file muhash.cpp.

◆ SERIALIZE_METHODS()

MuHash3072::SERIALIZE_METHODS ( MuHash3072  ,
obj   
)
inline

Definition at line 124 of file muhash.h.

◆ ToNum3072()

Num3072 MuHash3072::ToNum3072 ( Span< const unsigned char >  in)
private

Definition at line 298 of file muhash.cpp.

Here is the call graph for this function:

Member Data Documentation

◆ m_denominator

Num3072 MuHash3072::m_denominator
private

Definition at line 98 of file muhash.h.

◆ m_numerator

Num3072 MuHash3072::m_numerator
private

Definition at line 97 of file muhash.h.


The documentation for this class was generated from the following files: