Artifacts generated from c246fae99dd1bd472bbe79a8c220b76865de12aa
Home /
Input Output /
formal-ledger-specifications
Jun 09, 12-1 PM (1)
Jun 09, 1-2 PM (1)
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)
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)
15 commits this week
Jun 09, 2026
-
Jun 16, 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
Artifacts generated from 90f4c41e7f7faa587182077f3d100556caeadd83
Gov property #417: state that a voter's last vote is applied to the GA
Add the statement stub for issue #417 in a new module
Ledger.Conway.Specification.Gov.Properties.LastVoteApplied:
- votedOn / lookupGAState / recordedVote: read back the vote a voter has
recorded on a governance action in a GovState
- lastVoteOn: the last vote a voter casts on an action in a block
- vote-applied-to-GA: a single GOV vote step records the cast vote (base case)
- last-vote-applied-to-GA: over a block (GOVS), the last vote a voter casts on
an action is the one recorded in the resulting state
The proof is left as future work ("coming soon"). Wire the module into the
Gov.Properties aggregator, list the claim in the properties index, and note it
in the changelog.