ADR 027: Deterministic Protobuf Serialization

​

变更记录

• 2020-08-07：初始草案
• 2020-09-01：进一步澄清规则

​

状态

​

摘要

​

背景

​

决策

​

规范

​

范围

​

背景 - Protobuf3 编码

​

序列化规则

1. 字段必须且只能按升序序列化一次
2. 不得添加额外字段或任何额外数据
3. 必须省略默认值
4. 标量数值类型的 repeated 字段必须使用 packed encoding
5. Varint 编码不得长于必要长度：
   • 不得有尾随的零字节（按小端表示，即按大端表示时不得有前导零）。根据上面的规则 3，默认值 0 必须省略，因此该规则在这种情况下不适用。
   • Varint 的最大值必须为 FF FF FF FF FF FF FF FF FF 01。 换句话说，解码后，70 位无符号整数的最高 6 位必须为 0。（10 字节 varint 由 10 组 7 位组成，即 70 位，其中只有最低的 70-6=64 位是有效的。）
   • 32 位数值在 varint 编码中的最大值必须为 FF FF FF FF 0F， 但有一个例外（如下）。换句话说，解码后，70 位无符号整数的最高 38 位必须为 0。
     • 上述规则的唯一例外是负数 int32，它必须使用完整的 10 个字节进行编码，以完成符号扩展²。
   • 布尔值在 varint 编码中的最大值必须为 01（也就是它只能是 0 或 1）。根据上面的规则 3，默认值 0 必须省略，因此如果包含某个布尔值，它的值必须为 1。

​

实现

• 使用默认遵循上述规则的 protobuf 序列化器。 例如， gogoproto 已知在大多数情况下是兼容的，但在使用某些注解（如 nullable = false）时并非如此。另一种选择也可能是对现有序列化器进行相应配置。
• 在编码前规范化默认值。 如果你的序列化器遵循规则 1 和 2，并允许你在序列化时显式取消设置字段，你可以将默认值规范化为未设置状态。使用 protobuf.js 时可以这样做：
  const bytes = SignDoc.encode({
    bodyBytes: body.length > 0 ? body : null, // normalize empty bytes to unset
    authInfoBytes: authInfo.length > 0 ? authInfo : null, // normalize empty bytes to unset
    chainId: chainId || null, // normalize "" to unset
    accountNumber: accountNumber || null, // normalize 0 to unset
    accountSequence: accountSequence || null, // normalize 0 to unset
  }).finish();
  
• 为所需类型手写序列化器。 如果上述方法都不适用，你可以自行编写序列化器。对于 SignDoc，在 Go 中基于现有 protobuf 工具，大致会是下面这样：
  if !signDoc.body_bytes.empty() {
      buf.WriteUVarInt64(0xA) // wire type and field number for body_bytes
      buf.WriteUVarInt64(signDoc.body_bytes.length())
  
  buf.WriteBytes(signDoc.body_bytes)
  }
      if !signDoc.auth_info.empty() {
      buf.WriteUVarInt64(0x12) // wire type and field number for auth_info
      buf.WriteUVarInt64(signDoc.auth_info.length())
  
  buf.WriteBytes(signDoc.auth_info)
  }
      if !signDoc.chain_id.empty() {
      buf.WriteUVarInt64(0x1a) // wire type and field number for chain_id
      buf.WriteUVarInt64(signDoc.chain_id.length())
  
  buf.WriteBytes(signDoc.chain_id)
  }
      if signDoc.account_number != 0 {
      buf.WriteUVarInt64(0x20) // wire type and field number for account_number
      buf.WriteUVarInt(signDoc.account_number)
  }
      if signDoc.account_sequence != 0 {
      buf.WriteUVarInt64(0x28) // wire type and field number for account_sequence
      buf.WriteUVarInt(signDoc.account_sequence)
  }
  

  See all 26 lines

​

测试向量

package blog;
syntax = "proto3";

enum Type {
  UNSPECIFIED = 0;
  IMAGES = 1;
  NEWS = 2;
};

enum Review {
  UNSPECIFIED = 0;
  ACCEPTED = 1;
  REJECTED = 2;
};

message Article {
  string title = 1;
  string description = 2;
  uint64 created = 3;
  uint64 updated = 4;
  bool public = 5;
  bool promoted = 6;
  Type type = 7;
  Review review = 8;
  repeated string comments = 9;
  repeated string backlinks = 10;
};

title: "The world needs change 🌳"
description: ""
created: 1596806111080
updated: 0
public: true
promoted: false
type: Type.NEWS
review: Review.UNSPECIFIED
comments: ["Nice one", "Thank you"]
backlinks: []

0a1b54686520776f726c64206e65656473206368616e676520f09f8cb318e8bebec8bc2e280138024a084e696365206f6e654a095468616e6b20796f75

$ echo 0a1b54686520776f726c64206e65656473206368616e676520f09f8cb318e8bebec8bc2e280138024a084e696365206f6e654a095468616e6b20796f75 | xxd -r -p | protoc --decode_raw
1: "The world needs change \360\237\214\263"
3: 1596806111080
5: 1
7: 2
9: "Nice one"
9: "Thank you"

​

影响

​

正面影响

• 规则定义明确，可独立于参考实现进行验证
• 足够简单，能够保持交易签名实现门槛较低
• 它使我们能够继续在 SignDoc 中使用 0 和其他空值，从而避免为 0 sequence 设计变通方案。这并不意味着不应合并 链接 中的更改，只是其重要性已经没有那么高。

​

负面影响

• 在实现交易签名时，必须理解并实现上述编码规则。
• 规则 3 的存在为实现增加了一些复杂度。
• 某些数据结构可能需要编写自定义序列化代码。因此，这些代码的可移植性不强，每个实现序列化的客户端都需要额外工作，才能正确处理自定义数据结构。

​

中性影响

​

在 Cosmos SDK 中的使用

​

参考资料

• ¹ 当一条消息被序列化时，其已知字段或未知字段应按何种顺序写出，并没有保证。序列化顺序属于实现细节，任何特定实现的细节在未来都可能发生变化。因此，protocol buffer 解析器必须能够按任意顺序解析字段。 摘自 Link
• ² Link
• ³ 请注意，对于标量消息字段，一旦消息被解析，就无法判断某个字段是被显式设置为了默认值（例如某个布尔值是否被设置为 false），还是根本没有被设置：在定义消息类型时应牢记这一点。例如，如果你不希望某种行为默认也会发生，就不要使用一个在设置为 false 时会开启该行为的布尔值。 摘自 Link
• ⁴ 当一条消息被解析时，如果编码后的消息不包含某个特定的单值元素，则解析后对象中的对应字段会被设置为该字段的默认值。 摘自 Link
• ⁵ 另请注意，如果某个标量消息字段被设置为其默认值，该值将不会在 wire 上被序列化。 摘自 Link
• ⁶ 对于枚举类型，默认值是第一个定义的枚举值，并且该值必须为 0。 摘自 Link
• ⁷ 对于消息字段，该字段不会被设置。其确切值取决于具体语言。 摘自 Link
• 编码规则以及部分推理内容取自 canonical-proto3 Aaron Craelius

​

Changelog

• 2020-08-07: Initial Draft
• 2020-09-01: Further clarify rules

​

Status

​

Abstract

​

Context

​

Decision

​

Specification

​

Scope

​

Background - Protobuf3 Encoding

​

Serialization rules

1. Fields must be serialized only once in ascending order
2. Extra fields or any extra data must not be added
3. Default values must be omitted
4. repeated fields of scalar numeric types must use packed encoding
5. Varint encoding must not be longer than needed:
   • No trailing zero bytes (in little endian, i.e. no leading zeroes in big endian). Per rule 3 above, the default value of 0 must be omitted, so this rule does not apply in such cases.
   • The maximum value for a varint must be FF FF FF FF FF FF FF FF FF 01. In other words, when decoded, the highest 6 bits of the 70-bit unsigned integer must be 0. (10-byte varints are 10 groups of 7 bits, i.e. 70 bits, of which only the lowest 70-6=64 are useful.)
   • The maximum value for 32-bit values in varint encoding must be FF FF FF FF 0F with one exception (below). In other words, when decoded, the highest 38 bits of the 70-bit unsigned integer must be 0.
     • The one exception to the above is negative int32, which must be encoded using the full 10 bytes for sign extension².
   • The maximum value for Boolean values in varint encoding must be 01 (i.e. it must be 0 or 1). Per rule 3 above, the default value of 0 must be omitted, so if a Boolean is included it must have a value of 1.

​

Implementation

• Use a protobuf serializer that follows the above rules by default. E.g. gogoproto is known to be compliant by in most cases, but not when certain annotations such as nullable = false are used. It might also be an option to configure an existing serializer accordingly.
• Normalize default values before encoding them. If your serializer follows rule 1. and 2. and allows you to explicitly unset fields for serialization, you can normalize default values to unset. This can be done when working with protobuf.js:
  const bytes = SignDoc.encode({
    bodyBytes: body.length > 0 ? body : null, // normalize empty bytes to unset
    authInfoBytes: authInfo.length > 0 ? authInfo : null, // normalize empty bytes to unset
    chainId: chainId || null, // normalize "" to unset
    accountNumber: accountNumber || null, // normalize 0 to unset
    accountSequence: accountSequence || null, // normalize 0 to unset
  }).finish();
  
• Use a hand-written serializer for the types you need. If none of the above ways works for you, you can write a serializer yourself. For SignDoc this would look something like this in Go, building on existing protobuf utilities:
  if !signDoc.body_bytes.empty() {
      buf.WriteUVarInt64(0xA) // wire type and field number for body_bytes
      buf.WriteUVarInt64(signDoc.body_bytes.length())
  
  buf.WriteBytes(signDoc.body_bytes)
  }
      if !signDoc.auth_info.empty() {
      buf.WriteUVarInt64(0x12) // wire type and field number for auth_info
      buf.WriteUVarInt64(signDoc.auth_info.length())
  
  buf.WriteBytes(signDoc.auth_info)
  }
      if !signDoc.chain_id.empty() {
      buf.WriteUVarInt64(0x1a) // wire type and field number for chain_id
      buf.WriteUVarInt64(signDoc.chain_id.length())
  
  buf.WriteBytes(signDoc.chain_id)
  }
      if signDoc.account_number != 0 {
      buf.WriteUVarInt64(0x20) // wire type and field number for account_number
      buf.WriteUVarInt(signDoc.account_number)
  }
      if signDoc.account_sequence != 0 {
      buf.WriteUVarInt64(0x28) // wire type and field number for account_sequence
      buf.WriteUVarInt(signDoc.account_sequence)
  }
  

  See all 26 lines

​

Test vectors

package blog;
syntax = "proto3";

enum Type {
  UNSPECIFIED = 0;
  IMAGES = 1;
  NEWS = 2;
};

enum Review {
  UNSPECIFIED = 0;
  ACCEPTED = 1;
  REJECTED = 2;
};

message Article {
  string title = 1;
  string description = 2;
  uint64 created = 3;
  uint64 updated = 4;
  bool public = 5;
  bool promoted = 6;
  Type type = 7;
  Review review = 8;
  repeated string comments = 9;
  repeated string backlinks = 10;
};

title: "The world needs change 🌳"
description: ""
created: 1596806111080
updated: 0
public: true
promoted: false
type: Type.NEWS
review: Review.UNSPECIFIED
comments: ["Nice one", "Thank you"]
backlinks: []

0a1b54686520776f726c64206e65656473206368616e676520f09f8cb318e8bebec8bc2e280138024a084e696365206f6e654a095468616e6b20796f75

$ echo 0a1b54686520776f726c64206e65656473206368616e676520f09f8cb318e8bebec8bc2e280138024a084e696365206f6e654a095468616e6b20796f75 | xxd -r -p | protoc --decode_raw
1: "The world needs change \360\237\214\263"
3: 1596806111080
5: 1
7: 2
9: "Nice one"
9: "Thank you"

​

Consequences

​

Positive

• Well defined rules that can be verified independent of a reference implementation
• Simple enough to keep the barrier to implement transaction signing low
• It allows us to continue to use 0 and other empty values in SignDoc, avoiding the need to work around 0 sequences. This does not imply the change from Link should not be merged, but not too important anymore.

​

Negative

• When implementing transaction signing, the encoding rules above must be understood and implemented.
• The need for rule number 3. adds some complexity to implementations.
• Some data structures may require custom code for serialization. Thus the code is not very portable - it will require additional work for each client implementing serialization to properly handle custom data structures.

​

Neutral

​

Usage in Cosmos SDK

​

References

• ¹ When a message is serialized, there is no guaranteed order for how its known or unknown fields should be written. Serialization order is an implementation detail and the details of any particular implementation may change in the future. Therefore, protocol buffer parsers must be able to parse fields in any order. from Link
• ² Link
• ³ Note that for scalar message fields, once a message is parsed there’s no way of telling whether a field was explicitly set to the default value (for example whether a boolean was set to false) or just not set at all: you should bear this in mind when defining your message types. For example, don’t have a boolean that switches on some behavior when set to false if you don’t want that behavior to also happen by default. from Link
• ⁴ When a message is parsed, if the encoded message does not contain a particular singular element, the corresponding field in the parsed object is set to the default value for that field. from Link
• ⁵ Also note that if a scalar message field is set to its default, the value will not be serialized on the wire. from Link
• ⁶ For enums, the default value is the first defined enum value, which must be 0. from Link
• ⁷ For message fields, the field is not set. Its exact value is language-dependent. from Link
• Encoding rules and parts of the reasoning taken from canonical-proto3 Aaron Craelius