[Question] PCS based Range Proof

General Zero-Knowledge
1

Hello ZkProof community!

I have been trying to implement the PCS-based Range Proofs as described here.

My code is shared in a public repository.

I have difficulties in understanding the verification part. The authors have said:

This entire process makes two polynomial commitments, to g and q, and uses the polynomial evaluation protocol three times to evaluate g(ρ), w_cap(ρ), and g(ρω).

In order to verify the commitment to w_cap(X), the prover will also have to commit to the polynomial f(X) as well as a commitment to w_cap(X), am I correct? Using the commitments to f(X) and q(X), the verifier can verify that the calculated commitment to w_cap(X) is in fact the one claimed by the prover.

Also, in my case, I have chosen f(X) to simple be a constant polynomial f(X) = z. So revealing any evaluation of f is not an option.

How can the verifier calculate w(ρ), from the available information to them:

  • values { ρ and τ }
  • evaluations { g(ρ) , w_cap(ρ) , and g(ρω) }
  • commitments { f_commit, g_commit, q_commit, w_cap_commit }

From the evaluation challenge ρ and above evaluations, I know the evaluation of w2 and w3 at X = ρ. But I am missing something here majorly to be able to get to w(ρ).

Any help would be appreciated. Thank you.

1 Like
2

I think I have an idea of how this can be achieved.

Prover:

  • commitments { f_commit, g_commit, q_commit }
  • random values { ρ, τ } [ transformation from interactive to non-interactive is assumed ]
  • evaluations { g(ρ), g(ρω), w_cap(ρ) }
  • witness A: [ g at ρ, q at ρ, w_cap at ρ ]
  • witness B: [ g at ρw ]

Verifier

  • Using f_commit, ρ and q_commit, reconstruct w_cap_commit
  • at X = ρ, w(ρ) = w1(ρ) + τ*w2(ρ) + τ^2*w3(ρ) - q.(ρ^n - 1)
    • w(ρ) = knowns - w_cap(ρ), knowns can be calculated using g(ρ), g(ρw) and τ
    • proceed only if w(ρ) = 0
  • verify the witness for [ g at ρw ]
  • batch verify the witnesses for [ g at ρ, q at ρ, w_cap at ρ ]

By performing these operations, the verifier can verify all polynomial commitments, as well as, w(X) being 0 at a random evaluation point ρ (not controlled by the prover) signifies, it is most likely the zero polynomial.

Nowhere was f evaluated, so this seems valid.

If I’m wrong, please help correct me. Thank you all.

1 Like
3

Yes, it seems I was correct.

The proof of concept implementation has been updated to include complete proof and verification methods, and example instructions.