Cryptographic Proofs and State Reconstruction

← Back to SHAMap and NodeStore: Data Persistence and State Management

---

Introduction

The combination of SHAMap and NodeStore provides more than just efficient storage—they enable cryptographic proofs that transactions were executed correctly and state was computed honestly.

This chapter explores:

• Merkle proof generation and verification

• State reconstruction from transaction history

• Cross-chain or light-client verification

• The guarantee of verifiable ledger history

Merkle Proof Generation

A Merkle proof allows someone to verify that data is in a tree without reconstructing the entire tree.

Algorithm: getProofPath

std::optional<std::vector<Blob>>
SHAMap::getProofPath(uint256 const& key)
{
    std::vector<Blob> path;

    auto node = std::dynamic_pointer_cast<SHAMapInnerNode>(mRoot);

    for (int depth = 0; depth < 64; ++depth) {
        // Serialize current node
        Blob serialized = node->serialize();
        path.push_back(serialized);

        // Is this the target leaf?
        if (auto leaf = std::dynamic_pointer_cast<SHAMapLeafNode>(node)) {
            if (leaf->getKey() == key) {
                return path;  // Success
            } else {
                return std::nullopt;  // Wrong leaf
            }
        }

        // Navigate to next level
        int branch = key.nthNibble(depth);
        node = std::dynamic_pointer_cast<SHAMapInnerNode>(
            node->getChild(branch));

        if (!node) {
            return std::nullopt;  // Path doesn't exist
        }
    }

    return std::nullopt;  // Shouldn't reach here
}

Example Proof:

For an account with key 0x3A7F2E1B...:

Proof path (from root to leaf):

[0]: Inner node (root)
     Hash: 0x1234... (all state)
     Children: [3 -> 0xABCD..., 5 -> 0x5678..., ...]

[1]: Inner node (depth 1, branch 3)
     Hash: 0xABCD... (state with branch 3)
     Children: [A -> 0xEF12..., B -> 0x3456..., ...]

[2]: Inner node (depth 2, branch A)
     Hash: 0xEF12... (state with branch 3, then A)
     Children: [7 -> 0x7890..., ...]

[3]: Inner node (depth 3, branch 7)
     Hash: 0x7890... (state with branch 3, A, 7)
     Children: [F -> 0x8765..., ...]

[4]: Leaf node
     Content: {Account, Data}
     Hash: 0x8765... (account data)

Total: 5 nodes (including leaf)
Size: ~500 bytes for 5 serialized nodes

Proof Size Properties:

Tree size: 1 million accounts
Tree depth: log_16(1M) ≈ 5 levels

Proof includes:
  5 inner nodes + 1 leaf: ~100 bytes per node
  Total: ~600 bytes

Without proof:
  Send all 1M accounts: gigabytes

Proof is logarithmic in tree size
Verification requires one hash per level: O(log N)

Proof Verification

Verifying a proof requires only the root hash and the proof:

Algorithm: verifyProofPath

bool verifyProofPath(
    uint256 const& key,
    uint256 const& expectedRootHash,
    std::vector<Blob> const& proof)
{
    if (proof.empty()) {
        return false;
    }

    // Start from leaf (last in proof)
    auto leafNode = deserializeNode(proof.back(), /* leaf */);
    if (!leafNode || leafNode->getKey() != key) {
        return false;
    }

    // Compute leaf hash
    uint256 computedHash = leafNode->computeHash();

    // Walk from leaf toward root
    for (int i = (int)proof.size() - 2; i >= 0; --i) {
        auto innerNode = deserializeNode(proof[i], /* inner */);
        if (!innerNode) {
            return false;
        }

        // Determine which branch we came from
        int depth = i;
        int branch = key.nthNibble(depth);

        // Verify the child hash matches
        if (innerNode->getChildHash(branch) != computedHash) {
            return false;  // Proof is invalid
        }

        // Compute this node's hash for next iteration
        computedHash = innerNode->computeHash();
    }

    // Verify final hash matches expected root
    return (computedHash == expectedRootHash);
}

Verification Process:

Given:
  - Key: 0x3A7F2E1B...
  - Expected root: 0x1234...
  - Proof: [inner_0, inner_1, inner_2, inner_3, leaf]

Step 1: Deserialize leaf, verify it contains key
        Compute leaf hash: 0x8765...

Step 2: Deserialize inner_3
        Check: child[F] hash == 0x8765... ✓
        Compute inner_3 hash: 0x7890...

Step 3: Deserialize inner_2
        Check: child[7] hash == 0x7890... ✓
        Compute inner_2 hash: 0xEF12...

Step 4: Deserialize inner_1
        Check: child[A] hash == 0xEF12... ✓
        Compute inner_1 hash: 0xABCD...

Step 5: Deserialize inner_0 (root)
        Check: child[3] hash == 0xABCD... ✓
        Compute root hash: 0x1234...

Final check: Computed hash == expected? 0x1234 == 0x1234 ✓
Result: Proof is valid! Account is in ledger.

Proof Use Cases

1. Light Clients

Scenario: Mobile wallet wanting to verify account balance

Traditional: Download entire ledger (~gigabytes)
With proofs: Download only account proof (~600 bytes)

Client verifies:
  1. Receives account balance and proof
  2. Verifies root hash matches known ledger
  3. Uses proof verification algorithm
  4. Trusts balance without downloading full ledger

2. Cross-Chain Bridges

Scenario: Ethereum bridge wants to verify XRPL state

Bridge requires: Proof that account exists in XRPL
Verification:
  1. Receives XRPL ledger header (small)
  2. Receives Merkle proof (small)
  3. Verifies proof against root hash
  4. Acts on verified state

3. Auditing and Compliance

Scenario: Auditor wants to prove a transaction executed

Proof includes:
  - Transaction existence proof (proof in tx tree)
  - Resulting state proof (proof in state tree)
  - Chain of ledgers connecting them

Verifier can:
  - Confirm transaction was processed
  - Confirm state effects were applied
  - Build complete chain of evidence

4. Rollups and Scaling

Scenario: Layer-2 rollup batches XRPL transactions

Instead of: All transactions + full ledger
Rollup uses: Transaction proofs + state root

Verification:
  - Verify each transaction in batch
  - Verify resulting state
  - All with minimal data

State Reconstruction Guarantee

The transaction tree provides a critical guarantee: verifiable unique history.

The Problem Without Transaction Tree:

State progression:

Initial state: S₀ (all accounts have 0 balance)

Could have arrived via many paths:
  Path 1: S₀ --tx1--> S₁ --tx2--> S₂ --tx3--> S₃
  Path 2: S₀ --tx4--> S₁' --tx5--> S₂' --tx3--> S₃
  Path 3: S₀ --tx6--> S₁'' --tx1--> S₂'' --tx2--> S₃

Same final state S₃, but completely different history!
Which is correct? Without history, no way to know.

The Solution: Transaction Tree

The XRP Ledger maintains both trees in every ledger:

struct LedgerHeader {
    uint256 accountTreeHash;      // Root of account state
    uint256 transactionTreeHash;  // Root of transaction history

    // Both are cryptographically committed
    // Both are signed by validators
    // Both must match
};

State Reconstruction:

Given: LedgerHeader with both tree hashes

Verifiable state reconstruction:
  1. Fetch account tree → current state
  2. Fetch transaction tree → history
  3. Replay transactions: S₀ + all_tx → S_computed
  4. Verify: S_computed matches account tree root
  5. Verify: transaction tree contains all_tx

Result: Proven that state is correct result of transactions

Why This Matters:

Without verification: Anyone could claim different history
With verification: Only one possible history is correct

Example:
  Alice claims she sent 100 XRP to Bob
  Bob claims he received only 50 XRP

  Ledger history is immutable and verified
  Proof shows exactly what happened
  No ambiguity

Ledger Verifiability

Every aspect of XRPL state is cryptographically verifiable:

Account Proof

Prove: Account has balance 1000 XRP

Components:
  1. Ledger header with account state root
  2. Merkle proof from root to account leaf
  3. Account data (balance, etc.)

Verification:
  Verify proof leads from root to account
  Account balance is in proof
  Root hash signed by supermajority of validators

Transaction Proof

Prove: Transaction T was executed in ledger L

Components:
  1. Ledger L header with transaction tree root
  2. Merkle proof from root to transaction leaf
  3. Transaction data and execution results

Verification:
  Verify proof leads from root to transaction
  Matches all known transaction identifiers
  Root hash signed by validators

Full Ledger Proof

Prove: Ledger state transitions from L1 to L2

Components:
  1. L1 ledger header (initial state)
  2. All transactions between L1 and L2
  3. L2 ledger header (final state)

Verification:
  1. Verify all transaction proofs against L2
  2. Verify all account proofs against L2
  3. Verify L2 header is valid

Result: Complete proof that L2 is correct result of applying
        all transactions to L1

Practical Verification Workflow

Step 1: Trust the Ledger Header

// Ledger headers are small (~100 bytes)
// Signed by supermajority (>80%) of validators
// Distributed via gossip protocol

LedgerHeader verified_header = getLedgerHeader(ledgerSeq);
// Root hashes are in verified_header

Step 2: Request Proof

// Client requests proof of account existence
MerkleProof proof = peer.requestProof(
    accountID,
    verified_header.accountStateRoot);

// Proof is small (~500 bytes)

Step 3: Verify Proof

// Client verifies locally (no network needed)
if (verifyProofPath(accountID,
                    verified_header.accountStateRoot,
                    proof)) {
    // Account exists and is proven
    // Can trust all data in proof
    auto account = parseAccountFromProof(proof);
}

Step 4: Use Verified Data

// Application can now use the verified account data
// with absolute confidence it's correct
double balance = account.balance;  // Proven correct

Summary

Key Concepts:

1. Merkle Proofs: Logarithmic-sized proofs of inclusion

2. Proof Verification: O(log N) hash checks to verify

3. Light Clients: Verify without downloading full ledger

4. Unique History: Transaction tree guarantees verifiable history

5. Ledger Integrity: All state cryptographically provable

Security Properties:

Proof tampering:         Detected by hash mismatch
Missing nodes:           Detected by proof verification failure
Fork detection:          Different ledger headers = detected forgery
State divergence:        Account proof path breaks

All attacks: Detectable by cryptographic verification

Performance:

Traditional verification:  All data (gigabytes) + full hashing
Proof-based verification:  600 bytes + 5 hash operations
Speedup:                   10,000x less data, 100,000x less compute

This is the power of Merkle trees applied to blockchain: trustless verification at scale.