We present <Emphasis FontCategory="NonProportional">DualMatrix</Emphasis>, 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. <Emphasis FontCategory="NonProportional">DualMatrix </Emphasis>excels in its scalability. The prover time of <Emphasis FontCategory="NonProportional">DualMatrix </Emphasis>scales linearly with respect to the number of non-zero elements in the input matrices. For <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$n \times n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> matrix multiplication with N non-zero elements across three input matrices, <Emphasis FontCategory="NonProportional">DualMatrix </Emphasis>employs a structured reference string (SRS) of size O(n), and achieves RAM usage of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(N+n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo>+</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, transcript size of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, prover time of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(N+n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo>+</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, and verifier time of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. The prover time, notably at <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O(N+n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo>+</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and surpassing all existing protocols, includes <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$O(N+n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo>+</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> field multiplications and O(n) exponentiations and pairings within bilinear groups. These efficiencies make <Emphasis FontCategory="NonProportional">DualMatrix </Emphasis>effective for linear algebra on large matrices common in real-world applications. We evaluated <Emphasis FontCategory="NonProportional">DualMatrix </Emphasis>with <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$2^{15} \times 2^{15}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mn>15</mn> </msup> <mo>×</mo> <msup> <mn>2</mn> <mn>15</mn> </msup> </mrow> </math></EquationSource> </InlineEquation> input matrices each containing 1G non-zero integers, which necessitate 32T integer multiplications in naive matrix multiplication. <Emphasis FontCategory="NonProportional">DualMatrix </Emphasis>recorded prover and verifier times of 150.84s and 0.56s, respectively. When applied to <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$1M \times 1M$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mi>M</mi> <mo>×</mo> <mn>1</mn> <mi>M</mi> </mrow> </math></EquationSource> </InlineEquation> sparse matrices each containing 1G 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, <Emphasis FontCategory="NonProportional">DualMatrix </Emphasis>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.

Dualmatrix: conquering zkSNARK for large matrix multiplication

期刊论文
出版模式：

开放获取
发表日期：

2026年2月22日

查看全文

Mingshu Cong,
Tsz Hon Yuen,
Siu Ming Yiu

摘要

We present DualMatrix, 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. DualMatrix excels in its scalability. The prover time of DualMatrix scales linearly with respect to the number of non-zero elements in the input matrices. For $n \times n$ $n \times n$ matrix multiplication with N non-zero elements across three input matrices, DualMatrix employs a structured reference string (SRS) of size O(n), and achieves RAM usage of $O(N+n)$ $O (N + n)$ , transcript size of $O(\log n)$ $O (log n)$ , prover time of $O(N+n)$ $O (N + n)$ , and verifier time of $O(\log n)$ $O (log n)$ . The prover time, notably at $O(N+n)$ $O (N + n)$ and surpassing all existing protocols, includes $O(N+n)$ $O (N + n)$ field multiplications and O(n) exponentiations and pairings within bilinear groups. These efficiencies make DualMatrix effective for linear algebra on large matrices common in real-world applications. We evaluated DualMatrix with $2^{15} \times 2^{15}$ $2^{15} \times 2^{15}$ input matrices each containing 1G non-zero integers, which necessitate 32T integer multiplications in naive matrix multiplication. DualMatrix recorded prover and verifier times of 150.84s and 0.56s, respectively. When applied to $1M \times 1M$ $1 M \times 1 M$ sparse matrices each containing 1G 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, DualMatrix 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.