search

jeong0982 / gkr

zero knowledge proof aggregator for general circuit
70 stars 3 forks source link

Structure of GKR circuit #1

Closed jeong0982 closed 1 year ago

jeong0982 commented 1 year ago

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.

jeong0982 commented 1 year ago

For now, in rust branch, trying to implement general GKR circuit struct to reuse it for halo2 version after circom-GKR proof aggregation.\ It will use circom DAG or parse .r1cs file and then convert it to GKRCircuit struct.