Skip to content

Latest commit

 

History

History
61 lines (46 loc) · 2.62 KB

README.md

File metadata and controls

61 lines (46 loc) · 2.62 KB

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.
  1. 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.