Practical PQ-SNARKs have verifier costs that grow linearly with the desired number of bits of security. One promising technique for mitigating this tension is SNARK composition — which I described in my previous post as a means to resolve tension between prover and verifier costs, but it can also address security.
Polygon Hermez is composing PQ-SNARKs with PlonK. The idea is that the prover first generates a PQ-SNARK proof π. If the PQ-SNARK is configured to have a fast prover and an adequate security level, then π will be large. So the prover does not send π to the verifier. Instead, it uses PlonK to prove that it knows π.
This means applying PlonK to a circuit that takes π as input and checks that the PQ-SNARK verifier would accept π. Since the PQ-SNARK has polylogarithmic verification cost, PlonK is applied to a small circuit, and hence the PlonK prover is fast. Since PlonK proofs are small and cheap to verify, verification costs are low.
Unfortunately, the use of PlonK destroys transparency and post-quantum security. One can instead consider using the PQ-SNARK itself in place of PlonK to prove knowledge of π (in fact the PQ-SNARK used by Polygon is self-composed in this manner).
In this second application of the PQ-SNARK, to prove knowledge of π, the system can be configured to achieve adequate security with reasonably-sized proofs, for example, by selecting a very small code rate for use in FRI. The key point is that, while this small code rate is bad for prover time, the second application of the PQ-SNARK is applied only to a small circuit, so the total prover time should still be small.
Our theoretical understanding of the security of composed SNARKs leaves much to be desired. However, there aren’t known attacks on them that are faster than attacking one of the constituent SNARKs individually. For example, if composing a PQ-SNARK with PlonK, we do not know a better attack than to either attack the PQ-SNARK (i.e., find a PQ-SNARK proof π of a false statement), or to attack PlonK (i.e., find a PlonK proof of the false statement “I know a PQ-SNARK proof π that the verifier would have accepted.”)
Composing SNARKs in this manner is an increasingly popular way to improve performance. I hope that protocol designers also use it to improve security.
Justin Thaler is an Associate Professor at Georgetown University. Before joining Georgetown, he spent two years as a Research Scientist at Yahoo Labs in New York, before which he was a Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley.
Editor: Tim Sullivan @tim_org
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information