Paper 2022/462

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
plonkarithmetizationposeidonhadeszero-knowledge
Contact author(s)
miguel ambrona @ nomadic-labs com
raphael toledo @ nomadic-labs com
anne-laure schmitt @ nomadic-labs com
danny willems @ nomadic-labs com
History
2022-04-22: received
Short URL
https://ia.cr/2022/462
License
Creative Commons Attribution
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.