状态机共识的构件模块（下）

每晚八点，我们在社区分享知识，等你。

NervosFans 微信公号：Nervosfans

入群请加乐乐微信：sensus113 美果大冰微信：xj73226

备注入群，谢谢！

---

4. 发布证明及未发布证明

通常，某些协议会要求证明指定受众能够收到特定消息。比方说，PayPub协议、Todd / Taaki的时间锁加密协议、零知识或有支付和闪电等，就规定在比特币区块链中公开发布秘密密钥作为收取付款的条件。再或者，如受众规模上要小得多的监管环境下的某些FinTech应用程序中，除非向监管机构公布，否则交易可能被视为无效。再或者，透明度证书中，除非SSL证书公布给了第三方运维的透明度日志，否则无效。

其次，很多发布证明方案也可以用来证明消息未发布给特定受众。这种类型的证明中，可以实现一次性封印。具体来说，就是证明套证明，从创建封印到封闭封印之间未发布指定消息（消息的发布证明）。

4.1 实施

4.1.1去中心化区块链

区块链中受众指系统的全部参与者。然而，矿工审查是个问题，且尚不存在（要求提交（U）TXO）的紧凑未发布证明。

树链提议是种非常通用且可扩展的实现，能够在受众（安全性）和发布成本之间进行权衡。

4.1.2中心化公共日志

透明度证书就是这个套路，所谓由作为发布媒介的知名方运行的可信（但可审计）日志，承诺允许任何人获取日志副本。

日志本身可以以各种方式索引，CT是按时间索引日志，但是也有很多高效的方式，好比操作者提交‘主题’的密钥：值映射，来为指定的单个或多个主题前缀创建发布（和未发布）证明。

审核日志是通过验证对日志状态的查询为不同的请求者同时返回相同的状态来完成的。

4.1.3收据预言机

最后，由预言机发布的收据证明证明发布，意思说预言机已成功接收消息。特别是在FinTech监管机构的用例中，目标受众是预言机本身，这种提供收据的形式尤其适用。

5. 有效性预言机

随交易历史扩增，证明能从一方转向另一方就变得不太实际。那么，可以使用有效性预言机证明交易的有效性，这样一来，被证明是有效交易之前的（交易）历史就可以丢弃了。

可以使用确定性表达式系统创建非常通用的有效性预言机。 用户提供一个表达式给预言机之后，预言机返回一个签名消息，证明表达式的有效性。表达式也可以是不完整的，其中的一部分被先前生成的证明替换。 好比，若交易有效，返回true的表达式是可以依赖先前交易的有效性，这属于递归调用，且可以通过先前的证明来证明递归调用。

5.1 实施

5.1.1去中心化工作量证明共识

可以把去中心化共识系统中的矿工视为一类有效性预言机，原因是系统的经济激励（应该是）旨在鼓励只挖掘有效区块，那么信任多数算力的用户也可以相信有多数工作量的链中有有效Merkle路径到区块头的交易也都是有效的。 但是，在比特币、以太坊这类去中心化共识系统中，将有效性预言机跟一次性封印/反重放预言机的不同角色混为一谈，原则上本不必如此的。

5.1.2 可信预言机

顾名思义，这种支持远程证明的可信硬件是个特别强大的实现。有个阴谋理论认为，到现在还没有真正意义上的安全远程证明实现的原因是：有了它，实现无法追踪的数字货币系统分分钟的事儿。

有没有注意到，支持封印授权的通用确定性表达式方案的一次性封印预言机扩展至提供有效性预言机服务是何等的easy。 那么，一次性封印预言机的审计机制也是可以应用至有效性预言机中的。

6. 欺诈证明

使用确定性表达式规定的协议能够轻松生成“欺诈证明”，意思是表明系统中声明的状态/证明实际上是无效的。 此外，可以使用 klog_{2}n 深度的表达式规定许多协议，进而生成紧凑欺诈证明。

有个简单的例子是在Merkle和树中证明欺诈，其中有效性表达式如下：

为证明上面的表达式求值为true，需要整颗树。 但是，证明计算结果为false，只需要树的一个子集，原因是证明表达式求值为false仅需一侧，也就是需要klog_{2}n多的数据。 其次，通过修剪，确定性表达式求值器可以自动跟踪证明结果所需的数据，并在序列化证明时修剪掉其他数据。

6.1 有效性挑战

但是，如何保证从一开始就能证明欺诈行为？ 若允许修剪，可能根本无法访问证明欺诈的数据。特别在交易性系统中，单笔欺诈交易能凭空伪造任意数量的价值，这是个尤其严重的问题。

可以考虑是有效性挑战这种方式：说有个证明数据的子集，其中部分数据标记为“可能存在欺诈”。 那么，当提供标记数据并证明可疑证明实际上是有效时，成功挑战响应。若未能成功响应，系统中的参与者可以采取行动，譬如拒绝认可附加交易。

当然，挑战大法也引发了许多迄今尚未解决的问题，例如DoS攻击和数据丢失。

7. 概率性验证

允许部分欺诈的协议可以利用概率验证技术来证明系统内未检测到的欺诈百分比小于特定量，这个概率当然是需要规定的。

常见的方法是Fiat-Shamir变形，就是用数据的哈希摘要作为PRNG种子，以确定性方式重复采样数据结构。将这种技术应用于Merkle和树，首先需要一个递归函数来检查样本，用值加权：

现在可以组合上面的多次（256个）调用：

假设攻击者能啃（反复简单运算）到128位，还剩下128个他们控制不了的随机样本。若给定节点欺诈的（值加权）概率是q，则攻击者欺诈并逃脱的几率是 （1-q）^{128} ， q = 5％时，逃脱概率为0.1％。（注意，这个分析比较糙，实施前再仔细分析下比较好。）

7.1 随机锚节点及交易历史线性化

Fiat-Shamir变形需要大量样本来抵御反复简单运算攻击（grinding attacks），若有随机锚节点可用，则能显着降低概率证明的大小。 PoW区块链本身可以充当随机锚节点，原因是矿工操纵自己产生区块的哈希摘要成本非常高，或者说相当于要丢弃原本有效的区块。

降低概率证明大小在交易历史线性化技术中显得尤为重要。比特币这样的价值转移系统中，随着硬币在整个经济中穿梭，硬币历史呈指数级增长。那么，可以通过将硬币有效性重新定义为概率性来线性化历史证明的增长。

假设一笔交易有n个输入，真输入总值为p，假输入总值为q。 提交交易全部输入至Merkle

和树，若随机选取输入（值加权）可以被证明有效，则交易定义为有效。 最后，假设创建一个真正的输入是种不可撤销的行为，因此提交所有输入的集也是不可变更的，无论输入真假。

若全部输入为真，则交易100％有效；若全部输入为假，则交易100％无效。输入有真有假时，检测到欺诈的几率为：

假输入的预期值为上行潜力（检测到欺诈）与下行潜力（未检测到欺诈）的总和，但是会破坏真输入：

因此，经济层面上，创建假输入并无优势，原因是这么做创造的价值与毁掉的价值一样多。证明一个输入即可证明有效性，则交易历史证明的缩放比例为O（n）。

7.2通膨O(1)历史证明

还可以利用通膨进一步改善交易历史证明的缩放性。 具体而言，就是偶尔允许不验证任何输入的情况下将交易证明视为有效。不验证任何输入即允许交易通过，相当于重置交易历史证明的大小。 当然，这可能引起通膨，但只要通膨的几率可限制，那么最大通膨率也是可以限制在所选值上的。

譬如，假设比特币中每个块都会使货币供应膨胀25BTC，且最多包含1MB的交易数据，通膨率相当于0.025BTC/KB。用概率p检查先前的输入证明，那么声称花费xx BTC的交易预期值为：

可以用每个字节的块奖励R和交易大小l重写：

然后求出p：

比如，声称支出10BTC的1KB交易证明中，0.25％的时间可以不用检查输入且不会产生比出块奖励更多的通膨。 其次，这意味着在n次交易之后，证明大小缩短不会发生的概率是pn，这个值在1840次交易后达到1％。

比特币这种需要矿工验证的系统中，交易证明只包含表明某TXO提交中的一次性封印被封闭的单一Merkle路径即可，数据大小可能不到10KB。 那么，历史数据层面来说，99％的时间数据大小不到18.4MB；90％的时间大小不到9.2MB。

这种设计还有个比较有趣的结果是可以将通膨欺诈制度化：整个区块奖励可以由矿工试图创建有效的“假”交易来代替。 但是，这样一个纯粹的实施可以为最低交易费用设置底线，因此最好还是允许交易费和补贴（于矿工）。

参考：

1. PayPub 

2. Timelock 

3. The first successful Zero-Knowledge Contingent Payment 

4. RPOW 

https://petertodd.org/2016/state-machine-consensus-building-blocks