Arithmetization of Σ¹₁ relations with polynomial bounds in Halo 2

Anthony Hart; Morgan Thomas

Paper 2022/1105

Arithmetization of Σ¹₁ relations with polynomial bounds in Halo 2

Anthony Hart, Orbis Labs

Morgan Thomas, Orbis Labs

Abstract

Previously [4], Orbis Labs presented a method for compiling (“arithmetizing”) relations, expressed as Σ¹₁ formulas in the language of rings, into Halo 2 [1, 2, 3] arithmetic circuits. In this research, we extend this method to support polynomial quantifier bounds, in addition to constant quantifier bounds. This allows for more efficient usage of rows in the resulting circuit.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint.
Keywords: PLONK Halo 2 arithmetization logic second order arithmetic
Contact author(s): team @ orbislabs com
team @ orbislabs com
History: 2022-08-29: approved; 2022-08-26: received; See all versions
Short URL: https://ia.cr/2022/1105
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1105,
      author = {Anthony Hart and Morgan Thomas},
      title = {Arithmetization of Σ¹₁ relations with polynomial bounds in Halo 2},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1105},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1105}},
      url = {https://eprint.iacr.org/2022/1105}
}