This website is no longer actively supported. Please see the Ripple Developer Center for up-to-date documentation and other resources.

Ledger

From Ripple Wiki
Jump to: navigation, search

The Ledger is the heart of the Ripple system. The Ledger contains a list of all the accounts and the balance of each account (and similar data). Every Ripple Node has a synchronized copy of the current Ledger.

The main job of the network is keeping this ledger consistent across all the nodes.

The Ledger Ripple currently runs on was first created December 21st, 2012.

Ledger

The Ledger is a notional structure that consists of a previous ledger (unless it's the zero ledger), a list or tree of transactions, and a tree of account states showing all balances after those transactions are applied. Ledgers are stored in such a way as to make syncing ledgers between nodes very efficient. We use a method similar to rsync. See Ledger Syncing for more details. The ledger is stored as a hash tree that allows individual branches to be validated. The Validations that are signed by Validators include the top level hash of this ledger structure.

At the basic level, there's a Hash Tree of account balances, and this tree is altered by transactions. Every ledger has a sequence one greater than its parent ledger. (Except the genesis, of course.)

Once you know the hash of the current ledger, you need no further signature operations to walk ledgers, transactions, past ledgers, and so on. It's all linked by hash.

Nothing is signed in the ledger itself. Only the master hash ledgers are validated or signed by other nodes in the network. To verify the hash you don't need to download the entire ledger. The hash is a hash of branches. The "ledger master hash" is a hash of a small control structure that includes, among other things, the "root hash" of tree of account states. So from the ledger master hash, you can know the root hash for sure with that small structure.

The root hash is the hash of a node that contains 16 branch hashes. And each branch hash is the hash of a node that contains 16 sub-branch hashes, until you get to the nodes that have the actual balances. So to prove account X has balance Y in ledger Z, you just need the path to that node. So I give you the small ledger structure, you confirm the hash, and you know the hash of the account state tree. Then I give you the root node, you confirm the hash (with the one in the ledger), and you know that. And so on, each hash leads you to the next hash.

Similarly, if a server starts up after having been offline for awhile, many of the nodes will be unchanged, and they don't need to be synched. As soon as you get a node with a child you already have, you know you have the rest of that branch. The beauty of this is that checking digital signatures is expensive, and this design means you rarely have to do it. It also makes it easy to verify parts of the ledger. And it makes it easy to synchronize ledgers or compute the differences between two ledgers.


Ignoring some optimizations, it's basically by the nibbles of the account ID (which is a 160-bit hash). Each nibble splits the tree into 16 branches. So if your account starts with a 4, it's on branch 4 of the tree root. If it has a 2 next, it's on branch 2 of branch 4. a nibble is 4 bits


The Consensus process forces all nodes to agree on which transactions to apply, a new ledger is published, and that is signed by all nodes who choose to validate (provide such signatures). The validations are used by people to figure out what ledger is the right one, from there it's all hashes.

At each interior node of the hash tree there are 16 hashes, one for each branch off that node. (or zeroes for empty branches).

Also included in that ledger is the hash of the previous ledger, so you can walk ledgers backwards by hash without any signature operations. The ledgers form a chain. Each ledger also contains the set of transactions that made it into that ledger, as a separate tree whose hash is included.

Introduction

The Ledger format is designed to permit efficient storage, discovery by hash, and efficient comparisons of ledgers to find differences. It is designed to have a canonical, but notional, binary format to permit these operations.

Formats

A node may internally store a ledger in any format it wishes. Many nodes will need indexes in order to discover transaction paths. However, no index is needed to validate and perform transactions, as the ledger format is sufficiently self-indexing to permit this.

Binary Format

Each ledger element has a canonical binary format in which it can be hashed. Higher-level ledger structures include hashes of lower-level structures in their canonical format.

Header

The ledger has a header that includes basic information about the ledger. These include:

  • The ledger's sequence number, which is the count of previous ledgers to the genesis ledger.
  • The total number of Ripples accounted for in the ledger. This is only needed for Ripples because only Ripples are destroyed when fees are paid.
  • The hash of the previous ledger, or zero for the genesis ledger.
  • The hash for the transactions successfully applied in this ledger interval (see below).
  • The hash for the account states at the close of this ledger.
  • The time at which this ledger closed.
  • The time at which the previous ledger closed.
  • Flags that indicate certain ledger properties.

The ledger's ID is the hash of this ledger header.

Trees

The ledger uses hash trees for large structures. Each hash tree consists of inner nodes and leaf nodes. The hash of the tree itself is the hash of its uppermost inner node (root node). Leaf nodes contain data elements indexed by a hash (that may or may not be the hash of the data in the leaf). Trees are trivially traversable in hash order and are specifically designed for efficient synchronization, validation, traversal, modification, and comparison.

Account Tree

The account tree contains all persistent state at the close of the ledger. This includes account balances, credit limits, and so on.

Each account will have a master node, indexed by the account ID. It will contain the account's Ripple balance and the sequence number of its last transaction. (The last transaction successfully processed by the close of this ledger, signed by this account.)

For each other currency an account holds (or has held) a balance in, there must be a balance node. Since account IDs are 160-bits and tree indexes are 256-bits, this gives us 96 additional bits for account balance nodes for additional currencies, ripple credit, offers, and the like. Each such additional node will be indexed by using the 160-bit account ID and filling the additional 96-bits with part of the ID for the alternative currency, account issuing the credit, or whatever appropriately identified the balance node. This algorithm must be deterministic but need not guarantee unique results. This means a single index may hold multiple data points and the node format must support that in a canonical way to ensure all nodes get the same results.

For balances that affect multiple accounts, for example, if account A extends credit to account B, the account the index is based on will be the account one needs to locate the record by in order to process transactions. If either way works, then the full index account will be the account that did not originate the operation. So for credit A has extended to B, it is indexed by B's full account ID. If A invoices B, it is indexed by B's full account ID. (The 96 remaining bits are a partial hash specific to the operation.)

Transactions

The transaction tree contains each transaction applied to produce this ledger from the previous ledger. Each transaction is indexed in the tree by its transaction ID. The actual leaf nodes contains both the transaction itself and metadata that explains what effects the transaction had on the account state tree.

The tree hash should be the hash of the root node of the tree.

FAQ