References: Our main references for PLUME are this ERC draft, Aayush’s blog post, and the ZK-nullifier-sig repo.
One of the most expensive parts of the PLUME circuit is computing
$$ c = \text{hash}(g, pk, h, \text{nul}, g^r, h^r) $$
because the SHA256 hash is SNARK-unfriendly. Moving this computation out of circuit would greatly decrease the circuit size at low cost to the Verifier.
The role of $c$ in the circuit is as a Fiat-Shamir challenge point. It binds the Prover to all data that precedes the Verifier challenge step. In this case, that data is $pk, h, \text{nul}, g^r, h^r$.
We propose the following redefinition of $c$:
$$ c = \text{hash}(\text{nul}, g^r, h^r) $$
Before justifying the definition, we explain how this allows us to move computation of $c$ uout of circuit:
verify protocol the assertion $c == \text{hash}(\text{nul}, g^r, h^r)$. (All of these inputs are now public quantities)Since $\text{nul}$ is already binding to $h, pk$, there is no loss of “bindingness” in removing these from the definition of $c$, so long as $\text{nul}$ remains.
The addition of $g^r, h^r$ to the set of public inputs does not sacrifice privacy, since $r$ is distributed randomly. Note that the constraint
$$ \text{nul}^c*h^r = h^s $$
with $\text{nul}, c, h^r$ public inputs implies that $h^s$ is now a public quantity. Because $s$ is distributed randomly, this does not sacrifice privacy.
$\text{nul}$ Binds to h, pk:
The constraint $\text{nul}^ch^r = h^s$ is interpreted as “Prover knows discrete log of $\text{nul}^ch^r$ with respect to $h$.” This is non-trivial because $c$ is binding to $\text{nul}, h^r$. The implication is that the Prover knows the discrete logs of $\text{nul}$ and $h^r$ separately. Moreover, the use of the same values $c, s$ as appeared in $pk^c = g^s*g^r$ implies that the discrete log of $\text{nul}$ with respect to $h$ equals that of $pk$ with respect to $g$. That is, $\text{nul} = h^{sk}$.
Thus these two constraints bind $\text{nul}$ to $h$, which in turn was computed in circuit as $\text{hash}(pk, m).$