proofs.rs

Claim #11 — Verification of crc::Crc<u16, Table<0>>::checksum (with Aeneas be86ab0f1989d04944292b345b24c435be3ad10a)

crc::Crc<u16, Table<0>>::checksum

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 <= current algorithm.width = w <= 16; raw polynomial = zero-extended width-w poly; raw xorout = zero-extended width-w xorout; arbitrary raw init interpreted by low w bits; both flags arbitrary; any representable byte slice including empty

Formal statement

CrcPartialNoTableConstructors.checksum16

for allself : CrcPartialNoTableConstructors.NoCrc16
for allbytes : Aeneas.Std.Slice Aeneas.Std.U8
for allpoly : BitVec ↑self.algorithm.width
for allxorout : BitVec ↑self.algorithm.width
assumehw : 1 ≤ ↑self.algorithm.width ∧ ↑self.algorithm.width ≤ 16
assumehp : self.algorithm.poly.bv = BitVec.setWidth 16 poly
assumehx : self.algorithm.xorout.bv = BitVec.setWidth 16 xorout
then∃ out, CrcBody.crc16.CrcU16Table.checksum self bytes = Aeneas.Std.Result.ok out ∧ out.bv = BitVec.setWidth 16 (CrcPartialSpec.checksum self.algorithm.refin self.algorithm.refout poly (BitVec.setWidth (↑self.algorithm.width) self.algorithm.init.bv) xorout (List.map Aeneas.Std.UScalar.bv ↑bytes))

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

Complete Lean proposition
∀ (self : CrcPartialNoTableConstructors.NoCrc16) (bytes : Aeneas.Std.Slice.{0} Aeneas.Std.U8)
  (poly xorout :
    BitVec
      (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8
        (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U16
          (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
            (CrcBody.Table
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                CrcPartialNoTableConstructors.NoCrc8._proof_1))
            (Aeneas.Std.Array.{0}
              (Aeneas.Std.Array.{0} Aeneas.Std.U16
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_2))
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                CrcPartialNoTableConstructors.NoCrc8._proof_1))
            self))))
  (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.U16
            (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
              (CrcBody.Table
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              (Aeneas.Std.Array.{0}
                (Aeneas.Std.Array.{0} Aeneas.Std.U16
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_2))
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              self))))
      (@LE.le.{0} Nat instLENat
        (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8
          (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U16
            (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
              (CrcBody.Table
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              (Aeneas.Std.Array.{0}
                (Aeneas.Std.Array.{0} Aeneas.Std.U16
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_2))
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              self)))
        (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16)))))
  (hp :
    @Eq.{1} (BitVec (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16))))
      (Aeneas.Std.U16.bv
        (@CrcBody.crc_catalog.Algorithm.poly.{0} Aeneas.Std.U16
          (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
            (CrcBody.Table
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                CrcPartialNoTableConstructors.NoCrc8._proof_1))
            (Aeneas.Std.Array.{0}
              (Aeneas.Std.Array.{0} Aeneas.Std.U16
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_2))
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                CrcPartialNoTableConstructors.NoCrc8._proof_1))
            self)))
      (@BitVec.setWidth
        (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8
          (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U16
            (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
              (CrcBody.Table
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              (Aeneas.Std.Array.{0}
                (Aeneas.Std.Array.{0} Aeneas.Std.U16
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_2))
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              self)))
        (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16))) poly))
  (hx :
    @Eq.{1} (BitVec (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16))))
      (Aeneas.Std.U16.bv
        (@CrcBody.crc_catalog.Algorithm.xorout.{0} Aeneas.Std.U16
          (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
            (CrcBody.Table
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                CrcPartialNoTableConstructors.NoCrc8._proof_1))
            (Aeneas.Std.Array.{0}
              (Aeneas.Std.Array.{0} Aeneas.Std.U16
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_2))
              (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                CrcPartialNoTableConstructors.NoCrc8._proof_1))
            self)))
      (@BitVec.setWidth
        (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8
          (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U16
            (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
              (CrcBody.Table
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              (Aeneas.Std.Array.{0}
                (Aeneas.Std.Array.{0} Aeneas.Std.U16
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_2))
                (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                  CrcPartialNoTableConstructors.NoCrc8._proof_1))
              self)))
        (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16))) xorout)),
  @Exists.{1} Aeneas.Std.U16 fun (out : Aeneas.Std.U16) =>
    And
      (@Eq.{1} (Aeneas.Std.Result.{0} Aeneas.Std.U16)
        (@CrcBody.crc16.CrcU16Table.checksum
          (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
            CrcPartialNoTableConstructors.NoCrc8._proof_1)
          self bytes)
        (@Aeneas.Std.Result.ok.{0} Aeneas.Std.U16 out))
      (@Eq.{1} (BitVec (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16)))) (Aeneas.Std.U16.bv out)
        (@BitVec.setWidth
          (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8
            (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U16
              (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
                (CrcBody.Table
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_1))
                (Aeneas.Std.Array.{0}
                  (Aeneas.Std.Array.{0} Aeneas.Std.U16
                    (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                      CrcPartialNoTableConstructors.NoCrc8._proof_2))
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_1))
                self)))
          (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16)))
          (@CrcPartialSpec.checksum
            (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8
              (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U16
                (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
                  (CrcBody.Table
                    (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                      CrcPartialNoTableConstructors.NoCrc8._proof_1))
                  (Aeneas.Std.Array.{0}
                    (Aeneas.Std.Array.{0} Aeneas.Std.U16
                      (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                        CrcPartialNoTableConstructors.NoCrc8._proof_2))
                    (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                      CrcPartialNoTableConstructors.NoCrc8._proof_1))
                  self)))
            (@CrcBody.crc_catalog.Algorithm.refin.{0} Aeneas.Std.U16
              (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
                (CrcBody.Table
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_1))
                (Aeneas.Std.Array.{0}
                  (Aeneas.Std.Array.{0} Aeneas.Std.U16
                    (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                      CrcPartialNoTableConstructors.NoCrc8._proof_2))
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_1))
                self))
            (@CrcBody.crc_catalog.Algorithm.refout.{0} Aeneas.Std.U16
              (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
                (CrcBody.Table
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_1))
                (Aeneas.Std.Array.{0}
                  (Aeneas.Std.Array.{0} Aeneas.Std.U16
                    (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                      CrcPartialNoTableConstructors.NoCrc8._proof_2))
                  (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                    CrcPartialNoTableConstructors.NoCrc8._proof_1))
                self))
            poly
            (@BitVec.setWidth (@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16)))
              (@Aeneas.Std.UScalar.val Aeneas.Std.UScalarTy.U8
                (@CrcBody.crc_catalog.Algorithm.width.{0} Aeneas.Std.U16
                  (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
                    (CrcBody.Table
                      (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                        CrcPartialNoTableConstructors.NoCrc8._proof_1))
                    (Aeneas.Std.Array.{0}
                      (Aeneas.Std.Array.{0} Aeneas.Std.U16
                        (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                          CrcPartialNoTableConstructors.NoCrc8._proof_2))
                      (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                        CrcPartialNoTableConstructors.NoCrc8._proof_1))
                    self)))
              (Aeneas.Std.U16.bv
                (@CrcBody.crc_catalog.Algorithm.init.{0} Aeneas.Std.U16
                  (@CrcBody.Crc.algorithm.{0, 0, 0} Aeneas.Std.U16
                    (CrcBody.Table
                      (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                        CrcPartialNoTableConstructors.NoCrc8._proof_1))
                    (Aeneas.Std.Array.{0}
                      (Aeneas.Std.Array.{0} Aeneas.Std.U16
                        (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 256) (instOfNatNat (nat_lit 256)))
                          CrcPartialNoTableConstructors.NoCrc8._proof_2))
                      (Aeneas.Std.Usize.ofNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))
                        CrcPartialNoTableConstructors.NoCrc8._proof_1))
                    self))))
            xorout
            (@List.map.{0, 0} Aeneas.Std.U8 (BitVec (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))))
              (@Aeneas.Std.UScalar.bv Aeneas.Std.UScalarTy.U8) (@Aeneas.Std.Slice.val.{0} Aeneas.Std.U8 bytes)))))

Theorem source at recorded commit · Recorded check

Referenced definitions (up to 100 direct references)

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/PartialNoTableConstructors.lean#L240-L258

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 →