Encoding - Cosmos Docs

协议缓冲区

CometBFT 对所有数据结构都使用 Protocol Buffers，具体为 proto3。更多细节请参阅 Proto3 语言指南。

字节数组

字节数组的编码方式很简单：先写入数组长度的 UVarint 前缀（在 proto 中称为 Varint），再写入原始字节。关于 varint 的细节，请参阅 protobuf 规范。例如，字节数组 [0xA, 0xB] 会被编码为 0x020A0B，而一个包含 300 个条目、起始为 [0xA, 0xB, ...] 的字节数组会被编码为 0xAC020A0B...，其中 0xAC02 是 300 的 UVarint 编码。

哈希

CometBFT 使用 SHA256 作为哈希函数。对象在计算哈希前总会先序列化。因此，SHA256(obj) 是 SHA256(ProtoEncoding(obj)) 的简写。

公钥密码学

CometBFT 使用 Protobuf 的 Oneof 来区分不同类型的公钥和签名。此外，CometBFT 还为每种公钥定义了 Address 函数，可作为公钥的更紧凑标识符。下面列出了具体类型、名称、公钥和签名的前缀字节，以及各个 PubKey 的地址方案。为简洁起见，这里不展开私钥的细节，仅给出其类型和名称。

密钥类型

每种类型都定义了自己的 pubkey、address 和 signature 格式。

Ed25519

地址是原始 32 字节公钥的 SHA256 哈希前 20 个字节：

address = SHA256(pubkey)[:20]

签名是原始 64 字节的 ED25519 签名。 CometBFT 采用 zip215 来验证 ed25519 签名。

注意：此变更将在 CometBFT 的下一个主版本中发布。

Secp256k1

地址是原始 32 字节公钥的 SHA256 哈希前 20 个字节：

address = SHA256(pubkey)[:20]

其他常见类型

BitArray

BitArray 在某些共识消息中用于表示从验证者收到的投票，或区块中收到的部分数据。它表示为一个结构体，包含比特数（Bits）以及以 base64 编码的位数组本体（Elems）。

名称	类型
bits	int64
elems	int64 切片（`[]int64`）

注意，BitArray 在 JSON 中有一种特殊编码形式，使用 x 和 _ 分别表示 1 和 0。例如，BitArray 10110 的 JSON 编码为 "x_xx_"

Part

Part 用于将区块拆分为多个片段，以便并行传播，并可通过这些片段的 Merkle 树进行安全验证。 Part 包含片段索引（Index）、片段的实际底层数据（Bytes），以及证明该片段包含在集合中的 Merkle 证明（Proof）。

名称	类型
index	uint32
bytes	字节切片（`[]byte`）
proof	proof

详见下文的 SimpleProof。

MakeParts

使用 Protobuf 对对象编码，并将其切分为多个 part。 CometBFT 使用 65536 字节的 part 大小，最多允许 1601 个 part（见 types.MaxBlockPartsCount）。这对应于硬编码的 100MB 区块大小上限。

func MakeParts(block Block) []Part

Merkle 树

关于 Merkle 树的概览，请参阅 wikipedia 我们使用 RFC 6962 规定的 Merkle 树规范，并以 sha256 作为哈希函数。 Merkle 树在 CometBFT 中被广泛用于计算数据结构的密码学摘要。 RFC 6962 与最简单形式的 Merkle 树之间的差异在于：

叶子节点和内部节点使用不同的哈希。这是为了实现“第二原像抗性”，防止某个内部节点的证明被当作叶子节点的证明而通过验证。叶子节点使用 SHA256(0x00 || leaf_data)，内部节点使用 SHA256(0x01 || left_hash || right_hash)。
当条目数量不是 2 的幂时，树的左半部分会尽可能大。（即小于条目数的最大 2 的幂）这样在添加新叶子时需要重新计算的内容更少。例如：

   Simple Tree with 6 items           Simple Tree with 7 items

              *                                  *
             / \                                / \
           /     \                            /     \
         /         \                        /         \
       /             \                    /             \
      *               *                  *               *
     / \             / \                / \             / \
    /   \           /   \              /   \           /   \
   /     \         /     \            /     \         /     \
  *       *       h4     h5          *       *       *       h6
 / \     / \                        / \     / \     / \
h0  h1  h2 h3                      h0  h1  h2  h3  h4  h5

MerkleRoot

函数 MerkleRoot 是一个简单的递归函数，定义如下：

// SHA256([]byte{})
func emptyHash() []byte {
    return tmhash.Sum([]byte{})
}

// SHA256(0x00 || leaf)
func leafHash(leaf []byte) []byte {
 return tmhash.Sum(append(0x00, leaf...))
}

// SHA256(0x01 || left || right)
func innerHash(left []byte, right []byte) []byte {
 return tmhash.Sum(append(0x01, append(left, right...)...))
}

// largest power of 2 less than k
func getSplitPoint(k int) { ... }

func MerkleRoot(items [][]byte) []byte{
 switch len(items) {
 case 0:
  return empthHash()
 case 1:
  return leafHash(items[0])
 default:
  k := getSplitPoint(len(items))
  left := MerkleRoot(items[:k])
  right := MerkleRoot(items[k:])
  return innerHash(left, right)
 }
}

注意：MerkleRoot 处理的是任意字节数组形式的条目，不一定已经是哈希值。对于需要先进行哈希的条目，我们引入 Hashes 函数：

func Hashes(items [][]byte) [][]byte {
    return SHA256 of each item
}

注意：这里我们会对记号做一定泛化，并使用类型为 struct 或 []struct 的参数来调用 MerkleRoot。对于 struct 参数，我们会构造一个 [][]byte，其中包含该结构体每个字段的 protobuf 编码，顺序与字段在结构体中的出现顺序一致。对于 []struct 参数，我们会通过对各个 struct 元素分别进行 protobuf 编码来得到一个 [][]byte。

Merkle 证明

用于证明某个叶子位于 Merkle 树中的 Proof 由以下部分组成：

名称	类型
total	int64
index	int64
leafHash	字节切片（`[]byte`）
aunts	字节矩阵（[][]byte）

其验证方式如下：

func (proof Proof) Verify(rootHash []byte, leaf []byte) bool {
 assert(proof.LeafHash, leafHash(leaf)

 computedHash := computeHashFromAunts(proof.Index, proof.Total, proof.LeafHash, proof.Aunts)
    return computedHash == rootHash
}

func computeHashFromAunts(index, total int, leafHash []byte, innerHashes [][]byte) []byte{
 assert(index < total && index >= 0 && total > 0)

 if total == 1{
  assert(len(proof.Aunts) == 0)
  return leafHash
 }

 assert(len(innerHashes) > 0)

 numLeft := getSplitPoint(total) // largest power of 2 less than total
 if index < numLeft {
  leftHash := computeHashFromAunts(index, numLeft, leafHash, innerHashes[:len(innerHashes)-1])
  assert(leftHash != nil)
  return innerHash(leftHash, innerHashes[len(innerHashes)-1])
 }
 rightHash := computeHashFromAunts(index-numLeft, total-numLeft, leafHash, innerHashes[:len(innerHashes)-1])
 assert(rightHash != nil)
 return innerHash(innerHashes[len(innerHashes)-1], rightHash)
}

aunt 的数量限制为 100（MaxAunts），以保护节点免受 DOS 攻击。这将树的大小限制为最多 2^100 个叶子，对于任何可设想的用途来说都应当足够。

IAVL+ 树

由于 CometBFT 只使用简单 Merkle 树，因此应用开发者应在自己的应用中使用自定义的 Merkle 树。例如，IAVL+ Tree 这种用于持久化应用状态的不可变自平衡二叉树，就被 Cosmos SDK 所采用。

JSON

为了与之前的 RPC 层保持向后兼容，CometBFT 定义了自己的 JSON 编码。已注册类型编码如下：

{
  "type": "<type name>",
  "value": <JSON>
}

例如，一个 ED25519 PubKey 看起来如下：

{
  "type": "tendermint/PubKeyEd25519",
  "value": "uZ4h63OFWuQ36ZZ4Bd6NF+/w9fWUwrOncrQsackrsTk="
}

其中，"value" 是原始 pubkey 字节的 base64 编码，"type" 是 Ed25519 公钥的类型名。

已签名消息

共识中的已签名消息（例如投票、提案）使用 protobuf 编码。在签名时，消息中的元素会被重新排序，使固定长度字段排在前面，从而便于快速检查类型、高度和轮次。 ChainID 也会被附加到末尾。我们将这种编码称为 SignBytes。例如，投票的 SignBytes 就是以下结构体的 protobuf 编码：

message CanonicalVote {
  SignedMsgType             type      = 1;
  sfixed64                  height    = 2;  // canonicalization requires fixed size encoding here
  sfixed64                  round     = 3;  // canonicalization requires fixed size encoding here
  CanonicalBlockID          block_id  = 4;
  google.protobuf.Timestamp timestamp = 5;
  string                    chain_id  = 6;
}

字段顺序以及前三个字段使用定长编码，是为了便于 HSM 解析 SignBytes 而做的优化。这样可以为此场景下需要读取的关键字段创建固定偏移量。

注意：所有规范化消息都带有长度前缀。

更多细节请参阅签名规范。另请参阅 #1622 中的背景讨论。

Protocol Buffers

CometBFT uses Protocol Buffers, specifically proto3, for all data structures. Please see the Proto3 language guide for more details.

Byte Arrays

The encoding of a byte array is simply the raw-bytes prefixed with the length of the array as a UVarint (what proto calls a Varint). For details on varints, see the protobuf spec. For example, the byte-array [0xA, 0xB] would be encoded as 0x020A0B, while a byte-array containing 300 entires beginning with [0xA, 0xB, ...] would be encoded as 0xAC020A0B... where 0xAC02 is the UVarint encoding of 300.

Hashing

CometBFT uses SHA256 as its hash function. Objects are always serialized before being hashed. So SHA256(obj) is short for SHA256(ProtoEncoding(obj)).

Public Key Cryptography

CometBFT uses Protobuf Oneof to distinguish between different types public keys, and signatures. Additionally, for each public key, CometBFT defines an Address function that can be used as a more compact identifier in place of the public key. Here we list the concrete types, their names, and prefix bytes for public keys and signatures, as well as the address schemes for each PubKey. Note for brevity we don’t include details of the private keys beyond their type and name.

Key Types

Each type specifies it’s own pubkey, address, and signature format.

Ed25519

The address is the first 20-bytes of the SHA256 hash of the raw 32-byte public key:

address = SHA256(pubkey)[:20]

The signature is the raw 64-byte ED25519 signature. CometBFT adopts zip215 for verification of ed25519 signatures.

Note: This change will be released in the next major release of CometBFT.

Secp256k1

The address is the first 20-bytes of the SHA256 hash of the raw 32-byte public key:

address = SHA256(pubkey)[:20]

Other Common Types

BitArray

The BitArray is used in some consensus messages to represent votes received from validators, or parts received in a block. It is represented with a struct containing the number of bits (Bits) and the bit-array itself encoded in base64 (Elems).

Name	Type
bits	int64
elems	slice of int64 (`[]int64`)

Note BitArray receives a special JSON encoding in the form of x and _ representing 1 and 0. Ie. the BitArray 10110 would be JSON encoded as "x_xx_"

Part

Part is used to break up blocks into pieces that can be gossiped in parallel and securely verified using a Merkle tree of the parts. Part contains the index of the part (Index), the actual underlying data of the part (Bytes), and a Merkle proof that the part is contained in the set (Proof).

Name	Type
index	uint32
bytes	slice of bytes (`[]byte`)
proof	proof

See details of SimpleProof, below.

MakeParts

Encode an object using Protobuf and slice it into parts. CometBFT uses a part size of 65536 bytes, and allows a maximum of 1601 parts (see types.MaxBlockPartsCount). This corresponds to the hard-coded block size limit of 100MB.

func MakeParts(block Block) []Part

Merkle Trees

For an overview of Merkle trees, see wikipedia We use the RFC 6962 specification of a merkle tree, with sha256 as the hash function. Merkle trees are used throughout CometBFT to compute a cryptographic digest of a data structure. The differences between RFC 6962 and the simplest form a merkle tree are that:

leaf nodes and inner nodes have different hashes. This is for “second pre-image resistance”, to prevent the proof to an inner node being valid as the proof of a leaf. The leaf nodes are SHA256(0x00 || leaf_data), and inner nodes are SHA256(0x01 || left_hash || right_hash).
When the number of items isn’t a power of two, the left half of the tree is as big as it could be. (The largest power of two less than the number of items) This allows new leaves to be added with less recomputation. For example:

   Simple Tree with 6 items           Simple Tree with 7 items

              *                                  *
             / \                                / \
           /     \                            /     \
         /         \                        /         \
       /             \                    /             \
      *               *                  *               *
     / \             / \                / \             / \
    /   \           /   \              /   \           /   \
   /     \         /     \            /     \         /     \
  *       *       h4     h5          *       *       *       h6
 / \     / \                        / \     / \     / \
h0  h1  h2 h3                      h0  h1  h2  h3  h4  h5

MerkleRoot

The function MerkleRoot is a simple recursive function defined as follows:

// SHA256([]byte{})
func emptyHash() []byte {
    return tmhash.Sum([]byte{})
}

// SHA256(0x00 || leaf)
func leafHash(leaf []byte) []byte {
 return tmhash.Sum(append(0x00, leaf...))
}

// SHA256(0x01 || left || right)
func innerHash(left []byte, right []byte) []byte {
 return tmhash.Sum(append(0x01, append(left, right...)...))
}

// largest power of 2 less than k
func getSplitPoint(k int) { ... }

func MerkleRoot(items [][]byte) []byte{
 switch len(items) {
 case 0:
  return empthHash()
 case 1:
  return leafHash(items[0])
 default:
  k := getSplitPoint(len(items))
  left := MerkleRoot(items[:k])
  right := MerkleRoot(items[k:])
  return innerHash(left, right)
 }
}

Note: MerkleRoot operates on items which are arbitrary byte arrays, not necessarily hashes. For items which need to be hashed first, we introduce the Hashes function:

func Hashes(items [][]byte) [][]byte {
    return SHA256 of each item
}

Note: we will abuse notion and invoke MerkleRoot with arguments of type struct or type []struct. For struct arguments, we compute a [][]byte containing the protobuf encoding of each field in the struct, in the same order the fields appear in the struct. For []struct arguments, we compute a [][]byte by protobuf encoding the individual struct elements.

Merkle Proof

Proof that a leaf is in a Merkle tree is composed as follows:

Name	Type
total	int64
index	int64
leafHash	slice of bytes (`[]byte`)
aunts	Matrix of bytes ([][]byte)

Which is verified as follows:

func (proof Proof) Verify(rootHash []byte, leaf []byte) bool {
 assert(proof.LeafHash, leafHash(leaf)

 computedHash := computeHashFromAunts(proof.Index, proof.Total, proof.LeafHash, proof.Aunts)
    return computedHash == rootHash
}

func computeHashFromAunts(index, total int, leafHash []byte, innerHashes [][]byte) []byte{
 assert(index < total && index >= 0 && total > 0)

 if total == 1{
  assert(len(proof.Aunts) == 0)
  return leafHash
 }

 assert(len(innerHashes) > 0)

 numLeft := getSplitPoint(total) // largest power of 2 less than total
 if index < numLeft {
  leftHash := computeHashFromAunts(index, numLeft, leafHash, innerHashes[:len(innerHashes)-1])
  assert(leftHash != nil)
  return innerHash(leftHash, innerHashes[len(innerHashes)-1])
 }
 rightHash := computeHashFromAunts(index-numLeft, total-numLeft, leafHash, innerHashes[:len(innerHashes)-1])
 assert(rightHash != nil)
 return innerHash(innerHashes[len(innerHashes)-1], rightHash)
}

The number of aunts is limited to 100 (MaxAunts) to protect the node against DOS attacks. This limits the tree size to 2^100 leaves, which should be sufficient for any conceivable purpose.

IAVL+ Tree

Because CometBFT only uses a Simple Merkle Tree, application developers are expected to use their own Merkle tree in their applications. For example, the IAVL+ Tree - an immutable self-balancing binary tree for persisting application state is used by the Cosmos SDK

JSON

CometBFT has its own JSON encoding in order to keep backwards compatibility with the previous RPC layer. Registered types are encoded as:

{
  "type": "<type name>",
  "value": <JSON>
}

For instance, an ED25519 PubKey would look like:

{
  "type": "tendermint/PubKeyEd25519",
  "value": "uZ4h63OFWuQ36ZZ4Bd6NF+/w9fWUwrOncrQsackrsTk="
}

Where the "value" is the base64 encoding of the raw pubkey bytes, and the "type" is the type name for Ed25519 pubkeys.

Signed Messages

Signed messages (eg. votes, proposals) in the consensus are encoded using protobuf. When signing, the elements of a message are re-ordered so the fixed-length fields are first, making it easy to quickly check the type, height, and round. The ChainID is also appended to the end. We call this encoding the SignBytes. For instance, SignBytes for a vote is the protobuf encoding of the following struct:

message CanonicalVote {
  SignedMsgType             type      = 1;
  sfixed64                  height    = 2;  // canonicalization requires fixed size encoding here
  sfixed64                  round     = 3;  // canonicalization requires fixed size encoding here
  CanonicalBlockID          block_id  = 4;
  google.protobuf.Timestamp timestamp = 5;
  string                    chain_id  = 6;
}

The field ordering and the fixed sized encoding for the first three fields is optimized to ease parsing of SignBytes in HSMs. It creates fixed offsets for relevant fields that need to be read in this context.

Note: All canonical messages are length prefixed.

For more details, see the signing spec. Also, see the motivating discussion in #1622.

​协议缓冲区

​字节数组

​哈希

​公钥密码学

​密钥类型

​Ed25519

​Secp256k1

​其他常见类型

​BitArray

​Part

​MakeParts

​Merkle 树

​MerkleRoot

​Merkle 证明

​IAVL+ 树

​JSON

​已签名消息

​Protocol Buffers

​Byte Arrays

​Hashing

​Public Key Cryptography

​Key Types

​Ed25519

​Secp256k1

​Other Common Types

​BitArray

​Part

​MakeParts

​Merkle Trees

​MerkleRoot

​Merkle Proof

​IAVL+ Tree

​JSON

​Signed Messages

协议缓冲区

字节数组

哈希

公钥密码学

密钥类型

Ed25519

Secp256k1

其他常见类型

BitArray

Part

MakeParts

Merkle 树

MerkleRoot

Merkle 证明

IAVL+ 树

JSON

已签名消息

Protocol Buffers

Byte Arrays

Hashing

Public Key Cryptography

Key Types

Ed25519

Secp256k1

Other Common Types

BitArray

Part

MakeParts

Merkle Trees

MerkleRoot

Merkle Proof

IAVL+ Tree

JSON

Signed Messages