jeong0982 / gkr Goto Github PK

Currently, GKR is used for many schemes to use its fast proving time. It will be helpful if it can provide proving scheme api and circuit construction by itself (cause it is hard to extract arithmetic circuit from circom itself).

Using arkworks-rs/algebra

Current status

• GKR prover can be run with circuit, function $D$ that is claimed to equal $W_0$, and returns proof.
• GKR verifier can be run with circuit, proof, z.
• Integrated sumcheck protocol is implemented.

TODO

For now, sumcheck is integrated with prover and verifier.
To get sumcheck proof, it should be separate. With this, structure of GKR proof should be fixed.

• Implement verify_sumcheck, prove_sumcheck
• Define GKR proof structure

GKR circuit

GKR generates proofs for the data-parallel execution of a layered arithmetic circuit.
But users who want to make new circuit for using GKR may have difficulty for designing layered circuit.
For usability of GKR protocol, it should have programmable and intuitive abstract structure for circuit.

Naive approach

Just make Node and make directed acyclic graph with that. Users should make DAG on their own from Node.
For now, it will be okay but it should be revised. It is hard to build circuit with layer for large program.

From circom

Start from circom rust library, it have dag library inside. It can make DAG, but it would be implemented after implementation of whole protocol. If this circom -> GKR -> circom flow is implemented, recursive proof can be made from this.

Own IR and further

It is kind of ambitious work. Making IR for circuit. And it can be optimized to GKR protocol. (maybe)
[ZLW+ 21] proposed GKR protocol that applies directly to non-layered circuits.
Not sure for if it is available to implement, but it can be helpful for exploring way to use general circuit with GKR protocol.