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

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

以太坊爱好者 发布在 技术指南 区块链 65277

编者注:一般而言,我们会将 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. 如何让比特币更像实体黄金

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

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

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

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

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

  1. 【正向做法(传统)】运行软件,等待实现完全同步。
  2. 【反向做法(实验性)】首先,运行一个 “轻客户端”——只会策略性地对某些简单部分进行同步;然后注意是否出现 “alert(警告)”。
第一种方法就是所谓的 “全节点”,依靠的是 positive proof(正向证明)—— 你理应看到 X,一旦你看到 X ,就知道自己已经收到钱了;第二种方法称为“ SPV 模式” 1,依靠的是 negative proof(反向证明)—— 你本不应看到 Y,一旦你看到 Y,就知道自己没有收到钱。这里的 Y 就是白皮书中提到的 “alert(警示)”,现在大家可能更常听到另一种叫法 —— “错误性证明(fraud proof)”。

B. “alert” 的理论支撑

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

试想以下例子:

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

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

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

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

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

  1. 抗 DoS 攻击:比特币全节点之所以对 DoS 攻击有很强的抵御能力,是因为工作量证明机制(Proof of Work)所具备的不对称性——每隔 10 分钟才能产出一个新区块,验证这个区块却只要很短的时间。不过这是否适用于“alert”?“alert” 实行 PoW 机制吗?谁来为服务买单?如果没有人买单,如何阻止恶意节点滥发假的 “alert” 来掩盖真的 “alert” ?
  2. 反向证明:恶意的/粗心的 矿工可能会丢弃区块内的一部分数据,更极端地说,矿工可能会在根本不知晓区块里有什么的情况下,创建出一个区块!如果区块里包含错误交易,我们怎么发现呢?如果没人发现得了,又如何提醒他人呢?
针对第一个问题,我们可以采用区块链以外的方法来抵御 DoS 攻击,也就是支付通道(Payment Channel)。

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

2. 问题

A. SPV 模式

中本聪的 SPV 模式(白皮书第 8 章处):
  1. 比特币的区块头非常小(每年 4MB 的增量),且易于验证,不受区块所含交易数量的影响。
  2. 可以很容易地证明,区块中包含了某个东西(某笔交易) “ X ” —— 只要有 “X” 本身、区块头,以及包含两者的有效 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,并伴随着交易一起发送给收款者;这种成本是可以忽略不计的。

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

B. SPV 模式的问题

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

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

C. 好消息

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

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

D. 正向/反向证明回顾

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

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

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

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

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

要实现比特币上的错误性证明,我们需要一样东西——在区块合法的情况下出现;在区块不合法的情况下绝不出现(或者反过来也行)。

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

E. 我们的需求

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

举个具体的例子,理想情形应该如下:

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

F. 区块错误的类别

区块可能会出现很多种缺陷(详见 validation.ccp, 特别是 “CheckBlock”)。我将它们分为四类:
  1. “第一类”——不良交易(无效交易、双花交易,或是重复的交易)。
  2. “第二类”——区块数据缺失(记录 Sally 交易的默克尔树(Merkle Tree)上,与 Sally 交易所在位置相邻的节点数据处于未知或不可见状态 —— 这可能是人为或无意导致的)。
  3. “第三类”——不良区块(coinbase 错置、版本错误、“见证” 数据丢失、 [drivechain] 大量更新了 Escrow_DB/Withdrawal_DB)。(译者注:drivechain 是作者自己提出的一种侧链架构,可见 Peer-to-Peer Bitcoin Sidechains )
  4. “第四类”——不当累加(超过区块大小/ SigOps 限制、coinbase 交易费【必须等于区块内所有交易费之和】、 [drivechain] 侧链的输出—— Escrow DB 的 “CTIP” 字段)。
第一类错误

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

第二类缺陷

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

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

我提出的解决方案是要求 Sally 除了区块头,还需要下载每一个区块的最后一条交易(加上 Merkle Branch) 2

第三类缺陷

Class III 第三类缺陷

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

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

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

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

  • 旧式【中本聪的古典 SPV】:同步区块链中每个区块的区块头(80 byte/区块);每收到一笔新交易就进行一次汇总(交易 & Merkle Branch)。
  • 新式【SPV + 模式】:80 byte/区块 + (coinbase 交易 + 区块中最后一笔交易)/区块 + 两个(不相同的)Merkle Branch /区块;每收到一笔新交易就进行一次汇总(交易 & Merkle Branch); 与其他几个节点建立支付通道。
SPV+ 模式会增加多少存储开销?我不确定,但假如 coinbase 交易约 1000 bytes,“最末尾交易” 约 280 bytes,每个区块约装有 5000 笔交易,那么同步一个区块的开销就会提升为 2192 bytes/区块 4,而不仅仅是 80 bytes,而且开销的增速不只是 O(1),会大幅提高到 O(log(n))。

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

第四类缺陷

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

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

(未完)

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

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

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

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

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

评论
登录 账号发表你的看法,还没有账号?立即免费 注册