Documentation

ArkLib.ProofSystem.RingSwitching.SumcheckPhase

Ring-Switching Core Interaction Phase #

This module implements the core interactive sumcheck phase of the ring-switching protocol.

Iterated Sumcheck Steps #

  1. P and V execute the following loop: for i ∈ {0, ..., ℓ'-1} do P sends V the polynomial hᵢ(X) := Σ_{w ∈ {0,1}^{ℓ'-i-1}} h(r'₀, ..., r'_{i-1}, X, w₀, ..., w_{ℓ'-i-2}). V requires sᵢ ?= hᵢ(0) + hᵢ(1). V samples r'ᵢ ← L, sets s_{i+1} := hᵢ(r'ᵢ), and sends P r'ᵢ.

Each iteration of the loop constitutes a single round:

This is the core computational phase with ℓ' rounds, each with 2 messages, and is the main source of RBR knowledge soundness error.

Final Sumcheck Step #

  1. P computes s' := t'(r'_0, ..., r'_{ℓ'-1}) and sends V s'.
  2. V sets e := eq̃(φ₀(r_κ), ..., φ₀(r_{ℓ-1}), φ₁(r'_0), ..., φ₁(r'_{ℓ'-1})) and decomposes e =: Σ_{u ∈ {0,1}^κ} β_u ⊗ e_u.
  3. V requires s_{ℓ'} ?= (Σ_{u ∈ {0,1}^κ} eq̃(u_0, ..., u_{κ-1}, r''_0, ..., r''_{κ-1}) ⋅ e_u) ⋅ s'.

Per-round prover / verifier (re-exported from Sumcheck.Structured.SingleRound) #

The per-round protocol code was lifted to ArkLib.ProofSystem.Sumcheck.Structured.SingleRound as round{PrvState, OracleProver, OracleVerifier, OracleReduction}, getRoundProverFinalOutput, and roundKnowledgeError, parameterized over a generic Context : Type and OStmtIn : ιₛᵢ → Type.

For backwards compatibility, the wrappers below preserve the original autobound signature (via the surrounding variable block — κ L K ℓ ℓ' aOStmtIn) by specializing Context := RingSwitchingBaseContext κ L K ℓ and OStmtIn := aOStmtIn.OStmtIn. They keep the iteratedSumcheck* names (these are what the sumcheck loop iterates over) and are @[reducible] so that subsequent soundness proofs and the seqCompose loop can still access fields like .KnowledgeStateFunction / .rbrKnowledgeSoundness through them.

@[reducible]
def RingSwitching.SumcheckPhase.iteratedSumcheckPrvState (κ : ) (L : Type) [CommRing L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (aOStmtIn : AbstractOStmtIn L ℓ') (i : Fin ℓ') :
Fin (2 + 1)Type
Instances For
    @[reducible]
    noncomputable def RingSwitching.SumcheckPhase.getIteratedSumcheckProverFinalOutput (κ : ) (L : Type) [CommRing L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (aOStmtIn : AbstractOStmtIn L ℓ') (i : Fin ℓ') (finalPrvState : iteratedSumcheckPrvState κ L K P ℓ' aOStmtIn i 2) :
    (Sumcheck.Structured.Statement (RingSwitchingBaseContext κ L K P) i.succ × ((j : aOStmtIn.ιₛᵢ) → aOStmtIn.OStmtIn j)) × SumcheckWitness L ℓ' i.succ
    Instances For
      @[reducible]
      Instances For
        @[reducible]
        Instances For
          theorem RingSwitching.SumcheckPhase.iteratedSumcheckOracleReduction_perfectCompleteness (κ : ) [NeZero κ] (L : Type) [CommRing L] [Nontrivial L] [DecidableEq L] [SampleableType L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) [NeZero ] [NeZero ℓ'] (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {σ : Type} {init : ProbComp σ} {impl : QueryImpl []ₒ (StateT σ ProbComp)} (i : Fin ℓ') :
          OracleReduction.perfectCompleteness init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn i.castSucc) (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn i.succ) (iteratedSumcheckOracleReduction κ L K P ℓ' aOStmtIn i)
          @[reducible, inline]
          noncomputable abbrev RingSwitching.SumcheckPhase.roundKnowledgeError (L : Type) [Fintype L] ( : ) (i : Fin ) :
          Instances For
            noncomputable def RingSwitching.SumcheckPhase.iteratedSumcheckRbrExtractor (κ : ) (L : Type) [CommRing L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') (i : Fin ℓ') :
            Extractor.RoundByRound []ₒ (Sumcheck.Structured.Statement (RingSwitchingBaseContext κ L K P) i.castSucc × ((j : aOStmtIn.ιₛᵢ) → aOStmtIn.OStmtIn j)) (SumcheckWitness L ℓ' i.castSucc) (SumcheckWitness L ℓ' i.succ) (pSpecSumcheckRound L) fun (_messageIdx : Fin (2 + 1)) => SumcheckWitness L ℓ' i.castSucc
            Instances For
              def RingSwitching.SumcheckPhase.iteratedSumcheckKStateProp (κ : ) (L : Type) [CommRing L] [Nontrivial L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') (i : Fin ℓ') (m : Fin (2 + 1)) (tr : ProtocolSpec.Transcript m (pSpecSumcheckRound L)) (stmt : Sumcheck.Structured.Statement (RingSwitchingBaseContext κ L K P) i.castSucc) (witMid : SumcheckWitness L ℓ' i.castSucc) (oStmt : (j : aOStmtIn.ιₛᵢ) → aOStmtIn.OStmtIn j) :

              This follows the KState of foldKStateProp

              Instances For
                def RingSwitching.SumcheckPhase.iteratedSumcheckKnowledgeStateFunction (κ : ) (L : Type) [CommRing L] [Nontrivial L] [DecidableEq L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {σ : Type} {init : ProbComp σ} {impl : QueryImpl []ₒ (StateT σ ProbComp)} (i : Fin ℓ') :
                OracleVerifier.KnowledgeStateFunction init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn i.castSucc) (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn i.succ) (iteratedSumcheckOracleVerifier κ L K P ℓ' aOStmtIn i) (iteratedSumcheckRbrExtractor κ L K P ℓ' h_l aOStmtIn i)

                Knowledge state function (KState) for single round

                Instances For
                  theorem RingSwitching.SumcheckPhase.iteratedSumcheckOracleVerifier_rbrKnowledgeSoundness (κ : ) [NeZero κ] (L : Type) [CommRing L] [Nontrivial L] [Fintype L] [DecidableEq L] [SampleableType L] (K : Type) [CommRing K] [Fintype K] [DecidableEq K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) [NeZero ] [NeZero ℓ'] (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {σ : Type} {init : ProbComp σ} {impl : QueryImpl []ₒ (StateT σ ProbComp)} [IsDomain L] (i : Fin ℓ') :
                  OracleVerifier.rbrKnowledgeSoundness init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn i.castSucc) (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn i.succ) (iteratedSumcheckOracleVerifier κ L K P ℓ' aOStmtIn i) fun (j : (pSpecSumcheckRound L).ChallengeIdx) => roundKnowledgeError L ℓ' i

                  RBR knowledge soundness for a single round oracle verifier

                  Final Sumcheck Step #

                  noncomputable def RingSwitching.SumcheckPhase.finalSumcheckProver (κ : ) (L : Type) [CommRing L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (aOStmtIn : AbstractOStmtIn L ℓ') :

                  The prover for the final sumcheck step

                  Instances For
                    noncomputable def RingSwitching.SumcheckPhase.finalSumcheckVerifier (κ : ) (L : Type) [CommRing L] [DecidableEq L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') :

                    The verifier for the final sumcheck step

                    Instances For
                      noncomputable def RingSwitching.SumcheckPhase.finalSumcheckOracleReduction (κ : ) (L : Type) [CommRing L] [DecidableEq L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') :

                      The oracle reduction for the final sumcheck step

                      Instances For
                        theorem RingSwitching.SumcheckPhase.finalSumcheckOracleReduction_perfectCompleteness (κ : ) [NeZero κ] (L : Type) [CommRing L] [Nontrivial L] [Fintype L] [DecidableEq L] [SampleableType L] (K : Type) [CommRing K] [Fintype K] [DecidableEq K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) [NeZero ] [NeZero ℓ'] (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {σ : Type} (init : ProbComp σ) (impl : QueryImpl []ₒ (StateT σ ProbComp)) :
                        OracleReduction.perfectCompleteness init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn (Fin.last ℓ')) (AbstractOStmtIn.toRelInput L ℓ' aOStmtIn) (finalSumcheckOracleReduction κ L K P ℓ' h_l aOStmtIn)

                        Perfect completeness for the final sumcheck step

                        RBR knowledge error for the final sumcheck step

                        Instances For
                          noncomputable def RingSwitching.SumcheckPhase.finalSumcheckRbrExtractor (κ : ) (L : Type) [CommRing L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') :
                          Extractor.RoundByRound []ₒ (Sumcheck.Structured.Statement (RingSwitchingBaseContext κ L K P) (Fin.last ℓ') × ((j : aOStmtIn.ιₛᵢ) → aOStmtIn.OStmtIn j)) (SumcheckWitness L ℓ' (Fin.last ℓ')) (WitMLP L ℓ') (pSpecFinalSumcheck L) fun (_m : Fin (1 + 1)) => SumcheckWitness L ℓ' (Fin.last ℓ')

                          The round-by-round extractor for the final sumcheck step

                          Instances For
                            def RingSwitching.SumcheckPhase.finalSumcheckKStateProp (κ : ) (L : Type) [CommRing L] [Nontrivial L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {m : Fin (1 + 1)} (tr : ProtocolSpec.Transcript m (pSpecFinalSumcheck L)) (stmt : Sumcheck.Structured.Statement (RingSwitchingBaseContext κ L K P) (Fin.last ℓ')) (witMid : SumcheckWitness L ℓ' (Fin.last ℓ')) (oStmt : (j : aOStmtIn.ιₛᵢ) → aOStmtIn.OStmtIn j) :
                            Instances For
                              noncomputable def RingSwitching.SumcheckPhase.finalSumcheckKnowledgeStateFunction (κ : ) (L : Type) [CommRing L] [Nontrivial L] [DecidableEq L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {σ : Type} (init : ProbComp σ) (impl : QueryImpl []ₒ (StateT σ ProbComp)) :
                              OracleVerifier.KnowledgeStateFunction init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn (Fin.last ℓ')) (AbstractOStmtIn.toRelInput L ℓ' aOStmtIn) (finalSumcheckVerifier κ L K P ℓ' h_l aOStmtIn) (finalSumcheckRbrExtractor κ L K P ℓ' h_l aOStmtIn)

                              The knowledge state function for the final sumcheck step

                              Instances For
                                theorem RingSwitching.SumcheckPhase.finalSumcheckOracleVerifier_rbrKnowledgeSoundness (κ : ) [NeZero κ] (L : Type) [CommRing L] [Nontrivial L] [Fintype L] [DecidableEq L] [SampleableType L] (K : Type) [CommRing K] [Fintype K] [DecidableEq K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) [NeZero ] [NeZero ℓ'] (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') [Fintype L] [IsDomain L] {σ : Type} (init : ProbComp σ) (impl : QueryImpl []ₒ (StateT σ ProbComp)) :
                                OracleVerifier.rbrKnowledgeSoundness init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn (Fin.last ℓ')) (AbstractOStmtIn.toRelInput L ℓ' aOStmtIn) (finalSumcheckVerifier κ L K P ℓ' h_l aOStmtIn) fun (x : (pSpecFinalSumcheck L).ChallengeIdx) => finalSumcheckRbrKnowledgeError L

                                Round-by-round knowledge soundness for the final sumcheck step

                                @[reducible]

                                Composed oracle verifier for the SumcheckStep (seqCompose over ℓ')

                                Instances For
                                  @[reducible]

                                  Composed oracle reduction for the SumcheckStep (seqCompose over ℓ')

                                  Instances For
                                    @[reducible]
                                    noncomputable def RingSwitching.SumcheckPhase.coreInteractionOracleVerifier (κ : ) (L : Type) [CommRing L] [Nontrivial L] [DecidableEq L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') :

                                    Large-field reduction verifier: Sumcheck seqCompose, then append FinalSum

                                    Instances For
                                      @[reducible]
                                      noncomputable def RingSwitching.SumcheckPhase.coreInteractionOracleReduction (κ : ) (L : Type) [CommRing L] [Nontrivial L] [DecidableEq L] (K : Type) [CommRing K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') :

                                      Large-field reduction: Sumcheck seqCompose, then append FinalSum

                                      Instances For

                                        RBR Knowledge Soundness Components for Single Round #

                                        theorem RingSwitching.SumcheckPhase.coreInteraction_perfectCompleteness (κ : ) [NeZero κ] (L : Type) [CommRing L] [Nontrivial L] [Fintype L] [DecidableEq L] [SampleableType L] (K : Type) [CommRing K] [Fintype K] [DecidableEq K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) [NeZero ] [NeZero ℓ'] (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {σ : Type} {init : ProbComp σ} {impl : QueryImpl []ₒ (StateT σ ProbComp)} :
                                        OracleReduction.perfectCompleteness init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn 0) (AbstractOStmtIn.toRelInput L ℓ' aOStmtIn) (coreInteractionOracleReduction κ L K P ℓ' h_l aOStmtIn)

                                        Perfect completeness for large-field reduction (Sumcheck ++ FinalSum)

                                        RBR knowledge error for a degree-d sumcheck loop, obtained from the seqCompose challenge-index decomposition.

                                        Instances For

                                          RBR knowledge error for the core interaction with a degree-d sumcheck loop. The loop contributes d / |L| per sumcheck challenge; the final sumcheck contributes 1 / |L|.

                                          Instances For

                                            Standard Binius ring-switching RBR knowledge error (d = 2) with exact final-step splitting.

                                            Instances For
                                              theorem RingSwitching.SumcheckPhase.coreInteraction_rbrKnowledgeSoundness (κ : ) [NeZero κ] (L : Type) [CommRing L] [Nontrivial L] [Fintype L] [DecidableEq L] [SampleableType L] (K : Type) [CommRing K] [Fintype K] [DecidableEq K] [Algebra K L] (P : RingSwitchingProfile K L κ) (ℓ' : ) [NeZero ] [NeZero ℓ'] (h_l : = ℓ' + κ) (aOStmtIn : AbstractOStmtIn L ℓ') {σ : Type} {init : ProbComp σ} {impl : QueryImpl []ₒ (StateT σ ProbComp)} [IsDomain L] :
                                              OracleVerifier.rbrKnowledgeSoundness init impl (sumcheckRoundRelation κ L K P ℓ' h_l aOStmtIn 0) (AbstractOStmtIn.toRelInput L ℓ' aOStmtIn) (coreInteractionOracleVerifier κ L K P ℓ' h_l aOStmtIn) (coreInteractionRbrKnowledgeError L ℓ')

                                              RBR knowledge soundness for large-field reduction (Sumcheck ++ FinalSum)