原文：https://steemit.com/eos/@dan/inter-blockchain-communication-via-merkle-proofs-with-eos-io
默克尔树被用于在轻客户端支持用户行为的证明。轻客户端是区块链间通信的基础，在区块链间通信中，一条区块链要作为另一条区块链的轻客户端。
每个用户行为都能被看作是，某人写了一张支票，然后由银行(区块链)进行处理，如果被接受，那就登记上去。区块链间通信的关键在于生成证明—一张特定的支票被接受了，以及相对于由相同的发送者或接受者写的其他支票的接受顺序。
链a通过跟随链b的区块头，然后处理行为证明，就能接收从链b发送的消息。每个行为证明都有一个或多个序列号，链a使用这个序列号来确保在处理的过程中没有遗漏。
其他的链都是使用状态(账号余额)来生成默克尔树的，而EOS.IO是使用一系列行为来生成默克尔树。一个轻客户端可以通过处理一个账户的所有序列行为，而不需要处理其他账号的行为，来导出该账号的余额。
很多情况下，是不需要知道一个账号的余额的，轻客户端需要做的是验证支付。这可以使用单个行为的证明来验证。
区块链是建立在确定状态机之上的；因此，当完整性和顺序能被提供的时候，区块链间通信就是最有效的。EOS.IO协议创建了一个类似TCP的在链之间的通信通道。这意味着，丢失的证明，或顺序错落的证明会被检测到。
当你能生成证明来保证不会有行为被忽略的话，就不可能证明你拥有目前为止的所有行为。为了证明当前的完整性，一个人必须生成一笔交易，并把它打包，然后生成一个证明，证明当前的多数交易都已使用合适的序列号被确认了。
目标读者
本文是为那些对EOS.IO区块链间通信的加密学设计感兴趣的人而写的。有了这些信息，你就可以设计和构建清客户端，或者集成你自己的区块链。本文原本是内部文档的草稿，但是现在我们把它公开，让社区进行审视和探究。
规范树与证明
EOS.IO里的所有默克尔计算都遵循一些规范，消除证明入口的歧义，而不需要多余的空间。给定两条具有各自摘要的叶结点Da 和 Db。它们在一棵基本的默克尔树中相同的父节点，就是Da 和 Db (Da|Db)的连接的摘要(digest)。不过，除非选定的摘要计算是可交换的，否则Da|Db 不等于 Db|Da。这意味着，一个证明—它的形式是从一个叶子节点到一棵默克尔树的根的路径—必须表明该路径的入口代表的是左还是右连接。
为了在证明中避免这种额外的“路径”，EOS.IO在把叶摘要连接到一个新的摘要之前，应用一个转换。这个转换，表明了该摘要是在连接的左边还是右边。这个证明“路径”然后打包预转换的摘要，让正确的连接操作容易进行推断。
更准确的说，EOS.IO强制设置叶摘要的第一个字节，0代表“左”，1代表“右”，当读到一个证明路径入口(Dp)时，把它应用到一个给定的摘要(Dn),如果Dp的第一个字节是0的话，结果就是hash(Dp|Dn)否则结果是hash(Dn|Dp) 。
C_HASH(left,right)
LET canonical_left := CLEAR_FIRST_BIT(left),
LET canonical_right := SET_FIRST_BIT(right),
LET data := CONCATENATE(canonical_left,canonical_right),
HASH_FN(data);
(pseudocode for generating a hash form a left and right leaf)
此外，一棵默克尔树的结构需要对一个未知值的节点进行哈希，比如，在一棵3个 节点的平衡树中，最后的摘要是它本身的摘要的连接。
Root:
Dabcc
/ \
Dab Dcc <- Dc concatenates with itself
/ \ /
Da Db Dc
区块默克尔
对于任意区块n，它的头包含了一棵平衡默克尔树(它的叶结点是之前区块0..N-1的区块id)的根。这相当于该区块链内容的委托，从源头到每个新的区块。
对于区块链上任意区块的区块id，以及受信任的不可逆的区块头。可以证明该区块是包含在该区块链中的。这个证明需要它摘要路径的ceil(log2(N)) ，n表示链中的区块的数量。给定一个摘要方法 SHA256，你就可以证明一条链(它包含了864字节的1亿个区块)上的任意区块的存在。
行为默克尔
对于任意的区块n，它的头包含了一棵近似平衡的默克尔树的根，这棵默克尔树的叶子是处理行为：行为根时产生的数据的委托。这可以用于存在证明，以及行为顺序。此外，它可以用于证明对给定的scope造成影响的行为脚本的完整性。
对每个行为的委托数据，是：
接受者：接受给定行为的合约账号名
范围：该行为被定义的范围
名称：行为的名称
数据：分发到合约中的加密二进制数据有效载荷
data_access：在处理行为时范围接受的序列号的数组
这可以通过提供行为以及在两个行为之间的序列号证明，来证明脚本的完整性。
序列号永远只在写操作时增加，而不会在读操作时增加。对于给定的(序列，范围，接受者)来说，一次行为只有一次写操作。
region_id：该行为被处理的region
cycle_index：该行为被处理的cycle
这可以用于证明顺序限制。
一个cycle内的shard可以并行执行；在相同的cycle的不同shard的行为之间，没有确定的顺序。
(Example Action Commitment)
{
receiver:inite,
scope:eosio,
name:transfer,
data:{
“from”:”inite”,
“to”:”inita”,
“amount”:10000,
“memo”:”memo”
},
data_access:[
{“type”:”write”,”scope”:”inite”,”sequence”:1},
{“type”:”write”,”scope”:”inita”,”sequence”:0}
],
region:0,
cycle:0
}
对于每个shard(在一个cycle中的可并行执行的单位)一棵平衡默克尔树由这些行为委托组成，来产生一个临时的共享默克尔根。这么做是为了并行计算的速度。区块头包含了一棵平衡默克尔树的根，该平衡默克尔树的叶子是它们自己的shard默克尔树的根。这意味着由行为根表示的最终的默克尔树无法保证是一棵完美平衡的默克尔树，不过，多数情况下，它也接近完美默克尔树了。
给定一个区块链中的行为，就可能简洁地证明该行为的回退，只需要首先证明它由一个区块的行为根所委托，然后给定的区块由一个受信任的不可逆区块头的区块根委托。这两个证明分别指向“行为路径”和“区块路径”。
行为路径包含了重新计算一颗指向一个行为委托的默克尔树的根的所有的必要的数据(从该默克尔树的兄弟摘要)。该默克尔树的根必须完美匹配行为根—由取消该行为的区块头委托。
区块路径包含了重新计算一颗指向一个区块id的默克尔树的根的所有必要数据。该默克尔树的根须完美匹配区块根—由一个受信任的不可逆区块的头委托。
例子，
给定上面的行为，使用下面的id撤销一个区块：
00000033e4f902358b1d43918d197652fc01baaf0e6ca8ee38cda2e8780b7dbd
它的行为根是：
067ed979eeff38064f10bd77dcd3630ce104ae2685b5d6c2500552b0172e4c57
受信任的不可逆区块的区块根是：
1ae092ea41e70982b56b9673f990346876ba535595df16dc1094740c144aaae6
证明数据看起来像是这样：
行为路径:
9b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91
9cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067
C65abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167
4cf39dfbe8a0fdc2540c8f0b68037484051a20d6ca00b891bbfc66d826503677
A8773db30f3733063352d1abec5fea265115bdf646a69d21545746a4f7cff3f3
区块路径:
8000003418a608c3704f80cdfed2793a055cc13993eea67ccdd018d9df027101
2351ee036c6a4052e18c9ded8d35c1b1dfb330531e163039847797d38e9babd2
De1996e5c23c73fa212abaaf423b9038e289fc7a19be5a7f395c7727a5266168
Ccd7c6e10b398fd27cfc4d29f339806593d614c736ae1af8a47908e44d2fe924
1e95b55e98d329bda8f2c79d1f969650716207a03f13f540931ab5a6a80f4d0b
369d86219b35e493a4fda3649c9f3a546809add40462c4b5ddca185f75cfe05c
9067c63043027831fbc7ba046d5bd7d9a0c23e1baa6fe0ac16a911ff7c3acd74
为了验证这个证明，首先对声明的行为委托序列化为EOS.IO的标准二进制格式。结果是厦门的二进制表达式(十六进制)：
000000000095dd740000000000ea3055000000572d3ccdcd1d000000000095dd74000000000093dd741027000000000000046d656d6f0000000000000000020100000000000000000000000095dd7401000000000000000100000000000000000000000093dd740000000000000000
目前EOS.IO使用SHA256作为摘要方法(HASH_FN)，所以，叶结点的摘要是上面上面二进制表达式的SHA256：
1b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91
使用这个叶结点摘要，应用区块路径，指向到规范路径和签名的section，来决定路径的入口是要求左规范还是右规范。应用到完整路径之后，最终的根摘要应当全等于撤销该行为的区块头的行为根：
C_HASH(
1b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91,
9b75773cc9e2d8d186c408c3f5cdc55cde5b23addb6f25aa924bd3279bd0ca91)
=> 1cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067
C_HASH(
1cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067,
9cb66ff0d78991662c4784afac391a0e5f7104164daed36ba1fd4c6cc4907067)
=> 465abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167
C_HASH(
465abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167,
C65abe772ecb192105cd627bcb170eff8ec8f707a5d68d5c8060fee0236b4167)
=> dd205c37e3de758120f50060b052736ba903382904a445fae3a371cfb29820ab
C_HASH(
4cf39dfbe8a0fdc2540c8f0b68037484051a20d6ca00b891bbfc66d826503677,
dd205c37e3de758120f50060b052736ba903382904a445fae3a371cfb29820ab)
=> ecce9664089221e351aaedafd967a9e19e25ad03d82949b3953de53f8b3b1996
C_HASH(
ecce9664089221e351aaedafd967a9e19e25ad03d82949b3953de53f8b3b1996,
a8773db30f3733063352d1abec5fea265115bdf646a69d21545746a4f7cff3f3)
=> 067ed979eeff38064f10bd77dcd3630ce104ae2685b5d6c2500552b0172e4c57
一旦我们验证了该区块包含撤销该行为的委托，我们也必须验证撤销区块也被使用区块路径和撤销区块id的区块链当中。在应用了完整 路径之后，最终的根摘要需要全等于该受信任的不可逆区块头的区块根：
C_HASH(
00000033e4f902358b1d43918d197652fc01baaf0e6ca8ee38cda2e8780b7dbd,
8000003418a608c3704f80cdfed2793a055cc13993eea67ccdd018d9df027101)
=> da16dd856cbb888545c0ed248f2acbbed57037cf407e258849d4600c8f074739
C_HASH(
2351ee036c6a4052e18c9ded8d35c1b1dfb330531e163039847797d38e9babd2,
da16dd856cbb888545c0ed248f2acbbed57037cf407e258849d4600c8f074739)
=> da1a4326c7d83cc86f1154e76000ae94a7579833e75d9378972c6f034e044c11
C_HASH(
da1a4326c7d83cc86f1154e76000ae94a7579833e75d9378972c6f034e044c11,
de1996e5c23c73fa212abaaf423b9038e289fc7a19be5a7f395c7727a5266168)
=> d2d0abf4e6d8b771f8de27413ce7c9ca9e443c89fd10c4d42cb37bcc47cb3598
C_HASH(
d2d0abf4e6d8b771f8de27413ce7c9ca9e443c89fd10c4d42cb37bcc47cb3598,
ccd7c6e10b398fd27cfc4d29f339806593d614c736ae1af8a47908e44d2fe924)
=> c36045ffee9c98eb419077aa356d65fb6a928914c40ec88aadcf634781e56c23
C_HASH(
1e95b55e98d329bda8f2c79d1f969650716207a03f13f540931ab5a6a80f4d0b,
c36045ffee9c98eb419077aa356d65fb6a928914c40ec88aadcf634781e56c23)
=> 4432bce7431f676ed704f2d3367cb33407898b70f51fea2dfa014b97ac37a97b
C_HASH(
369d86219b35e493a4fda3649c9f3a546809add40462c4b5ddca185f75cfe05c,
4432bce7431f676ed704f2d3367cb33407898b70f51fea2dfa014b97ac37a97b)
=> 94f5ba720b886515ada9c0f73ab393dffc43beaeac7be6f7f86bce808834dfde
C_HASH(
94f5ba720b886515ada9c0f73ab393dffc43beaeac7be6f7f86bce808834dfde,
9067c63043027831fbc7ba046d5bd7d9a0c23e1baa6fe0ac16a911ff7c3acd74)
=> 1ae092ea41e70982b56b9673f990346876ba535595df16dc1094740c144aaae6
致谢
感想Bart W.的帮忙，才写完了这篇文章，也才实现了我们github代码仓库中的eos-noon分支的协议。