观点 | 关于 Fraud Proof 的沉思,Part-3

观点 | 关于 Fraud Proof 的沉思,Part-1

观点 | 关于 Fraud Proof 的沉思,Part-2

5. 无效保险(Invalidity Insurance)

第一个解决方案算是两个解决方案的简化版。(好吧,也许我该让你们自己来判断。)

A. 概述

无效保障是一笔支付交易(即是一个比特币脚本),仅在某个区块被证明包含第一类错误时才会生效(区块由其哈希默克尔树根值  8 来定义)。

这种支付交易的受益方需要提供 4 个东西:

  1. 哈希默克尔树根值 (hashMerkleRoot,缩写为 “hMR”);

  2. 一笔 “ 不良交易 ” —— 因某些原因应被判定为无效的某笔交易的 TxID;

  3. 一个 默克尔分支 (如此处所述,由分支长度、分支哈希值及分支方向构成),能将不良交易与 hMR 关联起来;

  4. 证明交易无效的 证据

B. 证据类型

第四个东西(“证据”)还会因交易所属的错误类型不同而有所区别。不良交易可分为 4 种:(a)无效交易;(b)双花交易;(3)重复交易;以及第四类错误,(d)“错误累加(bad accumulator)”(见第 7 章)。

边注: Fraud Proof vs. 智能合约 Fraud Proof

在继续推进以前,我希望对比一下 “现有的 Fraud Proof” 与 “可以在一笔比特币交易中使用的 Fraud Proof”。

我的目的是实现后者,因为它是一种双赢的技术:首先,我们能获得 Fraud Proof;其次,它也给了我们一种激励兼容的办法,让我们能够便宜地从全节点处购买到这些 Fraud Proof。

实际上,我们确实需要双赢的局面,因为我想解决的不仅是 “如何构造 Fraud Proof” 的问题,也是 “保证 Fraud Proof 供应” 的  搭便车 难题。

让比特币自身能理解其 Fraud Proof 的好处是,我们可以把 Fraud Proof 放进交易中,并在比特币智能合约中使用它。但这是非常难实现的。我绝对不打算假装自己已经找到了最佳答案  9

(a)无效交易

乍看起来,我们似乎只需要用协议的交易验证函数把交易再跑一遍,要是函数运行  失败 就能证明该交易无效,因此,似乎只需要把交易自身作为 “证据” 就可以了。

但是,我认为没有那么简单。这里面有个难题!

如你我所知,跟比特币相关的每一棵默克尔树都包含可能是有效的交易,但是,树上也包含它自身的内部节点(interior node)!如果 Sally 的默克尔树声称某笔交易是无效的,然后她给我们展示了一个路径,指向 “两个串联起来的 32 字节的 SHA256 哈希值”,我们能怎么看呢?我们怎么知道这些字节所代表的比特币交易是无效的?Sally 的路径所指向的 node 可能并不代表一笔交易,她有可能在默克尔树的树高上说谎了!

或者相反的情况也有可能(比如恶意的 Fred 故意构造了一笔无效的交易,该交易的形式刚好是 64 个随机字节),到底是谁在骗谁?

为解决这一难题,我们要求 Sally 同时还得提供一个默克尔分支,来证明别的一些交易是有效的。为了方便程度最大化,可以就是她自己的交易(也就是她在收款时的交易,就在 Fraud Proof 交互过程刚开始的时候发生的),或者,也可以是 coinbase 交易(她的 “SPV+ 节点” 本身就会保存 coinbase 交易)。

因此,在这个方案中,给定一笔是无效的,证据至少要包含两笔交易,一是该无效交易本身,二是一笔有效交易,且两笔交易的默克尔分支高度必须相等。

如此,则(a)所需的证据形式与下文的 (b)和(c)所需的很相似。

(b,c)双花交易和重复交易

对于(b)和(c)来说,欺诈的证据似乎也很直接,只需要两笔交易和两个分支就够了——然后我们就可以看到两笔交易的输入(或者哈希值)是一样的。

但是这里又有一个陷阱,就是第二笔交易的位置!(我这里的 “第二笔” 的意思是按时间顺序算的 “第一笔” 交易,也就是某人尝试双花的那笔 “真正” 的 交易/资金)。该笔交易可能存在于另一个区块中。

实际上,两笔交易的位置可能远隔成百上千个区块。

如果脚本解释器可以访问过去的区块头,那我们也许可以完成证明工作,只需加多一个 32 字节的哈希值就好。但我不知道完成这个事的最好办法是什么——也许是一个新的操作码,会在验证出某个 32 字节的哈希值不在已知的 hMR 集合中时传出失败。

如果我们没有高效的办法,那么在最糟糕的情况下,处理方法就非常烦人 —— 要加入一整条连续的区块头链条,从双花交易所在区块的区块头一直追溯到第二笔交易所在区块的区块头。当然,后面的事情就比较简单了,要求包含一个 “三件套” (区块头、默克尔分支、交易)来证明一笔有效的交易已经花费过那笔资金(对应(c)时,则是一笔具有相同哈希值的有效交易)。

可怕的是,如果双花交易所花费的资金是在数年前已经花费过的,则我们需要几十万个 80 字节的区块头来完成证明。这样一个区块头链条自身的数据量可能就是 16MB!这么大的数据量根本塞不进一笔交易里面。现在,这里需要提升。

实际上,有些人,包括 Blockstream,曾经撰文讨论过如何把一百万个 80 字节的区块头压缩成 “几十 KB 的数据”,等等。(见附录 B)

如果你知道该怎么处理这个问题,请留下你的评论!

(d)错误累加

对于(d)类不良交易,比特币需要一种办法来理解交易中数据的 “累加器”(或者 “第二见证数据”)。网络需要根据交易的属性来检查这些数据。细节在本文第 7 章。

(重复一遍:用软件很容易实现,到要装进比特币脚本中就难很多。)

C. 汇总一下

有了这个脚本,我们可以策略性地部署在支付通道中,以保证不会收到无效的区块头。

具体来说,对每一个区块头,我们都将把一个通道推入 “动能” 阶段,使得:

  1. Sally 无条件给 Fred 支付一笔钱;并且

  2. Sally 可以从 Fred 处得到一大笔钱,只要她能找到一些证据,证明相关区块头是无效的。要不然,一段时间(比如 1000 个区块)之后,Fred 就会收回这笔钱。

前面那笔资金有点像 保险费 ,而第二笔资金像是 保险理赔 —— 只要条件满足,Sally 就有权得到赔付金,不然,Fred 就可以收回这笔钱。

一个诚实的 Fred 完全有信心接受这种交易。对他来说,因为绝对不可能找到他所提供的区块头无效的证明,因此他永远不用赔付,而保险费简直就是天上掉馅饼。

因此,这里的 “Fraud Proof” 是通过相反的方式来实现的:如果这种类型的交易没有人愿意签署了,那我们就得到警示了。

不过,在一种情况下,不诚实的 Fred 还会继续提供这种服务,我们在上文所述的故事里提到过,就是交易数据丢失的情况。不诚实的 Fred 知道,如果全网都丢失了某笔交易的数据,Sally 就不可能证明出其中的欺诈。因此,提供了相关服务的 Fred 也就永远不会被抓到 —— TA 犯罪的证明已经荡然无存,那 Sally 还凭什么送 TA 去监狱呢?

这就是为什么我们需要完整性审计(Fullness Audit)。

6. 完整性审计(Fullness Audit)

完整性审计使得 Fred 可以(向 Sally)证明他确实拥有一个区块中的所有交易。

A. 两种材料

首先,我们需要一种新的 “魔法材料”,用于把 “一个整数” 转化成 “默克尔路径方向” 并返回。

有趣的是,我们已经有这种东西,无需再费手脚了。默克尔路径方向已经作为单个 int32_t 值存储下来了(反正,Namecoin 的合并挖矿要用到)。甚至可以断言,这个值 “……就等于所在默克尔树最底层起始哈希值的索引”。这里用到的是整数的二进制编码原理!所以,问题解决了。

我们需要的第二种魔法材料,“范围证明/集合归属性证明”,让我们可以利用链下交互(可能你在阅读本文第 3 章时已经注意到了)。所以这个问题也基本上解决了。

我再加依据,现在有一支比特币顶级密码学家天团在全身心投入研究 “范围证明”,不过理由与我们这里的不相干(他们想把范围证明直接用在链上,用来隐匿比特币交易的金额)。相较之下,我们的用法柔和得多。

如果你认为你有一个绝佳的承诺方案,请留言告诉我(可阅读下文的 “(3)保险理赔” 了解更多细节)!

B. 汇总一下

链上发生的步骤如下(或更准确一点来说,是发生在支付通道的内部的事情,但这些指令可能随时需要上传到链上):

  1. Sally 给 Fred 无条件地支付一小笔钱。这是 Fred 要求的费用,或者说 “ 保险费 ”(数额很小的,因为保险条件是 Fred 明知绝不可能发生的情况)

  2. Sally 要给 Fred 支付非常大一笔钱,如果 Sally 坐等时间流逝,迟迟不公开 TA 的秘密 “R” 的话。这个金额一定要大于下面的保险理赔金额,以保证 Sally 会及时交互。有点像是 “ 诚意契约 (fidelity bond)”。

  3. 如果 Fred 不能提供 Sally 所要求的区块数据的话,TA 要给 Sally 支付一大笔钱。这就是 “ 保险理赔金 ”。

(1)保险费

保险费的数额非常小。通过普通的支付通道更新来传递。

(2)诚意契约

要实现诚意契约也很简单,尤其是在闪电通道类型的通道中,因为它是 “哈希时间锁合约”。举个例子,Sally 先发送 10 btc 给 Fred,这笔资金充当 “人质”。其次,Fred 把钱转回给 Sally,当且仅当 Sally 在 “时间锁窗口” 内公开了 R(即,一旦公开 R,就释放人质)。那么,如果 Sally 没有公开 R,TA 就等于是交了 10 btc 的罚金。

如果 TA 公开了 R,TA 就能拿回 10 btc,然后 Fred 就拿到了 R,他可以自由用在某笔交易中。如上所述,诚意契约必须是这几笔资金中金额最大的,而且其时间锁要短一些,因为还有一个针对 Fred 的时间锁(见下文),其长度要比诚意契约时间锁长一倍,以保证 Fred 也有足够长的时间来提供区块数据(即,在 Fred 获得了 R 之后,最坏也还有一个完整的时间锁周期来完成任务)。

(3)保险理赔

实现保险理赔要难一点。

保险理赔的形式与诚意契约一样,只不过人质是 Fred 的资金,而不是 Sally 的。只有提供与 R 相关的区块数据,TA 才能拿回自己的钱。

我分两部分来说明这个合约。第一部分是确认合约的初始参数:

  • Fred 必须提供两个整数 (X, R),并且承诺 c(X, R) 可以匹配一个预先设定好的哈希值 H1,而 hash(R) 匹配一个约定好的 H2。H1 和 H2 的值都是由 Sally 在选择自己的随机数并更新通道状态的时候提供的。

    • “X” 是一个默克尔树索引值(请看上文的第一种 “魔法材料”),而 “R” 是一个随机的 256 位的整数,是由 Sally 自主选择的。

    • Sally 为了拿回她的 “诚意契约金” 就会公开 R

    • 最后,Fred 可以用 R 来求得 X(只需计算该区块所装载的交易数量 L 的哈希值),然后提供 (X, R)。

很简单吧?但第一部分还有最后一个要求:

  • Sally 必须给 Fred 作出承诺,或者说提供范围证明(在链下,实时交互,体积大小任意):X 必然落在 (1, L) 范围内。

  • (所以这个承诺可能无法采用哈希值的形式。那么这就可能需要脚本的版本控制,或者一个新的操作码,或其它更为高级的技术。又或者只包含代数范围。抱歉,找出最合用的工具非我所长,问问 Andrew Poelstra。)

第一部分只是确认 “Fred 同意要做什么”。Fred 还没有真正着手去做!

所以,为了满足合约的条件,Fred 需要:

  • 将 x1 解释为一个默克尔树索引值,然后提供一个默克尔分支,既有同样的索引值,且最终的哈希值是 “H3”,即他们正在测试的区块头的哈希默克尔根值。这样 Fred 就证明了,无论 Sally 选择的随机数是什么,Fred 都可以向她出示相应的哈希值。

  • 最后,Fred 还必须提供这个哈希值的原像。

一句话:要是 Fred 可以出示那个原像(产生出相应哈希值的原始数据),TA 就过关了。否则就不过。

如果原像是一笔有效的交易,那么皆大欢喜。如果原像不是一笔有效的交易(比如就是一个乱七八糟的数据),那 Sally 就大可利用第 5 章所述的 “无效保险” 来赚一笔了。两个服务是相互补充的。

C. 重复审核

显然,Sally 能抓到欺诈的概率并不高:只有 1/L。所以,Sally 可能希望多次尝试。而 Fred 应该也很乐意,因为每次审核 TA 都有钱进账。

D. [可选] 关于丢失的数据

自上而下与自下而上

我们可以把默克尔树(在视觉上)想象成一个巨大的三角形。一般来说,这个三角形是 “自下而上” 搭起来的,最底下那一层是最先搭好的,而 “顶部” 是最后完成的。顶部的值(也就是默克尔根)会放到区块头里。

全节点总是这样自下而上来搭建这个三角形的,原因如下:【1】全节点一般都拥有全部的底层数据;【2】三角形上,除了最底层,每一层的数据都取决于其底下一层的数据。

但 SPV 节点也可以选择用 “自上而下” 的方式来搭建三角形,就是从默克尔根往下延伸。这样他们就既不需要保存整棵默克尔树,又能 “瞄中” 这个三角形中某个位置的准确数据。

(这种模式对正在下载和验证一个新发现区块的全节点来说也有用。因为全节点需要存储(最新一些区块的)整个三角形 —— 所有中间层的哈希值都要保存。)

“整个三角形”

那整个三角形到底有多大呢?看表:

可看出,设第一列的值为 “n”,那么第二列的值就是 “2^(n-1)”,第三列的值就是 “(2^n)-1”。

所以,第三列的值(也就是 “整个三角形” 的大小),差不多总是第二列值(“三角形” 的底层)的两倍大。所以,如果我们存下整个三角形,而不是只存底层,存储(哈希值的)所要求的空间只不过增加了一倍。

而且,全节点存储着所有的交易,还有交易的哈希值。如果一个区块的大小是 8 GB,因为一笔交易的数据量大概是 250 字节,那么区块中大概会有 32,000,000 (3200 万)笔交易,那么 “三角形底层” 的大小是 32,000,000 * 32 byte(一个哈希值的数据量),就是 1.024 GB。根据上面的逻辑,三角形的其余部分也会占去约 1.024 GB,所以,全三角形存储模式所要求的内存空间及硬盘空间是 10.048 GB,而不是 9.024 GB。

(而且,一旦获得了整个三角形,存储要求会回落到 9.024 GB)。

审核三角形

一个遵守协议的 Fred 可以获得完整的三角形,但丢失了一些数据的 Fred 就做不到了。TA 甚至可能遗失一些 “从中到上” 路径上的值,这就更容易被发现了,因为数量上要少得多。

实际上,Sally 可以要求任意的一个哈希值,具体在树上哪个位置无所谓,只要是在树上的就行。

要通过这样做来审核三角形的完整性,TA 可采取跟我上文所述完全相同的步骤!只不过最后一步不是公开一笔比特币交易,而是两个 32 字节的哈希值(Sally 不能把这个数据用在无效保险中,恰好相反 —— TA 会认定这是 Fred 拥有整棵默克尔树的证据)。

(未完)

(未完)

(文内提供了许多超链接,请点击阅读原文到 EthFans 网站上获取)

原文链接:

http://www.truthcoin.info/blog/fraud-proofs/

作者:  Paul Sztorc

翻译 & 校对:IAN LIU & 阿剑

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章