Redactable Blockchain in the Permissionless Setting (S&P 2019)

    摘要简介:比特币中可能存在有害的信息。之前的可编辑区块链都有额外的信任假设,因此不实用。这篇文章旨在提出一个能轻松集成到比特币中不依赖加密、信任假设的可重定义区块链。策略规定了修订的要求和约束,如果一个修订收到足够多的投票,那么操作将执行。另外,提供了正式的安全定义和证明,表明协议不受未经协商一致同意的修订所影响。 Proof-of-concept说明相比immutable区块链,chain validation的开支很小。

    之前有人在permissioned区块链中使用变色龙哈希来解决修改的问题。基于门限共享的知识,使用变色龙哈希进行碰撞,来保证修改数据后的一致性。但是在无许可链中,无修改痕迹的修改方法不合理。还有一种方法,交易的唯一未加密版本是活跃的交易。解密密钥在矿工间共享。但是这种方法存在伸缩性问题,并且不安全。

    贡献:

  • 可编辑的区块链协议。编辑操作可以由任何用户提出;协议基于PoW,但是并不局限特定的共识算法。提出的协议还支持公开验证。
  • 形式化分析。规定了可编辑区块链的所有必要属性,并证明满足这些属性。

协议详细描述:

    编辑某个区块时,遵从以下协议

propose В; 
Voting l»riod (С) 
(а) Proposing а redaction Щ for the Ь1осК В] 
Р(С, В;) = accept 
ш-гз-гз-гз-гз-гз=п 
ф) After а successfu1 voting phase, В; rep1aces В] in the chain

  用户提出edit请求,包括想要修改的区块的index和一个替换这个区块的候选区块。如果矿工收到了修改的请求,则先用旧的state 信息验证候选块,遵循的规则:(1)是否包括前置区块的信息。(2)解决了工作量证明。(3)不会让下一个区块失效。 如果候选区块是valid的,那么矿工可以对它进行投票,只要将请求的hash值包括在矿工挖掘的下一个区块里即可。使用hash可以单独地确定一个请求。投票结束后,每个人都可以验证编辑请求是否被批注,也就是获得了足够多的投票。

预备:

  • k是安全参数,a←A(in)表示算法A在输入in时的output。
  • 安全区块链的性质:采用同步的网络。区块链需要满足persistence和liveness,意味着一段时间后所有节点会有一个一致的链,诚实用户发布的交易最终都会被包含在内。
    • persistence:如果一个用户宣称某个transaction是稳定的,其他节点在被查询时要么返回特定位置的transaction,要么不反馈任何其他的冲突交易为稳定的。(没看懂) 只有在k个区块产生后,某个区块才是被认为稳定的。
    • liveness:如果所有诚实的用户都想include一个区块,那么当相应的确认时间槽过去后,所有用户在诚实地进行查询和相应时都会汇报transaction是稳定的。
  • 执行模式。协议以模拟原子时间步的方式执行。每一轮开始诚实的节点从环境中接收输入,每一轮结束诚实的节点向环境中输出消息。
    • Adversary不能修改诚实节点广播的消息内容。
    • 任何时候恶意节点都可以入侵诚实节点。
    • 任何时候恶意节点都能脱离控制诚实节点。这个时候诚实节点被当做新加入。

编辑区块的细节:

    首先考虑常规的immutale区块链,节点从环境中接收输入,然后agree on排序的ledger。

    然后介绍Editable区块链。Editable继承了所有immutable的性质。validateChain和validateBlock有不同。除此之外还多了两个接口:

  • proposeEdit,用来对某个区块进行修改,返回值是candidate block。
  • validateCand,如果candidate block正确,返回1。

    首先专注于只能修改一次的协议,然后拓展到可以无穷修改的协议。

    采用的Blockchain Policy: 这个协议用来决定一个edit是否合法。

协议描述:

    每个节点从网络中收集候选区块,然后进行验证,验证区块是否合法。采用的方法应该是之前介绍的例如是否包含前置信息,是否解决了PoW之类的方法,来验证是否合法。然后在进行确认的interval中验证协议P是否已经满足。如果还在决定中则什么都不做。如果一个user想确认所提议的edit,只需要将propose的哈希值加入data (x) (data是什么?是用来存储未确认的transaction的数据库)。如果一个用户要提出修改,需要调用proposeEdit的接口,这个接口会返回一个候选区块。

  • 链验证协议。协议的输入是链C,从整个链的头部开始验证。 
2: 
3: 
5: 
6: 
8: 
9: 
Algorithm 1: validateChain (implements r/ .validateChain) 
input : Chain C (Bl, , Bn) of length n. 
output: {0, 1} 
1 then return F'.validateBlock(B1); 
if 
j 
while j 2 2 do 
Head (C) when j — 
if F'.validateBlock(Bj) = 0 then return 0; 
sj = yj-l) 
if 
then 
(sj = yj_l, yj-l)) A 
else if 
(F'.validateCand(C, Bj_l) = 1) A (P(C, Bj-l) = 
accept) then 
j. 
else return 0; 
return 1;

总的来看,就是从链头开始验证,如果没被改过那么这个区块的验证就正确移到下一个;如果被改过就要满足协议以及候选区块验证才能算正确。

  • 提出修改。算法很简单。
Algorithm 3: proposeEdit (implements r' .proposeEdit) 
input : Chain C = (Bl, 
, Bn) of length n, an index 
j e [n], and the new data x* 
1: 
2: 
3: 
output: A candidate block 
Parse BJ < 
sj, xj, ctrj, yj); 
Build the candidate block B* 
return Bi•, 
(s • x* ctrj,yj);
  • 验证候选链。
Algorithm 4: validateCand (implements r'.vaIidateCand) 
input : Chain C = (Bl, • , Bn) of length n, and a 
candidate block Bt for an edit. 
output: {0, 1} 
l: Parse = < 
s • ctrj,yj); 
if F'.validateBlock(Bt) = 0 then return 0; 
2: 
sj—l, x j —1, ctrj—l' Yj—l); 
3: Parse By-I 
(sj+l, Xj+l, ctrj+l, Y) +1); 
4: Parse Bj+l 
if = H (ctrj—l, yj_l, yj_l) A s j +1 = H (ctrj,yj, yj) 
5: 
then return 
1; 
else return 0; 
6:

思路非常简单,首先验证新的区块满不满足指向前面的哈希,然后看原来旧的链接是不是还保留。也就是说,通过在一个位置直接再加一个区块来修改,而链靠的是原来的旧状态来保证。

安全分析:

    证明可编辑区块链和不可编辑的安全性一样。

    第一个定理说对任意策略P,区块增长方式都相同。证明是因为策略不影响增长方式。

    Chain Quality。由诚实节点所持有的adversary区块不超过一定比例。

    定理二说明如果H是安全哈希,那么可编辑块 链质量和不可编辑的一样。一个对手可能将正常的区块改成有恶意信息的区块。如果A提议一个恶意区块,因为对手掌握的算力为u,那么在投票阶段它最多挖矿u。而一个恶意的区块B*只有在足够多的诚实节点投票的时候才能被确认。 注意到adversary可能提议看起来正常的区块来在voting阶段欺骗诚实节点,但是安全哈希函数组织这种情况。

    共同前缀。可编辑的区块链不满足共同前缀,因为可能存在区块被修改但是长链没同步的情况。所以作者提出了另外的定义。

    可编辑链的共同前缀。定义是指,共同前缀相同如果1:短链属于长链;2:在修剪掉长链多出来的l2-l1+k这一部分后,所有的修改过的区块Bj*都满足策略P。

    定理3,如果immutable区块链满足共同前缀么,那么可编辑区块链满足可编辑链共同前缀。 证明是如果没有编辑,那么肯定满足;如果有修改,那么如果修改被认可了, 那么肯定收到了足够多的投票。安全哈希保证不会出现冲突。

与比特币的结合:

    为了简单起见,只考虑每个区块进行一次更改。如果一个提出的修改是合理的,应该满足这些条件:

  • 它应该跟被替换的交易一样,除了删掉了一些数据。
  • 只能移除一些不会被花掉的数据。
  • It does not redact votes for other redactions in the chain。
  • 在1024个周期收到了超过50%的投票。

    当投票结束时,所有节点删除数据。 

    还狡辩了一下为什么不替换可以花掉的交易。

  提出的新区块结构:为了达到redaction,文章认为区块头需要有一个用来存放旧默克尔树的位置。如果一个区块刚创建未被更改过,则这个部分和默克尔树一样。

    区块验证:首先验证transactions。没改过的transactions和immutable区块链中相同的验证方法。被改过的transaction如图所示。

тхз 
(а) Non-redacted. 
тх7, тм,о 
ты 
тхз 
(Ь) Redacted transaction

其中Tx1ID是Tx1的hash值。采用这种方式能在一个transaction被改的时候仍然保证对旧状态的验证。(保留hash值应该是能继续构建起witness,类似默克尔树一样)。用来提议修改的editTx这个transaction会广播到网络中,然后应该会被添加到链中? 最后验证一下PoW。

    链验证。要验证完整的链一个矿工需要验证所有的blocks。如果链断了,则检查是否被修改过。如果修改没有被许可,或者merkle_root在被修改的区块中与被提议的修改transaction不符合,或者一个本该被修改的操作没执行,验证都失败。

    Transaction的连续性。又说了一遍不能修改可以花掉的transactions。

    强调redactable的主要目的是为了移除恶意信息阻止传播,但是不能防止恶意节点本地存储恶意信息。提出存储本该被删掉的信息的节点应该被惩罚(liable)。怎么罚?

    最后作者指出,系统的操作应该公开可见,如果一个矿工投票支持可消费的数据导致了不连续性,可能导致用户不再使用这个系统。但是作者认为矿工投入了大量资金,所以从利益政策的角度出发,他们不会做允许这样的操作。

    最后,本文提出的方法允许数据的所有者声明确实是它们的数据被删除了,因为用hash能够验证旧的数据,旧数据的hash留在链上,这样就能阻止系统删除良性的数据。同时这个协议依靠hash来防止虚假的声明。

    实验部分:做了与immutable的对比,不同修改数量的开支,以及不同投票参数的开支。感觉实验做的不是很多。

    最后Discussion,

    对于未批准的编辑,投票不足,用户可以再链中验证。因为大多数矿工是诚实的,所以用户接受到的能认可的编辑是成熟的。

    审核候选区块。反对使用默认策略,比如没有审查的时候投票给候选区块。没看懂。

    editTx的开支可以组织DoS攻击,因为要花钱。

    假受害人没法成功声明受害,因为hash抗碰撞。

发表评论

电子邮件地址不会被公开。 必填项已用*标注