clearmatics · AntoineRondelet · May 5, 2021 · Apr 29, 2021 · Apr 29, 2021 · Apr 29, 2021
diff --git a/client/test_contracts/test_mimc_contract.py b/client/test_contracts/test_mimc_contract.py
@@ -4,14 +4,19 @@
 
 from zeth.core.utils import get_contracts_dir
 from zeth.core.contracts import InstanceDescription
-from zeth.core.mimc import MiMC7, MiMC31
+from zeth.core.mimc import MiMCAltBN128, MiMCBLS12_377
 from zeth.cli.utils import get_eth_network, open_web3_from_network
 from os.path import join
 from unittest import TestCase
 from typing import Any
 
 CONTRACT_INSTANCE: Any = None
 
+"""
+Test data here matches that used in test_mimc.py, which is also used in the
+tests of mimc circuits.
+"""
+
 
 class TestMiMCContract(TestCase):
 
@@ -30,22 +35,22 @@ def setUpClass() -> None:
         global CONTRACT_INSTANCE  # pylint: disable=global-statement
         CONTRACT_INSTANCE = contract_instance_desc.instantiate(web3)
 
-    def test
8000
_mimc7(self) -> None:
+    def test_mimc_alt_bn128(self) -> None:
         # pylint: disable=line-too-long
         x = int(28948022309329048855892746252171976963317496166410141009864396001978282409983).to_bytes(32, 'big')  # noqa
         y = int(14220067918847996031108144435763672811050758065945364308986253046354060608451).to_bytes(32, 'big')  # noqa
         # pylint: enable=line-too-long
-        h = MiMC7().hash(x, y)
+        h = MiMCAltBN128().hash(x, y)
 
-        result = CONTRACT_INSTANCE.functions.testMimc7(x, y).call()
+        result = CONTRACT_INSTANCE.functions.testMimcAltBN128(x, y).call()
         self.assertEqual(h, result)
 
-    def test_mimc31(self) -> None:
+    def test_mimc_bls12_377(self) -> None:
         # pylint: disable=line-too-long
         x = int(28948022309329048855892746252171976963317496166410141009864396001978282409983).to_bytes(32, 'big')  # noqa
         y = int(14220067918847996031108144435763672811050758065945364308986253046354060608451).to_bytes(32, 'big')  # noqa
         # pylint: enable=line-too-long
-        h = MiMC31().hash(x, y)
+        h = MiMCBLS12_377().hash(x, y)
 
-        result = CONTRACT_INSTANCE.functions.testMimc31(x, y).call()
+        result = CONTRACT_INSTANCE.functions.testMimcBLS12_377(x, y).call()
         self.assertEqual(h, result)
diff --git a/client/tests/test_input_hasher.py b/client/tests/test_input_hasher.py
@@ -2,7 +2,7 @@
 #
 # SPDX-License-Identifier: LGPL-3.0+
 
-from zeth.core.mimc import MiMC7, MiMC31
+from zeth.core.mimc import MiMCAltBN128, MiMCBLS12_377
 from zeth.core.input_hasher import InputHasher
 from unittest import TestCase
 
@@ -13,7 +13,7 @@ class TestInputHasher(TestCase):
 
     def test_input_hasher_simple(self) -> None:
         # Some very simple cases
-        mimc = MiMC7()
+        mimc = MiMCAltBN128()
         input_hasher = InputHasher(mimc, 7)
         self.assertEqual(mimc.hash_int(7, 0), input_hasher.hash([]))
         self.assertEqual(
@@ -25,20 +25,20 @@ def test_input_hasher_simple(self) -> None:
                 2),
             input_hasher.hash([1, 2]))
 
-    def test_input_hasher_mimc7(self) -> None:
-        mimc = MiMC7()
+    def test_input_hasher_mimc_alt_bn128(self) -> None:
+        mimc = MiMCAltBN128()
         input_hasher = InputHasher(mimc)
         values = [x % mimc.prime for x in DUMMY_INPUT_VALUES]
         # pylint:disable=line-too-long
-        expect = 5568471640435576440988459485125198359192118312228711462978763973844457667180  # noqa
+        expect = 1147542777914688064255377945014225852776952826405497760158376896026758431650  # noqa
         # pylint:enable=line-too-long
         self.assertEqual(expect, input_hasher.hash(values))
 
-    def test_input_hasher_mimc31(self) -> None:
-        mimc = MiMC31()
+    def test_input_hasher_mimc_bls12_377(self) -> None:
+        mimc = MiMCBLS12_377()
         input_hasher = InputHasher(mimc)
         values = [x % mimc.prime for x in DUMMY_INPUT_VALUES]
         # pylint: disable=line-too-long
-        expect = 1029772481427643815119825324071277815354972734622711297984795198139876181749  # noqa
+        expect = 3481757288350338818975783012202519902801563645563026508811358096682731778741  # noqa
         # pylint: enable=line-too-long
         self.assertEqual(expect, input_hasher.hash(values))
diff --git a/client/tests/test_merkle_tree.py b/client/tests/test_merkle_tree.py
@@ -6,7 +6,7 @@
 from zeth.core.merkle_tree import MerkleTree, PersistentMerkleTree, ZERO_ENTRY, \
     compute_merkle_path
 from zeth.core.utils import extend_32bytes
-from zeth.core.mimc import MiMC7
+from zeth.core.mimc import MiMCAltBN128
 from os.path import exists, join
 from os import makedirs
 from shutil import rmtree
@@ -16,7 +16,7 @@
 MERKLE_TREE_TEST_DIR = "_merkle_tests"
 MERKLE_TREE_TEST_DEPTH = 4
 MERKLE_TREE_TEST_NUM_LEAVES = pow(2, MERKLE_TREE_TEST_DEPTH)
-MERKLE_TREE_HASH = MiMC7()
+MERKLE_TREE_HASH = MiMCAltBN128()
 TEST_VALUES = [
     extend_32bytes(i.to_bytes(1, 'big'))
     for i in range(1, MERKLE_TREE_TEST_NUM_LEAVES)]
@@ -43,7 +43,7 @@ def test_combine(self) -> None:
         right = self._test_vector_to_bytes32(
             15683951496311901749339509118960676303290224812129752890706581988986633412003)  # noqa
         expect = self._test_vector_to_bytes32(
-            16797922449555994684063104214233396200599693715764605878168345782964540311877)  # noqa
+            449619487941393604225985437455969025878050402333083242690002834641114429734)  # noqa
 
         result = MERKLE_TREE_HASH.hash(left, right)
         self.assertEqual(expect, result)
@@ -147,7 +147,7 @@ def _expected_empty(self) -> bytes:
         self.assertEqual(16, MERKLE_TREE_TEST_NUM_LEAVES)
         # Test vector generated by test_mimc.py
         return self._test_vector_to_bytes32(
-            1792447880902456454889084480864374954299744757125100424674028184042059183092)  # noqa
+            20048582095008167683805983195827846276103487741417695738966466927999203944276)  # noqa
 
     def _check_merkle_path(
             self, address: int, mkpath: List[str], mktree: MerkleTree) -> None:

diff --git a/client/tests/test_mimc.py b/client/tests/test_mimc.py
@@ -2,45 +2,49 @@
 #
 # SPDX-License-Identifier: LGPL-3.0+
 
-from zeth.core.mimc import MiMC7, MiMC31
+from zeth.core.mimc import MiMCAltBN128, MiMCBLS12_377
 from unittest import TestCase
 
 # pylint: disable=line-too-long
 
 
 class TestMiMC(TestCase):
 
-    def test_mimc7_round(self) -> None:
-        mimc = MiMC7("Clearmatics")
+    def test_mimc_alt_bn128_round(self) -> None:
+        mimc = MiMCAltBN128("Clearmatics")
         msg = 340282366920938463463374607431768211456
         key = 28948022309329048855892746252171976963317496166410141009864396001978282409983  # noqa
         round_const = 14220067918847996031108144435763672811050758065945364308986253046354060608451  # noqa
-        expect_result = 7970444205539657036866618419973693567765196138501849736587140180515018751924  # noqa
+        expect_result = 15194574649778181158537940501307832704788048781286507777438072456493095881604  # noqa
         self.assertEqual(expect_result, mimc.mimc_round(msg, key, round_const))
 
-    def test_mimc7(self) -> None:
-        left = 28948022309329048855892746252171976963317496166410141009864396001978282409983  # noqa
-        right = 14220067918847996031108144435763672811050758065945364308986253046354060608451  # noqa
-        expect_result = 14404914332179247771191118015445305957789480573634910846417052002923707343766  # noqa
-        result = MiMC7().hash(_int_to_bytes(left), _int_to_bytes(right))
-        self.assertEqual(_int_to_bytes(expect_result), result)
+    def test_mimc_alt_bn128_hash(self) -> None:
+        left = 340282366920938463463374607431768211456
+        right = 28948022309329048855892746252171976963317496166410141009864396001978282409983  # noqa
+        expect_result = 14599678357063082723814206975733222579132256174923645170354481857040188426666  # noqa
+        result = MiMCAltBN128().hash(_int_to_bytes(left), _int_to_bytes(right))
+        self.assertEqual(expect_result, _bytes_to_int(result))
 
-    def test_mimc31_round(self) -> None:
+    def test_mimc_bls12_377_round(self) -> None:
         msg = 340282366920938463463374607431768211456
         key = 3614637061043937583146271435827337369189798160947949526058695634226054692860  # noqa
         round_const = 5775606169419625606859319496982126279674858730791300481051019590436651369410  # noqa
-        expect_result = 5523634951166384704739554074217840169048851347397743343350526776025419511991  # noqa
+        expect_result = 706529233840138407487116494744828417642056684171152884149736992660816802274  # noqa
         self.assertEqual(
-            expect_result, MiMC31().mimc_round(msg, key, round_const))
+            expect_result, MiMCBLS12_377().mimc_round(msg, key, round_const))
 
-    def test_mimc31(self) -> None:
+    def test_mimc_bls12_377_hash(self) -> None:
         left = 3614637061043937583146271435827337369189798160947949526058695634226054692860  # noqa
         right = 5775606169419625606859319496982126279674858730791300481051019590436651369410  # noqa
-        expect_result = 7575204549404107478830739557698679330537656688050664462892741835534561279075  # noqa
-        result = MiMC31().hash(_int_to_bytes(left), _int_to_bytes(right))
-        self.assertEqual(_int_to_bytes(expect_result), result)
+        expect_result = 5803106354831571205534057512593837953191890709037390680911925249983717812220  # noqa
+        result = MiMCBLS12_377().hash(_int_to_bytes(left), _int_to_bytes(right))
+        self.assertEqual(expect_result, _bytes_to_int(result))
 
 
 # pylint: enable=line-too-long
 def _int_to_bytes(value: int) -> bytes:
     return value.to_bytes(32, byteorder='big')
+
+
+def _bytes_to_int(value: bytes) -> int:
+    return int.from_bytes(value, byteorder='big')
diff --git a/client/zeth/core/mimc.py b/client/zeth/core/mimc.py
@@ -76,44 +76,45 @@ def mimc_round(self, message: int, key: int, rc: int) -> int:
         pass
 
 
-class MiMC7(MiMCBase):
+class MiMC17Base(MiMCBase):
     """
-    MiMC specialized for Fr in ALT-BN128, in which the exponent is 7 and 91
-    rounds are used.
+    Implementation of MiMCBase with exponent 17
+    """
+    def mimc_round(self, message: int, key: int, rc: int) -> int:
+        # May not be optimal to operate on huge numbers (256 * e bits). For
+        # reference, the manual version is below:
+        #   a = (message + key + rc) % self.prime
+        #   a_2 = (a * a) % self.prime
+        #   a_4 = (a_2 * a_2) % self.prime
+        #   a_8 = (a_4 * a_4) % self.prime
+        #   a_16 = (a_8 * a_8) % self.prime
+        #   return (a_16 * a) % self.prime
+        return ((message + key + rc) ** 17) % self.prime
+
+
+class MiMCAltBN128(MiMC17Base):
+    """
+    MiMC specialized for Fr in ALT-BN128, using exponent 17 and 65 rounds. See
+    zeth specifications (Section 3.2) for details.
     """
     def __init__(self, seed_str: str = MIMC_MT_SEED):
-        MiMCBase.__init__(
-            self,
+        super().__init__(
             seed_str,
             21888242871839275222246405745257275088548364400416034343698204186575808495617,  # noqa
             # pylint: disable=line-too-long
-            91)
+            65)
 
-    def mimc_round(self, message: int, key: int, rc: int) -> int:
-        xored = (message + key + rc) % self.prime
-        return xored ** 7 % self.prime
 
-
-class MiMC31(MiMCBase):
+class MiMCBLS12_377(MiMC17Base):  # pylint: disable=invalid-name
     """
-    MiMC implementation using exponent of 31 and 51 rounds. Note that this is
-    suitable for BLS12-377, since 31=2^5-1, and 1 == gcd(31, r-1). See
-    [AGRRT16] for details.
+    MiMC specialized for Fr in BLS12-377, using exponent 17 and 62 rounds. See
+    zeth specifications (Section 3.2) for details.
     """
     def __init__(self, seed_str: str = MIMC_MT_SEED):
-        MiMCBase.__init__(
-            self,
+        super().__init__(
             seed_str,
             8444461749428370424248824938781546531375899335154063827935233455917409239041,  # noqa
-            51)
-
-    def mimc_round(self, message: int, key: int, rc: int) -> int:
-        a = (message + key + rc) % self.prime
-        a_2 = (a * a) % self.prime
-        a_4 = (a_2 * a_2) % self.prime
-        a_8 = (a_4 * a_4) % self.prime
-        a_16 = (a_8 * a_8) % self.prime
-        return (a_16 * a_8 * a_4 * a_2 * a) % self.prime
+            62)
 
 
 def get_tree_hash_for_pairing(pairing_name: str) -> ITreeHash:
@@ -122,9 +123,9 @@ def get_tree_hash_for_pairing(pairing_name: str) -> ITreeHash:
     the selection logic in `libzeth/circuits/circuit_types.hpp`.
     """
     if pairing_name == "alt-bn128":
-        return MiMC7()
+        return MiMCAltBN128()
     if pairing_name == "bls12-377":
-        return MiMC31()
+        return MiMCBLS12_377()
     raise Exception(f"no tree hash for pairing: {pairing_name}")
 
 

diff --git a/libzeth/circuits/circuit_types.hpp b/libzeth/circuits/circuit_types.hpp
@@ -28,22 +28,22 @@ template<typename FieldT> class tree_hash_selector
 {
 };
 
-// For alt-bn128, use MiMC7 with 91 rounds
+// For alt-bn128, use MiMC17 with 65 rounds.
 template<> class tree_hash_selector<libff::alt_bn128_Fr>
 {
 public:
     using tree_hash = MiMC_mp_gadget<
         libff::alt_bn128_Fr,
-        MiMC_permutation_gadget<libff::alt_bn128_Fr, 7, 91>>;
+        MiMC_permutation_gadget<libff::alt_bn128_Fr, 17, 65>>;
 };
 
-// For bls12-377, use MiMC31 with 51 rounds
+// For bls12-377, use MiMC17 with 62 rounds
 template<> class tree_hash_selector<libff::bls12_377_Fr>
 {
 public:
     using tree_hash = MiMC_mp_gadget<
         libff::bls12_377_Fr,
-        MiMC_permutation_gadget<libff::bls12_377_Fr, 31, 51>>;
+        MiMC_permutation_gadget<libff::bls12_377_Fr, 17, 62>>;
 };
 
 // Hash function to be used in the Merkle Tree

diff --git a/libzeth/circuits/mimc/mimc.hpp b/libzeth/circuits/mimc/mimc.hpp