1. 引言

Groth 2009年论文《Linear Algebra with Sub-linear Zero-Knowledge Arguments》。

已知2个matrices $\mathbf{A},\mathbf{B}$ 的commitments $C_{\mathbf{A}},C_{\mathbf{B}}$ 和 1个matrix $\mathbf{C}$ 的commitment $C_{\mathbf{C}}$ ，本文构建了：

sub-linear size的零知识证明，用于证明 product of two matrices $\mathbf{C}=\mathbf{A}*\mathbf{B}$ 。
sub-linear size的零知识证明，用于证明 Hadamard product of two matrices $\mathbf{C}=\mathbf{A}\odot \mathbf{B}$ 。

基于以上两种证明方案，可以构建其它sub-linear 零知识证明，用于证明，如：（用于证明 a set of committed vectors and matrices satisfying a set of linear algebra relations。）

a committed matrix being upper or lower triangular；
a committed matrix being the inverse of another committed matrix；
a committed matrix being a permutation of another committed matrix （using either a public or a hidden permutation）；
a committed field element being the dot product of two committed vectors；
a committed matrix being the product of two other committed matrices；
a committed vector being the Hadamard product (the entry-wise product) of two other vectors；
a committed matrix has a particular trace；
compute the sums of the rows or columns of a committed matrix；

同时，可将本文技术用于证明 the satisfiability of an arithmetic circuit with $N$ gates，本文所构建的arithmetic circuit 零知识证明算法具有的communication complexity 为 $O(\sqrt{N})$ 个group elements。本文提供了2种实现方式：

1）constant round 的零知识证明算法；
2） $O(\log_2 N)$ round 的零知识证明算法，Prover的computation complexity 为 $O(N/{\log_2 N})$ 个exponentiations，Verifier的computation complexity为 $O(N)$ 个multiplications。

对于只有与非门的binary circuit来说，本文基于Pedersen commitment的变体，提供了一种circuit satisfiability的public-coin 零知识证明算法：

communication complexity为 $O(\sqrt{N})$ 个group elements；
Prover和Verifier的computation complexity 均为 $O(N)$ 个multiplications。

在构建零知识证明算法时，需要同时关注communication complexity和computation complexity。本文所构建的零知识证明算法，具有sub-linear communication的同时，也具有 low computational complexity。

对于 $n\times n$ 矩阵 $\mathbf{A}$ ，以行向量表示为 $\mathbf{A}=[\vec{a}_1,\cdots,\vec{a}_n]^T$ ，对每个行向量进行Pedersen commitment为 a single group element。 $Com(\mathbf{A})=[Com(\vec{a}_1),\cdots,Com(\vec{a}_n)]^T$ 。