背景

在上一篇文章”Solidity合约中签名验证的一点实践”中提到过，白名单机制一般有两种，除了签名验证的方式外，就是本文讲述的Merkle Root验证的方式。
主要做法是在服务端对白名单地址列表整体构建Merkle树，计算出树的root hash，合约只需存储这个Merkle的根哈希值就可以了。由于Merkle tree的构建，不需要任何私钥，所以安全性有很大提升，目前大多数新项目都会采用这个方法。

整体交互流程和签名验证比较相似，大致为：

  1. 后端预先收集所有的白名单地址，构建出完整的Merkle树
  2. 用户在前端网页操作发起pre mint时，弹出信息提示用户对该请求进行签名
    请求发到后端，后端校验签名后，查询地址是否在白名单列表中。
  3. 如果确实存在白名单中，则从Merkle树查询该地址对应的Merkle proof列表，并返回给前端
  4. 前端调用钱包，把后端返回的proof列表作为参数传给合约pre mint方法
  5. 合约通过该地址和proof列表，计算出root hash，与合约中保存的root hash做比较，相同则通过校验，并且保存该地址到合约中，避免用户重复发起。

Merkle Tree


Merkle树在区块链中应用非常广泛，比如在比特币中就是用交易作为了叶子节点的数据节点，使得可以快速验证某一笔交易是否在区块中是否存在。概念参考: Merkle Tree与区块链
而在白名单场景中，叶子节点的数据节点就是一个一个的地址。

合约

同样，在第三方库OpenZeppelin中，已经实现(或者说定义)了根哈希验证的方法，用户的自定义合约里只有引入MerkleProof这个library即可。验证的源代码如下：

function verify(bytes32[] memory proof,bytes32 root,bytes32 leaf) internal pure returns (bool) {bytes32 computedHash = leaf;for (uint256 i = 0; i < proof.length; i++) {bytes32 proofElement = proof[i];if (computedHash <= proofElement) {// Hash(current computed hash + current element of the proof)computedHash = keccak256(abi.encodePacked(computedHash, proofElement));} else {// Hash(current element of the proof + current computed hash)computedHash = keccak256(abi.encodePacked(proofElement, computedHash));}}// Check if the computed hash (root) is equal to the provided rootreturn computedHash == root;}

在这里我们可以看到传参分别是proof的byte32数组，root的hash值，以及leaf(实际就是用户地址)。这个方法中，通过leaf和对应Merkle节点的hash值，循环计算出根root哈希值，如果与传参root相同则验证通过。
其中需要注意的是

  1. 每次计算下一个hash时，都需要先比较computedHash与proofElement的大小，较小的在拼接时放在前面。由于两者都是bytes32的数据类型，而solidity中byte是无符号的，所以在服务端务必需要用相同规则生成这个merkle树，这样才能满足合约的校验方法。
  2. 如果节点总数为奇数，那么最后一个节点，需要和自身拼接后进行hash

使用该library的合约示例代码如下，rootHash则为预先保存在合约里的根哈希值：

using MerkleProof for bytes32[];bytes32 public rootHash;function merkleVerify(bytes32[] memory proof) public view returns(bool){return proof.verify(rootHash,bytes32(uint256(uint160(msg.sender))));}

后端

根据语言的不同，后端工作量差别较大。
如果是nodejs，则有OpenZeppelin推荐的merkletreejs库，直接使用即可，操作十分简单。可参考OpenZeppelin官方测试用例

如果是其他语言，则需要寻找是否有现成的第三方库，目前构建Merkle树的库很多，但是加入了节点间排序的比较少，而且构造的proof列表往往不符合solidity验证的需求。因此本文模仿merkletreejs的核心逻辑，结合web3j库，用java实现了初始化构建、生成proof列表，验证proof 这三个功能：

import org.web3j.crypto.Hash;import org.web3j.utils.Numeric;import java.nio.ByteBuffer;import java.util.ArrayList;import java.util.List;import java.util.stream.Collectors;public class MerkleTree {private final List<byte[]> leaves;private final List<List<byte[]>> layers;public MerkleTree(List<String> leafList) {this.leaves = leafList.stream().map(key -> Hash.sha3(key.getBytes())).collect(Collectors.toList());this.layers = new ArrayList<>();processLeaves(this.leaves);}private byte[] getRoot() {if(this.layers.size() == 0){return new byte[]{};}return this.layers.get(this.layers.size()-1).get(0);}public String getHexRoot(){return Numeric.toHexString(getRoot());}public List<String> getHexProof(String leaf, Integer intIndex){return getProof(leaf.getBytes(), intIndex).stream().map(Numeric::toHexString).collect(Collectors.toList());}public List<byte[]> getProof(byte[] leaf, Integer intIndex){int index = -1;List<byte[]> proofList = new ArrayList<>();byte[] hashLeaf = Hash.sha3(leaf);ByteBuffer bytesLeaf = ByteBuffer.wrap(hashLeaf);if(intIndex == null){for (int i = 0; i < this.leaves.size(); i++) {ByteBuffer item = ByteBuffer.wrap(this.leaves.get(i));if(bytesLeaf.equals(item)){index = i;break;}}}else {index = intIndex;ByteBuffer itemBytes = ByteBuffer.wrap(this.leaves.get(intIndex));if(!bytesLeaf.equals(itemBytes)){System.out.printf("index not match%s-%s\n",itemBytes, bytesLeaf);return null;}}if(index <= -1){System.out.print("not found in leaves\n");return null;}//root node is not needed in prooffor (int i = 0; i < this.layers.size() - 1; i++) {List<byte[]> layer = this.layers.get(i);boolean isRightNode = index % 2 == 1;int pairIndex = isRightNode? index - 1 : (index == layer.size()-1 ? index: index + 1);if(pairIndex<layer.size()){proofList.add(layer.get(pairIndex));}index = index / 2;}return proofList;}private void processLeaves(List<byte[]> leafList){try {this.layers.add(leafList);List<byte[]> nodeList = leafList;while (nodeList.size()>1) {int layerIndex = this.layers.size();this.layers.add(new ArrayList<>());for (int i = 0; i < nodeList.size(); i += 2) {//if i is the last one, it means the nodeList amount is oddif(i + 1 == nodeList.size()){this.layers.get(layerIndex).add(nodeList.get(i));continue;}byte[] left = nodeList.get(i);byte[] right = (i + 1 == nodeList.size()) ? left : nodeList.get(i + 1);byte[] combine;if (unsignedBytesCompare(left, right) <= 0) {combine = combinedHash(left, right);} else {combine = combinedHash(right, left);}this.layers.get(layerIndex).add(combine);}nodeList = this.layers.get(layerIndex);}}catch (Exception e){System.out.println(e.getMessage());}}private byte[] combinedHash(byte[] left, byte[] right){byte[] combine = new byte[left.length + right.length];System.arraycopy(left, 0, combine, 0, left.length);System.arraycopy(right, 0, combine, left.length, right.length);return Hash.sha3(combine);}private int unsignedBytesCompare(byte[] left, byte[] right) throws Exception {if(left.length!=right.length){throw new Exception("length not match");}for (int i = 0; i < left.length; i++) {int unLeft = Byte.toUnsignedInt(left[i]);int unRight = Byte.toUnsignedInt(right[i]);int result = unLeft - unRight;if(result != 0){return result;}}return 0;}public boolean verify(List<byte[]> proof, byte[] root, byte[] leaf){byte[] computedHash = leaf;try {for (int i = 0; i < proof.size(); i++) {byte[] proofElement = proof.get(i);if (unsignedBytesCompare(computedHash, proofElement) <= 0) {computedHash = combinedHash(computedHash, proofElement);} else {computedHash = combinedHash(proofElement, computedHash);}}ByteBuffer cRoot = ByteBuffer.wrap(computedHash);ByteBuffer bRoot = ByteBuffer.wrap(root);return bRoot.equals(cRoot);}catch (Exception e){System.out.println(e.getMessage());}return false;}@Overridepublic String toString() {return "MerkleTree{" +"leaves=" + leaves +", layers=" + layers +'}';}public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("A");list.add("B");list.add("C");list.add("D");list.add("E");MerkleTree tree = new MerkleTree(list);byte[] root = tree.getRoot();System.out.println(Numeric.toHexString(root));byte[] leaf =Hash.sha3("A".getBytes());List<byte[]> proof =tree.getProof("A".getBytes(),null);System.out.println(tree.verify(proof, root, leaf));System.out.println(tree.getHexProof("A",null));}}

其中需要注意的有：

  1. 原本是准备用ByteBuffer保存字节数组byte[]，因为ByteBuffer本身有compareTo和equals两个方法，可以比较方便实现整体逻辑。但是java的byte是有符号类型，范围是-128-127，所以为了和solidity表现一致，compareTo是没办法使用的，就自行实现了unsignedBytesCompare来判断。
  2. 由于solidity中最后proof生成的是root哈希，所以在服务端构建proof列表(getProof方法)的逻辑中，要把root节点排除。
  3. getProof方法的第二个入参intIndex，如果为空null，则表示该数据(第一个参数leaf)在所有数据中是不重复的；如果不为空，则表示该数据有重复的，intIndex需要给出该数据在列表中的准确下标。

优势

通过上文分析，可以看到服务端是不需要保存任何隐私信息的，所以安全性得到了很大的保障。数据量不大时（白名单场景），构建proof的速度，一般比签名的方式更快

劣势

  1. 验证某个值是否存在于某个数据列表中时，可以使用本文描述的merkle root方法，但是如果需要实现一些自定义的业务逻辑，则还是需要上一篇的签名方式。
  2. 因为整个merkle树是保存在内存中，如果数据量特别大，整体性能会下降。在本文的getProof中查找某个leaf的下标，是通过循环的方式，效率较低，如果预计数据量很大的前提下，可以在构建的时候就预先把数据排好序，在getProof中使用二分法查找leaf的下标。

参考

OpenZeppelin MerkleProof
java将byte转为无符号字节——解决java没有unsigned byte问题
How to convert an address to bytes in Solidity?