Try   HackMD

High level proposal for roadmap for the Chiquito language

This does not include stuff about new front-ends or back-ends or improvements to the Halo2 backend.

Statuses, refer to the status of the specific spec, not it implementation. Status can be: TODO, DRAFT, PROPOSAL, FINAL.

[FINAL] Constraint builder typing

Constraint struct in the DSL should have a field typing (type is a rust keyword). The value is a enum that should be Unknown, Boolean and AntiBooly.

AntiBooly means that when the text of the predicate is true, it returns 0, another number otherwise.

Queries and expressions when converted to Constraints should have type Unkown.

Constrain builder functions returns a type and can panic if the input must be of certain type.

For example:

  • and -> accepts !AntiBooly and returns Boolean
  • eq -> accepts anything and returns AntiBooly

When adding a constraint with ctx.constr or ctx.transition, it should panic if the constraint is not AntiBooly.

Some cb functions return the type of a parameter, for example, if_next_step(S, C), its type is the type of C.

https://github.com/privacy-scaling-explorations/chiquito/issues/32

[FINAL] Plaff backend

Implement backend that takes our IR and convert it to Plaf format.

We could be tempted to compile our circuit to halo2 and then import that into plaf. But that would create other problems down the line. Plaf should be supported natively as a backend.

Plaf will not support Halo2 imported columns and expressions, hence if in the process of compiling to Plaf any of these are found we should terminate with an error.

In the end we should have a module backend/plaf.rs with a function like chiquito2Halo2 named chiquito2plaf that will return a plaf struct from a (ir::Circuit)[https://github.com/privacy-scaling-explorations/chiquito/blob/main/src/ir.rs#L12] .

https://github.com/privacy-scaling-explorations/chiquito/issues/33

[FINAL] Public signals

Add public signals to circuits.

A new type of signal is created, called public_column.

In the circuit context, a forward signal in the first step instance can be made public.

ctx.expose(forward); // forward is a Queriable

This, should be added to AST and to the IR.

In the AST, we can have a field called

exposed: Vec<ForwardSignal>

In the IR, we can have a field called

exposed: Vec<(Column, i32)> // i32 is the rotation

In Halo2 and Plaf backend, create one single column for the public signal. In both Halo2 and Plaf, it's an instance column.

The Halo2 backend should use constrain_instance to assign the public signal rows.

Before starting investigate: how public signals work on plaf?

[FINAL] Managed padding

In the trace context we can spec the padding step with its parameters:

    ctx.padding(step_type_hander, || step_args );

When doing witness generation, after finishing if there are more rows to fill according to the established height, then the padding step should be added until the circuit is filled.

This is specd in the trace function because step_args could depends on trace_args.

This does not need to be added to the AST or IR as it is included in the trace lambda. It should be included in the witness generation code.

The second parameter is a lambda to allow step_args to be different for each padding step instance, giving more generality.

[TODO] Abstract Gadgets

[TODO] Other Fixed height cell managers

Fixed height cell manager are simpler in terms of calculating their fixed height and hence padding and q_last.

[FINAL] Composition of circuits (SuperCircuit)

A super circuit represents several circuits (SubCirctuis) connected with each other, that are compiled together into one circuit.

What to do with circular dependencies between SubCircuits?

[TODO] Calls to other circuits

A Subcircuit can "call" another circuit, the caller in its witness generation can "call" the other SubCircuit, more than just once.

The calee will receive all the values of the calls in its witness generation.

This way one or more caller SubCircuits can control the witness generation of other calee Subcircuits.

Does it make sense for the call to return a value? Or Lookup is enough?

[FINAL] Lookup abstraction

[TODO] Stats

[TODO] Variable height cell manager

Padding step should be forced to have height 1. That is what make it different from the others.

Later

[TODO] Steps nesting

[TODO] Witness inference

[TODO] Typed signals

[TODO] Reuse of step types in different circuits