Strategies for integrating plookup with PLONK

Research
#1

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
#2

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
#3

We noticed in Barretenberg and some other implementations that there is a fourth wire already being (only partially) used. This thread started with the assumption that having a vector of length n devoted solely to housing lookups was unavoidable, but here are our thoughts on taking advantage of available real estate on the fourth wire. We’re hoping if there are any glaring errors, the community would catch them.

First consider the slightly easier case of a lookup table of size n/2 so that we can concatenate n/2 lookups and fit the sequence’s index set in a subgroup of size n. I don’t think we’d run into any new kinds of trouble by extending it to tables of size n.

(Apologies for the abundance of notation) Let H be the multiplicative subgroup of order n. Let q = \{q_i\}_{i \in H} be the selector sequence for lookup gates. Let d = \{d_i\}_{i \in H} be the sequence of fourth wire values (where we’ll keep our compressed gate lookups). Let \rho be a permutation on H. Overloading notation, \rho acts on polynomials of degree at most n-1 by sending a polynomial \hat{r}(X) which interpolates a sequence \{r_i\}_{i \in H} to \rho(\hat{r})(X) which interpolates \{r_{\rho(i)}\}_{i \in H}.

With this notation, it seems that the condition we would want to check is that there exists a \rho such that

\rho(\hat{q}) \cdot \rho(\hat{d}) \equiv_H \rho(\hat{q}) \cdot \hat{s}

which, following Ariel’s suggestion, would most easily be done by checking equality of a simple multiset encoding

\prod_{i \in H} \big( x - \rho(q_i) \cdot \rho(d_i) \big) = \prod_{i \in H} \big( x - \rho(q)_i \cdot s_i \big)

or, because \rho is a permutation, we can save a bit of effort on the left hand side and re-write it as

\prod_{i \in H} \big( x - q_i \cdot d_i \big) = \prod_{i \in H} \big( x - \rho(q)_i \cdot s_i \big)

And this check would fit neatly in Plonk’s product argument.

Looking forward to ultra-plonk!

1 Like