淺談 Commitment
來看一個丟銅板的問題.
平常的丟銅板
(一陣討論之後)
A: … 那不然來丟銅板好了, 猜錯請客.
B: 好喔. 你猜我丟.
A: 我猜… 正面.
B: (丟) 反面.
A: 好吧, 我請客.
隔牆丟銅板
上面是平常的版本. 如果場景改成 A B 中間隔著一道牆呢?
B: 好喔. 你猜我丟.
A: (喊過去) 我猜正面!
B: (喊回去) 我丟出反面!
A: (…好像哪裡怪怪的)
這裡有個問題: 要是 B 壞心, A 猜正面 B 就說反面, A 猜反面 B 就說正面, 那不是永遠都是 A 請客了? 😅
來換個方法.
B: 好喔. 你猜我丟.
A: (把 “正面” 寫在紙條上, 鎖在小盒子裡, 從牆頭丟過去)
B: (喊回去) 我丟正面!
A: (把鑰匙丟過牆頭) “看來你要請客囉!”
B: (打開盒子看到 “正面”)
B: 好啦好啦! 我請客!
或者也可能是:
A: (把裝著 “正面” 的小盒子丟過去)
B: (喊回去) 我丟反面!
A: (把鑰匙丟過牆頭) “好啦好啦! 我請客!”
為什麼這時候 A B 都甘願了?
A 想: 先前我不甘願, 是因為 B 先知道我猜什麼的話, 就可以和我唱反調, 讓結果傾向對他有利的那邊. 但是現在他看不到我猜什麼了, 也就不知道要傾向哪一邊, 所以我願意接受這個玩法.
這個 “看不到” 的特性, 我們把它叫做 “hiding”.
B想: A 猜什麼已經先鎖在盒子裡了. 只要盒子沒有機關 (比方說 A 聽到正面就丟個能開出正面的鑰匙過來, 聽到反面就丟個能開出反面的鑰匙過來), 不會變來變去, 那我也願意接受這過玩法.
這個 “不會變來變去” 的特性, 我們把它叫做 “binding”.
A 把箱子丟過去, 這個動作我們把它叫 commit, 而裝著紙條的箱子叫做 commitment.
A 把鑰匙丟過去, B 打開相信了某件事, 這件事的內容(“A猜正面”)叫做 opening, 而鑰匙則是 proof.
隔網路丟銅板
場景再改一改: 如果 A 和 B 不是隔著牆, 而是隔著網路呢?
這時候 “盒子” 就有很多種設計了. 我們先想一個基本的: hash.
正面 0, 反面 1.
如果 A 只是直接拿 hash(0), hash(1) 給 B 看, 固定就是那兩個值的話, B 一看就知道了, 這樣沒有 hiding 的效果. 所以可以讓 A 先從很大的範圍 random 取個整數 x, 偶數正面奇數反面, 把 hash(x) 當成 commitment 送給 B. 這樣 B 拿到範圍也很大的 hash(x) 時, 應該猜不出 x 的奇偶 (hiding), 也就不能作怪.
再來 B 投了銅板之後, A 把 x 傳給 B, 讓 B 去 hash 確認. B 為什麼會甘願呢? 因為 B 相信目前沒有人能夠輕易地找出另一個 x’, 讓 x’ 也 hash 到原先的 hash(x), 也就是 A 沒辦法在聽到 B 說什麼之後又變來變去 (binding), 所以 B 也甘願.
另一種方法是: A 拿 0 或 1 配上一個 random number 一起去 hash, 將來再把 0 1 和 random number 開給 B 看, 也有一樣的效果.
Merkle Tree: Hash 又 Hash
再推遠一點: 前面 A 給 B 一個 commitment 之後, 後來可以讓 B 願意相信單一某件事 (單個 opening). 那, 有沒有辦法讓 B 相信多件事呢? (多個 opening)
假設 A 想後來讓 B 相信 p q r s. 最簡單的就是先把 hash(p, q, r, s) 送給 B, 之後再把 p q r s 給 B 看, B 就會相信. 但是有些應用我們不想讓 B 一次知道那麼多, 或者 p q r s 很多很大, 不想傳那麼巨量的資料給 B 的話, 我們可以改用另一個設計: Merkle Tree.
A 先拿 ROOT 當成 commitment 送給 B.
之後如果 A 想讓 B 相信 q , 那 A 可以提供 q, HP, HHRHS 給 B. 讓 B 自己先計算出 HQ, HHPHQ . 然後從上往下看:
A: 我說 HHPHQ 沒有變來變去, 你相信嗎?
B: 嗯… 我相信. 因為目前沒有人可以在固定 hash(y, z) 的值的狀況下, 給出另一組 y’ z’ 讓他也 hash 到 hash(y, z). 所以在固定 ROOT 的值的狀況下, 現在的 HHPHQ 和 HHRHS 應該是你先前算好沒有變來變去的. 好, 我相信 HHPHQ.
A: 那我說 HQ 沒有變來變去, 你相信嗎?
B: 嗯… 我相信. 因為目前沒有人可以在固定 hash(y, z) 的值的狀況下, 給出另一組 y’ z’ 讓他也 hash 到 hash(y, z). 所以在固定 HHPHQ 的值的狀況下, 現在的 HP 和 HQ 應該是你先前算好沒有變來變去的. 我相信 HQ.
A: 那我說 q 沒有變來變去, 你相信嗎?
B: 嗯… 我相信. 因為目前沒有人可以在固定 hash(x) 的值的狀況下, 給出另一個 x’ 讓他也 hash 到 hash(x). 所以固定了 HQ, 我相信 q 沒有變來變去.
所以, 如果有 N 個資訊想要將來讓 B 相信, A 可以把這個 hash 又 hash 的 tree 的 root 給 B 當成 commitment 固定住. 將來 A 想要和 B 開箱下面某個單一值的時候, 不用把所有底下的值 (p q r s) 都露給 B 看, B 就會願意相信 A, 且 A 給的 proof 只要大約 log(N) 的大小.
多項式
數學家還弄出了這樣的東西 (比方說 KZG10 演算法): 如果 A 想要讓 B 將來相信 x1, x2 … xN 能對應到 y1, y2 … yN, 那麼 A 可以造出一個穿過 (x1, y1), (x2, y2) … (xN, yN) 的多項式 P, 也就是 P(x1) = y1, P(x2) = y2 … P(xN) = yN, 然後給 B 一個關於這個多項式的 commitment 固定住. 將來有需要的時候, A 可以單獨開某個點, 讓 B 願意相信比方說 P(x3) = y3, 而且 B 不會因此知道其他點的資訊.
這邊 A 給的 commitment 和 Merkle tree 的做法一樣好, 是和 N 無關的常數大小. 而 A 每次給 B 的 proof 則比 Merkle tree 的 log(N) 厲害, 只要常數大小的資料就可以做到. 甚至一次開多個點所需的額外 proof 也只要常數大小. 因此對一些很計較大小的場合特別有用.
尾聲
從丟銅板的例子中, 我們可以體會到 hiding / binding 的動機, 也看到一些不同 commitment 方式的實作. 希望這個例子將來可以幫助你回想起這些觀念.
(感謝 吳秉宸 與 Chih-Cheng Liang 的審閱與建議)
參考資料:
Blum81: Coin Flipping by Telephone: A Protocol for Solving Impossible Problems
KZG10: Constant-Size Commitments to Polynomials and Their Applications
