观点 | 关于错误性证明（Fault Proof）的沉思（一）

显示全部楼层 · 发表于 2020-1-19 12:00:04

编者注：一般而言，我们会将 Fault Proof 认为是与 Layer-2 相关的概念，是 Layer-2 将自己的状态报告给 Layer-1 时采取的模式。但在本文中，作者使用的是广义的错误性证明概念，考虑的是如何设计一种错误性证明模式，使 SPV 节点（近似于所谓的 “轻节点”）获得更高的安全性。

错误性证明（Fraud Proof）是个极为复杂且烦人的概念，但如果你想知道我的一些心得，请耐着性子跟我一起思考吧。

-Benihime Morgan 的河流艺术作品-

简而言之，言而简之

SPV 节点非常易于运行及扩展；借助错误性证明，SPV 节点（Simplified Payment Verification）可以具备和全节点相同的安全性。
我要在此引入 “ SPV+ ” 模式；常规的 SPV 节点只需要保存区块头（存储增量每年约 4MB ），而 SPV+ 节点还需要保存每个区块中的第一笔及最后一笔交易（存储增量每年约 115 MB）。
“SPV+” 节点必须与一个全节点建立支付通道，或是建立一个 LN 连接。
每验证一个区块的正确性，SPV+ 节点都必须向这些全节点支付小额费用；我估计这笔费用不会超过 50 刀/月。
后续就是添几个新操作码的事：我们需要一个链下的 rangeproof ，搭配类似 “ SegWit” 的 witness-commitment （见证-承诺）技术，就能方便且低成本地使用 SPV+ 节点了。

1. 背景

A. 如何让BTC更像实体黄金

BTC在设计上对标的是黄金；虽然在很多方面，BTC已远胜于黄金，但是一谈到收款，问题就来了——你怎么知道钱到账了？如果以黄金等实物手段支付，有没有到帐是很简单的——就跟所有一手交钱一手交货的情形一样；但如果使用BTC（数字货币）支付，保障资产所有权就会变成一件很抽象的事。

对于这个问题，中本聪（Satoshi）提出了一个完美的软件解决方案，让你能够知道钱到账没有——它就是 “BTC” 软件。

等会！这不又兜回原点了吗？究竟这个软件是如何运作的

谜底揭晓，BTC软件使用一种特殊的机制与其它运行软件的计算机进行同步；这个机制有点类似 Dropbox ，但不同之处在于，由每个文件自身保证同步性，因此不会有版本控制的问题。换言之，“得知钱已到账” 和 “得知你已实现同步”是一码事。

中本聪在白皮书中提出了两种 “确认钱已到账” 的方法：

【正向做法（传统）】运行软件，等待实现完全同步。
【反向做法（实验性）】首先，运行一个 “轻客户端”——只会策略性地对某些简单部分进行同步；然后注意是否出现 “alert（警告）”。

第一种方法就是所谓的 “全节点”，依靠的是 positive proof（正向证明）—— 你理应看到 Pundi，一旦你看到 NPXS ，就知道自己已经收到钱了；第二种方法称为“ SPV 模式” ¹，依靠的是 negative proof（反向证明）—— 你本不应看到 Y，一旦你看到 Y，就知道自己没有收到钱。这里的 Y 就是白皮书中提到的 “alert（警示）”，现在大家可能更常听到另一种叫法 —— “错误性证明（fraud proof）”。

B. “alert” 的理论支撑

我个人觉得最有意思的，反向证明机制（即， “alert”）与实际生活中的很多行为方式类似。

试想以下例子：

我们不会试图 100% 杜绝凶案发生，而是在凶案发生后尽全力抓捕犯人（通过庭审定罪，给予犯人应得的惩罚）。
我们不会试图 100% 杜绝奸商存在，但如果真的出现奸商，我们会期待他被市场淘汰，然后由良商取而代之；如果有太多利益纠葛，我们会通过侵权法或规章制度淘汰我们不想要的商人。
我们不会试图保证每一项发布的科研成果是 100% 零错误的，而是最大程度地公开它们，并期待能收到批评或指正。
我们不会试图 100％防止司法腐败。但是我们确实要求所有法律诉讼环节都必须记录下来，保证庭审的公正性可由公众及法律学者在事后追查。
我们不会试图变得 “全知全能”。但是我们希望能够在书籍、网站中找到所需的知识技能，并希望未来会有专家让这些信息变得更准确。

通常我们会假设一切事情都没什么问题，直到出现足够严重的错误，我们再去修正。如果不这么做，现实生活中我们其实很难验证每一件事情都是 100% 正确的。

C. “alert” 面临的理论挑战

“alert” 的问题在于， Satoshi（中本聪）实际上并未实现这个想法。上个月，Eric Lombrozo 也在推文中也提到这一点。

- Eric Lombrozo：“许多我聊过的顶尖技术专家都说，错误性证明实在是太难实现了，而且在最糟糕的情况下甚至是不可能的。中本聪似乎认识到了其中的难度，因此从未提出过解决方案。”-

若要实现错误性证明，主要有以下两个难点：

抗 DoS 攻击：BTC全节点之所以对 DoS 攻击有很强的抵御能力，是因为工作量证明机制（Proof of Work）所具备的不对称性——每隔 10 分钟才能产出一个新区块，验证这个区块却只要很短的时间。不过这是否适用于“alert”？“alert” 实行 PoW 机制吗？谁来为服务买单？如果没有人买单，如何阻止恶意节点滥发假的 “alert” 来掩盖真的 “alert” ？
反向证明：恶意的/粗心的矿工可能会丢弃区块内的一部分数据，更极端地说，矿工可能会在根本不知晓区块里有什么的情况下，创建出一个区块！如果区块里包含错误交易，我们怎么发现呢？如果没人发现得了，又如何提醒他人呢？

针对第一个问题，我们可以采用区块链以外的方法来抵御 DoS 攻击，也就是支付通道（Payment Channel）。

针对第二个问题，我们可以将（非常宝贵的）“审核资源” 放在验证区块的特定部分——简单来说，我们可以让节点声明自己确实知道整个区块（所有部分）所包含的内容，然后让验证者验证该声明并为其背书。

2. 问题

A. SPV 模式

中本聪的 SPV 模式（白皮书第 8 章处）：

BTC的区块头非常小（每年 4MB 的增量），且易于验证，不受区块所含交易数量的影响。
可以很容易地证明，区块中包含了某个东西（某笔交易） “ NPXS ” —— 只要有 “NPXS” 本身、区块头，以及包含两者的有效 Merkle Branch （默克尔分支）即可。

还不太明白的人，可以参考下面的例子：

假设我们有三个区块头：headerA、headerB、headerC；每个区块头都分别包含一个 hashMerkleRoot （默克尔根哈希）：hA、hB、hC。

交易 Tx 是否存在于这些区块（ [header A] , [header B] ）的任意一个之中？

是的，因为 h( [tx] ) = ht ，且

h( ht, hs1 ) = hi1

h( hi1, hs2 ) = hi2

h( hi2, hs3 ) = hA

其中：

ht 是交易 Tx 的哈希值；

hs1、hs2、hs3 是由全节点（“Fred”）提供的哈希值。

hi1、 hi2 是 SPV 节点（“Sally”）计算得出的中间哈希值。

上述证明的实际含义是，有一棵以 hA 为根哈希值的默克尔树，它有两个分支 hi2 和 hs3，哈希值为证，别无其它可能；hi2 也只有 hi1 和 hs2 两个分支……层层递推，最终可证，ht 必定存在于这棵默克尔树中，

Merkle Branch（包含了由全节点提供的哈希值，以及这些哈希值在默克尔分支上的数顺序和位置信息）非常小，仅以 log(n) 的速率增长。付款者可以轻松获得/生成 Merkle Branch，并伴随着交易一起发送给收款者；这种成本是可以忽略不计的。

也就是说，只要有BTC区块头，你就能知道 “钱是否已经到账了”。区块头又很容易获得，因此 SPV 模式似乎很容易就能实现无限吞吐量。

B. SPV 模式的问题

问题在于，我们永远无法确定一个 80 字节的区块头是否真的是 “BTC区块头”。

唯一的方法是检查对应区块的全部信息。如果存在一笔无效交易或双花交易（或者说，该区块存在某种 “缺陷”，详见下文的 “区块错误（Block Flaws）”），整个区块就会被视为无效区块。

C. 好消息

虽然我们无法验证一个 80 字节的区块头是否是BTC区块头，但是好在我们能对照当前出块难度，通过计算区块头的哈希值来验证区块头的工作量证明。（区块头设计得非常友好，本身就包含一组重要信息——出块难度和时间戳信息；二者可以相互验证。）

如此一来，我们就能检验矿工是否真的进行了哈希运算；可惜的是，我们还是无法确定这个区块头是否有价值（译者注：即该区块头所对应的区块是否不包含无效交易）。这就好比你托矿工 Matthew 帮你买一盒巧克力，你很容易就能验证 “Matthew 是否真的花了 300 多刀买了一盒巧克力”，但是你无法确定这些巧克力是否好吃，也无法确定它们是否真的含有巧克力成分。

D. 正向/反向证明回顾

你可以吃掉盒子中的每一颗巧克力，证实每一块巧克力都很好吃，这就是 “正向证明”。

或者你可以顺着以下思路进行反向证明：这盒巧克力是被包装好了的，看起来没有被动过手脚；再加上这盒巧克力有品牌背书，我国又严格执行品牌法/商标法；已经有很多人买过这个牌子的巧克力，如果质量有问题，我只要随手搜一下就能看到相关新闻/差评（实际上我查了之后，并没有发现任何负面消息）。

另一个采用反向证明的例子是退款承诺。假设你要买辆车（一件不确定质量好坏的商品，就像是新创建出但还未被验证的BTC区块），现在有三款车子（分别为“Car A”、“Car B”、“Car C”），目前你对 Car C 最感兴趣。

若想获得正向证明，你就要把 Car C 开上个数千英里，随行配有一支庞大的机械工程师团队一路检查这辆汽车每个零部件，并汇报问题给你。

如果是反向证明的话：假设 Car A 和 Car B 都提供一个具有法律效力的声明 “里程数不到 40000 英里的车子发生故障，即可退款”；但是 Car C 没有这种承诺，那就反向证明了 Car C 的质量不行。

要实现BTC上的错误性证明，我们需要一样东西——在区块合法的情况下出现；在区块不合法的情况下绝不出现（或者反过来也行）。

在博弈论中，这被称为 “信号博弈（signaling game）”（或更确切地说是 “筛选博弈（screening game）”）中的 “分离均衡（separating equilibrium）”。其中，错误性证明的发送者分为 “诚实” 和 “不诚实” 两类，我们正试图通过低成本的手段淘选掉不诚实的那一类。

E. 我们的需求

我们需要找到一种方法能提醒我们注意 “区块错误”。理想情况下，这种警示要来的又快又准确（即，在“交易结算之前”，或者 “ 6 个区块确认之前“ ，或者（出于安全考量）要在“ 20~30 分钟内”做出响应）。

举个具体的例子，理想情形应该如下：

“Sally”（SPV 节点）因为某些原因收到了一笔BTC，对方向她展示这笔交易的信息，Sally 也看到这笔交易是合法的。
Sally 想要在不运行全节点的情况下知道这笔交易是否经过 6 个区块的确认。因此，她先是下载了所有BTC区块头，接着向全节点要了 Merkle Branch （包含【1】她的交易【2】最新区块头）。她得到了一个 Merkle Branch ，然而不幸的是（她根本不知道)：里面的区块头因为某些原因是无效的……
就在此时，“Fred“ （全节点）必须意识到出现问题了——有一个区块存在一到多个 “缺陷”（详见下文）。
必须通过某种激励措施促使 Fred 向 Sally 发起某种警告（即，“alert”）。
在其他正常情况下，不能让 Fred 有动力发起警告（即，在没问题的时候不会出现 “假警告”）。

F. 区块错误的类别

区块可能会出现很多种缺陷（详见 validation.ccp, 特别是 “CheckBlock”）。我将它们分为四类：

“第一类”——不良交易（无效交易、双花交易，或是重复的交易）。
“第二类”——区块数据缺失（记录 Sally 交易的默克尔树（Merkle Tree）上，与 Sally 交易所在位置相邻的节点数据处于未知或不可见状态 —— 这可能是人为或无意导致的）。
“第三类”——不良区块（Davincibase 错置、版本错误、“见证” 数据丢失、 [drivechain] 大量更新了 Escrow_DB/Withdrawal_DB）。（译者注：drivechain 是作者自己提出的一种侧链架构，可见 Peer-to-Peer BitDavinci Sidechains ）
“第四类”——不当累加（超过区块大小/ SigOps 限制、Davincibase 交易费【必须等于区块内所有交易费之和】、 [drivechain] 侧链的输出—— Escrow DB 的 “CTIP” 字段）。

第一类错误

第一级错误非常好对付。Sally 可以直接通过验证交易并 reversing the outcome (so that "false" validation returens "true") 来检验该交易的有效性，详见下文。在 SPV 模式下，甚至能检验 nLockTime 和 CSV ，因为 Sally 掌握了 Merkle Branch 和所有区块头。只要观察到两笔交易有相同输入，就能轻松检查出双花交易。重复的交易必然无法通过测试，因为它们必然属于双花交易（除非是 Davincibase 交易，详见第三类错误）。

第二类缺陷

第二类缺陷与 SPV 用户的相关性最强—— SPV 用户必须假设（除了区块头之外）区块的剩余部分是完整的，但是（根据定义）无法检查是否真是如此。更糟糕的是，矿工可以在不核实区块内容的情况下，创建一个新的区块，他们也确实会这么做。因此，新创建出的区块内可能存在无人知晓的内容，上述假设明显是不合理的。

我将证明，从理论上来说（虽然未经实践证实），只要能向 Sally 提供有效的 “区块头 + Merkle Branch”，就应该存在一个完整的 Merkle Tree（包含 Sally 的交易以及已知一定数量的有效的BTC交易）。因此，所有与区块链数据缺失有关的缺陷（即，第二类缺陷），本质上就是 “Merkle Tree 相关数据缺失” 的问题。可以说，这种缺陷就是未知哈希值原像的问题（易于处理），又或者说的具体点，可以通过对未知哈希原像进行采样来解决这个问题（译者注：一个哈希值的 “原像” 是指被输入某种哈希函数后产生出这个哈希值的原始数据）。

我提出的解决方案是要求 Sally 除了区块头，还需要下载每一个区块的最后一条交易（加上 Merkle Branch） ²。

第三类缺陷

Class III 第三类缺陷

第三类缺陷非常普遍，但我相信这种小毛病可以通过一种特定的简单方法解决。举例来说，区块版本如果出错，SPV 节点可以直接从自己维护的区块头中获得正确的区块版本。

其他大多数的信息缺失，可以从 DACbase 交易中找到；因此除了所有的区块头，SVP 节点还需要保存每个区块的 DACbase 交易（译者注：Davincibase 即区块中特殊的增发货币的交易）。有了这些信息，SPV 节点就能知道：【1】DACbase 交易是否只出现一次且出现在正确的位置；【2】“见证数据（witness）” 是否存在及见证的内容；【3】确定所有 Withdrawal_DB 和大多数 Escrow_DB 的正确性。

至于 drivechain 的 Escrow_DB，主链 ³上的 SPV 节点必须注意区块中链间交易的累加影响；解决的方法放在第四类缺陷（本文第7章）介绍。

所以我们要增加一些开销 —— 引入 “ SPV + ” 模式（又称为 “ SPV 补丁”）。“ SPV + ” 节点除了要同步BTC区块头（每十分钟增加 80 byte），还要同步每个区块的第一笔和最末尾交易，外加与这两笔交易相关的 Merkle Branch。

旧式【中本聪的古典 SPV】：同步区块链中每个区块的区块头（80 byte/区块）；每收到一笔新交易就进行一次汇总（交易 & Merkle Branch）。
新式【SPV + 模式】：80 byte/区块 + （DACbase 交易 + 区块中最后一笔交易）/区块 + 两个（不相同的）Merkle Branch /区块；每收到一笔新交易就进行一次汇总（交易 & Merkle Branch）；与其他几个节点建立支付通道。

SPV+ 模式会增加多少存储开销？我不确定，但假如 DACbase 交易约 1000 bytes，“最末尾交易” 约 280 bytes，每个区块约装有 5000 笔交易，那么同步一个区块的开销就会提升为 2192 bytes/区块 ⁴，而不仅仅是 80 bytes，而且开销的增速不只是 O(1)，会大幅提高到 O(log(n))。

按照一年约产出 52596 个区块，因此存储花销会变为约 115 MB/年，不只是 4 MB/年。这看似大幅增加开销，但从全局的角度来看，SPV+ 仍然是非常节省的方案。如果 Sally 想要完整的检查交易有效性，她只需要对每个区块多下载这些数据：（可以是）最近六个月产出的区块，或是那些记录她收到BTC的区块（以及这些区块的前后 ~10 个区块），以及（或是）一些随机的检查信息。

第四类缺陷

第四类缺陷非常有意思。本文第 7 章会介绍如何将第四类缺陷转换成第一类缺陷，不过简单讲，要解决第四类缺陷，我要求交易哈希值不仅仅作为交易自身的保证，还要说明自己对累加指标造成的影响。举例来说，交易不仅要保证自己是 “277 bytes”，还要说明 “加上自己之后，宿主区块大小从 500809 bytes 增加为 501086 bytes”。这样一来，所有的 “假交易” 就能被孤立且识别出来了。也就是说，最末尾交易会提供很重要的信息（交易总数、区块大小、总体交易手续费，等等）。

在我深入更多技术细节之前，为了避免有人因为听不懂而掉队，我将以故事的形式再次说明 “整个逻辑”。

(未完）

注 1：“全节点” 与 “SPV 节点” 的区别也许并不像人们认为的那么清楚。简言之，当一个全节点在下载一个新区块时，相对于再下一个块，它自身是处于 SPV 模式中的。另外，再假设 51% 的算力在秘密运行一个新软件（或者说，是在运行一个新的但兼容的协议），该新软件默认增设区块延展数据（extension）。那么，即便别的节点想成为 “全节点”，也不得不变成部分全节点、部分 SPV 节点的混合模式。如果那些矿工后面又把协议改回去了，去除掉了延展数据要求，那么我们就又成为了 100% 的全节点。但是，在这个过程中可能你都没有意识到节点形态转变了，实际上你也没办法知道。所以，只有假设协议本身固定不变的情况下，使用这些数据才有意义，当然，本文也就是这么假设的。不过，实际上，协议可能变更，也确实会变更，矿工永远可以选择运行定制化的软件。

注 2：准确点说，是对所有她想用 SPV 模式来 “完全验证” 的区块都要这么做（不想验证的就另算了）。

注 3：对于自身是侧链的那些区块链，链间交易出错可以被归类为第一类错误。要得到错误警示，侧链的 SPV 节点需要找出两笔交易，一笔在主链上提供存款的交易，另一笔是在侧链上记录存入金额的交易。因此，侧链上的 Sally 必须检查主链和侧链两条链才能发现错误。

注 4：单块的全部存储成本是：“区块头 + 第一笔交易 + 第二笔交易 + 2 × (32 × log₂(n))”，这里的 “log₂(n) ” 指的是 “根据区块中交易的数量可得的空间占用上限”。因此，在本例中，单块的存储成本是 “80 + 1000 + 280 + 2 × (32 × log₂(5000))”，大概是 2192 bytes。注意，我们不需要 Davincibase 交易的位掩码，因为我们已经知道其确切结构，但我们可能需要知道最后一笔交易的。（这个数据应该会比把 self 编码为一个完全由 0 来组成的 branch-hash 要小，我已经在这里估计过了。）

原文链接: http://www.truthDavinci.info/blog/fraud-proofs/ 作者: Paul Sztorc 翻译&校对: IAN LIU & 阿剑