状态机共识的构件模块（上）
鉴于以太坊最近在其基于帐户的命令式编程模型中遇到的问题，我在这里想简单写点有关所谓“智能合约”系统的状态机构建模块，属于比特币设计的扩展，我本人在自己的Proofchains / Dex项目研究工作中开发多年。
目录
1. 确定性代码及确定性表达
1.1 证明
1.2 修剪
2. 交易
2.1 证明分布
3. 独特性及一次性封条
3.1 实施：
3.1.1 交易性区块链
3.1.2 无界预言机
3.1.3 有界预言机
3.1.4 组封条
3.2 原子性
3.2.1 使用单一预言机
3.2.2 两阶段超时
4. 发布证明及未发布证明
4.1 实施
4.1.1 去中心化区块链
4.1.2 中心化公共日志
4.1.3 收据预言机
5. 有效性预言机
5.1 实施
5.1.1 去中心化工作量证明
5.1.2 可信预言机
6. 欺诈证明
6.1 有效性挑战
7. 概率验证
7.1 随机锚节点及交易历史线性化
7.2 通膨O(1)历史证明
8. 参考文献
1. 确定性代码及确定性表达
分布式系统中的共识源于确定性代码，即在不同计算机上运行相同代码后得到的结果相同。若不能，则与中央权威数据库无异。传统语言及周边框架中未定义未指定的行为，往往使得确定性难以实现，从C / C ++中的有符号整数溢出到数据库中的非确定性行为。比特币等系统虽基于传统语言，但其成功也归功于开发者功不可没。
确定性表达系统，如比特币的脚本系统、Dex等，通过哈希摘要精确指定表达式来改进确定性，并在具有确定性结果的环境下执行。 比特币脚本属于类Forth基于堆栈的表达；Dex中则采用了lambda演算表达式。
1.1 证明
目前为止，确定性表达式最常用于指定资金花费条件，特别是比特币的P2SH、Segwit用法。这种用法是可以常规成‘用状态机精确定义共识协议’的。每个状态用确定性表达式定义，意思是说达到状态时表达式必须返回true。 那么，使得给定表达式返回true的数据，就是‘证明’，且该证明可从一方传递至另一方证明已达到预想的若干状态。
这里边有个重要的含义，即，确定性及有效的证明数据序列化。
1.2修剪
通常，根据证明对表达式进行评估不需要用到证明中全部的数据。 好比，为向轻客户端证明给定区块包含交一笔易，知道交易到区块头的Merkle路径即可。
Proofchains和Dex系统中这个过程被称为‘修剪’，具体而言是种内置支持：一来跟踪访问数据的操作；二来支持操作的底层序列化方案中使用修剪数据的哈希摘要对不需要的数据进行省略和替换。
2. 交易
交易是常见的状态机类型。交易历史则是多笔交易的有向无环图，其中一个或多个源交易并没有输入（祖先），但是有一个或多个输出；零或多个非源交易有一个或多个输入，零或多个输出。图的边缘处输入连接到输出，每个输入都连接到一个输出。有相关输入的输出称为花费输出；没有相关输入的输出为未花费输出。
输出有附加条件，例如，必须为pubkey生成有效签名，且还会与诸如‘# of coins’之类的其他值相关联。若有一组证明，每个证明对应一个输入，且满足与每个输出相关的条件，则认为一笔交易有效。其次，有效性可能还会要求额外约束的真实性，譬如要求花费的硬币数量> =输出创建的硬币数量这种。输入证明也必须唯一地对应交易本身才是安全的，若不唯一，说明还可以用到其他交易中，就是重放攻击了。
以下情况下，非源交易有效：
1. 遵循协议规定的任意规则，例如硬币花费数量> =硬币输出数量。
2. 每个输入都有有效证据。
3. 每个输入交易本身都是有效的。
想在比特币这种价值转移系统中实现以上情形，可以使用两个Merkle和树（merkle-sum trees），一个用于输入，一个用于输出，输入仅提交前一笔交易的txid及输出＃；输出提交scriptPubKey及输出数量。 证人可以单独提供，并签署提交交易或输入和/或输出子集的签名。
只要所有源交易都是唯一的，且哈希函数是安全的，那么所有交易输出都可以被唯一的识别出。
2.1 证明分布
所以，Alice怎么才能让Bob相信：
1. 自己应完成了某笔交易，且
2. 交易已将系统置于Bob要求的状态？
答案当然是向Bob提交数据，证明系统现处于此状态。交易性系统中，证明代表了部分或全部交易历史。 比特币系统有通用的泛洪消息传递层，其中的参与者都有机会获得系统中全部证据的副本，但是，也还是可以基于点对点消息传递实现更为细化的解决方案。
想象一下Alice向Bob证明自己已将名下的房产过给了Bob，这个动作由提供一系列证明来完成。仔细想来，这套证明与现实生活房产交易中向买方提供一系列契约文件证明财产所有权的转让在方法上也没什么差，但是，这里边可是有双重支付的问题哟。
3. 独特性及一次性封印
除了知道给定交易历史有效之外，还得知道交易是否唯一。意思是说，交易历史中的每个花费输出只与一个输入相关联，且不存在其他有效花费。绕了这么一圈，想说的其实就四个字：严禁双花。
比特币（基本上所有类似的加密货币）通过就所有（有效）交易集达成共识的方法来实现（禁止双花）这一目标，然后规定当且仅当输出未被双花时，此共识才有效。
更为通用的方法则是引入一次性加密封印（single-use seals）的概念，有点类似运输储存时保护货物的篡改留痕一次性封印。 每个封印都与全局唯一标识符相关联，有‘封闭’和‘拆封’两种状态。 安全的封印只能‘封闭’一次，进而产生‘封闭’这个证明。
实用的一次性封印都应该与某种条件相关联，例如pubkey或确定性表达，条件满足后方可封闭。 其次，证明的内容将能够提交新数据，比如交易花费与封印相关的输出。
此外，一次性封印的一些实施方式也可以产生封印在特定时间/块高度等处未被被封的证明。
3.1 实施：
3.1.1 交易性区块链
比特币系统中的交易输出可以用作一次性封印。 此实现中，输出（txid：vout＃）就是封印的标识符，授权机制是输出的scriptPubKey，证明则是花费该输出的交易。 证明可以视需要以各种方式提交附加数据，比如OP_RETURN输出或不可花费输出。
若封印标识符未公开，那么该实现就是抗矿工审查的，且协议还能允许证明交易提交带有不可花费输出的封闭内容；不可花费输出无法与转移资金的交易区分开来。
3.1.2 无界预言机
可信预言机P能够维护一组封闭的封印，生成签名消息，证明封印已封闭。 具体而言，封印由元组（P，q）识别，其中q是每个封印封闭必须满足的授权表达式。 首次向预言机提供有效的封印签名时，预言机将签名以及封印ID添加至封闭的封印集中，然后提供一个签名消息，证明封印已经封闭。 这里边的证明就是这个消息（还可能是签名，或者是由其签发的第二条消息）。
出于透明度或审计目的，预言机可以发布所有封闭封印集。 一个比较好的发布方式是创建一个Merkle密钥：值集（merkelized
key:value set），其中封印的标识符作为密钥，值为证明，然后创建该集的签名证书透明度日志。 来自该日志的Merkle路径也可以作为封印封闭证明，证明某封印未封。
3.1.3有界预言机
无界预言机中由于封闭封印集增长无限制，存在一定的存储问题。这个问题可以通过要求预言机用户提前分配封印来解决，类似比特币中的UTXO集。
为分配封印，用户向预言机P提供带授权的表达式q。 然后预言机生成一个随机数n并将（q，n）添加至未封闭的封印集，并告知用户此随机数。此后，封印被唯一的（P，q，n）识别。
为封闭封印，用户向预言机提供有效签名（P，q，n）。 若拆封封印集包含此封印，则封印被从集合中移除，且预言机向用户提供证明有效封闭的签名消息。
实际实施中，应该是让预言机发布一个透明度日志，日志中的每个条目都提交带Merkle集的拆封封印集，以及在该条目期间封闭的任何封印。同样，该日志的Merkle路径可以作为封印拆或封状态的证明。
注意，（U）TXO提交也表明了比特币本身是个能生成紧凑证明的有界预言机实现。
3.1.4组封印
使拆封封印提交一组子封印，然后在第二组封闭封印证明的基础上封闭主封印，可以将多重封印合并为单个封印。 不需要封闭的封印可以通过特殊的重新授权消息进行封闭，相当于把封印重新委托给新的拆封封印。
由于封闭的子封印证明还可以包括授权证明，以前出现过这种情形，说有个协议中，被授权封闭主封印的实体有能力DoS攻击子封印所有者，但不能欺骗性地随意封闭封印。 若主封印上的操作比较贵，比如实施在区块链上的封印， 这种在子封印上摊销成本的方法，也还不错。
3.2 原子性
协议通常会要求封闭多个封印，交易才有效。 若由单一实体控制全部封印，则没有问题：反正最后一个封印封闭前，交易是无效的。
但若由多方控制封印，那么一方在其他方封闭各自封印后，拒绝通过交易进行攻击，留下个半拉交易，卡在那里。
这个问题有下面几种解决方式：
3.2.1 使用单一预言机
若其他封印集也被封闭，预言机可以保证封印被封闭；比特币上是可以这样的。 若交易各方不都在同一个预言机上，可以添加一个额外的交易，将各自输出重新分配给一个共同的预言机。
同样，可以使用预言机共享的共识协议创建出多个相互信任的预言机之间的临时共识；此方法无需变更证明验证实现。
3.2.2 两阶段超时
若能够生成封印拆封这一事实的证明，即使在对抗条件下，也可以使封印协议允许在超时后撤销封闭，前提是（以指定方式）提供其他封印亦未封闭的证据。
根据实施情况，特别是去中心化系统中，下次封印封闭时，封印已封闭的证明也可能反过来提供前一次封闭实际上是无效的证明。
未完待续。
https://petertodd.org/2016/state-machine-consensus-building-blocks
