previous posts: 1,2, and 3
Overview of spartan paper
summarize again what spartan paper offer:
- transparent zksnark for arbitrarily NP statement
- sub-linear verification
- time optimal prover
sub-linear verification,computation commitment for sparse multilinear polynomials
recall in post 3, the remaining problems:
- use extractable polynomial commitment for multiliear polynomial \(\widetilde{Z}(r_y)\) to avoid \(O(|w|)\) communications
- other terms can be computed locally by verifier, namely, \(\widetilde{A},\widetilde{B},\widetilde{C}\) it is circuit information. section 6 of the paper discusses how to make the computation sublinear
sub-linear verification is achieved by a public preprocessing step, in this pre-processing step, verifier basically need to evaluated the metrics \(\widetilde{A},\widetilde{B},\widetilde{C}\), but this evaluation can also be verifiably delegated to the prover, using the computation commitment. these computation commitments are commitments for sparse multilinear polynomials.
Spark
- compiler to transform extractable polynomial commitment scheme for multilinear polynomials to one for sparse multilinear polynomials.
- consists of:
- extractable polynomial commitment scheme as black box
- special-purpose zkSNARK???
- circuit that employs offline memory checking
goal=> to efficiently prove evaluations of sparse multilinear polynomials.
SPARK–transferring dense multilinear poly commitments to sparse multilinear poly commitments.
Describe SPARK that applies to \(2 \log m\) variate sparse polynomials \(\widetilde{A},\widetilde{B},\widetilde{C}\)
we want to compute \(\widetilde{M}_{r_x}(r_y)\), re-write it to
\(\widetilde{M}_{r_x}(r_y)=\sum\limits_{(i,j)\in(\{0,1\}^s,\{0,1\}^s)::M(i,j) \neq 0}M(i,j)\cdot \widetilde{eq}(i,r_x)\cdot \widetilde{eq}(j,r_y)\)