【译文】阿童木COSMOS白皮书（十）

10.8Merkle树与证明规范

Tendermint/共识生态系统支持两种Merkle树：简单树和IAVL+树。

10.8.1简单树

简单树是元素静态列表的Merkle树。如果物品的数量不是2的幂，一些叶子会处于不同的水平。简单树试图使树的两边保持相同的高度，但左边的高度可能更大。此Merkle树用于Merkle化区块的事务和应用程序状态根的顶级元素。

*

/ \

/ \

/ \

/ \

* *

/ \ / \

/ \ / \

/ \ / \

* * * h6

/ \ / \ / \

h0 h1 h2 h3 h4 h5

包含7个元素的简单树

10.8.2IAVL+树

IAVL+数据结构的目的是为应用程序状态下的键值对提供持久存储，以便能够有效地计算确定性Merkle根哈希。该树使用AVL算法的一个变体进行平衡，所有操作都是O（log（n））。

在AVL树中，任何节点的两个子树的高度最多相差一个。每当更新时违反此条件时，将通过创建指向旧树的未修改节点的O（log（n））个新节点来重新平衡树。在原始的AVL算法中，内部节点也可以保存键值对。AVL+算法（注意加号）修改了AVL算法，使其保持叶节点上的所有值，同时只使用分支节点存储密钥。这简化了算法，同时保持了Merkle哈希追踪短。

AVL+树类似于以太坊的Patricia尝试。有折衷办法。在插入IAVL+树之前不需要哈希键，因此这在键空间中提供了更快的有序迭代，这可能有利于某些应用程序。逻辑实现起来更简单，只需要两种类型的节点——内部节点和叶节点。Merkle证明平均更短，是一个平衡二叉树。另一方面，IAVL+树的Merkle根取决于更新的顺序。

我们将支持其他有效的Merkle树，例如以太坊的Patricia 尝试，当二进制变量可用时。

10.8.3交易类型

在规范实现中，事务通过ABCI接口流式传输到Cosmos hub应用程序。

Cosmos Hub将接受许多主要事务类型，包括SendTx、BondTx、UnbondTx、ReportHackTx、SlashTx、BurnAtomTx、ProposalCreateTx和proposalbotetx，这些类型都是相当自解释的，并将在本文的未来版本中记录。这里我们记录了IBC的两种主要事务类型：IBCBlockCommitTx和IBCPacketTx。

IBCBlockCommitTx

IBCBlockCommitTx事务由以下部分组成：

§ ChainID (string):区块链的ID

§ BlockHash ([]byte):区块哈希字节，包含应用程序哈希的Merkle根

§ BlockPartsHeader (PartSetHeader): 区块部分设置头字节，仅用于验证投票签名

§ BlockHeight (int): 提交的高度

§ BlockRound (int): 提交的轮次

§ Commit ([]Vote): 包含区块提交的>? Tendermint预提交投票数

§ ValidatorsHash ([]byte): 新验证器集合的Merkle树根哈希

§ ValidatorsHashProof (SimpleProof): 证明ValidatorsHash不符合BlockHash的简单树Merkle证明

§ AppHash ([]byte): 应用程序状态的IAVL树 Merkle 树根哈希

§ AppHashProof (SimpleProof): 一个简单树Merkle证明，证明AppHash与BlockHash相反

IBCPacketTx

IBCPacket由以下部分组成：

§ Header (IBCPacketHeader): 包头

§ Payload ([]byte): 数据包载荷的字节数。可选的

§ PayloadHash ([]byte): 数据包字节的哈希值。可选的

必须存在Payload或PayloadHash之一。IBCPacket的哈希是头和负载这两个项的简单Merkle根。没有完整负载的IBCPacket称为缩写包。

IBCPacketHeader由以下部件组成：

§ SrcChainID (string): 源区块链 ID

§ DstChainID (string): 目标区块链ID

§ Number (int): 所有数据包的唯一编号

§ Status (enum): 可以是AckPending、AckSent、AckReceived、NoAck或Timeout之一

§ Type (string): 这些类型依赖于应用程序。Cosmos保留“代币”包类型

§ MaxHeight (int): 如果此高度没有NoAckWanted或AckReceived状态，则状态变为超时。可选的

IBCPacketTx事务由以下部分组成：

§ FromChainID (string): 提供此数据包的区块链的ID；不一定是源

§ FromBlockHeight (int): 在源链的区块哈希中包含（Merkle-ized）以下数据包的区块链高度

§ Packet (IBCPacket): 一种数据包，其状态可以是akpending、AckSent、AckReceived、NoAck或Timeout

§ PacketProof (IAVLProof): 一个IAVL树-Merkle证明，用于在给定高度证明包的哈希值与源链的AppHash值之间的关系

{图X}描述了通过“Hub”将数据包从“Zone1”发送到“Zone2”的序列。首先，IBCPacketTx向“Hub”证明包包含在“Zone1”的应用程序状态中。然后，另一个IBCPacketTx向“Zone2”证明包包含在“Hub”的应用状态中。在此过程中，IBCPacket字段是相同的：SrcChainID始终为“Zone1”，DstChainID始终为“Zone2”。

PacketProof必须具有正确的Merkle证明路径，如下所示：

IBC/<srcchanid>/<dstchanid>/<Number>

当“Zone1”想通过“Hub”向“Zone2”发送数据包时，无论数据包是在“Zone1”、“Hub”还是“Zone2”上聚合的，它们的数据都是相同的。唯一可变字段是跟踪分发的状态。

11.致谢

我们感谢我们的朋友和同行在构思、审查和支持我们与Tendermint和Cosmos的合作方面提供的帮助。

SkuChain的Zaki Manian在格式和措辞方面提供了很多帮助，特别是在ABCI部分

Adhea和Dustin Byington的Jehan Tremback帮助进行初始迭代

Honey Badger的安德鲁·米勒（Andrew Miller）就共识提供反馈

·Greg Slepak就共识和措辞提供反馈

还要感谢比尔·格雷姆和韩升华的各种贡献。

你的名字和组织在这里是因为你的贡献

12.引文

§ 1Bitcoin:https://bitcoin.org/bitcoin.pdf

§ 2ZeroCash:http://zerocash-project.org/paper

§ 3Ethereum:https://github.com/ethereum/wiki/wiki/White-Paper

§ 4TheDAO:https://download.slock.it/public/DAO/WhitePaper.pdf

§ 5Segregated Witness:https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki

§ 6BitcoinNG:https://arxiv.org/pdf/1510.02037v2.pdf

§ 7Lightning Network:https://lightning.network/lightning-network-paper-DRAFT-0.5.pdf

§ 8Tendermint:https://github.com/tendermint/tendermint/wiki

§ 9FLP Impossibility:https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

§ 10Slasher:https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/

§ 11PBFT:http://pmg.csail.mit.edu/papers/osdi99.pdf

§ 12BitShares:https://bitshares.org/technology/delegated-proof-of-stake-consensus/

§ 13Stellar:https://www.stellar.org/papers/stellar-consensus-protocol.pdf

§ 14Interledger:https://interledger.org/rfcs/0001-interledger-architecture/

§ 15Sidechains:https://blockstream.com/sidechains.pdf

§ 16Casper:https://blog.ethereum.org/2015/08/01/introducing-casper-friendly-ghost/

§ 17ABCI:https://github.com/tendermint/abci

§ 18Ethereum Sharding:https://github.com/ethereum/EIPs/issues/53

§ 19LibSwift:http://www.ds.ewi.tudelft.nl/fileadmin/pds/papers/PerformanceAnalysisOfLibswift.pdf

§ 20DLS:http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf

§ 21Thin Client Security:https://en.bitcoin.it/wiki/Thin_Client_Security

§ 22Ethereum 2.0 Mauve Paper:http://vitalik.ca/files/mauve_paper.html

未排序链接

https://www.docdroid.net/ec7xGzs/314477721-ethereum-platform-review-opportunities-and-challenges-for-private-and-consortium-blockchains.pdf.html

—-

编译者/作者：灰狼

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。