✳flâneur — a map of the web's best reading

Arithmetic Circuits for ZK

rareskills.io · 8,022 words · saved by 1 readers

One key point from our article on P vs NP was that any solution to a problem in P or NP can be verified by modeling the problem as a Boolean circuit. Then, we convert our solution for the original problem to a set of values for the Boolean variables (called the witness) that results in the Boolean circuit returning true. This article continues the one linked above, so please read that first. One disadvantage of using a Boolean circuit to represent a solution to a problem is that it can be verbose when representing arithmetic operations such as addition or multiplication. For example, if we want to express "a + b = c where a = 16, b = 8, c = 24," we must transform a, b, and c into binary numbers. Each bit in the binary number will correspond to a distinct Boolean variable. In this example, let's assume we need 4 bits to encode a, b, and c, where a₀ represents the Least Significant Bit (LSB), and a₃ represents the Most Significant Bit (MSB) of number a, as shown below: a₃, a₂, a₁, a₀ a =

In the context of zero-knowledge proofs, an arithmetic circuit is a system of equations that models a problem in NP. A key point from our article on P vs NP is that any solution to a problem in P or NP can be verified by modeling the problem as a Boolean circuit. Then, we convert our solution for the original problem to a set of values for the Boolean variables (called the witness) that results in the Boolean circuit returning true. This article builds on the one linked above, so please read that first. Arithmetic circuits as an alternative to Boolean circuits One disadvantage of using a Boole

Explore this link on the map →

saved by

related reading