diff options
author | Wladimir J. van der Laan <laanwj@protonmail.com> | 2020-09-01 16:46:53 +0200 |
---|---|---|
committer | Wladimir J. van der Laan <laanwj@protonmail.com> | 2020-09-01 17:12:20 +0200 |
commit | 48c1083632687a42ac603d4f241e70616a1d3815 (patch) | |
tree | dcbc7b6b439aa4bdd64a1977ebbff6a942d5e868 /test/functional/test_framework/util.py | |
parent | bab4cce1b0eedc1a51692aaf83ba54dd0a9d17e6 (diff) | |
parent | 36ec9801a4edb9663ef9ce9ad298233766b903e8 (diff) | |
download | bitcoin-48c1083632687a42ac603d4f241e70616a1d3815.tar.xz |
Merge #19105: Add Muhash3072 implementation in Python
36ec9801a4edb9663ef9ce9ad298233766b903e8 test: Add chacha20 test vectors in muhash (Fabian Jahr)
0e2b400fea890e769b75da5b55fa1902fd9f9851 test: Add basic Python/C++ Muhash implementation parity unit test (Fabian Jahr)
b85543cb7361d6ba27c0eeca756eec9fd5395b36 test: Add Python MuHash3072 implementation to test framework (Pieter Wuille)
ab30cece0e84a8b917cb9a219c2466574362f300 test: Move modinv to util and add unit test (Fabian Jahr)
Pull request description:
This is the second in a [series of pull requests](https://github.com/bitcoin/bitcoin/pull/18000) 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.
ACKs for top commit:
jnewbery:
utACK 36ec9801a
laanwj:
Code review ACK 36ec9801a4edb9663ef9ce9ad298233766b903e8
Tree-SHA512: a3519c6e11031174f1ae71ecd8bcc7f3be42d7fc9c84c77f2fbea7cfc5ad54fcbe10b55116ad8d9a52ac5d675640eefed3bf260c58a02f2bf3bc0d8ec208baa6
Diffstat (limited to 'test/functional/test_framework/util.py')
-rw-r--r-- | test/functional/test_framework/util.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/test/functional/test_framework/util.py b/test/functional/test_framework/util.py index cfc4ee65d4..b9c7e89ac8 100644 --- a/test/functional/test_framework/util.py +++ b/test/functional/test_framework/util.py @@ -15,6 +15,7 @@ import os import random import re import time +import unittest from . import coverage from .authproxy import AuthServiceProxy, JSONRPCException @@ -625,3 +626,33 @@ def find_vout_for_address(node, txid, addr): if any([addr == a for a in tx["vout"][i]["scriptPubKey"]["addresses"]]): return i raise RuntimeError("Vout not found for address: txid=%s, addr=%s" % (txid, addr)) + +def modinv(a, n): + """Compute the modular inverse of a modulo n using the extended Euclidean + Algorithm. See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers. + """ + # TODO: Change to pow(a, -1, n) available in Python 3.8 + t1, t2 = 0, 1 + r1, r2 = n, a + while r2 != 0: + q = r1 // r2 + t1, t2 = t2, t1 - q * t2 + r1, r2 = r2, r1 - q * r2 + if r1 > 1: + return None + if t1 < 0: + t1 += n + return t1 + +class TestFrameworkUtil(unittest.TestCase): + def test_modinv(self): + test_vectors = [ + [7, 11], + [11, 29], + [90, 13], + [1891, 3797], + [6003722857, 77695236973], + ] + + for a, n in test_vectors: + self.assertEqual(modinv(a, n), pow(a, n-2, n)) |