Spartan 4

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:

  1. use extractable polynomial commitment for multiliear polynomial \(\widetilde{Z}(r_y)\) to avoid \(O(|w|)\) communications
  2. 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:
  1. extractable polynomial commitment scheme as black box
  2. special-purpose zkSNARK???
  3. 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)\)

observation:

  1. the equation above transforming computing a multilinear polynomial extension of a matrix to the multiplication of two multilinear extension of equal function. Notice on the right side, no tilde on top of \(M\), it is just a matrix, not an extension.
  2. \(r_x\) and \(r_y\) belong to \(\mathbb{F}^s\), which means they are vectors! the multilinear extension of \(\widetilde{eq}(i,r_x)\) and \(\widetilde{eq}(j,r_y)\) should have at least \(s+1\) variables.

now the question come to have to efficiently compute \(\widetilde{M}_{r_x}(r_y)\), namely \(\widetilde{M}(r_x,r_y)\)

recall the parameter related to the “sparse”: there are at most \(n\) non-zero entries in each matrix.

for \(\widetilde{eq}(i,r_x)\) and \( \widetilde{eq}(j,r_y)\), they can be computed in \(O(m)\) time, how? (need to expand the computing process to see things clearly) but let’s focus on the most important part now,

to make the computation process more clear:

\(\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)\)

\(=\sum\limits_{(i,j)\in(\{0,1\}^s,\{0,1\}^s)::M(i,j) \neq 0}M(i,j)\cdot \prod\limits_{k=1}^s(i_k\cdot r_{x_k}+(1-i_k)(1-r_{x_k})) \)

\(\cdot \prod\limits_{k=1}^s(i_k\cdot r_{y_k}+(1-i_k)(1-r_{y_k}))\)

observation:

computing the sum requires n random accesses into two tables each with m entries. theses operations can be consider as RAM operations.

use Offline Memory Checking techniques:

An \(O(n)\)-sized circuit for evaluating \(\widetilde{M}\)

Goal: a circuit to evaluate \(\widetilde{M}\)

Encoding sparse polynomials

A sparse polynomial \(\widetilde{M}\) can be represented by \(n\) tuples of the form \((i,j,M(i,j))\) is encoded by three vector:

\(row(k)=i, col(k)=j,val(k)=M(i,j)\) where \(k\in [0,n-1]\)

additional metadata to accelerate the memory checking:

six vectors:

  1. \(read-ts_{row} \in \mathbb{F}^n\)
  2. \(write-ts_{row} \in \mathbb{F}^n\)
  3. \(audit-ts_{row} \in \mathbb{F}^n\)
  4. \(read-ts_{col} \in \mathbb{F}^n\)
  5. \(write-ts_{col} \in \mathbb{F}^n\)
  6. \(audit-ts_{col} \in \mathbb{F}^n\)

computing the above vectors needs: memory size, sequence of addresses at which the memory is accessed.

Leave a Reply

Your email address will not be published. Required fields are marked *