# HONK (Highly Optimized ploNK)

Aztec is a Layer 2 hybrid zk-zk-Rollup blockchain Virtual Machine on Ethereum, designed to enable programmable anonymity, data privacy and confidential contracts, with composable calling semantics; it has private state as the default first-class primitive. Due to its own privacy nature, users generate their zero-knowledge proofs of correctness of private functions execution client-side and run the kernel’s private circuits themselves to recursively verify their private function calls. This proving execution ecosystem is done locally in WebAssembly leaving us a memory limit of 4 GB. On the other hand, the second segment of the protocol is the public state VM where the proof is delegated to the sequencer that executes the public call stack until it is empty, always after finishing the private kernel circuit, generating rigid structures for composable call semantics between or within smart contracts. These types of proofs must be ultra-cheap, small enough (avoid mempool saturation), and recursively friendly.

To achieve these goals, the Aztec team led by Zachary J. Williamson and top-level cryptographers such as Tohru Kohrita and Patrick Towa for scoring some along with other scientists from other research foundations such as Ariel Gabizon (Zeta Function Technologies), Dario Fiore (IMDEA Software) and Liam Eagen (Blockstream Research, Zeta Function Technologies) directly or indirectly build a zero-knowledge SNARK proof system called Honk. The frenetic development of SNARKs in recent years by the scientific community has led them to become increasingly modular, presenting several layers of abstractions. Honk is composed of the following layers: arithmetization, polynomial interactive oracle proof, polynomial commitment scheme, folding scheme and folding accelerator. Other adjacent and complementary schemes necessary for the work of the whole are defined, such as Zeromorph, private kernel circuits, Plonk data bus and look-up tables.

- **ARITHMETIZATION OF ULTRAPLONK CIRCUITS**

This first layer consists of representing a program as algebraic relationships that you are evaluating. It compiles the circuit into a calculation trace and show that it is valid and that the output is zero such that C(x,w)=0.

UltraPlonk is a system made up of Turbo Plonk + lookup tables.

Plonk is the first universal and upgradeable zk-SNARK configuration with low prover runtime (quasilinear in circuit size) and succinct verification (polylogarithmic in circuit size) for general arithmetic circuits (Plonk-ish). PLONK improves prover run time over Sonic is due to “a permutation argument over univariate evaluations on a multiplicative subgroup rather than over coefficients of a bivariate polynomial.

TurboPlonk is Plonk + custom and high degree gates. It uses larger circuits (larger fan-in and fan-out at each gates by committing to an extra column).

UltraPlonk utilizes the "Ultra" circuit arithmetisation. This is a configuration with four wires per-gate, and the following set of gate types: arithmetic gate, elliptic curve point addition/doubling gate, range-check gate, plookup table gate, memory-checking gates and non-native field arithmetic gates.

The system is extended with the following efficiencies: possibility of having hundreds of custom gate equations and Plonk's permutation argument is trivially modified to achieve efficient range checks, “ROM” tables with O(1) read costs, and RAM tables with O(1) write costs. It also uses logarithmic derivative lookup tables.

---

- **POLYNOMIAL INTERACTIVE ORACLE PROOF**

It compiles the previous step (execution trace) into a Polynomial Interactive Oracle Proof (PIOP) which is an interactive protocol between prover and verifier where its gonna validate the correctness of the arithmetization for a given instance. PIOP reduces the claim about your correctness of your cicuit to the claim about some evaluations of committed polynomials.

Multilinear Sumcheck protocol.
It is a protocol that works as follows: given input multilinear polynomials (witness input), and some expression of your polynomials; the algorithm does the sum of the possible evaluation points of your polynomials over some domain and that equation is equal to zero. In other words: Honk performs the polynomial testing via checking, using a sumcheck protocol, that a relation over multilinear polynomials vanishes when summed over a boolean hypercube.

You can use the protocol to check that constrains on Plonk-ish circuits is equal to zero by adding random polynomials and verifying you have linear independence. At the end of the evaluation protocol you will have a claim that your polynomial identity evaluated at a series of random points will be equal to a constant field element and then you can check that with a compatible Polynomial Commitment Scheme (PCS).
Prover works in linear-time because the prover of Sumcheck-based SNARKs does not need to commit to quotient polynomials, composition polynomials and no Fast Fourier Transform (FFTs) is needed.

----

* **KZG**

The KZG polynomial commitment scheme (PCS), introduced by Kate, Zaverucha and Goldberg requires a universal setup and it is instantiated over a pairing-friendly elliptic curve. It allows a prover to compute a commitment to a polynomial, with the properties that this commitment can later be opened at any position. It is called a commitment, because having sent the commitment value (an elliptic curve point) to someone (the verifier), the prover cannot change the polynomial they are working with. They will only be able to provide valid proofs for one polynomial, and if they are trying to cheat, they will either fail to produce a proof or the proof will be rejected by the verifier.

Computing an opening proof of a degree-$n$ polynomial requires scalar multiplications, with a constant proof size and a constant verifier time.

---

* **INNER PRODUCT ARGUMENT**

The IPA polynomial commitment scheme (PCS) has worse asymptotics than KZG but can be instantiated over non-pairing friendly curves.

We utilize the Grumpkin elliptic curve as part of the Goblin Plonk protocol, where we utilize the curve cycle formed between BN254 and Grumpkin to translate expensiven on-native BN254 group operations in a BN254 circuit, into native group operations in a Grumpkin circuit.

To batch-verify multiple opening proofs, we use the technique articulated in the Halo protocol. To compute a proof of a single rollup block, only one linear-time PCS opening proof is verified despite multiple IPA proofs being generated as part of constructing the rollup proof.

----

- **ZEROMORPH**

Zeromorph (Zero-knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments) is a recipe to obtain a multilinear PCS from additive univariate PCS with degree verification protocol.
We want to integrate Sumcheck-based circuit satisfiability testing because Sumcheck is more efficient than Plonk's univariate proving systems. PCS is used to evaluate SumCheck claims. We need a multivariate commitment scheme to make it compatible. So that, if we have a linear relation over multilinear polynomials, we can convert it to a linear relation of univariate polynomials by trivially applying isomorphism. In KZG multilinear PCS, the relation being checked is a linear expression, so we apply isomorphism to evaluate univariate polynomials and the checker checks for equality at a challenge point.
It is quite fast and compatible with zk, perfect for the Aztec netqork.

---

* **PROTOGALAXY**

The Protogalaxy protocol efficiently supports the ability to fold multiple Honk instances (describing different circuits) into the same accumulator. It is a ProtoStar-style multi-instance folding. Protocol workflow: given an input string and a witness string tuple describing a relationship you want to proof, put them together (fold) to create a new random relationship. Instead you have a prover and a verifier, the system is being re-structured and now there is a prover, an incremental verifier which checks the folds and a decider doing the original verification.

It is a critical layer for SNARK improvements because if you are running a verification algorithm with a high cost, you could use folding to fold a large number of protocol instances using IVC, and amortize the cost of the decider at the end of the protocol. A nice property of this scheme is that while the data structure is maintained with a specific structure, any arbitrary number of instances can be added.

The detail explanation by one of its authors Liam Eagen is in the following video: https://www.youtube.com/watch?v=SpkTvRia1EA

The technical explanation of the integration of the Protogalaxy paper with the Aztec architecture is explained in the following URL: https://hackmd.io/h0yTcOHiQWeeTXnxTQhTNQ?view

-----

* **PLONK DATA BUS**

When passing data between successive IVC steps, the canonical method is to do so via public inputs. This adds significant costs to an IVC folding verifier (or recursive verifier when not using a folding scheme). Public inputs must be hashed prior to generating Fiat-Shamir challenges. When this is performed in-circuit, this adds a cost linear in the number of public inputs (with unpleasant constants ~30 constraints per field element).

The Data Bus protocol eliminates this cost by representing cross-step data via succinct commitments instead of raw field elements.

The Plonk Data Bus protocol enables efficient data transfer between two Honk instances within a larger IVC protocol.

---

* **GOBLIN PLONK**

Folding acelerator. It is an iteration of Halo-2's curve cycles to perform recursion along with Sumcheck-based SNARKs, Zeromorph multilinear PCS, and ProtoGalaxy folding scheme. It makes non-native scalar multiplications extremely efficient and economical, specifically operations that are complicated to compute in folding schemes.

The setup is made up of a prover with limited resources to build a client-side zero-knowledge proof for privacy, where you want to perform recursion of arbitrary depth and then you have a public prover with good resources. Specifically, this is the context of the Aztec hybrid zk-rollup.

To make recursion feasible (checking a proof within a proof efficiently) in a SNARK-ECC based system, the circuits will be defined over a curve (F^2q) where the arithmetic operations of the gates will be modulo "p ", to verify a SNARK proof in recursion we need to perform arithmetic gate operations on the field in which the curve is defined "q", that means that "q" is not equal to "p".
Because Goblin Plonk is based on Halo-2 curve cycles, we made the premise that we want to eliminate the costly curve bounce step from that scheme.

**Goblin Plonk Concepts**

Instruction machine. Where complex instructions are written into lookup tables along with function inputs and claimed outputs. Write them down in transcripts to demonstrate the correctness of instructions within a circuit simply by evaluating them. You can create custom wide circuits where you can define complex and non-native functions and have them efficiently verifiable.

Transcript agregation. As prover recurses, we need to efficienctly aggregate incoming transcripts into a single transcript. This is very compatible with Sumcheck-style protocols with multilinear ploynomials. The size of the transcript grows as you recurse linearly but we do not need too much transcript agregations such that polynomial degree is kept lower.

Curve transposition. It consists of proving two commitments to the same set of data (transcripts) over two different elliptic curves (cycle curves) and different prime fields ("p" and "q"). In the scheme, you are recursing repeatedly in some stack where on each layer of recursion you are running a brute force verification algorithm which does not do complex-non native operations ( e.g. elliptic scalar multiplication) by itself, it shows your instruction into a transcript, then it agregates them as recursion continuos until stack is empty. At this final step, you are going to have a polynomial commitment of your transcript agregation which you have to proof the correctnes of your scalar multiplications in a circuit define over your cycle curve where operations are native.

Due to the nature of the verifier which does not know the operations to be performed, it is necessary to construct an NNF VM defined on the main curve (BN254) where non-native field operations are represented by opcodes and other ECC VMs defined on the grumpkin curve with simple arithmetic operations. Curve transposition is the subprotocol used to perform the equivalence of the Grumpkin ECC VM transcripts with the NNF main VM.

Eventual structure: Goblin Plonk recursion for 100 cycles (fixed depth), then recurses the 4 output proofs of the above system using Halo2 cycle curves, and then applies a generic accumulation scheme without a linear growth term like the folding scheme of ProtoGalaxy for efficient amortization.

Transcript will grow linearly at each recursion layer but the size of the transcript is much smaller than the degrees of the polynomials you are committing for your circuit assuming the operations that are been simulating are expensive.

Estimated costs: performing 1 non-native scalar multiplication means using Goblin Plonk to perform 1 native scalar multiplication plus 5 non-native field operations.

---

* **CQ (IS NOT USED)**

Cq (Cached quotients) is a truly practical protocol to use large tables. It is a lookup protocol and could be easily integrated to a proving system like Aztec's Plonk-ish based arithmetization to save a lot of prover time.

In this system, first you pre-compute a table of legal input/output values of some complex-nasty function (bit-wise operations, range checks, Keccak hash functions) and what you put on the circuit is some randomized combination of the look up table values and the witness with randomness that was chosen by the verifier.

Cq uses pairings so its compatible with the KZG PCS that Aztec uses as a sub-protocol. KZG is additively homomorphic what means that you can do operations in two different orders and it does not change the result. Also, KZG has sort of a partial multiplicative homomorphism, that is extremely powerful; computing the commitment of the quotient much cheaper than the polynomial itself.

In cq protocol the circuit (number of custom gates) is independent of the table size "t". Cq allows efficient recursive aggregation of proofs because verifier does not do pairings with G2 points.

* **Log derivative Lookup**

Look up arguments is a technique used to efficiently prove relations that do not arithmetic well. In this system, first you pre-compute a table of legal input/output values of some complex-nasty function (bitwise operations, range checks, Keccak hash functions) and what you put on the circuit is some randomized combination of the lookup table values and the witness with randomness that was chosen by the verifier. Values on the table could be totally represented as unstructured tables. Look up tables usually works well over computation represented as bits instead of computations over primer fields which is the nature of SNARKs.

Log derivatives lookups use multisets equality to express equivalent mathematical relations, this technique is well-known as common product identity. Applying log derivatives transformation to the functions makes the technique functional.

---

**PRIVATE KERNEL CIRCUIT**

Is a software layer between user code (Noir contracts) and Aztec rollup. It enforces code deployment and execution rules. Manages access to data and other functions from within a contract. Maintains privacy of user transaction, (nested) function arguments and return values, state reads, the function itself. It could expose private information by passing private arguments to a public function. The circuit is used to mainly achieve the composability property: every contract function is its own zero knowledge circuit and follows the same rules of the Kernel circuit. That means functions can do cross-contract function calls.

User generates in the browser (to avoid leaking information) the proofs of correctness of the private (nested) functions called A, B and C and runs the private kernel circuit. Kernel stitches together (nested) function calls (A → B → C), then proofs A, B and C are all verified recursively by the private Kernel circuit. It generates a single private kernel proof of correct execution that represents the execution of the full private call stack. Then, it is submitted to the transaction pool by the Aztec RPC server (ARS) and it will be picked up by the sequencer that executes the public call stack until it is empty, performs UTXO updates, performs nullifier updates and validates oracle states; generating their final kernel proofs. Next, kernel proofs are submitted to provers to be merged incrementally in parallel.

The private Kernel circuit uses recursion to sequentially construct proofs of correct execution of your functions to be efficient. The private circuits A, B and C generate their respective proofs, then proofs are recursively verified sequentially until generating the final snark proof. First iteration is a mock proof because there are no previous proof.

---

* **FUTURE IMPROVEMENTS**

GKR protocol is a SNARK for circuit satisfiability where prover only commits to the circuits input, not intermediate gate values. In the GKR protocol, the verifier only needs to evaluate at a single random point the multilinear-extensions polynomials of “x” and “w” inputs. SumCheck protocol is applied once per circuit layer (circuit evaluation gate by gate) but without using any cryptography on “x”, however you still need to cryptographically commit to “w”.

Structured circuits eliminate the need to commit to “derivable” commmitments. E.g. remove Plonk grand-product polynomial and remove log-derivative inverse polynomial in lookup tables tecnhiques.

Incremental verifier on ProtoGalaxy folding's scheme works on O(log2n) so there is a research to make it O(logn).

---

* **PERFORMANCE TARGET FOR HONK**

Most important components and optimal expectations of the Aztec team:
1. Prover size: <16kb to avoid mempool latency issues and increment tps.
1. Prover runtime: 2^20 Plonk gates <5 seconds with a WASM prover on consumer hardware.
1. Prover Memory: 1GB of RAM maximum.
1. Recursion/folding cost: 8-32 client-side recursive checks, ideally 10-20 ms to prove 1 layer of recursion.


Code implementation:
https://github.com/AztecProtocol/barretenberg/tree/master/cpp/src/barretenberg/honk

Descuento Joven: JV24-71679434A-6JWCB