Paper 2023/474

eSTARK: Extending STARKs with Arguments

Héctor Masip-Ardevol, Universitat Politècnica de Catalunya
Marc Guzmán-Albiol, Universitat Politècnica de Catalunya
Jordi Baylina-Melé, Polygon zkEVM
Jose Luis Muñoz-Tapia, Universitat Politècnica de Catalunya
Abstract

STARK is a widely used transparent proof system that uses low-degree tests for proving the correctness of a computer program. STARK consumes an intermediate representation known as AIR that is more appropriate for programs with a relatively short and structured description. However, an AIR is not able to succinctly express non-equality constraints, leading to the incorporation of unwanted polynomials. We present the eSTARK protocol, a new probabilistic proof that generalizes the STARK family through the introduction of a more generic intermediate representa- tion called eAIR. We describe eSTARK in the polynomial IOP model, which com- bines the optimized version of the STARK protocol with the incorporation of three arguments into the protocol. We also explain various techniques that enhance the vanilla STARK complexity, including optimizations applied to polynomial computa- tions, and analyze the tradeoffs between controlling the constraint degree either at the representation of the AIR or inside the eSTARK itself.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
STARKlookupconectionSNARK
Contact author(s)
hector masip @ upc edu
marc guzman albiol @ upc edu
jordi @ baylina cat
jose luis munoz @ upc edu
History
2023-04-01: approved
2023-03-31: received
See all versions
Short URL
https://ia.cr/2023/474
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/474,
      author = {Héctor Masip-Ardevol and Marc Guzmán-Albiol and Jordi Baylina-Melé and Jose Luis Muñoz-Tapia},
      title = {eSTARK: Extending STARKs with Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2023/474},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/474}},
      url = {https://eprint.iacr.org/2023/474}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.