My ZKPlayground HW0 Write-up

朋友揪我一起報名參加 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。

post image

向合約匯款 0.001 ETH

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

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

post image

解決 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.
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

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

Play Video

如何快速理解題目

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

post image

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

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

post image

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

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

先再次確認題目的 rootHash 是多少來著，避免踩到雷
先再次確認題目的 rootHash 是多少來著，避免踩到雷
# 然後分析解答的 Transaction 的 Calldata
0x81f0765400000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000004cc61ebc064488ecc9c6aa0138875f527fe4033a5b0fb9a1acf9d48f8809a82e96cba9ea971cd36a1100bbe94d254d62109b18a1eb3714c80fbbcc9ffef36974440ef6049493657f0558c92f1f64806570ebba9e20cd40eb1385d8c61b3c523c7a7a7ef787c98fd4abfa510e07a146c11dbfcc93e6a316a41cb57f0dfa2b4cbd6

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

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

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

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

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

找到 Proof
找到 Proof

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

找到 Proof
找到 Proof

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

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

leaves
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
暴力尋找正確的 Proof

執行輸出如下:

Proof
Proof

尋找 Proof[2]

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

暴力尋找正確的 Proof
暴力尋找正確的 Proof
Proof
Proof

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

正確的 Mercle Tree 元素排列順序
正確的 Mercle Tree 元素排列順序

送出交易

HW0 完成。
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]