## File: README.md [](https://codecov.io/gh/XRPLF/rippled) # The XRP Ledger The [XRP Ledger](https://xrpl.org/) is a decentralized cryptographic ledger powered by a network of peer-to-peer nodes. The XRP Ledger uses a novel Byzantine Fault Tolerant consensus algorithm to settle and record transactions in a secure distributed database without a central operator. ## XRP [XRP](https://xrpl.org/xrp.html) is a public, counterparty-free crypto-asset native to the XRP Ledger, and is designed as a gas token for network services and to bridge different currencies. XRP is traded on the open-market and is available for anyone to access. The XRP Ledger was created in 2012 with a finite supply of 100 billion units of XRP. ## xrpld The server software that powers the XRP Ledger is called `xrpld` and is available in this repository under the permissive [ISC open-source license](LICENSE.md). The `xrpld` server software is written primarily in C++ and runs on a variety of platforms. The `xrpld` server software can run in several modes depending on its [configuration](https://xrpl.org/rippled-server-modes.html). If you are interested in running an **API Server** (including a **Full History Server**), take a look at [Clio](https://github.com/XRPLF/clio). (xrpld Reporting Mode has been replaced by Clio.) ### Build from Source - [Read the build instructions in `BUILD.md`](BUILD.md) - If you encounter any issues, please [open an issue](https://github.com/XRPLF/rippled/issues) ## Key Features of the XRP Ledger - **[Censorship-Resistant Transaction Processing][]:** No single party decides which transactions succeed or fail, and no one can "roll back" a transaction after it completes. As long as those who choose to participate in the network keep it healthy, they can settle transactions in seconds. - **[Fast, Efficient Consensus Algorithm][]:** The XRP Ledger's consensus algorithm settles transactions in 4 to 5 seconds, processing at a throughput of up to 1500 transactions per second. These properties put XRP at least an order of magnitude ahead of other top digital assets. - **[Finite XRP Supply][]:** When the XRP Ledger began, 100 billion XRP were created, and no more XRP will ever be created. The available supply of XRP decreases slowly over time as small amounts are destroyed to pay transaction fees. - **[Responsible Software Governance][]:** A team of full-time developers at Ripple & other organizations maintain and continually improve the XRP Ledger's underlying software with contributions from the open-source community. Ripple acts as a steward for the technology and an advocate for its interests. - **[Secure, Adaptable Cryptography][]:** The XRP Ledger relies on industry standard digital signature systems like ECDSA (the same scheme used by Bitcoin) but also supports modern, efficient algorithms like Ed25519. The extensible nature of the XRP Ledger's software makes it possible to add and disable algorithms as the state of the art in cryptography advances. - **[Modern Features][]:** Features like Escrow, Checks, and Payment Channels support financial applications atop of the XRP Ledger. This toolbox of advanced features comes with safety features like a process for amending the network and separate checks against invariant constraints. - **[On-Ledger Decentralized Exchange][]:** In addition to all the features that make XRP useful on its own, the XRP Ledger also has a fully-functional accounting system for tracking and trading obligations denominated in any way users want, and an exchange built into the protocol. The XRP Ledger can settle long, cross-currency payment paths and exchanges of multiple currencies in atomic transactions, bridging gaps of trust with XRP. [Censorship-Resistant Transaction Processing]: https://xrpl.org/transaction-censorship-detection.html#transaction-censorship-detection [Fast, Efficient Consensus Algorithm]: https://xrpl.org/consensus-research.html#consensus-research [Finite XRP Supply]: https://xrpl.org/what-is-xrp.html [Responsible Software Governance]: https://xrpl.org/contribute-code.html#contribute-code-to-the-xrp-ledger [Secure, Adaptable Cryptography]: https://xrpl.org/cryptographic-keys.html#cryptographic-keys [Modern Features]: https://xrpl.org/use-specialized-payment-types.html [On-Ledger Decentralized Exchange]: https://xrpl.org/decentralized-exchange.html#decentralized-exchange ## Source Code Here are some good places to start learning the source code: - Read the markdown files in the source tree: `src/xrpld/**/*.md`. - Read [the levelization document](.github/scripts/levelization) to get an idea of the internal dependency graph. - In the big picture, the `main` function constructs an `ApplicationImp` object, which implements the `Application` virtual interface. Almost every component in the application takes an `Application&` parameter in its constructor, typically named `app` and stored as a member variable `app_`. This allows most components to depend on any other component. ### Repository Contents | Folder | Contents | | :--------- | :--------------------------------------------- | | `./bin` | Scripts and data files for XRPL developers. | | `./Builds` | Platform-specific guides for building `xrpld`. | | `./docs` | Source documentation files and doxygen config. | | `./cfg` | Example configuration files. | | `./src` | Source code. | | `./crates` | Rust source code. | Some of the directories under `src` are external repositories included using git-subtree. See those directories' README files for more details. ## Additional Documentation - [XRP Ledger Dev Portal](https://xrpl.org/) - [Setup and Installation](https://xrpl.org/install-rippled.html) - [Source Documentation (Doxygen)](https://xrplf.github.io/rippled/) ## See Also - [Clio API Server for the XRP Ledger](https://github.com/XRPLF/clio) - [Mailing List for Release Announcements](https://groups.google.com/g/ripple-server) - [Learn more about the XRP Ledger (YouTube)](https://www.youtube.com/playlist?list=PLJQ55Tj1hIVZtJ_JdTvSum2qMTsedWkNi) --- ## File: conan/lockfile/README.md # Conan lockfile To achieve reproducible dependencies, we use a [Conan lockfile](https://docs.conan.io/2/tutorial/versioning/lockfiles.html). The `conan.lock` file in the repository contains a "snapshot" of the current dependencies. It is implicitly used when running `conan` commands, so you don't need to specify it. You have to update this file every time you add a new dependency or change a revision or version of an existing dependency. To update a lockfile, run from the repository root: `./conan/lockfile/regenerate.sh` --- ## File: docs/0010-ledger-replay/README.md # Ledger Replay `LedgerReplayer` is a new `Stoppable` for replaying ledgers. Patterned after two other `Stoppable`s under `JobQueue`---`InboundLedgers` and `InboundTransactions`---it acts like a factory for creating state-machine workers, and a network message demultiplexer for those workers. Think of these workers like asynchronous functions. Like functions, they each take a set of parameters. The `Stoppable` memoizes these functions. It maintains a table for each worker type, mapping sets of arguments to the worker currently working on that argument set. Whenever the `Stoppable` is asked to construct a worker, it first searches its table to see if there is an existing worker with the same or overlapping argument set. If one exists, then it is used. If not, then a new one is created, initialized, and added to the table. For `LedgerReplayer`, there are three worker types: `LedgerReplayTask`, `SkipListAcquire`, and `LedgerDeltaAcquire`. Each is derived from `TimeoutCounter` to give it a timeout. For `LedgerReplayTask`, the parameter set is {reason, finish ledger ID, number of ledgers}. For `SkipListAcquire` and `LedgerDeltaAcquire`, there is just one parameter: a ledger ID. Each `Stoppable` has an entry point. For `LedgerReplayer`, it is `replay`. `replay` creates two workers: a `LedgerReplayTask` and a `SkipListAcquire`. `LedgerDeltaAcquire`s are created in the callback for when the skip list returns. For `SkipListAcquire` and `LedgerDeltaAcquire`, initialization fires off the underlying asynchronous network request and starts the timeout. The argument set identifying the worker is included in the network request, and copied to the network response. `SkipListAcquire` sends a request for a proof path for the skip list of the desired ledger. `LedgerDeltaAcquire` sends a request for the transaction set of the desired ledger. `LedgerReplayer` is also a network message demultiplexer. When a response arrives for a request that was sent by a `SkipListAcquire` or `LedgerDeltaAcquire` worker, the `Peer` object knows to send it to the `LedgerReplayer`, which looks up the worker waiting for that response based on the identifying argument set included in the response. `LedgerReplayTask` may ask `InboundLedgers` to send requests to acquire the start ledger, but there is no way to attach a callback or be notified when the `InboundLedger` worker completes. All the responses for its messages will be directed to `InboundLedgers`, not `LedgerReplayer`. Instead, `LedgerReplayTask` checks whether the start ledger has arrived every time its timeout expires. Like a promise, each worker keeps track of whether it is pending (`!isDone()`) or whether it has resolved successfully (`complete_ == true`) or unsuccessfully (`failed_ == true`). It will never exist in both resolved states at once, nor will it return to a pending state after reaching a resolved state. Like promises, some workers can accept continuations to be called when they reach a resolved state, or immediately if they are already resolved. `SkipListAcquire` and `LedgerDeltaAcquire` both accept continuations of a type specific to their payload, both via a method named `addDataCallback()`. Continuations cannot be removed explicitly, but they are held by `std::weak_ptr` so they can be removed implicitly. `LedgerReplayTask` is simultaneously: 1. an asynchronous function, 1. a continuation to one `SkipListAcquire` asynchronous function, 1. a continuation to zero or more `LedgerDeltaAcquire` asynchronous functions, and 1. a continuation to its own timeout. Each of these roles corresponds to different entry points: 1. `init()` 1. the callback added to `SkipListAcquire`, which calls `updateSkipList(...)` or `cancel()` 1. the callback added to `LedgerDeltaAcquire`, which calls `deltaReady(...)` or `cancel()` 1. `onTimer()` Each of these entry points does something unique to that entry point. They either (a) transition `LedgerReplayTask` to a terminal failed resolved state (`cancel()` and `onTimer()`) or (b) try to make progress toward the successful resolved state. `init()` and `updateSkipList(...)` call `trigger()` while `deltaReady(...)` calls `tryAdvance()`. There's a similarity between this pattern and the way coroutines are implemented, where every yield saves the spot in the code where it left off and every resume jumps back to that spot. ### Sequence Diagram ### Class Diagram --- ## File: docs/0001-negative-unl/README.md # Negative UNL Engineering Spec ## The Problem Statement The moment-to-moment health of the XRP Ledger network depends on the health and connectivity of a small number of computers (nodes). The most important nodes are validators, specifically ones listed on the unique node list ([UNL](#Question-What-are-UNLs)). Ripple publishes a recommended UNL that most network nodes use to determine which peers in the network are trusted. Although most validators use the same list, they are not required to. The XRP Ledger network progresses to the next ledger when enough validators reach agreement (above the minimum quorum of 80%) about what transactions to include in the next ledger. As an example, if there are 10 validators on the UNL, at least 8 validators have to agree with the latest ledger for it to become validated. But what if enough of those validators are offline to drop the network below the 80% quorum? The XRP Ledger network favors safety/correctness over advancing the ledger. Which means if enough validators are offline, the network will not be able to validate ledgers. Unfortunately validators can go offline at any time for many different reasons. Power outages, network connectivity issues, and hardware failures are just a few scenarios where a validator would appear "offline". Given that most of these events are temporary, it would make sense to temporarily remove that validator from the UNL. But the UNL is updated infrequently and not every node uses the same UNL. So instead of removing the unreliable validator from the Ripple recommended UNL, we can create a second negative UNL which is stored directly on the ledger (so the entire network has the same view). This will help the network see which validators are **currently** unreliable, and adjust their quorum calculation accordingly. _Improving the liveness of the network is the main motivation for the negative UNL._ ### Targeted Faults In order to determine which validators are unreliable, we need clearly define what kind of faults to measure and analyze. We want to deal with the faults we frequently observe in the production network. Hence we will only monitor for validators that do not reliably respond to network messages or send out validations disagreeing with the locally generated validations. We will not target other byzantine faults. To track whether or not a validator is responding to the network, we could monitor them with a “heartbeat” protocol. Instead of creating a new heartbeat protocol, we can leverage some existing protocol messages to mimic the heartbeat. We picked validation messages because validators should send one and only one validation message per ledger. In addition, we only count the validation messages that agree with the local node's validations. With the negative UNL, the network could keep making forward progress safely even if the number of remaining validators gets to 60%. Say we have a network with 10 validators on the UNL and everything is operating correctly. The quorum required for this network would be 8 (80% of 10). When validators fail, the quorum required would be as low as 6 (60% of 10), which is the absolute **_minimum quorum_**. We need the absolute minimum quorum to be strictly greater than 50% of the original UNL so that there cannot be two partitions of well-behaved nodes headed in different directions. We arbitrarily choose 60% as the minimum quorum to give a margin of safety. Consider these events in the absence of negative UNL: 1. 1:00pm - validator1 fails, votes vs. quorum: 9 >= 8, we have quorum 1. 3:00pm - validator2 fails, votes vs. quorum: 8 >= 8, we have quorum 1. 5:00pm - validator3 fails, votes vs. quorum: 7 < 8, we don’t have quorum - **network cannot validate new ledgers with 3 failed validators** We're below 80% agreement, so new ledgers cannot be validated. This is how the XRP Ledger operates today, but if the negative UNL was enabled, the events would happen as follows. (Please note that the events below are from a simplified version of our protocol.) 1. 1:00pm - validator1 fails, votes vs. quorum: 9 >= 8, we have quorum 1. 1:40pm - network adds validator1 to negative UNL, quorum changes to ceil(9 \* 0.8), or 8 1. 3:00pm - validator2 fails, votes vs. quorum: 8 >= 8, we have quorum 1. 3:40pm - network adds validator2 to negative UNL, quorum changes to ceil(8 \* 0.8), or 7 1. 5:00pm - validator3 fails, votes vs. quorum: 7 >= 7, we have quorum 1. 5:40pm - network adds validator3 to negative UNL, quorum changes to ceil(7 \* 0.8), or 6 1. 7:00pm - validator4 fails, votes vs. quorum: 6 >= 6, we have quorum - **network can still validate new ledgers with 4 failed validators** ## External Interactions ### Message Format Changes This proposal will: 1. add a new pseudo-transaction type 1. add the negative UNL to the ledger data structure. Any tools or systems that rely on the format of this data will have to be updated. ### Amendment This feature **will** need an amendment to activate. ## Design This section discusses the following topics about the Negative UNL design: - [Negative UNL protocol overview](#Negative-UNL-Protocol-Overview) - [Validator reliability measurement](#Validator-Reliability-Measurement) - [Format Changes](#Format-Changes) - [Negative UNL maintenance](#Negative-UNL-Maintenance) - [Quorum size calculation](#Quorum-Size-Calculation) - [Filter validation messages](#Filter-Validation-Messages) - [High level sequence diagram of code changes](#High-Level-Sequence-Diagram-of-Code-Changes) ### Negative UNL Protocol Overview Every ledger stores a list of zero or more unreliable validators. Updates to the list must be approved by the validators using the consensus mechanism that validators use to agree on the set of transactions. The list is used only when checking if a ledger is fully validated. If a validator V is in the list, nodes with V in their UNL adjust the quorum and V’s validation message is not counted when verifying if a ledger is fully validated. V’s flow of messages and network interactions, however, will remain the same. We define the **\*effective UNL** = original UNL - negative UNL\*, and the **_effective quorum_** as the quorum of the _effective UNL_. And we set _effective quorum = Ceiling(80% _ effective UNL)\*. ### Validator Reliability Measurement A node only measures the reliability of validators on its own UNL, and only proposes based on local observations. There are many metrics that a node can measure about its validators, but we have chosen ledger validation messages. This is because every validator shall send one and only one signed validation message per ledger. This keeps the measurement simple and removes timing/clock-sync issues. A node will measure the percentage of agreeing validation messages (_PAV_) received from each validator on the node's UNL. Note that the node will only count the validation messages that agree with its own validations. We define the **PAV** as the Percentage of Agreed Validation messages received for the last N ledgers, where N = 256 by default. When the PAV drops below the **_low-water mark_**, the validator is considered unreliable, and is a candidate to be disabled by being added to the negative UNL. A validator must have a PAV higher than the **_high-water mark_** to be re-enabled. The validator is re-enabled by removing it from the negative UNL. In the implementation, we plan to set the low-water mark as 50% and the high-water mark as 80%. ### Format Changes The negative UNL component in a ledger contains three fields. - **_NegativeUNL_**: The current negative UNL, a list of unreliable validators. - **_ToDisable_**: The validator to be added to the negative UNL on the next flag ledger. - **_ToReEnable_**: The validator to be removed from the negative UNL on the next flag ledger. All three fields are optional. When the _ToReEnable_ field exists, the _NegativeUNL_ field cannot be empty. A new pseudo-transaction, **_UNLModify_**, is added. It has three fields - **_Disabling_**: A flag indicating whether the modification is to disable or to re-enable a validator. - **_Seq_**: The ledger sequence number. - **_Validator_**: The validator to be disabled or re-enabled. There would be at most one _disable_ `UNLModify` and one _re-enable_ `UNLModify` transaction per flag ledger. The full machinery is described further on. ### Negative UNL Maintenance The negative UNL can only be modified on the flag ledgers. If a validator's reliability status changes, it takes two flag ledgers to modify the negative UNL. Let's see an example of the algorithm: - Ledger seq = 100: A validator V goes offline. - Ledger seq = 256: This is a flag ledger, and V's reliability measurement _PAV_ is lower than the low-water mark. Other validators add `UNLModify` pseudo-transactions `{true, 256, V}` to the transaction set which goes through the consensus. Then the pseudo-transaction is applied to the negative UNL ledger component by setting `ToDisable = V`. - Ledger seq = 257 ~ 511: The negative UNL ledger component is copied from the parent ledger. - Ledger seq=512: This is a flag ledger, and the negative UNL is updated `NegativeUNL = NegativeUNL + ToDisable`. The negative UNL may have up to `MaxNegativeListed = floor(original UNL * 25%)` validators. The 25% is because of 75% \* 80% = 60%, where 75% = 100% - 25%, 80% is the quorum of the effective UNL, and 60% is the absolute minimum quorum of the original UNL. Adding more than 25% validators to the negative UNL does not improve the liveness of the network, because adding more validators to the negative UNL cannot lower the effective quorum. The following is the detailed algorithm: - **If** the ledger seq = x is a flag ledger 1. Compute `NegativeUNL = NegativeUNL + ToDisable - ToReEnable` if they exist in the parent ledger 1. Try to find a candidate to disable if `sizeof NegativeUNL < MaxNegativeListed` 1. Find a validator V that has a _PAV_ lower than the low-water mark, but is not in `NegativeUNL`. 1. If two or more are found, their public keys are XORed with the hash of the parent ledger and the one with the lowest XOR result is chosen. 1. If V is found, create a `UNLModify` pseudo-transaction `TxDisableValidator = {true, x, V}` 1. Try to find a candidate to re-enable if `sizeof NegativeUNL > 0`: 1. Find a validator U that is in `NegativeUNL` and has a _PAV_ higher than the high-water mark. 1. If U is not found, try to find one in `NegativeUNL` but not in the local _UNL_. 1. If two or more are found, their public keys are XORed with the hash of the parent ledger and the one with the lowest XOR result is chosen. 1. If U is found, create a `UNLModify` pseudo-transaction `TxReEnableValidator = {false, x, U}` 1. If any `UNLModify` pseudo-transactions are created, add them to the transaction set. The transaction set goes through the consensus algorithm. 1. If have enough support, the `UNLModify` pseudo-transactions remain in the transaction set agreed by the validators. Then the pseudo-transactions are applied to the ledger: 1. If have `TxDisableValidator`, set `ToDisable=TxDisableValidator.V`. Else clear `ToDisable`. 1. If have `TxReEnableValidator`, set `ToReEnable=TxReEnableValidator.U`. Else clear `ToReEnable`. - **Else** (not a flag ledger) 1. Copy the negative UNL ledger component from the parent ledger The negative UNL is stored on each ledger because we don't know when a validator may reconnect to the network. If the negative UNL was stored only on every flag ledger, then a new validator would have to wait until it acquires the latest flag ledger to know the negative UNL. So any new ledgers created that are not flag ledgers copy the negative UNL from the parent ledger. Note that when we have a validator to disable and a validator to re-enable at the same flag ledger, we create two separate `UNLModify` pseudo-transactions. We want either one or the other or both to make it into the ledger on their own merits. Readers may have noticed that we defined several rules of creating the `UNLModify` pseudo-transactions but did not describe how to enforce the rules. The rules are actually enforced by the existing consensus algorithm. Unless enough validators propose the same pseudo-transaction it will not be included in the transaction set of the ledger. ### Quorum Size Calculation The effective quorum is 80% of the effective UNL. Note that because at most 25% of the original UNL can be on the negative UNL, the quorum should not be lower than the absolute minimum quorum (i.e. 60%) of the original UNL. However, considering that different nodes may have different UNLs, to be safe we compute `quorum = Ceiling(max(60% * original UNL, 80% * effective UNL))`. ### Filter Validation Messages If a validator V is in the negative UNL, it still participates in consensus sessions in the same way, i.e. V still follows the protocol and publishes proposal and validation messages. The messages from V are still stored the same way by everyone, used to calculate the new PAV for V, and could be used in future consensus sessions if needed. However V's ledger validation message is not counted when checking if the ledger is fully validated. ### High Level Sequence Diagram of Code Changes The diagram below is the sequence of one round of consensus. Classes and components with non-trivial changes are colored green. - The `ValidatorList` class is modified to compute the quorum of the effective UNL. - The `Validations` class provides an interface for querying the validation messages from trusted validators. - The `ConsensusAdaptor` component: - The `RCLConsensus::Adaptor` class is modified for creating `UNLModify` Pseudo-Transactions. - The `Change` class is modified for applying `UNLModify` Pseudo-Transactions. - The `Ledger` class is modified for creating and adjusting the negative UNL ledger component. - The `LedgerMaster` class is modified for filtering out validation messages from negative UNL validators when verifying if a ledger is fully validated. ![Sequence diagram](./negativeUNL_highLevel_sequence.png?raw=true "Negative UNL Changes") ## Roads Not Taken ### Use a Mechanism Like Fee Voting to Process UNLModify Pseudo-Transactions The previous version of the negative UNL specification used the same mechanism as the [fee voting](https://xrpl.org/fee-voting.html#voting-process.) for creating the negative UNL, and used the negative UNL as soon as the ledger was fully validated. However the timing of fully validation can differ among nodes, so different negative UNLs could be used, resulting in different effective UNLs and different quorums for the same ledger. As a result, the network's safety is impacted. This updated version does not impact safety though operates a bit more slowly. The negative UNL modifications in the _UNLModify_ pseudo-transaction approved by the consensus will take effect at the next flag ledger. The extra time of the 256 ledgers should be enough for nodes to be in sync of the negative UNL modifications. ### Use an Expiration Approach to Re-enable Validators After a validator disabled by the negative UNL becomes reliable, other validators explicitly vote for re-enabling it. An alternative approach to re-enable a validator is the expiration approach, which was considered in the previous version of the specification. In the expiration approach, every entry in the negative UNL has a fixed expiration time. One flag ledger interval was chosen as the expiration interval. Once expired, the other validators must continue voting to keep the unreliable validator on the negative UNL. The advantage of this approach is its simplicity. But it has a requirement. The negative UNL protocol must be able to vote multiple unreliable validators to be disabled at the same flag ledger. In this version of the specification, however, only one unreliable validator can be disabled at a flag ledger. So the expiration approach cannot be simply applied. ### Validator Reliability Measurement and Flag Ledger Frequency If the ledger time is about 4.5 seconds and the low-water mark is 50%, then in the worst case, it takes 48 minutes _((0.5 _ 256 + 256 + 256) _ 4.5 / 60 = 48)_ to put an offline validator on the negative UNL. We considered lowering the flag ledger frequency so that the negative UNL can be more responsive. We also considered decoupling the reliability measurement and flag ledger frequency to be more flexible. In practice, however, their benefits are not clear. ## New Attack Vectors A group of malicious validators may try to frame a reliable validator and put it on the negative UNL. But they cannot succeed. Because: 1. A reliable validator sends a signed validation message every ledger. A sufficient peer-to-peer network will propagate the validation messages to other validators. The validators will decide if another validator is reliable or not only by its local observation of the validation messages received. So an honest validator’s vote on another validator’s reliability is accurate. 1. Given the votes are accurate, and one vote per validator, an honest validator will not create a UNLModify transaction of a reliable validator. 1. A validator can be added to a negative UNL only through a UNLModify transaction. Assuming the group of malicious validators is less than the quorum, they cannot frame a reliable validator. ## Summary The bullet points below briefly summarize the current proposal: - The motivation of the negative UNL is to improve the liveness of the network. - The targeted faults are the ones frequently observed in the production network. - Validators propose negative UNL candidates based on their local measurements. - The absolute minimum quorum is 60% of the original UNL. - The format of the ledger is changed, and a new _UNLModify_ pseudo-transaction is added. Any tools or systems that rely on the format of these data will have to be updated. - The negative UNL can only be modified on the flag ledgers. - At most one validator can be added to the negative UNL at a flag ledger. - At most one validator can be removed from the negative UNL at a flag ledger. - If a validator's reliability status changes, it takes two flag ledgers to modify the negative UNL. - The quorum is the larger of 80% of the effective UNL and 60% of the original UNL. - If a validator is on the negative UNL, its validation messages are ignored when the local node verifies if a ledger is fully validated. ## FAQ ### Question: What are UNLs? Quote from the [Technical FAQ](https://xrpl.org/technical-faq.html): "They are the lists of transaction validators a given participant believes will not conspire to defraud them." ### Question: How does the negative UNL proposal affect network liveness? The network can make forward progress when more than a quorum of the trusted validators agree with the progress. The lower the quorum size is, the easier for the network to progress. If the quorum is too low, however, the network is not safe because nodes may have different results. So the quorum size used in the consensus protocol is a balance between the safety and the liveness of the network. The negative UNL reduces the size of the effective UNL, resulting in a lower quorum size while keeping the network safe.

Question: How does a validator get into the negative UNL? How is a validator removed from the negative UNL?

A validator’s reliability is measured by other validators. If a validator becomes unreliable, at a flag ledger, other validators propose _UNLModify_ pseudo-transactions which vote the validator to add to the negative UNL during the consensus session. If agreed, the validator is added to the negative UNL at the next flag ledger. The mechanism of removing a validator from the negative UNL is the same. ### Question: Given a negative UNL, what happens if the UNL changes? Answer: Let’s consider the cases: 1. A validator is added to the UNL, and it is already in the negative UNL. This case could happen when not all the nodes have the same UNL. Note that the negative UNL on the ledger lists unreliable nodes that are not necessarily the validators for everyone. In this case, the liveness is affected negatively. Because the minimum quorum could be larger but the usable validators are not increased. 1. A validator is removed from the UNL, and it is in the negative UNL. In this case, the liveness is affected positively. Because the quorum could be smaller but the usable validators are not reduced. 1. A validator is added to the UNL, and it is not in the negative UNL. 1. A validator is removed from the UNL, and it is not in the negative UNL. Case 3 and 4 are not affected by the negative UNL protocol. ### Question: Can we simply lower the quorum to 60% without the negative UNL? Answer: No, because the negative UNL approach is safer. First let’s compare the two approaches intuitively, (1) the _negative UNL_ approach, and (2) _lower quorum_: simply lowering the quorum from 80% to 60% without the negative UNL. The negative UNL approach uses consensus to come up with a list of unreliable validators, which are then removed from the effective UNL temporarily. With this approach, the list of unreliable validators is agreed to by a quorum of validators and will be used by every node in the network to adjust its UNL. The quorum is always 80% of the effective UNL. The lower quorum approach is a tradeoff between safety and liveness and against our principle of preferring safety over liveness. Note that different validators don't have to agree on which validation sources they are ignoring. Next we compare the two approaches quantitatively with examples, and apply Theorem 8 of [Analysis of the XRP Ledger Consensus Protocol](https://arxiv.org/abs/1802.07242) paper: _XRP LCP guarantees fork safety if **Oi,j > nj / 2 + ni − qi + ti,j** for every pair of nodes Pi, Pj,_ where _Oi,j_ is the overlapping requirement, nj and ni are UNL sizes, qi is the quorum size of Pi, _ti,j = min(ti, tj, Oi,j)_, and ti and tj are the number of faults can be tolerated by Pi and Pj. We denote _UNLi_ as _Pi's UNL_, and _|UNLi|_ as the size of _Pi's UNL_. Assuming _|UNLi| = |UNLj|_, let's consider the following three cases: 1. With 80% quorum and 20% faults, _Oi,j > 100% / 2 + 100% - 80% + 20% = 90%_. I.e. fork safety requires > 90% UNL overlaps. This is one of the results in the analysis paper. 1. If the quorum is 60%, the relationship between the overlapping requirement and the faults that can be tolerated is _Oi,j > 90% + ti,j_. Under the same overlapping condition (i.e. 90%), to guarantee the fork safety, the network cannot tolerate any faults. So under the same overlapping condition, if the quorum is simply lowered, the network can tolerate fewer faults. 1. With the negative UNL approach, we want to argue that the inequation _Oi,j > nj / 2 + ni − qi + ti,j_ is always true to guarantee fork safety, while the negative UNL protocol runs, i.e. the effective quorum is lowered without weakening the network's fault tolerance. To make the discussion easier, we rewrite the inequation as _Oi,j > nj / 2 + (ni − qi) + min(ti, tj)_, where Oi,j is dropped from the definition of ti,j because _Oi,j > min(ti, tj)_ always holds under the parameters we will use. Assuming a validator V is added to the negative UNL, now let's consider the 4 cases: 1. V is not on UNLi nor UNLj The inequation holds because none of the variables change. 1. V is on UNLi but not on UNLj The value of *(ni − qi)* is smaller. The value of *min(ti, tj)* could be smaller too. Other variables do not change. Overall, the left side of the inequation does not change, but the right side is smaller. So the inequation holds. 1. V is not on UNLi but on UNLj The value of *nj / 2* is smaller. The value of *min(ti, tj)* could be smaller too. Other variables do not change. Overall, the left side of the inequation does not change, but the right side is smaller. So the inequation holds. 1. V is on both UNLi and UNLj The value of *Oi,j* is reduced by 1. The values of *nj / 2*, *(ni − qi)*, and *min(ti, tj)* are reduced by 0.5, 0.2, and 1 respectively. The right side is reduced by 1.7. Overall, the left side of the inequation is reduced by 1, and the right side is reduced by 1.7. So the inequation holds. The inequation holds for all the cases. So with the negative UNL approach, the network's fork safety is preserved, while the quorum is lowered that increases the network's liveness.

Question: We have observed that occasionally a validator wanders off on its own chain. How is this case handled by the negative UNL algorithm?

Answer: The case that a validator wanders off on its own chain can be measured with the validations agreement. Because the validations by this validator must be different from other validators' validations of the same sequence numbers. When there are enough disagreed validations, other validators will vote this validator onto the negative UNL. In general by measuring the agreement of validations, we also measured the "sanity". If two validators have too many disagreements, one of them could be insane. When enough validators think a validator is insane, that validator is put on the negative UNL.

Question: Why would there be at most one disable UNLModify and one re-enable UNLModify transaction per flag ledger?

Answer: It is a design choice so that the effective UNL does not change too quickly. A typical targeted scenario is several validators go offline slowly during a long weekend. The current design can handle this kind of cases well without changing the effective UNL too quickly. ## Appendix ### Confidence Test We will use two test networks, a single machine test network with multiple IP addresses and the QE test network with multiple machines. The single machine network will be used to test all the test cases and to debug. The QE network will be used after that. We want to see the test cases still pass with real network delay. A test case specifies: 1. a UNL with different number of validators for different test cases, 1. a network with zero or more non-validator nodes, 1. a sequence of validator reliability change events (by killing/restarting nodes, or by running modified xrpld that does not send all validation messages), 1. the correct outcomes. For all the test cases, the correct outcomes are verified by examining logs. We will grep the log to see if the correct negative UNLs are generated, and whether or not the network is making progress when it should be. The ripdtop tool will be helpful for monitoring validators' states and ledger progress. Some of the timing parameters of xrpld will be changed to have faster ledger time. Most if not all test cases do not need client transactions. For example, the test cases for the prototype: 1. A 10-validator UNL. 1. The network does not have other nodes. 1. The validators will be started from the genesis. Once they start to produce ledgers, we kill five validators, one every flag ledger interval. Then we will restart them one by one. 1. A sequence of events (or the lack of events) such as a killed validator is added to the negative UNL. #### Roads Not Taken: Test with Extended CSF We considered testing with the current unit test framework, specifically the [Consensus Simulation Framework](https://github.com/XRPLF/rippled/blob/develop/src/test/csf/README.md) (CSF). However, the CSF currently can only test the generic consensus algorithm as in the paper: [Analysis of the XRP Ledger Consensus Protocol](https://arxiv.org/abs/1802.07242). --- ## File: docs/CheatSheet.md # Code Style Cheat Sheet ## Form - One class per header file. - Place each data member on its own line. - Place each ctor-initializer on its own line. - Create typedefs for primitive types to describe them. - Return descriptive local variables instead of constants. - Use long descriptive names instead of abbreviations. - Use "explicit" for single-argument ctors - Avoid globals especially objects with static storage duration - Order class declarations as types, public, protected, private, then data. - Prefer 'private' over 'protected' ## Function - Minimize external dependencies - Pass options in the ctor instead of using theConfig - Use as few other classes as possible --- ## File: docs/CodingStyle.md # Coding Standards Coding standards used here gradually evolve and propagate through code reviews. Some aspects are enforced more strictly than others. ## Rules These rules only apply to our own code. We can't enforce any sort of style on the external repositories and libraries we include. The best guideline is to maintain the standards that are used in those libraries. - Tab inserts 4 spaces. No tab characters. - Braces are indented in the [Allman style][1]. - Modern C++ principles. No naked `new` or `delete`. - Line lengths limited to 80 characters. Exceptions limited to data and tables. ## Guidelines If you want to do something contrary to these guidelines, understand why you're doing it. Think, use common sense, and consider that these changes will probably need to be maintained long after you've moved on to other projects. - Use white space and blank lines to guide the eye and keep your intent clear. - Put private data members at the top of a class, and the 6 public special members immediately after, in the following order: - Destructor - Default constructor - Copy constructor - Copy assignment - Move constructor - Move assignment - Don't over-inline by defining large functions within the class declaration, not even for template classes. ## Formatting The goal of source code formatting should always be to make things as easy to read as possible. White space is used to guide the eye so that details are not overlooked. Blank lines are used to separate code into "paragraphs." - Always place a space before and after all binary operators, especially assignments (`operator=`). - The `!` operator should be preceded by a space, but not followed by one. - The `~` operator should be preceded by a space, but not followed by one. - The `++` and `--` operators should have no spaces between the operator and the operand. - A space never appears before a comma, and always appears after a comma. - Don't put spaces after a parenthesis. A typical member function call might look like this: `foobar (1, 2, 3);` - In general, leave a blank line before an `if` statement. - In general, leave a blank line after a closing brace `}`. - Do not place code on the same line as any opening or closing brace. - Do not write `if` statements all-on-one-line. The exception to this is when you've got a sequence of similar `if` statements, and are aligning them all vertically to highlight their similarities. - In an `if-else` statement, if you surround one half of the statement with braces, you also need to put braces around the other half, to match. - When writing a pointer type, use this spacing: `SomeObject* myObject`. Technically, a more correct spacing would be `SomeObject *myObject`, but it makes more sense for the asterisk to be grouped with the type name, since being a pointer is part of the type, not the variable name. The only time that this can lead to any problems is when you're declaring multiple pointers of the same type in the same statement - which leads on to the next rule: - When declaring multiple pointers, never do so in a single statement, e.g. `SomeObject* p1, *p2;` - instead, always split them out onto separate lines and write the type name again, to make it quite clear what's going on, and avoid the danger of missing out any vital asterisks. - The previous point also applies to references, so always put the `&` next to the type rather than the variable, e.g. `void foo (Thing const& thing)`. And don't put a space on both sides of the `*` or `&` - always put a space after it, but never before it. - The word `const` should be placed to the right of the thing that it modifies, for consistency. For example `int const` refers to an int which is const. `int const*` is a pointer to an int which is const. `int *const` is a const pointer to an int. - Always place a space in between the template angle brackets and the type name. Template code is already hard enough to read! [1]: http://en.wikipedia.org/wiki/Indent_style#Allman_style --- ## File: docs/consensus.md # Consensus and Validation **This section is a work in progress!!** Consensus is the task of reaching agreement within a distributed system in the presence of faulty or even malicious participants. This document outlines the [XRP Ledger Consensus Algorithm](https://arxiv.org/abs/1802.07242) as implemented in [xrpld](https://github.com/XRPLF/rippled), but focuses on its utility as a generic consensus algorithm independent of the detailed mechanics of the XRPL consensus Ledger. Most notably, the algorithm does not require fully synchronous communication between all nodes in the network, or even a fixed network topology, but instead achieves consensus via collectively trusted subnetworks. ## Distributed Agreement A challenge for distributed systems is reaching agreement on changes in shared state. For the XRPL network, the shared state is the current ledger--account information, account balances, order books and other financial data. We will refer to shared distributed state as a /ledger/ throughout the remainder of this document. As shown above, new ledgers are made by applying a set of transactions to the prior ledger. For the XRPL network, transactions include payments, modification of account settings, updates to offers and more. In a centralized system, generating the next ledger is trivial since there is a single unique arbiter of which transactions to include and how to apply them to a ledger. For decentralized systems, participants must resolve disagreements on the set of transactions to include, the order to apply those transactions, and even the resulting ledger after applying the transactions. This is even more difficult when some participants are faulty or malicious. The XRPL network is a decentralized and **trust-full** network. Anyone is free to join and participants are free to choose a subset of peers that are collectively trusted to not collude in an attempt to defraud the participant. Leveraging this network of trust, the XRPL algorithm has two main components. - _Consensus_ in which network participants agree on the transactions to apply to a prior ledger, based on the positions of their chosen peers. - _Validation_ in which network participants agree on what ledger was generated, based on the ledgers generated by chosen peers. These phases are continually repeated to process transactions submitted to the network, generating successive ledgers and giving rise to the blockchain ledger history depicted below. In this diagram, time is flowing to the right, but links between ledgers point backward to the parent. Also note the alternate Ledger 2 that was generated by some participants, but which failed validation and was abandoned. The remainder of this section describes the Consensus and Validation algorithms in more detail and is meant as a companion guide to understanding the generic implementation in `xrpld`. The document **does not** discuss correctness, fault-tolerance or liveness properties of the algorithms or the full details of how they integrate within `xrpld` to support the XRPL consensus Ledger. ## Consensus Overview ### Definitions - The _ledger_ is the shared distributed state. Each ledger has a unique ID to distinguish it from all other ledgers. During consensus, the _previous_, _prior_ or _last-closed_ ledger is the most recent ledger seen by consensus and is the basis upon which it will build the next ledger. - A _transaction_ is an instruction for an atomic change in the ledger state. A unique ID distinguishes a transaction from other transactions. - A _transaction set_ is a set of transactions under consideration by consensus. The goal of consensus is to reach agreement on this set. The generic consensus algorithm does not rely on an ordering of transactions within the set, nor does it specify how to apply a transaction set to a ledger to generate a new ledger. A unique ID distinguishes a set of transactions from all other sets of transactions. - A _node_ is one of the distributed actors running the consensus algorithm. It has a unique ID to distinguish it from all other nodes. - A _peer_ of a node is another node that it has chosen to follow and which it believes will not collude with other chosen peers. The choice of peers is not symmetric, since participants can decide on their chosen sets independently. - A /position/ is the current belief of the next ledger's transaction set and close time. Position can refer to the node's own position or the position of a peer. - A _proposal_ is one of a sequence of positions a node shares during consensus. An initial proposal contains the starting position taken by a node before it considers any peer positions. If a node subsequently updates its position in response to its peers, it will issue an updated proposal. A proposal is uniquely identified by the ID of the proposing node, the ID of the position taken, the ID of the prior ledger the proposal is for, and the sequence number of the proposal. - A _dispute_ is a transaction that is either not part of a node's position or not in a peer's position. During consensus, the node will add or remove disputed transactions from its position based on that transaction's support amongst its peers. Note that most types have an ID as a lightweight identifier of instances of that type. Consensus often operates on the IDs directly since the underlying type is potentially expensive to share over the network. For example, proposal's only contain the ID of the position of a peer. Since many peers likely have the same position, this reduces the need to send the full transaction set multiple times. Instead, a node can request the transaction set from the network if necessary. ### Overview The diagram above is an overview of the consensus process from the perspective of a single participant. Recall that during a single consensus round, a node is trying to agree with its peers on which transactions to apply to its prior ledger when generating the next ledger. It also attempts to agree on the [network time when the ledger closed](#effective_close_time). There are 3 main phases to a consensus round: - A call to `startRound` places the node in the `Open` phase. In this phase, the node is waiting for transactions to include in its open ledger. - At some point, the node will `Close` the open ledger and transition to the `Establish` phase. In this phase, the node shares/receives peer proposals on which transactions should be accepted in the closed ledger. - At some point, the node determines it has reached consensus with its peers on which transactions to include. It transitions to the `Accept` phase. In this phase, the node works on applying the transactions to the prior ledger to generate a new closed ledger. Once the new ledger is completed, the node shares the validated ledger hash with the network and makes a call to `startRound` to start the cycle again for the next ledger. Throughout, a heartbeat timer calls `timerEntry` at a regular frequency to drive the process forward. Although the `startRound` call occurs at arbitrary times based on when the initial round began and the time it takes to apply transactions, the transitions from `Open` to `Establish` and `Establish` to `Accept` only occur during calls to `timerEntry`. Similarly, transactions can arrive at arbitrary times, independent of the heartbeat timer. Transactions received after the `Open` to `Close` transition and not part of peer proposals won't be considered until the next consensus round. They are represented above by the light green triangles. Peer proposals are issued by a node during a `timerEntry` call, but since peers do not synchronize `timerEntry` calls, they are received by other peers at arbitrary times. Peer proposals are only considered if received prior to the `Establish` to `Accept` transition, and only if the peer is working on the same prior ledger. Peer proposals received after consensus is reached will not be meaningful and are represented above by the circle with the X in it. Only proposals from chosen peers are considered. ### Effective Close Time ### {#effective_close_time} In addition to agreeing on a transaction set, each consensus round tries to agree on the time the ledger closed. Each node calculates its own close time when it closes the open ledger. This exact close time is rounded to the nearest multiple of the current _effective close time resolution_. It is this _effective close time_ that nodes seek to agree on. This allows servers to derive a common time for a ledger without the need for perfectly synchronized clocks. As depicted below, the 3 pink arrows represent exact close times from 3 consensus nodes that round to the same effective close time given the current resolution. The purple arrow represents a peer whose estimate rounds to a different effective close time given the current resolution. The effective close time is part of the node's position and is shared with peers in its proposals. Just like the position on the consensus transaction set, a node will update its close time position in response to its peers' effective close time positions. Peers can agree to disagree on the close time, in which case the effective close time is taken as 1 second past the prior close. The close time resolution is itself dynamic, decreasing (coarser) resolution in subsequent consensus rounds if nodes are unable to reach consensus on an effective close time and increasing (finer) resolution if nodes consistently reach close time consensus. ### Modes Internally, a node operates under one of the following consensus modes. Either of the first two modes may be chosen when a consensus round starts. - _Proposing_ indicates the node is a full-fledged consensus participant. It takes on positions and sends proposals to its peers. - _Observing_ indicates the node is a passive consensus participant. It maintains a position internally, but does not propose that position to its peers. Instead, it receives peer proposals and updates its position to track the majority of its peers. This may be preferred if the node is only being used to track the state of the network or during a start-up phase while it is still synchronizing with the network. The other two modes are set internally during the consensus round when the node believes it is no longer working on the dominant ledger chain based on peer validations. It checks this on every call to `timerEntry`. - _Wrong Ledger_ indicates the node is not working on the correct prior ledger and does not have it available. It requests that ledger from the network, but continues to work towards consensus this round while waiting. If it had been _proposing_, it will send a special "bow-out" proposal to its peers to indicate its change in mode for the rest of this round. For the duration of the round, it defers to peer positions for determining the consensus outcome as if it were just _observing_. - _Switch Ledger_ indicates that the node has acquired the correct prior ledger from the network. Although it now has the correct prior ledger, the fact that it had the wrong one at some point during this round means it is likely behind and should defer to peer positions for determining the consensus outcome. Once either wrong ledger or switch ledger are reached, the node cannot return to proposing or observing until the next consensus round. However, the node could change its view of the correct prior ledger, so going from switch ledger to wrong ledger and back again is possible. The distinction between the wrong and switched ledger modes arises because a ledger's unique identifier may be known by a node before the ledger itself. This reflects that fact that the data corresponding to a ledger may be large and take time to share over the network, whereas the smaller ID could be shared in a peer validation much more quickly. Distinguishing the two states allows the node to decide how best to generate the next ledger once it declares consensus. ### Phases As depicted in the overview diagram, consensus is best viewed as a progression through 3 phases. There are 4 public methods of the generic consensus algorithm that determine this progression - `startRound` begins a consensus round. - `timerEntry` is called at a regular frequency (`LEDGER_MIN_CLOSE`) and is the only call to consensus that can change the phase from `Open` to `Establish` or `Accept`. - `peerProposal` is called whenever a peer proposal is received and is what allows a node to update its position in a subsequent `timerEntry` call. - `gotTxSet` is called when a transaction set is received from the network. This is typically in response to a prior request from the node to acquire the transaction set corresponding to a disagreeing peer's position. The following subsections describe each consensus phase in more detail and what actions are taken in response to these calls. #### Open The `Open` phase is a quiescent period to allow transactions to build up in the node's open ledger. The duration is a trade-off between latency and throughput. A shorter window reduces the latency to generating the next ledger, but also reduces transaction throughput due to fewer transactions accepted into the ledger. A call to `startRound` would forcibly begin the next consensus round, skipping completion of the current round. This is not expected during normal operation. Calls to `peerProposal` or `gotTxSet` simply store the proposal or transaction set for use in the coming `Establish` phase. A call to `timerEntry` first checks that the node is working on the correct prior ledger. If not, it will update the mode and request the correct ledger. Otherwise, the node checks whether to switch to the `Establish` phase and close the ledger. ##### Ledger Close Under normal circumstances, the open ledger period ends when one of the following is true - if there are transactions in the open ledger and more than `LEDGER_MIN_CLOSE` have elapsed. This is the typical behavior. - if there are no open transactions and a suitably longer idle interval has elapsed. This increases the opportunity to get some transaction into the next ledger and avoids doing useless work closing an empty ledger. - if more than half the number of prior round peers have already closed or finished this round. This indicates the node is falling behind and needs to catch up. When closing the ledger, the node takes its initial position based on the transactions in the open ledger and uses the current time as its initial close time estimate. If in the proposing mode, the node shares its initial position with peers. Now that the node has taken a position, it will consider any peer positions for this round that arrived earlier. The node generates disputed transactions for each transaction not in common with a peer's position. The node also records the vote of each peer for each disputed transaction. In the example below, we suppose our node has closed with transactions 1,2 and 3. It creates disputes for transactions 2,3 and 4, since at least one peer position differs on each. ##### disputes ##### {#disputes_image} #### Establish The establish phase is the active period of consensus in which the node exchanges proposals with peers in an attempt to reach agreement on the consensus transactions and effective close time. A call to `startRound` would forcibly begin the next consensus round, skipping completion of the current round. This is not expected during normal operation. Calls to `peerProposal` or `gotTxSet` that reflect new positions will generate disputed transactions for any new disagreements and will update the peer's vote for all disputed transactions. A call to `timerEntry` first checks that the node is working from the correct prior ledger. If not, the node will update the mode and request the correct ledger. Otherwise, the node updates the node's position and considers whether to switch to the `Accepted` phase and declare consensus reached. However, at least `LEDGER_MIN_CONSENSUS` time must have elapsed before doing either. This allows peers an opportunity to take an initial position and share it. ##### Update Position In order to achieve consensus, the node is looking for a transaction set that is supported by a super-majority of peers. The node works towards this set by adding or removing disputed transactions from its position based on an increasing threshold for inclusion. By starting with a lower threshold, a node initially allows a wide set of transactions into its position. If the establish round continues and the node is "stuck", a higher threshold can focus on accepting transactions with the most support. The constants that define the thresholds and durations at which the thresholds change are given by `AV_XXX_CONSENSUS_PCT` and `AV_XXX_CONSENSUS_TIME` respectively, where `XXX` is `INIT`,`MID`,`LATE` and `STUCK`. The effective close time position is updated using the same thresholds. Given the [example disputes above](#disputes_image) and an initial threshold of 50%, our node would retain its position since transaction 1 was not in dispute and transactions 2 and 3 have 75% support. Since its position did not change, it would not need to send a new proposal to peers. Peer C would not change either. Peer A would add transaction 3 to its position and Peer B would remove transaction 4 from its position; both would then send an updated position. Conversely, if the diagram reflected a later call to =timerEntry= that occurs in the stuck region with a threshold of say 95%, our node would remove transactions 2 and 3 from its candidate set and send an updated position. Likewise, all the other peers would end up with only transaction 1 in their position. Lastly, if our node were not in the proposing mode, it would not include its own vote and just take the majority (>50%) position of its peers. In this example, our node would maintain its position of transactions 1, 2 and 3. ##### Checking Consensus After updating its position, the node checks for supermajority agreement with its peers on its current position. This agreement is of the exact transaction set, not just the support of individual transactions. That is, if our position is a subset of a peer's position, that counts as a disagreement. Also recall that effective close time agreement allows a supermajority of participants agreeing to disagree. Consensus is declared when the following 3 clauses are true: - `LEDGER_MIN_CONSENSUS` time has elapsed in the establish phase - At least 75% of the prior round proposers have proposed OR this establish phase is `LEDGER_MIN_CONSENSUS` longer than the last round's establish phase - `minimumConsensusPercentage` of ourself and our peers share the same position The middle condition ensures slower peers have a chance to share positions, but prevents waiting too long on peers that have disconnected. Additionally, a node can declare that consensus has moved on if `minimumConsensusPercentage` peers have sent validations and moved on to the next ledger. This outcome indicates the node has fallen behind its peers and needs to catch up. If a node is not proposing, it does not include its own position when calculating the percent of agreeing participants but otherwise follows the above logic. ##### Accepting Consensus Once consensus is reached (or moved on), the node switches to the `Accept` phase and signals to the implementing code that the round is complete. That code is responsible for using the consensus transaction set to generate the next ledger and calling `startRound` to begin the next round. The implementation has total freedom on ordering transactions, deciding what to do if consensus moved on, determining whether to retry or abandon local transactions that did not make the consensus set and updating any internal state based on the consensus progress. #### Accept The `Accept` phase is the terminal phase of the consensus algorithm. Calls to `timerEntry`, `peerProposal` and `gotTxSet` will not change the internal consensus state while in the accept phase. The expectation is that the application specific code is working to generate the new ledger based on the consensus outcome. Once complete, that code should make a call to `startRound` to kick off the next consensus round. The `startRound` call includes the new prior ledger, prior ledger ID and whether the round should begin in the proposing or observing mode. After setting some initial state, the phase transitions to `Open`. The node will also check if the provided prior ledger and ID are correct, updating the mode and requesting the proper ledger from the network if necessary. ## Consensus Type Requirements The consensus type requirements are given below as minimal implementation stubs. Actual implementations would augment these stubs with members appropriate for managing the details of transactions and ledgers within the larger application framework. ### Transaction The transaction type `Tx` encapsulates a single transaction under consideration by consensus. ```{.cpp} struct Tx { using ID = ...; ID const & id() const; //... implementation specific }; ``` ### Transaction Set The transaction set type `TxSet` represents a set of `Tx`s that are collectively under consideration by consensus. A `TxSet` can be compared against other `TxSet`s (typically from peers) and can be modified to add or remove transactions via the mutable subtype. ```{.cpp} struct TxSet { using Tx = Tx; using ID = ...; ID const & id() const; bool exists(Tx::ID const &) const; Tx const * find(Tx::ID const &) const ; // Return set of transactions that are not common with another set // Bool in map is true if in our set, false if in other std::map compare(TxSet const & other) const; // A mutable view that allows changing transactions in the set struct MutableTxSet { MutableTxSet(TxSet const &); bool insert(Tx const &); bool erase(Tx::ID const &); }; // Construct from a mutable view. TxSet(MutableTxSet const &); // Alternatively, if the TxSet is itself mutable // just alias MutableTxSet = TxSet //... implementation specific }; ``` ### Ledger The `Ledger` type represents the state shared amongst the distributed participants. Notice that the details of how the next ledger is generated from the prior ledger and the consensus accepted transaction set is not part of the interface. Within the generic code, this type is primarily used to know that peers are working on the same tip of the ledger chain and to provide some basic timing data for consensus. ```{.cpp} struct Ledger { using ID = ...; using Seq = //std::uint32_t?...; ID const & id() const; // Sequence number that is 1 more than the parent ledger's seq() Seq seq() const; // Whether the ledger's close time was a non-trivial consensus result bool closeAgree() const; // The close time resolution used in determining the close time NetClock::duration closeTimeResolution() const; // The (effective) close time, based on the closeTimeResolution NetClock::time_point closeTime() const; // The parent ledger's close time NetClock::time_point parentCloseTime() const; json::Value getJson() const; //... implementation specific }; ``` ### PeerProposal The `PeerProposal` type represents the signed position taken by a peer during consensus. The only type requirement is owning an instance of a generic `ConsensusProposal`. ```{.cpp} // Represents our proposed position or a peer's proposed position // and is provided with the generic code template class ConsensusProposal; struct PeerPosition { ConsensusProposal< NodeID_t, typename Ledger::ID, typename TxSet::ID> const & proposal() const; // ... implementation specific }; ``` ### Generic Consensus Interface The generic `Consensus` relies on `Adaptor` template class to implement a set of helper functions that plug the consensus algorithm into a specific application. The `Adaptor` class also defines the types above needed by the algorithm. Below are excerpts of the generic consensus implementation and of helper types that will interact with the concrete implementing class. ``` /* Detailed source-code truncated for AI context efficiency. */ ``` ### Adapting Generic Consensus The stub below shows the set of callback/helper functions required in the implementing class. ``` /* Detailed source-code truncated for AI context efficiency. */ ``` The implementing class hides many details of the peer communication model from the generic code. - The `share` member functions are responsible for sharing the given type with a node's peers, but are agnostic to the mechanism. Ideally, messages are delivered faster than `LEDGER_GRANULARITY`. - The generic code does not specify how transactions are submitted by clients, propagated through the network or stored in the open ledger. Indeed, the open ledger is only conceptual from the perspective of the generic code---the initial position and transaction set are opaquely generated in a `Consensus::Result` instance returned from the `onClose` callback. - The calls to `acquireLedger` and `acquireTxSet` only have non-trivial return if the ledger or transaction set of interest is available. The implementing class is free to block while acquiring, or return the empty option while servicing the request asynchronously. Due to legacy reasons, the two calls are not symmetric. `acquireTxSet` requires the host application to call `gotTxSet` when an asynchronous `acquire` completes. Conversely, `acquireLedger` will be called again later by the consensus code if it still desires the ledger with the hope that the asynchronous acquisition is complete. ## Validation Coming Soon! --- ## File: docs/Docker.md # `xrpld` Docker Image - Some info relating to Docker containers can be found here: [../Builds/containers](../Builds/containers) - Images for building and testing xrpld can be found here: [thejohnfreeman/rippled-docker](https://github.com/thejohnfreeman/rippled-docker/) - These images do not have xrpld. They have all the tools necessary to build xrpld. --- ## File: docs/HeapProfiling.md ## Heap profiling of xrpld with jemalloc The jemalloc library provides a good API for doing heap analysis, including a mechanism to dump a description of the heap from within the running application via a function call. Details on how to perform this activity in general, as well as how to acquire the software, are available on the jemalloc site: [https://github.com/jemalloc/jemalloc/wiki/Use-Case:-Heap-Profiling](https://github.com/jemalloc/jemalloc/wiki/Use-Case:-Heap-Profiling) jemalloc is acquired separately from xrpld, and is not affiliated with Ripple Labs. If you compile and install jemalloc from the source release with default options, it will install the library and header under `/usr/local/lib` and `/usr/local/include`, respectively. Heap profiling has been tested with xrpld on a Linux platform. It should work on platforms on which both xrpld and jemalloc are available. To link xrpld with jemalloc, the argument `profile-jemalloc=` is provided after the optional target. The `` argument should be the same as that of the `--prefix` parameter passed to the jemalloc configure script when building. ## Examples: Build xrpld with jemalloc library under /usr/local/lib and header under /usr/local/include: $ scons profile-jemalloc=/usr/local Build xrpld using clang with the jemalloc library under /opt/local/lib and header under /opt/local/include: $ scons clang profile-jemalloc=/opt/local --- ## Using the jemalloc library from within the code The `profile-jemalloc` parameter enables a macro definition called `PROFILE_JEMALLOC`. Include the jemalloc header file as well as the api call(s) that you wish to make within preprocessor conditional groups, such as: In global scope: #ifdef PROFILE_JEMALLOC #include #endif And later, within a function scope: #ifdef PROFILE_JEMALLOC mallctl("prof.dump", NULL, NULL, NULL, 0); #endif Fuller descriptions of how to acquire and use jemalloc's api to do memory analysis are available at the [jemalloc site.](http://www.canonware.com/jemalloc/) Linking against the jemalloc library will override the system's default `malloc()` and related functions with jemalloc's implementation. This is the case even if the code is not instrumented to use jemalloc's specific API. --- ## File: external/antithesis-sdk/README.md # Antithesis C++ SDK This library provides methods for C++ programs to configure the [Antithesis](https://antithesis.com) platform. It contains three kinds of functionality: - Assertion macros that allow you to define test properties about your software or workload. - Randomness functions for requesting both structured and unstructured randomness from the Antithesis platform. - Lifecycle functions that inform the Antithesis environment that particular test phases or milestones have been reached. For general usage guidance see the [Antithesis C++ SDK Documentation](https://antithesis.com/docs/using_antithesis/sdk/cpp/overview/)