Ledger

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

The ledger is a small chain that Hedgehog nodes keep together: a record of account balances and of the validators that maintain it. Every block carries a certificate, the signatures of more than two thirds of the validators, so a node that holds the blocks can check the whole history on its own. So far it is a self-contained library in its own Maven module, ledger, and nothing else in the node uses it yet.

The name is unrelated to the ledger entries of the Legacy chain snapshot, which hold the history of the earlier chain.

What it records

  • the balance of each account, where an account is an Ed25519 public key;
  • the references of the mints already made, so that none is made twice;
  • the validator set, in the order that decides who proposes;
  • the votes cast in the current round;
  • the height, hash and time of the latest block, the tip.

Every block commits to all of this with a state root, a Merkle root over SHA-512. A validator signs a block only if it arrives at the same root, so two nodes that accept the same block hold the same state.

Transactions

Kind What it does Authorised by
Mint Credits an amount to an account, under a 32-byte reference that can be used once The node’s mint authority, not a signature
Vote A validator’s vote to add a key to the validator set, or to remove one, in the current round The voter’s signature, which also covers the chain it is for

The mint authority is the one question the ledger asks the node around it: may this mint be made? A node that does not know yet answers no, which only delays the block. What a reference stands for is not the ledger’s business. There are no transfers, so a mint is the only way a balance changes.

How a block is made

The ledger offers four steps, and a consensus engine, which is not written yet, drives them and carries the results between the nodes.

sequenceDiagram
    participant E as Consensus engine
    participant P as Proposer's ledger
    participant V as Other validators' ledgers
    E->>P: submit transactions
    E->>P: propose
    P-->>E: block, signed by the proposer
    E->>V: sign
    V-->>E: one more signature each
    Note over E: more than two thirds have signed
    E->>P: commit
    E->>V: commit
  • One proposer per height. The validators take turns in the order of the set, and the first one proposes height 1. A block holds 1 to 1000 transactions. There are no empty blocks: with nothing waiting, no block is made.
  • Checked before signing. A validator signs only a block that follows the tip, comes from the proposer of its height, is not older than the tip, and whose transactions are all valid and lead to the state root it states.
  • Never two blocks at one height. A validator refuses to sign a second, different block at a height it has signed, and a proposer that is asked again hands back the same block.
  • The certificate. A block is valid with the signatures of more than two thirds of the validators, each once, the proposer among them. The block hash covers the header only, so a block has one identity however its signatures were gathered.
  • A certified block is trusted for its mints. More than two thirds of the validators asked their mint authorities before signing, so a node does not ask its own again. This is what lets a node replay old blocks after a restart, whatever its authority knows by then.
  • Commit. The block is written to disk before the state changes, so a crash between the two replays to the same state. Waiting transactions that the new state no longer allows are dropped.

Up to 10,000 transactions wait for a block. Beyond that, new ones are refused and nothing is evicted.

Validators and rounds

The chain starts from a genesis: a start time, the length of a round in blocks and the foundation validators. Its hash is the chain id, which every vote and heartbeat signature covers, so neither can be replayed on another chain.

The validator set is fixed for a whole round. During the round a validator may vote to add or remove a key, and the last block of the round closes it: every change that more than two thirds of the set voted for takes effect from the next block, and the votes start over. Exactly two thirds is not enough.

  • A validator votes once per candidate and casts at most 64 votes in a round.
  • The genesis validators can never be removed. They stay on as the backup.
  • The set holds 1 to 1000 keys. Added keys go to the end of the proposing order.

Heartbeats

Blocks are made only when there is something to record, so a quiet chain has no new block for a long while. A heartbeat is a validator’s signed statement that it is up and sees the current tip at a given time, and it is how a quiet chain is told from a stalled one: the chain counts as progressing while more than two thirds of the validators have a heartbeat within a chosen window.

A node keeps only the newest heartbeat of each validator, and only for the current tip. Committing a block discards them all, and a heartbeat for a tip that has been replaced is refused. Heartbeats never enter a block or the state.

Storage

Blocks are stored in one append-only file. A record is the length of the block, a checksum of that length, a checksum of the block, and the block itself. A block counts as stored only once it has been forced to disk.

  • A torn last record is dropped. A crash can only damage the end of the file: a record cut short, or a tail of zeros. Opening the log cuts that off with a warning.
  • Damage elsewhere is refused. A record that fails its checksum in the middle of the file stops the log from opening and leaves the file untouched, since dropping one record would drop every block behind it. The checksum of the length is what tells the two cases apart.
  • A failed write is rolled back, so the next block does not land behind half a record.

The state is not stored. A node rebuilds it on start by replaying every block with all checks, so a log that was tampered with does not come up as a state.

Not there yet

  • A consensus engine and networking. Nothing carries transactions, blocks, signatures or heartbeats between nodes, and nothing steps in when a proposer is absent.
  • A mint authority. The node is expected to answer from the mint sporks, see Grid sporks.
  • Transfers and fees.
  • REST endpoints and commands. The application module does not depend on the ledger.
  • A lasting record of signed heights. What a validator has signed is kept in memory only, so a restart forgets it.

Key facts

Fact Value
Account key Ed25519 public key, 32 bytes
Signature Ed25519, 64 bytes
Hash SHA-512, 64 bytes
Block header 240 bytes
Transactions per block 1 to 1000
Encoded mint and vote 73 and 138 bytes
Largest encoded block 234,244 bytes
Validators 1 to 1000
Signatures a block needs n * 2 / 3 + 1 of n validators: 3 of 4, 5 of 7, 67 of 100
Votes per validator per round 64
Waiting transactions 10,000
Log record header 12 bytes: the length and two CRC32C checksums
Maven module ledger, artifact hedgehog-ledger

In the source

All paths are on the ledger branch of the Hedgehog repository.

  • ledger/src/main/java/org/unigrid/hedgehog/ledger/Ledger.java ties the state, the waiting transactions and the block log together.
  • ledger/src/main/java/org/unigrid/hedgehog/ledger/LedgerApplication.java is the interface a consensus engine drives.
  • ledger/src/main/java/org/unigrid/hedgehog/ledger/LedgerState.java holds every rule for transactions, blocks, certificates and rounds.
  • ledger/src/main/java/org/unigrid/hedgehog/ledger/Block.java is the header, the transactions and the certificate.
  • ledger/src/main/java/org/unigrid/hedgehog/ledger/ValidatorSet.java decides the proposer and the quorum.
  • ledger/src/main/java/org/unigrid/hedgehog/ledger/Mempool.java holds the waiting transactions and the heartbeats.
  • ledger/src/main/java/org/unigrid/hedgehog/ledger/BlockLog.java is the append-only file and its recovery.
  • ledger/src/main/java/org/unigrid/hedgehog/ledger/MintAuthority.java is the question the node answers.