# RareSkills Authors - Quadratic Arithmetic Programs (Highlights)  ## Metadata **Review**:: [readwise.io](https://readwise.io/bookreview/38790673) **Source**:: #from/readwise #from/reader **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[RareSkills Authors]] **Full Title**:: Quadratic Arithmetic Programs **Category**:: #articles #readwise/articles **Category Icon**:: 📰 **URL**:: [www.rareskills.io](https://www.rareskills.io/post/quadratic-arithmetic-program) **Host**:: [[www.rareskills.io]] **Highlighted**:: [[2024-03-19]] **Created**:: [[2024-03-21]] ## Highlights - A Quadratic Arithmetic Program (QAP) is a system of equations where the coefficients are monovariate polynomials and a valid solution results in a single polynomial equality. They are quadratic because they have exactly one polynomial multiplication. ([View Highlight](https://read.readwise.io/read/01hs8v7yq9y6kdczhrbh5qgd2c)) ^694507061 - Polynomials allow us to make statements succinctly due to the Schwartz-Zippel Lemma – in a sense, we can compress a polynomial down to a single point. ([View Highlight](https://read.readwise.io/read/01hs8v8mqkd6p4p23qt57nan9e)) ^694507106 - There exists an easily computable homomorphism from R1CS to polynomials ([View Highlight](https://read.readwise.io/read/01hs8v9hbbecc4t7p9d9h2758h)) ^694507142 - The Schwartz-Zippel Lemma states that if two polynomials are randomly evaluated at the same x value, and their y value is the same, then one can be nearly certain that they are the same polynomial. ([View Highlight](https://read.readwise.io/read/01hs8vay55vrp57tq9e0jhmbms)) ^694507450 - Better yet, we turn u, v, and w into elliptic curve points [A], [B], [C] to hide their value, and the verifier pairs [A] with [B] and compares the result to [C], so we can achieve zero knowledge. ([View Highlight](https://read.readwise.io/read/01hs8vdqx5bga30hcqkf96b0qz)) ^694508203 - The goal is to prove we know Ls𝇇Rs = Os using only 3 values. ([View Highlight](https://read.readwise.io/read/01hs8vebcb6zf09z64dwzt0zfx)) ^694508266 - Vectors under addition and hadamard product are a ring ([View Highlight](https://read.readwise.io/read/01hs8vtwphycjbe551tsndezyh)) ^694510504 - Polynomials are a bit annoying to multiply by hand, so we will use python to accomplish that ([View Highlight](https://read.readwise.io/read/01hs8w2gmeay4j5n01r9a6pe3m)) ^694511741 [Poly.mul](https://docs.sympy.org/latest/modules/polys/reference.html#sympy.polys.polytools.Poly.mul) in sympy, or poly1d in numpy - Scalar multiplication is not a third operator. It is shorthand for hadamard product with a vector where each entry is the scalar. ([View Highlight](https://read.readwise.io/read/01hs8w6ynqj82tsvqa6hzkf0w2)) ^694512333 - Theorem: there exists a [Ring Homomorphism](https://en.wikipedia.org/wiki/Ring_homomorphism) from column vectors of dimension n with real number elements to polynomials with real coefficients. ([View Highlight](https://read.readwise.io/read/01hs8w7ksqa72j504eygma4w8z)) ^694512382 - Instead of thinking of a polynomial as y = ax^2 + bx + c, let’s think of it as an infinite set consisting of pairs (x, y), where the (x, y) point satisfies the polynomial equation. ([View Highlight](https://read.readwise.io/read/01hs8w98h7yhyap7rt91fq279e)) ^694512602 - In other words, we’re combining matching pairs of values from two polynomials (cartesian product), adding their “y” values together, and making a new pair with the shared x-value and summed “y” value. ([View Highlight](https://read.readwise.io/read/01hs8wcjcx69qrxk59c6r5edew)) ^694512780 - Theorem: Given n points on a cartesian (x, y) plane, they can be uniquely interpolated by a polynomial of degree n - 1. ([View Highlight](https://read.readwise.io/read/01hsazdrkkmm458rsgs8k9qsf5)) ^694880856 - There are a lot of algorithms for interpolating polynomial points, but lagrange interpolation is probably the most well known, so we will use that. ([View Highlight](https://read.readwise.io/read/01hsazfn3vzqbs2fxnx0rt458g)) ^694881041 `from scipy.interpolate import lagrange` or [sympy](https://docs.sympy.org/latest/modules/physics/mechanics/lagrange.html) - Turning matrix multiplication into the Hadamard product for Ls⊙Rs = Os ([View Highlight](https://read.readwise.io/read/01hsazs1e11hkbmwj4hdjrfzj5)) ^694881508  - (U·a) Notation ([View Highlight](https://read.readwise.io/read/01hsazzfy2ysgcxc84mhyt7x2x)) ^694882311  Pairwise vector pairwise multiplication. - However, we can preserve the equality in polynomial land by introducing a degree four polynomial that interpolates zero at x = 1,2,3,4. ([View Highlight](https://read.readwise.io/read/01hsb0372wba76bs9rv0bckbcf)) ^694882794 - Although the polynomial is non-zero, it represents a zero vector! That is, it is valid for φ(0) to be a polynomial of degree 4, like the one in the image above. ([View Highlight](https://read.readwise.io/read/01hsb03k1fwes7avep4rgtb772)) ^694882931 - It should be obvious that although t(x) represents the zero vector (it has roots at x = 1,2,3…), it won’t necessarily balance the equation (U·a)(V·a) = (W·a) + t(x). We need to multiply it by yet another polynomial that interpolates zero and balances out the equation. ([View Highlight](https://read.readwise.io/read/01hsb058zykcz51k1km4t7szq7)) ^694883113 - Remember, in vector land, h(x)t(x) is the zero vector. However, there are plenty of polynomials that represent the zero vector in polynomial land. We just pick one that balances out the equation. ([View Highlight](https://read.readwise.io/read/01hsb06grz514v7ap912crn797)) ^694883185 - The fact that t(x) is a public polynomial matters. It forces the prover to compute an h(x) that interpolates zero at x = 1,2,3. Otherwise, the prover might pick polynomial that satisfies the equation, but doesn’t actually correspond to anything from the R1CS. ([View Highlight](https://read.readwise.io/read/01hsb07zabmk6s2zywfnt21mdq)) ^694883278