Multi-Party Proof Generation in QAP-Based zk-SNARKs

Ali Rahimi, Mohammad Ali Maddah-AliIEEE J. Sel. Areas Inf. Theory 2021 · DOI

TL;DR

This paper tackles the challenge of computationally intensive zk-SNARK proof generation by proposing a secure multi-party computation (MPC) scheme. It allows a prover to delegate proof generation to untrusted servers, significantly reducing the prover's computational load while ensuring that even colluding servers cannot learn the secret inputs.

What Problem Does This Paper Address?

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are powerful cryptographic tools for proving knowledge of a secret without revealing it. While efficient for verifiers, zk-SNARKs, particularly those based on Quadratic Arithmetic Programs (QAPs), impose a heavy computational burden on the prover. This can be prohibitive for provers with limited resources, necessitating offloading the computation. Existing solutions either require trusted servers or impose the same computational load on each server as the original task. This paper addresses the need for a solution that allows delegation to untrusted servers with a reduced computational load per server, while maintaining security against collusion.

Methods

The paper proposes a secure multi-party proof generation scheme that leverages ideas from multi-party computation. The core innovation lies in delegating the prover's task to $N$ semi-honest servers, where a subset of up to $T$ servers can collude. The scheme achieves two key properties:

  1. Reduced Server Load: The computation load per server is a fraction of the prover's primary computation, specifically less than $1/(N-T)$ of the original load.
  2. Untrusted Servers: The servers are not required to be trusted, and collusion among up to $T$ servers does not compromise the secret inputs.

The scheme involves a multiparty algorithm for computing Fast Fourier Transforms (FFTs) and their inverses, which are crucial components of the zk-SNARK prover's computation. This multiparty FFT computation is designed to distribute the workload efficiently among the servers. The paper also details the main zk-SNARK prover algorithm, adapted for this multi-party setting.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Decoupling Prover Load and Server Trust: The paper successfully decouples the need for trusted servers from the goal of reducing the prover's computational load. This is a significant advancement over prior work.
  • Efficient Multiparty FFT: The development of a multiparty algorithm for computing FFTs and their inverses is a key technical contribution, enabling the efficient distribution of the prover's computation.
  • Security Against Collusion: The scheme's ability to withstand collusion among a significant fraction of servers ($T$ out of $N$) while preserving privacy is a crucial security feature.
  • Practical Implications: By reducing the prover's computational burden, this work makes zk-SNARKs more accessible and practical for a wider range of applications and users with limited computational resources.

Key Results

The paper presents a scheme where a prover can delegate its zk-SNARK proof generation task to $N$ semi-honest servers. The key results are:

  • Computational Load Reduction: The computation complexity for each server is reduced to $O(\log(n/K))$ (where $n$ is the size of the arithmetic circuit and $K$ is a parameter related to partitioning), and the prover's complexity is $O(Kn)$. This is a significant reduction compared to the original $O(n \log n)$ complexity.
  • Privacy Guarantee: The scheme ensures that even if up to $T$ servers collude, they cannot gain any information about the secret inputs. This is formally proven using information-theoretic arguments.
  • Correctness: The proposed algorithms for multiparty FFT computation and the overall proof generation are proven to be correct.

Limitations and Future Work

  • Semi-Honest Servers: The current scheme assumes semi-honest servers, meaning they follow the protocol but may try to learn secret information. Future work could explore extending this to fully adversarial servers.
  • Trusted Setup: Like most zk-SNARK systems, this work relies on a trusted setup phase to generate public parameters. While not directly addressed in this paper, future research could explore decentralized or MPC-based trusted setup mechanisms.
  • Specific zk-SNARK Variant: The paper focuses on QAP-based zk-SNARKs, specifically Groth's variant. While the approach is generalizable, further work might be needed to adapt it to other zk-SNARK constructions.

Summary updated

BibTeX
@article{rahimi2021multi,
  author = {Ali Rahimi and Mohammad Ali Maddah-Ali},
  title = {{Multi-Party Proof Generation in QAP-Based zk-SNARKs}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2021},
  doi = {10.1109/jsait.2021.3102267},
}
Figure