---
title: 'Solidity WTF 103 36 單元 Merkle Tree'
lang: zh-tw
---

Solidity WTF 103 36 單元 Merkle Tree
===
:::info
:date: 2024/10/13
:::

[TOC]
# Merkle Tree
`Merkle`樹是一種樹狀數據結構，用來驗證某個數據是否在一組數據中。通過`Merkle Proof`(默克爾證明)，只需提供少量信息即可驗證數據有效性。
## 樹
組成結構為:
- 葉片節點
- 非葉片節點
- 根節點(`root`)
> 大部分樹結構都如此，會根據不同算法與應用場景，而有不同的延伸方向。
## 驗證
如何通過`Merkle Proof`驗證某個數據是否存在與有效。
舉例:

        Top Hash (Root)
           /      \
       Hash 0     Hash 1
      /    \      /    \
 Hash 0-0 Hash 0-1 Hash 1-0 Hash 1-1
  (L1)    (L2)   (L3)     (L4)

- 葉片節點`L1`和`L2`的`hash`值分別為`Hash0-0`和`Hash0-1`，他們的哈希值又會是結合起來得到`Hash0`，同樣`L3`、`L4`的哈希可以得到`Hash1`。

假設你想驗證`L1`是否在這棵樹裡:
- `Hash0-1`: 你可以通過`L1`計算出`Hash0-0`，然後用這個和`Hash0-1`來計算`Hash0`。
- `Hash1`: 有了`Hash0`，你可以用`Hash0`和`Hash1`計算出根節點。

如果你計算出的根節點和存儲的根節點相同，就證明L1是這顆樹的一部分。

## Ceil(log₂N)
### 計算方式
要驗證數據使否有效，也會需要一些資料帶入來去計算，那這邊只需要`ceil(log₂N)`個數據(也稱為`proof`)。

`ceil(log₂N)是`指取不小於`log₂N`的最小整數。這邊舉例如何計算:
- 如果有`N = 4`個葉片節點，就會是`log₂4 = 2`，表示這棵樹有兩層。

### 為何使用`log₂N`？
> 因為每個節點都會需要用到倆的值來計算，就等同於一個節點會分裂出兩個節點，所以使用`log₂N。`
### 什麼是 ceil(log₂N)？
> 如果`N = 5`個子節點，`log₂5 ≈ 2.32`，向上取整束後`ceil(log₂5) = 3`，代表需要`3`層哈希來驗證。
### 舉例
假設有`8`個葉子節點:

        Root
       /    \
    H0       H1
   /  \     /  \
H00  H01  H10  H11
/ \   / \  / \  / \
L1 L2 L3 L4 L5 L6 L7 L8

樹的高度就是`log₂8 = 3`，因次驗證某個節點，需要`3`個哈希值。
> 假設需要驗證`L1`是否在樹中，`Merkle Proof`包含以下哈希值:
> - `H00`: 通過`L1`計算出`H00`。
> - `H01`: 用`H00`和`H01`計算出。
> - `H1`: 用`H0`和`H1`計算出`root`。
::: warning
這邊的`Merkle proof`為`L2`、`H01`、`H1`。
:::

#### 這邊有實際網站可以學習
[點選這邊](https://lab.miguelmota.com/merkletreejs/example/)，給予下列四個地址生成`Merkle Tree`。

[
    "0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", 
    "0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
    "0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db",
    "0x78731D3Ca6b7E34aC0F824c42a7cC18A495cabaB"
]

在網站內選`Keccak-256`, `hashLeaves`和`sortPairs`選項，然後點`Compute`，`Merkle Tree`就生成好了，展開為:

根: eeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097
   ├─ 9d997719c0a5b5f6db9b8ac69a988be57cf324cb9fffd51dc2c37544bb520d65
   │  ├─ 葉子0：5931b4ed56ace4c46b68524cb5bcbf4195f1bbaacbe5228fbd090546c88dd229
   │  └─ 葉子1：999bf57501565dbd2fdcea36efa2b9aef8340a8901e3459f4a4c926275d36cdb
   └─ 4726e4102af77216b09ccd94f40daa10531c87c4d60bba7f3b3faf5ff9f19b3c
      ├─ 葉子2：04a10bfd00977f54cc3450c9b25c9b3a502a089eba0097ba35fc33c4ea5fcb54
      └─ 葉子3：dfbe3e504ac4e35541bebad4d0e7574668e16fefa26cd4172f93e18b59ce9486

點`Proof`驗證你要的葉子節點，就會出現`Proof`的內容。
## code
>MerkleProof庫有三個函數
> - verify(): 利用proof來驗證leaf是否存在根為root的Merkle Tree中，是的話回傳true且調用processProof()。
> - processProof(): 利用proof和leaf計算Merkle Tree的root。調用了_hashPPair()。
> - _hashPPair(): 用keccak256()去計算非根節點的兩個子節點的哈希(排序後)。
>>

library MerkleProof {
    /**
     * @dev 當通過 `proof` 和 `leaf` 重建出的 `root` 與給定的 `root` 相等時，返回 `true`，表示資料有效。
     * 在重建時，葉子節點對和元素對都是已排序的。
     */
    function verify(
        bytes32[] memory proof,
        bytes32 root,
        bytes32 leaf
    ) internal pure returns (bool) {
        return processProof(proof, leaf) == root;
    }

    /**
     * @dev 返回通過 Merkle 樹使用 `leaf` 和 `proof` 計算出的 `root`。當重建出的 `root` 與給定的 `root` 相同時，`proof` 才是有效的。
     * 在重建時，葉子節點對和元素對都是已排序的。
     */
    function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    // 已排序的節點對 Hash
    function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
        return a < b ? keccak256(abi.encodePacked(a, b)) : keccak256(abi.encodePacked(b, a));
    }
}