# My ZKPlayground HW0 Write-up

By [{     }](https://paragraph.com/@whiteberets) · 2023-07-17

---

朋友揪我一起報名參加 ZKPlayground 課程，雖然我有點既期待又怕受傷害(ZK充滿了數學問題…😅)，不過既然有學伴一起探索零知識證明的世界，就一起組隊報名啦。

2023/07/13 晚上有辦課程說明會，主要說明了：

*   ZK Playground 活動介紹和目標
    
*   零知識證明的應用前景
    
*   重要的加分作業公告
    

因為最終只會有 15 個團隊錄取課程，所以加分作業主要是用來提高錄取率的。

我覺得加分題難度不高，而且解題過程頗有趣值得記錄下來，接下來就來看一下 HW0 的內容吧。

* * *

題目介紹
====

HW0 是一個部署在 Sepolia 上，沒有 Open-source 的智能合約，一共有兩個挑戰：

1.  向合約匯款 0.001 ETH。
    
2.  從合約中 ，根據規定架構製作此 Merkle Tree 的 Merkle Root，以及 `"zkplayground"` 這個字串之哈希存在在此 Merkle Tree 的 Merkle Proof。
    

![](https://storage.googleapis.com/papyrus_images/71d2a465f296dcf19aa29dde1858169c205db036802f2d3d064c97e1e7e1b5ce.png)

* * *

向合約匯款 0.001 ETH
---------------

就是單純地在 `opening` 作業繳交時間截止日完成前，發 0.001 ETH 到這個合約。

單純地用 Foundry 內建的 CLI Tool 就可以搞定了。

![](https://storage.googleapis.com/papyrus_images/aec96f90834f094d8635cfaf0055436f7a2d481237bb487970fc54fc2b7a086d.png)

* * *

解決 Merkle Proof 挑戰
------------------

Merkle Tree 是一種 Binary Tree 樹狀資料結構，是一種用於驗證數據完整性的數據結構，常用於區塊鏈和分佈式系統中。Merkle Tree 的特性是:

1.  完整性驗證：只需檢查 Merkle Tree 的 Root Node，就可以驗證整個數據集是否完整和未被修改，從而節省了大量的計算和存儲成本。**這點在區塊鏈特別重要，因為 I/O 儲存成本是非常昂貴的**。
    
2.  效率：當數據集中的某些數據發生變化時，只需重新計算與這些數據相關的 Sub-Tree，而不需要重新計算整個 Merkle Tree。**這點在區塊鏈特別重要，因為遍歷 O(n) 的運算成本是寶貴的**。
    

![Image by Martin Thoma.](https://storage.googleapis.com/papyrus_images/939e10792320b315e09ac355ec08d4974dbff1bda4dc9ca614d7576036311752.webp)

Image by Martin Thoma.

構成一個 Merkle Tree 會組成以下元素:

1.  底層葉子 Leaf (示意圖的 `[1, 2, 3, 4, 5, …]` 方塊)
    
2.  中間節點 Node (示意圖帶有 `H(…)` 的方塊)
    
3.  根節點 Root Node (綠色方塊，每個 Tree 只會有一個 Root Node)
    

**葉子節點(Leaf)** 存儲實際的數據，**中間節點(Node)** 是其底下兩個子節點串起來的 Hash，兩兩成對，最終往上組成的最後一個 Node 即為 **Root Node**。

Merkle Tree 特別適用於那些需要仰賴分散式系統進行某種身份驗證的應用程式，例如:

1.  門票領取: 每個領取者都是一個 Leaf。應用程式可以結合 Root Node 高效率地知道 **“這個領取者是否在白名單內“**，來做白名單身份驗證校驗。
    
2.  儲備量證明: 每個交易所的使用者帳本都是一個 Leaf。使用者可以拿著自己的帳本 Hash 和交易所公開的 Root Node Hash 比對，如果算出來的 Root Node Hash 和公開的 Root Node Hash 不吻合，則交易所有挪用使用者資產的嫌疑。
    
    1.  實際用例: [XREX Proof of User Balances Merkle Tree](https://support.xrex.io/en/articles/6799307-what-is-the-xrex-merkle-tree)
        

詳細運作方式，可以參考一下影片會有更深刻的理解：

[![]({{DOMAIN}}/editor/youtube/play.png)](https://www.youtube.com/watch?v=PraPZFMj6h8)

如何快速理解題目
--------

好家在，題目中只有 10 個葉子，我們可以用 [draw.io](https://draw.io) 把 Merkle Tree 圖像化出來，方便理解題目所要求的每個節點和葉子之間的關係。

![](https://storage.googleapis.com/papyrus_images/5003416706bbceb702a3d2d65ef509b4463c6b3fe19a307a8c255ba60f7c4dcc.png)

我們想要找到可以證明 `“zkplayground”` 在 Merkle Tree 裡的證明。已知 `“zkplayground”` 位於陣列的第一個元素，也就是 `leaves[0]`。

也就是說，智能合約有存著 `leaves[0]` 和 `Root Node` 的資訊，我們需要提出這些節點的資訊，才能讓智能合約還原出 `leaves[0]` 和 `Root Node` 之間的關係：

![](https://storage.googleapis.com/papyrus_images/c1759c9fb9c98082603f513ca47a7294922022cdcc4512be7ce2b222e9cefcb1.png)

幸運的是，智能合約部署在 Sepolia 上，不是每一個報名團隊獨立的環境，而且疑似出題方為了驗證部署上去的合約可以工作，已經送出過[解答的 Transaction](https://sepolia.etherscan.io/tx/0xca84a47ae904567f44b636f5ddeb72064ebeab9dca4f696537066a7092062ecf) 了，這就很方便我們進行 Debug 與確認正確解答。

下面是我對已被解答的 Transaction 進行分析的記錄
------------------------------

![先再次確認題目的 rootHash 是多少來著，避免踩到雷](https://storage.googleapis.com/papyrus_images/2ec58b42b95cd301eea2f586b1684d95ff768efe1598d92c4bffd004d6925332.png)

先再次確認題目的 rootHash 是多少來著，避免踩到雷

    # 然後分析解答的 Transaction 的 Calldata
    0x81f0765400000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000004cc61ebc064488ecc9c6aa0138875f527fe4033a5b0fb9a1acf9d48f8809a82e96cba9ea971cd36a1100bbe94d254d62109b18a1eb3714c80fbbcc9ffef36974440ef6049493657f0558c92f1f64806570ebba9e20cd40eb1385d8c61b3c523c7a7a7ef787c98fd4abfa510e07a146c11dbfcc93e6a316a41cb57f0dfa2b4cbd6
    

雖然出題方沒有要求寫 Write-up，所以其實可以直接複製相同的 Calldata 發送交易來通關😂，但是重點還是要理解這關要怎麼解掉。

![分析 Calldata 參數，原理推薦閱讀: EVM Deep Dive](https://storage.googleapis.com/papyrus_images/16edc502ac61b28b040c74f441df0fa87539b60aa693c7f7a4874bad3feb4794.png)

分析 Calldata 參數，原理推薦閱讀: EVM Deep Dive

也順便確認一下 Function Selector 是正確無誤的:

![已確認 Etherscan 上面看到的 Function Selector 和 Signature 匹配](https://storage.googleapis.com/papyrus_images/d9b6755d724c0a08606f858c23ad66a57425d29027d3c50844fb566f7d93bc98.png)

已確認 Etherscan 上面看到的 Function Selector 和 Signature 匹配

現在，已經知道了正確的 `Proofs[0]` 應該要是多少。我們可以快速確認一下 `leaves[1]` 是否就是 `Proofs[0]`，就可以知道我們要獲取的紅色方塊 Proofs 沒有畫錯，也沒有使用錯誤 Hash 算法。

![找到 Proof](https://storage.googleapis.com/papyrus_images/9796de692ac1af88bd58b5acd77a59a66b24f8fb740dc160e79131d80fd7f7a3.png)

找到 Proof

接下來，我們就可以利用相同的方式，取 `leaves[2]` 和 `leaves[3]` 兩兩成對算 Hash，找到 `Proofs[1]`：

![找到 Proof](https://storage.googleapis.com/papyrus_images/60473d2b3befd5e91a3ab113a41c5812b9241a2ea9357d41f5f37e50bdf54f79.png)

找到 Proof

### 但是，你會發現相同的作法，沒辦法找到 `Proofs[2]` 和 `Proofs[3]`。

初步猜想是出題方故意把順序打亂，而且不想讓你知道。一袋米要扛幾樓。

![leaves](https://storage.googleapis.com/papyrus_images/496d98ea697415d5fd61f1eb9ad4522486f85b97adbe73980f45d92e96e2ab98.png)

leaves

### 尋找 Proof\[3\]

我們可以先從 `Proof[3]` 開始尋找排列組成模式，因為它只經過一次的 `abi.encodePacked()`，找起來比較容易。`Proof[3]` 可以透過枚舉所有 `leaves[4]` 到 `leaves[9]` 的排列組合來爆破出來。

我們可以假設 Proof\[3\] 為 **n 個 leaves** 組合兩兩成對的 Hash，那麼這樣一共會有 `(n * (n - 1)) / 2` 個排列組合。

但是由於雜湊函式的特性，`Hash[1,2]` 與 `Hash[2,1]` 將會是完全不一樣的雜湊值，我們必須要一併將前後順序考慮進去。所以最終將會有 `(n * (n - 1))` 個組合。

我使用了 Python itertools 爆破排列組合：

![暴力尋找正確的 Proof](https://storage.googleapis.com/papyrus_images/7cf5f1e34e3d629ab6dcbf6858e29eed05256af83a0dea0a6edbb00a64ee4330.png)

暴力尋找正確的 Proof

執行輸出如下:

![Proof](https://storage.googleapis.com/papyrus_images/708aa3410b61209d3c11ef216bd0f9155d1f02dc33d577427d85fe2d8dc8886c.png)

Proof

### 尋找 Proof\[2\]

其實概念上和尋找 `Proof[3]` 一樣，只是需要再多加一層 keccak256，以及反過來枚舉出組成 sub-node 的 leaves 是誰。

![暴力尋找正確的 Proof](https://storage.googleapis.com/papyrus_images/de2646eac44aa4fe08d1ff862228d4fb1de516dc2d997c45135394ff3642e5bc.png)

暴力尋找正確的 Proof

![Proof](https://storage.googleapis.com/papyrus_images/7d86170c2d4da23ba42ac3030da2c909bec6dba8f25f25d47d23e9450fcf8c78.png)

Proof

最後，我們就可以得到完整的排列順序了。

![正確的 Mercle Tree 元素排列順序](https://storage.googleapis.com/papyrus_images/a0ccf1ea6ddd522b263047428ea45c693dabb4253e257ca795cd646dd26116d1.png)

正確的 Mercle Tree 元素排列順序

送出交易
----

![HW0 完成。](https://storage.googleapis.com/papyrus_images/91a4ffba460376d5b79e956126320d310f64572a323847d01731b0b6a25fed19.png)

HW0 完成。

完整爆破程式碼:

    from web3 import Web3
    import itertools
    import binascii
    
    
    # 第一層 Leaves
    a0 = Web3.solidity_keccak(['string'], ['zkplayground'])
    a1 = Web3.solidity_keccak(['string'], ['zkpapaya'])
    a2 = Web3.solidity_keccak(['string'], ['zkpeach'])
    a3 = Web3.solidity_keccak(['string'], ['zkpear'])
    a4 = Web3.solidity_keccak(['string'], ['zkpersimmon'])
    a5 = Web3.solidity_keccak(['string'], ['zkpineapple'])
    a6 = Web3.solidity_keccak(['string'], ['zkpitaya'])
    a7 = Web3.solidity_keccak(['string'], ['zkplum'])
    a8 = Web3.solidity_keccak(['string'], ['zkpomegranate'])
    a9 = Web3.solidity_keccak(['string'], ['zkpomelo'])
    leaves = [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9]
    
    # The correct proof we discovered from the previous tx.
    #https://sepolia.etherscan.io/tx/0xca84a47ae904567f44b636f5ddeb72064ebeab9dca4f696537066a7092062ecf
    proof_2 = '40ef6049493657f0558c92f1f64806570ebba9e20cd40eb1385d8c61b3c523c7' # Situated at c1
    proof_3 = 'a7a7ef787c98fd4abfa510e07a146c11dbfcc93e6a316a41cb57f0dfa2b4cbd6' # Situated at d1
    
    
    def find_proof3():
        print("In order to find the `proof[4]`, the total combinations possible for the B layer:")
    
        arr = [a4, a5, a6, a7, a8, a9] # The leaves we want to enumerate
        combinations = list(itertools.combinations(arr, 2)) # Generate all leaves combination
        total_combinations_count = len(combinations)
    
        print("Total combinations possible counts: ", total_combinations_count)
    
        # Enumerate all leaves combination
        for i in combinations:
            left_to_right = Web3.solidity_keccak(['bytes32', 'bytes32'], i) # [4, 5], [6, 7], [8, 9] ...etc.
            right_to_left = Web3.solidity_keccak(['bytes32', 'bytes32'], (i[1], i[0])) # [5, 4], [7, 6], [9, 8] ...etc.
    
            # Convert bytestring to string (no 0x prefix)
            L2R_hash = binascii.hexlify(left_to_right).decode()
            R2L_hash = binascii.hexlify(right_to_left).decode()
    
            if L2R_hash == proof_4:
                left_hash = i[0]
                right_hash = i[1]
                print('proof[4] found!!')
                print('Left Hash: ', binascii.hexlify(left_hash).decode())
                print('Right Hash: ', binascii.hexlify(right_hash).decode())
                break
            elif R2L_hash == proof_4:
                left_hash = i[1]
                right_hash = i[0]
                print('proof[4] found!!')
                print('Left Hash: ', binascii.hexlify(left_hash).decode())
                print('Right Hash: ', binascii.hexlify(right_hash).decode())
                break
        
        # mapping and print the leaf index
        print(f'Proof[4] left: leaves[{leaves.index(left_hash)}]')
        print(f'Proof[4] right: leaves[{leaves.index(right_hash)}]')
        
        return [left_hash, right_hash]
    
    
    def find_proof2():
        print("In order to find the `proof[3]`, the total combinations possible for the C layer:")
    
        arr = [a4, a5, a6, a7, a8, a9] # The leaves we want to enumerate
        combinations = list(itertools.combinations(arr, 2)) # Generate all leaves combination
    
        # Enumerate all leaves combination
        cache = []
        for i in combinations:
            # [4, 5], [6, 7], [8, 9] ...etc.
            left_to_right = Web3.solidity_keccak(['bytes32', 'bytes32'], i) 
            
            # [5, 4], [7, 6], [9, 8] ...etc.
            right_to_left = Web3.solidity_keccak(['bytes32', 'bytes32'], (i[1], i[0])) 
            
            # Cache the hash, to construct the parent node for enumeration
            cache.append(left_to_right)
            cache.append(right_to_left)
        
        layerB_combinations = list(itertools.combinations(cache, 2)) # Generate all sub-node combination
        total_combinations_count = len(layerB_combinations)
        print("Total combinations possible counts: ", total_combinations_count)
    
        # Enumerate all sub-nodes combination
        for i in layerB_combinations:
            # [4, 5], [6, 7], [8, 9] ...etc.
            left_to_right = Web3.solidity_keccak(['bytes32', 'bytes32'], i)
            
            # [5, 4], [7, 6], [9, 8] ...etc.
            right_to_left = Web3.solidity_keccak(['bytes32', 'bytes32'], (i[1], i[0]))
    
            # Convert bytestring to string (no 0x prefix)
            L2R_hash = binascii.hexlify(left_to_right).decode()
            R2L_hash = binascii.hexlify(right_to_left).decode()
    
            if L2R_hash == proof_3:
                left_hash = i[0]
                right_hash = i[1]
                print('proof[3] found!!')
                print('Left Hash: ', binascii.hexlify(left_hash).decode())
                print('Right Hash: ', binascii.hexlify(right_hash).decode())
                break
            elif R2L_hash == proof_3:
                left_hash = i[1]
                right_hash = i[0]
                print('proof[3] found!!')
                print('Left Hash: ', binascii.hexlify(left_hash).decode())
                print('Right Hash: ', binascii.hexlify(right_hash).decode())
                break
    
        return [left_hash, right_hash]
    
    def find_subnode_leaf(layerB_node_hash):
        combinations = list(itertools.combinations(leaves, 2)) # Generate all leaves combination
    
        # Enumerate all leaves combination
        for i in combinations:
            # [4, 5], [6, 7], [8, 9] ...etc.
            left_to_right = Web3.solidity_keccak(['bytes32', 'bytes32'], i) 
            
            # [5, 4], [7, 6], [9, 8] ...etc.
            right_to_left = Web3.solidity_keccak(['bytes32', 'bytes32'], (i[1], i[0])) 
    
            if left_to_right == layerB_node_hash:
                left_hash = i[0]
                right_hash = i[1]
                print('Left Hash: ', binascii.hexlify(left_hash).decode())
                print('Right Hash: ', binascii.hexlify(right_hash).decode())
                break
            elif right_to_left == layerB_node_hash:
                left_hash = i[1]
                right_hash = i[0]
                print('Left Hash: ', binascii.hexlify(left_hash).decode())
                print('Right Hash: ', binascii.hexlify(right_hash).decode())
                break
    
        # mapping and print the leaf index
        print(f'left leaf: leaves[{leaves.index(left_hash)}]')
        print(f'right leaf: leaves[{leaves.index(right_hash)}]')
        pass
    
    
        
    
    if __name__ == '__main__':
        find_proof3()
        print('----------------------------------------')
        [left_subnode, right_subnode] = find_proof2()
        find_subnode_leaf(left_subnode)
        find_subnode_leaf(right_subnode)
    
        # The Answer:
        # [0, 1, 2, 3, 5, 4, 7, 6, 9, 8]

---

*Originally published on [{     }](https://paragraph.com/@whiteberets/my-zkplayground-hw0-write-up)*