1 个不稳定版本
0.20.1 | 2024年2月11日 |
---|
#604 在 编码
55KB
1K SLoC
RISC Zero的更小序列化
此存储库实现了一个针对RISC Zero序列化的不同算法,并在https://github.com/risc0/risc0/pull/1303中进行讨论。
该算法有可能成为RISC Zero的官方序列化器,但仍有一些问题待解决。
在此期间,开发人员可以在自己的实现中使用此序列化器进行定制化的序列化和反序列化。
动机
RISC Zero通过serde
框架将zkVM的输入序列化为一个u32
向量。然而,这意味着它面临着Rust中的一个主要开放问题。
当serde
为Rust数据结构实现Serialize
和Deserialize
时,它具有以下实现
impl<T> Serialize for Vec<T> where T: Serialize
{
#[inline]
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where S: Serializer,
{
serializer.collect_seq(self)
}
}
collect_seq
有以下的默认实现,意味着元素会一个接一个地序列化,作为一个连接。
pub trait Serializer: Sized {
fn collect_seq<I>(self, iter: I) -> Result<Self::Ok, Self::Error>
where I: IntoIterator, <I as IntoIterator>::Item: Serialize,
{
let mut iter = iter.into_iter();
let mut serializer = tri!(self.serialize_seq(iterator_len_hint(&iter)));
tri!(iter.try_for_each(|item| serializer.serialize_element(&item)));
serializer.end()
}
}
这会影响RISC Zero,因为现在,为了序列化一个字节数组Vec<u8>
,每个数字都会被转换成u32,然后序列化一个Vec<u32>
数组,这会导致4倍存储开销。
回到serde的讨论。问题是,我们可能希望为不同的T
指定不同的规则,特别是当T = u8
时,以获得更好的效率。一种解决方案是serde_bytes存储库,它允许通过自定义serde函数绕过限制。
use serde::{Deserialize, Serialize};
#[derive(Deserialize, Serialize)]
struct Efficient<'a> {
#[serde(with = "serde_bytes")]
bytes: &'a [u8],
#[serde(with = "serde_bytes")]
byte_buf: Vec<u8>,
#[serde(with = "serde_bytes")]
byte_array: [u8; 314],
}
这个想法是实施一种不同的实现策略,该策略不将通用规则应用于Vec<T>
(对于任何可序列化的T
),并要求开发者在这两种策略之间进行切换。这种方法存在一些问题
- 它要求开发者修改多层和抽象层。如果一个开发者使用了四个crate——A、B、C、D——A依赖于B,B依赖于C,C依赖于D,而D使用
Vec<u8>
,开发者需要一路下到D来更改其数据结构的定义。这可能导致与整个系统的兼容性问题。 - 很难全面解决,因为
Vec<u8>
在Rust数据结构中非常常见,开发者需要对代码进行几次遍历来解决此问题。 - 如果需要大量的修补,同步代码与原始仓库将会非常困难。这不仅增加了维护开销,而且在实践中往往会导致安全问题。
人们对这个问题的希望寄托在特殊化上,但这种情况很快成为稳定版的机会非常有限。在生产环境中使用nightly版本被强烈反对,并且不适合RISC Zero的zkVM,因为它正在成为Rust的一部分。
我们的解决方案
之前的讨论表明自下而上的方法可能是灾难性的。这个仓库建议自上而下的方法,换句话说,我们不需要对Rust中实现的现有数据结构进行任何修改,而是提供一个序列化器,将RISC Zero输入转换为Vec<u32>
,并进行相应的反序列化。
我们的想法是有一个侧缓冲区,我们称之为ByteBuffer
,由ByteHandler
管理。当它观察到几个连续的u8正在序列化时,它会尝试将它们组合在一起,而不是让每个都占用一个字。
字节缓冲区由四个字节组成。因此,当缓冲区中有四个字节时,就会产生一个字,缓冲区就会被清空。当序列化其他内容时,字节处理器会立即发出一个字并清理缓冲区。
实现细节可以在代码库中找到。以下我们总结了代码中的主要更改。
序列化
serialize_u8
和serialize_u32
的旧代码是对比代码更改前后的好例子,除了新有限状态自动机的代码。
// Old
impl<'a, W: WordWrite> serde::ser::Serializer for &'a mut Serializer<W> {
fn serialize_u8(self, v: u8) -> Result<()> {
self.serialize_u32(v as u32)
}
fn serialize_u32(self, v: u32) -> Result<()> {
self.stream.write_words(&[v]);
Ok(())
}
}
// New
impl<'a, W: WordWrite> serde::ser::Serializer for &'a mut Serializer<W> {
fn serialize_u8(self, v: u8) -> Result<()> {
self.byte_handler.handle(&mut self.stream, v)
}
fn serialize_u32(self, v: u32) -> Result<()> {
self.byte_handler.reset(&mut self.stream)?;
let res = self.stream.write_words(&[v]);
if res.is_err() {
return Err(Error::from(res.unwrap_err()));
} else {
return Ok(res.unwrap());
}
}
}
主要更改是self.byte_handler.handle()
和self.byte_handler.reset()
。
Handle
将一个字节传递给字节处理器,以便这个字节可以在适当的时候与其他字节一起发出一个字。Reset
告诉字节处理器将要序列化除字节之外的内容,缓冲区中的所有内容都必须发出,并且缓冲区需要被清空。
反序列化
同样,代码更改包括对 deserialize_u8
的重定向以及对宏调用 activate_byte_buf_automata_and_take!(self)
和 deactivate_byte_buf_automata!(self)
的插入。
// old
impl<'de, 'a, R: WordRead + 'de> serde::Deserializer<'de> for &'a mut Deserializer<'de, R> {
fn deserialize_u8<V>(self, visitor: V) -> Result<V::Value>
where
V: Visitor<'de>,
{
visitor.visit_u32(self.try_take_word()?)
}
fn deserialize_u128<V>(self, visitor: V) -> Result<V::Value>
where
V: Visitor<'de>,
{
let mut bytes = [0u8; 16];
self.reader.read_padded_bytes(&mut bytes)?;
visitor.visit_u128(u128::from_le_bytes(bytes))
}
}
// new
impl<'de, 'a, R: WordRead + 'de> serde::Deserializer<'de> for &'a mut Deserializer<'de, R> {
fn deserialize_u8<V>(self, visitor: V) -> Result<V::Value>
where
V: Visitor<'de>,
{
visitor.visit_u8(self.byte_handler.handle_byte(&mut self.reader)?)
}
fn deserialize_u128<V>(self, visitor: V) -> Result<V::Value>
where
V: Visitor<'de>,
{
self.byte_handler.reset()?;
let mut bytes = [0u8; 16];
self.reader.read_padded_bytes(&mut bytes)?;
visitor.visit_u128(u128::from_le_bytes(bytes))
}
}
处理一个特殊情况
上述高级计划存在一个限制。由于字节处理器正在保留字节,并且序列化器在序列化结束时不会通知字节处理器,所以存在一种情况,即字节处理器无法将字节输出到单词中,因为序列化已经完成。
这是一个需要特别注意的棘手问题。我们的策略是首先观察到,我们可以将Rust中的所有类型分为三组。
- 原始类型
- bool, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, f32, f64, char, str,
- ()
- 单元结构,即“struct Nothing”
- 单元枚举,即“enum{ A, B, C }”,没有底层变量
- "newtype",这是一种在另一个类型上定义的虚拟伪类型,专门为效率而定义
- Option,可以将其视为
enum { None, Some(T) }
- newtype结构,即
struct(T)
- newtype变体,即
enum { struct1(T1), struct2(T2), ... }
- Option,可以将其视为
- 包装器
- 序列,包括 vec![], 长切片
- 元组,即
(T1, T2)
- 元组结构,即
struct(T1, T2)
- 元组变体,即
enum { struct1(T1, T2), struct2(T3, T4, T5) }
- 映射
- 结构,即
struct { a: A, b: B}
- 结构体变体(variant),也称为
枚举 { struct1 : T1, b:T2, struct2: T3, c: T4, d: T5 }
注意,如果缓冲的字节没有完全写入到流中,这意味着最后一个正在写入的基本类型必须是 bool 或 u8(在下面的操作中,我们将只将 bool 视为 u8)。其后没有其他基本类型,否则它将被写入到流中,因为字节处理程序将被重置。
因此,这个 u8 只有两种可能性。
- 要序列化的变量直接或间接地位于某种包装器内部。通过“间接”,意味着
结构体 { Option<struct(Option<u8>)> }
也会被视为“在包装器内部”。 - 要序列化的变量不在任何包装器内部。它可以是
u8
或Option<struct(Option<u8>)>
。
我们分别处理这两种情况。
对于第一种情况,我们引入了一个“深度”的概念。当序列化器进入包装器时,深度增加1,当它离开包装器时,深度减少1。当深度为零时,这意味着它已经离开了最后一层有意义的包装器,其后不可能有新的字节。当深度达到零时,需要立即将其写入流。实现看起来是这样的
#[inline]
fn decrease_depth<W: WordWrite>(&mut self, stream: &mut W) -> Result<()> {
self.depth -= 1;
if self.depth == 0 && self.status != 0 {
stream.write_words(&[self.byte_holder])?;
self.status = 0;
}
Ok(())
}
对于第二种情况,我们注意到最后一个 u8 在深度 0,因此,这个 u8 被放入缓冲区,并立即写入到流中,即,将 u8 视为 u32。
fn handle<W: WordWrite>(&mut self, stream: &mut W, v: u8) -> Result<()> {
if self.depth == 0 {
stream.write_words(&[v as u32])?;
} else {
......
}
Ok(())
}
结果
在此处可以提供更多信息的集成测试 这里。但在我们的例子中,我们使用一个具有成员 Vec<u8>
和另一个成员 Vec<Vec<u8>>
的结构体。
fn test() {
// ...
test_s.strings = b"Here is a string.".to_vec();
test_s.stringv = vec![b"string a".to_vec(), b"34720471290497230".to_vec()];
// ...
}
我们的实验表明,它可以正确地将它们序列化为 Vec<u32>
中的紧凑格式。
更新
此算法已经多次更改以处理不同的边缘情况。
有必要感谢 @austinabell、@flaub 和 @nategraf,他们的思考过程导致了这个新算法。
对算法感兴趣的读者可以查看待处理的PR:https://github.com/risc0/risc0/pull/1303。
许可证
代码主要来自RISC Zero的实现此处,并进行了必要的修改以添加有限状态自动机。
由于RISC Zero采用Apache 2.0许可证,此仓库也将采用Apache 2.0。
依赖项
约15MB
约224K SLoC