Module gkr 

GKR Air Module

The GKR protocol reduces a fractional sum claim $\sum_{y \in H_{\ell+n}} \frac{\hat{p}(y)}{\hat{q}(y)} = 0$ to evaluation claims on the input layer polynomials at a random point. This is done through a layer-by-layer recursive reduction, where each layer uses a sumcheck protocol.

The GKR Air Module verifies the [GkrProof] struct and consists of four AIRs:

1. GkrInputAir - Handles initial setup, coordinates other AIRs, and sends final claims to batch constraint module
2. GkrLayerAir - Manages layer-by-layer GKR reduction (verifies verify_gkr)
3. GkrLayerSumcheckAir - Executes sumcheck protocol for each layer (verifies verify_gkr_sumcheck)
4. GkrXiSamplerAir - Samples additional xi randomness challenges if required

Architecture

                               ┌─────────────────┐
                               │                 │───────────────────► TranscriptBus
                               │ GkrXiSamplerAir │
                               │                 │───────────────────► XiRandomnessBus
                               └─────────────────┘
                                        ▲
                                        ┆
                        GkrXiSamplerBus ┆
                                        ┆
                                        ▼
                               ┌─────────────────┐
                               │                 │───────────────────► TranscriptBus
                               │                 │
 GkrModuleBus ────────────────►│   GkrInputAir   │───────────────────► ExpBitsLenBus
                               │                 │
                               │                 │───────────────────► BatchConstraintModuleBus
                               └─────────────────┘
                                     ┆      ▲
                                     ┆      ┆
                    GkrLayerInputBus ┆      ┆ GkrLayerOutputBus
                                     ┆      ┆
                                     ▼      ┆
                            ┌─────────────────────────┐
                            │                         │──────────────► TranscriptBus
  ┌┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄│       GkrLayerAir       │
  ┆                         │                         │──────────────► XiRandomnessBus
  ┆                         └─────────────────────────┘
  ┆                                  ┆      ▲
  ┆                                  ┆      ┆
  ┆              GkrSumcheckInputBus ┆      ┆ GkrSumcheckOutputBus
  ┆                                  ┆      ┆
  ┆                                  ▼      ┆
  ┆ GkrSumcheckChallengeBus ┌─────────────────────────┐
  ┆┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄│                         │──────────────► TranscriptBus
  ┆                         │   GkrLayerSumcheckAir   │
  └┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄►│                         │──────────────► XiRandomnessBus
                            └─────────────────────────┘

Modules

input

layer

sumcheck

xi_sampler

Structs

GkrModule

GkrSumcheckChallengeBus

GkrSumcheckChallengeMessage

Message for passing challenges between consecutive sumcheck sub-rounds

GkrSumcheckInputBus

GkrSumcheckInputMessage

Message sent from GkrLayerAir to GkrLayerSumcheckAir

GkrSumcheckOutputBus

GkrSumcheckOutputMessage

Message sent from GkrLayerSumcheckAir to GkrLayerAir