Cycle#2 - Pinocchio (PHGR13) / Groth16

Pinocchio (PHGR13) and Groth16

Note

• SNARG vs SNARK

  • SNARG - Succinct Non-interactive ARGument
    • At least computational soundness, which means verifier is highly unlikely to accept a proof if the corresponding statement
      $\varphi$ is not in the relation
      $R$
  • SNARK - Succinct Non-interactive ARgument of Knowledge
    • At least computational knowledge soundness, which means verifier is highly unlikely to accept a proof if the corresponding statement and witness
      $(\varphi ,w)$ is not in the relation
      $R$
    • Given access to the same information as an adversary who generates a proof, the extractor is able to "extract" the associated witness information
      $w$.
  • In Gro16 P.8

    SNARGs and SNARKs. A non-interactive argument where the verifier runs in poly- nomial time in λ + |φ| and the proof size is polynomial in λ is called a preprocessing succinct non-interactive argument (SNARG) if it sound, and a preprocessing succinct argument of knowledge (SNARK) if it is knowledge sound.

• 2 field elements NILPs (Non-Interactive Linear Proofs)

  • Since Gro16 use 3 field elements as a NILP, it is natural to ask whether the number of field elements the prover sends in the NILP can be reduced further.
  • By using only squaring gates in arithmetic circuit, then we will get
    $u_i(x)=v_i(x)$. So it is possible to make 2 field elements NILPs.
  • In Gro16 P.16

    2 field element NILPs. It is natural to ask whether the number of field elements the prover sends in the NILP can be reduced further. The square span programs of Danezis et al. [DFGK14] give rise to 2 field element NILPs for boolean circuit satisfiability. It is also possible to get a 2-element NILP for arithmetic circuit satisfiability by rewriting the circuit into one that only uses squaring gates, since each multiplication gate

    $a·b=c$ can be rewritten as a

    $(a+b{)}^2-(a-b{)}^2=4c$. When an arithmetic circuit only has squaring gates we get

    $u_i(x)=v_i(x)$ for all

    $i$. By choosing

    $r=s$ in the NILP, we now have that

    $B=A+\beta -\alpha$, so the prover only needs to send two elements

    $A$ and

    $C$ to make a convincing proof. Rewriting the arithmetic circuit to only use squaring gates may double the number of gates and also requires some additional wires for the subtraction of the squares, so the reduction of the size of the NILP comes at a significant computational cost though.

• Vanishing Polynomial

  When converting R1CS to QAP, we can choose vanishing polynomial

  $Z(x)$ to be
  $Z(x)=x^d-1$, where
  $d$ is
  $2^m$ (next power of 2 larger than wire count).

Question

• Gro16
  • Why is asymmetric bilinear groups higher efficiency than symmetric one?

    We prefer to work with asymmetric bilinear groups for their higher efficiency than symmetric bilinear groups. [Gro16 P.5]

Reference

• zk-SNARKs: A High-Level Primer by clearmatics. It metions the difference between SANRG and SNARK
• Pinocchio (PGHR13)
  • Pinocchio: Nearly Practical Verifiable Computation
  • What are zk-SNARKs? by ZCash
  • Series by ECC
    • Explaining SNARKs Part I: Homomorphic Hidings
    • Explaining SNARKs Part II: Blind Evaluation of Polynomials
    • Explaining SNARKs Part III: The Knowledge of Coefficient Test and Assumption
    • Explaining SNARKs Part IV: How to make Blind Evaluation of Polynomials Verifiable
    • Explaining SNARKs Part V: From Computations to Polynomials
    • Explaining SNARKs Part VI: The Pinocchio Protocol
    • Explaining SNARKs Part VII: Pairings of Elliptic Curves
  • Series by Vitalik Buterin
    • Quadratic Arithmetic Programs: from Zero to Hero
    • Exploring Elliptic Curve Pairings
    • Zk-SNARKs: Under the Hood
  • On the security of the BCTV Pinocchio zk-SNARK variant
  • Demystifying the Role of zk-SNARKs in Zcash
  • zk-SNARK explained: Basic Principles
  • PGHR13 in a nutshell from BCTV14 P.25
    
• Groth16
  • On the Size of Pairing-based Non-interactive Arguments
  • How to Generate a Groth16 Proof for Forgery
  • Perpetual Powers of Tau
  • Security Considerations of zk-SNARK Parameter Multi-Party Computation
    
• Others
  • How gnark calculate QAP coefficients of A, B, C