# My ZKPlayground HW0 Write-up

**Published by:** [{     }](https://paragraph.com/@whiteberets/)
**Published on:** 2023-07-17
**URL:** https://paragraph.com/@whiteberets/my-zkplayground-hw0-write-up

## Content

朋友揪我一起報名參加 ZKPlayground 課程，雖然我有點既期待又怕受傷害(ZK充滿了數學問題…😅)，不過既然有學伴一起探索零知識證明的世界，就一起組隊報名啦。 2023/07/13 晚上有辦課程說明會，主要說明了： ZK Playground 活動介紹和目標 零知識證明的應用前景 重要的加分作業公告 因為最終只會有 15 個團隊錄取課程，所以加分作業主要是用來提高錄取率的。 我覺得加分題難度不高，而且解題過程頗有趣值得記錄下來，接下來就來看一下 HW0 的內容吧。 題目介紹 HW0 是一個部署在 Sepolia 上，沒有 Open-source 的智能合約，一共有兩個挑戰： 向合約匯款 0.001 ETH。 從合約中 ，根據規定架構製作此 Merkle Tree 的 Merkle Root，以及 "zkplayground" 這個字串之哈希存在在此 Merkle Tree 的 Merkle Proof。 向合約匯款 0.001 ETH 就是單純地在 opening 作業繳交時間截止日完成前，發 0.001 ETH 到這個合約。 單純地用 Foundry 內建的 CLI Tool 就可以搞定了。 解決 Merkle Proof 挑戰 Merkle Tree 是一種 Binary Tree 樹狀資料結構，是一種用於驗證數據完整性的數據結構，常用於區塊鏈和分佈式系統中。Merkle Tree 的特性是: 完整性驗證：只需檢查 Merkle Tree 的 Root Node，就可以驗證整個數據集是否完整和未被修改，從而節省了大量的計算和存儲成本。這點在區塊鏈特別重要，因為 I/O 儲存成本是非常昂貴的。 效率：當數據集中的某些數據發生變化時，只需重新計算與這些數據相關的 Sub-Tree，而不需要重新計算整個 Merkle Tree。這點在區塊鏈特別重要，因為遍歷 O(n) 的運算成本是寶貴的。 Image by Martin Thoma. 構成一個 Merkle Tree 會組成以下元素: 底層葉子 Leaf (示意圖的 [1, 2, 3, 4, 5, …] 方塊) 中間節點 Node (示意圖帶有 H(…) 的方塊) 根節點 Root Node (綠色方塊，每個 Tree 只會有一個 Root Node) 葉子節點(Leaf) 存儲實際的數據，中間節點(Node) 是其底下兩個子節點串起來的 Hash，兩兩成對，最終往上組成的最後一個 Node 即為 Root Node。 Merkle Tree 特別適用於那些需要仰賴分散式系統進行某種身份驗證的應用程式，例如: 門票領取: 每個領取者都是一個 Leaf。應用程式可以結合 Root Node 高效率地知道 “這個領取者是否在白名單內“，來做白名單身份驗證校驗。 儲備量證明: 每個交易所的使用者帳本都是一個 Leaf。使用者可以拿著自己的帳本 Hash 和交易所公開的 Root Node Hash 比對，如果算出來的 Root Node Hash 和公開的 Root Node Hash 不吻合，則交易所有挪用使用者資產的嫌疑。 實際用例: XREX Proof of User Balances Merkle Tree 詳細運作方式，可以參考一下影片會有更深刻的理解： 如何快速理解題目 好家在，題目中只有 10 個葉子，我們可以用 draw.io 把 Merkle Tree 圖像化出來，方便理解題目所要求的每個節點和葉子之間的關係。 我們想要找到可以證明 “zkplayground” 在 Merkle Tree 裡的證明。已知 “zkplayground” 位於陣列的第一個元素，也就是 leaves[0]。 也就是說，智能合約有存著 leaves[0] 和 Root Node 的資訊，我們需要提出這些節點的資訊，才能讓智能合約還原出 leaves[0] 和 Root Node 之間的關係： 幸運的是，智能合約部署在 Sepolia 上，不是每一個報名團隊獨立的環境，而且疑似出題方為了驗證部署上去的合約可以工作，已經送出過解答的 Transaction 了，這就很方便我們進行 Debug 與確認正確解答。 下面是我對已被解答的 Transaction 進行分析的記錄 先再次確認題目的 rootHash 是多少來著，避免踩到雷 # 然後分析解答的 Transaction 的 Calldata 0x81f0765400000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000004cc61ebc064488ecc9c6aa0138875f527fe4033a5b0fb9a1acf9d48f8809a82e96cba9ea971cd36a1100bbe94d254d62109b18a1eb3714c80fbbcc9ffef36974440ef6049493657f0558c92f1f64806570ebba9e20cd40eb1385d8c61b3c523c7a7a7ef787c98fd4abfa510e07a146c11dbfcc93e6a316a41cb57f0dfa2b4cbd6 雖然出題方沒有要求寫 Write-up，所以其實可以直接複製相同的 Calldata 發送交易來通關😂，但是重點還是要理解這關要怎麼解掉。 分析 Calldata 參數，原理推薦閱讀: EVM Deep Dive 也順便確認一下 Function Selector 是正確無誤的: 已確認 Etherscan 上面看到的 Function Selector 和 Signature 匹配 現在，已經知道了正確的 Proofs[0] 應該要是多少。我們可以快速確認一下 leaves[1] 是否就是 Proofs[0]，就可以知道我們要獲取的紅色方塊 Proofs 沒有畫錯，也沒有使用錯誤 Hash 算法。 找到 Proof 接下來，我們就可以利用相同的方式，取 leaves[2] 和 leaves[3] 兩兩成對算 Hash，找到 Proofs[1]： 找到 Proof 但是，你會發現相同的作法，沒辦法找到 Proofs[2] 和 Proofs[3]。 初步猜想是出題方故意把順序打亂，而且不想讓你知道。一袋米要扛幾樓。 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[2] 其實概念上和尋找 Proof[3] 一樣，只是需要再多加一層 keccak256，以及反過來枚舉出組成 sub-node 的 leaves 是誰。 暴力尋找正確的 Proof Proof 最後，我們就可以得到完整的排列順序了。 正確的 Mercle Tree 元素排列順序 送出交易 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]

## Publication Information

- [{     }](https://paragraph.com/@whiteberets/): Publication homepage
- [All Posts](https://paragraph.com/@whiteberets/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@whiteberets): Subscribe to updates