Claim #10 — Verification of crc::Crc<u128, Table<1>>::new (with Aeneas be86ab0f1989d04944292b345b24c435be3ad10a)

crc::Crc<u128, Table<1>>::new

Recorded callable · signature and safety not independently recorded.

Tool: Aeneas be86ab0f1989d04944292b345b24c435be3ad10a

This claim has no explanation of its own. Read the report Overview, and treat the formal statement below as authoritative. See Concepts and terminology.

Preconditions

1 <= algorithm.width = w <= 128; raw polynomial = zero-extended width-w poly; arbitrary init/xorout and both flags; constructor preserves algorithm and establishes current table coherence

Formal statement

CrcPartialConstructor128.new_table1

for alla : CrcBody.crc_catalog.Algorithm Aeneas.Std.U128

for allpoly : BitVec ↑a.width

assumehw : 1 ≤ ↑a.width ∧ ↑a.width ≤ 128

assumehp : a.poly.bv = BitVec.setWidth 128 poly

then∃ out, CrcBody.crc128.CrcU128Table.new 1#usize a = Aeneas.Std.Result.ok out ∧ out.algorithm = a ∧ CrcPartial128.Coherent out poly

In Lean notation, ↑ denotes an implicit type conversion (coercion).

Complete Lean proposition

∀ (a : CrcBody.crc_catalog.Algorithm.{0} Aeneas.Std.U128)
  (poly :
    BitVec
      (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8 (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U128 a)))
  (hw :
    And
      (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
        (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8 (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U128 a)))
      (@LE.le.{0} Nat instLENat
        (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8 (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U128 a))
        (@OfNat.ofNat.{0} Nat (nat_lit 128) (instOfNatNat (nat_lit 128)))))
  (hp :
    @Eq.{1} (BitVec (@OfNat.ofNat.{0} Nat (nat_lit 128) (instOfNatNat (nat_lit 128))))
      (Aeneas.Std.U128.bv (@CrcBody.crc_catalog.Algorithm.poly.{0} Aeneas.Std.U128 a))
      (@BitVec.setWidth
        (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8 (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U128 a))
        (@OfNat.ofNat.{0} Nat (nat_lit 128) (instOfNatNat (nat_lit 128))) poly)),
  @Exists.{1} CrcPublic128.Crc128 fun (out : CrcPublic128.Crc128) =>
    And
      (@Eq.{1}
        (Aeneas.Std.Result.{0}
          (CrcBody.Crc.{0, 0, 0} Aeneas.Std.U128
            (CrcBody.Table
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                (@of_decide_eq_true
                  (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (@id.{0}
                    (@Eq.{1} Bool
                      (@Decidable.decide
                        (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                        (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize)))
                      Bool.true)
                    (@Eq.refl.{1} Bool Bool.true)))))
            (Aeneas.Std.Array.{0}
              (Aeneas.Std.Array.{0} Aeneas.Std.U128
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                  CrcBody.table.crc128_table_loop0.body._proof_1))
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                (@of_decide_eq_true
                  (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (@id.{0}
                    (@Eq.{1} Bool
                      (@Decidable.decide
                        (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                        (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize)))
                      Bool.true)
                    (@Eq.refl.{1} Bool Bool.true)))))))
        (CrcBody.crc128.CrcU128Table.new
          (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
            (@of_decide_eq_true
              (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
              (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
              (@id.{0}
                (@Eq.{1} Bool
                  (@Decidable.decide
                    (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                      (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                    (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                      (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize)))
                  Bool.true)
                (@Eq.refl.{1} Bool Bool.true))))
          a)
        (@Aeneas.Std.Result.ok.{0}
          (CrcBody.Crc.{0, 0, 0} Aeneas.Std.U128
            (CrcBody.Table
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                (@of_decide_eq_true
                  (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (@id.{0}
                    (@Eq.{1} Bool
                      (@Decidable.decide
                        (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                        (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize)))
                      Bool.true)
                    (@Eq.refl.{1} Bool Bool.true)))))
            (Aeneas.Std.Array.{0}
              (Aeneas.Std.Array.{0} Aeneas.Std.U128
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                  CrcBody.table.crc128_table_loop0.body._proof_1))
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                (@of_decide_eq_true
                  (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                    (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                  (@id.{0}
                    (@Eq.{1} Bool
                      (@Decidable.decide
                        (@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize))
                        (Nat.decLe (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                          (Aeneas.Std.UScalar.cMax Aeneas.Std.UScalarTy.Usize)))
                      Bool.true)
                    (@Eq.refl.{1} Bool Bool.true))))))
          out))
      (And
        (@Eq.{1} (CrcBody.crc_catalog.Algorithm.{0} Aeneas.Std.U128)
          (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U128
            (CrcBody.Table
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
                CrcPublic128.Crc128._proof_1))
            CrcUpdate128.Table out)
          a)
        (@CrcPartial128.Coherent
          (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8 (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U128 a))
          out poly))

Theorem source at recorded commit · Recorded check

Referenced definitions (up to 100 direct references)

CrcBody.crc_catalog.Algorithm
Aeneas.Std.U128 · Aeneas.Std.Scalar.Core
BitVec · Init.Prelude
Aeneas.Std.UScalar.val · Aeneas.Std.Scalar.Core
Aeneas.Std.UScalarTy.U8 · Aeneas.Std.Scalar.Core
CrcBody.crc_catalog.Algorithm.width
And · Init.Prelude
LE.le · Init.Prelude
Nat · Init.Prelude
instLENat · Init.Prelude
OfNat.ofNat · Init.Prelude
instOfNatNat · Init.Prelude
Eq · Init.Prelude
Aeneas.Std.U128.bv · Aeneas.Std.Scalar.Core
CrcBody.crc_catalog.Algorithm.poly
BitVec.setWidth · Init.Data.BitVec.Basic
Exists · Init.Core
CrcPublic128.Crc128
Aeneas.Std.Result · Aeneas.Std.Primitives
CrcBody.Crc
CrcBody.Table
Aeneas.Std.Usize.ofNat · Aeneas.Std.Scalar.Core
of_decide_eq_true · Init.Prelude
Aeneas.Std.UScalar.cMax · Aeneas.Std.Scalar.Core
Aeneas.Std.UScalarTy.Usize · Aeneas.Std.Scalar.Core
Nat.decLe · Init.Prelude
id · Init.Prelude
Bool · Init.Prelude
Decidable.decide · Init.Prelude
Bool.true · Init.Prelude
Eq.refl · Init.Prelude
Aeneas.Std.Array · Aeneas.Std.Array.Array
CrcBody.table.crc128_table_loop0.body._proof_1 · CrcBody.Funs
CrcBody.crc128.CrcU128Table.new
Aeneas.Std.Result.ok · Aeneas.Std.Primitives
CrcBody.Crc.algorithm
CrcPublic128.Crc128._proof_1 · Stage2Proofs.Public128
CrcUpdate128.Table
CrcPartial128.Coherent

Mapping: manual. Translation was not rerun by this recording.

Evidence

https://github.com/keiichiw/crate-proofs/blob/d0358890f8bdc8e72a376d225667ac162f89e3b8/crc/3.4.0/aeneas/profiles/stage2/proofs/Stage2Proofs/PartialConstructor128.lean#L18-L66

What is trusted

From the report

The results depend on Rust-to-LLBC translation (LLBC is the intermediate representation consumed by Aeneas), Aeneas translation, primitive models, and the Lean kernel. Local bit-reversal definitions are assumed to match Rust's standard operations.

Reference model. The model feeds each byte in input-reflection order, applies output reflection and XOR at the end, and appends no zero block.

The proofs concern the translated program after three transformations used to normalize types and names and make source file references portable. If these transformations changed behavior, the proofs could describe a different program. Structural checks support their correspondence to the original translation, but do not formally prove it:

Type-only normalization lifts the built-in table associated type to the exact array type. An independent checker compares function bodies and permits only the specified type-reference changes; negative guards reject unsupported normalization shapes.
A display-name change preserves indices and operations.
File-name relocation is checked by inverse equality of the complete JSON tree.

These checks are not semantic-preservation or compiler-correctness proofs. The transitive audit permits only propext, Classical.choice, and Quot.sound.

Technical limitations

From the report

Conditions for users. Algorithm fields are public, so Rust types do not rule out invalid widths or out-of-range parameters. The public algorithm field of Crc can be replaced after construction, potentially leaving a stale cache. In addition to the parameter conditions, Table<1> checksum and update require the current table to be coherent with the current algorithm; construction alone does not establish coherence after a change. Table<0> has no cached-table coherence requirement.

Not covered. Table<16> checksum and update over message bytes, custom implementations, other lanes and re-exported dependency APIs are outside this coverage. The proofs do not validate catalogue check or residue values.

The selected executable crate bodies come from the locked crates.io 3.4.0 archive. The existing Rust-to-Lean translation (not rerun in this recording) uses the described transformations and locally authored bit-reversal models; their correspondence to release execution is supported by structural checks and native observations, not a formal equivalence theorem.

Tool limitations

Lean backend only, requiring cargo-proofs 0.4.0 or later. The version identifies the official Aeneas Git revision pinned in lake-manifest.json (backends/lean); this revision uses Lean 4.35.0. The recorder checks committed Lean theorem declarations and permits only propext, Classical.choice, and Quot.sound as transitive axioms. It rejects sorryAx and custom axioms, including axiomatized external models. Charon/Aeneas extraction is not rerun. The author must review that the committed functional model matches the recorded Rust source, that the named theorem corresponds to the public API, and that the reported precondition matches the theorem. A checked theorem alone does not establish those links or the adequacy of the specification. The current adapter records the default Cargo configuration, with ordinary Lean module paths and a pinned official Git dependency. Other backends, custom Lake source directories, and local-path Aeneas dependencies are unsupported. See https://proofs.rs/book/aeneas.html and https://github.com/AeneasVerif/aeneas/tree/be86ab0f1989d04944292b345b24c435be3ad10a.

Updated 2026-10-16 00:00 UTC

Aeneas be86ab0f1989d04944292b345b24c435be3ad10a — version details

Read and join the discussion on the report →