AFTD Auto-Formalizing Theoretical Domains

schnorr_linear_batch_soundness_bound

theoremverifiedoriginal

Let G be a commutative group, q a prime, and g in G an element of order q. Let pk, a₁, a₂ in Subgroup.zpowers g. For any challenges c₁, c₂ in ZMod q and responses s₁, s₂ in ZMod q, if transcript 1 does not satisfy Schnorr.Verify g pk a₁ c₁ s₁, then the set of linear batching weights α in ZMod q for which g^((s₁ + α * s₂).val) = a₁ * a₂^(α.val) * pk^((c₁ + α * c₂).val) holds has cardinality at most 1.

Statement

theorem schnorr_linear_batch_soundness_bound
    {G : Type*} [CommGroup G] [DecidableEq G] {q : ℕ} [Fact q.Prime] (g : G)
    (hg : orderOf g = q) (pk a₁ a₂ : G)
    (hpk : pk ∈ Subgroup.zpowers g)
    (ha₁ : a₁ ∈ Subgroup.zpowers g)
    (ha₂ : a₂ ∈ Subgroup.zpowers g)
    (c₁ c₂ s₁ s₂ : ZMod q)
    (hnot : ¬ Schnorr.Verify g pk a₁ c₁ s₁) :
    (Finset.filter (fun α : ZMod q =>
      g ^ (s₁ + α * s₂).val = a₁ * a₂ ^ α.val * pk ^ (c₁ + α * c₂).val) Finset.univ).card ≤ 1
Related work
Bellare, Garay, and Ralf 1998, Fast Batch Verification of Signatures
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • Schnorr.VerifyThe verifier accepts a transcript $(a, c, s)$ with respect to public key $\mathit{pk} \in G$ when $g^s = a \cdot \mathit{pk}^{c}$, where…
  • schnorr_mem_zpowers_iff_exists_zmodLet G be a commutative group, q a prime, and g in G an element of order q. Any element x in the cyclic subgroup generated by g is of the…
  • schnorr_zpow_eq_pow_zmod_valLet G be a commutative group, q a prime, and g in G an element of order q. For any integer z, the integer power g^z equals g^(z.val) where…

Read back from the Lean

Let G be a commutative group with decidable equality. Let q be a prime natural number. Let g : G be an element whose order in G equals q. Let pk, a₁, and a₂ be elements of G each belonging to the cyclic subgroup generated by g (Subgroup.zpowers g). Let c₁, c₂, s₁, and s₂ be elements of ZMod q. Assuming that Schnorr.Verify g pk a₁ c₁ s₁ does not hold (¬ Schnorr.Verify g pk a₁ c₁ s₁), then the number of elements α : ZMod q satisfying g ^ (s₁ + α * s₂).val = a₁ * a₂ ^ α.val * pk ^ (c₁ + α * c₂).val is at most 1.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

Linear batch verification for Schnorr signatures is sound because the batched verification equation reduces to an affine relation in the batching weight α over the field ZMod q. When the first transcript is invalid, the linear coefficient cannot vanish without validating that transcript, so the affine equation has at most one solution. Therefore, the set of accepting batch weights has cardinality at most 1.

  1. Exponentiation by n equals exponentiation by n modulo q.

    We reduce the natural exponent n to an integer power and apply the lemma schnorr_zpow_eq_pow_zmod_val, rewriting the cast to ZMod q.

    lines 5–8

    uses schnorr_zpow_eq_pow_zmod_val, zpow_natCast

      have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩
      have h2 := schnorr_zpow_eq_pow_zmod_val g hg (n : ℤ)
      push_cast at h2
      rw [← zpow_natCast, h2]
  2. Iterated exponentiation corresponds to multiplication of exponents in ZMod q.

    We rewrite using pow_mul and reduce the product of values modulo q using schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val.

    lines 14–18

    uses pow_mul, schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val

      have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩
      rw [← pow_mul, schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val g hg (x.val * y.val)]
      congr 1
      push_cast
      simp
  3. Product of powers corresponds to addition of exponents in ZMod q.

    We rewrite using pow_add and reduce the sum modulo q using schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val.

    lines 24–28

    uses pow_add, schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val

      have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩
      rw [← pow_add, schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val g hg (x.val + y.val)]
      congr 1
      push_cast
      simp
  4. Powers of g by values in ZMod q are injective.

    Equality of powers modulo order q implies congruence of exponents modulo q; since the values are strictly less than q, they are equal in ℕ and thus in ZMod q.

    lines 34–44

    uses pow_eq_pow_iff_modEq, ZMod.val_lt, Nat.mod_eq_of_lt, ZMod.val_injective

      have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩
      constructor
      · intro h
        rw [pow_eq_pow_iff_modEq, hg] at h
        have hs₁ := ZMod.val_lt k₁
        have hs₂ := ZMod.val_lt k₂
        change k₁.val % q = k₂.val % q at h
        rw [Nat.mod_eq_of_lt hs₁, Nat.mod_eq_of_lt hs₂] at h
        exact ZMod.val_injective q h
      · rintro rfl
        rfl
  5. Schnorr verification is equivalent to a linear relation in ZMod q.

    By combining powers in the verification equation and applying injectivity of powers of g, Schnorr verification is equivalent to s₁ = r₁ + c₁ * w.

    lines 50–55

    uses schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod, schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod, schnorr_linear_batch_soundness_bound_g_pow_inj

      change g ^ s₁.val = g ^ r₁.val * (g ^ w.val) ^ c₁.val ↔ s₁ = r₁ + c₁ * w
      rw [schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod g hg w c₁]
      rw [schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod g hg r₁ (w * c₁)]
      have h_exp : r₁ + w * c₁ = r₁ + c₁ * w := by ring
      rw [h_exp]
      exact schnorr_linear_batch_soundness_bound_g_pow_inj g hg s₁ (r₁ + c₁ * w)
  6. The linear batch verification equation in the group is equivalent to a linear equation in ZMod q.

    Using exponentiation laws, the right-hand side simplifies to a single power of g, which by injectivity yields the linear equation in the exponents.

    lines 62–71

    uses schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod, schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod, schnorr_linear_batch_soundness_bound_g_pow_inj

      have h_rhs : (g ^ r₁.val) * (g ^ r₂.val) ^ α.val * (g ^ w.val) ^ (c₁ + α * c₂).val =
          g ^ (r₁ + c₁ * w + α * (r₂ + c₂ * w)).val := by
        rw [schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod g hg r₂ α]
        rw [schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod g hg w (c₁ + α * c₂)]
        rw [schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod g hg r₁ (r₂ * α)]
        rw [schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod g hg (r₁ + r₂ * α) (w * (c₁ + α * c₂))]
        congr 2
        ring
      rw [h_rhs]
      exact schnorr_linear_batch_soundness_bound_g_pow_inj g hg (s₁ + α * s₂) (r₁ + c₁ * w + α * (r₂ + c₂ * w))
  7. Two distinct batch weights cannot satisfy the batch relation if transcript 1 is invalid.

    Subtracting the two equations gives (α₁ - α₂) * (s₂ - (r₂ + c₂ * w)) = 0. In an integral domain, either α₁ = α₂ or the second factor is 0, but the second factor being 0 would imply transcript 1 was valid, a contradiction.

    lines 80–96

    uses sub_eq_zero.mpr, sub_zero, mul_eq_zero.mp, sub_eq_zero.mp

      have h_diff : (α₁ - α₂) * (s₂ - (r₂ + c₂ * w)) = 0 := by
        calc (α₁ - α₂) * (s₂ - (r₂ + c₂ * w))
          _ = (s₁ + α₁ * s₂ - (r₁ + c₁ * w + α₁ * (r₂ + c₂ * w))) -
              (s₁ + α₂ * s₂ - (r₁ + c₁ * w + α₂ * (r₂ + c₂ * w))) := by ring
          _ = 0 - 0 := by rw [sub_eq_zero.mpr h₁, sub_eq_zero.mpr h₂]
          _ = 0 := sub_zero 0
      cases mul_eq_zero.mp h_diff with
      | inl h_sub => exact sub_eq_zero.mp h_sub
      | inr h_B =>
        have h_B_eq : s₂ = r₂ + c₂ * w := sub_eq_zero.mp h_B
        rw [h_B_eq] at h₁
        have h_contr : s₁ = r₁ + c₁ * w := by
          calc s₁ = (s₁ + α₁ * (r₂ + c₂ * w)) - α₁ * (r₂ + c₂ * w) := by ring
          _ = (r₁ + c₁ * w + α₁ * (r₂ + c₂ * w)) - α₁ * (r₂ + c₂ * w) := by rw [h₁]
          _ = r₁ + c₁ * w := by ring
        exact (h_not h_contr).elim
    
  8. At most one batching weight α satisfies the batched verification equation.

    We express public key and commitments as powers of g, translate the batch equation to the ring ZMod q, and deduce uniqueness of valid weights from uniqueness in domains.

    lines 108–119

    uses schnorr_mem_zpowers_iff_exists_zmod, schnorr_linear_batch_soundness_bound_verify_iff, Finset.card_le_one_iff, Finset.mem_filter, schnorr_linear_batch_soundness_bound_batch_eq_iff, schnorr_linear_batch_soundness_bound_linear_batch_eq_unique

      obtain ⟨w, rfl⟩ := schnorr_mem_zpowers_iff_exists_zmod g hg pk hpk
      obtain ⟨r₁, rfl⟩ := schnorr_mem_zpowers_iff_exists_zmod g hg a₁ ha₁
      obtain ⟨r₂, rfl⟩ := schnorr_mem_zpowers_iff_exists_zmod g hg a₂ ha₂
      have hnot_alg : s₁ ≠ r₁ + c₁ * w := by
        intro h_eq
        apply hnot
        rwa [schnorr_linear_batch_soundness_bound_verify_iff g hg]
      rw [Finset.card_le_one_iff]
      intro α₁ α₂ hα₁ hα₂
      rw [Finset.mem_filter] at hα₁ hα₂
      rw [schnorr_linear_batch_soundness_bound_batch_eq_iff g hg] at hα₁ hα₂
      exact schnorr_linear_batch_soundness_bound_linear_batch_eq_unique r₁ r₂ w c₁ c₂ s₁ s₂ α₁ α₂ hα₁.2 hα₂.2 hnot_alg

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (n : ℕ) :    g ^ n = g ^ (n : ZMod q).val := by  have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩  have h2 := schnorr_zpow_eq_pow_zmod_val g hg (n : ℤ)  push_cast at h2  rw [← zpow_natCast, h2]theorem schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (x y : ZMod q) :    (g ^ x.val) ^ y.val = g ^ (x * y).val := by  have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩  rw [← pow_mul, schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val g hg (x.val * y.val)]  congr 1  push_cast  simptheorem schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (x y : ZMod q) :    g ^ x.val * g ^ y.val = g ^ (x + y).val := by  have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩  rw [← pow_add, schnorr_linear_batch_soundness_bound_pow_eq_pow_zmod_val g hg (x.val + y.val)]  congr 1  push_cast  simptheorem schnorr_linear_batch_soundness_bound_g_pow_inj    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (k₁ k₂ : ZMod q) :    g ^ k₁.val = g ^ k₂.val ↔ k₁ = k₂ := by  have : NeZero q := ⟨Nat.Prime.ne_zero Fact.out⟩  constructor  · intro h    rw [pow_eq_pow_iff_modEq, hg] at h    have hs₁ := ZMod.val_lt k₁    have hs₂ := ZMod.val_lt k₂    change k₁.val % q = k₂.val % q at h    rw [Nat.mod_eq_of_lt hs₁, Nat.mod_eq_of_lt hs₂] at h    exact ZMod.val_injective q h  · rintro rfl    rfltheorem schnorr_linear_batch_soundness_bound_verify_iff    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (r₁ w c₁ s₁ : ZMod q) :    Schnorr.Verify g (g ^ w.val) (g ^ r₁.val) c₁ s₁ ↔ s₁ = r₁ + c₁ * w := by  change g ^ s₁.val = g ^ r₁.val * (g ^ w.val) ^ c₁.val ↔ s₁ = r₁ + c₁ * w  rw [schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod g hg w c₁]  rw [schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod g hg r₁ (w * c₁)]  have h_exp : r₁ + w * c₁ = r₁ + c₁ * w := by ring  rw [h_exp]  exact schnorr_linear_batch_soundness_bound_g_pow_inj g hg s₁ (r₁ + c₁ * w)theorem schnorr_linear_batch_soundness_bound_batch_eq_iff    {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (r₁ r₂ w c₁ c₂ s₁ s₂ α : ZMod q) :    g ^ (s₁ + α * s₂).val = (g ^ r₁.val) * (g ^ r₂.val) ^ α.val * (g ^ w.val) ^ (c₁ + α * c₂).val ↔    s₁ + α * s₂ = r₁ + c₁ * w + α * (r₂ + c₂ * w) := by  have h_rhs : (g ^ r₁.val) * (g ^ r₂.val) ^ α.val * (g ^ w.val) ^ (c₁ + α * c₂).val =      g ^ (r₁ + c₁ * w + α * (r₂ + c₂ * w)).val := by    rw [schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod g hg r₂ α]    rw [schnorr_linear_batch_soundness_bound_pow_pow_eq_pow_mul_zmod g hg w (c₁ + α * c₂)]    rw [schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod g hg r₁ (r₂ * α)]    rw [schnorr_linear_batch_soundness_bound_pow_mul_pow_eq_pow_add_zmod g hg (r₁ + r₂ * α) (w * (c₁ + α * c₂))]    congr 2    ring  rw [h_rhs]  exact schnorr_linear_batch_soundness_bound_g_pow_inj g hg (s₁ + α * s₂) (r₁ + c₁ * w + α * (r₂ + c₂ * w))theorem schnorr_linear_batch_soundness_bound_linear_batch_eq_unique    {R : Type*} [CommRing R] [IsDomain R]    (r₁ r₂ w c₁ c₂ s₁ s₂ α₁ α₂ : R)    (h₁ : s₁ + α₁ * s₂ = r₁ + c₁ * w + α₁ * (r₂ + c₂ * w))    (h₂ : s₁ + α₂ * s₂ = r₁ + c₁ * w + α₂ * (r₂ + c₂ * w))    (h_not : s₁ ≠ r₁ + c₁ * w) :    α₁ = α₂ := by  have h_diff : (α₁ - α₂) * (s₂ - (r₂ + c₂ * w)) = 0 := by    calc (α₁ - α₂) * (s₂ - (r₂ + c₂ * w))      _ = (s₁ + α₁ * s₂ - (r₁ + c₁ * w + α₁ * (r₂ + c₂ * w))) -          (s₁ + α₂ * s₂ - (r₁ + c₁ * w + α₂ * (r₂ + c₂ * w))) := by ring      _ = 0 - 0 := by rw [sub_eq_zero.mpr h₁, sub_eq_zero.mpr h₂]      _ = 0 := sub_zero 0  cases mul_eq_zero.mp h_diff with  | inl h_sub => exact sub_eq_zero.mp h_sub  | inr h_B =>    have h_B_eq : s₂ = r₂ + c₂ * w := sub_eq_zero.mp h_B    rw [h_B_eq] at h₁    have h_contr : s₁ = r₁ + c₁ * w := by      calc s₁ = (s₁ + α₁ * (r₂ + c₂ * w)) - α₁ * (r₂ + c₂ * w) := by ring      _ = (r₁ + c₁ * w + α₁ * (r₂ + c₂ * w)) - α₁ * (r₂ + c₂ * w) := by rw [h₁]      _ = r₁ + c₁ * w := by ring    exact (h_not h_contr).elim/-- Quantitative soundness bound for linear batch verification of Schnorr transcripts: at most one linear weight accepts an invalid transcript. -/theorem schnorr_linear_batch_soundness_bound    {G : Type*} [CommGroup G] [DecidableEq G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (pk a₁ a₂ : G)    (hpk : pk ∈ Subgroup.zpowers g)    (ha₁ : a₁ ∈ Subgroup.zpowers g)    (ha₂ : a₂ ∈ Subgroup.zpowers g)    (c₁ c₂ s₁ s₂ : ZMod q)    (hnot : ¬ Schnorr.Verify g pk a₁ c₁ s₁) :    (Finset.filter (fun α : ZMod q =>      g ^ (s₁ + α * s₂).val = a₁ * a₂ ^ α.val * pk ^ (c₁ + α * c₂).val) Finset.univ).card ≤ 1 := by  obtain ⟨w, rfl⟩ := schnorr_mem_zpowers_iff_exists_zmod g hg pk hpk  obtain ⟨r₁, rfl⟩ := schnorr_mem_zpowers_iff_exists_zmod g hg a₁ ha₁  obtain ⟨r₂, rfl⟩ := schnorr_mem_zpowers_iff_exists_zmod g hg a₂ ha₂  have hnot_alg : s₁ ≠ r₁ + c₁ * w := by    intro h_eq    apply hnot    rwa [schnorr_linear_batch_soundness_bound_verify_iff g hg]  rw [Finset.card_le_one_iff]  intro α₁ α₂ hα₁ hα₂  rw [Finset.mem_filter] at hα₁ hα₂  rw [schnorr_linear_batch_soundness_bound_batch_eq_iff g hg] at hα₁ hα₂  exact schnorr_linear_batch_soundness_bound_linear_batch_eq_unique r₁ r₂ w c₁ c₂ s₁ s₂ α₁ α₂ hα₁.2 hα₂.2 hnot_alg
See it in the graphDiscuss this resultChallenge it