We introduce \(\textsf{Zinc}\) , a hash-based succinct argument for integer arithmetic. \(\textsf{Zinc}\) ’s goal is to provide a practically efficient scheme that enables bypassing the arithmetization overheads that many field-based state-of-the-art succinct arguments currently present, and which can be of orders of magnitude in many applications. By enabling proving statements over the integers, we are able to arithmetize many operations of interests with almost no overhead. This includes modular operations involving any moduli, not necessarily prime, and possibly involving multiple moduli in the same statement. In particular, \(\textsf{Zinc}\) allows to prove statements for the ring \(\mathbb {Z}/n\mathbb {Z}\) for arbitrary \(n\ge 1\) . At its core, \(\textsf{Zinc}\) is a succinct argument for proving relations over the rational numbers \(\mathbb {Q}\) , even though when applied to integer statements, an honest \(\textsf{P}\) and \(\textsf{V}\) will only operate with integers. \(\textsf{Zinc}\) consists of two main components: 1) \(\textsf{Zinc}\) - \(\textsf{PIOP}\) , a framework for proving algebraic statements over the rationals by modding out a randomly chosen prime q, followed by running a suitable PIOP over \(\mathbb {F}_q\) (this is similar to the approach from [15], with the difference that we use localizations of \(\mathbb {Q}\) to enable prime modular projection); and 2) \(\textsf{Zip}\) , a Brakedown-type Polynomial Commitment Scheme which is built from what we call an IOP of Proximity to the Integers. The latter primitive guarantees that a prover is using a polynomial with coefficients close to being integral. Importantly, and departing from [8, 15], our schemes are purely code and hash-based, and do not require hidden order groups. In its final form, \(\textsf{Zinc}\) operates similarly to other hash-based schemes using Brakedown as their PCS, with the perk that it enables working over \(\mathbb {Z}\) (and \(\mathbb {Q}\) ) natively.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

\(\textsf{Zinc}\) : Succinct Arguments with Small Arithmetization Overheads from IOPs of Proximity to the Integers

  • Albert Garreta,
  • Hendrik Waldner,
  • Ilia Vlasov,
  • Katerina Hristova,
  • Luca Dall’Ava,
  • Marko Čupić,
  • Matthew Klein

摘要

We introduce \(\textsf{Zinc}\) , a hash-based succinct argument for integer arithmetic. \(\textsf{Zinc}\) ’s goal is to provide a practically efficient scheme that enables bypassing the arithmetization overheads that many field-based state-of-the-art succinct arguments currently present, and which can be of orders of magnitude in many applications. By enabling proving statements over the integers, we are able to arithmetize many operations of interests with almost no overhead. This includes modular operations involving any moduli, not necessarily prime, and possibly involving multiple moduli in the same statement. In particular, \(\textsf{Zinc}\) allows to prove statements for the ring \(\mathbb {Z}/n\mathbb {Z}\) for arbitrary \(n\ge 1\) . At its core, \(\textsf{Zinc}\) is a succinct argument for proving relations over the rational numbers \(\mathbb {Q}\) , even though when applied to integer statements, an honest \(\textsf{P}\) and \(\textsf{V}\) will only operate with integers. \(\textsf{Zinc}\) consists of two main components: 1) \(\textsf{Zinc}\) - \(\textsf{PIOP}\) , a framework for proving algebraic statements over the rationals by modding out a randomly chosen prime q, followed by running a suitable PIOP over \(\mathbb {F}_q\) (this is similar to the approach from [15], with the difference that we use localizations of \(\mathbb {Q}\) to enable prime modular projection); and 2) \(\textsf{Zip}\) , a Brakedown-type Polynomial Commitment Scheme which is built from what we call an IOP of Proximity to the Integers. The latter primitive guarantees that a prover is using a polynomial with coefficients close to being integral. Importantly, and departing from [8, 15], our schemes are purely code and hash-based, and do not require hidden order groups. In its final form, \(\textsf{Zinc}\) operates similarly to other hash-based schemes using Brakedown as their PCS, with the perk that it enables working over \(\mathbb {Z}\) (and \(\mathbb {Q}\) ) natively.