# Aztec's kernel circuit and client-side IVC

## Notation

In Protogalaxy, the symbols $(\phi; \omega)$ refer to, respectively, a committed transcript and transcript of a special-sound-protocol relation. In barretenberg this is defined via the `ProverInstance` class.
The symbols $((\phi, \beta, e); \omega)$ refer to the committed transcript and transcript of a randomized relation $\mathcal{R}_{rand}$. N.B. in barretenberg this is referred to via a "relaxed instance" and reuses the `ProverInstance` class.

The Aztec architecture has two relations, $\mathcal{R}_{rand}$ (from the Protogalaxy paper) and $\mathcal{R}_{honk}$. The $\mathcal{R}_{honk}$ relation can be modelled as a committed special sound protocol as defined in the Protogalaxy paper.

We can abuse notation and split the committed transcript $\phi_x$ for $\mathcal{R}_{honk}$ into two components: $\phi^{precomputed}_{x}$ and $\phi^{witness}_x$. The commitments to precomputed selector polynomials for a given Honk circuit are represented by $\phi^{precomputed}_{circuit}$. The commitments to wire polynomials, as well as challenges and all other Prover messages in the Honk protocol, are represented by $\phi_{witness}$.

i.e. for a fixed circuit, $\phi^{precomputed}_{circuit}$ will not change, but $\phi_{witness}$ will be different for every proof.

## Kernel circuit architecture

The Aztec kernel circuit takes in the following via public inputs:

- An input accumulator committed transcript $(\phi, \beta, e)$ (n.b. in bberg this is a `VerifierInstance`)
- An output accumulator committed transcript $(\phi^*, \beta^*, e^*)$

The following are present via _private_ inputs:

- An input kernel committed transcript $\phi_{kernel}$
- An input contract function committed transcript $\phi_{func}$

We require the Prover has knowledge of the full transcripts $\omega, \omega^*, \omega_{kernel}, \omega_{func}$.

We wish to establish the following:

$( (\phi, \beta, e); \omega ) \in \mathcal{R}_{rand}$
$( (\phi^*, \beta^*, e^*); \omega^* ) \in \mathcal{R}_{rand}$
$( \phi_{kernel}; \omega_{kernal} ) \in \mathcal{R}_{honk}$
$( \phi_{func}; \omega_{func} ) \in \mathcal{R}_{honk}$

In addition to the above, the following data structures are present on the public inputs of the kernel circuit:

- A function circuit tree root $r_{func}$
- An input "function call stack" $g_{in}$
- An output "function call stack" $g_{out}$
- A "step counter" variable $count$ that tracks the IVC depth
- $h_{kernel}$: a hash of the instance component of $\phi_{kernel}$

The function circuit tree root $r_{func}$ is the root of an append-only Merkle tree, where every leaf contains the hash of $\phi^{precomputed}_{func}$ - the precompute component of an Aztec smart contract function.

The "function call stack" objects are a set of field elements that describe a fixed-size list of functions that need to be executed in order to process the user transaction.

Of relevance to this document is that every function call stack element contains the following:

1. A committed instance $\phi^{precomputed}_{func}$
2. An $index$ field element that describes the leaf index of $H(\phi^{precomputed}_{func})$, in $r_{func}$

## Kernel Circuit Logic

We want to achieve the following outcomes:

1. Validate that $\phi^*$ is the result of folding $\phi_{func}, \phi_{kernel}$ into $\phi$
2. Validate that $\phi_{func}$ is a valid Aztec contract function circuit
3. Consistency checks between the current IVC state and the previous IVC state present in $\phi_{kernel}$'s public inputs
4. Validate the IVC step count is consistent (i.e. if previous IVC iteration had step count of $i$, the current IVC step count is $i+1$)
5. Validate the instance commitment to $\phi_{kernel}$ is consistent with previous instance commitments to $\phi_{kernel}$ used at previous IVC steps

Note: item 5 is due to the fact that we cannot hardcode the kernel circuit instance commitment into the kernel circuit constraints - circular dependency!

The kernel circuit logic evaluates the following steps:

1. Pop the front entry from $g_{in}$ to obtain $(\phi^{precomputed}_{func}, index)$.
2. Validate that $\phi^{precomputed}_{func}$ is the instance component of $\phi_{func}$ present in private inputs
3. Via a hash path presented via private inputs, validate $\phi^{precomputed}_{func} \in r_{func}$ at position $index$
4. Validate that $h_{kernel}$ is a hash of the instance component of $\phi_{kernel}$
5. Up to 4 additional function calls may be described by the public inputs of $\phi_{func}$, according to a fixed ABI. Define these extra function calls via $g_{new}$
6. Validate that $g_{out} = g_{in}.pop().concat(g_{new})$

IF $count = 0$:

1. Validate that $\phi$ is a committed transcript to an _empty_ accumulator
2. Run the protogalaxy folding verifier to validate that $protogalaxy(( \phi, \beta, e ), (\phi_{func}); \omega, (\omega_{func}))$ returns $((\phi^*, \beta^*, e^*); \omega^* )$

IF $count > 0$:

1. Run the protogalaxy folding verifier to validate that $protogalaxy(( \phi, \beta, e ), (\phi_{func}, \phi_{kernel})); \omega, (\omega_{func}, \omega_{kernel})$ returns $((\phi^*, \beta^*, e^*); \omega^* )$

2. From the public inputs of $\phi_{kernel}$, validate that $\phi_{kernel}.count = count - 1$
3. From the public inputs of $\phi_{kernel}$, validate that $\phi_{kernel}.h_{kernel} = h_{kernel}$
4. From the public inputs of $\phi_{kernel}$, validate that $r_{func} = \phi_{kernel}.r_{func}$
5. From the public inputs of $\phi_{kernel}$, validate that $\phi_{kernel}.g_{out} = g_{in}$

## Completing the IVC: "Seal" Circuit

A user transaction is considered executed when the user produces a kernel instance where $g_{out}$ is empty (i.e. no additional functions to execute).

This kernel circuit instance exposes information on its public inputs that we wish to hide from observers. For example, the differences between the input and output function call stacks leaks information about what function is called.

A final IVC step is enacted via the use of a new, "seal" circuit.

The final user instance $(\phi_{kernel}; \omega_{kernel})$ will contain, on its public inputs, the final output accumulator $((\phi^*, \beta^*, e^*); \omega^*)$.

To complete the IVC, we must fold $(\phi_{kernel}; \omega_{kernel})$ into $(\phi^*, \beta^*, e^*); \omega^*)$, producing a final accumulator instance $((\phi_{final}, \beta_{final}, e_{final}); \omega_{final})$.

**Public inputs of the seal circuit**

- Final accumulator committed transcript $(\phi^*, \beta^*, e^*)$

**Private inputs of the seal circuit**

- Committed transcript $\phi_{kernel}$

The seal circuit logic evaluates the following steps:

1. From the public inputs of $\phi_{kernel}$, validate that $\phi_{kernel}.g_{out}$ has a size of 0
2. From the public inputs of $\phi_{kernel}$, validate that $\phi_{kernel}.r_{func}$ is a valid root of the function circuits tree (i.e. the kernel circuit tracks a merkle tree of valid function circuit tree roots: $r_{roots}$, and a membership check of $r_{func} \in r_{roots}$ is satisfied)
3. Validate that the instance component of $\phi_{kernel}$ matches the kernel circuit as defined by the protocol
4. Validate that $\phi_{kernel}.h_{kernel}$ is a valid hash of the instance component of $\phi_{kernel}$
5. Extract $(\phi^*, \beta^*, e^*)$ from the public inputs of $\phi_{kernel}$.
6. Run the protogalaxy folding verifier to validate that$protogalaxy(( \phi^*, \beta^*, e^* ), (\phi_{kernel}); \omega^*, (\omega_{kernel}))$ returns $((\phi^{**}, \beta^{**}, e^{**}); \omega^{**} )$ (todo: clean up notation here)

## Validating the IVC: Rollup Circuit Logic

The Rollup circuit will validate the correctness of the IVC, given an instance of $(\phi_{seal}; \omega_{seal})$.

The final user instance $(\phi_{seal}; \omega_{seal})$ will contain, on its public inputs, the accumulator $((\phi^*, \beta^*, e^*); \omega^*)$.

To complete the IVC, we must fold $(\phi_{seal}; \omega_{seal})$ into $(\phi^*, \beta^*, e^*); \omega^*)$, producing a final accumulator instance $((\phi_{final}, \beta_{final}, e_{final}); \omega_{final})$. Finally a Decider verifier must validate a proof of correctness that $(\phi_{final}; \omega_{final} ) \in \mathcal{R}_{rand}$

**Public inputs of the rollup circuit**

- Committed transcript $\phi_{seal}$
- Final accumulator committed transcript $(\phi_{final}, \beta_{final}, e_{final})$
- Decider proof $\pi_{decider}$ that proves $((\phi_{final}, \beta_{final}, e_{final}); \omega_{final} ) \in \mathcal{R}_{rand}$

The rollup circuit logic evaluates the following steps:

1. Validate the instance component $\phi_{seal}$ matches hardcoded commitments to the seal circuit.
3. Extract $(\phi^*, \beta^*, e^*)$ from the public inputs of $\phi_{seal}$.
4. Run the protogalaxy folding verifier to validate that$protogalaxy(( \phi^*, \beta^*, e^* ), (\phi_{seal}); \omega^*, (\omega_{seal}))$ returns $((\phi_{final}, \beta_{final}, e_{final}); \omega_{final} )$
5. Run the protogalaxy decider verifier to validate that $((\phi_{final}, \beta_{final}, e_{final}); \omega_{final}) \in \mathcal{R}_{rand}$, using $\pi_{decider}$

# IVC scheme visualised


# Zero-knowledge requirements

Assuming Honk is honest-verifier zero-knowledge, we need to ensure that knowledge of any $\phi_{func}$ committed instance cannot be extracted from the $\phi_{kernel}$ instance passed to the rollup circuit, or the accumulator instance $(\phi^*, \beta^*, e^*)$