Alvan

Alvan

Smart contract developer in Shanghai

Aptos中实现merkle树验证

原理讲解:

由于区块链在存储/检索大量数据上成本过高,在一些情况下会采用用链下存储,链上验证的方法。例如如果要管理一个数万地址的白名单,使用merkle树不失为一种好方案。

img merkle树本质是一个满二叉树,它的叶子结点保存着原数据的hash值,非叶子结点存储的数据是左儿子节点和右儿子节点数据的拼接后求hash(排序后)。 如上图所示,Hash0=hash(Hash0_0+Hash0_1)TopHash=hash(Hash0+Hash1)Hash0 = hash(Hash0\_0 + Hash0\_1),Top Hash = hash( Hash0 + Hash1 )

详细介绍可见:https://mirror.xyz/qiwihui.eth/HRifb9gziR1UvVmRcMjDfDvQ9mq7o7FA6BNuCJMFT00

用法:

如果我们需要存储1W个地址作为白名单用户,那么全部存储和操作都在区块链上的成本明显有点太高了,我们可以利用merkle树的特性解决。步骤如下: 1.在链下使用1W个地址生成merkle树并存储。 2.并将根结点TopHashTopHash存入合约。 3.如果需要查询 L4 地址是否在白名单内,需要提供A地址本身和验证路径上的节点信息。例如需要验证L4在该树中,则需要提供 Hash1_0Hash 1\_0Hash0Hash 0. 4.在合约内验证 hash(Hash0+hash(Hash1_0+hash(L4)))==TopHashhash( Hash 0 + hash(Hash 1\_ 0 + hash( L4 ))) == TopHash ,即可判断 L4 是否在merkle树内了。

实现:

链下部分:

链下部分负责生成 merkle 树,存储 merkle 树,获取proof验证路径数据。

我们可以直接使用现成的 keccak256merkletreejs 库来管理merkle树,无论是存储,构建,生成验证路径,获取树根都有直接可用的方法供我们使用: 需要注意的只是要将数据结构匹配成aptos可以接受的形式

import keccak256 from "keccak256";
import MerkleTree from "merkletreejs";
export const NODE_URL = "https://fullnode.devnet.aptoslabs.com/v1";
export const FAUCET_URL = "https://faucet.devnet.aptoslabs.com";
export const privateKey = '0x.............';


let whitelistAddresses = [
    "0x36346bbcda6f9f74cf36cff31e00ac83c9d8a512a6564c9f93b00d249e3b2b45",
    "0x09d4ee382de0fa20f889ac6158273f29c81a1fec7385e8e26801db2e9e0c2f32",
    "0x09d4ee382de0fa20f889ac6158273f29c81a1fec7385e8e26801db2e9e0c2f32",
  ];

  let leafNodes = whitelistAddresses.map((address) => keccak256(address));
  let tree = new MerkleTree(leafNodes, keccak256, { sortPairs: true });

  export let root = tree.getRoot();

  function convert_to_bytes(v:string[]):Uint8Array{
    let len = v.length;
    let result = new Uint8Array(32*len);
    for(let i = 0;i<len;i++){
        result.set(Buffer.from(v[i].slice(2),'hex'),i*32);
    }
    return result;
  }

  export function get_proof(account:string):Uint8Array{
    let proof = tree.getHexProof((keccak256(account)));
    return convert_to_bytes(proof)
  }

链上部分:

负责存储树根和验证计算,代码是参考 openzeppelin 写的 :

Aptos 上使用 vector<u8>存储树根以及接收代验证数据和验证路径的原数据,

下图函数是使用 待验证的叶子结点leaf和验证路径数据proof计算tophash

    fun processProof(proof:vector<u8>,leaf:vector<u8>):vector<u8>{
        assert!(vector::length(&proof)%32==0,error::invalid_argument(LENGTH_INVALID));
        let deep = vector::length(&proof)/32;
        assert!(vector::length(&leaf)==32,error::invalid_argument(LENGTH_INVALID));
        let node = leaf;
        let index = 0;
        while(index < deep){
            node = hashPair(node,extract_vector(proof,index*32,index*32+32));
            index = index +1;
        };
        node
    }

由于aptos不能像 evm 一样可以直接传 byte32byte32[], 我们需要对验证路径信息即 proof 做简单的序列化。leaf和拆解出来的每一个vector<u8>挨个拼接并取hash ,以下为拼接函数:

fun hashPair(a:vector<u8>,b:vector<u8>):vector<u8>{
        if(compare_vector(&a,&b)==SMALLER){
            vector::append(&mut a,b);
            aptos_hash::keccak256(a)
        }else{
            vector::append(&mut b,a);
            aptos_hash::keccak256(b)
        }
    }

这里读者可以看到有一个拼接顺序的判断,因为我们并不知道当前位置的节点是左节点还是右节点,更不知道它的父节点、爷爷节点、太爷爷节点是左节点还是右节点,所以我们无法判断拼接的顺序。 这样就需要我们在链下和链上规定同一种排序方法,使得任意给两个兄弟节点,我们都可以知道他们的左右。 在这里我们使用比大小的方式,实际上如何排序都可以,只要链上链下的规则统一就不会出问题。

最后 判断 processProof计算得出的数据与合约中存储的树根是否相等,确定该 leaf 是否存在于该树中。

 public entry fun verify(proof:vector<u8>,leaf:vector<u8>)acquires Root {
        assert!(exists<Root>(Admin),error::not_found(ROOT_UNEXISTED));
        let root = borrow_global<Root>(Admin);
        assert!(com

再贴一下设置树根的方法:

struct Root has key {
   hash : vector<u8>
}

public entry fun set_root(signer:&signer,new_root:vector<u8>)acquires Root{
        assert!(address_of(signer)==Admin,error::permission_denied(NO_AUTHORIZATION));
        if(!exists<Root>(Admin)){
            move_to(
                signer,
                Root{
                    hash:new_root
                }
            );
        }else{
            let root = borrow_global_mut<Root>(Admin);
            root.hash = new_root;
        }
    }

交互部分:

只需要完成执行 set_rootverify 两个交易的方法,使用aptos官方sdk,做好序列化就好:

设置树根:

async function set_root(hash:string) {
    console.log(`set merkle root: ${hash}`);
    const entryFunctionPayload = new TransactionPayloadEntryFunction(
        EntryFunction.natural(          
          "0xe463a68bb1dd0d9b9864ed030a8cd357f2a38b6b3fea92c0af07694db203a6e0::merkle",         
          "set_root",
          [],
          [BCS.bcsSerializeBytes(Buffer.from(hash.slice(2),'hex')),],
        ),
      );
      const [{ sequence_number: sequenceNumber }, chainId] = await Promise.all([
        client.getAccount(admin.address()),
        client.getChainId(),
      ]);
      const rawTxn = new RawTransaction(
        AccountAddress.fromHex(admin.address()),
        BigInt(sequenceNumber),
        entryFunctionPayload,
        BigInt(2000),
        BigInt(100),
        BigInt(Math.floor(Date.now() / 1000) + 10),
        new ChainId(chainId),
      );
      const bcsTxn = AptosClient.generateBCSTransaction(admin, rawTxn);
      const transactionRes = await client.submitSignedBCSTransaction(bcsTxn);
      await client.waitForTransaction(transactionRes.hash);
    console.log(transactionRes.hash);
}

验证:

async function verify(proof:Uint8Array,hash:Buffer) {
    console.log(`set merkle root: ${hash}`);
    const entryFunctionPayload = new TransactionPayloadEntryFunction(
        EntryFunction.natural(          
          "0xe463a68bb1dd0d9b9864ed030a8cd357f2a38b6b3fea92c0af07694db203a6e0::merkle",          
          "verify",          
          [],
          [BCS.bcsSerializeBytes(proof),BCS.bcsSerializeBytes(hash)],
        ),
      );
      console.log(BCS.bcsSerializeBytes(proof));
      console.log(BCS.bcsSerializeBytes(hash));
    
      const [{ sequence_number: sequenceNumber }, chainId] = await Promise.all([
        client.getAccount(admin.address()),
        client.getChainId(),
      ]);
      const rawTxn = new RawTransaction(
        AccountAddress.fromHex(admin.address()),
        BigInt(sequenceNumber),
        entryFunctionPayload,
        BigInt(2000),
        BigInt(100),
        BigInt(Math.floor(Date.now() / 1000) + 10),
        new ChainId(chainId),
      );
      const bcsTxn = AptosClient.generateBCSTransaction(admin, rawTxn);  
      const transactionRes = await client.submitSignedBCSTransaction(bcsTxn);
      await client.waitForTransaction(transactionRes.hash);
    console.log(transactionRes.hash);
}

let account = '0x09d4ee382de0fa20f889ac6158273f29c81a1fec7385e8e26801db2e9e0c2f32'
//console.log('0x254a8d20f95c8a0ac2cb39041ba3375f6742dea2accf4361028e43ea669b8a91');
verify(get_proof(account),keccak256(account));

源码仓库地址:https://github.com/passer-byzhang/aptos-merkle 作者地址:alvan.coffee