Strategies for integrating plookup with PLONK

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!

3 Likes

Hey…glad people are looking into this!
As a disclaimer, there are a lot of little optimizations you can do while integrating that are wip on our side, and hopefully in a few months in what might be called the ultra-plonk paper we’ll detail them all.

The permutation ρ should definitely not be made public. You can compare the products of ℓ_i + gamma and s_i+gamma for random gamma, where s is allegedly the sorted version; this will check if some permutation holds between ℓ and s. You can do this with the PLONK grand product argument.

(Such a check is combined in the plookup protocol)

2 Likes