plonkish-cat

A PLONKish circuit system built on 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:

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:

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:

  4: Const(c)  0 -> 1    out = c

Compilation pipeline

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

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):

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:

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

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():

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

cargo build
cargo test
RUSTFLAGS="-D warnings" cargo clippy

License

MIT