Ledger state and rules

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.

The leaves of a small state in order, what each letter holds, and the shape of the tree over five leaves

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 key that the Ed25519 curve has no point for verifies nothing: Ed25519.verify answers false for it, not an exception. 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, whether a fee is high enough and how much a transfer to an address the ledger has no account for must carry. 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, when it pays less than the node demands (Fee is below what this node demands) and when the recipient holds no account and it sends less than the node demands for that (Amount to a new account 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 not for the round of the block’s time, the voter already voted on this candidate, the voter has cast 64 votes, the candidate is not a public key (for an add, Candidate is not a public key), 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.

A vote that arrives is checked for its round before anything else. A vote that waits is checked for its voter and candidate before its signature, which anyone can make with a key of their own for nothing. It leaves the pool once its round is past for the node, since no block the node makes can take it.

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 to pay fees that wait or close a round that holds votes, 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 round of the tip closes if this block’s time lies in a later one, and the changes it carries take effect;
  8. the fees of the last commit’s signers are paid out;
  9. every transaction, in order, on the copy;
  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
        Round[end of a round] --> Fees[pay the fees] --> Txs[each transaction] --> Root[state root]
    end
    Cheap --> Signatures --> Copy --> Swap[the copy becomes the state]

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 end of a round, the fees, the transactions with the node’s own authority asked at the block’s time, 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 when the pool is above zero, or when its time lies in a later round than the tip’s and the tip’s round holds votes. 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.

The round of a block is floorDiv(block time - genesis time, roundMillis): rounds follow each other from the genesis time, which starts round 0, and roundEndAt gives where one ends and the next starts. A block whose time lies in a later round than the tip first closes the tip’s round. 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 new set takes over from the next height. Rounds that pass without a block close together at the next block and change nothing, since they hold no votes. An empty block that closes a round is valid only when that round holds votes; the votes leave with the round, so a round has at most one such block, and a chain where nobody votes has none.

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 block has no lower bound from the clock: one that more than two thirds prevoted for is put forward again in a later view with the time it was made at, which a bound by the clock would refuse once enough time passed, and the validators locked on it could then vote for nothing else. So a proposer whose clock runs behind may date a block in a round that has passed for the others and take its votes. 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