# zkmatrix 0.1.1

zk-SNAKR for linear algebra
docs.rs failed to build zkmatrix-0.1.1
See Builds for ideas on how to fix a failed build, or Metadata for how to configure docs.rs builds.
If you believe this is docs.rs' fault, open an issue.
Visit the last successful build: zkmatrix-0.1.0

# 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