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

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

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

    贡献：

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

协议详细描述：

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

  用户提出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，从整个链的头部开始验证。 

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

• 提出修改。算法很简单。

• 验证候选链。

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

安全分析：

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

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

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

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

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

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

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

与比特币的结合：

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

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

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

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

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

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

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

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

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

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

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

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

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

    最后Discussion，

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

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

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

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