背景
在上一篇文章"Solidity合约中签名验证的一点实践"中提到过，白名单机制一般有两种，除了签名验证的方式外，就是本文讲述的Merkle Root验证的方式。
主要做法是在服务端对白名单地址列表整体构建Merkle树，计算出树的root hash，合约只需存储这个Merkle的根哈希值就可以了。由于Merkle tree的构建，不需要任何私钥，所以安全性有很大提升，目前大多数新项目都会采用这个方法。
整体交互流程和签名验证比较相似，大致为：
- 后端预先收集所有的白名单地址，构建出完整的Merkle树
- 用户在前端网页操作发起pre mint时，弹出信息提示用户对该请求进行签名
请求发到后端，后端校验签名后，查询地址是否在白名单列表中。 - 如果确实存在白名单中，则从Merkle树查询该地址对应的Merkle proof列表，并返回给前端
- 前端调用钱包，把后端返回的proof列表作为参数传给合约pre mint方法
- 合约通过该地址和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 root
return computedHash == root;
}
在这里我们可以看到传参分别是proof的byte32数组，root的hash值，以及leaf(实际就是用户地址)。这个方法中，通过leaf和对应Merkle节点的hash值，循环计算出根root哈希值，如果与传参root相同则验证通过。
其中需要注意的是
- 每次计算下一个hash时，都需要先比较computedHash与proofElement的大小，较小的在拼接时放在前面。由于两者都是bytes32的数据类型，而solidity中byte是无符号的，所以在服务端务必需要用相同规则生成这个merkle树，这样才能满足合约的校验方法。
- 如果节点总数为奇数，那么最后一个节点，需要和自身拼接后进行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 proof
for (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 odd
if(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;
}
@Override
public 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));
}
}
其中需要注意的有：
- 原本是准备用ByteBuffer保存字节数组byte[]，因为ByteBuffer本身有compareTo和equals两个方法，可以比较方便实现整体逻辑。但是java的byte是有符号类型，范围是-128-127，所以为了和solidity表现一致，compareTo是没办法使用的，就自行实现了unsignedBytesCompare来判断。
- 由于solidity中最后proof生成的是root哈希，所以在服务端构建proof列表(getProof方法)的逻辑中，要把root节点排除。
- getProof方法的第二个入参intIndex，如果为空null，则表示该数据(第一个参数leaf)在所有数据中是不重复的；如果不为空，则表示该数据有重复的，intIndex需要给出该数据在列表中的准确下标。
优势
通过上文分析，可以看到服务端是不需要保存任何隐私信息的，所以安全性得到了很大的保障。数据量不大时（白名单场景），构建proof的速度，一般比签名的方式更快
劣势
- 验证某个值是否存在于某个数据列表中时，可以使用本文描述的merkle root方法，但是如果需要实现一些自定义的业务逻辑，则还是需要上一篇的签名方式。
- 因为整个merkle树是保存在内存中，如果数据量特别大，整体性能会下降。在本文的getProof中查找某个leaf的下标，是通过循环的方式，效率较低，如果预计数据量很大的前提下，可以在构建的时候就预先把数据排好序，在getProof中使用二分法查找leaf的下标。
参考
OpenZeppelin MerkleProof
java将byte转为无符号字节——解决java没有unsigned byte问题
How to convert an address to bytes in Solidity?