# Aptos中实现merkle树验证

• Alvan
• 更新于 2022-10-11 11:41
• 阅读 2033

## 原理讲解：

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

## 实现：

### 链下部分：

``````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.............';

"0x36346bbcda6f9f74cf36cff31e00ac83c9d8a512a6564c9f93b00d249e3b2b45",
"0x09d4ee382de0fa20f889ac6158273f29c81a1fec7385e8e26801db2e9e0c2f32",
"0x09d4ee382de0fa20f889ac6158273f29c81a1fec7385e8e26801db2e9e0c2f32",
];

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&lt;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)
}``````

### 链上部分：

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

``````    fun processProof(proof:vector&lt;u8>,leaf:vector&lt;u8>):vector&lt;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 &lt; deep){
node = hashPair(node,extract_vector(proof,index*32,index*32+32));
index = index +1;
};
node
}``````

``````fun hashPair(a:vector&lt;u8>,b:vector&lt;u8>):vector&lt;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)
}
}``````

`````` public entry fun verify(proof:vector&lt;u8>,leaf:vector&lt;u8>)acquires Root {
assert!(com``````

``````struct Root has key {
hash : vector&lt;u8>
}

public entry fun set_root(signer:&signer,new_root:vector&lt;u8>)acquires Root{
move_to(
signer,
Root{
hash:new_root
}
);
}else{
root.hash = new_root;
}
}``````

### 交互部分：

``````async function set_root(hash:string) {
console.log(`set merkle root: \${hash}`);
EntryFunction.natural(
"0xe463a68bb1dd0d9b9864ed030a8cd357f2a38b6b3fea92c0af07694db203a6e0::merkle",
"set_root",
[],
[BCS.bcsSerializeBytes(Buffer.from(hash.slice(2),'hex')),],
),
);
const [{ sequence_number: sequenceNumber }, chainId] = await Promise.all([
client.getChainId(),
]);
const rawTxn = new RawTransaction(
BigInt(sequenceNumber),
BigInt(2000),
BigInt(100),
BigInt(Math.floor(Date.now() / 1000) + 10),
new ChainId(chainId),
);
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}`);
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.getChainId(),
]);
const rawTxn = new RawTransaction(
BigInt(sequenceNumber),
BigInt(2000),
BigInt(100),
BigInt(Math.floor(Date.now() / 1000) + 10),
new ChainId(chainId),
);
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));``````

Alvan
0x8958...672e