Artifacts generated from c246fae99dd1bd472bbe79a8c220b76865de12aa
Home /
Input Output /
formal-ledger-specifications
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)
Jun 11, 6-7 PM (0)
Jun 11, 7-8 PM (0)
Jun 11, 8-9 PM (0)
Jun 11, 9-10 PM (0)
Jun 11, 10-11 PM (0)
Jun 11, 11-12 AM (0)
Jun 12, 12-1 AM (0)
Jun 12, 1-2 AM (0)
Jun 12, 2-3 AM (0)
Jun 12, 3-4 AM (0)
Jun 12, 4-5 AM (0)
Jun 12, 5-6 AM (0)
Jun 12, 6-7 AM (0)
Jun 12, 7-8 AM (0)
Jun 12, 8-9 AM (0)
Jun 12, 9-10 AM (0)
Jun 12, 10-11 AM (0)
Jun 12, 11-12 PM (0)
Jun 12, 12-1 PM (0)
Jun 12, 1-2 PM (0)
Jun 12, 2-3 PM (0)
Jun 12, 3-4 PM (0)
Jun 12, 4-5 PM (0)
Jun 12, 5-6 PM (0)
Jun 12, 6-7 PM (0)
Jun 12, 7-8 PM (0)
Jun 12, 8-9 PM (0)
Jun 12, 9-10 PM (0)
Jun 12, 10-11 PM (0)
Jun 12, 11-12 AM (0)
Jun 13, 12-1 AM (0)
Jun 13, 1-2 AM (0)
Jun 13, 2-3 AM (0)
Jun 13, 3-4 AM (0)
Jun 13, 4-5 AM (0)
Jun 13, 5-6 AM (0)
Jun 13, 6-7 AM (0)
Jun 13, 7-8 AM (0)
Jun 13, 8-9 AM (0)
Jun 13, 9-10 AM (0)
Jun 13, 10-11 AM (0)
Jun 13, 11-12 PM (0)
Jun 13, 12-1 PM (0)
Jun 13, 1-2 PM (0)
Jun 13, 2-3 PM (0)
Jun 13, 3-4 PM (0)
Jun 13, 4-5 PM (0)
Jun 13, 5-6 PM (0)
Jun 13, 6-7 PM (0)
Jun 13, 7-8 PM (0)
Jun 13, 8-9 PM (0)
Jun 13, 9-10 PM (0)
Jun 13, 10-11 PM (0)
Jun 13, 11-12 AM (0)
Jun 14, 12-1 AM (0)
Jun 14, 1-2 AM (0)
Jun 14, 2-3 AM (0)
Jun 14, 3-4 AM (0)
Jun 14, 4-5 AM (0)
Jun 14, 5-6 AM (0)
Jun 14, 6-7 AM (0)
Jun 14, 7-8 AM (0)
Jun 14, 8-9 AM (0)
Jun 14, 9-10 AM (0)
Jun 14, 10-11 AM (0)
Jun 14, 11-12 PM (0)
Jun 14, 12-1 PM (0)
Jun 14, 1-2 PM (0)
Jun 14, 2-3 PM (0)
Jun 14, 3-4 PM (0)
Jun 14, 4-5 PM (0)
Jun 14, 5-6 PM (0)
Jun 14, 6-7 PM (0)
Jun 14, 7-8 PM (0)
Jun 14, 8-9 PM (0)
Jun 14, 9-10 PM (0)
Jun 14, 10-11 PM (0)
Jun 14, 11-12 AM (0)
Jun 15, 12-1 AM (0)
Jun 15, 1-2 AM (0)
Jun 15, 2-3 AM (0)
Jun 15, 3-4 AM (0)
Jun 15, 4-5 AM (0)
Jun 15, 5-6 AM (0)
Jun 15, 6-7 AM (0)
Jun 15, 7-8 AM (0)
Jun 15, 8-9 AM (0)
Jun 15, 9-10 AM (0)
Jun 15, 10-11 AM (0)
Jun 15, 11-12 PM (0)
Jun 15, 12-1 PM (0)
Jun 15, 1-2 PM (0)
Jun 15, 2-3 PM (0)
Jun 15, 3-4 PM (0)
Jun 15, 4-5 PM (0)
Jun 15, 5-6 PM (0)
Jun 15, 6-7 PM (0)
Jun 15, 7-8 PM (0)
Jun 15, 8-9 PM (0)
Jun 15, 9-10 PM (12)
Jun 15, 10-11 PM (1)
Jun 15, 11-12 AM (0)
Jun 16, 12-1 AM (0)
Jun 16, 1-2 AM (0)
Jun 16, 2-3 AM (0)
Jun 16, 3-4 AM (0)
Jun 16, 4-5 AM (0)
Jun 16, 5-6 AM (0)
Jun 16, 6-7 AM (0)
Jun 16, 7-8 AM (0)
Jun 16, 8-9 AM (0)
Jun 16, 9-10 AM (0)
Jun 16, 10-11 AM (0)
Jun 16, 11-12 PM (0)
Jun 16, 12-1 PM (0)
Jun 16, 1-2 PM (0)
Jun 16, 2-3 PM (0)
Jun 16, 3-4 PM (0)
Jun 16, 4-5 PM (0)
Jun 16, 5-6 PM (0)
Jun 16, 6-7 PM (0)
Jun 16, 7-8 PM (0)
Jun 16, 8-9 PM (0)
Jun 16, 9-10 PM (0)
Jun 16, 10-11 PM (0)
Jun 16, 11-12 AM (0)
Jun 17, 12-1 AM (0)
Jun 17, 1-2 AM (0)
Jun 17, 2-3 AM (0)
13 commits this week
Jun 10, 2026
-
Jun 17, 2026
Add Certs PoV: per-step ≡ᵐᵗ + coin bridges, RTC lift
New modules under src/Ledger/Dijkstra/Specification/Certs/Properties/: + PoVLemmas.lagda.md (CERT-level) + PoV.lagda.md (CERTS-level) PoVLemmas exports: + CERT-pov: preservation of value at one CERT step + CERT-pots-≡ᵐᵗ: per-step ≡ᵐ-componentwise triple bridge + CERT-coinFromDeposits-step: per-step coin bridge (derived) + Triple machinery: pots, coinFromDeposits-pots, updateCertDeposit-list, pots-updateCertDeposits + PoolDepositsAligned, Is-just-isPoolRegistered⇒∈-dom PoV exports a bundled Certs-PoV module parameterised by indexedSumᵛ'-∪ and PoolDepositsAligned-CERT, providing: + CERTS-pov: preservation across the closure + CERTS-Deposits-Bridge.CERTS-coinFromDeposits-updateCertDeposits: the closed-form coin bridge consumed by LEDGER-pov The triple-form per-step bridge from the previous Ledger-PoV branch required a deferred propositional equation m ∪ˡ ❴ k , v ❵ ≡ m (when k ∈ dom m). This PR drops that parameter, using instead the upstream ≡ᵐ-componentwise singleton-∈-∪ˡ plumbed through the closed form via ∪⁺-cong-r, ∪ˡ-cong, restrict-cong, and collapsed to a coin equality via ≡ᵉ-getCoin. Refs #1185
adopt Ledger.Prelude helper lemmas from earlier PR
Artifacts generated from 70b38f1e313b18d831d5bd41128b2c97874122c4
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.
add proof of Is-just-isPoolRegistered⇒∈-dom
old version of Ledger PoV
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.<...>.
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.
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.
fix Conway PoV module to use new lemmas in Ledger.Prelude
fix Conway modules to use new lemmas in Ledger.Prelude