題幹與適用場景
這是密碼學資料結構與協定實作題。Merkle 包含證明不是把整棵樹傳給客戶端，而是提供從目標葉子到根所需的兄弟節點清單。RFC 9162 將葉子與內部節點使用不同前綴雜湊，並要求驗證者結合 leafindex 與 treesize 判斷每層左右方向。題目假設客戶端已透過可信渠道取得 root_hash；驗證演算法本身不負責建立信任錨點。
面試官考察點
- 能否區分葉子雜湊、內部節點雜湊與證明路徑的方向資訊。
- 能否用
leafindex、treesize做越界與路徑長度檢查。 - 能否理解域分離，避免把葉子位元組誤當成內部節點輸入。
- 能否說明證明大小
O(log n)、驗證時間O(log n)與可信根的邊界。
回答前需要釐清的問題
先確認樹的規範：是 RFC 9162 的可變大小 Merkle Tree，還是固定滿二元樹；葉子是否已完成正規化；雜湊演算法與前綴常數是什麼；路徑是否按由葉到根排列。還要確認是否需要驗證 append-only consistency proof、簽章，或只驗證單個包含證明。沒有這些約定，單獨一串雜湊無法唯一決定根。
30 秒回答框架
先檢查 0 <= leafindex < treesize，並限制路徑長度。把葉子正規化為 HASH(0x00 || leafbytes)，然後維護 fn = leafindex、sn = treesize - 1 與目前雜湊 r。每層依 fn 的最低位元或 fn == sn 決定兄弟節點在左或右，使用內部節點前綴 0x01 串接後再雜湊，並右移索引。最後要求 sn == 0 且 r == roothash。
分步驟深入解答
1. 固定輸入契約與域分離
證明驗證器需要版本化的雜湊演算法、葉子編碼、路徑順序與樹大小語義。RFC 9162 的 Merkle Tree Hash 用 0x00 標示葉子、0x01 標示內部節點，避免同一位元組串在兩種角色間產生歧義。實作不應直接對 leaf || sibling 做裸雜湊，也不應接受呼叫方任意替換前綴。
2. 先做邊界與資源檢查
leafindex >= treesize 必須失敗；空樹沒有合法葉子。路徑長度應有協定上限，例如不超過 ceil(log2(tree_size)) + 1，且每個雜湊固定位元組長度。驗證器要拒絕整數溢位、負數編碼、重複解析與超大路徑，避免異常證明消耗不受控資源。路徑過短也不能直接當成功，最終狀態必須能收斂到唯一根。
3. 逐層重建根雜湊
RFC 9162 的可變樹不能只看 leaf_index 的奇偶性；當目標節點位於目前子樹邊界時，fn == sn 會改變串接方向。每層處理後同時右移 fn 與 sn，把目前節點映射到上一層。偽程式碼如下：
verify(leaf, leafIndex, treeSize, path, expectedRoot):
if treeSize <= 0 or leafIndex < 0 or leafIndex >= treeSize: return false
r = HASH(0x00 || leaf)
fn = leafIndex
sn = treeSize - 1
for sibling in path:
if sn == 0: return false
if (fn & 1) == 1 or fn == sn:
r = HASH(0x01 || sibling || r)
else:
r = HASH(0x01 || r || sibling)
fn = fn >> 1
sn = sn >> 1
return sn == 0 and r == expectedRoot4. 驗證路徑與樹大小一致
證明中的 tree_size 是方向計算的一部分，不能只把它當日誌中繼資料。路徑消耗完時 sn 必須為零；若仍大於零，表示證明沒有抵達根。若中途 sn 已為零仍有額外節點，應拒絕。固定樹實作可以使用另一套規則，但必須把樹形約定與產生器完全綁定，不能混用 RFC 9162 的路徑。
5. 複雜度、通訊與信任邊界
平衡樹的包含路徑通常包含 O(log n) 個雜湊，驗證需要 O(log n) 次雜湊和 O(1) 除路徑外的狀態，證明通訊量為 O(log n * hashSize)。它只證明葉子對應給定 root_hash；如果根來自不可信回應，攻擊者可以同時替換根與證明。生產協定還需要簽章、可信日誌頭或 TLS 驗證來保護根與樹大小。
高品質示範回答
我會把驗證器綁定到版本化樹規範。先檢查 treesize > 0、0 <= leafindex < treesize、雜湊長度與路徑資源上限，再計算 r = HASH(0x00 || leaf)。維護 fn = leafindex 與 sn = tree_size - 1，每層在 fn 為奇數或 fn == sn 時把兄弟放在左側，否則放在右側，並使用 HASH(0x01 || left || right) 更新。同時右移兩個索引；路徑結束時只有 sn == 0 且結果等於可信根才成功。證明大小與驗證成本都是 O(log n)，但可信根、樹大小與路徑排序必須由協定保證。
常見錯誤
- 只按索引奇偶性決定方向，忽略可變樹的邊界條件
fn == sn。 - 對葉子與內部節點使用同一個雜湊前綴，失去域分離。
- 只比較重建根，不檢查葉子越界、路徑長度與
sn是否歸零。 - 把不可信回應中的 root_hash 當作信任錨點，誤以為包含證明提供認證。
- 產生器使用一種樹形規則，驗證器卻按另一種滿二元樹規則串接。
- 路徑順序、雜湊位元組序或葉子正規化沒有寫入版本契約。
追問及應對
如何驗證 append-only consistency proof？
包含證明只回答「某葉子在某個根中」。一致性證明還要同時重建舊樹根與新樹根，並證明舊樹是新樹的前綴；輸入至少包括舊樹大小、新樹大小、證明路徑與兩棵樹的可信根。兩種證明的狀態轉移不同，不能複用一個只回傳布林值的函式。
為什麼需要 tree_size，而不只傳路徑？
在可變大小樹中，最後一個節點可能沒有同層右兄弟，方向取決於目前子樹邊界。tree_size 讓驗證器知道哪些節點真實存在，也能拒絕把額外雜湊偽裝成根路徑。
如何避免雜湊演算法降級？
把演算法識別、雜湊輸出長度、葉子/內部前綴與正規化版本放在帶版本的協定中。驗證器只允許白名單演算法，拒絕未知或弱演算法；更換演算法時產生新的根命名空間，不能把不同演算法的摘要混在同一棵樹裡。
如何處理重複葉子？
包含證明證明的是位置與位元組對應的葉子，不保證內容在整棵樹中只出現一次。若業務要求唯一性，需要額外的唯一鍵索引或集合證明；不能從單個 Merkle 根推導「不存在第二個相同值」。
如何做增量產生而不存整棵樹？
產生器可保存每一層最近的右側子樹摘要，形成前綴累加器；新葉到達時按二進位進位合併。要產生歷史葉子的路徑，仍需保存必要節點或外部儲存；只保留根無法反推出證明路徑。
如果攻擊者提交超長路徑怎麼辦？
在解析前按樹大小與雜湊長度計算上限，拒絕超過上限的路徑；每個元素檢查固定長度，避免整數乘法溢位。驗證器應在任何雜湊計算前完成資源預算，錯誤證明不能觸發無限迴圈或大記憶體配置。