Ancestry trie of ledgers.

Synopsis

template<
    class Ledger>
class LedgerTrie

Member Functions

Description

Combination of a compressed trie and merkle-ish tree that maintains validation support of recent ledgers based on their ancestry.

The compressed trie structure comes from recognizing that ledger history can be viewed as a string over the alphabet of ledger ids. That is, a given ledger with sequence number seq defines a length seq string, with i-th entry equal to the id of the ancestor ledger with sequence number i. "Sequence" strings with a common prefix share those ancestor ledgers in common. Tracking this ancestry information and relations across all validated ledgers is done conveniently in a compressed trie. A node in the trie is an ancestor of all its children. If a parent node has sequence number seq, each child node has a different ledger starting at seq+1. The compression comes from the invariant that any non-root node with 0 tip support has either no children or multiple children. In other words, a non-root 0-tip-support node can be combined with its single child.

The merkle-ish property is based on the branch support calculation. Each node has a tipSupport, which is the number of current validations for that particular ledger. The branch support is the sum of the tip support and the branch support of that node's children:

node->branchSupport = node->tipSupport
                    + sum_(child : node->children) child->branchSupport

This is analagous to the merkle tree property in which a node's hash is the hash of the concatenation of its child node hashes.

The templated Ledger type represents a ledger which has a unique history. It should be lightweight and cheap to copy.

// Identifier types that should be equality-comparable and copyable
struct ID;
struct Seq;

struct Ledger
{
   // The default ledger represents a ledger that prefixes all other
   // ledgers, e.g. the genesis ledger
   Ledger();

   Ledger(Ledger &);
   Ledger& operator=(Ledger );

   // Return the sequence number of this ledger
   Seq seq() const;

   // Return the ID of this ledger's ancestor with given sequence number
   // or ID{0} if unknown
   ID
   operator[](Seq s);

};

// Return the sequence number of the first possible mismatching ancestor
// between two ledgers
Seq
mismatch(ledgerA, ledgerB);

The unique history invariant of ledgers requires any ledgers that agree on the id of a given sequence number agree on ALL ancestors before that ledger:

Ledger a,b;
// For all Seq s:
if(a[s] == b[s]);
    for(Seq p = 0; p < s; ++p)
        assert(a[p] == b[p]);

Template Parameters

Header

#include <ripple/consensus/LedgerTrie.h>