mirror of
https://github.com/saymrwulf/risc0-ed25519-verified.git
synced 2026-09-03 19:53:45 +00:00
saymrwulf
49a68688c9
This v4.1.x fork implements Scalar52::sub with TWO loops (loop0 = borrow chain; loop1 adds L &&& underflow_mask — the arithmetic-mask constant-time conditional), a genuinely different code path from upstream v5's subtle-based conditional_add_l. Verified per R2 against this fork's own gen: - sub_loop_spec (= loop0): borrow chain, verbatim technique from dalek - sub_loop1_zero_spec / sub_loop1_one_spec: the masked-L add, both mask values (0 / 2^64-1), full carry chains - sub_val_spec: denote(sub a b) = denote a - denote b in ZMod l; the underflow mask um = ((borrow>>>63) XOR 1) - 1 resolved per case - add_loop_spec + add_val_spec: denote(add a b) = denote a + denote b (v4 add_loop extracts token-identical to v5; composition through this fork's own sub_val_spec) check-scalar.sh: full manifest, 5/5 kernel axiom audit [propext, Classical.choice, Quot.sound], green at 300-400s/4096MB. Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
62 lines
3.1 KiB
Text
62 lines
3.1 KiB
Text
/- ──────────────────────────────────────────────────────────────────────────────
|
||
Proofs/ScalarLoop.lean — generic loop-combinator lemmas for the scalar
|
||
layer's `for i in 0..5` reductions (sub_loop, add_loop, conditional_add_l).
|
||
|
||
These three lemmas are identical in statement to the field layer's
|
||
(Proofs/AddSpec.lean); they are about `Aeneas.Std.loop` and the transpiled
|
||
`core::iter::range` iterator, NOT about any field/scalar specifics, so they
|
||
are re-stated here to keep the scalar proofs independent of the field gen.
|
||
────────────────────────────────────────────────────────────────────────────── -/
|
||
import Proofs.ScalarDenote
|
||
open Aeneas Aeneas.Std Result ControlFlow
|
||
open curve25519_dalek
|
||
|
||
namespace ScalarProofs
|
||
|
||
open Aeneas.Std.WP
|
||
|
||
/-- Peel one iteration of the `Aeneas.Std.loop` fixed point under a `spec` goal. -/
|
||
theorem loop_step {α : Type u} {β : Type v}
|
||
{body : α → Result (ControlFlow α β)} {x : α} {post : β → Prop}
|
||
(h : body x ⦃ r => match r with
|
||
| .cont x' => Aeneas.Std.loop body x' ⦃ post ⦄
|
||
| .done y => post y ⦄) :
|
||
Aeneas.Std.loop body x ⦃ post ⦄ := by
|
||
obtain ⟨r, hr, hpost⟩ := spec_imp_exists h
|
||
rw [Aeneas.Std.loop.eq_def, hr]
|
||
cases r <;> simpa using hpost
|
||
|
||
/-- `Iterator::next` on a not-yet-finished `usize` range: yields `some start`
|
||
and advances `start`. -/
|
||
theorem range_next_lt_spec (r : core.ops.range.Range Usize)
|
||
(h : r.start.val < r.«end».val) :
|
||
core.iter.range.IteratorRange.next core.iter.range.StepUsize r
|
||
⦃ (o, r') => o = some r.start ∧ r'.start.val = r.start.val + 1 ∧
|
||
r'.«end» = r.«end» ⦄ := by
|
||
have hmax : r.start.val + 1 ≤ Usize.max := by scalar_tac
|
||
have hca := Usize.checked_add_bv_spec r.start 1#usize
|
||
unfold core.iter.range.IteratorRange.next
|
||
simp only [core.cmp.impls.PartialOrdUsize.lt,
|
||
core.clone.impls.CloneUsize.clone, core.iter.range.StepUsize.forward_checked,
|
||
liftFun1, liftFun2, bind_tc_ok]
|
||
simp only [h, decide_true, if_true]
|
||
cases hadd : Usize.checked_add r.start 1#usize with
|
||
| none => rw [hadd] at hca; simp at hca; scalar_tac
|
||
| some n =>
|
||
rw [hadd] at hca
|
||
simp at hca
|
||
simp [spec_ok, hca]
|
||
|
||
/-- `Iterator::next` on a finished `usize` range: yields `none`, range unchanged. -/
|
||
theorem range_next_ge_spec (r : core.ops.range.Range Usize)
|
||
(h : r.«end».val ≤ r.start.val) :
|
||
core.iter.range.IteratorRange.next core.iter.range.StepUsize r
|
||
⦃ (o, r') => o = none ∧ r' = r ⦄ := by
|
||
unfold core.iter.range.IteratorRange.next
|
||
simp only [core.cmp.impls.PartialOrdUsize.lt,
|
||
core.clone.impls.CloneUsize.clone, core.iter.range.StepUsize.forward_checked,
|
||
liftFun1, liftFun2, bind_tc_ok]
|
||
have : ¬ (r.start.val < r.«end».val) := by omega
|
||
simp [this]
|
||
|
||
end ScalarProofs
|