# plonkish-cat
A PLONKish circuit system built on [comp-cat-rs](https://crates.io/crates/comp-cat-rs)'s categorical infrastructure.
Circuits are morphisms in a free category generated by a graph of primitive gates. Composition is sequential wiring; the tensor product (from the symmetric monoidal structure) is parallel placement. The `compile` function interprets composed circuits into polynomial constraint sets via the universal property of free categories.
## The categorical model
Arithmetic circuits form a **symmetric monoidal category**:
| Object | Wire count (number of field-element wires) |
| Morphism | Gadget: consumes input wires, produces output wires, generates constraints |
| Identity | Pass-through (no constraints) |
| Composition | Sequential wiring: output of one gadget feeds into the next |
| Tensor product | Parallel placement: side-by-side wire bundles |
| Braiding | Wire permutation |
The **free category** on a directed graph of primitive gates gives the circuit DSL. Vertices are wire counts (0, 1, 2, ...); edges are gates (Add, Mul, Const, Bool, Dup). A composed circuit is a **path** in this graph. The `compile` function is the **universal property** in action: a graph morphism (per-gate constraint generation) extending uniquely to a functor on paths.
This design is justified by comp-cat-rs's thesis that every constructive computation in category theory is a Kan extension. The free category is the left Kan extension of the graph inclusion along the forgetful functor from categories to graphs.
## The PLONKish graph
The standard graph ships with three vertices and four edges:
```text
Vertices (wire counts):
0 -> 0 wires (unit object, empty circuit)
1 -> 1 wire (single field element)
2 -> 2 wires (pair of field elements)
Edges (primitive gates):
0: Add 2 -> 1 out = in0 + in1
1: Mul 2 -> 1 out = in0 * in1
2: Bool 1 -> 1 in * (1 - in) = 0; out = in
3: Dup 1 -> 2 copy constraint: out0 = out1 = in
```
Constant gates are added dynamically via `with_const(c)`, since they carry a field element:
```text
4: Const(c) 0 -> 1 out = c
```
## Compilation pipeline
```text
Graph of primitive gates
|
v
Free category (paths = composed circuits)
|
| compile()
v
ConstraintSet<F> (polynomial + copy constraints)
|
| is_satisfied(assignment)
v
bool (all constraints hold?)
```
The `compile` function walks the path edge by edge, threading a `WireAllocator` that assigns fresh wire indices to each gate boundary. Each gate generates constraints referencing its allocated input and output wires. The result is a `ConstraintSet<F>` containing:
- **Polynomial constraints**: expressions over wires that must evaluate to zero.
- **Copy constraints**: pairs of wires that must carry equal values.
## Quick start
```rust
use plonkish_cat::*;
use comp_cat_rs::collapse::free_category::{Edge, Path};
fn main() -> Result<(), Error> {
// Build the standard PLONKish graph.
let graph = PlonkishGraph::<F101>::standard();
// Compose: dup (1 -> 2) then mul (2 -> 1) = squaring circuit.
let dup = Path::singleton(&graph, Edge::new(3))?;
let mul = Path::singleton(&graph, Edge::new(1))?;
let square = dup.compose(mul)?;
// Compile to constraints.
let cs = compile(&graph, &square)?;
// The squaring circuit generates:
// 2 copy constraints (dup: w0 -> w1, w0 -> w2)
// 1 polynomial constraint (mul: w3 - w1*w2 = 0)
assert_eq!(cs.copy_constraints().len(), 2);
assert_eq!(cs.constraints().len(), 1);
Ok(())
}
```
## Example: verifying x^2
Build a squaring circuit (`dup ; mul : 1 -> 1`), compile it, and check satisfaction over F101 (integers mod 101):
```rust
use plonkish_cat::*;
use plonkish_cat::interpret::compile_with_io;
use comp_cat_rs::collapse::free_category::{Edge, Path};
fn main() -> Result<(), Error> {
// Build the circuit: dup then mul.
let graph = PlonkishGraph::<F101>::standard();
let dup = Path::singleton(&graph, Edge::new(3))?;
let mul = Path::singleton(&graph, Edge::new(1))?;
let square = dup.compose(mul)?;
// Compile with I/O info.
let (cs, input, output) = compile_with_io(&graph, &square)?;
// Input is 1 wire, output is 1 wire.
assert_eq!(input.count(), WireCount::new(1));
assert_eq!(output.count(), WireCount::new(1));
// Wire layout after compilation:
// w0: input (x)
// w1, w2: dup outputs (both equal x, via copy constraints)
// w3: mul output (x * x)
// Assign x = 3, so x^2 = 9.
let assignment = |w: Wire| -> Result<F101, Error> {
match w.index() {
0 => Ok(F101::new(3)), // input
1 => Ok(F101::new(3)), // dup output 0
2 => Ok(F101::new(3)), // dup output 1
3 => Ok(F101::new(9)), // mul output (3 * 3)
_ => Err(Error::WireOutOfBounds { wire_index: w.index(), allocated: 4 }),
}
};
assert!(cs.is_satisfied(&assignment)?);
Ok(())
}
```
## Example: constant multiplication
Build a circuit that multiplies an input by 7: `const(7) ; dup_input ; mul`.
In graph terms, this requires composing gates with different arities. Since `Const(7): 0 -> 1` produces a wire and `Mul: 2 -> 1` consumes two, we need to prepare both inputs. One approach: build the constant and the input path separately, then connect them.
For the current version, the simplest encoding uses the standard gates directly:
```rust
use plonkish_cat::*;
use comp_cat_rs::collapse::free_category::{Edge, Path};
fn main() -> Result<(), Error> {
// Add a Const(7) gate to the graph.
let graph = PlonkishGraph::<F101>::standard();
let (graph, const7) = graph.with_const(F101::new(7));
// Const(7): 0 -> 1 produces a wire constrained to 7.
let path = Path::singleton(&graph, const7)?;
let cs = compile(&graph, &path)?;
// w0 must equal 7.
let assignment = |w: Wire| -> Result<F101, Error> {
match w.index() {
0 => Ok(F101::new(7)),
_ => Err(Error::WireOutOfBounds { wire_index: w.index(), allocated: 1 }),
}
};
assert!(cs.is_satisfied(&assignment)?);
Ok(())
}
```
## Key types
| `Field` | `field` | Trait for finite field arithmetic (uses `std::ops` supertraits) |
| `F101` | `field` | Test field: integers mod 101 |
| `Wire` | `wire` | Newtype for wire indices |
| `WireCount` | `wire` | Newtype for wire bundle sizes (category objects) |
| `WireRange` | `wire` | Contiguous block of allocated wires |
| `WireAllocator` | `wire` | Functional state for fresh wire allocation |
| `Expression<F>` | `expr` | Symbolic polynomial AST with operator overloads |
| `Constraint<F>` | `constraint` | Polynomial expression that must equal zero |
| `CopyConstraint` | `constraint` | Pair of wires that must be equal |
| `ConstraintSet<F>` | `constraint` | Collection of constraints; supports `merge` and `is_satisfied` |
| `PrimitiveGate<F>` | `gate` | Add, Mul, Const, Bool, Dup |
| `PlonkishGraph<F>` | `gate` | Directed graph implementing comp-cat-rs `Graph` trait |
| `compile` | `interpret` | Path -> `ConstraintSet<F>` (the compilation pipeline) |
| `compile_with_io` | `interpret` | Same, but also returns input/output `WireRange` |
## Implementing your own field
`Field` requires `Add`, `Sub`, `Mul`, `Neg` (all with `Output = Self`), plus `Clone`, `Eq`, and `Debug`. You provide `zero()`, `one()`, and `inv()`:
```rust
use plonkish_cat::{Field, Error};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct MyField(u64);
impl std::ops::Add for MyField { /* ... */ }
impl std::ops::Sub for MyField { /* ... */ }
impl std::ops::Mul for MyField { /* ... */ }
impl std::ops::Neg for MyField { /* ... */ }
impl Field for MyField {
fn zero() -> Self { MyField(0) }
fn one() -> Self { MyField(1) }
fn inv(&self) -> Result<Self, Error> {
if self.0 == 0 {
Err(Error::DivisionByZero)
} else {
// Your modular inverse here.
todo!()
}
}
}
```
Then use it: `PlonkishGraph::<MyField>::standard()`.
## Connection to comp-cat-rs
plonkish-cat uses the following comp-cat-rs infrastructure:
- **`Graph` trait** (`collapse::free_category`): `PlonkishGraph` implements this, making primitive gates into graph edges and wire counts into vertices.
- **`Path`** (`collapse::free_category`): composed circuits are paths in the free category. `Path::singleton` creates single-gate circuits; `Path::compose` chains them.
- **`Vertex`, `Edge`** (`collapse::free_category`): newtypes indexing into the graph.
- **`FreeCategoryError`**: wrapped by `plonkish_cat::Error` for `?` propagation.
The categorical infrastructure in comp-cat-rs (monoidal categories, natural transformations, spans, pullbacks) provides the foundation for future extensions: parallel circuit composition via the tensor product, backend polymorphism via natural transformations, and lookup arguments via spans.
## Building
```bash
cargo build
cargo test
RUSTFLAGS="-D warnings" cargo clippy
```
## License
MIT