Fix MMR peak bagging, add tests cases, rebased (Snowfork#418)

* update peak bagging (cherry picked from commit 1ef8661) * tests: add MMR fixture data (cherry picked from commit 4a618d9) * test: add MMR fixture data with 15 leaves (cherry picked from commit 0a2d583) * chore: add hardhat * fix: mmr verification * tests: fix remaining MMR verification tests * fix: duplicate declaration * tests: skip failing verification test * refactor: remove unnecessary variable from MMR verification * chore: remove commented test * chore: remove submodules Co-authored-by: denalimarsh <denalimarsh@gmail.com>
longlonghash · Jun 7, 2021 · 84561dc · 84561dc
1 parent fb5362c
commit 84561dc
Show file tree

Hide file tree

Showing 11 changed files with 409 additions and 73 deletions.
diff --git a/ethereum/contracts/MMRVerification.sol b/ethereum/contracts/MMRVerification.sol
@@ -15,6 +15,7 @@ pragma solidity ^0.7.0;
  *
  *      General definitions:
  *      - Height:         the height of the tree.
+ *      - Width:          the number of leaves in the tree.
  *      - Size:           the number of nodes in the tree.
  *      - Nodes:          an item in the tree. A node is a leaf or a parent. Nodes' positions are ordered from 1
  *                        to size in the order that they were added to the tree.
@@ -67,26 +68,28 @@ contract MMRVerification {
             return true;
         }
 
-        // Calculate the index of our leaf's mountain peak
-        uint256 targetPeakIndex;
+        // Calculate the position of our leaf's mountain peak
+        uint256 targetPeakPos;
         uint256 numLeftPeaks;
-        uint256[] memory peakIndexes = getPeakIndexes(leafCount);
-        for (uint256 i = 0; i < peakIndexes.length; i++) {
-            if (peakIndexes[i] >= leafPos) {
-                targetPeakIndex = peakIndexes[i];
+        uint256[] memory peakPositions = getPeakPositions(leafCount);
+        for (uint256 i = 0; i < peakPositions.length; i++) {
+            if (peakPositions[i] >= leafPos) {
+                targetPeakPos = peakPositions[i];
                 break;
             }
-            numLeftPeaks = numLeftPeaks + 1;
+            numLeftPeaks++;
         }
 
         // Calculate our leaf's mountain peak hash
         bytes32 mountainHash = calculatePeakRoot(
-            numLeftPeaks, leafNodeHash, leafPos, targetPeakIndex, proofItems
+            numLeftPeaks, leafNodeHash, leafPos, targetPeakPos, proofItems
         );
 
-        // All right peaks are rolled up into one hash. If there are any, bag them.
+        // Bag peaks
         bytes32 bagger = mountainHash;
-        if(targetPeakIndex > leafPos) {
+
+        // All right peaks are rolled up into one hash. If there are any, bag them.
+        if (targetPeakPos < peakPositions[peakPositions.length-1]) {
             bagger = keccak256(abi.encodePacked(proofItems[proofItems.length-1], bagger));
         }
 
@@ -205,25 +208,24 @@ contract MMRVerification {
     }
 
     /**
-     * @dev It returns all peaks of the smallest merkle mountain range tree which includes
-     *      the given index(size)
+     * @dev It returns positions of all peaks
      */
-    function getPeakIndexes(uint256 width)
+    function getPeakPositions(uint256 width)
         public
         pure
-        returns (uint256[] memory peakIndexes)
+        returns (uint256[] memory peakPositions)
     {
-        peakIndexes = new uint256[](numOfPeaks(width));
+        peakPositions = new uint256[](numOfPeaks(width));
         uint256 count;
         uint256 size;
         for (uint256 i = 255; i > 0; i--) {
             if (width & (1 << (i - 1)) != 0) {
                 // peak exists
                 size = size + (1 << i) - 1;
-                peakIndexes[count++] = size;
+                peakPositions[count++] = size;
             }
         }
-        require(count == peakIndexes.length, "Invalid bit calculation");
+        require(count == peakPositions.length, "Invalid bit calculation");
     }
 
     /**

diff --git a/ethereum/contracts/utils/MerkleProof.sol b/ethereum/contracts/utils/MerkleProof.sol
@@ -9,7 +9,7 @@ library MerkleProof {
      * @param leaf the leaf which needs to be proven
      * @param pos the position of the leaf, index starting with 0
      * @param width the width or number of leaves in the tree
-     * @param proof the array of proofs to help verify the leafs membership, ordered from leaf to root
+     * @param proof the array of proofs to help verify the leaf's membership, ordered from leaf to root
      * @return a boolean value representing the success or failure of the operation
      */
     function verifyMerkleLeafAtPosition(

diff --git a/ethereum/package.json b/ethereum/package.json
@@ -36,7 +36,7 @@
     "@nomiclabs/hardhat-truffle5": "^2.0.0",
     "@nomiclabs/hardhat-web3": "^2.0.0",
     "hardhat": "^2.3.0",
-    "ts-node": "^9.1.1",
-    "typescript": "^4.2.4"
+    "ts-node": "^10.0.0",
+    "typescript": "^4.3.2"
   }
 }
diff --git a/ethereum/test/fixtures/mmr-fixture-data-15-leaves.json b/ethereum/test/fixtures/mmr-fixture-data-15-leaves.json
@@ -0,0 +1,171 @@
+{
+    "leaves": [
+        "0x4320435e8c3318562dba60116bdbcc0b82ffcecb9bb39aae3300cfda3ad0b8b0",
+        "0xad4cbc033833612ccd4626d5f023b9dfc50a35e838514dd1f3c86f8506728705",
+        "0x9ba3bd51dcd2547a0155cf13411beeed4e2b640163bbea02806984f3fcbf822e",
+        "0x1b14c1dc7d3e4def11acdf31be0584f4b85c3673f1ff72a3af467b69a3b0d9d0",
+        "0x3b031d22e24f1126c8f7d2f394b663f9b960ed7abbedb7152e17ce16112656d0",
+        "0x8ed25570209d8f753d02df07c1884ddb36a3d9d4770e4608b188322151c657fe",
+        "0x611c2174c6164952a66d985cfe1ec1a623794393e3acff96b136d198f37a648c",
+        "0x1e959bd2b05d662f179a714fbf58928730380ad8579a966a9314c8e13b735b13",
+        "0x1c69edb31a1f805991e8e0c27d9c4f5f7fbb047c3313385fd9f4088d60d3d12b",
+        "0x0a4098f56c2e74557cf95f4e9bdc32e7445dd3c7458766c807cd6b54b89e8b38",
+        "0x79501646d325333e636b557abefdfb6fa688012eef0b57bd0b93ef368ff86833",
+        "0x251054c04fcdeca1058dd511274b5eeb22c04b76a3c80f92a989cec535abbd5e",
+        "0x9b2645185bbf36ecfd425c4f99596107d78d160cea01b428be0b079ec8bf2a85",
+        "0x9a9ca4381b27601fe46fe517eb2eedffd8b14d7140cb10fec111337968c0dd28",
+        "0xc43faffd065ac4fc5bc432ad45c13de341b233dcc55afe99ac05eef2fbb8a583"
+    ],
+    "rootHash": "0x3e81e73a77ddf45c0252bba8d1195d1076003d8387df373a46a3a559bc06acca",
+    "proofs": [
+        {
+            "leafIndex": 0,
+            "leafCount": 15,
+            "items": [
+                "0xad4cbc033833612ccd4626d5f023b9dfc50a35e838514dd1f3c86f8506728705",
+                "0xcb24f4614ad5b2a5430344c99545b421d9af83c46fd632d70a332200884b4d46",
+                "0x441bf63abc7cf9b9e82eb57b8111c883d50ae468d9fd7f301e12269fc0fa1e75",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 1,
+            "leafCount": 15,
+            "items": [
+                "0x4320435e8c3318562dba60116bdbcc0b82ffcecb9bb39aae3300cfda3ad0b8b0",
+                "0xcb24f4614ad5b2a5430344c99545b421d9af83c46fd632d70a332200884b4d46",
+                "0x441bf63abc7cf9b9e82eb57b8111c883d50ae468d9fd7f301e12269fc0fa1e75",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 2,
+            "leafCount": 15,
+            "items": [
+                "0x1b14c1dc7d3e4def11acdf31be0584f4b85c3673f1ff72a3af467b69a3b0d9d0",
+                "0x672c04a9cd05a644789d769daa552d35d8de7c33129f8a7cbf49e595234c4854",
+                "0x441bf63abc7cf9b9e82eb57b8111c883d50ae468d9fd7f301e12269fc0fa1e75",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 3,
+            "leafCount": 15,
+            "items": [
+                "0x9ba3bd51dcd2547a0155cf13411beeed4e2b640163bbea02806984f3fcbf822e",
+                "0x672c04a9cd05a644789d769daa552d35d8de7c33129f8a7cbf49e595234c4854",
+                "0x441bf63abc7cf9b9e82eb57b8111c883d50ae468d9fd7f301e12269fc0fa1e75",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 4,
+            "leafCount": 15,
+            "items": [
+                "0x8ed25570209d8f753d02df07c1884ddb36a3d9d4770e4608b188322151c657fe",
+                "0x421865424d009fee681cc1e439d9bd4cce0a6f3e79cce0165830515c644d95d4",
+                "0xae88a0825da50e953e7a359c55fe13c8015e48d03d301b8bdfc9193874da9252",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 5,
+            "leafCount": 15,
+            "items": [
+                "0x3b031d22e24f1126c8f7d2f394b663f9b960ed7abbedb7152e17ce16112656d0",
+                "0x421865424d009fee681cc1e439d9bd4cce0a6f3e79cce0165830515c644d95d4",
+                "0xae88a0825da50e953e7a359c55fe13c8015e48d03d301b8bdfc9193874da9252",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 6,
+            "leafCount": 15,
+            "items": [
+                "0x1e959bd2b05d662f179a714fbf58928730380ad8579a966a9314c8e13b735b13",
+                "0x7e4316ae2ebf7c3b6821cb3a46ca8b7a4f9351a9b40fcf014bb0a4fd8e8f29da",
+                "0xae88a0825da50e953e7a359c55fe13c8015e48d03d301b8bdfc9193874da9252",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 7,
+            "leafCount": 15,
+            "items": [
+                "0x611c2174c6164952a66d985cfe1ec1a623794393e3acff96b136d198f37a648c",
+                "0x7e4316ae2ebf7c3b6821cb3a46ca8b7a4f9351a9b40fcf014bb0a4fd8e8f29da",
+                "0xae88a0825da50e953e7a359c55fe13c8015e48d03d301b8bdfc9193874da9252",
+                "0xde783edd9fe65db4ce28c56687da424218086b4948185bdd9f685a42506e3ba2"
+            ]
+        },
+        {
+            "leafIndex": 8,
+            "leafCount": 15,
+            "items": [
+                "0x73d1bf5a0b1329cd526fba68bb89504258fec5a2282001167fd51c89f7ef73d3",
+                "0x0a4098f56c2e74557cf95f4e9bdc32e7445dd3c7458766c807cd6b54b89e8b38",
+                "0x7d1f24a6c60769cc6bdc9fc123848d36ef2c6c48e84d9dd464d153cbb0e7ae76",
+                "0x24a44d3d08fbb13a1902e9fa3995456e9a141e0960a2f59725e65a37d474f2c0"
+            ]
+        },
+        {
+            "leafIndex": 9,
+            "leafCount": 15,
+            "items": [
+                "0x73d1bf5a0b1329cd526fba68bb89504258fec5a2282001167fd51c89f7ef73d3",
+                "0x1c69edb31a1f805991e8e0c27d9c4f5f7fbb047c3313385fd9f4088d60d3d12b",
+                "0x7d1f24a6c60769cc6bdc9fc123848d36ef2c6c48e84d9dd464d153cbb0e7ae76",
+                "0x24a44d3d08fbb13a1902e9fa3995456e9a141e0960a2f59725e65a37d474f2c0"
+            ]
+        },
+        {
+            "leafIndex": 10,
+            "leafCount": 15,
+            "items": [
+                "0x73d1bf5a0b1329cd526fba68bb89504258fec5a2282001167fd51c89f7ef73d3",
+                "0x251054c04fcdeca1058dd511274b5eeb22c04b76a3c80f92a989cec535abbd5e",
+                "0x2c6280fdcaf131531fe103e0e7353a77440333733c68effa4d3c49413c00b55f",
+                "0x24a44d3d08fbb13a1902e9fa3995456e9a141e0960a2f59725e65a37d474f2c0"
+            ]
+        },
+        {
+            "leafIndex": 11,
+            "leafCount": 15,
+            "items": [
+                "0x73d1bf5a0b1329cd526fba68bb89504258fec5a2282001167fd51c89f7ef73d3",
+                "0x79501646d325333e636b557abefdfb6fa688012eef0b57bd0b93ef368ff86833",
+                "0x2c6280fdcaf131531fe103e0e7353a77440333733c68effa4d3c49413c00b55f",
+                "0x24a44d3d08fbb13a1902e9fa3995456e9a141e0960a2f59725e65a37d474f2c0"
+            ]
+        },
+        {
+            "leafIndex": 12,
+            "leafCount": 15,
+            "items": [
+                "0x73d1bf5a0b1329cd526fba68bb89504258fec5a2282001167fd51c89f7ef73d3",
+                "0xf323ac1a7f56de5f40ed8df3e97af74eec0ee9d72883679e49122ffad2ffd03b",
+                "0x9a9ca4381b27601fe46fe517eb2eedffd8b14d7140cb10fec111337968c0dd28",
+                "0xc43faffd065ac4fc5bc432ad45c13de341b233dcc55afe99ac05eef2fbb8a583"
+            ]
+        },
+        {
+            "leafIndex": 13,
+            "leafCount": 15,
+            "items": [
+                "0x73d1bf5a0b1329cd526fba68bb89504258fec5a2282001167fd51c89f7ef73d3",
+                "0xf323ac1a7f56de5f40ed8df3e97af74eec0ee9d72883679e49122ffad2ffd03b",
+                "0x9b2645185bbf36ecfd425c4f99596107d78d160cea01b428be0b079ec8bf2a85",
+                "0xc43faffd065ac4fc5bc432ad45c13de341b233dcc55afe99ac05eef2fbb8a583"
+            ]
+        },
+        {
+            "leafIndex": 14,
+            "leafCount": 15,
+            "items": [
+                "0x73d1bf5a0b1329cd526fba68bb89504258fec5a2282001167fd51c89f7ef73d3",
+                "0xf323ac1a7f56de5f40ed8df3e97af74eec0ee9d72883679e49122ffad2ffd03b",
+                "0xa0d0a78fe68bd0af051c24c6f0ddd219594b582fa3147570b8fd60cf1914efb4"
+            ]
+        }
+    ]
+}
diff --git a/ethereum/test/fixtures/mmr-fixture-data-7-leaves.json b/ethereum/test/fixtures/mmr-fixture-data-7-leaves.json
@@ -0,0 +1,76 @@
+{
+    "leaves": [
+        "0x4320435e8c3318562dba60116bdbcc0b82ffcecb9bb39aae3300cfda3ad0b8b0",
+        "0xad4cbc033833612ccd4626d5f023b9dfc50a35e838514dd1f3c86f8506728705",
+        "0x9ba3bd51dcd2547a0155cf13411beeed4e2b640163bbea02806984f3fcbf822e",
+        "0x1b14c1dc7d3e4def11acdf31be0584f4b85c3673f1ff72a3af467b69a3b0d9d0",
+        "0x3b031d22e24f1126c8f7d2f394b663f9b960ed7abbedb7152e17ce16112656d0",
+        "0x8ed25570209d8f753d02df07c1884ddb36a3d9d4770e4608b188322151c657fe",
+        "0x611c2174c6164952a66d985cfe1ec1a623794393e3acff96b136d198f37a648c"
+    ],
+    "rootHash": "0xe45e25259f7930626431347fa4dd9aae7ac83b4966126d425ca70ab343709d2c",
+    "proofs": [
+        {
+            "leafIndex": 0,
+            "leafCount": 7,
+            "items": [
+                "0xad4cbc033833612ccd4626d5f023b9dfc50a35e838514dd1f3c86f8506728705",
+                "0xcb24f4614ad5b2a5430344c99545b421d9af83c46fd632d70a332200884b4d46",
+                "0xdca421199bdcc55bb773c6b6967e8d16675de69062b52285ca63685241fdf626"
+            ]
+        },
+        {
+            "leafIndex": 1,
+            "leafCount": 7,
+            "items": [
+                "0x4320435e8c3318562dba60116bdbcc0b82ffcecb9bb39aae3300cfda3ad0b8b0",
+                "0xcb24f4614ad5b2a5430344c99545b421d9af83c46fd632d70a332200884b4d46",
+                "0xdca421199bdcc55bb773c6b6967e8d16675de69062b52285ca63685241fdf626"
+            ]
+        },
+        {
+            "leafIndex": 2,
+            "leafCount": 7,
+            "items": [
+                "0x1b14c1dc7d3e4def11acdf31be0584f4b85c3673f1ff72a3af467b69a3b0d9d0",
+                "0x672c04a9cd05a644789d769daa552d35d8de7c33129f8a7cbf49e595234c4854",
+                "0xdca421199bdcc55bb773c6b6967e8d16675de69062b52285ca63685241fdf626"
+            ]
+        },
+        {
+            "leafIndex": 3,
+            "leafCount": 7,
+            "items": [
+                "0x9ba3bd51dcd2547a0155cf13411beeed4e2b640163bbea02806984f3fcbf822e",
+                "0x672c04a9cd05a644789d769daa552d35d8de7c33129f8a7cbf49e595234c4854",
+                "0xdca421199bdcc55bb773c6b6967e8d16675de69062b52285ca63685241fdf626"
+            ]
+        },
+        {
+            "leafIndex": 4,
+            "leafCount": 7,
+            "items": [
+                "0xae88a0825da50e953e7a359c55fe13c8015e48d03d301b8bdfc9193874da9252",
+                "0x8ed25570209d8f753d02df07c1884ddb36a3d9d4770e4608b188322151c657fe",
+                "0x611c2174c6164952a66d985cfe1ec1a623794393e3acff96b136d198f37a648c"
+            ]
+        },
+        {
+            "leafIndex": 5,
+            "leafCount": 7,
+            "items": [
+                "0xae88a0825da50e953e7a359c55fe13c8015e48d03d301b8bdfc9193874da9252",
+                "0x3b031d22e24f1126c8f7d2f394b663f9b960ed7abbedb7152e17ce16112656d0",
+                "0x611c2174c6164952a66d985cfe1ec1a623794393e3acff96b136d198f37a648c"
+            ]
+        },
+        {
+            "leafIndex": 6,
+            "leafCount": 7,
+            "items": [
+                "0xae88a0825da50e953e7a359c55fe13c8015e48d03d301b8bdfc9193874da9252",
+                "0x7e4316ae2ebf7c3b6821cb3a46ca8b7a4f9351a9b40fcf014bb0a4fd8e8f29da"
+            ]
+        }
+    ]
+}
diff --git a/ethereum/test/fixtures/mmr-fixture-data.json b/ethereum/test/fixtures/mmr-fixture-data.json
diff --git a/ethereum/test/helpers.js b/ethereum/test/helpers.js
@@ -52,10 +52,13 @@ const deployAppWithMockChannels = async (deployer, channels, appContract, ...app
   return app;
 }
 
-const deployLightClientBridge = async _ => {
+const deployLightClientBridge = async (validatorRoot, numOfValidators) => {
   await lazyInit();
   const mmrVerification = await MMRVerification.new();
   const blake2b = await Blake2b.new();
+  if (validatorRoot && numOfValidators != undefined) {
+    await validatorRegistry.update(validatorRoot, numOfValidators)
+  }
   const lightClientBridge = await LightClientBridge.new(
     validatorRegistry.address,
     mmrVerification.address,
@@ -102,6 +105,11 @@ const ChannelId = {
   Incentivized: 1,
 }
 
+const hexPrefix = /^(0x)/i
+
+const mergeKeccak256 = (left, right) =>
+  '0x' + keccakFromHexString('0x' + left.replace(hexPrefix, "") + right.replace(hexPrefix, ''), 256).toString('hex')
+
 module.exports = {
   deployAppWithMockChannels,
   deployLightClientBridge,
@@ -111,4 +119,5 @@ module.exports = {
   addressBytes,
   ChannelId,
   encodeLog,
+  mergeKeccak256,
 };