Hello all,
@cwgoes, @joebebel, and I work at Metastate and are looking to integrate plookup with PLONK. We’re curious what other teams have done.
In order to use plookup we need the lookup values to be sorted. I don’t know how much of a practical issue it is if the re-arrangement that puts it in order is leaked, but it might technically break the zero-knowledge aspect. For example, if i≤j and gate i and gate j are lookup gates with outputs ℓi and ℓj, respectively, but ℓj ≤ ℓi then ρ rearranges indices so that ρ(j)≤ρ(i). Without knowledge of ρ, the verifier may not know whether or not ℓj ≤ ℓi because the prover could blind it, but with ρ they would be able to figure it out. It’s still not obvious to me that this breaks the formal definition of zero-knowledge for an interactive proof system though.
Working only with the case of checking multiset inclusion of field elements (i.e. only looking at sections 1-3 of the plookup paper for now), the obvious (to me) way to integrate plookup with a PLONK circuit is to introduce a new sequence of lookups (ℓ1, ℓ2, … , ℓn) and then extend the copy constraint permutation σ to integrate lookups as gates. (Here the lookup index j would roughly imply that the lookup ℓj happens in the circuit between gates i and k if i≤j≤k (though I think some efficiency can be gained by a better indexing of the lookups))
| a1 | b1 | c1 | QL1 | … | QO1 | ℓ1 |
| … | … | … | … | … | … | … |
| an | bn | cn | QAn | … | QOn | ℓn |
Here we run into the issue that there’s almost no chance that the lookups will appear “in order” as part of the computation process, and the necessary re-ordering will be dependent on the wire values, so it’s input-specific, not circuit-specific.
So far, we think the best course of action is to perform PLONK’s gate check and permutation check (including wires copied to lookup table) with {ℓi}i∈[ℓ], and then have the prover compute a permutation ρ: [n] → [n]) so that (ℓρ(1), ℓρ(2), … ℓρ(n)) is increasing, perform plookup on (ℓρ(1), ℓρ(2), … ℓρ(n)) and then use a ZKP to show (ℓρ(1), ℓρ(2), … ℓρ(n)) = (ℓ1, ℓ2, … ℓn) without revealing ρ.
There seems to be some work done in this area for mixnets in electronic voting, where it’s more commonly called knowledge of a shuffle, and the PLONK paper actually cites this paper by Bayer & Groth which does just that. We’re also looking into how expensive it would be to represent the permutation in a circuit or to embed a plonk verifier (particularly pairing operation) in a depth-1 inner snark (so we can just send ρ to the snarkified verifier).
Any approaches other teams are taking, suggested directions, or warnings of dead ends are appreciated!