1 个不稳定版本
0.1.3 | 2022年10月24日 |
---|
#1905 在 编码
64KB
1K SLoC
二进制规范序列化 (BCS)
BCS(之前称为“Libra规范序列化”或LCS)是在Diem区块链环境中开发的一种序列化格式。
BCS的设计主要目标是
- 提供良好的性能和简洁的(二进制)表示;
- 支持Rust中常用的丰富数据类型;
- 强制执行规范序列化,即给定类型的每个值应该有单个有效的表示。
BCS还旨在通过在序列化/反序列化期间对大型或嵌套容器执行良好定义的限制来减轻恶意输入的后果。
Rust 实现
该crate提供BCS作为编码格式的Rust实现,用于Serde库。因此,此实现涵盖了Serde支持的大多数数据类型——包括用户定义的结构体、标记变体(Rust枚举)、元组和映射——不包括浮点数、单个Unicode字符(char)和集合。
由于有独立的项目serde-reflection,BCS也适用于其他编程语言。
在密码学中的应用
BCS格式保证了规范序列化,这意味着对于任何给定的数据类型,内存中的值和有效的字节表示之间都存在一一对应关系。
在密码学应用中,规范序列化有以下几个优点
- 它为将内存中的值与密码学哈希关联提供了一种自然且可靠的方法。
- 它允许将消息的签名定义为对序列化字节或内存值的签名。
请注意,BCS为每个数据类型分别确保了规范序列化。序列化值的类型必须由应用程序本身强制执行。通常使用每个数据类型的唯一哈希种子来满足这一要求。(例如,请参阅Diem的密码学库。)
向后兼容性
按设计,BCS不提供隐式版本或向后/向前兼容性,因此应用程序必须提前仔细计划临时扩展点。
- 枚举可用于显式版本和向后兼容性(例如,可扩展查询接口)。
- 在某些情况下,还可以添加类型为
Vec<u8>
的数据字段,以便允许(未来的)未知负载以序列化形式存在。
详细规范
BCS支持以下数据类型
- 布尔值
- 有符号8位、16位、32位、64位和128位整数
- 无符号8位、16位、32位、64位和128位整数
- 选项
- 单位(空值)
- 固定和可变长度序列
- UTF-8编码字符串
- 元组
- 结构体(也称为“struct”)
- 外部标记枚举(也称为“enum”)
- 映射
BCS不是一个自描述的格式。因此,为了反序列化消息,必须事先知道消息类型和布局。
除非指定,否则所有数字都以小端、二进制补码格式存储。
递归和BCS数据深度
允许递归数据结构(例如树)。然而,由于在序列化(反序列化)过程中可能发生栈溢出,任何有效BCS数据的容器深度不能超过常量MAX_CONTAINER_DEPTH
。正式定义容器深度为序列化(反序列化)过程中遍历的结构体和枚举的数量。
此定义旨在最大限度地减少操作次数,同时确保已知BCS格式的序列化(反序列化)不会导致任意大的栈分配。
例如,如果v1
和v2
是深度为n1
和n2
的值,
- 结构值
Foo { v1, v2 }
的深度为1 + max(n1, n2)
; - 枚举值
E::Foo { v1, v2 }
的深度为1 + max(n1, n2)
; - 对
(v1, v2)
的深度为max(n1, n2)
; - 值
Some(v1)
的深度为n1
。
所有字符串和整数值的深度为0
。
布尔型和整型
类型 | 原始数据 | 十六进制表示 | 序列化字节 |
---|---|---|---|
布尔型 | 真/假 | 0x01 / 0x00 | 01 / 00 |
8位有符号整数 | -1 | 0xFF | FF |
8位无符号整数 | 1 | 0x01 | 01 |
16位有符号整数 | -4660 | 0xEDCC | CC ED |
16位无符号整数 | 4660 | 0x1234 | 34 12 |
32位有符号整数 | -305419896 | 0xEDCBA988 | 88 A9 CB ED |
32位无符号整数 | 305419896 | 0x12345678 | 78 56 34 12 |
64位有符号整数 | -1311768467750121216 | 0xEDCBA98754321100 | 00 11 32 54 87 A9 CB ED |
64位无符号整数 | 1311768467750121216 | 0x12345678ABCDEF00 | 00 EF CD AB 78 56 34 12 |
ULEB128编码的整数
BCS格式还使用ULEB128编码在内部表示无符号32位整数,在通常期望小值的两种情况下:1)可变长度序列的长度;(2)枚举值的标签(请参阅下面的相应部分)。
类型 | 原始数据 | 十六进制表示 | 序列化字节 |
---|---|---|---|
ULEB128编码的u32整数 | 2^0 = 1 | 0x00000001 | 01 |
2^7 = 128 | 0x00000080 | 80 01 | |
2^14 = 16384 | 0x00004000 | 80 80 01 | |
2^21 = 2097152 | 0x00200000 | 80 80 80 01 | |
2^28 = 268435456 | 0x10000000 | 80 80 80 80 01 | |
9487 | 0x0000250f | 8f 4a |
通常,ULEB128编码由一个基为128(7位)的数字的小端序列组成。每个数字通过将最高位设置为1来完成到字节的转换,除了最后一个(最高有效位)的数字,其最高位设置为0。
在BCS中,解码ULEB128字节的结果必须适合32位无符号整数,并且处于规范形式。例如,以下值将被拒绝
- 80 80 80 80 80 01 (2^36) 太大了。
- 80 80 80 80 10 (2^33) 太大了。
- 80 00 不是0的最小编码。
可选数据
可选或可空数据要么以完整形式存在,要么不存在。BCS将此表示为表示数据存在(0x01
)或不存在(0x00
)的单个字节。如果数据存在,则随后跟随着该数据的序列化形式。例如
let some_data: Option<u8> = Some(8);
assert_eq!(to_bytes(&some_data)?, vec![1, 8]);
let no_data: Option<u8> = None;
assert_eq!(to_bytes(&no_data)?, vec![0]);
固定长度和可变长度序列
序列可以由任何BCS支持的类型(甚至复杂结构)组成,但序列中的所有元素必须是同一类型。如果序列的长度是固定且已知的,那么BCS将其表示为序列中每个单独元素序列化的连接。如果序列的长度是可变的,那么序列化的序列前面有一个以ULEB128编码的无符号整数,表示序列中的元素数量。所有可变长度序列的长度必须不超过MAX_SEQUENCE_LENGTH
元素。
let fixed: [u16; 3] = [1, 2, 3];
assert_eq!(to_bytes(&fixed)?, vec![1, 0, 2, 0, 3, 0]);
let variable: Vec<u16> = vec![1, 2];
assert_eq!(to_bytes(&variable)?, vec![2, 1, 0, 2, 0]);
let large_variable_length: Vec<()> = vec![(); 9_487];
assert_eq!(to_bytes(&large_variable_length)?, vec![0x8f, 0x4a]);
字符串
只支持有效的UTF-8字符串。BCS将这些字符串序列化为可变长度的字节序列,即长度以ULEB128编码的无符号整数开头,后面是字符串的字节表示。
// Note that this string has 10 characters but has a byte length of 24
let utf8_str = "çå∞≠¢õß∂ƒ∫";
let expecting = vec![
24, 0xc3, 0xa7, 0xc3, 0xa5, 0xe2, 0x88, 0x9e, 0xe2, 0x89, 0xa0, 0xc2,
0xa2, 0xc3, 0xb5, 0xc3, 0x9f, 0xe2, 0x88, 0x82, 0xc6, 0x92, 0xe2, 0x88, 0xab,
];
assert_eq!(to_bytes(&utf8_str)?, expecting);
元组
元组是对象的类型化组合:(Type0, Type1)
元组被视为固定长度序列,其中序列中的每个元素可以是BCS支持的任何不同类型。元组的每个元素按照在元组内定义的顺序进行序列化,即[tuple.0, tuple.2]。
let tuple = (-1i8, "diem");
let expecting = vec![0xFF, 4, b'd', b'i', b'e', b'm'];
assert_eq!(to_bytes(&tuple)?, expecting);
结构体
结构体是由可能具有不同类型的字段组成的固定长度序列。结构体内的每个字段按照规范结构定义中指定的顺序进行序列化。结构体可以存在于其他结构体中,因此BCS递归到每个结构体并将它们按顺序序列化。序列化格式中没有标签,结构体顺序定义了序列化流中的组织。
#[derive(Serialize)]
struct MyStruct {
boolean: bool,
bytes: Vec<u8>,
label: String,
}
#[derive(Serialize)]
struct Wrapper {
inner: MyStruct,
name: String,
}
let s = MyStruct {
boolean: true,
bytes: vec![0xC0, 0xDE],
label: "a".to_owned(),
};
let s_bytes = to_bytes(&s)?;
let mut expecting = vec![1, 2, 0xC0, 0xDE, 1, b'a'];
assert_eq!(s_bytes, expecting);
let w = Wrapper {
inner: s,
name: "b".to_owned(),
};
let w_bytes = to_bytes(&w)?;
assert!(w_bytes.starts_with(&s_bytes));
expecting.append(&mut vec![1, b'b']);
assert_eq!(w_bytes, expecting);
外部标记枚举
枚举通常表示为可以采取许多不同变体的类型。在BCS中,每个变体都映射到一个变体索引,一个ULEB128编码的32位无符号整数,后面是如果类型具有关联值则序列化的数据。关联类型可以是任何BCS支持的类型。变体索引基于规范枚举定义中变体的顺序确定,其中第一个变体索引为0
,第二个变体索引为1
等。
#[derive(Serialize)]
enum E {
Variant0(u16),
Variant1(u8),
Variant2(String),
}
let v0 = E::Variant0(8000);
let v1 = E::Variant1(255);
let v2 = E::Variant2("e".to_owned());
assert_eq!(to_bytes(&v0)?, vec![0, 0x40, 0x1F]);
assert_eq!(to_bytes(&v1)?, vec![1, 0xFF]);
assert_eq!(to_bytes(&v2)?, vec![2, 1, b'e']);
如果您需要序列化C样式的枚举,应使用原始整数类型。
映射(键/值存储)
映射表示为可变长度、排序的键/值对序列。键必须是唯一的,并且元组按每个键的BCS字节按字典顺序增加排序。表示方式与其他可变长度序列类似。特别是,它前面是元组数量,以ULEB128编码。
let mut map = HashMap::new();
map.insert(b'e', b'f');
map.insert(b'a', b'b');
map.insert(b'c', b'd');
let expecting = vec![(b'a', b'b'), (b'c', b'd'), (b'e', b'f')];
assert_eq!(to_bytes(&map)?, to_bytes(&expecting)?);
贡献
有关如何提供帮助的信息,请参阅CONTRIBUTING文件。
许可证
此项目可以在Apache 2.0许可证的条款下使用。
依赖项
~0.4-1MB
~23K SLoC