\(\textsf{Zinc}\) : Succinct Arguments with Small Arithmetization Overheads from IOPs of Proximity to the Integers
摘要
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.