ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Documentation

data ArithmeticCircuit a p i o

Arithmetic circuit in the form of a system of polynomial constraints.

Constructors

ArithmeticCircuit

Fields

• acSystem :: Map ByteString (Constraint a i)

  The system of polynomial constraints

• acRange :: MonoidalMap a (Set (SysVar i))

  The range constraints [0, a] for the selected variables

• acWitness :: Map ByteString (CircuitWitness a p i)

  The witness generation functions

• acFold :: Map ByteString (CircuitFold a (Var a i) (CircuitWitness a p i))

  The set of folding operations

• acOutput :: o (Var a i)

  The output variables

Instances

(Ord (Rep i), Ord a) => HApplicative (ArithmeticCircuit a p i :: (Type -> Type) -> Type)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

hpure :: (forall (a0 :: k). f a0) -> ArithmeticCircuit a p i f

hunit :: ArithmeticCircuit a p i U1

hap :: forall (f :: k -> Type) (g :: k -> Type). ArithmeticCircuit a p i (Transform f g) -> ArithmeticCircuit a p i f -> ArithmeticCircuit a p i g

hliftA2 :: (forall (a0 :: k). f a0 -> g a0 -> h a0) -> ArithmeticCircuit a p i f -> ArithmeticCircuit a p i g -> ArithmeticCircuit a p i h

hpair :: forall (f :: k -> Type) (g :: k -> Type). ArithmeticCircuit a p i f -> ArithmeticCircuit a p i g -> ArithmeticCircuit a p i (f :*: g)

HFunctor (ArithmeticCircuit a p i :: (Type -> Type) -> Type)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

hmap :: (forall (a0 :: k). f a0 -> g a0) -> ArithmeticCircuit a p i f -> ArithmeticCircuit a p i g

(Ord (Rep i), Ord a) => Package (ArithmeticCircuit a p i :: (Type -> Type) -> Type)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

unpack :: forall f (g :: k1 -> Type). Functor f => ArithmeticCircuit a p i (f :.: g) -> f (ArithmeticCircuit a p i g)

unpackWith :: Functor f => (forall (a0 :: k1). h a0 -> f (g a0)) -> ArithmeticCircuit a p i h -> f (ArithmeticCircuit a p i g)

pack :: forall f (g :: k1 -> Type). (Foldable f, Functor f) => f (ArithmeticCircuit a p i g) -> ArithmeticCircuit a p i (f :.: g)

packWith :: (Foldable f, Functor f) => (forall (a0 :: k1). f (g a0) -> h a0) -> f (ArithmeticCircuit a p i g) -> ArithmeticCircuit a p i h

(Arithmetic a, Binary a, Binary (Rep p), Binary (Rep i), Ord (Rep i), NFData (Rep i)) => Symbolic (ArithmeticCircuit a p i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Associated Types

type BaseField (ArithmeticCircuit a p i)

type WitnessField (ArithmeticCircuit a p i)

Methods

witnessF :: Functor f => ArithmeticCircuit a p i f -> f (WitnessField (ArithmeticCircuit a p i))

fromCircuitF :: forall (f :: Type -> Type) (g :: Type -> Type). ArithmeticCircuit a p i f -> CircuitFun '[f] g (ArithmeticCircuit a p i) -> ArithmeticCircuit a p i g

sanityF :: BaseField (ArithmeticCircuit a p i) ~ a0 => ArithmeticCircuit a p i f -> (f a0 -> g a0) -> (ArithmeticCircuit a p i f -> ArithmeticCircuit a p i g) -> ArithmeticCircuit a p i g

(Arithmetic a, Arbitrary a, Binary a, Binary (Rep p), Arbitrary (Rep i), Binary (Rep i), Ord (Rep i), NFData (Rep i), Representable i, Foldable i) => Arbitrary (ArithmeticCircuit a p i Par1)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Instance

Methods

arbitrary :: Gen (ArithmeticCircuit a p i Par1)

shrink :: ArithmeticCircuit a p i Par1 -> [ArithmeticCircuit a p i Par1]

(Arithmetic a, Arbitrary a, Binary a, Binary (Rep p), Arbitrary (Rep i), Binary (Rep i), Ord (Rep i), NFData (Rep i), Representable i, Foldable i, KnownNat l) => Arbitrary (ArithmeticCircuit a p i (Vector l))

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Instance

Methods

arbitrary :: Gen (ArithmeticCircuit a p i (Vector l))

shrink :: ArithmeticCircuit a p i (Vector l) -> [ArithmeticCircuit a p i (Vector l)]

(FromJSON a, FromJSON (o (Var a i)), ToJSONKey (Var a i), FromJSONKey a, Ord a, Ord (Rep i), FromJSON (Rep i)) => FromJSON (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Instance

Methods

parseJSON :: Value -> Parser (ArithmeticCircuit a p i o)

parseJSONList :: Value -> Parser [ArithmeticCircuit a p i o]

(ToJSON a, ToJSON (o (Var a i)), ToJSONKey a, FromJSONKey (Var a i), ToJSON (Rep i)) => ToJSON (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Instance

Methods

toJSON :: ArithmeticCircuit a p i o -> Value

toEncoding :: ArithmeticCircuit a p i o -> Encoding

toJSONList :: [ArithmeticCircuit a p i o] -> Value

toEncodingList :: [ArithmeticCircuit a p i o] -> Encoding

(Ord a, Ord (Rep i), o ~ (U1 :: Type -> Type)) => Monoid (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

mempty :: ArithmeticCircuit a p i o

mappend :: ArithmeticCircuit a p i o -> ArithmeticCircuit a p i o -> ArithmeticCircuit a p i o

mconcat :: [ArithmeticCircuit a p i o] -> ArithmeticCircuit a p i o

(Ord a, Ord (Rep i), o ~ (U1 :: Type -> Type)) => Semigroup (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

(<>) :: ArithmeticCircuit a p i o -> ArithmeticCircuit a p i o -> ArithmeticCircuit a p i o

sconcat :: NonEmpty (ArithmeticCircuit a p i o) -> ArithmeticCircuit a p i o

stimes :: Integral b => b -> ArithmeticCircuit a p i o -> ArithmeticCircuit a p i o

Generic (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Associated Types

type Rep (ArithmeticCircuit a p i o) :: Type -> Type

Methods

from :: ArithmeticCircuit a p i o -> Rep (ArithmeticCircuit a p i o) x

to :: Rep (ArithmeticCircuit a p i o) x -> ArithmeticCircuit a p i o

(Show a, Show (o (Var a i)), Show (Var a i), Show (Rep i), Ord (Rep i)) => Show (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Instance

Methods

showsPrec :: Int -> ArithmeticCircuit a p i o -> ShowS

show :: ArithmeticCircuit a p i o -> String

showList :: [ArithmeticCircuit a p i o] -> ShowS

(NFData a, NFData1 o, NFData (Rep i)) => NFData (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

rnf :: ArithmeticCircuit a p i o -> ()

type BaseField (ArithmeticCircuit a p i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

type BaseField (ArithmeticCircuit a p i) = a

type WitnessField (ArithmeticCircuit a p i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

type WitnessField (ArithmeticCircuit a p i) = WitnessF a (WitVar p i)

type Rep (ArithmeticCircuit a p i o)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

type Rep (ArithmeticCircuit a p i o)

data CircuitFold a v w

Constructors

forall s j.(Functor s, NFData1 s, Binary (Rep s), NFData (Rep s), Ord (Rep s), Functor j, Binary (Rep j), NFData (Rep j), Ord (Rep j)) => CircuitFold

Fields

• foldStep :: ArithmeticCircuit a U1 (j :*: s) s
• foldSeed :: s v
• foldStream :: Infinite (j w)
• foldCount :: v
• foldResult :: s v

Instances

Bifunctor (CircuitFold a)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

bimap :: (a0 -> b) -> (c -> d) -> CircuitFold a a0 c -> CircuitFold a b d

first :: (a0 -> b) -> CircuitFold a a0 c -> CircuitFold a b c

second :: (b -> c) -> CircuitFold a a0 b -> CircuitFold a a0 c

Functor (CircuitFold a v)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

fmap :: (a0 -> b) -> CircuitFold a v a0 -> CircuitFold a v b

(<$) :: a0 -> CircuitFold a v b -> CircuitFold a v a0

(NFData a, NFData v) => NFData (CircuitFold a v w)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Internal

Methods

rnf :: CircuitFold a v w -> ()

data Var a i

Constructors

LinVar a (SysVar i) a

ConstVar a

Instances

FromConstant a (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

fromConstant :: a -> Var a i

(FromJSON (Rep i), FromJSON a) => FromJSON (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

parseJSON :: Value -> Parser (Var a i)

parseJSONList :: Value -> Parser [Var a i]

(FromJSON (Rep i), FromJSON a) => FromJSONKey (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

fromJSONKey :: FromJSONKeyFunction (Var a i)

fromJSONKeyList :: FromJSONKeyFunction [Var a i]

(ToJSON (Rep i), ToJSON a) => ToJSON (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

toJSON :: Var a i -> Value

toEncoding :: Var a i -> Encoding

toJSONList :: [Var a i] -> Value

toEncodingList :: [Var a i] -> Encoding

(ToJSON (Rep i), ToJSON a) => ToJSONKey (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

toJSONKey :: ToJSONKeyFunction (Var a i)

toJSONKeyList :: ToJSONKeyFunction [Var a i]

Generic (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Associated Types

type Rep (Var a i) :: Type -> Type

Methods

from :: Var a i -> Rep (Var a i) x

to :: Rep (Var a i) x -> Var a i

(Show (Rep i), Show a) => Show (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

showsPrec :: Int -> Var a i -> ShowS

show :: Var a i -> String

showList :: [Var a i] -> ShowS

(NFData (Rep i), NFData a) => NFData (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

rnf :: Var a i -> ()

(Eq (Rep i), Eq a) => Eq (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

(==) :: Var a i -> Var a i -> Bool

(/=) :: Var a i -> Var a i -> Bool

(Ord (Rep i), Ord a) => Ord (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

compare :: Var a i -> Var a i -> Ordering

(<) :: Var a i -> Var a i -> Bool

(<=) :: Var a i -> Var a i -> Bool

(>) :: Var a i -> Var a i -> Bool

(>=) :: Var a i -> Var a i -> Bool

max :: Var a i -> Var a i -> Var a i

min :: Var a i -> Var a i -> Var a i

type Rep (Var a i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

type Rep (Var a i) = D1 ('MetaData "Var" "ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var" "symbolic-base-0.1.0.0-inplace" 'False) (C1 ('MetaCons "LinVar" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (SysVar i)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))) :+: C1 ('MetaCons "ConstVar" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))

data SysVar i

Constructors

InVar (Rep i)

NewVar ByteString

Instances

FromJSON (Rep i) => FromJSON (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

parseJSON :: Value -> Parser (SysVar i)

parseJSONList :: Value -> Parser [SysVar i]

FromJSON (Rep i) => FromJSONKey (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

fromJSONKey :: FromJSONKeyFunction (SysVar i)

fromJSONKeyList :: FromJSONKeyFunction [SysVar i]

ToJSON (Rep i) => ToJSON (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

toJSON :: SysVar i -> Value

toEncoding :: SysVar i -> Encoding

toJSONList :: [SysVar i] -> Value

toEncodingList :: [SysVar i] -> Encoding

ToJSON (Rep i) => ToJSONKey (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

toJSONKey :: ToJSONKeyFunction (SysVar i)

toJSONKeyList :: ToJSONKeyFunction [SysVar i]

Generic (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Associated Types

type Rep (SysVar i) :: Type -> Type

Methods

from :: SysVar i -> Rep (SysVar i) x

to :: Rep (SysVar i) x -> SysVar i

Show (Rep i) => Show (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

showsPrec :: Int -> SysVar i -> ShowS

show :: SysVar i -> String

showList :: [SysVar i] -> ShowS

NFData (Rep i) => NFData (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

rnf :: SysVar i -> ()

Eq (Rep i) => Eq (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

(==) :: SysVar i -> SysVar i -> Bool

(/=) :: SysVar i -> SysVar i -> Bool

Ord (Rep i) => Ord (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

Methods

compare :: SysVar i -> SysVar i -> Ordering

(<) :: SysVar i -> SysVar i -> Bool

(<=) :: SysVar i -> SysVar i -> Bool

(>) :: SysVar i -> SysVar i -> Bool

(>=) :: SysVar i -> SysVar i -> Bool

max :: SysVar i -> SysVar i -> SysVar i

min :: SysVar i -> SysVar i -> SysVar i

type Rep (SysVar i)

Defined in ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var

type Rep (SysVar i) = D1 ('MetaData "SysVar" "ZkFold.Symbolic.Compiler.ArithmeticCircuit.Var" "symbolic-base-0.1.0.0-inplace" 'False) (C1 ('MetaCons "InVar" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Rep i))) :+: C1 ('MetaCons "NewVar" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 ByteString)))

data WitVar p i

Constructors

WExVar (Rep p)

WSysVar (SysVar i)

type VarField = Zp (2 ^ (32 * 8))

Variables are SHA256 digests (32 bytes)

type Arithmetic a = (ResidueField Natural a, Eq a, Ord a, NFData a)

Field of residues with decidable equality and ordering is called an `arithmetic' field.

type Constraint c i = Poly c (SysVar i) Natural

The type that represents a constraint in the arithmetic circuit.

acInput :: (Representable i, Semiring a) => i (Var a i)

getAllVars :: forall a p i o. (Representable i, Foldable i) => ArithmeticCircuit a p i o -> [SysVar i]

crown :: ArithmeticCircuit a p i g -> f (Var a i) -> ArithmeticCircuit a p i f

hlmap :: (Representable i, Representable j, Ord (Rep j), Functor o) => (forall x. j x -> i x) -> ArithmeticCircuit a p i o -> ArithmeticCircuit a p j o

hpmap :: (Representable p, Representable q) => (forall x. q x -> p x) -> ArithmeticCircuit a p i o -> ArithmeticCircuit a q i o

witnessGenerator :: (Arithmetic a, Representable p, Representable i) => ArithmeticCircuit a p i o -> p a -> i a -> Map ByteString a

eval :: (Arithmetic a, Representable p, Representable i, Functor o) => ArithmeticCircuit a p i o -> p a -> i a -> o a

Evaluates the arithmetic circuit using the supplied input map.

eval1 :: (Arithmetic a, Representable p, Representable i) => ArithmeticCircuit a p i Par1 -> p a -> i a -> a

Evaluates the arithmetic circuit with one output using the supplied input map.

exec :: (Arithmetic a, Functor o) => ArithmeticCircuit a U1 U1 o -> o a

Evaluates the arithmetic circuit with no inputs.

exec1 :: Arithmetic a => ArithmeticCircuit a U1 U1 Par1 -> a

Evaluates the arithmetic circuit with no inputs and one output.

apply :: (Eq a, Field a, Ord (Rep j), Representable i, Functor o) => i a -> ArithmeticCircuit a p (i :*: j) o -> ArithmeticCircuit a p j o

Applies the values of the first couple of inputs to the arithmetic circuit.

indexW :: (Arithmetic a, Representable p, Representable i) => ArithmeticCircuit a p i o -> p a -> i a -> Var a i -> a

witToVar :: forall a p i. (Finite a, Binary a, Binary (Rep p), Binary (Rep i)) => WitnessF a (WitVar p i) -> ByteString

Generates new variable index given a witness for it.

It is a root hash (sha256) of a Merkle tree which is obtained from witness:

1. Due to parametricity, the only operations inside witness are operations from WitnessField interface;

2. Thus witness can be viewed as an AST of a WitnessField "language" where:

   • leafs are fromConstant calls and variables;
   • nodes are algebraic operations;
   • root is the witness value for new variable.
3. To inspect this AST, we instantiate witness with a special inspector type whose WitnessField instances perform inspection.
4. Inspector type used here, MerkleHash, treats AST as a Merkle tree and performs the calculation of hashes for it.
5. Thus the result of running the witness with MerkleHash as a WitnessField is a root hash of a Merkle tree for a witness.