Circuits as gate verifiers — ordering the wires as in Definition 3.14 preserves the language
ProvedLatticePrepro.BoolCircuit.language_toGateVerifierLet be a Boolean circuit with input wires, witness wires and gates in topological order (gate writes wire , reads two earlier wires and applies ), with a designated output gate whose wire is . Let be its gate verifier: the wires are renumbered in the order "inputs, output wire, remaining wires", and each gate becomes the constraint on the renumbered wires. Then
Explicitly, for every the following are equivalent:
- there is a wire assignment satisfying every gate constraint of , with for and ;
- there is a witness such that the output wire of evaluates to on .
In the paper, a verifier is a Boolean circuit (Definition 3.13), and its computations are recorded as assignments listing the input bits, the output of the designated gate, the witness bits and the remaining gate outputs (Definition 3.14); the language of is then the set of with an accepting computation. This theorem is that correspondence. Together with Claim 3.15 (GateVerifier.language_toQuadratic) it turns any Boolean circuit into a quadratic verifier with the same language, for which the main theorems are stated.
Formalization Note: The gate verifier's language is the set of having a valid wire assignment with prefix (GateVerifier.Language); the circuit's language uses the recursive evaluation evalAux.
import Mathlib import Definitions.Def_LatticePrepro_Verifier_Quadratic import Definitions.Def_LatticePrepro_Verifier_Gates import Definitions.Def_LatticePrepro_Verifier_Circuit open LatticePrepro open LatticePrepro.BoolCircuit variable (C : BoolCircuit)
theorem LatticePrepro.BoolCircuit.language_toGateVerifier : C.toGateVerifier.Language = C.Language := by sorry
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.