verified

    Download zip
    Version
    0.0.3
    License
    Apache-2.0
    Last updated
    last month
    Downloads
    1K

    No dependencies

    #MoonBit Verified Examples

    This repository collects MoonBit packages that use the experimental moon prove command to verify contracts, loop invariants, and data-structure properties through Why3-backed SMT solving.

    The project is organized into reusable proof support, verified data structures, compact proof demos, and finance-oriented case studies.

    #Running

    Verify every package:

    moon prove

    Run executable tests:

    moon test

    CI uses a checked-in .github/why3.conf with Alt-Ergo, Z3, and CVC5. Local moon prove also generates proof reports under _build/verif/.

    #Package Layout

    • libs/* contains low-level proof support packages used by other packages.
    • Top-level data-structure packages are the main reusable verified libraries.
    • examples/demos/* contains compact proof exercises and algorithm examples.
    • examples/finance/* contains larger finance-specific case studies.

    #Core Proof Libraries

    These packages provide reusable logical models, proof shims, or low-level bridges used by other packages.

    PackageRole
    libs/mathintMathematical integer helpers
    libs/seqSequence model imports and operations
    libs/fsetFinite-set model imports and operations
    libs/fmapFinite-map model imports and operations
    libs/readonlyarrayRead-only array model bridge
    libs/bv3232-bit bitvector model bridge
    libs/bitmap32UInt/bitmap bridge helpers
    libs/bytesByte-oriented proof support

    #Verified Data Structures

    These packages expose data-structure APIs with representation invariants and semantic model postconditions.

    PackageWhat it verifies
    vectorPersistent vector operations against a sequence model
    sparse_arrayBitmap-backed sparse array against a finite-map model
    avlAVL tree balancing, insertion, deletion, and set model preservation
    leftist_heapHeap merge and minimum invariants
    skew_heapHeap merge and minimum invariants
    pairing_heapPairing heap structure and heap-order properties
    stack_minStack operations with tracked minimum

    #Algorithm Demos

    These packages are compact verification examples for proof patterns, loop invariants, binary-search invariants, quantified assertions, and arithmetic facts.

    PackageWhat it demonstrates
    examples/demos/absBranch-only arithmetic postconditions
    examples/demos/clampRange-bounded branch logic
    examples/demos/maxfnMaximum of two integers
    examples/demos/maxarrMaximum-element index with quantified array bounds
    examples/demos/findLinear search
    examples/demos/countCounting elements satisfying a predicate
    examples/demos/gaussClosed-form sum of 1..n
    examples/demos/two_sumPair search over arrays
    examples/demos/binary_searchOption-returning binary search
    examples/demos/lowerboundLower-bound binary search with quantified invariants
    examples/demos/invpredBinary search using a named invariant predicate
    examples/demos/isqrtInteger square root via binary search
    examples/demos/divInteger division via binary search
    examples/demos/bubble_sortSorting loop invariants
    examples/demos/selection_sortSorting loop invariants
    examples/demos/checksortedRelating a boolean flag to a quantified sortedness property
    examples/demos/arreqTwo-array equality
    examples/demos/sumboundsArray sum bounded by element range
    examples/demos/cauchy_schwarzArithmetic inequality proof
    examples/demos/bmh_bytesByte-string search proof patterns

    #Finance Case Studies

    These packages model finance, custody, auction, and risk-control workflows. For more detail, see examples/finance/README.md.

    PackageWhat it verifies
    examples/finance/stablecoin_engineMint/repay/withdraw/liquidate flows with bad-debt handling
    examples/finance/margin_engineLiquidation boundary, funding impact, and deleveraging logic
    examples/finance/clearinghouse_waterfallMulti-layer default waterfall accounting
    examples/finance/bridge_custodyReplay-safe bridge withdrawals
    examples/finance/cpmm_swapFee-adjusted constant-product AMM swap math
    examples/finance/ltv_lendingSolvency-preserving lending operations
    examples/finance/batch_auctionUniform-price batch-auction frontier search
    examples/finance/risk_limitsEarliest-breach risk monitor
    examples/finance/vesting_streamBounded token vesting and release logic
    examples/finance/threshold_multisigThreshold execution via counted approvals