Skip to main content
Changed receiver to verifier for clarity
Source Link
Marc Ilunga
  • 3.4k
  • 1
  • 11
  • 23

Observe that it is not enough for the verifier to check that $v = v_L v_Ru^{d/2}$ only. The prover provides $v, v_L$ and $v_R$, furthermore, they know $u$. So the prover can cheat by claiming that some $v$ is the evaluation of $f(u)$ even if $com_f$ is not at all a commitment to $f$.

The reason for this extra computation is found in the note "recurse log d times". At a high level, the PCS built on bulletproofs is a recursive procedure where: a commitment $com_f$ to a polynomial $f$ and a claimed evaluation value $v = f(u)$, the problem is recursively transformed into a similar problem of half the size. This means we have a new polynomial $f'$ with a commitment value $com_f'$ and claimed evaluation value $v'$. Those values are related to the initial ones in a manner that guarantees soundness.

Finally, the receiververifier can compute the inputs to the new (smaller) problem. But the receiververifier mustn't simply take the values $com_f', gp', v'$ from the prover. First, this improves bandwidth, but importantly, it allows the receiververifier to enforce consistency checks necessary for soundness.

Observe that it is not enough for the verifier to check that $v = v_L v_Ru^{d/2}$ only. The prover provides $v, v_L$ and $v_R$, furthermore, they know $u$. So the prover can cheat by claiming that some $v$ is the evaluation of $f(u)$ even if $com_f$ is not at all a commitment to $f$.

The reason for this extra computation is found in the note "recurse log d times". At a high level, the PCS built on bulletproofs is a recursive procedure where: a commitment $com_f$ to a polynomial $f$ and a claimed evaluation value $v = f(u)$, the problem is recursively transformed into a similar problem of half the size. This means we have a new polynomial $f'$ with a commitment value $com_f'$ and claimed evaluation value $v'$. Those values are related to the initial ones in a manner that guarantees soundness.

Finally, the receiver can compute the inputs to the new (smaller) problem. But the receiver mustn't simply take the values $com_f', gp', v'$ from the prover. First, this improves bandwidth, but importantly, it allows the receiver to enforce consistency checks necessary for soundness.

Observe that it is not enough for the verifier to check that $v = v_L v_Ru^{d/2}$ only. The prover provides $v, v_L$ and $v_R$, furthermore, they know $u$. So the prover can cheat by claiming that some $v$ is the evaluation of $f(u)$ even if $com_f$ is not at all a commitment to $f$.

The reason for this extra computation is found in the note "recurse log d times". At a high level, the PCS built on bulletproofs is a recursive procedure where: a commitment $com_f$ to a polynomial $f$ and a claimed evaluation value $v = f(u)$, the problem is recursively transformed into a similar problem of half the size. This means we have a new polynomial $f'$ with a commitment value $com_f'$ and claimed evaluation value $v'$. Those values are related to the initial ones in a manner that guarantees soundness.

Finally, the verifier can compute the inputs to the new (smaller) problem. But the verifier mustn't simply take the values $com_f', gp', v'$ from the prover. First, this improves bandwidth, but importantly, it allows the verifier to enforce consistency checks necessary for soundness.

Source Link
Marc Ilunga
  • 3.4k
  • 1
  • 11
  • 23

Observe that it is not enough for the verifier to check that $v = v_L v_Ru^{d/2}$ only. The prover provides $v, v_L$ and $v_R$, furthermore, they know $u$. So the prover can cheat by claiming that some $v$ is the evaluation of $f(u)$ even if $com_f$ is not at all a commitment to $f$.

The reason for this extra computation is found in the note "recurse log d times". At a high level, the PCS built on bulletproofs is a recursive procedure where: a commitment $com_f$ to a polynomial $f$ and a claimed evaluation value $v = f(u)$, the problem is recursively transformed into a similar problem of half the size. This means we have a new polynomial $f'$ with a commitment value $com_f'$ and claimed evaluation value $v'$. Those values are related to the initial ones in a manner that guarantees soundness.

Finally, the receiver can compute the inputs to the new (smaller) problem. But the receiver mustn't simply take the values $com_f', gp', v'$ from the prover. First, this improves bandwidth, but importantly, it allows the receiver to enforce consistency checks necessary for soundness.