Skip to content

Latest commit

 

History

History
237 lines (201 loc) · 8.79 KB

cap-0044.md

File metadata and controls

237 lines (201 loc) · 8.79 KB
Raw

Preamble

CAP: 0044
Title: SPEEDEX - Configuration
Working Group:
    Owner: Jonathan Jove <@jonjove>
    Authors: Geoff Ramseyer <@gramseyer>
    Consulted: Nicolas Barry <@monsieurnicolas>
Status: Draft
Created: 2022-02-01
Discussion: TBD
Protocol version: TBD

Simple Summary

Provide validators the ability to configure SPEEDEX.

Working Group

This proposal is based on an earlier draft written by Geoff Ramseyer, which Nicolas Barry has also contributed to.

Motivation

SPEEDEX requires two kinds of configuration: the set of assets comprising the market, and the parameters used by the built-in solver. The set of assets must be configurable because the time to compute a solution increases with the number of assets, so we cannot compute a solution for all assets. The parameters must be configurable because different parameters may work better during different market regimes.

Goals Alignment

This proposal supports the development of SPEEDEX on Stellar, which in turn supports the Stellar Network Goals

  • The Stellar Network should run at scale and at low cost to all participants of the network.
  • The Stellar Network should enable cross-border payments, i.e. payments via exchange of assets, throughout the globe, enabling users to make payments between assets in a manner that is fast, cheap, and highly usable.

Abstract

This proposal introduces SpeedexConfigurationEntry, a new type of LedgerEntry, that tracks the assets that can be traded in SPEEDEX and the solver configuration for computing the prices.

Specification

XDR changes

This patch of XDR changes is based on the XDR files in commit (a211531148f13ab38725bc176630793d657b7f88) of stellar-core.

diff --git a/src/xdr/Stellar-ledger-entries.x b/src/xdr/Stellar-ledger-entries.x
index c870fe09..cb91c48d 100644
--- a/src/xdr/Stellar-ledger-entries.x
+++ b/src/xdr/Stellar-ledger-entries.x
@@ -473,6 +473,31 @@ struct LiquidityPoolEntry
     body;
 };
 
+enum SpeedexSolutionComparisonHeuristic
+{
+    PRICE_WEIGHTED_SQUARED_L2_NORM = 0
+};
+
+struct SpeedexSolverConfiguration
+{
+    SpeedexSolutionComparisonHeuristic heuristic;
+    uint32 minStepSize;
+    uint32 smoothness;
+};
+
+struct SpeedexConfigurationEntry
+{
+    Asset asset<>;
+    SpeedexSolverConfiguration solverConfig;
+
+    union switch (int v)
+    {
+    case 0:
+        void;
+    }
+    ext;
+};
+
 struct LedgerEntryExtensionV1
 {
     SponsorshipDescriptor sponsoringID;
@@ -503,6 +528,8 @@ struct LedgerEntry
         ClaimableBalanceEntry claimableBalance;
     case LIQUIDITY_POOL:
         LiquidityPoolEntry liquidityPool;
+    case SPEEDEX_CONFIGURATION:
+        SpeedexConfigurationEntry speedexConfiguration;
     }
     data;
 
@@ -557,6 +584,9 @@ case LIQUIDITY_POOL:
     {
         PoolID liquidityPoolID;
     } liquidityPool;
+
+case SPEEDEX_CONFIGURATION:
+    void;
 };
 
 // list of all envelope types used in the application
diff --git a/src/xdr/Stellar-ledger.x b/src/xdr/Stellar-ledger.x
index 84b84cbf..141c0a70 100644
--- a/src/xdr/Stellar-ledger.x
+++ b/src/xdr/Stellar-ledger.x
@@ -122,7 +122,10 @@ enum LedgerUpgradeType
     LEDGER_UPGRADE_BASE_FEE = 2,
     LEDGER_UPGRADE_MAX_TX_SET_SIZE = 3,
     LEDGER_UPGRADE_BASE_RESERVE = 4,
-    LEDGER_UPGRADE_FLAGS = 5
+    LEDGER_UPGRADE_FLAGS = 5,
+    LEDGER_UPGRADE_ADD_SPEEDEX_ASSET = 6,
+    LEDGER_UPGRADE_REMOVE_SPEEDEX_ASSET = 7,
+    LEDGER_UPGRADE_SPEEDEX_TATONNEMENT_CONFIGURATION = 8
 };
 
 union LedgerUpgrade switch (LedgerUpgradeType type)
@@ -137,6 +140,12 @@ case LEDGER_UPGRADE_BASE_RESERVE:
     uint32 newBaseReserve; // update baseReserve
 case LEDGER_UPGRADE_FLAGS:
     uint32 newFlags; // update flags
+case LEDGER_UPGRADE_SPEEDEX_ADD_ASSET:
+    Asset speedexAddAsset; // add asset to list of eligible assets
+case LEDGER_UPGRADE_SPEEDEX_REMOVE_ASSET:
+    Asset speedexRemoveAsset; // remove asset from list of eligible assets
+case LEDGER_UPGRADE_SPEEDEX_SOLVER_CONFIGURATION:
+    SpeedexSolverConfiguration speedexNewConfig; // update solver configuration
 };
 
 /* Entries used to define the bucket list */

Semantics

During the protocol upgrade, a SpeedexConfigurationEntry will be initialized with an empty list of assets and a reasonable default solver configuration. The default solver configuration will be detailed when the actual parameters are specified.

There is only ever one SpeedexConfigurationEntry.

The set of assets

SpeedexConfigurationEntry.asset is an ordered list of assets, using the same ordering as CAP-0038. When an asset is added to the set, it must be inserted in the appropriate location. The set can be modified by the upgrades LEDGER_UPGRADE_SPEEDEX_ADD_ASSET and LEDGER_UPGRADE_SPEEDEX_REMOVE_ASSET.

The add/remove asset upgrades

The upgrade LEDGER_UPGRADE_SPEEDEX_ADD_ASSET is valid if the asset is valid, the asset is not a pool share, and the asset is not currently a SPEEDEX asset.

The upgrade LEDGER_UPGRADE_SPEEDEX_REMOVE_ASSET is valid if the asset is currently a SPEEDEX asset (which implies that the asset is valid, and that the asset is not a pool share).

The solver configuration upgrade

The upgrade LEDGER_UPGRADE_SPEEDEX_SOLVER_CONFIGURATION is valid if the configuration is valid. The validity conditions will be detailed when the actual parameters are specified.

Design Rationale

SPEEDEX has a number of control parameters determining how to run the solver (current default solver is Tatonnement). Most of these parameters can take any value in a reasonable range and produce a reasonably good result. However, based on changes in the distribution of data sent to SPEEDEX, Stellar may wish to occasionally adjust or fine-tune these parameters. This CAP enables Stellar to adjust these parameters without doing a full protocol update.

For example, one important parameter is the "smoothness" parameter (name TBD, I've yet to come up with a concise but descriptive name). This parameter specifies how offers behave within Tatonnement. An offer's optimal behavior is a step function -- that is, sell all of its endowment iff the market price is strictly greater than its limit price. Tatonnement works best, though, with a smooth demand curve. This "smoothness" parameter defines an approximation of offer optimal behavior -- offers sell their endowment fully if the market price is at least (1+\mu) greater (multiplicatively) than their minimum price, not at all if the market price is less than the offer's minimum price, and linearly interpolate on the interim. Smaller smoothness parameters result in harder-to-compute Tatonnement instances (which might require more rounds of computation, e.g.), but more accurate results when Tatonnement successfully converges. Experimentally, larger numbers of trade offers can allow Tatonnement to handle smaller smoothness multipliers. As such, Stellar may want to adjust the smoothness multiplier in response to network traffic.

Alternative configuration mechanisms

A number of different approaches to SPEEDEX configuration were considered, in addition to this proposal:

  • validators propose the entire configuration, including the set of assets, during nomination
  • validators propose the solver configuration, but not the set of assets, during nomination

The first proposal would be the SPEEDEX equivalent of anarchy. The market would be different in every ledger, and people may not be able to trade when they want to depending on which node nominates.

The second proposal is more palatable, but is still worse than this proposal. In order for SPEEDEX to be robust to the nomination of a pathological solver configuration, it must run a backup computation with a more trustworthy configuration. But how should that configuration be chosen? It could be fixed or chosen via upgrades. If it is fixed, then it won't be robust to changes in market regime. If it is chosen via upgrades, then it reduces to this proposal.

With this proposal, the solver configuration is for the backup computation. But instead of nominating a solver configuration, nodes nominate a complete set of candidate prices (not detailed in this proposal).

All SPEEDEX assets in a single ledger entry

This proposal stores all SPEEDEX assets in a single ledger entry. Initially, I had favored a design where every SPEEDEX asset has its own ledger entry because it keeps the ledger entry size bounded. But every node needs to know the full set of SPEEDEX assets in order to perform the price computation, which would necessitate loading all of the SPEEDEX asset ledger entries anyway.

Protocol Upgrade Transition

Backwards Incompatibilities

This proposal does not introduce any backwards incompatibilities.

Resource Utilization

This proposal does not change resource utilization.

Security Concerns

This proposal does not introduce any security concerns.

Test Cases

None yet.

Implementation

None yet.