觀點 | 關於 Fraud Proof 的沉思,Part-1
觀點 | 關於 Fraud Proof 的沉思,Part-2
5. 無效保險(Invalidity Insurance)
第一個解決方案算是兩個解決方案的簡化版。(好吧,也許我該讓你們自己來判斷。)
A. 概述
無效保障是一筆支付交易(即是一個比特幣腳本),僅在某個區塊被證明包含第一類錯誤時纔會生效(區塊由其哈希默克爾樹根值 8 來定義)。
這種支付交易的受益方需要提供 4 個東西:
- 哈希默克爾樹根值(hashMerkleRoot,縮寫爲 “hMR”);
- 一筆 “不良交易” —— 因某些原因應被判定爲無效的某筆交易的 TxID;
- 一個默克爾分支(如此處所述,由分支長度、分支哈希值及分支方向構成),能將不良交易與 hMR 關聯起來;
- 證明交易無效的證據。
B. 證據類型
第四個東西(“證據”)還會因交易所屬的錯誤類型不同而有所區別。不良交易可分爲 4 種:(a)無效交易;(b)雙花交易;(3)重複交易;以及第四類錯誤,(d)“錯誤累加(bad accumulator)”(見第 7 章)。
邊注: Fraud Proof vs. 智能合約 Fraud Proof 在繼續推進以前,我希望對比一下 “現有的 Fraud Proof” 與 “可以在一筆比特幣交易中使用的 Fraud Proof”。我的目的是實現後者,因爲它是一種雙贏的技術:首先,我們能獲得 Fraud Proof;其次,它也給了我們一種激勵兼容的辦法,讓我們能夠便宜地從全節點處購買到這些 Fraud Proof。實際上,我們確實需要雙贏的局面,因爲我想解決的不僅是 “如何構造 Fraud Proof” 的問題,也是 “保證 Fraud Proof 供應” 的 搭便車 難題。
讓比特幣自身能理解其 Fraud Proof 的好處是,我們可以把 Fraud Proof 放進交易中,並在比特幣智能合約中使用它。但這是非常難實現的。我絕對不打算假裝自己已經找到了最佳答案 9。
(a)無效交易乍看起來,我們似乎只需要用協議的交易驗證函數把交易再跑一遍,要是函數運行 失敗 就能證明該交易無效,因此,似乎只需要把交易自身作爲 “證據” 就可以了。但是,我認爲沒有那麼簡單。這裏面有個難題!如你我所知,跟比特幣相關的每一棵默克爾樹都包含可能是有效的交易,但是,樹上也包含它自身的內部節點(interior node)!如果 Sally 的默克爾樹聲稱某筆交易是無效的,然後她給我們展示了一個路徑,指向 “兩個串聯起來的 32 字節的 SHA256 哈希值”,我們能怎麼看呢?我們怎麼知道這些字節所代表的比特幣交易是無效的?Sally 的路徑所指向的 node 可能並不代表一筆交易,她有可能在默克爾樹的樹高上說謊了!或者相反的情況也有可能(比如惡意的 Fred 故意構造了一筆無效的交易,該交易的形式剛好是 64 個隨機字節),到底是誰在騙誰?爲解決這一難題,我們要求 Sally 同時還得提供一個默克爾分支,來證明別的一些交易是有效的。爲了方便程度最大化,可以就是她自己的交易(也就是她在收款時的交易,就在 Fraud Proof 交互過程剛開始的時候發生的),或者,也可以是 coinbase 交易(她的 “SPV+ 節點” 本身就會保存 coinbase 交易)。因此,在這個方案中,給定一筆是無效的,證據至少要包含兩筆交易,一是該無效交易本身,二是一筆有效交易,且兩筆交易的默克爾分支高度必須相等。如此,則(a)所需的證據形式與下文的 (b)和(c)所需的很相似。(b,c)雙花交易和重複交易對於(b)和(c)來說,欺詐的證據似乎也很直接,只需要兩筆交易和兩個分支就夠了——然後我們就可以看到兩筆交易的輸入(或者哈希值)是一樣的。但是這裏又有一個陷阱,就是第二筆交易的位置!(我這裏的 “第二筆” 的意思是按時間順序算的 “第一筆” 交易,也就是某人嘗試雙花的那筆 “真正” 的 交易 / 資金)。該筆交易可能存在於另一個區塊中。實際上,兩筆交易的位置可能遠隔成百上千個區塊。如果腳本解釋器可以訪問過去的區塊頭,那我們也許可以完成證明工作,只需加多一個 32 字節的哈希值就好。但我不知道完成這個事的最好辦法是什麼——也許是一個新的操作碼,會在驗證出某個 32 字節的哈希值不在已知的 hMR 集合中時傳出失敗。如果我們沒有高效的辦法,那麼在最糟糕的情況下,處理方法就非常煩人 —— 要加入一整條連續的區塊頭鏈條,從雙花交易所在區塊的區塊頭一直追溯到第二筆交易所在區塊的區塊頭。當然,後面的事情就比較簡單了,要求包含一個 “三件套” (區塊頭、默克爾分支、交易)來證明一筆有效的交易已經花費過那筆資金(對應(c)時,則是一筆具有相同哈希值的有效交易)。可怕的是,如果雙花交易所花費的資金是在數年前已經花費過的,則我們需要幾十萬個 80 字節的區塊頭來完成證明。這樣一個區塊頭鏈條自身的數據量可能就是 16MB!這麼大的數據量根本塞不進一筆交易裏面。現在,這裏需要提升。實際上,有些人,包括 Blockstream,曾經撰文討論過如何把一百萬個 80 字節的區塊頭壓縮成 “幾十 KB 的數據”,等等。(見附錄 B)如果你知道該怎麼處理這個問題,請留下你的評論!(d)錯誤累加對於(d)類不良交易,比特幣需要一種辦法來理解交易中數據的 “累加器”(或者 “第二見證數據”)。網絡需要根據交易的屬性來檢查這些數據。細節在本文第 7 章。(重複一遍:用軟件很容易實現,到要裝進比特幣腳本中就難很多。)
**
**
C. 彙總一下
有了這個腳本,我們可以策略性地部署在支付通道中,以保證不會收到無效的區塊頭。具體來說,對每一個區塊頭,我們都將把一個通道推入 “動能” 階段,使得:
- Sally 無條件給 Fred 支付一筆錢;並且
- Sally 可以從 Fred 處得到一大筆錢,只要她能找到一些證據,證明相關區塊頭是無效的。要不然,一段時間(比如 1000 個區塊)之後,Fred 就會收回這筆錢。
前面那筆資金有點像保險費,而第二筆資金像是保險理賠 —— 只要條件滿足,Sally 就有權得到賠付金,不然,Fred 就可以收回這筆錢。一個誠實的 Fred 完全有信心接受這種交易。對他來說,因爲絕對不可能找到他所提供的區塊頭無效的證明,因此他永遠不用賠付,而保險費簡直就是天上掉餡餅。因此,這裏的 “Fraud Proof” 是通過相反的方式來實現的:如果這種類型的交易沒有人願意簽署了,那我們就得到警示了。不過,在一種情況下,不誠實的 Fred 還會繼續提供這種服務,我們在上文所述的故事裏提到過,就是交易數據丟失的情況。不誠實的 Fred 知道,如果全網都丟失了某筆交易的數據,Sally 就不可能證明出其中的欺詐。因此,提供了相關服務的 Fred 也就永遠不會被抓到 —— TA 犯罪的證明已經蕩然無存,那 Sally 還憑什麼送 TA 去監獄呢?這就是爲什麼我們需要完整性審計(Fullness Audit)。
6. 完整性審計(Fullness Audit)
完整性審計使得 Fred 可以(向 Sally)證明他確實擁有一個區塊中的所有交易。
**
**
A. 兩種材料
首先,我們需要一種新的 “魔法材料”,用於把 “一個整數” 轉化成 “默克爾路徑方向” 並返回。有趣的是,我們已經有這種東西,無需再費手腳了。默克爾路徑方向已經作爲單個 int32_t 值存儲下來了(反正,Namecoin 的合併挖礦要用到)。甚至可以斷言,這個值 “……就等於所在默克爾樹最底層起始哈希值的索引”。這裏用到的是整數的二進制編碼原理!所以,問題解決了。我們需要的第二種魔法材料,“範圍證明 / 集合歸屬性證明”,讓我們可以利用鏈下交互(可能你在閱讀本文第 3 章時已經注意到了)。所以這個問題也基本上解決了。我再加依據,現在有一支比特幣頂級密碼學家天團在全身心投入研究 “範圍證明”,不過理由與我們這裏的不相干(他們想把範圍證明直接用在鏈上,用來隱匿比特幣交易的金額)。相較之下,我們的用法柔和得多。如果你認爲你有一個絕佳的承諾方案,請留言告訴我(可閱讀下文的 “(3)保險理賠” 瞭解更多細節)!
B. 彙總一下
鏈上發生的步驟如下(或更準確一點來說,是發生在支付通道的內部的事情,但這些指令可能隨時需要上傳到鏈上):
- Sally 給 Fred 無條件地支付一小筆錢。這是 Fred 要求的費用,或者說 “保險費”(數額很小的,因爲保險條件是 Fred 明知絕不可能發生的情況)
- Sally 要給 Fred 支付非常大一筆錢,如果 Sally 坐等時間流逝,遲遲不公開 TA 的祕密 “R” 的話。這個金額一定要大於下面的保險理賠金額,以保證 Sally 會及時交互。有點像是 “誠意契約(fidelity bond)”。
- 如果 Fred 不能提供 Sally 所要求的區塊數據的話,TA 要給 Sally 支付一大筆錢。這就是 “保險理賠金”。
(1)保險費保險費的數額非常小。通過普通的支付通道更新來傳遞。(2)誠意契約要實現誠意契約也很簡單,尤其是在閃電通道類型的通道中,因爲它是 “哈希時間鎖合約”。舉個例子,Sally 先發送 10 btc 給 Fred,這筆資金充當 “人質”。其次,Fred 把錢轉回給 Sally,當且僅當 Sally 在 “時間鎖窗口” 內公開了 R (即,一旦公開 R,就釋放人質)。那麼,如果 Sally 沒有公開 R,TA 就等於是交了 10 btc 的罰金。如果 TA 公開了 R,TA 就能拿回 10 btc,然後 Fred 就拿到了 R,他可以自由用在某筆交易中。如上所述,誠意契約必須是這幾筆資金中金額最大的,而且其時間鎖要短一些,因爲還有一個針對 Fred 的時間鎖(見下文),其長度要比誠意契約時間鎖長一倍,以保證 Fred 也有足夠長的時間來提供區塊數據(即,在 Fred 獲得了 R 之後,最壞也還有一個完整的時間鎖週期來完成任務)。(3)保險理賠實現保險理賠要難一點。保險理賠的形式與誠意契約一樣,只不過人質是 Fred 的資金,而不是 Sally 的。只有提供與 R 相關的區塊數據,TA 才能拿回自己的錢。我分兩部分來說明這個合約。第一部分是確認合約的初始參數:
- Fred 必須提供兩個整數 (X, R),並且承諾 c(X, R) 可以匹配一個預先設定好的哈希值 H1,而 hash(R) 匹配一個約定好的 H2。H1 和 H2 的值都是由 Sally 在選擇自己的隨機數並更新通道狀態的時候提供的。
- “X” 是一個默克爾樹索引值(請看上文的第一種 “魔法材料”),而 “R” 是一個隨機的 256 位的整數,是由 Sally 自主選擇的。
- Sally 爲了拿回她的 “誠意契約金” 就會公開 R
- 最後,Fred 可以用 R 來求得 X (只需計算該區塊所裝載的交易數量 L 的哈希值),然後提供 (X, R)。
很簡單吧?但第一部分還有最後一個要求:
- Sally 必須給 Fred 作出承諾,或者說提供範圍證明(在鏈下,實時交互,體積大小任意):X 必然落在 (1, L) 範圍內。
- (所以這個承諾可能無法採用哈希值的形式。那麼這就可能需要腳本的版本控制,或者一個新的操作碼,或其它更爲高級的技術。又或者只包含代數範圍。抱歉,找出最合用的工具非我所長,問問 Andrew Poelstra。)
第一部分只是確認 “Fred 同意要做什麼”。Fred 還沒有真正着手去做!所以,爲了滿足合約的條件,Fred 需要 :
- 將 x1 解釋爲一個默克爾樹索引值,然後提供一個默克爾分支,既有同樣的索引值,且最終的哈希值是 “H3”,即他們正在測試的區塊頭的哈希默克爾根值。這樣 Fred 就證明了,無論 Sally 選擇的隨機數是什麼,Fred 都可以向她出示相應的哈希值。
- 最後,Fred 還必須提供這個哈希值的原像。
一句話:要是 Fred 可以出示那個原像(產生出相應哈希值的原始數據),TA 就過關了。否則就不過。如果原像是一筆有效的交易,那麼皆大歡喜。如果原像不是一筆有效的交易(比如就是一個亂七八糟的數據),那 Sally 就大可利用第 5 章所述的 “無效保險” 來賺一筆了。兩個服務是相互補充的。
**
**
C. 重複審覈
顯然,Sally 能抓到欺詐的概率並不高:只有 1/L。所以,Sally 可能希望多次嘗試。而 Fred 應該也很樂意,因爲每次審覈 TA 都有錢進賬。
D. [可選] 關於丟失的數據
自上而下與自下而上我們可以把默克爾樹(在視覺上)想象成一個巨大的三角形。一般來說,這個三角形是 “自下而上” 搭起來的,最底下那一層是最先搭好的,而 “頂部” 是最後完成的。頂部的值(也就是默克爾根)會放到區塊頭裏。全節點總是這樣自下而上來搭建這個三角形的,原因如下:【1】全節點一般都擁有全部的底層數據;【2】三角形上,除了最底層,每一層的數據都取決於其底下一層的數據。但 SPV 節點也可以選擇用 “自上而下” 的方式來搭建三角形,就是從默克爾根往下延伸。這樣他們就既不需要保存整棵默克爾樹,又能 “瞄中” 這個三角形中某個位置的準確數據。(這種模式對正在下載和驗證一個新發現區塊的全節點來說也有用。因爲全節點需要存儲(最新一些區塊的)整個三角形 —— 所有中間層的哈希值都要保存。)“整個三角形”那整個三角形到底有多大呢?看錶:可看出,設第一列的值爲 “n”,那麼第二列的值就是 “2^(n-1)”,第三列的值就是 “(2^n)-1”。所以,第三列的值(也就是 “整個三角形” 的大小),差不多總是第二列值(“三角形” 的底層)的兩倍大。所以,如果我們存下整個三角形,而不是隻存底層,存儲(哈希值的)所要求的空間只不過增加了一倍。而且,全節點存儲着所有的交易,還有交易的哈希值。如果一個區塊的大小是 8 GB,因爲一筆交易的數據量大概是 250 字節,那麼區塊中大概會有 32,000,000 (3200 萬)筆交易,那麼 “三角形底層” 的大小是 32,000,000 * 32 byte (一個哈希值的數據量),就是 1.024 GB。根據上面的邏輯,三角形的其餘部分也會佔去約 1.024 GB,所以,全三角形存儲模式所要求的內存空間及硬盤空間是 10.048 GB,而不是 9.024 GB。(而且,一旦獲得了整個三角形,存儲要求會回落到 9.024 GB)。審覈三角形一個遵守協議的 Fred 可以獲得完整的三角形,但丟失了一些數據的 Fred 就做不到了。TA 甚至可能遺失一些 “從中到上” 路徑上的值,這就更容易被發現了,因爲數量上要少得多。實際上,Sally 可以要求任意的一個哈希值,具體在樹上哪個位置無所謂,只要是在樹上的就行。要通過這樣做來審覈三角形的完整性,TA 可採取跟我上文所述完全相同的步驟!只不過最後一步不是公開一筆比特幣交易,而是兩個 32 字節的哈希值(Sally 不能把這個數據用在無效保險中,恰好相反 —— TA 會認定這是 Fred 擁有整棵默克爾樹的證據)。
(未完) (文內提供了許多超鏈接,請點擊閱讀原文到 EthFans 網站上獲取) * * * **原文鏈接 :** http://www.truthcoin.info/blog/fraud-proofs/ **作者 :** Paul Sztorc **翻譯 & 校對 :**IAN LIU & 阿劍