muhash.py raw

   1  # Copyright (c) 2020 Pieter Wuille
   2  # Distributed under the MIT software license, see the accompanying
   3  # file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4  """Native Python MuHash3072 implementation."""
   5  
   6  import hashlib
   7  import unittest
   8  
   9  from .chacha20 import chacha20_block
  10  
  11  def data_to_num3072(data):
  12      """Hash a 32-byte array data to a 3072-bit number using 6 Chacha20 operations."""
  13      bytes384 = b""
  14      for counter in range(6):
  15          bytes384 += chacha20_block(data, bytes(12), counter)
  16      return int.from_bytes(bytes384, 'little')
  17  
  18  class MuHash3072:
  19      """Class representing the MuHash3072 computation of a set.
  20  
  21      See https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf and https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html
  22      """
  23  
  24      MODULUS = 2**3072 - 1103717
  25  
  26      def __init__(self):
  27          """Initialize for an empty set."""
  28          self.numerator = 1
  29          self.denominator = 1
  30  
  31      def insert(self, data):
  32          """Insert a byte array data in the set."""
  33          data_hash = hashlib.sha256(data).digest()
  34          self.numerator = (self.numerator * data_to_num3072(data_hash)) % self.MODULUS
  35  
  36      def remove(self, data):
  37          """Remove a byte array from the set."""
  38          data_hash = hashlib.sha256(data).digest()
  39          self.denominator = (self.denominator * data_to_num3072(data_hash)) % self.MODULUS
  40  
  41      def digest(self):
  42          """Extract the final hash. Does not modify this object."""
  43          val = (self.numerator * pow(self.denominator, -1, self.MODULUS)) % self.MODULUS
  44          bytes384 = val.to_bytes(384, 'little')
  45          return hashlib.sha256(bytes384).digest()
  46  
  47  class TestFrameworkMuhash(unittest.TestCase):
  48      def test_muhash(self):
  49          muhash = MuHash3072()
  50          muhash.insert(b'\x00' * 32)
  51          muhash.insert((b'\x01' + b'\x00' * 31))
  52          muhash.remove((b'\x02' + b'\x00' * 31))
  53          finalized = muhash.digest()
  54          # This mirrors the result in the C++ MuHash3072 unit test
  55          self.assertEqual(finalized[::-1].hex(), "10d312b100cbd32ada024a6646e40d3482fcff103668d2625f10002a607d5863")
  56