Skip to content

Instantly share code, notes, and snippets.

@3esmit
Last active January 24, 2020 17:22
Show Gist options
  • Save 3esmit/101b59a0f54f24d0810ba7d3744db875 to your computer and use it in GitHub Desktop.
Save 3esmit/101b59a0f54f24d0810ba7d3744db875 to your computer and use it in GitHub Desktop.
pragma solidity >=0.5.0 <0.7.0;
/**
* @author Ricardo Guilherme Schmidt (Status Research & Development GmbH)
* @notice simplified multi proofs
*/
library MerkleMultiProof {
/**
* @notice Calculates a merkle root using multiple leafs at same time
* @param leafs out of order sequence of leafs and it's siblings
* @param proofs out of order sequence of parent proofs
* @param useProof indexing for using or not proofs while hashing against hashes.
* @return merkle root of tree
*/
function calculateMultiMerkleRoot(
bytes32[] memory leafs,
bytes32[] memory proofs,
bool[] memory useProof
)
internal
pure
returns (bytes32 merkleRoot)
{
uint256 leafsLen = leafs.length;
uint256 proofsLen = proofs.length;
uint256 totalHashes = proofsLen + leafsLen - 1;
uint256 totalIndexes = totalHashes + proofsLen - 1;
bytes32[] memory hashes = new bytes32[](totalHashes);
uint256 hashCount = 0;
//calculate fixed hashing pairs // leaf+sibling
for(uint256 i = 0; i < leafsLen; i += 2){
hashes[hashCount] = keccak256(abi.encodePacked(leafs[i],leafs[i+1]));
hashCount++;
}
//calculate dynamic hashing pairs // hashes+proofs & hashes+hashes
uint hashPos = 0;
uint proofPos = 0;
for(uint256 i = 0; proofPos+hashPos < totalIndexes; i++){
hashes[hashCount] = hashPair(
proofPos < proofsLen && useProof[i] ? proofs[proofPos++] : hashes[hashPos++],
hashes[hashPos++]
);
hashCount++;
}
return hashes[totalHashes-1];
}
function hashPair(bytes32 a, bytes32 b) private pure returns(bytes32){
return keccak256(a < b ? abi.encodePacked(a, b) : abi.encodePacked(b, a));
}
/**
* @notice Check validity of multimerkle proof
* @param root merkle root
* @param leafs out of order sequence of leafs and it's siblings
* @param proofs out of order sequence of parent proofs
* @param useProof indexing for using or not proofs while hashing against hashes.
*/
function verifyMultiProof(
bytes32 root,
bytes32[] memory leafs,
bytes32[] memory proofs,
bool[] memory useProof
)
internal
pure
returns (bool)
{
return calculateMultiMerkleRoot(leafs, proofs, useProof) == root;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment