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 n n × n 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) O (N + n), transcript size of O (n) O (log n), prover time of O (N+n) O (N + n), and verifier time of O (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 effective for linear algebra on large matrices common in real-world applications. We evaluated with 2^15 2^15 2 15 × 2 15 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 1M 1 M × 1 M 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.
Cong et al. (Sun,) studied this question.