# 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**:

| Categorical concept | Circuit meaning |
|---|---|
| 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

| Type | Module | Purpose |
|---|---|---|
| `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
