Verification

So now the prover, who has issued the challenge $\gamma$, has both $c$ and $\pi$. He will use the verification function that takes as parameters $c,\pi ,\gamma$ and $b=f(\gamma )$. We are finally ready to use the pairing. We want to check whether the following values are equal.

$$e(\pi ,S_2-\gamma \cdot Q)\stackrel{?}{=}e(c-b\cdot P,Q)$$

The left-hand side is:

$$e(\pi ,S_2-\gamma \cdot Q)=e(Q_c(\tau )\cdot P,(\tau -\gamma )\cdot Q)$$

and using bilinearity:

$$e(Q_c(\tau )\cdot P,(\tau -\gamma )\cdot Q)=e(Q_c(\tau )\cdot (\tau -\gamma )\cdot P,Q)$$

The right-hand side is:

$$e(c-b\cdot P,Q)=e(f(\tau )\cdot P-f(\gamma )\cdot P,Q)=e((f(\tau )-f(\gamma ))\cdot P,Q)$$

So essentially what the pairing allows us to do is to check:

$$f(\tau )-f(\gamma )\stackrel{?}{=}{Q}_c(\tau )\cdot (\tau -\gamma )$$

which is expected by the construction of $Q_c$. This is equivalent to checking polynomial equality using the challenge $\tau$. But remember, nobody knows $\tau$ directly because we deleted it after setup ("toxic waste")!

Exercise 10

Implement a $\mathsf{\text{verification}}$ function that takes $c,\pi ,\gamma$ and $f(\gamma )=b$ as parameters. It should output true or false, by evaluating:

$$e(\pi ,S_2-\gamma \cdot Q)\stackrel{?}{=}e(c-b\cdot P,Q)$$

Test the function on the previously computed commitment $c$ for $a(x)$ and the proof $\pi$ computed in the previous exercise.

def verification(c,π,γ,b):
    #Solve here!
    
assert verification(c,π,γ,b) == True