adamisz / from0k2bp Goto Github PK

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'^2 being nonzero (in order to multiply by its inverse), but this could be zero if e' = -e

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"

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 of C_z?

Bootle's protocol divides the lengths of vectors in each step, until the length is one. Any decomposition works, but we want to send as few elements as possible. In other words, we want the minimal sum of factors, which is the prime factors if I am not mistaken.

Does it make sense to change the example 600 = 10 * 10 * 6 (yielding 42 elements) into 600 = 2^3 * 3 * 5^2 (yielding 23 elements)? Would this help underline the message?

Hi Adam, at the end of Section 5.1 (Condensing a single vector), we consider the example starting with a 600-dimension vector, which we first chunk into ten 60-dimensional vectors, and then again into ten 6-dimensional vectors. Shouldn't the number of commitments / revelations in this example be 10 × 2 - 1 diagonals + 10 × 2 - 1 diagonals + 6 scalars = 19 + 19 + 6 = 44 items, instead of 43 as stated?

I just don't make sense of why c=<a,b> can be ensured by raising u to the power x.
Thank your for any advise.

To prove knowledge soundness of the Bulletproofs inner product argument, I think you need four transcripts per step: Three transcripts are used to compute the vectors a, a_L, etc. Then, we arrange these vectors in a cubic polynomial over (x_i)^2 and show that it is the zero polynomial (using four transcripts). This implies that half of the a_L and a_R vectors is zero and the other half is equal to a.

Should the proof of soundness (Schnorr) in page 12 use fixed C_0 (as well as the corresponding x_0) to extract (x_1, x_2, ..., x_m) by running m+1 times?

I think C_0 should be fixed to get the Vandermonde matrix, which should be as follows:
(C_0, e_1, (z_1, s_1))
(C_0, e_2, (z_2, s_2))
...
(C_0, e_m, (z_m, s_m))
Otherwise we cannot get the Vandermonde matrix since x_0 changes every time.

Anyway, thanks for your perfect introduction of ZK and bullet proof.

Not really an issue, but regarding sentence on page 9/10:

In academic coverage of this concept, there are a lot additional definitions used. A “witness” is a piece of (usually secret) data corresponding to a “state- ment” which the Prover possesses but does not want to reveal. Zero knowledge comes in flavours such as “Honest Verifier Zero Knowledge” with a number of subcategories

I just want to signal I have recently closed an A3/tabloid size cheat-sheet about that stuff at a level I think suitable to from0k2bp typical readers:
https://github.com/baro77/ZKbasicsCS
It also quickly deals with Fiat-Shamir NIZK heuristic recalled in section 6.2.4

Thanks for your inspiring document!

BTW I don't open a PR cause it's more an automation-issue I guess, but I take the occasion to notice that pre-compiled PDF in your repo is missing the recent PRs by robot-dreams

This paragraph:

I tried to do this, by splitting the 600 length vectors into vectors of 10 elements each ([a1-a10, a11-a20, ...]) and doing the diagonal iteration. Since the length of this new vector is 60, this gives us -59 <= k <= 59 minus the k=0 case, resulting in 118 commitments for the first reduction. Where does "2*10- 1 = 19" come from?

There is some math missing on page 8 between the sentences
"These last two are calculated as:" AND "Note that the summations.."

OK, so there was another error here that neither you or I noticed before: send to V - I believe I originally had in mind send k + x to V, with k random (something like that). Point being you can send x in a blinded form but it's useless unless V can verify that what was blinded was the right x.

Source: #11 (comment)

on page 23, there are four lines using x . dy . y . dx instead of x . dy + y . dx
also, how do you compute z there without having x . dy + y . dx available (it seems you only know its commitment).