内存一致性检查：Multiset Hashing

felicityin
发布于 9小时前
阅读 51

在zkVM中，内存访问一致性检查是证明任何读操作返回的值确实是写入该内存地址的最新值。如果能证明读取和写入的数据是置换关系，便可证明内存访问的一致性。内存一致性检查构造读集合RRR和写集合WWW，元素都是(addr,val,cnt)(addr,val,cnt)(addr,val,

在 zkVM 中，内存访问一致性检查是证明任何读操作返回的值确实是写入该内存地址的最新值。如果能证明读取和写入的数据是置换关系，便可证明内存访问的一致性。

# 内存一致性检查

构造读集合 $R$ 和写集合 $W$，元素都是 $(addr, val, cnt)$，分别表示地址、值和计数器。

- Write(addr, val)
  1. 读取地址 addr 处的旧值及其计数器 cnt，$R=R \cup \{(addr, val_{pre}, cnt)\}$
  2. 将新值 val 和计数器 cnt+1 写入地址 addr，$W=W \cup \{(addr, val_{cur},cnt+1)\}$

- Read(addr)
  1. 读取地址 addr 处的旧值 val 及其计数器 cnt，$R=R \cup \{(addr, val_{pre}, cnt\}$
  2. 在地址 addr 处写入 val 和计数器 cnt+1，$W=W \cup \{(addr, val_{pre}, cnt+1\}$

如果最终 $W=R \cup Final$，便可证明内存访问的一致性，其中 $Final$ 表示对于所有地址 $addr_i$，写集合 $W$ 中该地址的最新元素 $(addr_i, val_i, cnt_i)$

LogUp 方式：
$$
\sum_{(a,v,t)\in W}\frac{1}{f(a,v,t)-\tau}=\sum_{(a,v,t) \in R}\frac{1}{f(a,v,t)-\tau} + \sum_{(a,v,t) \in Final}\frac{1}{f(a,v,t)-\tau}
$$
Multiset Hashing 方式：
$$
\sum_{(a,v,t)\in W}Enc(f(a,v,t))=\sum_{(a,v,t) \in R}Enc(f(a,v,t)) + \sum_{(a,v,t) \in Final}Enc(f(a,v,t))
$$
前者需要先运行一遍程序以计算挑战值 $\tau$；后者的约束更复杂，因为涉及到椭圆曲线群上的计算以及对哈希过程的约束，比如 Poseidon2

# Multiset Hashing

Multiset hashing 由 Clarke, Devadas, van Dijk, Gassend and Suh [CDvD+ 03] (building on Bellare and Micciancio [BM97]) 引入，可以将一个大的集合哈希到一个短字符串上，并且很难找到两个不同的集合可以映射到同一个值上。该哈希方式是增量的，即一次只哈希一个元素，并且与元素被哈希的顺序无关。这样，就可以比较两个以不同顺序生成元素的集合。

相对于 LogUp，multiset hashing 允许直接更新哈希值，而不需要先运行一遍程序以计算挑战值。

## 定义

一个 multset hash，对于一个域 $U$，一个压缩函数族 $H = \left\{h_k: P(U) \rightarrow \left\{0,1\right\}^{\lambda}\right\}_{k \in \left\{0,1\right\}^*}$，其中 $\lambda$ 表示安全参数，算法如下：

1. 空集合：给定 $k$，返回 $h_k(\emptyset)$
2. 增量：给定 $k, \space h(S)$，其中 $S ⊆ U$，并且 $u ∈ U$，返回 $h(S ∪ \left\{u\right\})$

在多项式时间内找到两个不同的集合拥有相同的哈希值的概率是非常小的。

## 基于 Hash-to-Group 的构建

$(G, +)$ 是循环群，$\left\{f_k: U \rightarrow G\right\}_k$ 是一个函数集合。multiset hash 函数定义如下：
$$
h_k(S)=\sum_{s \in S}f_k(s)
$$
可以看到，空集合和增量功能是比较容易实现的。空集合就是群的幺元 $0_G$，添加一个元素 $x$ 到 multiset $S$ 就是计算 $h(S)+h(x)$

以上构建方式是 multiset 抗碰撞的，因为 $G$ 上的离散对数难问题，以及 $f_k: U \rightarrow G$ 建模为一个随机函数。

### 基于椭圆曲线的构建

群 $G$ 是椭圆曲线 $y^2=x^3+Ax+B$ 上的点 $(x,y)$ 的集合（以及位于无穷远处的特殊点），$A,B \in \text{F}$，$\text{F}$ 是一个大的域。哈希函数使用 BabyBear 域上的 Poseidon2。为了将一个元素哈希到椭圆曲线上，先用 Poseidon2 计算点的 $x$ 坐标，该 $x$ 坐标可能不是椭圆曲线上的有效值，还需要加一个 8-bit 调整值，该值也会被哈希在内。另外，需要通过范围检查来约束 $y$ 坐标不能被反转。

# 椭圆曲线参数

对椭圆曲线 $y^2=x^3+Ax+B$ 的要求：

- 阶 $r$ 为素数
- 高 embedding degree. If the elliptic curve has size $r$, it is important that the embedding degree $e$, the minimum positive integer such that $p^e ≡1 (\text{mod} \space r)$ is large, to avoid MOV-type attacks.
- CM Discriminant of the curve is sufficiently large, at least 200 bits.
- 点加和二倍运算尽可能简洁（可以让A，B 绝对值较小）。

寻找椭圆曲线的方法在这里：[Memory Consistency Checking](https://docs.zkm.io/design/memory-checking.html#memory-consistency-checking)

## BabyBear

对于 BabyBear 域 $\text{F}_p$，其中 $p=15 * 2^{27}+1$，选择**不可约**的 7 次扩域 $\text{F}_{p^7} = \text{F}_{p^7}/(z^7-2z-5)$ 和椭圆曲线 
$$
y^2=x^3+2x+26z^5
$$
该椭圆曲线有素数阶 $r = 134062710381075636479997415343722979822569397998875702343109881667$

用 SageMath 验证 $\text{F}_{p^7} = \text{F}_{p^7}/(z^7-2z-5)$ 在 $p=15 * 2^{27}+1$ 上不可约：

```
sage: p = 2013265921
....: R.<z> = GF(p)[]
....: f = z^7 - 2*z - 5
....: f.is_irreducible()
True
```

## KoalaBear

对于 KoalaBear 域 $\text{F}_p$，其中 $p=127 * 2^{24} + 1$，选择**不可约**的 7 次扩域 $\text{F}_{p^7} = \text{F}_{p^7}/(z^7+2z-8)$ 和椭圆曲线 
$$
y^2=x^3+3zx-3
$$

该椭圆曲线有素数阶 $r=199372529839252601278447397890875723011140055175072723225727394951$

#  参考

SP1 V4 Turbo: Memory Argument via Elliptic Curve based Multiset Hashing

[Memory Consistency Checking](https://docs.zkm.io/design/memory-checking.html#memory-consistency-checking)

[A guide to zkVM memory checking protocols](https://olegfomenko.dev/2025/09/15/memory.html)

内存一致性检查

构造读集合 $R$ 和写集合 $W$，元素都是 $(addr, val, cnt)$，分别表示地址、值和计数器。

Write(addr, val)
1. 读取地址 addr 处的旧值及其计数器 cnt，$R=R \cup {(addr, val_{pre}, cnt)}$
2. 将新值 val 和计数器 cnt+1 写入地址 addr，$W=W \cup {(addr, val_{cur},cnt+1)}$
Read(addr)
1. 读取地址 addr 处的旧值 val 及其计数器 cnt，$R=R \cup {(addr, val_{pre}, cnt}$
2. 在地址 addr 处写入 val 和计数器 cnt+1，$W=W \cup {(addr, val_{pre}, cnt+1}$

如果最终 $W=R \cup Final$，便可证明内存访问的一致性，其中 $Final$ 表示对于所有地址 $addr_i$，写集合 $W$ 中该地址的最新元素 $(addr_i, val_i, cnt_i)$

LogUp 方式： $$ \sum{(a,v,t)\in W}\frac{1}{f(a,v,t)-\tau}=\sum{(a,v,t) \in R}\frac{1}{f(a,v,t)-\tau} + \sum{(a,v,t) \in Final}\frac{1}{f(a,v,t)-\tau} $$ Multiset Hashing 方式： $$ \sum{(a,v,t)\in W}Enc(f(a,v,t))=\sum{(a,v,t) \in R}Enc(f(a,v,t)) + \sum{(a,v,t) \in Final}Enc(f(a,v,t)) $$ 前者需要先运行一遍程序以计算挑战值 $\tau$；后者的约束更复杂，因为涉及到椭圆曲线群上的计算以及对哈希过程的约束，比如 Poseidon2

Multiset Hashing

相对于 LogUp，multiset hashing 允许直接更新哈希值，而不需要先运行一遍程序以计算挑战值。

定义

一个 multset hash，对于一个域 $U$，一个压缩函数族 $H = \left{hk: P(U) \rightarrow \left{0,1\right}^{\lambda}\right}{k \in \left{0,1\right}^*}$，其中 $\lambda$ 表示安全参数，算法如下：

空集合：给定 $k$，返回 $h_k(\emptyset)$
增量：给定 $k, \space h(S)$，其中 $S ⊆ U$，并且 $u ∈ U$，返回 $h(S ∪ \left{u\right})$

在多项式时间内找到两个不同的集合拥有相同的哈希值的概率是非常小的。

基于 Hash-to-Group 的构建

$(G, +)$ 是循环群，$\left{f_k: U \rightarrow G\right}_k$ 是一个函数集合。multiset hash 函数定义如下： $$ hk(S)=\sum{s \in S}f_k(s) $$ 可以看到，空集合和增量功能是比较容易实现的。空集合就是群的幺元 $0_G$，添加一个元素 $x$ 到 multiset $S$ 就是计算 $h(S)+h(x)$

以上构建方式是 multiset 抗碰撞的，因为 $G$ 上的离散对数难问题，以及 $f_k: U \rightarrow G$ 建模为一个随机函数。

基于椭圆曲线的构建

椭圆曲线参数

对椭圆曲线 $y^2=x^3+Ax+B$ 的要求：

阶 $r$ 为素数
高 embedding degree. If the elliptic curve has size $r$, it is important that the embedding degree $e$, the minimum positive integer such that $p^e ≡1 (\text{mod} \space r)$ is large, to avoid MOV-type attacks.
CM Discriminant of the curve is sufficiently large, at least 200 bits.
点加和二倍运算尽可能简洁（可以让A，B 绝对值较小）。

寻找椭圆曲线的方法在这里：Memory Consistency Checking

BabyBear

对于 BabyBear 域 $\text{F}p$，其中 $p=15 * 2^{27}+1$，选择不可约的 7 次扩域 $\text{F}{p^7} = \text{F}_{p^7}/(z^7-2z-5)$ 和椭圆曲线 $$ y^2=x^3+2x+26z^5 $$ 该椭圆曲线有素数阶 $r = 134062710381075636479997415343722979822569397998875702343109881667$

用 SageMath 验证 $\text{F}{p^7} = \text{F}{p^7}/(z^7-2z-5)$ 在 $p=15 * 2^{27}+1$ 上不可约：

sage: p = 2013265921
....: R.&lt;z> = GF(p)[]
....: f = z^7 - 2*z - 5
....: f.is_irreducible()
True

KoalaBear

对于 KoalaBear 域 $\text{F}p$，其中 $p=127 * 2^{24} + 1$，选择不可约的 7 次扩域 $\text{F}{p^7} = \text{F}_{p^7}/(z^7+2z-8)$ 和椭圆曲线 $$ y^2=x^3+3zx-3 $$

该椭圆曲线有素数阶 $r=199372529839252601278447397890875723011140055175072723225727394951$

参考

SP1 V4 Turbo: Memory Argument via Elliptic Curve based Multiset Hashing

Memory Consistency Checking

A guide to zkVM memory checking protocols

原创
学分: 2
分类: 零知识证明
标签: zkVM

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。