DualMatrix

This folder contains codes for our paper DualMatrix: Conquering zk-SNARK for Large Matrix Multiplication.

Introduction

Given a pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{G}_T$, and two vectors $\hat{\mathbf{G}} \in \mathbb{G}_1^{q-1}$ and $\hat{\mathbf{H}} \in \mathbb{G}_2^{q-1}$,

then the two-tier commitment $C_a \in \mathbb{G}_T$ for a $m \times n$ ( $m,n \le q-1$ ) matrix

$\mathbf{a} = \lbrace a_{ij} \rbrace \in \mathbb{Z}_p^{m\times n}$ is defined by:

$$ \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). $$

Suppose the prover has made commitments to three matrices $\mathbf{a}$, $\mathbf{b}$, and $\mathbf{c}$ as follows:

$$ 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 . $$

Then, the prover can generate a zero-knowledge proof with $O(m+n+l)$ group operations for the relation:

$$ \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. $$

We employ the random oracle approach.

For more details, refer to the math in our paper.

Running the Code

To run the experiment in the DualMatrix paper, run the following command:

cd /path/to/zkmatrix
cargo bench

Compatibility Note

• Rust Toolchain: 3.10.12

• Environment: Ubuntu 22.04

Directory Contents

• util/ Utility functions for Fiat-Shamir transformation, matrix projections, and inner products.

• protocols/ The MatMul protocol and its sub-protocols.

• zkprotocols/ The zero-knowledge MatMul protocol and its sub-protocols.

Subprotocols

DualMatrix contains four subprotocols:

• Scalar projection argument
• Left projection argument
• Right projection argument
• Inner product argument in $\mathbb{G}_T$

The scalar projection argument, for example, is for the following relation:

$$ \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. $$

The pseudo-code for this subprotocol is as follows:

Citing

If our work benefits to your research, please cite our paper as follows:

Anonymous