1  pragma solidity >=0.5.0 <0.7.0;
 2  
 3  /**
 4   * @author Ricardo Guilherme Schmidt (Status Research & Development GmbH)
 5   * @notice based on https://github.com/ethereum/eth2.0-specs/blob/dev/ssz/merkle-proofs.md#merkle-multiproofs but without generalized indexes
 6   */
 7  library MerkleMultiProof {
 8  
 9     /**
10       * @notice Calculates a merkle root using multiple leafs at same time
11       * @param leafs out of order sequence of leafs and it's siblings
12       * @param proofs out of order sequence of parent proofs
13       * @param proofFlag flags for using or not proofs while hashing against hashes.
14       * @return merkle root of tree
15       */
16      function calculateMultiMerkleRoot(
17          bytes32[] memory leafs,
18          bytes32[] memory proofs,
19          bool[] memory proofFlag
20      )
21          internal
22          pure
23          returns (bytes32 merkleRoot)
24      {
25          uint256 leafsLen = leafs.length;
26          uint256 totalHashes = proofFlag.length;
27          bytes32[] memory hashes = new bytes32[](totalHashes);
28          uint leafPos = 0;
29          uint hashPos = 0;
30          uint proofPos = 0;
31          for(uint256 i = 0; i < totalHashes; i++){
32              hashes[i] = hashPair(
33                  proofFlag[i] ? (leafPos < leafsLen ? leafs[leafPos++] : hashes[hashPos++]) : proofs[proofPos++],
34                  leafPos < leafsLen ? leafs[leafPos++] : hashes[hashPos++]
35              );
36          }
37  
38          return hashes[totalHashes-1];
39      }
40  
41      function hashPair(bytes32 a, bytes32 b) private pure returns(bytes32){
42          return a < b ? hash_node(a, b) : hash_node(b, a);
43      }
44  
45      function hash_node(bytes32 left, bytes32 right)
46          private pure
47          returns (bytes32 hash)
48      {
49          assembly {
50              mstore(0x00, left)
51              mstore(0x20, right)
52              hash := keccak256(0x00, 0x40)
53          }
54          return hash;
55      }
56  
57      /**
58       * @notice Check validity of multimerkle proof
59       * @param root merkle root
60       * @param leafs out of order sequence of leafs and it's siblings
61       * @param proofs out of order sequence of parent proofs
62       * @param proofFlag flags for using or not proofs while hashing against hashes.
63       */
64      function verifyMultiProof(
65          bytes32 root,
66          bytes32[] memory leafs,
67          bytes32[] memory proofs,
68          bool[] memory proofFlag
69      )
70          internal
71          pure
72          returns (bool)
73      {
74          return calculateMultiMerkleRoot(leafs, proofs, proofFlag) == root;
75      }
76  
77  }