A question about Halo

Research and Development
#1

I’ve been reading the Halo paper, and I’ve got a question about the protocol in Fig 1. It seems to me that the commitment S is not necessary, given that the correctness of S_new demonstrates the correctness of C, so if a value v_3 verifies with C, it should hold that v_3 = s(x, y). There is no need to verify it again with S. Plus S is neither used in the recursion process, so can S be eliminated? Or do I miss something here?

Thanks!

3 Likes
#2

the correctness of S_new demonstrates the correctness of C

The correctness of S_new is never established inside the circuit, only that S_old and S_cur are commitments to the same polynomial. Establishing that they’re commitments to the correct polynomial happens outside the circuit (by the “decider” or ultimate verifier of the recursive proof) as it requires linear work. S is indeed used in the recursive process; the values (S_new, y_new) are public inputs to the circuit just like G_new and the challenges from the polynomial commitment scheme. The value S_new takes on the role of S_old in the “next” proof in the recursion.

4 Likes
#3

Thank you very much for the reply! But I’m still confused on this, so please bear with me a bit more…

My understanding of the recursive process:

  1. Once the decider decides that S_new is correct, meaning S_new=Com(s(X, y_new)), and C agrees with S_new on (x, y_new), then C is correct, C=Com(s(x, Y))
  2. If C is correct, and it opens to v_3 at Y = y, then v_3 = s(x, y)
  3. With v_3=s(x, y) the verifier can check the equation ‘t = a(r + s’(x, y))-k(y)’, which concludes the current round
  4. If C agrees with S_old on (x, y_old), and C=Com(s(x, Y)), then S_old is correct, S_old=Com(s(X, y_old)).
  5. Going to the “next” proof S_old becomes S_new. Start over from step 1 (except that we do not need the decider any more).

What do I miss in the deduction, or in which step do I go wrong? Thanks again!

4 Likes
#4

Yes, I think you have a solid grasp on what’s going on. I think you’re right, the S value isn’t actually needed because we get s(x, y) from C. It’s just a redundant opening/commitment.

So the simplified process:

Accumulator: (S, y)

Accumulation step:

  • Verifier samples x, y_cur
  • Prover sends C = Commit(s(x, Y))
  • Prover sends a = s(x, y)
  • Prover sends b = s(x, y_cur)
  • Verifier samples y_new
  • Prover sends S_new = Commit(s(X, y_new))
  • Prover sends c = s(x, y_new)
  • Prover shows C opens at y to a
  • Prover shows S opens at x to a
  • Prover shows C opens at y_cur to b (which it uses to check the proof)
  • Prover shows C opens at y_new to c
  • Prover shows S_new opens at x to c
  • Accumulator is set to (S_new, y_new)

Decider:

  • Checks that S = Commit(s(X, y))
5 Likes
#5

Cool, Thanks! Happy to know that I do get the brilliant idea of Halo :smiley:

2 Likes