-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Arithmetic circuits for zkSNARKs
--   
--   Arithmetic circuits for zkSNARKs
@package arithmetic-circuits
@version 0.2.0


-- | Definition of arithmetic circuits that only contain addition, scalar
--   multiplications and constant gates, along with its direct evaluation
--   and translation into affine maps.
module Circuit.Affine

-- | Arithmetic circuits without multiplication, i.e. circuits describe
--   affine transformations.
data AffineCircuit i f
Add :: AffineCircuit i f -> AffineCircuit i f -> AffineCircuit i f
ScalarMul :: f -> AffineCircuit i f -> AffineCircuit i f
ConstGate :: f -> AffineCircuit i f
Var :: i -> AffineCircuit i f
collectInputsAffine :: Ord i => AffineCircuit i f -> [i]

-- | Apply mapping to variable names, i.e. rename variables. (Ideally the
--   mapping is injective.)
mapVarsAffine :: (i -> j) -> AffineCircuit i f -> AffineCircuit j f

-- | Evaluate the arithmetic circuit without mul-gates on the given input.
--   Variable map is assumed to have all the variables referred to in the
--   circuit. Failed lookups are currently treated as 0.
evalAffineCircuit :: Num f => (i -> vars -> Maybe f) -> vars -> AffineCircuit i f -> f

-- | Convert non-mul circuit to a vector representing the evaluation
--   function. We use a <tt>Map</tt> to represent the potentially sparse
--   vector.
affineCircuitToAffineMap :: (Num f, Ord i) => AffineCircuit i f -> (f, Map i f)

-- | Evaluating the affine map representing the arithmetic circuit without
--   mul-gates against inputs. If the input map does not have a variable
--   that is referred to in the affine map, then it is treated as a 0.
evalAffineMap :: (Num f, Ord i) => (f, Map i f) -> Map i f -> f
dotProduct :: (Num f, Ord i) => Map i f -> Map i f -> f
instance (Data.Aeson.Types.ToJSON.ToJSON i, Data.Aeson.Types.ToJSON.ToJSON f) => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Affine.AffineCircuit i f)
instance (Data.Aeson.Types.FromJSON.FromJSON f, Data.Aeson.Types.FromJSON.FromJSON i) => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Affine.AffineCircuit i f)
instance (Control.DeepSeq.NFData f, Control.DeepSeq.NFData i) => Control.DeepSeq.NFData (Circuit.Affine.AffineCircuit i f)
instance GHC.Generics.Generic (Circuit.Affine.AffineCircuit i f)
instance (GHC.Show.Show f, GHC.Show.Show i) => GHC.Show.Show (Circuit.Affine.AffineCircuit i f)
instance (GHC.Classes.Eq f, GHC.Classes.Eq i) => GHC.Classes.Eq (Circuit.Affine.AffineCircuit i f)
instance (GHC.Read.Read f, GHC.Read.Read i) => GHC.Read.Read (Circuit.Affine.AffineCircuit i f)
instance (Text.PrettyPrint.Leijen.Text.Pretty i, GHC.Show.Show f) => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Affine.AffineCircuit i f)


-- | Definition of arithmetic circuits: one with a single multiplication
--   gate with affine inputs and another variant with an arbitrary number
--   of such gates.
module Circuit.Arithmetic

-- | An arithmetic circuit with a single multiplication gate.
data Gate i f
Mul :: AffineCircuit i f -> AffineCircuit i f -> i -> Gate i f
[mulLeft] :: Gate i f -> AffineCircuit i f
[mulRight] :: Gate i f -> AffineCircuit i f
[mulOutput] :: Gate i f -> i
Equal :: i -> i -> i -> Gate i f
[eqInput] :: Gate i f -> i
[eqMagic] :: Gate i f -> i
[eqOutput] :: Gate i f -> i
Split :: i -> [i] -> Gate i f
[splitInput] :: Gate i f -> i
[splitOutputs] :: Gate i f -> [i]

-- | Apply mapping to variable names, i.e. rename variables. (Ideally the
--   mapping is injective.)
mapVarsGate :: (i -> j) -> Gate i f -> Gate j f
collectInputsGate :: Ord i => Gate i f -> [i]

-- | List output wires of a gate
outputWires :: Gate i f -> [i]

-- | A circuit is a list of multiplication gates along with their output
--   wire labels (which can be intermediate or actual outputs).
newtype ArithCircuit f
ArithCircuit :: [Gate Wire f] -> ArithCircuit f
fetchVars :: AffineCircuit Wire f -> [Wire]

-- | Generate enough roots for a circuit
generateRoots :: Applicative m => m f -> ArithCircuit f -> m [[f]]

-- | Check whether an arithmetic circuit does not refer to intermediate
--   wires before they are defined and whether output wires are not used as
--   input wires.
validArithCircuit :: ArithCircuit f -> Bool

-- | Wires are can be labeled in the ways given in this data type
data Wire
InputWire :: Int -> Wire
IntermediateWire :: Int -> Wire
OutputWire :: Int -> Wire

-- | Evaluate a single gate
evalGate :: (Bits f, Fractional f) => (i -> vars -> Maybe f) -> (i -> f -> vars -> vars) -> vars -> Gate i f -> vars

-- | Evaluate an arithmetic circuit on a given environment containing the
--   inputs. Outputs the entire environment (outputs, intermediate values
--   and inputs).
evalArithCircuit :: forall f vars. (Bits f, Fractional f) => (Wire -> vars -> Maybe f) -> (Wire -> f -> vars -> vars) -> ArithCircuit f -> vars -> vars

-- | Turn a binary expansion back into a single value.
unsplit :: Num f => [Wire] -> AffineCircuit Wire f
instance Data.Aeson.Types.ToJSON.ToJSON f => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Arithmetic.ArithCircuit f)
instance Data.Aeson.Types.FromJSON.FromJSON f => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Arithmetic.ArithCircuit f)
instance Control.DeepSeq.NFData f => Control.DeepSeq.NFData (Circuit.Arithmetic.ArithCircuit f)
instance GHC.Generics.Generic (Circuit.Arithmetic.ArithCircuit f)
instance GHC.Show.Show f => GHC.Show.Show (Circuit.Arithmetic.ArithCircuit f)
instance GHC.Classes.Eq f => GHC.Classes.Eq (Circuit.Arithmetic.ArithCircuit f)
instance (Data.Aeson.Types.ToJSON.ToJSON i, Data.Aeson.Types.ToJSON.ToJSON f) => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Arithmetic.Gate i f)
instance (Data.Aeson.Types.FromJSON.FromJSON i, Data.Aeson.Types.FromJSON.FromJSON f) => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Arithmetic.Gate i f)
instance (Control.DeepSeq.NFData f, Control.DeepSeq.NFData i) => Control.DeepSeq.NFData (Circuit.Arithmetic.Gate i f)
instance GHC.Generics.Generic (Circuit.Arithmetic.Gate i f)
instance (GHC.Classes.Eq f, GHC.Classes.Eq i) => GHC.Classes.Eq (Circuit.Arithmetic.Gate i f)
instance (GHC.Show.Show f, GHC.Show.Show i) => GHC.Show.Show (Circuit.Arithmetic.Gate i f)
instance Data.Aeson.Types.FromJSON.FromJSON Circuit.Arithmetic.Wire
instance Data.Aeson.Types.ToJSON.ToJSON Circuit.Arithmetic.Wire
instance Control.DeepSeq.NFData Circuit.Arithmetic.Wire
instance GHC.Generics.Generic Circuit.Arithmetic.Wire
instance GHC.Classes.Ord Circuit.Arithmetic.Wire
instance GHC.Classes.Eq Circuit.Arithmetic.Wire
instance GHC.Show.Show Circuit.Arithmetic.Wire
instance GHC.Show.Show f => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Arithmetic.ArithCircuit f)
instance (Text.PrettyPrint.Leijen.Text.Pretty i, GHC.Show.Show f) => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Arithmetic.Gate i f)
instance Text.PrettyPrint.Leijen.Text.Pretty Circuit.Arithmetic.Wire


-- | Translate arithmetic circuits into a Hadamard product equation and
--   linear constraints.
module Circuit.Bulletproofs
setupProof :: MonadRandom m => AltArithCircuit Fr -> m (SetupProof Fr PA)
data SetupProof f p
SetupProof :: Assignment f -> Pedersens f p -> ArithCircuit f -> ArithWitness f p -> Int -> Int -> SetupProof f p
[assignment] :: SetupProof f p -> Assignment f
[pedersens] :: SetupProof f p -> Pedersens f p
[circuit] :: SetupProof f p -> ArithCircuit f
[witness] :: SetupProof f p -> ArithWitness f p
[n] :: SetupProof f p -> Int
[m] :: SetupProof f p -> Int
data AltArithCircuit f
data LinearConstraint f
LinearConstraint :: Map Int f -> Map Int f -> Map Int f -> Map Int f -> f -> LinearConstraint f

-- | wL
[lcWeightsLeft] :: LinearConstraint f -> Map Int f

-- | wR
[lcWeightsRight] :: LinearConstraint f -> Map Int f

-- | wO
[lcWeightsOut] :: LinearConstraint f -> Map Int f

-- | wV
[lcWeightsIn] :: LinearConstraint f -> Map Int f

-- | c
[lcConstant] :: LinearConstraint f -> f
data GateConstraint i f
GateConstraint :: LinearConstraint f -> LinearConstraint f -> MulConstraint i -> GateConstraint i f
[gcLinearConstraintLeft] :: GateConstraint i f -> LinearConstraint f
[gcLinearConstraintRight] :: GateConstraint i f -> LinearConstraint f
[gcMulConstraint] :: GateConstraint i f -> MulConstraint i
rewire :: Int -> Wire -> AltWire

-- | Use different wire type as required for the constraints generated in
--   this module.
rewireCircuit :: ArithCircuit f -> AltArithCircuit f
circuitToConstraints :: Num f => AltArithCircuit f -> [GateConstraint AltWire f]

-- | Replace all input wires v_i with a mul-gate (v_i * 1). This means that
--   when we translate it to linear constraints, the weights matrix for V
--   will always be of rank m, where m is the number of input wires, as is
--   required by the Bulletproof protocol.
transformInputs :: forall f. Num f => AltArithCircuit f -> AltArithCircuit f
evalCircuit :: Num f => AltArithCircuit f -> Assignment f -> Assignment f
computeBulletproofsAssignment :: AltArithCircuit Fr -> [Fr] -> Int -> Assignment Fr
instance (Control.DeepSeq.NFData f, Control.DeepSeq.NFData p) => Control.DeepSeq.NFData (Circuit.Bulletproofs.SetupProof f p)
instance GHC.Generics.Generic (Circuit.Bulletproofs.SetupProof f p)
instance (GHC.Show.Show f, GHC.Show.Show p) => GHC.Show.Show (Circuit.Bulletproofs.SetupProof f p)
instance (Control.DeepSeq.NFData f, Control.DeepSeq.NFData p) => Control.DeepSeq.NFData (Circuit.Bulletproofs.Pedersens f p)
instance GHC.Generics.Generic (Circuit.Bulletproofs.Pedersens f p)
instance (GHC.Show.Show f, GHC.Show.Show p) => GHC.Show.Show (Circuit.Bulletproofs.Pedersens f p)
instance Data.Aeson.Types.ToJSON.ToJSON f => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Bulletproofs.Assignment f)
instance Data.Aeson.Types.FromJSON.FromJSON f => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Bulletproofs.Assignment f)
instance GHC.Generics.Generic (Circuit.Bulletproofs.Assignment f)
instance GHC.Show.Show f => GHC.Show.Show (Circuit.Bulletproofs.Assignment f)
instance (Data.Aeson.Types.ToJSON.ToJSON i, Data.Aeson.Types.ToJSON.ToJSON f) => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Bulletproofs.GateConstraint i f)
instance (Data.Aeson.Types.FromJSON.FromJSON f, Data.Aeson.Types.FromJSON.FromJSON i) => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Bulletproofs.GateConstraint i f)
instance GHC.Generics.Generic (Circuit.Bulletproofs.GateConstraint i f)
instance (GHC.Show.Show f, GHC.Show.Show i) => GHC.Show.Show (Circuit.Bulletproofs.GateConstraint i f)
instance Data.Aeson.Types.ToJSON.ToJSON i => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Bulletproofs.MulConstraint i)
instance Data.Aeson.Types.FromJSON.FromJSON i => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Bulletproofs.MulConstraint i)
instance GHC.Generics.Generic (Circuit.Bulletproofs.MulConstraint i)
instance GHC.Show.Show i => GHC.Show.Show (Circuit.Bulletproofs.MulConstraint i)
instance Data.Aeson.Types.ToJSON.ToJSON f => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Bulletproofs.LinearConstraint f)
instance Data.Aeson.Types.FromJSON.FromJSON f => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Bulletproofs.LinearConstraint f)
instance GHC.Generics.Generic (Circuit.Bulletproofs.LinearConstraint f)
instance GHC.Show.Show f => GHC.Show.Show (Circuit.Bulletproofs.LinearConstraint f)
instance Data.Aeson.Types.ToJSON.ToJSON f => Data.Aeson.Types.ToJSON.ToJSON (Circuit.Bulletproofs.AltArithCircuit f)
instance Data.Aeson.Types.FromJSON.FromJSON f => Data.Aeson.Types.FromJSON.FromJSON (Circuit.Bulletproofs.AltArithCircuit f)
instance Control.DeepSeq.NFData f => Control.DeepSeq.NFData (Circuit.Bulletproofs.AltArithCircuit f)
instance GHC.Generics.Generic (Circuit.Bulletproofs.AltArithCircuit f)
instance GHC.Show.Show f => GHC.Show.Show (Circuit.Bulletproofs.AltArithCircuit f)
instance Data.Aeson.Types.ToJSON.ToJSON Circuit.Bulletproofs.AltWire
instance Data.Aeson.Types.FromJSON.FromJSON Circuit.Bulletproofs.AltWire
instance Control.DeepSeq.NFData Circuit.Bulletproofs.AltWire
instance GHC.Generics.Generic Circuit.Bulletproofs.AltWire
instance GHC.Classes.Ord Circuit.Bulletproofs.AltWire
instance GHC.Classes.Eq Circuit.Bulletproofs.AltWire
instance GHC.Show.Show Circuit.Bulletproofs.AltWire
instance (Text.PrettyPrint.Leijen.Text.Pretty i, Text.PrettyPrint.Leijen.Text.Pretty f) => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Bulletproofs.GateConstraint i f)
instance Text.PrettyPrint.Leijen.Text.Pretty i => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Bulletproofs.MulConstraint i)
instance Text.PrettyPrint.Leijen.Text.Pretty f => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Bulletproofs.LinearConstraint f)
instance (Text.PrettyPrint.Leijen.Text.Pretty f, GHC.Show.Show f) => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Bulletproofs.AltArithCircuit f)
instance Text.PrettyPrint.Leijen.Text.Pretty Circuit.Bulletproofs.AltWire


-- | Visualise circuits using Graphviz
module Circuit.Dot
arithCircuitToDot :: Show f => ArithCircuit f -> Text
dotWriteSVG :: FilePath -> Text -> IO ()

module Circuit.Expr
data UnOp f a
[UNeg] :: UnOp f f
[UNot] :: UnOp f Bool

-- | rotate bits
[URot] :: Int -> Int -> UnOp f f
data BinOp f a
[BAdd] :: BinOp f f
[BSub] :: BinOp f f
[BMul] :: BinOp f f
[BAnd] :: BinOp f Bool
[BOr] :: BinOp f Bool
[BXor] :: BinOp f Bool

-- | Expression data type of (arithmetic) expressions over a field
--   <tt>f</tt> with variable names/indices coming from <tt>i</tt>.
data Expr i f ty
[EConst] :: f -> Expr i f f
[EConstBool] :: Bool -> Expr i f Bool
[EVar] :: i -> Expr i f f
[EVarBool] :: i -> Expr i f Bool
[EUnOp] :: UnOp f ty -> Expr i f ty -> Expr i f ty
[EBinOp] :: BinOp f ty -> Expr i f ty -> Expr i f ty -> Expr i f ty
[EIf] :: Expr i f Bool -> Expr i f ty -> Expr i f ty -> Expr i f ty
[EEq] :: Expr i f f -> Expr i f f -> Expr i f Bool
type ExprM f a = State (ArithCircuit f, Int) a
compile :: Num f => Expr Wire f ty -> ExprM f (Either Wire (AffineCircuit Wire f))

-- | Add a Mul and its output to the ArithCircuit
emit :: Gate Wire f -> ExprM f ()

-- | Fresh intermediate variables
imm :: ExprM f Wire

-- | Turn a wire into an affine circuit, or leave it be
addVar :: Either Wire (AffineCircuit Wire f) -> AffineCircuit Wire f

-- | Turn an affine circuit into a wire, or leave it be
addWire :: Num f => Either Wire (AffineCircuit Wire f) -> ExprM f Wire

-- | Fresh input variables
freshInput :: ExprM f Wire

-- | Fresh output variables
freshOutput :: ExprM f Wire

-- | Rotate a list to the right
rotateList :: Int -> [a] -> [a]
runCircuitBuilder :: ExprM f a -> (a, ArithCircuit f)
evalCircuitBuilder :: ExprM f a -> a
execCircuitBuilder :: ExprM f a -> ArithCircuit f

-- | Translate an arithmetic expression to an arithmetic circuit
exprToArithCircuit :: Num f => Expr Int f ty -> Wire -> ExprM f ()

-- | Evaluate arithmetic expressions directly, given an environment
evalExpr :: (Bits f, Num f) => (i -> vars -> Maybe f) -> Expr i f ty -> vars -> ty

-- | Truncate a number to the given number of bits and perform a right
--   rotation (assuming small-endianness) within the truncation.
truncRotate :: Bits f => Int -> Int -> f -> f
instance (GHC.Show.Show i, GHC.Show.Show f) => GHC.Show.Show (Circuit.Expr.Expr i f ty)
instance GHC.Show.Show f => GHC.Show.Show (Circuit.Expr.BinOp f a)
instance GHC.Show.Show f => GHC.Show.Show (Circuit.Expr.UnOp f a)
instance (Text.PrettyPrint.Leijen.Text.Pretty f, Text.PrettyPrint.Leijen.Text.Pretty i, Text.PrettyPrint.Leijen.Text.Pretty ty) => Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Expr.Expr i f ty)
instance Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Expr.BinOp f a)
instance Text.PrettyPrint.Leijen.Text.Pretty (Circuit.Expr.UnOp f a)


-- | Surface language
module Circuit.Lang

-- | Convert constant to expression
c :: f -> Expr Wire f f

-- | Binary arithmetic operations on expressions
add :: Expr Wire f f -> Expr Wire f f -> Expr Wire f f

-- | Binary arithmetic operations on expressions
sub :: Expr Wire f f -> Expr Wire f f -> Expr Wire f f

-- | Binary arithmetic operations on expressions
mul :: Expr Wire f f -> Expr Wire f f -> Expr Wire f f

-- | Binary logic operations on expressions Have to use underscore or
--   similar to avoid shadowing <tt>and</tt> and <tt>or</tt> from
--   Prelude/Protolude.
and_ :: Expr Wire f Bool -> Expr Wire f Bool -> Expr Wire f Bool

-- | Binary logic operations on expressions Have to use underscore or
--   similar to avoid shadowing <tt>and</tt> and <tt>or</tt> from
--   Prelude/Protolude.
or_ :: Expr Wire f Bool -> Expr Wire f Bool -> Expr Wire f Bool

-- | Binary logic operations on expressions Have to use underscore or
--   similar to avoid shadowing <tt>and</tt> and <tt>or</tt> from
--   Prelude/Protolude.
xor_ :: Expr Wire f Bool -> Expr Wire f Bool -> Expr Wire f Bool

-- | Negate expression
not_ :: Expr Wire f Bool -> Expr Wire f Bool

-- | Compare two expressions
eq :: Expr Wire f f -> Expr Wire f f -> Expr Wire f Bool

-- | Convert wire to expression
deref :: Wire -> Expr Wire f f

-- | Return compilation of expression into an intermediate wire
e :: Num f => Expr Wire f f -> ExprM f Wire

-- | Conditional statement on expressions
cond :: Expr Wire f Bool -> Expr Wire f ty -> Expr Wire f ty -> Expr Wire f ty

-- | Return compilation of expression into an output wire
ret :: Num f => Expr Wire f f -> ExprM f Wire
input :: ExprM f Wire

module Circuit

module Fresh
fresh :: Fresh Int
evalFresh :: Fresh a -> a
type Fresh a = FreshT Identity a
type FreshT m a = StateT Int m a


-- | Definitions of quadratic arithmetic programs, along with their
--   assignment verification functions and the translations from single
--   multiplication- or equality-gates into QAPs and arithmetic circuits
--   into QAPs.
module QAP

-- | The sets of polynomials/constants as they occur in QAPs, grouped into
--   their constant, input, output and intermediate parts.
data QapSet f
QapSet :: f -> Map Int f -> Map Int f -> Map Int f -> QapSet f
[qapSetConstant] :: QapSet f -> f
[qapSetInput] :: QapSet f -> Map Int f
[qapSetIntermediate] :: QapSet f -> Map Int f
[qapSetOutput] :: QapSet f -> Map Int f

-- | Quadratic arithmetic program
data QAP f
QAP :: QapSet (VPoly f) -> QapSet (VPoly f) -> QapSet (VPoly f) -> VPoly f -> QAP f
[qapInputsLeft] :: QAP f -> QapSet (VPoly f)
[qapInputsRight] :: QAP f -> QapSet (VPoly f)
[qapOutputs] :: QAP f -> QapSet (VPoly f)
[qapTarget] :: QAP f -> VPoly f

-- | Update the value at the given wire label in the <tt>QapSet</tt>.
--   (Partial function at the moment.)
updateAtWire :: Wire -> a -> QapSet a -> QapSet a

-- | Lookup the value at the given wire label in the <tt>QapSet</tt>.
lookupAtWire :: Wire -> QapSet a -> Maybe a
cnstInpQapSet :: g -> Map Int g -> QapSet g

-- | Sum all the values contained in a QapSet.
sumQapSet :: Monoid g => QapSet g -> g

-- | Sum only over constant and input values
sumQapSetCnstInp :: Monoid g => QapSet g -> g

-- | Sum only over intermediate and output values
sumQapSetMidOut :: Monoid g => QapSet g -> g

-- | Fold over a QapSet with an operation that is assumed to be
--   commutative.
foldQapSet :: (a -> a -> a) -> QapSet a -> a
combineWithDefaults :: (a -> b -> c) -> a -> b -> QapSet a -> QapSet b -> QapSet c
combineInputsWithDefaults :: (a -> b -> c) -> a -> b -> QapSet a -> QapSet b -> QapSet c
combineNonInputsWithDefaults :: (a -> b -> c) -> a -> b -> c -> QapSet a -> QapSet b -> QapSet c

-- | Verify whether an assignment of variables is consistent with the given
--   QAP
verifyAssignment :: (Eq f, Field f, Num f) => QAP f -> QapSet f -> Bool

-- | Produce the polynomial witnessing the validity of given assignment
--   against the given QAP. Will return <tt>Nothing</tt> if the assignment
--   is not valid.
--   
--   In Pinocchio's terminology: this produces the h(x) such that p(x) =
--   h(x) * t(x) where t(x) is the target polynomial and p(x) is the left
--   input polynomials times the right input polynomials minus the output
--   polynomials.
verificationWitness :: forall f. (Eq f, Field f, Num f) => QAP f -> QapSet f -> Maybe (VPoly f)
verificationWitnessZk :: (Eq f, Field f, Num f) => f -> f -> f -> QAP f -> QapSet f -> Maybe (VPoly f)

-- | Convert a single multiplication- or equality-gate into a QAP
gateToQAP :: GaloisField k => (Int -> k) -> [k] -> Gate Wire k -> QAP k

-- | Convert a single multiplication gate (with affine circuits for inputs)
--   into a GenQAP
gateToGenQAP :: GaloisField k => [k] -> Gate Wire k -> [GenQAP ((,) k) k]
qapSetToMap :: QapSet g -> Map Int g
initialQapSet :: Num f => Map Int f -> QapSet f

-- | Generate a valid assignment for a single gate.
generateAssignmentGate :: (Bits f, Fractional f) => Gate Wire f -> Map Int f -> QapSet f
generateAssignment :: forall f. (Bits f, Fractional f) => ArithCircuit f -> Map Int f -> QapSet f

-- | Add zeroes for those roots that are missing, to prevent the values in
--   the GenQAP to be too sparse. (We can be sparse in wire values, but not
--   in values at roots, otherwise the interpolation step is incorrect.)
addMissingZeroes :: forall f. (Ord f, Num f) => [f] -> GenQAP (Map f) f -> GenQAP (Map f) f

-- | Convert an arithmetic circuit into a GenQAP: perform every step of the
--   QAP translation except the final interpolation step.
arithCircuitToGenQAP :: GaloisField k => [[k]] -> ArithCircuit k -> GenQAP (Map k) k

-- | Convert an arithmetic circuit into a QAP
arithCircuitToQAP :: GaloisField k => [[k]] -> ArithCircuit k -> QAP k

-- | Convert an arithmetic circuit into a QAP
arithCircuitToQAPFFT :: GaloisField k => (Int -> k) -> [[k]] -> ArithCircuit k -> QAP k

-- | For the left input<i>right input</i>output polynomials: turn list of
--   coordinates into a polynomial that interpolates the coordinates. For
--   the target polynomial: define it as the product of all monics t_g(x)
--   := x - r_g where r_g is the root corresponding to the gate g.
--   
--   Naive construction of polynomials using Lagrange interpolation This
--   has terrible complexity at the moment. Use the FFT-based approach if
--   possible.
createPolynomials :: forall k. GaloisField k => GenQAP (Map k) k -> QAP k

-- | Create polynomials using FFT-based polynomial operations instead of
--   naive.
createPolynomialsFFT :: GaloisField k => (Int -> k) -> GenQAP (Map k) k -> QAP k
instance Data.Aeson.Types.FromJSON.FromJSON (p f) => Data.Aeson.Types.FromJSON.FromJSON (QAP.GenQAP p f)
instance Data.Aeson.Types.ToJSON.ToJSON (p f) => Data.Aeson.Types.ToJSON.ToJSON (QAP.GenQAP p f)
instance Control.DeepSeq.NFData (p f) => Control.DeepSeq.NFData (QAP.GenQAP p f)
instance GHC.Generics.Generic (QAP.GenQAP p f)
instance GHC.Classes.Eq (p f) => GHC.Classes.Eq (QAP.GenQAP p f)
instance GHC.Show.Show (p f) => GHC.Show.Show (QAP.GenQAP p f)
instance (Data.Aeson.Types.FromJSON.FromJSON f, GHC.Generics.Generic f, GHC.Classes.Eq f, GHC.Num.Num f) => Data.Aeson.Types.FromJSON.FromJSON (QAP.QAP f)
instance (GHC.Generics.Generic f, Data.Aeson.Types.ToJSON.ToJSON f) => Data.Aeson.Types.ToJSON.ToJSON (QAP.QAP f)
instance Control.DeepSeq.NFData f => Control.DeepSeq.NFData (QAP.QAP f)
instance GHC.Generics.Generic (QAP.QAP f)
instance GHC.Classes.Eq f => GHC.Classes.Eq (QAP.QAP f)
instance GHC.Show.Show f => GHC.Show.Show (QAP.QAP f)
instance Data.Aeson.Types.FromJSON.FromJSON f => Data.Aeson.Types.FromJSON.FromJSON (QAP.QapSet f)
instance Data.Aeson.Types.ToJSON.ToJSON f => Data.Aeson.Types.ToJSON.ToJSON (QAP.QapSet f)
instance Control.DeepSeq.NFData f => Control.DeepSeq.NFData (QAP.QapSet f)
instance GHC.Generics.Generic (QAP.QapSet f)
instance Data.Foldable.Foldable QAP.QapSet
instance GHC.Base.Functor QAP.QapSet
instance GHC.Classes.Eq f => GHC.Classes.Eq (QAP.QapSet f)
instance GHC.Show.Show f => GHC.Show.Show (QAP.QapSet f)
instance (Text.PrettyPrint.Leijen.Text.Pretty f, Text.PrettyPrint.Leijen.Text.Pretty (p f)) => Text.PrettyPrint.Leijen.Text.Pretty (QAP.GenQAP p f)
instance GHC.Base.Functor p => GHC.Base.Functor (QAP.GenQAP p)
instance (GHC.Classes.Eq f, GHC.Num.Num f, Text.PrettyPrint.Leijen.Text.Pretty f, GHC.Show.Show f) => Text.PrettyPrint.Leijen.Text.Pretty (QAP.QAP f)
instance Text.PrettyPrint.Leijen.Text.Pretty f => Text.PrettyPrint.Leijen.Text.Pretty (QAP.QapSet f)
instance (Data.Aeson.Types.ToJSON.ToJSON f, GHC.Generics.Generic f) => Data.Aeson.Types.ToJSON.ToJSON (Data.Poly.Internal.Dense.VPoly f)
instance (Data.Aeson.Types.FromJSON.FromJSON f, GHC.Generics.Generic f, GHC.Classes.Eq f, GHC.Num.Num f) => Data.Aeson.Types.FromJSON.FromJSON (Data.Poly.Internal.Dense.VPoly f)
instance Data.Aeson.Types.ToJSON.ToJSON (Data.Field.Galois.Prime.Prime n)
instance Data.Aeson.Types.FromJSON.FromJSON (Data.Field.Galois.Prime.Prime n)
instance Text.PrettyPrint.Leijen.Text.Pretty (GHC.Real.Ratio GHC.Integer.Type.Integer)