Home / IntersectMBO / formal-ledger-specifications
Jun 04, 5-6 PM (0)
Jun 04, 6-7 PM (0)
Jun 04, 7-8 PM (0)
Jun 04, 8-9 PM (0)
Jun 04, 9-10 PM (0)
Jun 04, 10-11 PM (0)
Jun 04, 11-12 AM (0)
Jun 05, 12-1 AM (0)
Jun 05, 1-2 AM (0)
Jun 05, 2-3 AM (0)
Jun 05, 3-4 AM (0)
Jun 05, 4-5 AM (0)
Jun 05, 5-6 AM (0)
Jun 05, 6-7 AM (0)
Jun 05, 7-8 AM (0)
Jun 05, 8-9 AM (0)
Jun 05, 9-10 AM (0)
Jun 05, 10-11 AM (0)
Jun 05, 11-12 PM (0)
Jun 05, 12-1 PM (0)
Jun 05, 1-2 PM (0)
Jun 05, 2-3 PM (0)
Jun 05, 3-4 PM (0)
Jun 05, 4-5 PM (0)
Jun 05, 5-6 PM (0)
Jun 05, 6-7 PM (0)
Jun 05, 7-8 PM (0)
Jun 05, 8-9 PM (0)
Jun 05, 9-10 PM (0)
Jun 05, 10-11 PM (0)
Jun 05, 11-12 AM (0)
Jun 06, 12-1 AM (0)
Jun 06, 1-2 AM (0)
Jun 06, 2-3 AM (0)
Jun 06, 3-4 AM (0)
Jun 06, 4-5 AM (0)
Jun 06, 5-6 AM (0)
Jun 06, 6-7 AM (0)
Jun 06, 7-8 AM (0)
Jun 06, 8-9 AM (0)
Jun 06, 9-10 AM (0)
Jun 06, 10-11 AM (0)
Jun 06, 11-12 PM (0)
Jun 06, 12-1 PM (0)
Jun 06, 1-2 PM (0)
Jun 06, 2-3 PM (0)
Jun 06, 3-4 PM (0)
Jun 06, 4-5 PM (0)
Jun 06, 5-6 PM (0)
Jun 06, 6-7 PM (0)
Jun 06, 7-8 PM (0)
Jun 06, 8-9 PM (0)
Jun 06, 9-10 PM (0)
Jun 06, 10-11 PM (0)
Jun 06, 11-12 AM (0)
Jun 07, 12-1 AM (0)
Jun 07, 1-2 AM (0)
Jun 07, 2-3 AM (0)
Jun 07, 3-4 AM (0)
Jun 07, 4-5 AM (0)
Jun 07, 5-6 AM (0)
Jun 07, 6-7 AM (0)
Jun 07, 7-8 AM (0)
Jun 07, 8-9 AM (0)
Jun 07, 9-10 AM (0)
Jun 07, 10-11 AM (0)
Jun 07, 11-12 PM (0)
Jun 07, 12-1 PM (0)
Jun 07, 1-2 PM (0)
Jun 07, 2-3 PM (0)
Jun 07, 3-4 PM (0)
Jun 07, 4-5 PM (0)
Jun 07, 5-6 PM (0)
Jun 07, 6-7 PM (0)
Jun 07, 7-8 PM (0)
Jun 07, 8-9 PM (0)
Jun 07, 9-10 PM (0)
Jun 07, 10-11 PM (0)
Jun 07, 11-12 AM (0)
Jun 08, 12-1 AM (0)
Jun 08, 1-2 AM (0)
Jun 08, 2-3 AM (0)
Jun 08, 3-4 AM (0)
Jun 08, 4-5 AM (0)
Jun 08, 5-6 AM (0)
Jun 08, 6-7 AM (0)
Jun 08, 7-8 AM (0)
Jun 08, 8-9 AM (0)
Jun 08, 9-10 AM (0)
Jun 08, 10-11 AM (0)
Jun 08, 11-12 PM (0)
Jun 08, 12-1 PM (0)
Jun 08, 1-2 PM (0)
Jun 08, 2-3 PM (0)
Jun 08, 3-4 PM (0)
Jun 08, 4-5 PM (0)
Jun 08, 5-6 PM (0)
Jun 08, 6-7 PM (0)
Jun 08, 7-8 PM (0)
Jun 08, 8-9 PM (0)
Jun 08, 9-10 PM (0)
Jun 08, 10-11 PM (0)
Jun 08, 11-12 AM (0)
Jun 09, 12-1 AM (0)
Jun 09, 1-2 AM (0)
Jun 09, 2-3 AM (0)
Jun 09, 3-4 AM (0)
Jun 09, 4-5 AM (0)
Jun 09, 5-6 AM (0)
Jun 09, 6-7 AM (0)
Jun 09, 7-8 AM (8)
Jun 09, 8-9 AM (0)
Jun 09, 9-10 AM (0)
Jun 09, 10-11 AM (0)
Jun 09, 11-12 PM (0)
Jun 09, 12-1 PM (1)
Jun 09, 1-2 PM (0)
Jun 09, 2-3 PM (0)
Jun 09, 3-4 PM (0)
Jun 09, 4-5 PM (0)
Jun 09, 5-6 PM (0)
Jun 09, 6-7 PM (0)
Jun 09, 7-8 PM (0)
Jun 09, 8-9 PM (0)
Jun 09, 9-10 PM (0)
Jun 09, 10-11 PM (0)
Jun 09, 11-12 AM (0)
Jun 10, 12-1 AM (0)
Jun 10, 1-2 AM (0)
Jun 10, 2-3 AM (0)
Jun 10, 3-4 AM (0)
Jun 10, 4-5 AM (0)
Jun 10, 5-6 AM (0)
Jun 10, 6-7 AM (0)
Jun 10, 7-8 AM (0)
Jun 10, 8-9 AM (0)
Jun 10, 9-10 AM (0)
Jun 10, 10-11 AM (0)
Jun 10, 11-12 PM (0)
Jun 10, 12-1 PM (0)
Jun 10, 1-2 PM (0)
Jun 10, 2-3 PM (0)
Jun 10, 3-4 PM (0)
Jun 10, 4-5 PM (0)
Jun 10, 5-6 PM (0)
Jun 10, 6-7 PM (0)
Jun 10, 7-8 PM (0)
Jun 10, 8-9 PM (0)
Jun 10, 9-10 PM (0)
Jun 10, 10-11 PM (0)
Jun 10, 11-12 AM (0)
Jun 11, 12-1 AM (0)
Jun 11, 1-2 AM (0)
Jun 11, 2-3 AM (0)
Jun 11, 3-4 AM (0)
Jun 11, 4-5 AM (0)
Jun 11, 5-6 AM (0)
Jun 11, 6-7 AM (0)
Jun 11, 7-8 AM (0)
Jun 11, 8-9 AM (0)
Jun 11, 9-10 AM (0)
Jun 11, 10-11 AM (0)
Jun 11, 11-12 PM (0)
Jun 11, 12-1 PM (0)
Jun 11, 1-2 PM (0)
Jun 11, 2-3 PM (0)
Jun 11, 3-4 PM (0)
Jun 11, 4-5 PM (0)
Jun 11, 5-6 PM (0)
9 commits this week Jun 04, 2026 - Jun 11, 2026
Gov property #414: state that GA deposits are eventually refunded
Add the statement stub for issue #414 as a CHAIN-level claim in a new
module Ledger.Conway.Specification.Chain.Properties.EventuallyRefunded:

- gaDepositInPot: a governance-action deposit is still held in a chain state
- CHAINStar: reflexive-transitive closure of CHAIN over a list of blocks
- GADepositsEventuallyRefunded: every held GA deposit is eventually removed
  from the deposit pot once the chain progresses past its expiry epoch

The proof is left as future work ("coming soon"). Wire the module into the
Chain.Properties aggregator, list the claim in the properties index, and note
it in the changelog.
Add ENTITIES preservation-of-value
Step 4 of the LEDGER preservation-of-value plan (#1187).  Chains the
three lemmas already proved in steps 2-3 over the single ENTITIES
constructor:

  applyWithdrawals-pov  on (wdrls, r₀)
  CERTS-pov             on the inner ⟦ ... ,CERTS⦈ premise
  applyDirectDeposits-pov on (dd, r₁)

The resulting equation is the value-flow statement for the whole rule:

  getCoin s + getCoin (DirectDepositsOf Γ)
    ≡ getCoin s' + getCoin (WithdrawalsOf Γ)

ENTITIES-pov takes the two per-batch NetworkId witnesses as separate
arguments, mirroring extract-netId's output in the old #1190 LEDGER-pov
proof.  These witnesses are produced at the call site by the
SUBUTXOW/UTXOW step and threaded into ENTITIES-pov from there.

The module ENTITIES-PoV inherits and re-exports the three set/map
parameters of ApplyToRewards-PoV (∪ˡ-lookup-preserve,
sum-map-proj₂≡getCoin, setToList-Unique), to be discharged in a
follow-up.

Also adds a top-level Entities.Properties module that re-exports the
two property submodules, matching the existing Certs.Properties
convention.
Bridge CERTS evolution to closed-form cert-deposit accounting
Adds the per-step and RTC-induction bridging lemmas that prove the actual `CertState` produced by a `CERTS` chain has the same three deposit pots (and hence the same `coinFromDeposits`) as the closed-form `updateCertDeposits` applied to the initial state and the cert list.  This is the cert-deposit half of the `LEDGER-pov` chain; combined with the `posNeg-deposits` cancellation identity, it closes the deposit-accounting equation against the UTXO batch-balance equation.

New proofs (PR branch):

+  `CERT-deposits-updateCertDeposit` in `Certs.Properties.PoVLemmas`.  Per-step, case-split on the `CERT` rule's eight `DCert` constructors; `refl` in seven cases, `POOL-rereg` discharged via the pool-deposit alignment invariant.

+  `CERTS-deposits-updateCertDeposits` in `Certs.Properties.PoV`.  RTC induction mirroring `CERTS-pov`.  Factored through `updateCertDeposit-list`, a pure pot-only `foldl` that is the rule-intrinsic counterpart of `updateCertDeposits`; the bridge `pots-updateCertDeposits` handles the inheritance of non-deposit `CertState` fields.

+  `CERTS-coinFromDeposits-updateCertDeposits`.  Coin projection of the main lemma, immediately usable by `LEDGER-pov`.

Both bridging lemmas are parameterised over (a) two deferred set/map facts (`∪ˡ-singleton-mem-≡`, `Is-just-isPoolRegistered⇒∈-dom`) to be discharged from the standard library; and (b) the pool-deposit alignment invariant `PoolDepositsAligned` plus, for the RTC sibling, its `CERT`-step preservation lemma — both follow by inspection of the `POOL` sub-rules.

Master-touching changes

+  **Bug fix in `updateCertDeposits`**.  Was setting `DState.deposits` to `depositsᵍ` (the `GState` delta) instead of `depositsᵈ`.  The `depositsᵈ` name was bound by destructuring but otherwise unused — almost certainly an unintended typo.

+  **Bug fix in `updateCertDeposits`**.  Was using `foldr`, processing certs right-to-left.  The `CERTS` rule processes certs left-to-right (via `BS-ind`'s head-first decomposition).  For non-commutative cert sequences this is unsound: e.g. `[delegate c keyDeposit, dereg c (just keyDeposit)]` for a fresh credential should end with `c ∉ deposits` per `CERTS`, but `foldr` (which processes the `dereg` on the fresh state first as a no-op, then the `delegate`) ends with `c ∈ deposits`.  Switched to `foldl`.  Conway's `updateCertDeposits` is recursive left-to-right (equivalent to `foldl`); Dijkstra's own `applyToRewards` uses `foldl`.

+  **Refactor**.  Extracted `updateCertDepositsStep` as a named function from `updateCertDeposits`' inner lambda, so that downstream proofs can state and use its per-step pots equation.

+  **Hoist**.  Moved `updateCertDeposit`, `updateCertDeposits`, `coinFromDeposits`, `depositsChange`, `newCertDeposits`, `refundCertDeposits` from `Utxo.lagda.md` to `Certs.lagda.md`.  These depend only on `Certs`-level definitions (`PParams`, `DCert`, `CertState`); the previous location forced any proof referencing them to take the larger `TransactionStructure` / `AbstractFunctions` parameter set, blocking placement of the bridging lemmas in `Certs.Properties.PoV{,Lemmas}`.  `govProposalsDeposits` remains in `Utxo.lagda.md` (depends on `GovProposal`).

PR-branch-only changes:

+  `Ledger.lagda.md`. Replaced the local `coinFromDeposit` (singular) with the hoisted `coinFromDeposits` (plural).  `HasCoin-LedgerState` has three summands: `getCoin(UTxOState) + rewardsBalance(DState) + coinFromDeposits(CertState)`.  Gov-action deposits are stored in `GState.deposits` (keyed by `returnAddr`'s stake credential) and are therefore already counted by the third summand.
new helpers in Ledger.Prelude and Certs PoV
+  Add singleton/union/sum lemmas to Ledger.Prelude

   Foundational identities used by the Dijkstra preservation-of-value
   proofs (#1187) and likely useful elsewhere.  All are stated at the
   generic `A ⇀ Coin` (or `List A`) level and are independent of any
   ledger-era rule.

   Added definitions:

   +  ≡ᵉ-getCoin, getCoin-cong, indexedSumᵛ'-∪, res-decomp: lift the
      abstract-set-theory equational machinery (≡ᵉ, indexedSum-cong,
      indexedSumᵐ-∪) to the `getCoin` interface.
   +  getCoin-singleton, ∪ˡsingleton∈dom, ∪ˡsingleton∉dom, ∪ˡsingleton0≡:
      left-biased union with a single-entry map, with the zero-valued
      specialisation that arises in DELEG-delegate / DELEG-dereg.
   +  sumConstZero, indexedSumL-proj₂-zero, setToList-∈: small list/set
      bookkeeping used by sumConstZero.
   +  sum-map-+, +-interleave: list-of-ℕ algebra that the eventual
      LEDGER-pov chain will use to interleave summands.
   +  dec-de-morgan: de Morgan rewrite for a decidable conjunction.

   No semantic change to any ledger rule.

+  Add Certs preservation-of-value lemmas for Dijkstra

   Step 2 of the LEDGER preservation-of-value plan (#1187).  In Dijkstra
   (post-#1201), CERTS is the plain reflexive-transitive closure of CERT,
   with withdrawal and direct-deposit handling having migrated to the
   surrounding ENTITIES rule.  Consequently the value-preservation
   statement for CERTS reduces to

      getCoin s ≡ getCoin s'

   This commit adds two new modules:

   +  Certs.Properties.PoVLemmas: the per-step lemma CERT-pov, with all
      four sub-rule cases (CERT-deleg DELEG-delegate, CERT-deleg
      DELEG-dereg, CERT-pool, CERT-gov).  The proofs use the
      singleton/union helpers now in Ledger.Prelude.
   +  Certs.Properties.PoV: the closure-level CERTS-pov, by induction on
      the reflexive-transitive closure using CERT-pov at each step.

   A one-line addition to Certs/Properties.lagda.md re-exports both new
   modules from the top-level Properties namespace.

   No parameterised wrapper modules.  Both lemmas are top-level
   definitions and threading-free for consumers.
Add applyWithdrawals-pov and applyDirectDeposits-pov
Step 3 of the LEDGER preservation-of-value plan (#1187).

These two lemmas describe the value flow through the per-transaction
withdrawal and direct-deposit handling that bracket the inner CERTS
step inside the new ENTITIES rule (#1201):

+  applyWithdrawals-pov: getCoin rwds ≡ getCoin (applyWithdrawals w r) + getCoin w
+  applyDirectDeposits-pov: getCoin (applyDirectDeposits d r) ≡ getCoin r + getCoin d

Both are proved by induction over setToList of the underlying
RewardAddress ⇀ Coin map, with a per-step lemma about applyOne (the
lambda body of applyToRewards) at each inductive step.

The withdrawal version requires the per-batch NetworkId witness and a
Unique-on-stake-projection invariant on the remaining fold list,
because truncating subtraction (_∸_) means an already-reduced balance
must never be revisited.  The direct-deposit version drops both --
addition is total and commutative, so a re-visit is harmless -- and
the resulting signature is correspondingly leaner.

The module ApplyToRewards-PoV is parameterised over three set/map
identities to be discharged in a follow-up:

+  ∪ˡ-lookup-preserve
+  sum-map-proj₂≡getCoin
+  setToList-Unique  (used only by applyWithdrawals-pov)

File location reflects the post-#1201 home of applyWithdrawals and
applyDirectDeposits: Entities.Specification.<...>, not
Certs.Specification.<...>.