Artifacts generated from 91fd3397a4a0d1498ca69dedfefa2e4f44752110
Home /
Input Output /
formal-ledger-specifications
May 22, 9-10 PM (0)
May 22, 10-11 PM (0)
May 22, 11-12 AM (0)
May 23, 12-1 AM (0)
May 23, 1-2 AM (0)
May 23, 2-3 AM (0)
May 23, 3-4 AM (0)
May 23, 4-5 AM (0)
May 23, 5-6 AM (0)
May 23, 6-7 AM (0)
May 23, 7-8 AM (0)
May 23, 8-9 AM (0)
May 23, 9-10 AM (0)
May 23, 10-11 AM (0)
May 23, 11-12 PM (0)
May 23, 12-1 PM (0)
May 23, 1-2 PM (0)
May 23, 2-3 PM (0)
May 23, 3-4 PM (0)
May 23, 4-5 PM (0)
May 23, 5-6 PM (0)
May 23, 6-7 PM (0)
May 23, 7-8 PM (0)
May 23, 8-9 PM (0)
May 23, 9-10 PM (0)
May 23, 10-11 PM (0)
May 23, 11-12 AM (0)
May 24, 12-1 AM (0)
May 24, 1-2 AM (0)
May 24, 2-3 AM (0)
May 24, 3-4 AM (0)
May 24, 4-5 AM (0)
May 24, 5-6 AM (0)
May 24, 6-7 AM (0)
May 24, 7-8 AM (0)
May 24, 8-9 AM (0)
May 24, 9-10 AM (0)
May 24, 10-11 AM (0)
May 24, 11-12 PM (0)
May 24, 12-1 PM (0)
May 24, 1-2 PM (0)
May 24, 2-3 PM (0)
May 24, 3-4 PM (0)
May 24, 4-5 PM (0)
May 24, 5-6 PM (0)
May 24, 6-7 PM (0)
May 24, 7-8 PM (0)
May 24, 8-9 PM (0)
May 24, 9-10 PM (0)
May 24, 10-11 PM (0)
May 24, 11-12 AM (0)
May 25, 12-1 AM (0)
May 25, 1-2 AM (0)
May 25, 2-3 AM (0)
May 25, 3-4 AM (0)
May 25, 4-5 AM (0)
May 25, 5-6 AM (0)
May 25, 6-7 AM (0)
May 25, 7-8 AM (0)
May 25, 8-9 AM (3)
May 25, 9-10 AM (0)
May 25, 10-11 AM (0)
May 25, 11-12 PM (0)
May 25, 12-1 PM (0)
May 25, 1-2 PM (0)
May 25, 2-3 PM (0)
May 25, 3-4 PM (0)
May 25, 4-5 PM (0)
May 25, 5-6 PM (0)
May 25, 6-7 PM (0)
May 25, 7-8 PM (0)
May 25, 8-9 PM (0)
May 25, 9-10 PM (0)
May 25, 10-11 PM (0)
May 25, 11-12 AM (0)
May 26, 12-1 AM (0)
May 26, 1-2 AM (0)
May 26, 2-3 AM (0)
May 26, 3-4 AM (0)
May 26, 4-5 AM (0)
May 26, 5-6 AM (0)
May 26, 6-7 AM (4)
May 26, 7-8 AM (5)
May 26, 8-9 AM (0)
May 26, 9-10 AM (1)
May 26, 10-11 AM (0)
May 26, 11-12 PM (0)
May 26, 12-1 PM (0)
May 26, 1-2 PM (1)
May 26, 2-3 PM (7)
May 26, 3-4 PM (0)
May 26, 4-5 PM (0)
May 26, 5-6 PM (0)
May 26, 6-7 PM (0)
May 26, 7-8 PM (0)
May 26, 8-9 PM (0)
May 26, 9-10 PM (0)
May 26, 10-11 PM (0)
May 26, 11-12 AM (0)
May 27, 12-1 AM (0)
May 27, 1-2 AM (0)
May 27, 2-3 AM (0)
May 27, 3-4 AM (1)
May 27, 4-5 AM (0)
May 27, 5-6 AM (0)
May 27, 6-7 AM (0)
May 27, 7-8 AM (0)
May 27, 8-9 AM (0)
May 27, 9-10 AM (1)
May 27, 10-11 AM (0)
May 27, 11-12 PM (0)
May 27, 12-1 PM (0)
May 27, 1-2 PM (0)
May 27, 2-3 PM (0)
May 27, 3-4 PM (0)
May 27, 4-5 PM (0)
May 27, 5-6 PM (0)
May 27, 6-7 PM (0)
May 27, 7-8 PM (0)
May 27, 8-9 PM (0)
May 27, 9-10 PM (1)
May 27, 10-11 PM (1)
May 27, 11-12 AM (0)
May 28, 12-1 AM (0)
May 28, 1-2 AM (1)
May 28, 2-3 AM (0)
May 28, 3-4 AM (0)
May 28, 4-5 AM (3)
May 28, 5-6 AM (0)
May 28, 6-7 AM (0)
May 28, 7-8 AM (0)
May 28, 8-9 AM (0)
May 28, 9-10 AM (1)
May 28, 10-11 AM (0)
May 28, 11-12 PM (2)
May 28, 12-1 PM (1)
May 28, 1-2 PM (13)
May 28, 2-3 PM (4)
May 28, 3-4 PM (0)
May 28, 4-5 PM (0)
May 28, 5-6 PM (0)
May 28, 6-7 PM (12)
May 28, 7-8 PM (2)
May 28, 8-9 PM (1)
May 28, 9-10 PM (0)
May 28, 10-11 PM (0)
May 28, 11-12 AM (22)
May 29, 12-1 AM (3)
May 29, 1-2 AM (1)
May 29, 2-3 AM (1)
May 29, 3-4 AM (0)
May 29, 4-5 AM (0)
May 29, 5-6 AM (0)
May 29, 6-7 AM (0)
May 29, 7-8 AM (0)
May 29, 8-9 AM (0)
May 29, 9-10 AM (1)
May 29, 10-11 AM (0)
May 29, 11-12 PM (0)
May 29, 12-1 PM (0)
May 29, 1-2 PM (0)
May 29, 2-3 PM (0)
May 29, 3-4 PM (0)
May 29, 4-5 PM (0)
May 29, 5-6 PM (0)
May 29, 6-7 PM (0)
May 29, 7-8 PM (0)
May 29, 8-9 PM (0)
May 29, 9-10 PM (0)
93 commits this week
May 22, 2026
-
May 29, 2026
Artifacts generated from b672c29721fcb39f4f32bc1fe923696edb1114da
old version of Ledger PoV
bring forward new helper proofs from earlier PRs
Artifacts generated from 5b33fbb5a62836948ecd0337e4b7dae91c358dd1
Artifacts generated from 914e4f7d4ef502c146d95ad67d5c6041fd8b92c0
Artifacts generated from 41b9d86d56b10fe12861c512106bb91546e2c1fe
Artifacts generated from cdcc0f43bea6b4cc6a63c8901d6b8bc4dc80860f
general clarifications and improvements
Artifacts generated from 6a737fd104fefed2be6c6e8bed1fe1514022f50e
Hoist cert-deposit helpers from Utxo to Certs (#1208)
Move six closed-form cert-deposit helpers from
src/Ledger/Dijkstra/Specification/Utxo.lagda.md to
src/Ledger/Dijkstra/Specification/Certs.lagda.md:
+ updateCertDeposit
+ updateCertDepositsStep (new named extraction of the fold body)
+ updateCertDeposits
+ coinFromDeposits
+ depositsChange
+ newCertDeposits
+ refundCertDeposits
These helpers depend only on Certs-level definitions, so their natural
home is Certs.lagda.md. Their placement in Utxo.lagda.md forced any
proof referencing them to take the larger TransactionStructure /
AbstractFunctions parameter set, blocking proofs in
Certs.Properties.PoV(Lemmas) (parameterised only by GovStructure) from
referring to them.
govProposalsDeposits stays in Utxo.lagda.md — it depends on GovProposal
from Gov.Actions, not on a Certs-level type.
Bundled bug fixes to updateCertDeposits:
+ Typo: DState.deposits was being set from the GState delta instead
of the DState delta.
+ Fold direction: was foldr (right-to-left). CERTS processes certs
left-to-right via BS-ind's head-first decomposition. Changed to
foldl, matching Conway's left-to-right recursion and Dijkstra's
own applyToRewards. Counterexample under foldr:
[delegate c d, dereg c (just d)] on a fresh credential should
leave c ∉ deposits per CERTS, but foldr processes dereg first
(a no-op) then delegate, ending with c ∈ deposits.
updateCertDepositsStep is the inner fold body extracted as a named
function so downstream proofs in Certs.Properties.PoV can state and
use a per-step pots equation about it.
Also: add HasCoin-UTxOState (Utxo.lagda.md) and HasCoin-LedgerState
(Ledger.lagda.md). HasCoin-LedgerState sums UTxO state total, DState
rewards balance, and the three deposit pots via the hoisted
coinFromDeposits — the form needed to balance against the UTXO
batch-balance equation.
Closes #1208.
address PR review comments
fix Conway PoV module to use new lemmas in Ledger.Prelude
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.<...>.
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 proof of Is-just-isPoolRegistered⇒∈-dom
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.
fix Conway modules to use new lemmas in Ledger.Prelude
Add HasCoin-LedgerState and promote coinFromDeposit to top level
Preliminary infrastructure for the LEDGER preservation-of-value proof (#1187). LedgerState contains three coin-bearing components: the UTxO state (fees and donations counted via the existing HasCoin-UTxOState instance), the rewards balance in DState.rewards, and the three deposit pots (stake-key, pool, DRep). The existing HasCoin-CertState instance only counts the rewards balance; the deposit pots have to be added at the LedgerState level for the LEDGER-pov equation to balance. This commit: + Promotes coinFromDeposit from a where-bound helper inside calculateDepositsChange to a top-level definition, so the PoV proof (and any future consumer) can reference it directly. + Adds a HasCoin-LedgerState instance summing UTxO state coin, the rewards balance, and coinFromDeposit applied to the CertState. No semantic change to LEDGER or any other rule.
Fix hs-src build (2)
Remove dead links from readme
Add missing modules to mkdocs.yaml
Illiterate Foreign* modules
Trace imports during build