gkr

GKR Protocol Implementation

This repository contains an implementation of the GKR (Goldwasser-Kalai-Rothblum) protocol in Rust. The GKR protocol is an efficient interactive proof system for verifiable computation. In addition, it contains an implementation of a Succinct Non-Interactive Argument of Knowledge (SNARK) based on the GKR (Goldwasser-Kalai-Rothblum) protocol, enhanced with Multilinear KZG (Kate-Zaverucha-Goldberg) polynomial commitments. This implementation transforms the interactive GKR protocol into a non-interactive, succinct proof system.

Overview

The implementation includes the following main components:

1. GKR

• GKR Protocol: The core implementation of the GKR protocol.
• Circuit Representation: A structure to represent arithmetic circuits.
• Gate Types: Support for addition and multiplication gates.
• Utility Functions: Helper functions for various computations.
• FiatShamirTranscript: Implements the Fiat-Shamir heuristic for non-interactive proofs.

2. SuccintGKR

• SuccintGKRProof: Represents the succinct proof generated by the prover.
• SuccintGKRProtocol: The main structure implementing the succinct GKR protocol.
• Circuit: Represents the arithmetic circuit being proven.
• MultilinearKZG: Used for polynomial commitments, crucial for achieving succinctness.
• FiatShamirTranscript: Implements the Fiat-Shamir heuristic for non-interactive proofs.

Features

• Proof Generation: Create proofs for correct circuit evaluation.
• Verification: Verify the correctness of generated proofs.
• Circuit Evaluation: Evaluate arithmetic circuits on given inputs.
• Multilinear Extension: Compute multilinear extensions of circuit layers.

Usage

Here's a basic example of how to use the GKR protocol:

// GKR PROTOCOL
let circuit = Circuit::new(/* ... */);
let input = vec![/* ... */];

// Generate proof
let proof = GKRProtocol::prove(&circuit, &input);

// Verify proof
let is_valid = GKRProtocol::verify(&circuit, &input, &proof);


// SUCCINT-GKR PROTOCOL
let circuit = Circuit::new(/* ... */);
let input = vec![/* ... */];
let point = vec![/* ... */]

// Set up the trusted setup
let tau = TrustedSetup::<Bls12_381>::setup(&points);

// Generate the succinct proof
let (commitment, proof) = GKRProtocol::prove(&circuit, &input, &tau);

// Verify the succinct proof
let verify = GKRProtocol::verify(&circuit, &commitment, &proof, &tau);

Implementation Details

• The protocol uses the Fiat-Shamir heuristic for non-interactive proofs.
• Supports arithmetic circuits with addition and multiplication gates.
• Utilizes multilinear polynomials and sumcheck protocols.