Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Boolean circuits and the reordering of their wires (Definitions 3.13–3.14)

Definition
LatticePrepro_Verifier_Circuit

by WizardOfMenlo · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
  • Boolean circuit (BoolCircuit): nnn input wires, www witness wires and ggg gates in topological order. The wires are numbered 0,…,S−10, \dots, S-10,…,S−1 with S=n+w+gS = n + w + gS=n+w+g (S): wires 0,…,n−10,\dots,n-10,…,n−1 carry the instance, wires n,…,n+w−1n, \dots, n+w-1n,…,n+w−1 the witness, and wire n+w+kn + w + kn+w+k is the output of gate kkk. Gate kkk reads two (possibly equal) wires among the first n+w+kn + w + kn+w+k and applies a Boolean function fk ⁣:{0,1}2→{0,1}f_k\colon \{0,1\}^2 \to \{0,1\}fk​:{0,1}2→{0,1}. One gate is designated as the output; its wire is o=n+w+(index of the output gate)o = n + w + (\text{index of the output gate})o=n+w+(index of the output gate) (outW).
  • Evaluation (evalAux): for an instance x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n and a witness u∈{0,1}wu \in \{0,1\}^wu∈{0,1}w, wire iii has value xix_ixi​ if i<ni < ni<n, ui−nu_{i-n}ui−n​ if n≤i<n+wn \le i < n+wn≤i<n+w, and fkf_kfk​ applied to the values of its two input wires if i=n+w+ki = n+w+ki=n+w+k is a gate wire (wires i≥Si \ge Si≥S get the value 000).
  • Language (Language): L(C)={x∈{0,1}n:the output wire has value 1 for some witness u}L(C) = \{x \in \{0,1\}^n : \text{the output wire has value } 1 \text{ for some witness } u\}L(C)={x∈{0,1}n:the output wire has value 1 for some witness u}.
  • Reordering (coordOfNat, coordOf): the coordinate of wire iii in the order "inputs, output wire, remaining wires": i↦ii \mapsto ii↦i for i<ni < ni<n, o↦no \mapsto no↦n, i↦i+1i \mapsto i + 1i↦i+1 for n≤i<on \le i < on≤i<o, and i↦ii \mapsto ii↦i for i>oi > oi>o. gateWire, inWire1, inWire2 are the output and input wires of gate kkk.
  • Gate verifier of a circuit (toGateVerifier): the gate verifier with instance length nnn, SSS wires and ggg gates, gate kkk being the constraint "coordinate of its output wire =fk= f_k=fk​(coordinates of its input wires)".

A BoolCircuit is a verifier in the sense of Definition 3.13, and the reordering is the coordinate order of assignments in Definition 3.14 (input bits, output of the designated gate, witness bits, remaining gate outputs). BoolCircuit.language_toGateVerifier shows that the gate verifier has the same language; the 3SAT verifier is built as a BoolCircuit.

Formalization Note: Every gate has exactly two input wires (gates of smaller fan-in are expressed by repeating or ignoring an input), and the designated output gate forces g≥1g \ge 1g≥1. Evaluation is defined by well-founded recursion on the wire index. The bundle also contains the facts o<So < So<S, n≤on \le on≤o, and that the reordering maps wires below SSS to coordinates below SSS.

Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Verifier_Quadratic
import Definitions.Def_LatticePrepro_Verifier_Gates

/-!
# Boolean circuits (Definitions 3.13–3.14)

A `BoolCircuit` has `n` input wires, `w` witness wires and `g` gates of fan-in two in topological
order: gate `k` reads two of the first `n + w + k` wires and writes wire `n + w + k`. A designated
gate is the output. Evaluation (`evalAux`) is defined by well-founded recursion on the wire index,
and the accepted language consists of the instances `x` for which some witness makes the output
wire `true`.

Reordering the wires as in Definition 3.14 (inputs, then the output wire, then the remaining
wires in order) turns a circuit into a `GateVerifier` with the same language
(`BoolCircuit.language_toGateVerifier`): the valid wire assignments of the gate verifier are
exactly the evaluations of the circuit.
-/

namespace LatticePrepro

/-- A Boolean circuit with gates of fan-in two in topological order. -/
structure BoolCircuit where
  /-- Number of input wires. -/
  n : ℕ
  /-- Number of witness wires. -/
  w : ℕ
  /-- Number of gates. -/
  g : ℕ
  /-- Gate `k` reads two of the first `n + w + k` wires. -/
  gateIn : (k : Fin g) → Fin (n + w + k.val) × Fin (n + w + k.val)
  /-- The Boolean function computed by gate `k`. -/
  gateFn : Fin g → Bool → Bool → Bool
  /-- The designated output gate. -/
  output : Fin g

namespace BoolCircuit

variable (C : BoolCircuit)

/-- The number of wires. -/
abbrev S : ℕ := C.n + C.w + C.g

/-- The index of the output wire. -/
def outW : ℕ := C.n + C.w + C.output.val

lemma outW_lt : C.outW < C.n + C.w + C.g := by
  unfold outW; have := C.output.isLt; omega

lemma n_le_outW : C.n ≤ C.outW := by unfold outW; omega

/-- Evaluation of the wire with index `i` on instance `x` and witness `wit`
(wires `≥ n + w + g` evaluate to `false`). -/
def evalAux (x : Fin C.n → Bool) (wit : Fin C.w → Bool) (i : ℕ) : Bool :=
  if h1 : i < C.n then x ⟨i, h1⟩
  else if h2 : i < C.n + C.w then wit ⟨i - C.n, by omega⟩
  else if h3 : i < C.n + C.w + C.g then
    C.gateFn ⟨i - (C.n + C.w), by omega⟩
      (evalAux x wit (C.gateIn ⟨i - (C.n + C.w), by omega⟩).1.val)
      (evalAux x wit (C.gateIn ⟨i - (C.n + C.w), by omega⟩).2.val)
  else false
termination_by i
decreasing_by
  · have h := (C.gateIn ⟨i - (C.n + C.w), by omega⟩).1.isLt
    simp only [Fin.val_mk] at h
    omega
  · have h := (C.gateIn ⟨i - (C.n + C.w), by omega⟩).2.isLt
    simp only [Fin.val_mk] at h
    omega

/-- The language of the circuit: instances with a witness making the output wire `true`. -/
def Language : Set (Fin C.n → Bool) := {x | ∃ wit, C.evalAux x wit C.outW = true}

/-! ### Reordering the wires -/

/-- The coordinate (in the order inputs, output, remaining wires) of a wire. -/
def coordOfNat (wi : ℕ) : ℕ :=
  if wi < C.n then wi else if wi = C.outW then C.n else if wi < C.outW then wi + 1 else wi

lemma coordOfNat_lt {wi : ℕ} (_h : wi < C.n + C.w + C.g) : C.coordOfNat wi < C.n + C.w + C.g := by
  unfold coordOfNat
  have := C.outW_lt; have := C.n_le_outW
  split_ifs <;> omega

/-- The coordinate of a wire, as an element of `Fin S`. -/
def coordOf (wi : Fin C.S) : Fin C.S := ⟨C.coordOfNat wi, C.coordOfNat_lt wi.isLt⟩

/-- The wire written by gate `k`. -/
def gateWire (k : Fin C.g) : Fin C.S :=
  ⟨C.n + C.w + k.val, by show _ < C.n + C.w + C.g; have := k.isLt; omega⟩

/-- The first input wire of gate `k`. -/
def inWire1 (k : Fin C.g) : Fin C.S :=
  ⟨(C.gateIn k).1.val, by have := (C.gateIn k).1.isLt; have := k.isLt; show _ < C.n + C.w + C.g; omega⟩

/-- The second input wire of gate `k`. -/
def inWire2 (k : Fin C.g) : Fin C.S :=
  ⟨(C.gateIn k).2.val, by have := (C.gateIn k).2.isLt; have := k.isLt; show _ < C.n + C.w + C.g; omega⟩

/-- The gate verifier of a circuit (Definition 3.14): the coordinates list the inputs, then the
output wire, then the remaining wires in order. -/
abbrev toGateVerifier : GateVerifier where
  n := C.n
  S := C.S
  n_succ_le := by show C.n + 1 ≤ C.n + C.w + C.g; have := C.output.isLt; omega
  G := C.g
  gate := fun k =>
    (C.coordOf (C.gateWire k), C.coordOf (C.inWire1 k), C.coordOf (C.inWire2 k), C.gateFn k)

end BoolCircuit

end LatticePrepro
Source
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), Definitions 3.13–3.14 (\label{def:verifier}, \label{def:computation-assignment}); Lean: LatticePrepro/Verifier/Circuit.lean, LatticePrepro.BoolCircuit, LatticePrepro.BoolCircuit.evalAux, LatticePrepro.BoolCircuit.Language, LatticePrepro.BoolCircuit.toGateVerifier

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me