Dualmatrix: conquering zkSNARK for large matrix multiplication

Abstract We present , a zkSNARK solution for large-scale matrix multiplication. Classical zkSNARK protocols typically underperform in data analytic contexts, hampered by the large size of datasets and the superlinear nature of matrix multiplication. excels in its scalability. The prover time of scales linearly with respect to the number of non-zero elements in the input matrices. For $$n \times n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> matrix multiplication with N non-zero elements across three input matrices, employs a structured reference string (SRS) of size O ( n ), and achieves RAM usage of $$O(N+n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , transcript size of $$O(\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , prover time of $$O(N+n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , and verifier time of $$O(\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . The prover time, notably at $$O(N+n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and surpassing all existing protocols, includes $$O(N+n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> field multiplications and O ( n ) exponentiations and pairings within bilinear groups. These efficiencies make effective for linear algebra on large matrices common in real-world applications. We evaluated with $$2^{15} \times 2^{15}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>15</mml:mn> </mml:msup> <mml:mo>×</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>15</mml:mn> </mml:msup> </mml:mrow> </mml:math> input matrices each containing 1 G non-zero integers, which necessitate 32 T integer multiplications in naive matrix multiplication. recorded prover and verifier times of 150.84s and 0.56s, respectively. When applied to $$1M \times 1M$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mi>M</mml:mi> <mml:mo>×</mml:mo> <mml:mn>1</mml:mn> <mml:mi>M</mml:mi> </mml:mrow> </mml:math> sparse matrices each containing 1 G non-zero integers, it demonstrated prover and verifier times of 1, 384.45s and 0.67s. Our approach outperforms current zkSNARK solutions by successfully handling the large matrix multiplication task in experiment. We extend matrix operations from field matrices to group matrices, formalizing group matrix algebra. This mathematical advancement brings notable symmetries beneficial for high-dimensional elliptic curve cryptography. By leveraging the bilinear properties of our group matrix algebra in the context of the two-tier commitment scheme, achieves efficiency gains over previous matrix multiplication arguments. To accomplish this, we extend and enhance Bulletproofs to construct an inner product argument featuring a transparent setup and logarithmic verifier time.