Is Aztec’s Plookup Technically Sound?
Thanks to Dr. Jamie Judd and Dr. Suah Kim for providing feedback on this article.
Caution: This article contains a lot of mathematical symbols and formulas.
Table of contents
- Introduction
- Protocol summary
- Notations
- The key idea: comparing algorithm
- Algorithm testing examples
- Why is the comparing algorithm technically sound?
- Why should β and γ be random (indeterminate)?
- Applying the comparing algorithm to a protocol
- Why is the comparing protocol technically sound?
- Conclusion and opinion
Introduction
In this article, we study Plookup, especially focusing on why it technically works. Plookup is a verifiable computation protocol proposed in the manuscript “Plookup: A simplified polynomial protocol for lookup tables” written in 2020 by A. Gabizon and Z. J. Williamson who work for Aztek. This idea has been tried to be integrated with PlonK in another manuscript “PlonKup: Reconciling PlonK with plookup” written in 2022 (L. Pearson et. al.).
Protocol summary
Plookup itself is not a zero-knowledge protocol. With a polynomial commitment scheme such as Kate’s, Plookup can be transformed into a zero-knowledge protocol. When transformed, the witness becomes concealed, the proof polynomials become commitments, and the verification may need additional commitment verifications.
Plookup itself is an interactive protocol. That is, the verifier sends some challenge values in the middle that prover is producing a series of proof components. More specifically, the prover algorithm consists of at least three stages, where the first stage generates a part of the proof, the second stage receives the challenge, and the last stage generates the rest of the proof using the challenge. With the Fiat-Shamir transform, the protocol can be transformed into a non-interactive protocol. Fiat-Shamir transform introduces random oracles to sign proofs with time stamps (not absolute time but just chronological order) and verify the signatures later.
Notations
The key idea: comparing algorithm
Algorithm testing examples
Why is the comparing algorithm technically sound?
Why should β and γ be random (indeterminate)?
Applying the comparing algorithm to a protocol
Why is the comparing protocol technically sound?
Though the followings are not rigorous, we can get a rough intuition of why the protocol is technically sound. Let us move to the verification part in the 4th interaction.
Strict proof of the soundness of the comparing protocol is given in the original manuscript.
Conclusion and opinion
Plookup is an efficient protocol to verify a statement that a submitted witness has been pre-registered with a lookup table. The protocol takes computational efficiency at the cost of assuming that a prover can fully access the lookup table so that witness values can be sorted with the table values. This assumption enables the reduction of computationally heavy problems that require at worst nd comparisons to lighter problems with n+3 comparisons. Although the protocol itself is interactive and not zero-knowledge, with the help of polynomial commitment schemes and Fiat-Shamir transformation, it could be upgraded to have such properties.
In 2022, L. Pearson et. al. have tried to apply Plookup into PlonK. They extended the custom gates idea of Plonk so that in addition to the addition and multiplication gates, some gates can be customized as lookup gates. Lookup gates are simpler than arithmetic gates as they just compare a witness with expected outputs. If this approach indeed works, we can expect that proving and verifying circuits including some hard operations to be transformed into arithmetic gates such as hashing algorithms can be done with quite relieved computational complexity.
However, it is unclear whether the assumption of this protocol is practical. The assumption is that table values are always open to everyone. That means everyone carries the key, and no one would fail in generating a working proof. In this case, proofs may contain no information further than what the table values have. To make Plookup useful, we may need to find limited but focused applications where a lookup table is restricted to be published before a witness is committed.
