Ledger state and rules

Ledger state and rules

Upcoming. This page describes the ledger-node branch. It is not part of a release, and details may change.

Part of Ledger implementation. This page covers what LedgerState holds, the order in which it checks every transaction and block, how fees and rounds are settled, and how the waiting transactions and heartbeats are kept. Why the rules are what they are is on the Ledger page.

What the state holds

LedgerState holds the balances of keys and legacy addresses, the claims that redirect a legacy address to its claimer, the number of transfers of each key, the set of used references, the votes of the round (sorted by candidate, then action, then voter), the validator set and the one before it, the supply, the unclaimed part of the snapshot, the fee pool, and the height, tip hash, tip time and tip certificate. It is built from a genesis, an authority and, for a chain with claims, a Snapshot of the legacy balances.

Nothing is changed before it is known to be right. Every block is checked and applied on a copy of the state, and the copy replaces the state only when the whole block passed. A refused block leaves the state as it was. applicable uses the same idea to pick transactions that fit together: it walks the candidates in order on a scratch copy and keeps each one that is still valid after the ones kept before it.

The state root is a Merkle root over these leaves, in this order:

1. H, the height;
2. S, the supply;
3. U, the unclaimed part of the snapshot;
4. P, the fee pool;
5. A, the address, balance and transfer count of each account, sorted by address;
6. R, each legacy address and the key that claimed it, sorted;
7. M, each used reference, sorted;
8. V, each validator in the order of the set, which is also the proposing order;
9. Q, each validator of the set before this one, in order;
10. T, each open vote: candidate, action and voter, in vote order.

Deterministic rules and the authority

The rules that every node must agree on are checked by the state itself: signatures, nonces, balances, the supply, the snapshot amount of a claim and its signature against the snapshot that the genesis commits to. A certified block therefore cannot carry a false claim. What is a node's own policy is asked of the LedgerAuthority: whether a mint is due and may be made, whether a claim is held back and whether a fee is high enough. The authority is skipped for a certified block, which is vouched for, so a change of policy never forks a replay. The authority the daemon uses is described on Ledger in the daemon.

Transactions

A mint is refused when its reference is already used (Reference already used), when the supply would overflow (Supply would overflow), and when the authority does not authorise it (Mint is not authorized). The authority is told the supply of the state the mint would be made on, which already holds the mints before it in the same block, so a limit on the supply holds for the block as a whole. It is also told the sum of the mints made to the recipient so far, so the sum that the mint spork grants an address can be kept in the same way. The state counts that sum under the address the mint names, before any redirect to a claimer, so a claimed legacy address goes on counting under its own address. It is not part of the state root, since the transaction roots already commit to the mints, and a replay of the blocks builds it again. A mint credits the recipient, or the claimer if the recipient is a claimed legacy address, and adds to the supply.

A claim is refused, in this order, when the address is already claimed, when its snapshot balance is negative, when it is above what is left of the snapshot (Claim is above what the snapshot has left), when there is nothing to claim, when the signature is not valid and when the authority does not authorise it (Claim is not authorized). It pays the recipient what the snapshot owes plus the balance the ledger holds on the address, removes the account, records the redirect and the claim's reference, and lowers the unclaimed amount. The supply does not change, since the snapshot total is already in it.

A transfer is refused, in this order, when its nonce is not the next (Transfer nonce is N but the next is M), when it would overflow, when the balance does not cover amount and fee, when the signature is not valid and when it pays less than the node demands (Fee is below what this node demands). It lowers the balance by amount and fee, credits the recipient and adds the fee to the pool. A transfer to oneself costs only the fee. The queue of the mempool uses a variant that lets a nonce in the future wait for the ones before it.

A vote is refused, in this order, when the voter is not a validator, the vote is for another round, the voter already voted on this candidate, the voter has cast 64 votes, the candidate is already a validator (for an add) or is not one (for a remove), the set is full, the candidate is a genesis validator being removed, and finally when the signature is not valid.

An exception from an authority is turned into the refusal Could not be checked: <message> and logged, so a peer cannot crash the node with an item that makes the authority throw. So is an ArithmeticException from a sum that would overflow.

Blocks

A block is checked in this order, and the first failure is its reason:

1. its place: the next height, the tip as previous hash, the proposer of that height and view, a time not older than the tip;
2. its content: 1 to 1000 transactions, or none while fees wait, and the transaction root they lead to;
3. the certificate by its shape: a view not earlier than the block's, at least a quorum of endorsements, every signer a validator, the signers strictly ascending so that each signs once;
4. the last commit by its shape, against the validators of the set before: none for the first block;
5. every signature in the certificate, against the precommit of the block;
6. every signature in the last commit, against the precommit of the block before;
7. the fees of the last commit's signers are paid out;
8. every transaction, in order, on the copy;
9. the end of a round, if this is its last block;
10. the state root, which must equal the root of the copy.

flowchart TD
    subgraph Cheap["1-4: by shape"]
        direction LR
        Place[place] --> Content[content] --> Cert[certificate] --> Last[last commit]
    end
    subgraph Signatures["5-6: signatures"]
        direction LR
        CertSig[of the certificate] --> LastSig[of the last commit]
    end
    subgraph Copy["7-10: on a copy of the state"]
        direction LR
        Fees[pay the fees] --> Txs[each transaction] --> Round[end of a round] --> Root[state root]
    end
    Cheap --> Signatures --> Copy --> Swap[the copy becomes the state]

Loading

The cheap checks come before the signatures, which come before the transactions. A validator about to vote runs proposalRejection instead: the place, the content, the last commit and its signatures, then the transactions with the node's own authority asked at the block's time, the end of a round and the root. It does not check the certificate, because a block with no certificate yet has not been vouched for by anyone.

Fees. Every transfer adds its fee to the pool. At the start of the next block the pool is paid to the signers of that block's last commit: each gets pool / n, and the remainder pool % n goes one unit each to the first signers in key order. A signer can spend what it is paid in the same block. An empty block is allowed only while the pool is above zero. For example, a pool of 10 units and three signers pays 4, 3 and 3 units, the first signer in key order getting the extra unit. The whole path of a coin is drawn on Ledger.

A round ends with the block whose height is a multiple of the round length. The votes are counted per candidate and action, and a change passes when votes * 3 > validators * 2, so exactly two thirds is not enough. Removals are taken out of the set first, then the added keys are appended in key order up to the limit of 1000, and the votes start over.

The proposer of height h in view v is the key at index ((h - 1) % n + v) % n of the set. The quorum is n * 2 / 3 + 1, and one third is n / 3 + 1.

Time is in Unix milliseconds. A block must not be older than the tip, and the proposer uses the later of its clock and the tip time. A validator refuses, before it votes, a block dated more than 30,000 ms ahead of its own clock. A certified block is not refused for being ahead of the clock, but it must still not be older than the tip.

Due mints. MintSchedule(tipHeight, tipTime) gives the due time of a legacy height as tipTime + (height - tipHeight) * 60,000 ms and refuses a height at or below the tip. The ledger itself only calls due(time): it leaves out the mints already made, puts the rest first among the candidates of a proposal, ahead of the mempool, and cuts the list at 1000. The authority lists every due mint and never cuts the list itself, so the entries behind the first block's worth are not starved. A due mint counts as work only if it survives applicable and the authority, so a mint that can never be made does not start a view every second.

The waiting transactions

A transaction waits in a slot: a mint is identified by its reference, a vote by its voter and candidate, a claim by its legacy address and a transfer by its sender and nonce. A second transaction for a slot that is taken is refused, except that a transfer may replace a waiting one by paying a strictly higher fee.

submit refuses, in this order, a taken slot, a full mempool (nothing is evicted, except that a transfer may replace one), a validator that already has 64 votes waiting, and anything the current state refuses. A transfer must have a nonce within 16 of the sender's next, and the transfers it waits behind must leave its balance covered. propose takes the oldest 1000, with each sender's transfers in nonce order, and keeps those that fit together. After a commit the transactions of the block leave, every remaining one is checked again against the new state, and every heartbeat is dropped, since each was for the old tip.

The pool is in memory only. A Ledger that replaces another in the same process, as a signing node replaces an observer, takes in the waiting transactions of the old one with takeWaitingFrom, in the order they were waiting, and what the new state refuses is left out. Heartbeats are not handed over.

Heartbeats

A heartbeat is accepted when its validator is in the set, it names the current height and tip hash, it is strictly newer than the one held for that validator and its signature is valid. isProgressing counts the current heartbeats whose time is within the window on either side of now, so a heartbeat dated far ahead does not count, and compares the count with the quorum. Nothing calls it yet.

In the source

• ledger/src/main/java/org/unigrid/hedgehog/ledger/LedgerState.java: the rules, the state root and the end of a round
• ledger/src/main/java/org/unigrid/hedgehog/ledger/LedgerAuthority.java: the questions the node answers
• ledger/src/main/java/org/unigrid/hedgehog/ledger/MintSchedule.java: a legacy height turned into a time
• ledger/src/main/java/org/unigrid/hedgehog/ledger/Snapshot.java: the legacy balances the genesis commits to
• ledger/src/main/java/org/unigrid/hedgehog/ledger/Mempool.java: the waiting transactions and the heartbeats
• ledger/src/main/java/org/unigrid/hedgehog/ledger/ValidatorSet.java: the proposer and the quorum
• ledger/src/main/java/org/unigrid/hedgehog/ledger/VerifiedSignatures.java: the signatures already checked