双矩阵

此文件夹包含我们论文《双矩阵：征服大矩阵乘法的zk-SNARK》的代码。

简介

给定一个配对 $e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{G}_T$，以及两个向量 $\hat{\mathbf{G}} \in \mathbb{G}_1^{q-1}$ 和 $\hat{\mathbf{H}} \in \mathbb{G}_2^{q-1}$，

则对于 $m \times n$ （$m,n \le q-1$）矩阵

$\mathbf{a} = \lbrace a_{ij} \rbrace \in \mathbb{Z}_p^{m\times n}$ 的双层承诺 $C_a \in \mathbb{G}_T$ 定义如下

$$ \langle \hat{\mathbf{G}} | \mathbf{a} | \hat{\mathbf{H}} \rangle : = \bigoplus_{i=1}^m \bigoplus_{j=1}^n a_{ij} e(G_i, H_j). $$

假设验证者已经对三个矩阵 $\mathbf{a}$、$\mathbf{b}$ 和 $\mathbf{c}$ 做出了如下承诺

$$ C_a = \langle \hat{\mathbf{G}} | \mathbf{a} | \hat{\mathbf{H}} \rangle \in \mathbb{G}_T, $$

$$ C_b = \langle \hat{\mathbf{G}} | \mathbf{b} | \hat{\mathbf{H}} \rangle \in \mathbb{G}_T, $$

$$ C_c = \langle \hat{\mathbf{G}} | \mathbf{c} | \hat{\mathbf{H}} \rangle \in \mathbb{G}_T . $$

然后，验证者可以为以下关系生成一个零知识证明，需要进行 $O(m+n+l)$ 组群运算

$$ \mathcal{R} = \lbrace C_c \in \mathbb{G}_T, C_a \in \mathbb{G}_T, C_b \in \mathbb{G}_T; \hat{\mathbf{G}} \in \mathbb{G}_1^{q-1} , \hat{\mathbf{H}} \in \mathbb{G}_2^{q-1} $$

$$ : \mathbf{a} \in \mathbb{Z}_p^{m\times l}, \mathbf{b} \in \mathbb{Z}_p^{l \times n}, \mathbf{c} \in \mathbb{Z}_p^{m \times n} $$

$$ | \mathbf{c} = \mathbf{a} \mathbf{b} \wedge C_c = \langle \hat{\mathbf{G}} | \mathbf{c} | \hat{\mathbf{H}} \rangle \wedge C_a = \langle \hat{\mathbf{G}} | \mathbf{a} | \hat{\mathbf{H}} \rangle \wedge C_b = \langle \hat{\mathbf{G}} | \mathbf{b} | \hat{\mathbf{H}} \rangle
\rbrace. $$

我们采用了随机预言机方法。

更多详情请参阅我们论文中的数学部分。

运行代码

要运行DualMatrix论文中的实验，请运行以下命令

cd /path/to/zkmatrix
cargo bench

兼容性说明

• Rust 工具链 3.10.12
• 环境： Ubuntu 22.04

目录内容

• util/ 用于 Fiat-Shamir 变换、矩阵投影和内积的实用函数。
• protocols/ 矩阵乘法协议及其子协议。
• zkprotocols/ 零知识矩阵乘法协议及其子协议。

子协议

DualMatrix 包含四个子协议

• 标量投影论证
• 左投影论证
• 右投影论证
• 在 $\mathbb{G}_T$ 中的内积论证

例如，标量投影论证用于以下关系

$$ \mathcal{R} = \lbrace C_c \in \mathbb{G}_T, C_a \in \mathbb{G}_T, \vec{\mathbf{l}} \in \mathbb{Z}_p^{m}, \vec{\mathbf{r}} \in \mathbb{Z}_p^{n}; \hat{G}_0 \in \mathbb{G}_1, \hat{H}_0 \in \mathbb{G}_2, \hat{\mathbf{G}} \in \mathbb{G}_1^{q-1} , \hat{\mathbf{H}} \in \mathbb{G}_2^{q-1} $$

$$ : \mathbf{a} \in \mathbb{Z}_p^{m \times n} $$

$$ | C_c = \langle \hat{G}_0 | \vec{\mathbf{l}}^T\mathbf{a} \vec{\mathbf{r}} | \hat{H}_0 \rangle \wedge C_a = \langle \hat{\mathbf{G}} | \mathbf{a} | \hat{\mathbf{H}} \rangle \rbrace. $$

此子协议的伪代码如下

引用

如果我们的工作对您的研究有所帮助，请按照以下方式引用我们的论文

匿名