### New optimization techniques for PlonK’s arithmetization

Miguel Ambrona, Anne-Laure Schmitt, Raphael R. Toledo, and Danny Willems

##### Abstract

PlonK is a universal and updatable zk-SNARK for general circuit satisfiability that allows a verifier to check the validity of a certain NP statement very efficiently, optionally in zero-knowledge. PlonK requires that the NP relation of interest be expressed as a system of so-called PlonK constraints. Such conversion is complex and can be implemented in various ways, having a great impact on the prover complexity (which is typically linearithmic in the number of PlonK constraints). We propose several general results for simplifying PlonK constraint systems, which produce more compact but equivalent systems and can lead to significant performance improvements. We also develop an automated optimizer of constraints, based on our techniques, that can be used to construct very compact and less error-prone constraint systems, favoring a more auditable circuit design. Finally, we demonstrate the potential of our techniques by implementing optimized constraint systems for the Poseidon hash, obtaining the most compact representations in the Turbo-PlonK model with minimal custom gates. En route, we devise a novel optimization idea for implementing Poseidon partial rounds and show that it can be applied to both simplifying SNARK circuits and achieving performance improvements in CPU implementations of the Poseidon hash.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Contact author(s)
History
Short URL
https://ia.cr/2022/462

CC BY

BibTeX

@misc{cryptoeprint:2022/462,
author = {Miguel Ambrona and Anne-Laure Schmitt and Raphael R.  Toledo and Danny Willems},
title = {New optimization techniques for PlonK’s arithmetization},
howpublished = {Cryptology ePrint Archive, Paper 2022/462},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/462}},
url = {https://eprint.iacr.org/2022/462}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.