and 
as:
* 
* 
* 
The tower of finite fields we work with is defined as:
* 
* 
* 
### Arithmetic circuits
be a finite field and 
a map that takes 
arguments as inputs from and outputs l elements in . The function C is an arithmetic circuit if the
value of the inputs that pass through wires to gates are only manipulated according to arithmetic operations + or x (allowing
constant gates).
Let 
, 
, 
respectively denote the input, witness and output size and
be the number of all inputs and outputs of the circuit
A tuple 
, is said to be a valid
assignment for an arithmetic circuit C if 
.
### Quadratic Arithmetic Programs (QAP)
QAPs are encodings of arithmetic circuits that allow the prover to construct a
proof of knowledge of a valid assignment 
for a given
circuit 
.
A quadratic arithmetic program (QAP) 
contains three sets of polynomials in
:
, 
, 
and a target polynomial 
.
In this setting, an assignment 
is valid for a circuit if and
only if the target polynomial divides the polynomial:
Logical circuits can be written in terms of the addition, multiplication and
negation operations.
* 
* 
* 
* 
* 
## DSL and Circuit Builder Monad
Any arithmetic circuit can be built using a domain specific language to
construct circuits that lives inside [Lang.hs](src/Circuit/Lang.hs).
```haskell ignore
type ExprM f a = State (ArithCircuit f, Int) a
execCircuitBuilder :: ExprM f a -> ArithCircuit f
```
```haskell ignore
-- | Binary arithmetic operations
add, sub, mul :: Expr Wire f f -> Expr Wire f f -> Expr Wire f f
```
```haskell ignore
-- | Binary logic operations
-- Have to use underscore or similar to avoid shadowing @and@ and @or@
-- from Prelude/Protolude.
and_, or_, xor_ :: Expr Wire f Bool -> Expr Wire f Bool -> Expr Wire f Bool
```
```haskell ignore
-- | Negate expression
not_ :: Expr Wire f Bool -> Expr Wire f Bool
```
```haskell ignore
-- | Compare two expressions
eq :: Expr Wire f f -> Expr Wire f f -> Expr Wire f Bool
```
```haskell ignore
-- | Convert wire to expression
deref :: Wire -> Expr Wire f f
```
```haskell ignore
-- | Return compilation of expression into an intermediate wire
e :: Num f => Expr Wire f f -> ExprM f Wire
```
```haskell ignore
-- | Conditional statement on expressions
cond :: Expr Wire f Bool -> Expr Wire f ty -> Expr Wire f ty -> Expr Wire f ty
```
```haskell ignore
-- | Return compilation of expression into an output wire
ret :: Num f => Expr Wire f f -> ExprM f Wire
```
The following program represents the image of the
arithmetic circuit [above](#arithmetic-circuits-1).
```haskell ignore
program :: ArithCircuit Fr
program = execCircuitBuilder (do
i0 <- fmap deref input
i1 <- fmap deref input
i2 <- fmap deref input
let r0 = mul i0 i1
r1 = mul r0 (add i0 i2)
ret r1)
```
The output of an arithmetic circuit can be converted to a DOT graph and save it
as SVG.
```haskell ignore
dotOutput :: Text
dotOutput = arithCircuitToDot (execCircuitBuilder program)
```
.
```haskell
import Protolude
import qualified Data.Map as Map
import Data.Pairing.BN254 (Fr, getRootOfUnity)
import Circuit.Arithmetic
import Circuit.Expr
import Circuit.Lang
import Fresh (evalFresh, fresh)
import QAP
program :: ArithCircuit Fr
program = execCircuitBuilder (do
i0 <- fmap deref input
i1 <- fmap deref input
i2 <- fmap deref input
let r0 = mul i0 i1
r1 = mul r0 (add i0 i2)
ret r1)
```
We need to generate the roots of the circuit to construct polynomials and
that satisfy the divisibility property and encode the circuit to a QAP to
allow the prover to construct a proof of a valid assignment.
We also need to give values to the three input wires to this arithmetic circuit.
```haskell
roots :: [[Fr]]
roots = evalFresh (generateRoots (fmap (fromIntegral . (+ 1)) fresh) program)
qap :: QAP Fr
qap = arithCircuitToQAPFFT getRootOfUnity roots program
inputs :: Map.Map Int Fr
inputs = Map.fromList [(0, 7), (1, 5), (2, 4)]
```
A prover can now generate a valid assignment.
```haskell
assignment :: QapSet Fr
assignment = generateAssignment program inputs
```
The verifier can check the divisibility property of by for the given circuit.
```haskell
main :: IO ()
main = do
if verifyAssignment qap assignment
then putText "Valid assignment"
else putText "Invalid assignment"
```
## Disclaimer
This is experimental code meant for research-grade projects only. Please do not
use this code in production until it has matured significantly.
## License
```
Copyright (c) 2017-2020 Adjoint Inc.
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE
OR OTHER DEALINGS IN THE SOFTWARE.
```