这篇文章是今年发表在IACR Cryptol.ePrint Arch上的一篇区块链相关论文，质量很不错，值得深入研读，有很多学习的地方。
主要内容是：在许多场景下，区块链的immutability(不可变性)同样带来了许多弊端。例如，存储一些非法数据在链上将带来诸多挑战。因此，本文设计了一种可编辑区块链构造的通用协议，该协议在无授权设置下可即时编辑，并在基于PoS和PoW共识区块链进行了实例化。最后，为编辑协议开发了一个概念验证(Proof of Concept, PoC)实现和应用该协议，实验表明较高的效率，引起的开销也很小。
下面将大致按照文章结构内容，并结合自己读后的学习笔记进行梳理和归纳，可能会有整理不当的地方，仅代表个人理解，详细内容还是建议看原文！
- 原文链接：Redactable Blockchain Protocols with Instant Redaction
（长文警告，本篇大约1.6w个字，谨慎阅读！）
文章目录预览- Redactable Blockchain Protocols with Instant Redaction(具有即时编辑功能的可编辑区块链)
- 文章主要贡献：
- 一、写作背景
- 二、 主要内容
- 2.1 传统（不可变）区块链
- 2.1.1 基本特征概述：
- 2.1.2 三个重要的安全属性（后面安全性证明需要用到）：
- 2.2 可编辑区块链协议
- 2.2.1 可编辑区块链概述：
- 2.2.2 具体步骤：（此处根据自身的理解，本人想象的画了一张步骤图，供参考）
- 2.2.3 可编辑区块链定义
- 2.3 安全分析（根据自身理解，本人大概描绘了三个证明的思想）
- 2.3.1 证明 ∏ i d e a l prod_{ideal} ∏ideal满足可编辑common prefix。
- 2.3.2 证明 ∏ i d e a l prod_{ideal} ∏ideal满足chain quality。
- 2.3.3 证明 ∏ i d e a l prod_{ideal} ∏ideal满足chain growth。
- 2.4 实例化
- 2.4.1 可编辑PoS区块链
- 2.4.2 可编辑PoW区块链
- 2.5 实现评估与分析
- 2.5.1 实验一：分析编辑的vote和proof开销
- 2.5.2 实验二：评估编辑proof如何影响共识的性能
- 2.5.3 实验三：验证已编辑区块链的额外成本
- 三、结论与思考
- 3.1 本文总结
- 3.2 我的思考
- 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_jin {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）
- 1）Common prefix（公共前缀）：要求所有诚实参与方的链是相同的，确认后无法编辑；
- 2）Chain quality（链质量）：限制敌手的贡献，即大多数诚实方贡献；
- 3）Chain growth（链增长）：有效性，随时可以上传数据上链。
- 链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 cneq 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∗。
此小节，作者定义了几个算法，包括 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_jneq 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，并返回它们；
- 聚合签名可以降低区块链的通信复杂性和存储开销。
除了common prefix之外，可编辑区块链的安全属性与不可变区块链的安全属性基本相同，下面将依次证明这三个属性的安全性。 为此，引入一个可扩展协议，称为可编辑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
kgeq k_0
k≥k0都成立，我们就说该区块链协议
∏
prod
∏满足
k
0
k_0
k0-可编辑common prefix： 接下来，根据以上这个定义，其证明路线为： 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。（这里就不再叙述，建议看原文） 证明：假设存在
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。 证明：假设将
B
j
B_j
Bj替换成恶意的
B
j
∗
B^*_j
Bj∗，敌手增加链中恶意区块的比例，以打破chain quality属性。然而根据ideal协议，编辑区块只当票数超过敌对委员数时才被采用，即
∏
i
d
e
a
l
prod_{ideal}
∏ideal满足chain quality。 证明：根据ideal协议，任何编辑操作不改变链长度（不删除区块），且新区块上链不受投票影响，即
∏
i
d
e
a
l
prod_{ideal}
∏ideal满足chain growth。 假设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之后所有用户都能以更大概率收到选票。 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=0siB(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_Srho^K_S(1-rho_S)^{S-K}=frac{Scdots(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)TKK!TK(1−ST)(S−K)
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获胜。况且下一投票期间的委员会重新选举，故不会有任何不可忽略的优势。 为了根据计算能力分布获得足够数量的委员会，并确保委员会中的诚实多数，只需要收集足够的PoW迷题解决方案。这可以很容易地通过创建一个“虚拟选择”程序来实现PoW带有更大的难度参数D。然而，敌手可以通过保留攻击（若敌手在
s
l
sl
sl之前生成了一个更长的链，它将暂时扣留该链，并开始寻找solution。然后在slot位置敌手发布它的链和solutiion，因此他有更多机会来寻找solution）提前找到“虚拟迷题解决方案”。为了组织这种攻击，在slot连续的位置选举委员会，这样大多数委员会是诚实的，即使在保留攻击。与POS实例化类似，使用与网络相关的参数w来确保所有用户都将以大概率获得投票，其中
w
≥
r
wgeq 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
α=2lDhn和
β
=
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_Aleq(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^2alpha r}{2})
p2=exp(−2δ2αr)，它满足
N
H
≥
(
1
−
δ
)
α
r
N_Hgeq (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 考虑这样一种情况，当敌手保留一些区块时，在最长有效链中挖掘
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
α
′
tapprox 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=hr5000D′≈385D′。即 本篇论文是比较好的文章，如果深入阅读的话会发现许多有用的知识，不管是加深对不可变区块链的理解，还是创新性的了解可编辑区块链，都会有个很好的认识，值得仔细研读。 另外，作者也提出可以后续进一步优化减少存储proof的开销，以及就像前面提出的问题一样，为什么要用可编辑区块链？可编辑与不可变区块链的防篡改实则是冲突的，该如何共存？为什么我们不直接用分布式数据库呢，它也可以实现编辑和存储？这些问题都值得深思，或许就是下一个研究点。 （还有一些具体的思考和想法这里不便透露，欢迎合作交流！）
由于编辑操作可知，本协议本质上已经不满足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
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[viewleftarrow 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表示环境。
2.3.1 证明
∏
i
d
e
a
l
prod_{ideal}
∏ideal满足可编辑common prefix。
2.4.2 可编辑PoW区块链
若K为定值，有
lim
S
→
∞
S
⋯
(
S
−
K
+
1
)
S
K
=
1
lim_{Sto infty}frac{Scdots(S-K+1)}{S^K}=1
limS→∞SKS⋯(S−K+1)=1和
lim
S
→
∞
(
1
−
T
S
)
(
S
−
K
)
=
e
−
T
lim_{Sto 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!TKe−T
用#good和#bad分别表示委员会中诚实和恶意的成员数。假设大多数是诚实的，则满足以下条件。
∑
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−1K!(hT)Ke−hT(1)
∑
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−1K!((1−h)T)Le−(1−h)T(2)
因此，有
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数)。
(
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.1 实验一：分析编辑的vote和proof开销
2.5.2 实验二：评估编辑proof如何影响共识的性能
2.5.3 实验三：验证已编辑区块链的额外成本
三、结论与思考
3.1 本文总结
3.2 我的思考
