Ledger architecture & data structures

Introduction

≈90 min · Intermediate · builds on Advanced RPC features

The consensus phase starts with the object everyone is trying to agree on: the ledger. In this module you'll learn the Ledger and its LedgerHeader, the two SHAMaps it carries (state and transactions), and how a ledger is built, closed, hashed and chained to its parent. It's the noun that the consensus verb acts on.

The Ledger Chain Concept

In brief: each ledger links to its parent by hash, forming the chain.

Sequential Progression:

Properties:

Why Sequential Design?

• Ensures deterministic ordering of events
• Prevents double-spending and race conditions
• Enables efficient synchronization between nodes
• Provides clear audit trail for all network activity

Hierarchical Data Organization

Three-Tier Architecture:

Merkle Tree Architecture

In brief: a ledger holds two SHAMaps, one for account state and one for transactions.

The state and transaction data are organized as Merkle trees, enabling efficient verification:

Why Merkle Trees?

Practical Application:

A node can verify that a specific account balance is correct by checking only the path from that account to the root hash, rather than verifying the entire ledger.

Key idea. A ledger is two Merkle trees plus a header. The header's hashes commit to both trees, so a single ledger hash pins down the entire state and transaction set.

Data Integrity Mechanisms

In brief: hashing, signatures, consensus, and chaining stack up to make a ledger trustworthy.

Multiple Layers of Protection:

Layer 1: Cryptographic Hashing

Uses SHA-512Half to create unique fingerprints. Each ledger contains two Merkle trees:

• Transaction Map (txMap_): All transactions
• State Map (stateMap_): All account states and objects

Hash calculation proceeds bottom-up: leaf nodes hash their data, inner nodes hash their children, producing a root hash.

The ledger header stores both root hashes and calculates the final ledger hash:

header_.txHash = txMap_.getHash();
header_.accountHash = stateMap_.getHash();
header_.hash = calculateLedgerHash(header_);

Key verification points: When building a new ledger, hashes are computed FROM data (Ledger.cpp). When loading from database, the system verifies expected roots exist via fetchRoot() (Ledger.cpp). Network-acquired ledgers compare received vs expected hash (InboundLedger.cpp).

Failures detected: Missing nodes → network fetch. Hash mismatch → reject ledger. Internal corruption → abort via invariants() check.

Layer 2: Digital Signatures

Proves authorization using ed25519/secp256k1 signatures.

Transaction signatures: Every transaction must be signed by the account holder's private key. Invalid signatures result in tefBAD_AUTH rejection.

Validator signatures: Validators sign proposals during consensus (RCLCxPeerPos) and validations after building a ledger (STValidation). Each validation includes ledger hash, sequence, consensus hash, close time, and signature timestamp to prevent replay attacks.

Key management: Validators use a two-tier system, a master key (offline, long-term identity) and ephemeral keys (online, rotated regularly). The master key signs tokens authorizing ephemeral keys; each new token invalidates previous ones (see Exercise 1: Validator Keys Setup).

Failures: Invalid signatures → transaction/validation rejected. Revoked keys → all validations ignored. Unknown validators → not counted toward quorum.

Layer 3: Consensus Validation

Provides Byzantine fault tolerance through validator quorum.

A ledger requires validations from floor(trusted_validators × 0.8) + 1 validators, tolerating up to 20% Byzantine failures.

Process: Collect validations for the ledger hash, filter out validators on the Negative UNL (unreliable nodes), check if quorum is met, and verify all validators agree on the same hash (LedgerMaster.cpp).

Byzantine detection: If a node builds a different ledger than the network majority, it enters WrongLedger mode (Consensus.h), stops proposing, acquires the majority ledger from the network, and resumes consensus.

Failures: Insufficient validations → ledger remains unvalidated. Hash disagreement → enter WrongLedger mode. Network partition → wait for reconnection. The 80% quorum ensures agreement even with 20% compromised validators.

Layer 4: Chain Validation

Ensures temporal consistency through parent-child relationships.

Every ledger header references its predecessor (parentHash) and increments the sequence number (seq = parent.seq + 1). The system verifies: (1) parent exists, (2) parent hash matches, (3) sequence is continuous (LedgerMaster::checkAccept() line 922).

Skip list: Maintains references at exponential distances (parent, grandparent, great-grandparent) for efficient historical lookups via Ledger::updateSkipList().

Failures: Parent hash mismatch → reject ledger. Missing parent → fetch from network. Sequence gap → fetch missing ledgers. Chain fork → fixMismatch() repairs (LedgerMaster.cpp).

Protection: Guarantees unbroken sequence from genesis; altering past ledgers breaks the chain and is immediately detectable.

How Layers Work Together

All four layers work sequentially during validation: Layer 1 computes cryptographic hashes, Layer 2 verifies signatures, Layer 3 ensures validator agreement, and Layer 4 confirms chain continuity. If ANY layer fails, the ledger is rejected. This defense-in-depth design means even if one layer is compromised (e.g., a stolen validator key), the other layers protect the system.

The Ledger Lifecycle

In brief: how a ledger is opened, filled, closed, and validated.

Four Phases of Ledger Creation:

Phase Details:

1. Transaction Collection

• Gather pending transactions from network
• Apply transaction queue ordering rules
• Filter invalid or expired transactions

1. Ledger Assembly

• Apply transactions to previous ledger state
• Calculate new account balances and states
• Generate transaction results and metadata

1. Consensus Process

• Validators propose their assembled ledger
• Network reaches agreement on canonical version
• Disputed elements resolved through voting

1. Validation and Finalization

• Final ledger is cryptographically sealed
• Distributed to all network participants
• Becomes immutable part of the chain

State Transition Model

How State Changes Work:

ACID Properties:

Transaction Ordering and Determinism

Why Deterministic Ordering Matters:

All nodes must process transactions in identical order to reach the same final state.

Ordering Principles:

Multi-Tier Storage Architecture

Storage Hierarchy:

Data Lifecycle Management

Retention Policies:

Handling State Conflicts

Conflict Scenarios:

Ledger vs. Traditional Database

Comparison:

Immutability and Its Implications

Once a ledger is validated:

Code Enforcement:

class Ledger {
    bool mImmutable;

    void setImmutable() {
        mImmutable = true;
        stateMap_.setImmutable();
        txMap_.setImmutable();
    }
};

Only immutable ledgers can be stored in a LedgerHolder and published to the network.

Ledger Data Structures

Introduction

The XRP Ledger's reliability and performance depend on carefully designed data structures. This chapter explores the core classes that represent ledgers, manage their lifecycle, and provide efficient access to historical data.

The XRPL ledger is the authoritative record of the network's state at a given point in time. It contains all account balances, offers, escrows, and other objects, as well as a record of all transactions included in that ledger.

Every server always has an open ledger. All received new transactions are applied to the open ledger. The open ledger can't close until consensus is reached on the previous ledger and either there is at least one transaction or the ledger's close time has been reached.

Understanding these structures is essential for:

• Working with the codebase effectively
• Debugging ledger-related issues
• Implementing new features that interact with ledger state
• Understanding how consensus and validation work

The Ledger Class

The Ledger class is the primary representation of a single ledger instance. It manages both the state (account balances, offers, escrows, etc.) and transaction data for a specific ledger.

Location: LedgerHeader.h, Ledger.cpp

// Ledger.h (actual source code)
class Ledger final : public std::enable_shared_from_this<Ledger>,
                     public DigestAwareReadView,
                     public TxsRawView
{
private:
    // Ledger metadata (sequence, hashes, close time, etc.)
    LedgerHeader header_;

    // State tree (all account states, trust lines, offers, escrows, etc.)
    SHAMap mutable stateMap_;

    // Transaction tree (all transactions and their metadata)
    SHAMap mutable txMap_;

    // Immutability flag - once true, ledger cannot be modified
    bool mImmutable;

    // Protocol rules and enabled amendments for this ledger
    Rules rules_;

    // Fee schedule for this ledger
    Fees fees_;

    // ... additional private members ...
};

Key Points:

• Immutability: Once mImmutable is set to true via setImmutable(), the ledger cannot be modified. Only immutable ledgers can be stored in a LedgerHolder or published to the network.
• SHAMaps: Both stateMap_ and txMap_ are Merkle trees. The root hash of each tree is stored in header_.accountHash and header_.txHash respectively.
• Rules: The rules_ object determines which amendments are active, affecting how transactions are processed.

Core Components:

Construction Methods

Ledgers can be created in several ways, depending on the source of data:

1. Genesis Ledger:

// Ledger.cpp - Constructor signature
Ledger::Ledger(
    create_genesis_t,
    Config const& config,
    std::vector<uint256> const& amendments,
    Family& family)
{
    // Initialize first ledger with:
    // - Sequence 1
    // - Initial XRP distribution
    // - Genesis account states
    // - Activated amendments
}

Used to create the very first ledger in a new network.

2. From Previous Ledger:

// Ledger.cpp - Constructor signature
Ledger::Ledger(
    Ledger const& prevLedger,
    NetClock::time_point closeTime)
{
    // Copy and evolve:
    // - Increment sequence
    // - Set parent hash to previous ledger's hash
    // - Apply new close time
    // - Inherit state (copy-on-write)
}

This is the most common constructor used during consensus to build the next ledger.

3. From Serialized Data:

// Ledger.cpp - Constructor signature
Ledger::Ledger(
    LedgerHeader const& info,
    Config const& config,
    Family& family)
{
    // Reconstruct from:
    // - Persisted header info
    // - Load SHAMaps from NodeStore
}

Used when loading historical ledgers from the database or acquiring them from peers.

LedgerHeader Structure

The LedgerHeader struct contains all the metadata that uniquely identifies a ledger and its state. This is the data that hashes to the ledger's hash.

Location: LedgerHeader.h

// LedgerHeader.h (actual source code)
struct LedgerHeader
{
    //
    // For all ledgers
    //
    LedgerIndex seq = 0;                              // Sequence number
    NetClock::time_point parentCloseTime = {};         // When parent closed

    //
    // For closed ledgers
    //
    uint256 hash = beast::kZero;                        // This ledger's hash
    uint256 txHash = beast::kZero;                      // Transaction tree root
    uint256 accountHash = beast::kZero;                 // State tree root
    uint256 parentHash = beast::kZero;                  // Previous ledger's hash

    XRPAmount drops = beast::kZero;                     // Total XRP in existence

    bool mutable validated = false;                    // Has been validated?
    bool accepted = false;                             // Has been accepted?

    int closeFlags = 0;                                // Flags for ledger close
    NetClock::duration closeTimeResolution = {};       // Close time resolution (2-120s)
    NetClock::time_point closeTime = {};               // When this ledger closed
};

Key Header Fields:

Header Hashing:

The ledger hash uniquely identifies the ledger and is computed by serializing and hashing the header fields:

// From calculateLedgerHash() - conceptual representation
Ledger Hash = SHA512Half(
    HashPrefix::ledgerMaster ||  // Prefix for ledger headers
    seq ||
    drops ||
    parentHash ||
    txHash ||
    accountHash ||
    parentCloseTime ||
    closeTime ||
    closeTimeResolution ||
    closeFlags
)

This creates a unique, tamper-evident fingerprint for the entire ledger state. Any change to the state tree, transaction tree, or metadata produces a different hash.

Note: The "ledger base" refers to a query/response that includes the ledger header and may also contain the root node of the state tree. This is used during ledger acquisition from peers.

LedgerHolder

A thread-safe container that holds an immutable ledger. Only immutable ledgers can be held - this is enforced at runtime.

Location: LedgerHolder.h

// LedgerHolder.h (actual source code)
class LedgerHolder : public CountedObject<LedgerHolder>
{
public:
    // Update the held ledger (MUST be immutable!)
    void set(std::shared_ptr<Ledger const> ledger)
    {
        if (!ledger)
            LogicError("LedgerHolder::set with nullptr");
        if (!ledger->isImmutable())  // Runtime check!
            LogicError("LedgerHolder::set with mutable Ledger");

        std::lock_guard sl(m_lock);
        m_heldLedger = std::move(ledger);
    }

    // Return the (immutable) held ledger
    std::shared_ptr<Ledger const> get()
    {
        std::lock_guard sl(m_lock);
        return m_heldLedger;
    }

    // Check if a ledger is held
    bool empty()
    {
        std::lock_guard sl(m_lock);
        return m_heldLedger == nullptr;
    }

private:
    std::mutex m_lock;
    std::shared_ptr<Ledger const> m_heldLedger;
};

Why immutability matters:

• Multiple threads can safely read from an immutable ledger without locks
• Once set, the ledger's state never changes, preventing race conditions
• LedgerMaster uses LedgerHolders to track mValidLedger, mClosedLedger, etc.

Usage Pattern:

LedgerHistory

Manages the cache and retrieval of historical ledgers.

Location: LedgerHistory.h, LedgerHistory.cpp

// LedgerHistory.h (simplified from actual source)
class LedgerHistory {
    // Cache: hash → ledger
    TaggedCache<uint256, Ledger const> m_ledgers_by_hash;

    // Index: sequence → hash
    std::map<LedgerIndex, uint256> mLedgersByIndex;

public:
    // Insert ledger into cache
    void insert(
        std::shared_ptr<Ledger const> const& ledger,
        bool validated);

    // Retrieve by sequence
    std::shared_ptr<Ledger const> getLedgerBySeq(
        LedgerIndex ledgerIndex);

    // Retrieve by hash
    std::shared_ptr<Ledger const> getLedgerByHash(
        LedgerHash const& ledgerHash);

    // Fix index mapping
    void fixIndex(
        LedgerIndex ledgerIndex,
        LedgerHash const& ledgerHash);
};

Cache Organization:

Key Operations:

The insert() method (from LedgerHistory.cpp) adds ledgers to both caches and ensures the index-to-hash mapping is correct. The fixIndex() method is used to correct any inconsistencies in the index mapping that may occur during acquisition.

Immutability Enforcement

Once a ledger is finalized, it can never be changed. This is enforced both at compile time (via const correctness) and runtime (via the mImmutable flag).

void Ledger::setImmutable(bool rehash)
{
    // Force update of SHAMap root hashes
    if (!mImmutable && rehash)
    {
        // Get final root hashes from SHAMaps
        header_.txHash = txMap_.getHash().as_uint256();
        header_.accountHash = stateMap_.getHash().as_uint256();
    }

    // Calculate final ledger hash from header
    if (rehash)
        header_.hash = calculateLedgerHash(header_);

    // Lock down everything - no more modifications allowed
    mImmutable = true;
    txMap_.setImmutable();    // SHAMap becomes read-only
    stateMap_.setImmutable(); // SHAMap becomes read-only

    // Validate fee object exists (unless very early ledger)
    setup();
}

Immutability Lifecycle:

Immutability Rules:

SHAMap Integration

Ledgers use SHAMaps for state and transaction storage. The SHAMap is a Merkle-Patricia trie covered in detail in later modules. Here we focus on how the Ledger class interacts with it:

When setImmutable(true) is called, the final root hashes are retrieved from the SHAMaps and stored in the LedgerHeader.

The Rules Class

The Rules class encapsulates which amendments (protocol upgrades) are enabled for a specific ledger. All nodes must agree on which amendments are active for deterministic transaction processing.

Location: Rules.h

// Rules.h (actual source code - uses pimpl idiom)
class Rules
{
private:
    class Impl;  // Implementation hidden in .cpp file

    // Shared pointer makes Rules cheap to copy
    std::shared_ptr<Impl const> impl_;

public:
    // Construct rules from a set of enabled amendment IDs
    explicit Rules(std::unordered_set<uint256, beast::uhash<>> const& presets);

    // Check if a specific amendment is enabled
    bool enabled(uint256 const& feature) const;

    // Rules are cheap to copy due to shared_ptr
    Rules(Rules const&) = default;
    Rules& operator=(Rules const&) = default;

    // Compare two rule sets
    bool operator==(Rules const&) const;
};

How Rules Are Used:

Throughout transaction processing, the code checks if specific amendments are enabled to determine which logic path to use:

// Example from payment processing
if (view.rules().enabled(featureFlowCross))
{
    // Use new payment engine introduced by FlowCross amendment
    return flowCross(view, deliver, account, src, dst, ...);
}
else
{
    // Use legacy payment engine
    return legacyPaymentEngine(view, deliver, ...);
}

Amendment Activation:

Why This Matters:

• Consensus requires determinism: All validators must process transactions identically
• Amendments change behavior: Different amendment sets → different results
• Rules track the truth: The Rules object for ledger N reflects exactly which amendments were active when ledger N was built

See the Amendments, overview & architecture module for full details on the amendment system.

Key Operations

The Ledger class provides methods to read and modify state objects. All operations work through the stateMap_ SHAMap.

Reading State:

// Ledger.cpp
std::shared_ptr<SLE const> Ledger::read(Keylet const& k) const
{
    // 1. Look up item in state map
    auto const& item = stateMap_.peekItem(k.key);
    if (!item)
        return nullptr;  // Object doesn't exist

    // 2. Deserialize to Serialized Ledger Entry (SLE)
    auto sle = std::make_shared<SLE>(SerialIter{item->slice()}, item->key());

    // 3. Verify type matches expectation
    if (!k.check(*sle))
        return nullptr;

    return sle;
}

The read() method uses a Keylet for type-safe lookups. A Keylet combines a key with a type checker, ensuring you retrieve the correct object type (e.g., keylet::account(accountID) for account roots).

Modifying State (Mutable Ledgers Only):

// Insert new object
void rawInsert(std::shared_ptr<SLE> const& sle);

// Update existing object
void rawReplace(std::shared_ptr<SLE> const& sle);

// Delete object
void rawErase(std::shared_ptr<SLE> const& sle);

These methods:

• Only work on mutable ledgers (before setImmutable() is called)
• Serialize the SLE to binary format
• Add/update/remove items in stateMap_
• Throw LogicError if the operation fails (duplicate key, missing key, etc.)

Database Persistence

Ledgers are stored using a two-tier system:

Why Two Storage Systems?

1. SQL Database: Stores ledger headers for fast sequential access and indexing
2. NodeStore: Stores SHAMap tree nodes for efficient content-addressable storage

When loading a ledger:

1. Retrieve header from SQL database by sequence or hash
2. Construct empty SHAMaps with root hashes from header
3. Load tree nodes from NodeStore on-demand as they're accessed

Integrity Verification:

Before persisting, the system verifies hash consistency:

assert(header_.accountHash == stateMap_.getHash().as_uint256());
assert(header_.txHash == txMap_.getHash().as_uint256());

This ensures the header accurately represents the tree contents. Mismatches indicate data corruption, Byzantine attacks, or implementation bugs.

Implementation: See Node.cpp and SQLiteDatabase.cpp for details.

Summary

This module described the ledger itself, the object consensus is trying to agree on. You learned the LedgerHeader and the two SHAMaps a ledger carries (account state and transactions), how a ledger is built, closed, and hashed, and how each ledger is chained to its parent by hash. A single ledger hash pins down the entire state and transaction set.

To remember:

• A ledger = header + state SHAMap + transaction SHAMap
• Header fields to know: ledger_index, parent_hash, account_hash, transaction_hash, close_time
• ledger_hash is the hash of the header, which commits both trees: one hash pins everything
• Chaining: each header carries parent_hash; tamper with one ledger and every later hash breaks
• Close time is agreed during consensus and rounded
• Lifecycle: open (collecting), closed (agreed set), validated (quorum signed)
• Code: src/xrpld/app/ledger and include/xrpl/ledger
• Watch out: only validated data is safe to act on; the open ledger is a moving draft

Next up. You know what a ledger is made of. Now the famous question: how do hundreds of nodes agree on the next one, every few seconds, with no leader? Consensus fundamentals.