GKR Research

SumCheck, extended to GKR, provides means to encode heavily-repetitive circuits while having proving times grow only with the log of the number of constraints. This makes it an attractive potential option for encoding the Keccak hash function, which depends on expensive to encode operations ($\land, \lor, \lnot, \oplus$) and is usually impractical to implement in circuit.

This project aims to answer two main questions:

• Firstly, is it at all practical to encode Keccak using GKR, and does it bring any benefit to do so?
• Secondly, how do we verify a GKR proof inside of the Noir language for writing ZK circuits?

This repository exists primarily to collate research and experimentation in order to answer these questions. This will mostly be in the form of Jupyter notebooks.

Building

This repository is a series of Jupyter notebooks. Ensure that you have installed your dependencies by running poetry install --no-root, and then open the resultant virtualenv (which you can get the path to using poetry virtualenv info) in your notebook editor of choice. All cells should run successfully.

You also want to run npm install, as this will set up the formatting and type-checking hooks to be run pre-commit.