1
$\begingroup$

Many zkSNARKS (for e.g. Groth16) divide the Inputs into 2 parts - the public parts & the private parts. I understand how some of the stuff in the solution vector is known to both prover & verifier but some is known only to prover. But for the purpose of constructing the equations & the zkProof, I think if we consider everything as one single entity - the solution vector - it makes Groth16 a little simpler. And I don't think this splitting adds security to the protocol.

It adds some extra work for the verifier - for e.g. the verifier has to calculate the commitments to the public parts himself. And correspondingly reduces work done by prover. Though i am not sure if the amount of change is significant on either side? Also is prover time more precious than verifier time?

I don't think this even reduces communication between Prover & Verifier - because if the size of the commitment itself doesn't change - the size of a commitment is constant - it doesn't change with the size of the polynomial - the prover has to send one commitment either way.

UPDATE:

Let's take an example for Groth16

$x^2 + x + 3 = 23$

Flattening

$x * x = a$

$a + x = b$

$b + 3 = r$

Now, in my Solution vector, I have 5 elements - $\lbrace 1, x, a, b, r \rbrace$

Now, if I want my public & private inputs separate, I would have it in this order $S = \lbrace 1, r, x, a, b \rbrace$. The public inputs $1$ & $r$ are together while the private elements $x, a, b$ are together.

With the split, we can have a Solution Vector $S = \lbrace \lbrace I \rbrace, \lbrace W \rbrace \rbrace$ where $I = \lbrace 1, r \rbrace$ & $W = \lbrace x, a, b \rbrace $

If I didn't care, I could arrange it in any order - say $ \lbrace 1, x, a, b, r \rbrace $

If we don't split, we have $A(x) \cdot B(x) = O(x) + H(x)\cdot Z(x)$

Now, if we split private & public inputs & form the equations separately, then we get

$(A_{pub}(x) + A_{prv}(x))\cdot (B_{pub}(x) + B_{prv}(x)) = O_{pub}(x) + O_{prv}(x) + H(x) \cdot Z(x)$

The 2nd way is how Groth16 does it.

On Page 7 of the Groth16 Paper,

For pairs $(\phi, w) \in R$, we call $\phi$ the statement and $w$ the witness.

Here $\phi$ is the public part & the $w$ the witness is private. On Page 10, $1$ to $l$ are public & $l+1$ to $m$ are private

Page 10

Likewise on Page 14, if you see the CRS, it's again split between $1$ to $l$ & $l+1$ to $m$

Page 14

You can also check out this page - https://www.rareskills.io/post/groth16

Here again, they discuss how it's split enter image description here

You could do the proof without the split & everything would still work.

UPDATE2: The answer I have accepted & also the discussion with the author of the answer has shown me that I wasn't really asking the correct question. So I am accepting the answer though it doesn't really answer what I asked.

$\endgroup$
2
  • $\begingroup$ Could you give concrete examples of what you mean by dividing the witness into two parts? Public inputs are public, and it's unclear what proof is about when the public input is part of the proof (e.g., constants used in a specific padding scheme). Lastly, verifiers are already orders of magnitude faster than proper. So what's the benefit here? Constrained environments may benefit from some performance gain, but I am unsure if it makes a fundamental difference in the general case. $\endgroup$ Commented Jul 7 at 15:32
  • $\begingroup$ @MarcIlunga - I have updated the question to show how the split is done in Groth16 $\endgroup$
    – user93353
    Commented Jul 8 at 3:04

1 Answer 1

1
+50
$\begingroup$

Let us revisit the scenario in zkSNARKs. In any ZK protocol, the scenario is that the Verifier has a statement $\phi$ and the Prover claims to have a proof for $\phi \in L$. In the case where $L$ is an NP language, this implies that there exists a witness $w$ such that $(\phi, w) \in R$ where $R$ is an efficient relation associated with the language $L$. Observe that finding such a witness $w$ from the statement $\phi$ is usually challenging.

So, the Verifier does not have a witness $w$ (hence, it is private to Prover) but wants the Prover to convince it that $\phi \in L$ using $w$. However, both Verifier and Prover have $\phi$; which means it is public. And, in ZK, the prover does not wish to reveal any information about $w$ to the Verifier. In Groth16, the Prover has access to the entire public and private parts, i.e., $\{a_i\}_{i=0}^m$ whereas the Verifier only has access to the public part, which is $\{a_i\}_{i=0}^{\ell}$.

The running time of the Prover is usually overlooked, whereas the running time of the Verifier is prioritised. Its running time should be (a lot) less than that of the Prover. However, when considering practicality, all entities must be efficient. The following is an excerpt from Groth 16.

One powerful motivation for building efficient non-interactive arguments is verifiable computation. A client can outsource a complicated computational task to a server in the cloud and get back the results. To convince the client that the computation is correct the server may include a non-interactive argument of correctness with the result. However, since the verifier does not have many computational resources this only makes sense if the argument is compact and computationally light to verify, i.e., it is a succinct non-interactive argument (SNARG) or a succinct non-interactive argument of knowledge (SNARK). While pairing-based SNARGs are efficient for the verifier, the computational overhead for the prover is still orders of magnitude too high to warrant use in outsourced computation [WB15,Wal15] and further efficiency improvements are needed.

$\endgroup$
9
  • $\begingroup$ What exactly are you saying I am confused about? I know that the witness is available only to the Prover & the statement is available to both. $\endgroup$
    – user93353
    Commented Jul 8 at 5:23
  • $\begingroup$ My question is different - when we are forming the R1CS & QAP - why do we need to split the polynomials into ones which have the only private & those which have only public input. I don't think this answer addresses at all. If we assume both $\phi + w$ as private & do the proof - it would still work $\endgroup$
    – user93353
    Commented Jul 8 at 5:25
  • $\begingroup$ @user93353 "witness into 2 parts - the public parts & the private parts." $\{a_i\}_{i=0}^{\ell}$ is the statement whereas $\{a_i\}_{\ell+1}^{m}$ is the witness. Or am I confused about your question? If this is case, I don't understand "You could do the proof without the split & everything would still work.". $\endgroup$
    – Mahesh S R
    Commented Jul 8 at 5:32
  • $\begingroup$ My question is while doing the proof, why not consider the whole vector including the public & private parts as one entity - i.e. no need to consider the 0 to l & the l+1 to m separately. I tried it that way & the proof works - so what's the point of considering it as 2 things for the purpose of proving. Theoritically I know that some part is public & other part is private. But if you consider the whole as private while doing the R1CS & QAP, the proof still works $\endgroup$
    – user93353
    Commented Jul 8 at 5:36
  • $\begingroup$ In the page 14 of Groth16 paper, I have a screenshot of, instead of providing 2 terms (1 to l & l + 1 to m), if the CRS provides only 1 term from 1 to m, you can still construct the proof & it works $\endgroup$
    – user93353
    Commented Jul 8 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.