 # [Question] PCS based Range Proof

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

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.