最新論文筆記(+15)：Redactable Blockchain Protocols with Instant Redaction /IACR Cryptol.ePrint Arch 2021

Redactable Blockchain Protocols with Instant Redaction(具有即時編輯功能的可編輯區塊鏈)

這篇文章是今年發表在IACR Cryptol.ePrint Arch上的一篇區塊鏈相關論文，質量很不錯，值得深入研讀，有很多學習的地方，

主要內容是：在許多場景下，區塊鏈的immutability(不可變性)同樣帶來了許多弊端，例如，存盤一些非法資料在鏈上將帶來諸多挑戰，因此，本文設計了一種可編輯區塊鏈構造的通用協議，該協議在無授權設定下可即時編輯，并在基于PoS和PoW共識區塊鏈進行了實體化，最后，為編輯協議開發了一個概念驗證(Proof of Concept, PoC)實作和應用該協議，實驗表明較高的效率，引起的開銷也很小，

下面將大致按照文章結構內容，并結合自己讀后的學習筆記進行梳理和歸納，可能會有整理不當的地方，僅代表個人理解，詳細內容還是建議看原文！

• 原文鏈接：Redactable Blockchain Protocols with Instant Redaction

（長文警告，本篇大約1.6w個字，謹慎閱讀！）

文章主要貢獻：

• 1）具有即時編輯功能的區塊鏈通用構造方法：
  • 第一步，利用通用函式 C m t Cmt Cmt和 V e r f i y C m t VerfiyCmt VerfiyCmt來隨機選舉委員會，以確保足夠比例的委員會成員是誠實的；
  • 第二步，每個委員的候選編輯區塊 B j ? B^*_j Bj??的哈希上簽名進行投票，若 > 1 / 2 >1/2 >1/2的投票通過，則舊區塊 B j B_j Bj?被 B j ? B^*_j Bj??取代，
• 2）基于仿真的可編輯區塊鏈的安全性分析：
  • 首次定義了可編輯區塊鏈的理想化功能 F t r e e \mathcal{F}_{tree} Ftree?，它實時跟蹤所有有效鏈;
  • 并證明任何real-world協議中成功的攻擊都可規約到ideal-world的 F t r e e \mathcal{F}_{tree} Ftree?模型中，
• 3）實體化和性能評估：
  • 通過在基于PoS和PoW共識區塊鏈上的通用函式 C m t Cmt Cmt和 V e r i f y C m t VerifyCmt VerifyCmt的具體實體化，證明了本文的方案構造是通用的，

一、寫作背景

論文名稱	作者 / 單位	來源	年份	簡要內容
Redactable Blockchain Protocols with Instant Redaction	Jing Xu et.al (Institute of Software, Chinese Academy of Sciences)	IACR Cryptol.ePrint Arch	2021	本文設計了一種可編輯區塊鏈構造的通用協議，該協議在無授權設定下可即時編輯，

（1）首先，要理解為什么要有可編輯區塊鏈的出現？區塊鏈的內容為什么有編輯需求，該如何進行編輯和審查？

論文中提到，由于任何人都可以在無授權設定（可以理解為是公有鏈，沒有訪問限制）的區塊鏈中進行寫入（上傳）資料操作，一些惡意的用戶久可能會濫用發布任意的交易訊息 [ 40 ] \textcolor{blue}{[40]} [40]，

• 區塊鏈賬本上存盤的資料可能是敏感的、有害的或非法的，如侵犯知識產權的資料 [ 28 ] \textcolor{blue}{[28]} [28]、兒童性侵照片 [ 34 ] \textcolor{blue}{[34]} [34]，它們可能會永遠影響人們的生活，并阻礙更廣泛的區塊鏈應用，
• 歐盟在2018年發布了資料保護條例（GDPR） [ 7 ] \textcolor{blue}{[7]} [7]不再與位元幣和以太坊等當前區塊鏈兼容 [ 6 ] \textcolor{blue}{[6]} [6]記錄個人資料，特別是，GDPR將“被遺忘權”規定為關鍵的資料主體權利，
• 另外，臭名昭著的DAO漏洞被利用時，以太坊的DAO合約 [ 31 ] \textcolor{blue}{[31]} [31]的缺陷導致360w以太幣（約7900w美元）被盜，必須通過硬分叉“回滾”來解決，

（2）其次，目前可編輯區塊鏈的研究現狀是怎樣的？一些相關作業主要做了那些方面？

論文中提到，有一些不用編輯的方法就是發起硬分叉，這本質上要求所有社區成員進行投票，這樣的方法會帶來分裂社區的風險，且非常昂貴和緩慢，那么就有幾篇可編輯區塊鏈的研究作業，

• 在2017年，Ateniese等 [ 12 ] \textcolor{blue}{[12]} [12]首次引入了可編輯區塊鏈的概念，該方案使用了帶陷門的變色龍函式（Chameleon Hash）(變色龍哈希函式的詳細介紹）來代替了內層的普通抗碰撞哈希函式，而外層還是普通的哈希函式，帶陷門的用戶可以計算任意輸入資料的哈希碰撞，而不知道陷門的用戶則變色龍哈希與傳統哈希函式一樣具有抗碰撞性，該方案從而可以不改變外層哈希函式H、不破壞哈希鏈路完整性的情況下，實作對區塊內容的修改，
• 在2019年，Derler等 [ 20 ] \textcolor{blue}{[20]} [20]提出了一種基于策略的變色龍哈希函式的細粒度可控編輯機制，任何擁有足夠特權滿足策略的人都可以找到給定哈希的碰撞，他們的解決方案關注于授權設定，而在非授權設定中，沒有單個可信物體，用戶可以隨時加入和離開系統，因此在共享陷門密鑰時，他們的解決方案將面臨可伸縮性問題，
• 在2017年，Puddu等 [ 39 ] \textcolor{blue}{[39]} [39]提出了 μ \mu μ鏈，交易發送方可對交易不同版本加密，用解密密鑰在礦工之間秘密共享，收到編輯請求時，先根據交易發送方制定的編輯策略進行檢測，然后通過執行多方計算協議算出相應的解密密鑰，最后對該密鑰解密，然而，建立編輯策略的惡意用戶可能會逃避編輯，甚至會由于交易之間的影響而破壞交易的穩定性，此外， μ \mu μ鏈采用多方計算協議重建解密密鑰也面臨可擴展問題，
• 在2019年，Deuber等 [ 21 ] \textcolor{blue}{[21]} [21]在無權限設定中提出了第一個可編輯區塊鏈協議，該協議不依賴繁重的加密協議或額外的信任假設，一旦用戶提出修訂，協議就開始一個基于共識的投票期，只有在獲得足夠的投票批準修訂后，版本才在區塊鏈上執行，每個用戶都可查看鏈上的投票數來驗證一個編輯填是否被批準，
• 最近，Thyagarajan等 [ 42 ] \textcolor{blue}{[42]} [42]提出了一個稱為Reparo的通用協議，用于在任何區塊鏈上執行編輯，其中區塊結構通過引入外部資料結構來存盤區塊內容保持不變，然而，他們的投票周期很長，實體化中需要1024個連續的區塊，大約7天時間來確認和發布一個編輯區塊，

最后，該論文依據上面的分析，提出設計了一種具有即時編輯的可編輯區塊鏈協議！

該篇論文提出在無授權設定中，讓受信任的一方持特定的陷門來修改鏈區塊似乎是不合理的，因此，需要選取一個委員會共同決定，且論文指出編輯至少會與委員會規模大小T和底層區塊鏈區塊生成時間t呈線性關系，委員會規模要大，確保誠實的委員居多，論文的目標實作即時的可編輯功能，這意味著編輯鏈要像底層鏈一樣快，

下面我們看下協議的具體設計，

二、 主要內容

2.1 傳統（不可變）區塊鏈

2.1.1 基本特征概述：

• n n n個參與方 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1?,P2?,...,Pn?擁有公私鑰對 ( p k i , s k i ) (pk_i, sk_i) (pki?,ski?)
• slots：表示協議執行被劃分的時間單位（記住，在本文中挺重要的，方便理解）
• c h a i n chain chain：表示鏈，由一個個區塊組成，即 c h a i n : = { B 0 , B 1 , B 2 , . . . B m } chain:=\{B_0,B_1,B_2,...B_m\} chain:={B0?,B1?,B2?,...Bm?}
• B j : = ( h e a d e r j , d j ) B_j:=(header_j, d_j) Bj?:=(headerj?,dj?)：表示區塊;
• h e a d e r j = ( s l j , s t j , G ( d j ) , π j ) header_j=(sl_j, st_j, G(d_j), \pi_j) headerj?=(slj?,stj?,G(dj?),πj?)：表示區塊頭資訊
• d j d_j dj?：表示區塊資料
• s l j ∈ { s l 1 , . . . , s l R } sl_j\in \{sl_1,..., sl_R\} slj?∈{sl1?,...,slR?}：表示slots的序號
• s t j st_j stj?：表示前一個區塊頭的哈希值，即 H ( h e a d e r j ? 1 ) H(header_{j-1}) H(headerj?1?)
• G ( d j ) G(d_j) G(dj?)：表示區塊資料的狀態（實驗中表示區塊資料的Merkle root）
• π j \pi_j πj?：表示包含區塊的一些特殊頭資料（例如在PoS中，表示在生成區塊slot 領導者下用密鑰計算出的簽名 ( s l j , s t j , G ( d j ) ) (sl_j,st_j,G(d_j)) (slj?,stj?,G(dj?))，在PoW中，表示謎題的nonce）

2.1.2 三個重要的安全屬性（后面安全性證明需要用到）：

• 1）Common prefix（公共前綴）：要求所有誠實參與方的鏈是相同的，確認后無法編輯；
• 2）Chain quality（鏈質量）：限制敵手的貢獻，即大多數誠實方貢獻；
• 3）Chain growth（鏈增長）：有效性，隨時可以上傳資料上鏈，

2.2 可編輯區塊鏈協議

2.2.1 可編輯區塊鏈概述：

• 鏈chain更新：表示為 c h a i n ? = c h a i n ∣ ∣ B ? chain^*=chain||B^* chain?=chain∣∣B?，區塊結構與不可變區塊鏈類似，區塊頭資訊增加了一個 i b ib ib，即 h e a d e r j = ( s l j , s t j , G ( d j ) , i b j , π j ) header_j=(sl_j,st_j, G(d_j),ib_j,\pi_j) headerj?=(slj?,stj?,G(dj?),ibj?,πj?).
• B j ? B^*_j Bj??：表示第 j j j個候選編輯區塊，
• i b ib ib：表示區塊的原始狀態，為了維護編輯區塊和它相鄰區塊的關系，將 i b ib ib代表區塊的初始和未編輯狀態，例如，若在編輯區塊 B = ( h e a d e r , d ) B=(header, d) B=(header,d)中還是原區塊資料 d 0 d_0 d0?，則 i b = G ( d 0 ) ib=G(d_0) ib=G(d0?)，其中 h e a d e r = ( s l , s t , G ( d ) , i b , π ) header=(sl,st,G(d),ib,\pi ) header=(sl,st,G(d),ib,π)，

D e f i n i t i o n 3.1 Definition 3.1 Definition3.1（編輯策略 R P \mathcal{R} \mathcal{P} RP)：如果編輯區塊 B ? B^* B?在投票期限內，投票數大于閾值（根據環境不同可動態調整），則表示在序號 s l sl sl的slot上的編輯區塊 B ? B^* B?滿足編輯策略 R P \mathcal{R} \mathcal{P} RP，即 R P ( c h a i n , B ? , s l ) = 1 \mathcal{R} \mathcal{P}(chain, B^*,sl)=1 RP(chain,B?,sl)=1，

2.2.2 具體步驟：（此處根據自身的理解，本人想象的畫了一張步驟圖，供參考）

• 1）提出編輯請求：若參與方 P i P_i Pi?想將編輯區塊 B j ? = ( h e a d e r j ? , d j ? ) B^*_j=(header^*_j,d^*_j) Bj??=(headerj??,dj??)上鏈，先將 B j ? B^*_j Bj??編輯請求廣播至網路，其中 h e a d e r j ? = ( s l j , s t j , G ( d j ? ) , i b j , π j ) header^*_j=(sl_j,st_j,G(d^*_j),ib_j,\pi_j) headerj??=(slj?,stj?,G(dj??),ibj?,πj?)，若他想移除 B j B_j Bj?的所有資料，則 d j ? d^*_j dj??是可以是空資料，
• 2）更新編輯池：從網路中接收到 B j ? B^*_j Bj??后，每個參與方 P i P_i Pi?首先驗證 B j ? B^*_j Bj??是否是一個有效的候選編輯區塊，若是，則將其存盤在自身的編輯池 E P \mathcal{E} \mathcal{P} EP中，每個編輯池 E P \mathcal{E} \mathcal{P} EP中的候選編輯區塊都有一個有效期 t p t_p tp?，在每個新slot的開始，每個參與方 P i P_i Pi?試圖更新自己的編輯池 E P \mathcal{E} \mathcal{P} EP，特別地
  • P i P_i Pi?檢查 B j ? B^*_j Bj??有沒有過期，如果過期了則洗掉它；
  • P i P_i Pi?計算編輯策略 R P ( c h a i n , B j ? , s l j ) \mathcal{R} \mathcal{P}(chain, B^*_j,sl_j) RP(chain,Bj??,slj?)，如果輸出1（感覺應該是輸出0吧），則 P i P_i Pi?洗掉 B j ? B^*_j Bj??，
• 3）對 B j ? B^*_j Bj??投票：對于在 E P \mathcal{E} \mathcal{P} EP中的每個候選編輯區塊 B j ? B^*_j Bj??， P i P_i Pi?檢查他在當前投票期間是否有投票權（這點沒理解，他自己檢查自己嗎？），這是由 C m t ( c h a i n , [ s l ′ ω ] ? ω , P i , p a r a ) Cmt(chain, [\frac{sl'}{\omega}]*\omega, P_i, para) Cmt(chain,[ωsl′?]?ω,Pi?,para)（[ ] 代表向下取整，公式不會打…），其中 s l ′ sl' sl′是當前slot， [ s l ′ ω ] ? ω [\frac{sl'}{\omega}]*\omega [ωsl′?]?ω表示當前投票期間的第一個slot，如果輸出 ( c , p r o o f ) (c, proof) (c,proof)且 c ≠ 0 c\neq 0 c?=0， P i P_i Pi?廣播 ( c , p r o o f ) (c, proof) (c,proof)并附上 H ( B j ? ) H(B^*_j) H(Bj??)的簽名 s i g sig sig，即投票，
• 4）提出新區塊：如果他的編輯池是空的，則序號 s l ′ sl' sl′的slot中的leader以不可變鏈相同方式創建一個區塊并廣播至chain，此外，對于在編輯池中的候選編輯區塊 B j ? B^*_j Bj??，leader試圖用子協議 c o l l e c t V o t e collectVote collectVote（這個演算法后面會介紹）收集并驗證投票期間內 B j ? B^*_j Bj??的選票，如果在 s l ′ sl' sl′slot中的 c o l l e c t V o t e collectVote collectVote回傳vote-proof，則leader將其添加到他的區塊資料中，創建一個新區塊并廣播到chain，
• 5）編輯區塊：對于在編輯池 E P \mathcal{E} \mathcal{P} EP中的每個候選區塊 B j ? B^*_j Bj??，用戶檢查是否 R P ( c h a i n , B j ? , s l j ) = 1 \mathcal{R} \mathcal{P}(chain, B^*_j,sl_j)=1 RP(chain,Bj??,slj?)=1，如果是，則將鏈上的 B j B_j Bj?替換成 B j ? B^*_j Bj??，并從 E P \mathcal{E} \mathcal{P} EP中洗掉 B j ? B^*_j Bj??，

2.2.3 可編輯區塊鏈定義

此小節，作者定義了幾個演算法，包括 v a l i d a t e B l o c k validateBlock validateBlock、 v a l i d a t e C h a i n validateChain validateChain和 v a l i d a t e C a n d validateCand validateCand，以及 c o l l e c t V o t e collectVote collectVote，

• 1) 有效區塊( A l g o r i t h m Algorithm Algorithm 1)：首先根據系統規則檢查區塊B包含的資料的有效性，然后通過合適的函式檢查leader的有效性，最后用leader的公鑰驗證簽名 π \pi π或驗證PoW中謎題亂數 π \pi π，
  
• 2) 有效鏈( A l g o r i t h m Algorithm Algorithm 2)：為了驗證區塊鏈chain，演算法2首先檢查每個區塊 B j B_j Bj?的有效性，然后檢查它與前一個區塊 B j ? 1 B_{j-1} Bj?1?的關系，它有兩種情況，取決于 B j ? 1 B_{j-1} Bj?1?是否是一個編輯過的區塊，如果 B j ? 1 B_{j-1} Bj?1?已編輯完成（即 s t j ≠ H ( h e a d e r j ? 1 ) st_j\neq H(header_{j-1}) stj??=H(headerj?1?)，它的檢查取決于是否滿足編輯策略 R P \mathcal{R} \mathcal{P} RP，當且僅當演算法2輸出1時，我們就說chain是有效的鏈，
  
• 3) 有效候選編輯區塊( A l g o r i t h m Algorithm Algorithm 3)：為了驗證區塊鏈chain上第 j j j個區塊的候選編輯區塊 B j ? B^*_j Bj??，演算法3首先檢查 B j ? B^*_j Bj??的有效性，然后檢查 B j ? 1 B_{j-1} Bj?1?和 B j + 1 B_{j+1} Bj+1?的鏈接關系，其中與 B j + 1 B_{j+1} Bj+1?的鏈接是“old“（如 s t j = H ( s l j , s t j , i b j , i b j , π j ) st_j=H(sl_j,st_j,ib_j,ib_j,\pi_j) stj?=H(slj?,stj?,ibj?,ibj?,πj?)），當且僅當演算法輸出1時，我們就說 B j ? B^*_j Bj??是一個有效的候選編輯區塊，
  

下面將介紹 c o l l e c t V o t e collectVote collectVote負責收集和驗證在 ( s l , s l + ω ? 1 ) (sl, sl+\omega -1) (sl,sl+ω?1) slots內的選票，并將其存盤在緩沖器 m s g s msgs msgs中，大致的步驟如下：

• 通過編輯策略 R P \mathcal{R} \mathcal{P} RP檢查 H ( B j ? ) H(B^*_j) H(Bj??)的投票數，如果它滿足編輯策略，則停止收集，否則開始驗證投票；
• 用投票人的公鑰驗證 H ( B j ? ) H(B^*_j) H(Bj??)上的簽名，并由 V e r i f y C m t ( c h a i n , s l , c , p r o o f , p a r a ′ ) VerifyCmt(chain, sl, c, proof, para') VerifyCmt(chain,sl,c,proof,para′)確認投票人投票的正確性和投票數 c c c；
• 演算法生成一個對所有有效簽名 S I G SIG SIG的聚合簽名 a s i g j asig_j asigj?，聚合相關的證明 P R O O F PROOF PROOF，并回傳它們；
• 聚合簽名可以降低區塊鏈的通信復雜性和存盤開銷，
  

2.3 安全分析（根據自身理解，本人大概描繪了三個證明的思想）

除了common prefix之外，可編輯區塊鏈的安全屬性與不可變區塊鏈的安全屬性基本相同，下面將依次證明這三個屬性的安全性，

由于編輯操作可知，本協議本質上已經不滿足common prefix的原始定義（上面2.1.2節）.具體來說考慮到參與方 P 1 P_1 P1?和 P 2 P_2 P2?分別在 s l 1 , s l 2 sl_1, sl_2 sl1?,sl2? slot上是誠實的，且 s l 1 < s l 2 sl_1<sl_2 sl1?<sl2?，對于一個候選區塊 B j ? B^*_j Bj??替換原始區塊 B j B_j Bj?，后者投票結果被公布在 s l sl sl slot中，且 s l 1 < s l < s l 2 sl_1<sl<sl_2 sl1?<sl<sl2?，在 c h a i n P 1 s l 1 ( v i e w ) chain^{sl_1}_{P_1}(view) chainP1?sl1??(view)中還沒有提出編輯請求，但可能已經在 c h a i n P 2 s l 2 ( v i e w ) chain^{sl_2}_{P_2}(view) chainP2?sl2??(view)中生效，對于這樣的結果，在 c h a i n P 1 s l 1 ( v i e w ) chain^{sl_1}_{P_1}(view) chainP1?sl1??(view)中的原始 B j B_j Bj?保持不變，但它在 c h a i n P 2 s l 2 ( v i e w ) chain^{sl_2}_{P_2}(view) chainP2?sl2??(view)中被替換成為候選 B j ? B^*_j Bj??，

為此，引入一個可擴展協議，稱為可編輯common prefix，并考慮每個編輯操作的效果，它適合于可編輯區塊鏈，如下定義：

D e f i n i t i o n 4.1 Definition 4.1 Definition4.1：（可編輯common prefix）如果對于所有 ( A , Z ) (\mathcal{A},\mathcal{Z}) (A,Z)，存在一個可忽略的函式 n e g l negl negl，使得對每個足夠大的 λ ∈ N \lambda \in N λ∈N和每個 k ≥ k 0 k\geq k_0 k≥k0?都成立，我們就說該區塊鏈協議 ∏ \prod ∏滿足 k 0 k_0 k0?-可編輯common prefix：
P r [ v i e w ← E X E C ∏ ( A , Z , λ ) : r e d a c t p r e f i x k ( v i e w ) = 1 ] ≥ 1 ? n e g l ( λ ) Pr[view\leftarrow EXEC^{\prod}(\mathcal{A},\mathcal{Z},\lambda):redactprefix^k(view)=1]\geq 1-negl(\lambda) Pr[view←EXEC∏(A,Z,λ):redactprefixk(view)=1]≥1?negl(λ)
其中 A A A表示敵手， Z Z Z表示環境，

接下來，根據以上這個定義，其證明路線為：

• 1）先考慮ideal-world協議 ∏ i d e a l \prod_{ideal} ∏ideal?可以訪問一個理想化功能 F t r e e \mathcal{F}_{tree} Ftree?，并滿足三個安全屬性，

• 2）再展示了real-world協議安全地模擬了 ∏ i d e a l \prod_{ideal} ∏ideal?，（這里就不再敘述，建議看原文）

2.3.1 證明 ∏ i d e a l \prod_{ideal} ∏ideal?滿足可編輯common prefix，

證明：假設存在 B j ? B^*_j Bj??的prefix與其他誠實方的鏈不相等，它必須根據ideal協議獲得足夠選票，則編輯策略 R P \mathcal{R} \mathcal{P} RP得到滿足，即 ∏ i d e a l \prod_{ideal} ∏ideal?滿足 k 0 k_0 k0?-可編校common prefix，

2.3.2 證明 ∏ i d e a l \prod_{ideal} ∏ideal?滿足chain quality，

證明：假設將 B j B_j Bj?替換成惡意的 B j ? B^*_j Bj??，敵手增加鏈中惡意區塊的比例，以打破chain quality屬性，然而根據ideal協議，編輯區塊只當票數超過敵對委員數時才被采用，即 ∏ i d e a l \prod_{ideal} ∏ideal?滿足chain quality，

2.3.3 證明 ∏ i d e a l \prod_{ideal} ∏ideal?滿足chain growth，

證明：根據ideal協議，任何編輯操作不改變鏈長度（不洗掉區塊），且新區塊上鏈不受投票影響，即 ∏ i d e a l \prod_{ideal} ∏ideal?滿足chain growth，

2.4 實體化

假設S為系統總權益，T為投票委員會的預期權益數，委員會中誠實用戶的權益至少為n，委員會成員只在每個投票期間的第一個slot 上選出 ( s l , s l + w ? 1 ) (sl, sl+w-1) (sl,sl+w?1)之間的 s l sl sl，可以根據具體網路環境設定 w w w，保證在 w w w slots之后所有用戶都能以更大概率收到選票，

2.4.1 可編輯PoS區塊鏈

• 1）檢查委員會成員Cmt：Cmt函式用私鑰 s k i sk_i ski?和權益 s i s_i si?檢查 P i P_i Pi?是否在slot s l sl sl中的委員會成員和輸出 ( c , p r o o f ) (c,proof) (c,proof)，如演算法4，首先，Cmt函式用VRF以私有或非互動的方式去隨機選擇投票人；為了選擇投票人與他們的權益成比例，把每個單位的stake看作是不同的子用戶，用 s i s_i si?表示，且每個單位的選擇概率為 p = T S p=\frac TS p=ST?，S為系統總stakes，T為委員會預期stakes值，而子用戶 s i s_i si?中選擇 q q q的概率服從二項分布 B ( q ; s i , p ) = C ( s i , q ) p q ( 1 ? p ) s i ? q B(q;s_i,p)=C(s_i,q)p^q(1-p)^{s_i-q} B(q;si?,p)=C(si?,q)pq(1?p)si??q，其中 C ( s i , q ) = s i ! q ! ( s i ? q ) ! C(s_i,q)=\frac {s_i!}{q!(s_i-q)!} C(si?,q)=q!(si??q)!si?!?且 ∑ q = 0 s i B ( q ; s i , p ) = 1 \sum^{s_i}_{q=0}B(q;s_i,p)=1 ∑q=0si??B(q;si?,p)=1，為了確定參與方中子用戶有多少，演算法從 I c I^c Ic中將區間 [ 0 , 1 ) [0, 1) [0,1)劃分為連續區間，若 h a s h 2 h a s h l e n \frac{hash}{2^{hashlen}} 2hashlenhash?落在 I c I^c Ic內，意味著 P i P_i Pi?的 c c c個子用戶(c個投票)被選中，其中 h a s h l e n hashlen hashlen表示哈希的bit長度，
  

• 2）驗證委員會成員VerifyCmt：演算法5中函式VerifyCmt用 P i P_i Pi?的公鑰 p k i pk_i pki?和proof驗證 P i P_i Pi?是權重為c的委員，它首先用 V e r i f y V R F p k i ( h a s h , π , s e e d ∣ ∣ s l ) VerifyVRF_{pk_i}(hash,\pi,seed||sl) VerifyVRFpki??(hash,π,seed∣∣sl)驗證proof，然后驗證 h a s h 2 h a s h l e n \frac{hash}{2^{hashlen}} 2hashlenhash?落在區間 I c I^c Ic，

• 3）引數選擇：如前面所述，將每個權益的單元視為不同的“sub-user”，例如，若用戶 U i U_i Ui?有 s i s_i si?個權益則他有 s i s_i si?個單元，當提出修訂建議時，將從所有子用戶中選出一個投票委員會，委員會的預期人數T是固定的，并且子用戶被選中的概率為 T S \frac{T}{S} ST?，然后準確抽取K個子用戶的概率為： P = C S K ρ S K ( 1 ? ρ S ) S ? K = S ? ( S ? K + 1 ) T K S K T K K ! ( 1 ? T S ) ( S ? K ) P=C^K_S\rho^K_S(1-\rho_S)^{S-K}=\frac{S\cdots(S-K+1)T^K}{S^K}\frac{T^K}{K!}(1-\frac{T}{S})^{(S-K)} P=CSK?ρSK?(1?ρS?)S?K=SKS?(S?K+1)TK?K!TK?(1?ST?)(S?K)
  若K為定值，有 lim ? S → ∞ S ? ( S ? K + 1 ) S K = 1 \lim_{S\to \infty}\frac{S\cdots(S-K+1)}{S^K}=1 limS→∞?SKS?(S?K+1)?=1和 lim ? S → ∞ ( 1 ? T S ) ( S ? K ) = e ? T \lim_{S\to \infty}(1-\frac{T}{S})^{(S-K)}=e^{-T} limS→∞?(1?ST?)(S?K)=e?T,則概率逼近
  P = T K K ! e ? T P=\frac{T^K}{K!}e^{-T} P=K!TK?e?T
  用#good和#bad分別表示委員會中誠實和惡意的成員數，假設大多數是誠實的，則滿足以下條件，

  • # g o o d ≥ 1 / 2 ? T good\geq 1/2·T good≥1/2?T，當誠實委員數達到<1/2時，違反了這個條件，由上面公式可知，正好抽K個誠實委員的概率是 ( h ? T ) K K ! e ? h ? T \frac{(h·T)^K}{K!}e^{-h·T} K!(h?T)K?e?h?T，其中 h ( h > 1 / 2 ) h(h>1/2) h(h>1/2)是系統中誠實的持股比例，因此，違反這條件的概率為；
    ∑ K = 0 T / 2 ? 1 ( h T ) K K ! e ? h T ( 1 ) \sum_{K=0}^{T/2-1}\frac{(hT)^K}{K!}e^{-hT} \qquad \qquad \qquad \qquad \qquad \qquad \qquad(1) K=0∑T/2?1?K!(hT)K?e?hT(1)
  • # b a d < 1 / 2 ? T bad<1/2·T bad<1/2?T，由上可知，我們抽取L個惡意委員會成員的概率為 ( ( 1 ? h ) T ) L L ! e ? ( 1 ? h ) T \frac{((1-h)T)^L}{L!}e^{-(1-h)T} L!((1?h)T)L?e?(1?h)T，因此，滿足條件的概率由公式給出為：
    ∑ L = 0 T / 2 ? 1 ( ( 1 ? h ) T ) L K ! e ? ( 1 ? h ) T ( 2 ) \sum_{L=0}^{T/2-1}\frac{((1-h)T)^L}{K!}e^{-(1-h)T} \qquad \qquad \qquad \qquad \qquad \qquad \qquad(2) L=0∑T/2?1?K!((1?h)T)L?e?(1?h)T(2)

  F F F是引數，它標志著兩種情況的失敗概率可以忽略不計，根據經驗設定為 F = 5 ? 1 0 ? 9 F=5*10^{-9} F=5?10?9我們目標是最小化 T T T，同時保持上面公式（1）或（2）的概率不超過F，如果 T T T的某個值以 1 ? F 1-F 1?F的概率滿足這兩個條件，那么任何較大的 T T T的值也以至少 1 ? F 1-F 1?F的概率滿足，基于上述觀察，為了找到最優的 T T T，首先令 T T T任意大的值，例如 1 0 4 10^4 104，然后檢查是否滿足這兩個條件，若滿足兩個條件則減小T（此處應該不滿足則減小T，論文寫錯了吧），再檢查，持續這個程序，直到兩個條件都滿足，

  在本文的系統實作中，我們假設誠實風險的比例為0.65，因此我們選擇𝑇= 1000，（后續2.5節再詳細介紹）

• 4）誠實用戶比例：只需證明委員會中誠實用戶的比例至少為1/2.如果敵手A能夠預知地確保哪個用戶將成為投票委員會成員，那么他可以自適應地腐敗并模范該用戶，使委員會中誠實用戶的比例小于1/2，然而，底層VRF的唯一性，敵手的獲勝概率只有可忽略的 ( 1 2 ) h a s h l e n (\frac12)^{hashlen} (21?)hashlen獲勝，況且下一投票期間的委員會重新選舉，故不會有任何不可忽略的優勢，

2.4.2 可編輯PoW區塊鏈

為了根據計算能力分布獲得足夠數量的委員會，并確保委員會中的誠實多數，只需要收集足夠的PoW迷題解決方案，這可以很容易地通過創建一個“虛擬選擇”程式來實作PoW帶有更大的難度引數D，然而，敵手可以通過保留攻擊（若敵手在 s l sl sl之前生成了一個更長的鏈，它將暫時扣留該鏈，并開始尋找solution，然后在slot位置敵手發布它的鏈和solutiion，因此他有更多機會來尋找solution）提前找到“虛擬迷題解決方案”，為了組織這種攻擊，在slot連續的位置選舉委員會，這樣大多數委員會是誠實的，即使在保留攻擊，與POS實體化類似，使用與網路相關的引數w來確保所有用戶都將以大概率獲得投票，其中 w ≥ r w\geq r w≥r，

• 1）檢查委員會成員Cmt：在演算法6中的Cmt函式中，若P能在 ( s l , s l + r ? 1 ) (sl,sl+r-1) (sl,sl+r?1)之間找到一些PoW困難引數 D D D的虛擬難題solution，則 P P P被選為委員會，且賦予 P P P為權重 c c c（即，解答solution的個數），委員會成員證明包括相應難題solution的proof，
  
  

• 2）驗證委員會成員VerifyCmt：這個演算法7與演算法6類似，通過解答計算哈希值，用公鑰 p k pk pk驗證 P P P是否是委員會成員，

• 3）引數選擇：假設敵手能在 t t t slots之前超過誠實節點找到大多數的難題solution且在 r r r slots中選舉委員會，假設 h = 1 2 + ? ( ? ∈ ( 0 , 1 2 ) h=\frac 12+\epsilon(\epsilon \in (0,\frac 12) h=21?+?(?∈(0,21?)是底層區塊鏈中誠實節點的比例，令 α = D 2 l h n \alpha=\frac{D}{2^l}hn α=2lD?hn和 β = D 2 l ( 1 ? h ) n \beta=\frac{D}{2^l}(1-h)n β=2lD?(1?h)n分別表示每個slot中誠實節點和腐敗節點所能找到難題solution的預期數量，其中 l l l為哈希函式 H ( ? ) H(·) H(?)的輸出長度， n n n為節點總數，

  本文用 N A N_A NA?表示敵手從slot ( s l ? t , s l + r ? 1 ) (sl-t, sl+r-1) (sl?t,sl+r?1)中找到難題solution的最大數量， N H N_H NH?表示誠實節點從slot ( s l , s l + r ? 1 ) (sl,sl+r-1) (sl,sl+r?1)找到難題solution的最小數量，特別地，根據Chernoff界限[17]，對于任意 δ > 0 \delta>0 δ>0，除了可忽略概率 p 1 = e x p ( ? δ ? m i n { δ , 1 } ? β ( t + r ) 3 ) p_1=exp(-\frac{\delta·min\{\delta,1\}·\beta(t+r)}{3}) p1?=exp(?3δ?min{δ,1}?β(t+r)?)，它滿足 N A ≤ ( 1 + δ ) β ( t + r ) N_A\leq(1+\delta)\beta(t+r) NA?≤(1+δ)β(t+r)，類似，對任意 δ ∈ ( 0 , 1 ) \delta \in (0,1) δ∈(0,1)，除了可忽略概率 p 2 = e x p ( ? δ 2 α r 2 ) p_2=exp(-\frac{\delta^2\alpha r}{2}) p2?=exp(?2δ2αr?)，它滿足 N H ≥ ( 1 ? δ ) α r N_H\geq (1-\delta )\alpha r NH?≥(1?δ)αr，若設定委員會成員大多數是誠實的，然后需要確保 N H > N A N_H>N_A NH?>NA?，并且滿足以下條件 ( 1 + δ ) β ( t + r ) < ( 1 ? δ ) α r (1+\delta)\beta(t+r)<(1-\delta)\alpha r (1+δ)β(t+r)<(1?δ)αr
  因此，有 r > t ( 1 ? δ ) h ( 1 + δ ) ( 1 ? h ) ? 1 r>\frac{t}{\frac{(1-\delta)h}{(1+\delta)(1-h)}-1} r>(1+δ)(1?h)(1?δ)h??1t?( t t t表示敵手可保留區塊B的最長slots數)，

  考慮這樣一種情況，當敵手保留一些區塊時，在最長有效鏈中挖掘 k 0 k_0 k0?個新區塊，其中 k 0 k_0 k0?是common prefix 引數，根據common prefix屬性，這些保留區塊永遠不會出現在誠實節點鏈中，因此， t t t應該是小于最長鏈增加至少 k 0 k_0 k0?區塊的最小時間，根據chain growth屬性[37]可知， t ≈ k 0 α ′ t\approx \frac{k_0}{\alpha'} t≈α′k0??，其中 α ′ = D ′ 2 ? h n \alpha'=\frac{D'}{2^\ell}hn α′=2?D′?hn，

例如：在Bitcoin中，令 k 0 = 6 , h = 0.65 , δ = 0.1 , D ′ 2 ? n = 1 k_0=6, h=0.65, \delta=0.1, \frac{D'}{2^\ell}n=1 k0?=6,h=0.65,δ=0.1,2?D′?n=1，根據上式可知 r > 1.93 t r>1.93t r>1.93t，為不失一般性，設定 r = 2 t r=2t r=2t，算出 t = 10 , r = 20 t=10,r=20 t=10,r=20，進一步，設定 p 1 = e x p ( ? 13 ) , p 2 = e x p ( ? 25 ) p_1=exp(-13), p_2=exp(-25) p1?=exp(?13),p2?=exp(?25)，則 D = 5000 h r D ′ ≈ 385 D ′ D=\frac{5000}{hr}D'\approx385D' D=hr5000?D′≈385D′，即
( 1 + δ ) β ( t + r ) = ( 1 ? h ) ( 1 + δ ) 5000 h r ( t + r ) ≈ 4443 (1+\delta)\beta(t+r)=(1-h)(1+\delta)\frac{5000}{hr}(t+r)\approx4443 (1+δ)β(t+r)=(1?h)(1+δ)hr5000?(t+r)≈4443
所以，只有當一個編輯區塊獲得超過4443個投票時，它才會被批準，

2.5 實作評估與分析

• 實驗環境：c語言(C11版本)撰寫了仿真Cardano SL的PoS鏈，Ubuntu 16.04(64bits)系統, 2.20GHz Intel Core i5-5200U CPU and 8GB記憶體，
• 其他引數： h = 0.65 h=0.65 h=0.65(即敵手最多控制35%的stakes)，委員會規模 T = 1000 T=1000 T=1000，指定每個區塊最多包含10筆交易，

2.5.1 實驗一：分析編輯的vote和proof開銷

• vote和proof產生的計算開銷很小
• 滿足了有效編輯的必要條件

2.5.2 實驗二：評估編輯proof如何影響共識的性能

• 帶有編輯proof會持續產生額外的延遲
• 僅需要約0.7s來驗證編輯proof

2.5.3 實驗三：驗證已編輯區塊鏈的額外成本

• 驗證鏈的延遲隨著編輯次數的增加呈線性增加
• 即使50%的區塊被編輯，成本仍然可以接受

三、結論與思考

3.1 本文總結

• 1）提出了具有即時編輯功能的區塊鏈構造方法(實驗二表現了即時性)；
• 2）首次定義了可編輯區塊鏈的理想化功能 F t r e e \mathcal{F}_{tree} Ftree?，并證明了安全性(創新點)；
• 3）基于PoS和PoW共識的區塊鏈上進行了實體化(雖然實驗僅仿真了PoS情況)，

3.2 我的思考

本篇論文是比較好的文章，如果深入閱讀的話會發現許多有用的知識，不管是加深對不可變區塊鏈的理解，還是創新性的了解可編輯區塊鏈，都會有個很好的認識，值得仔細研讀，

另外，作者也提出可以后續進一步優化減少存盤proof的開銷，以及就像前面提出的問題一樣，為什么要用可編輯區塊鏈？可編輯與不可變區塊鏈的防篡改實則是沖突的，該如何共存？為什么我們不直接用分布式資料庫呢，它也可以實作編輯和存盤？這些問題都值得深思，或許就是下一個研究點，

（還有一些具體的思考和想法這里不便透露，歡迎合作交流！）