AdamISZ
commented
2 years ago Well first, thanks for taking the time to read in detail! It's been a long while but it's great if there are things to fix, that we fix them :)
Issue 1. It relies on the quantity e^2 - e'^2 being nonzero (in order to multiply by its inverse), but this could be zero if e' = -e
Very valid point at least academically (I realise this affects the algorithm of the extractor) but: that $e$ must not be $e'$ is of course only computationally acceptable in the honest verifier model. I don't remember but I think maybe I didn't even discuss honest verifier in this document, I was trying to avoid academic niceties, but this is such a "big" part of this framework, that if I didn't, then I should have. W.r.t. the fact that we now have $e= -e'$, also, to consider, yes, again that is a very good point but I don't think it changes the fact that it's just about it being honest verifier, right? (because it's $2/n$ instead of $1/n$ and still negligible). Or did I misunderstand something there?
Issue 2. It makes substitutions using the definition of C_1; however, I don't think we can do this, because all we know is that the transcript was accepting (i.e. the verifier's final checks hold), and we can't guarantee that "an honest prover generated C_1 according to the protocol"
I can see you're right here, and it's a big mistake, so thanks for finding it.
(An aside: ironically I emailed Groth back in 2018 when writing this, to point out a couple of typos one of which is in exactly that part of the document (where he has $f{x}'$ instead of $f{x}''$ etc. in the third transcript), but somehow I didn't take seriously the fact that he used 3 transcripts, not 2. In defence of my younger self, the proof was only sketched there .. but now it's pretty clear).
So yeah 2 transcripts is not enough for the commitments for the inner product part, since there are 3 commitments. As far as I can tell it should have been like this:
(point of notation since it's so tricky here: I'll use $c_{ab}$ with $a \in {z, 1, 2}$ and $b \in {G,H}$ to represent the coefficient (scalar) of the given Pedersen commitment (one of $C_z, C_1, C_0$ corresponding to the base point $G, H$.)
So rewriting starting from equation 20, and considering only coefficients of $G$:
$\boldsymbol{f_x \cdot fy} = e^{2}c{zG} + ec{1G} + c{0G}$ $\boldsymbol{f_x' \cdot fy'} = e'^{2}c{zG} + e'c{1G} + c{0G}$
and writing it this way it's a lot clearer that we need three transcripts, not two, since we have three unknowns, i.e. we also need:
$\boldsymbol{f_x'' \cdot fy''} = e''^{2}c{zG} + e''c{1G} + c{0G}$
... in order to extract all of $c{zG}, c{1G}, c_{0G}$ and then proceed with the last part to prove (computationally) that $z = \boldsymbol{x \cdot y}$
robot-dreams
In the soundness proof of section 4.5, I think there are two potential issues with the extractor for
z:Issue 1. It relies on the quantity
e^2 - e'^2being nonzero (in order to multiply by its inverse), but this could be zero if e' = -eIssue 2. It makes substitutions using the definition of
C_1; however, I don't think we can do this, because all we know is that the transcript was accepting (i.e. the verifier's final checks hold), and we can't guarantee that "an honest prover generatedC_1according to the protocol"Would it make sense to address these issues by instead (i) generating three (rather than two) accepting transcripts, and then (ii) inverting the Vandermonde matrix for
e, e', e''in order to find an opening ofC_z?