# Trinity Proving System Research

This note summarizes the **arbitrage between different proving system options** for the **Trinity ZK Commitment** scheme.

Currently, Trinity is implemented using **Halo2**, but any ZK proving system using **KZG** as its polynomial commitment scheme (PCS) could be adapted. The main target for migration is **Aztec Noir with UltraPLONK**, and this note explains why, as well as alternatives to improve developer experience and performance.

---

## Why Target Noir + UltraPLONK?

* **Noir** has rapidly gained traction in the developer community for circuit development, offering:

* A growing standard library (`std`) and precompiled components.
* Fast Zk prover.
* Strong tooling and a smooth DevX for circuit writing.
* Performs well on **in-SNARKs ECC operations**.

Noir **Barretenberg (bb)** backend offers two major circuit builders:

---

## Barretenberg Circuit Builders: Standard vs. Ultra

### 🛠️ StandardCircuitBuilder (`standard_circuit_builder.cpp`)

* **Implements:** Standard PLONK.
* **Witness Columns:** 3 → `w_l`, `w_r`, `w_o` (left, right, output).
* **Selectors:**
* `q_m`: mul, `q_1`: left, `q_2`: right, `q_3`: output, `q_c`: constant.
* **Gate Equation:**
$$
q_m \cdot w_l \cdot w_r + q_1 \cdot w_l + q_2 \cdot w_r + q_3 \cdot w_o + q_c = 0
$$
* **Key APIs:**
* `create_add_gate()`, `create_mul_gate()`, `create_poly_gate()`, `create_bool_gate()`.
* **Adding Custom Advice (EWE bitvector):**
* Add an extra `w_4`.
* Add a custom selector `q_ewe`.
* Create `create_ewe_constraint()` and extend the main gate identity.
* Update prover/verification logic accordingly.

While we know Ultra is a significant breakthrough in terms of ZK performance, it’s not clear how Standard PLONK with `bb` performs against Halo2.

---

### 🚀 UltraCircuitBuilder (`ultra_circuit_builder.cpp`)

* **Implements:** UltraPLONK / UltraHonk.
* **Witness Columns:** 4 → `w_1`, `w_2`, `w_3`, `w_4` (more flexibility).
* **Selectors:** Extended set:
* Arithmetic: `q_m`, `q_c`, `q_1–q_4`, `q_arith`.
* ECC: `q_elliptic`.
* Auxiliary: `q_aux`.
* Lookup system: `q_lookup_type`, plus table/sorted list selectors.
* **Key APIs:**
* `create_add_gate()`, `create_mul_gate()`, `create_big_add_gate()`, `create_ecc_add_gate()`, `create_range_constraint()`, lookup setup.
* **Adding Custom Advice (EWE bitvector):**

**Option 1**: use the 4th witness column for Trinity bitvector:

* Reuse `w_4`.
* Add `q_ewe` selector.
* Create `create_ewe_constraint()` function.
* Modify UltraPLONK identity and prover/verifier logic.

Cons: In the actual version the 4th column is used for lookups, logical gates and other optimisations. Using it for another usage will result in a loss of features and will defeat the purpose of switching to Ultra.

**Option 2**: Add an extra (5th) column for Trinity bitvector:

* Instantiate `w_5`.
* Add `q_ewe` selector.

Cons: This might be a large refactor of the `bb` codebase, as the current logic is handled with 4 columns, adding a new one might introduce bugs and new engineering problems to solve.

**Summary:** Ultra is significantly more flexible and powerful, supporting advanced primitives like lookups and ECC natively—but adding columns or deeply modifying the circuit often requires nontrivial changes across the prover, verifier, and circuit APIs. While there are options, the scope of work for both solutions is quite large. Another point to take into consideration is the fact that this might require a fork and maintaining a whole copy of the `aztec-packages`.

---

## ⚡ Alternative Path: Noir + Halo2 Backend

One alternative is **keeping Halo2 as the backend** while using Noir as the frontend, taking advantage of:

* **DevX:** Noir’s expressive frontend for circuit writing.
* **Backend:** Halo2’s modular and well-documented backend.

Notably:

* Instantiating a custom advice column in Halo2 is *much* simpler:

  let advice_col = meta.unblinded_advice_column();

* Avoiding Barretenberg avoids touching complex C++ internals.

---

## 🚀 Performance Improvements in Halo2

To address Trinity Halo2’s current known performance bottlenecks:

* Focus on optimizing **multi-openings** (currently \~73% of evaluator time).
* Remove the **universal trusted setup** from `setup()`. Instead relly on one main `srs` for the protocol.
* Integrate **Fast Amortized KZG Proofs**
→ Reference: [Fast KZG Proofs HackMD](https://hackmd.io/@brech1/fk).
* Consider switching to **Axiom’s Halo2 fork**, which already implements:
* Faster `multiopen` via SHPLONK:
[Axiom Halo2 multiopen prover](https://github.com/axiom-crypto/halo2/blob/4e584896b62c981ec7c7dced4a9ca95b82306550/halo2_proofs/src/poly/kzg/multiopen/shplonk/prover.rs#L110).

---

### ⏱ Halo2 Raw Flow Benchmark (MacBook Pro M1, 16GB)

Element preparation:                  121.584µs
KZG commitment + proof:               63.2215ms
Polynomial conversion:                197.208µs
Domain point computation:             814.667µs
Openings at points (multiopen):      173.350417ms
LaconicOTRecv::new:                  237.785083ms

**Observation:** Multi-opening dominates runtime-- **~73% of evaluator's setup time** → optimizing this step will bring a good speedup.

---

## ⚖️ Arbitrage Summary

| Option | DevX | Performance | Complexity to Add Column |
| ------------------------------ | ---- | --------------------------- | ------------------------- |
| Noir + UltraPLONK (bb backend) | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | High (large C++ refactor) |
| Noir + Halo2 backend | ⭐⭐⭐⭐ | ⭐⭐ → ⭐⭐⭐ with optimizations | Low (simple Rust patch) |
| Keep Halo2 + optimize | ⭐⭐ | ⭐⭐⭐ after KZG optimizations | Low |

---

### Final Notes

* While Noir + UltraPLONK is the most “future-proof” in terms of ecosystem, integrating EWE will **likely require major Barretenberg refactoring**.
* Noir + Halo2 backend may offer the **best tradeoff** between DevX, performance, and integration cost.
* Regardless of choice, a KZG performance improvement path should be prioritized.