This is the second in a series of pull requests to implement an Index for UTXO set statistics.
This pull request adds a Python implementation of Muhash3072, a homomorphic hashing algorithm to be used for hashing the UTXO set. The Python implementation can then be used to compare behavior with the C++ version.
15+ r1, r2 = r2, r1 - q * r2
16+ if r1 > 1:
17+ return None
18+ if t1 < 0:
19+ t1 += n
20+ return t1
To simplify the code, one could just use Fermat’s little theorem here to calculate the modular inverse. The drawback is that it’s much slower than the extended Euclidean algorithm, calculating the modinv of a random 3072-bit number takes approx. 100-150ms on my machine, which is at least 1 order of magnitude slower. Not sure if that’s an issue and in the case of tests whether performance or readability is more important :-)
0def modinv(a, n):
1 """Compute the modular inverse of a prime modulo n using Fermat's little theorem."""
2 return pow(a, n-2, n)
pow() (see https://bugs.python.org/issue36027, https://github.com/python/cpython/pull/13266), internally calculating the modular inverse via the extended Euclidean algorithm. I.e. somewhere in the future it could be just a very simple:
return pow(a, -1, n)
That’s worth annotating in a TODO: // Python 3.8: return pow(a, -1, n) (tested locally with Python 3.8.2)
I like having the simpler approach here. It’s yet another sanity check that our implementation is correct, given the lack of test vectors. But given the performance impact, if it really matters compared to the rest of the test, better leave that as a TODO.
modinv(a, n) produces the same results as using pow(a, n-2, n)
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
0@@ -0,0 +1,80 @@
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+
8+def modinv(a, n):
key.py. Can you move it into util.py or a new crypto_util.py instead of repeating it?
17+ return None
18+ if t1 < 0:
19+ t1 += n
20+ return t1
21+
22+def rot32(v, bits):
bits < 0 or bits > 32 throws. Perhaps call bits %= 32 to reduce it to a valid value?
22+def rot32(v, bits):
23+ """Rotate the 32-bit value v left by bits bits."""
24+ return ((v << bits) & 0xffffffff) | (v >> (32 - bits))
25+
26+def chacha20_doubleround(s):
27+ """Apply a ChaCha20 double round to 16-element state array s."""
23+ """Rotate the 32-bit value v left by bits bits."""
24+ return ((v << bits) & 0xffffffff) | (v >> (32 - bits))
25+
26+def chacha20_doubleround(s):
27+ """Apply a ChaCha20 double round to 16-element state array s."""
28+ for a, b, c, d in ((0, 4, 8, 12), (1, 5, 9, 13), (2, 6, 10, 14), (3, 7, 11, 15), (0, 5, 10, 15), (1, 6, 11, 12), (2, 7, 8, 13), (3, 4, 9, 14)):
Explicitly naming the quarter rounds would make this clearer:
0 QUARTER_ROUNDS = [(0, 4, 8, 12),
1 (1, 5, 9, 13),
2 (2, 6, 10, 14),
3 (3, 7, 11, 15),
4 (0, 5, 10, 15),
5 (1, 6, 11, 12),
6 (2, 7, 8, 13),
7 (3, 4, 9, 14)]
8 for a, b, c, d in QUARTER_ROUNDS:
37+
38+def chacha20_32_to_384(key32):
39+ """Specialized ChaCha20 implementation with 32-byte key, 0 IV, 384-byte output."""
40+ init = [1634760805, 857760878, 2036477234, 1797285236] + [0] * 12
41+ for i in range(8):
42+ init[4 + i] = int.from_bytes(key32[4*i:4*(i+1)], 'little')
Again, being explicitly about where these magic numbers come from would be nice:
0 # See RFC 7539 section 2.3 for chacha20 parameters
1 CONSTANTS = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
2 key_bytes = []
3 for i in range(8):
4 key_bytes[i] = int.from_bytes(key32[4*i:4*(i+1)], 'little')
5 INITIALIZATION_VECTOR = [0] * 4
6 init = CONSTANTS + key_bytes + INITIALIZATION_VECTOR
39+ """Specialized ChaCha20 implementation with 32-byte key, 0 IV, 384-byte output."""
40+ init = [1634760805, 857760878, 2036477234, 1797285236] + [0] * 12
41+ for i in range(8):
42+ init[4 + i] = int.from_bytes(key32[4*i:4*(i+1)], 'little')
43+ out = bytearray()
44+ for pos in range(6):
pos? Would counter be a better name, since this value is used as the block counter?
42+ init[4 + i] = int.from_bytes(key32[4*i:4*(i+1)], 'little')
43+ out = bytearray()
44+ for pos in range(6):
45+ init[12] = pos
46+ s = list(init)
47+ for rnd in range(10):
rnd is often used to mean random, which is confusing here.
41+ for i in range(8):
42+ init[4 + i] = int.from_bytes(key32[4*i:4*(i+1)], 'little')
43+ out = bytearray()
44+ for pos in range(6):
45+ init[12] = pos
46+ s = list(init)
I think this would be clearer as:
0 s = init.copy()
.copy() is around twice as fast.
49+ for i in range(16):
50+ out.extend(((s[i] + init[i]) & 0xffffffff).to_bytes(4, 'little'))
51+ return bytes(out)
52+
53+def data_to_num3072(data):
54+ """Map a byte array data to a 3072-bit number."""
I think this docstring should indicate that it’s hashing using Chacha20
0 """Hash a 32-byte array data to a 3072-bit number using 6 Chacha20 operations."""
54+ """Map a byte array data to a 3072-bit number."""
55+ bytes384 = chacha20_32_to_384(data)
56+ return int.from_bytes(bytes384, 'little')
57+
58+class MuHash3072:
59+ """Class representing the MuHash3072 computation of a set."""
Reference where the algorithm comes from:
244@@ -241,6 +245,15 @@ def _test_gettxoutsetinfo(self):
245 del res['disk_size'], res3['disk_size']
246 assert_equal(res, res3)
247
248+ self.log.info("Test that MuHash implementation in Python returns the same result as C++")
53+def data_to_num3072(data):
54+ """Map a byte array data to a 3072-bit number."""
55+ bytes384 = chacha20_32_to_384(data)
56+ return int.from_bytes(bytes384, 'little')
57+
58+class MuHash3072:
You could add the same value twice and it would work.
Sets commonly ignore the second insertion. The set in Python also works like this.
63+ def __init__(self):
64+ """Initialize for an empty set."""
65+ self.numerator = 1
66+ self.denominator = 1
67+
68+ def insert(self, data):
add in collections.abc.
67+
68+ def insert(self, data):
69+ """Insert a byte array data in the set."""
70+ self.numerator = (self.numerator * data_to_num3072(data)) % self.MODULUS
71+
72+ def remove(self, data):
discard in collections.abc
collections.abc instead of inventing new names.
chacha20_doubleround() could be part of that, but until BIP324 I think it’s fine to have it in the same file as the muhash code.
629@@ -629,3 +630,33 @@ def find_vout_for_address(node, txid, addr):
630 if any([addr == a for a in tx["vout"][i]["scriptPubKey"]["addresses"]]):
631 return i
632 raise RuntimeError("Vout not found for address: txid=%s, addr=%s" % (txid, addr))
633+
634+def modinv(a, n):
635+ """Compute the modular inverse of a modulo n
636+
637+ See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers.
pow(a, n-2, n)
87+ """Remove a byte array from the set."""
88+ self.denominator = (self.denominator * data_to_num3072(data)) % self.MODULUS
89+
90+ def digest(self):
91+ """Extract the final hash. Does not modify this object."""
92+ # TODO: With Python 3.8 modinv can be replaced with pow(a, -1, n)
modinv, the helper function might be a better place to put this TODO. The helper function is useful anyway, because modinv is more readable than pow(a, -1, n).
634+def modinv(a, n):
635+ """Compute the modular inverse of a modulo n using the extended Euclidean
636+ Algorithm. See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers.
637+ """
638+ # TODO: This does not use Python's own modular inverse pow(a, n-2, n) since
639+ # that uses Fermat's little theorem which is significantly slower. However,
“… uses Fermat’s little theorem which is significantly slower” doesn’t really make sense. Fermat’s little theorem is that a^p = a (mod p). It’s not an algorithm for calculating powers.
I’d suggest just removing this TODO entirely.
// TODO: change to pow(a, -1, n) should be kept though (because it’s more readable)
std::span or std::optional), the same should be done for Python functions in the future. No need to keep the codebase larger than necessary. “Now that it’s implemented, it’s implemented.” doesn’t really sound like a convincing argument to me.
6+from .util import (
7+ assert_equal,
8+ modinv,
9+)
10+
11+import hashlib
pip install pycodestyle) and black (pip install black), not necessarily to follow blindly but they do provide helpful suggestions.
99+ muhash.insert([0]*32)
100+ muhash.insert([1] + [0]*31)
101+ muhash.remove([2] + [0]*31)
102+ finalized = muhash.digest()
103+ # This mirrors the result in the C++ MuHash3072 unit test
104+ assert_equal(finalized[::-1].hex(), "a44e16d5e34d259b349af21c06e65d653915d2e208e4e03f389af750dc0bfdc3")
self.assertEqual to our own version here.
11+def rot32(v, bits):
12+ """Rotate the 32-bit value v left by bits bits."""
13+ bits %= 32 # Make sure the term below does not throw an exception
14+ return ((v << bits) & 0xffffffff) | (v >> (32 - bits))
15+
16+def chacha20_doubleround(s):
