Skip to content

Latest commit

 

History

History
266 lines (227 loc) · 19.1 KB

cap-0003.md

File metadata and controls

266 lines (227 loc) · 19.1 KB
Raw

Preamble

CAP: 0003
Title: Asset-backed offers
Author: Jonathan Jove, Nicolas Barry
Status: Final
Created: 2018-05-15
Discussion: https://github.com/stellar/stellar-protocol/issues/36
Protocol version: 10

Simple Summary

Asset-backed offers is a proposal to resolve the issue that offers in the ledger might not be executable.

Abstract

Asset-backed offers is a proposal to resolve the issue that a single account might have liabilities, in the form of offers on the ledger, that exceeds the assets of the account. When this occurs offers in the ledger might not be executable, in the sense that there exists no crossing offer such that the entire amount of the offer is exchanged. Offers in the ledger that are not executable provide a false sense of liquidity.

Motivation

We will say that an offer is "immediately executable in full" (IEIF in short) if, were it crossed by a hypothetical offer with no limits on amount bought or sold, the entire amount of selling asset would be exchanged. It is desirable that all offers are IEIF since this enables users to easily evaluate the amount of available liquidity.

The protocol requires that, upon creation, every offer satisfies the following two conditions:

  • The amount offered to sell does not exceed the available balance of the selling asset
  • The amount offered to buy (computed implicitly) does not exceed the available limit of the buying asset

We will now demonstrate that these conditions are not sufficient to ensure that an offer is IEIF. Suppose that an account creates an offer which is IEIF with the selling amount equal to the available balance of the selling asset. The account then creates a second offer with a worse price but otherwise identical to the first. Although each offer individually satisfies the above requirements, the second offer is not IEIF. For suppose that the second offer was crossed by a hypothetical offer with no limits. This crossing offer would initially cross the first offer, which leaves no available balance for the selling asset. When the second offer is then crossed, no assets can be exchanged.

Analogous to the above example, it is possible to create multiple offers that individually meet the requirements but exceed the available limit when considered in aggregate. Suppose that an offer creates an offer which is IEIF with the buying amount equal to the available limit of the buying asset. The account then creates a second offer with a worse price but otherwise identical to the first. Although each offer individually satisfies the above requirements, the second offer is not IEIF. For suppose that the second offer was crossed by a hypothetical offer with no limits. This crossing offer would initially cross the first offer, which leaves no available limit for the buying asset. When the second offer is then crossed, no assets can be exchanged.

Specification

This proposal will require XDR changes for AccountEntry and TrustLineEntry, as well as schema updates for the accounts and trustlines tables. The updated XDR is:

struct Liabilities
{
    int64 buying;
    int64 selling;
};

struct AccountEntry
{
    AccountID accountID;      // master public key for this account
    int64 balance;            // in stroops
    SequenceNumber seqNum;    // last sequence number used for this account
    uint32 numSubEntries;     // number of sub-entries this account has
                              // drives the reserve
    AccountID* inflationDest; // Account to vote for during inflation
    uint32 flags;             // see AccountFlags

    string32 homeDomain; // can be used for reverse federation and memo lookup

    // fields used for signatures
    // thresholds stores unsigned bytes: [weight of master|low|medium|high]
    Thresholds thresholds;

    Signer signers<20>; // possible signers for this account

    union switch (int v)
    {
    case 0:
        void;
    case 1:
        struct {
            Liabilities liabilities;

            // reserved for future use
            union switch (int v)
            {
            case 0:
                void;
            } ext;
        } v1;
    }
    ext;
};

struct TrustLineEntry
{
    AccountID accountID; // account this trustline belongs to
    Asset asset;         // type of asset (with issuer)
    int64 balance;       // how much of this asset the user has.
                         // Asset defines the unit for this;

    int64 limit;  // balance cannot be above this
    uint32 flags; // see TrustLineFlags

    union switch (int v)
    {
    case 0:
        void;
    case 1:
        struct {
            Liabilities liabilities;

            // reserved for future use
            union switch (int v)
            {
            case 0:
                void;
            } ext;
        } v1;
    }
    ext;
};

The SQL required to update the schema is:

ALTER TABLE accounts ADD buyingliabilities BIGINT
    CHECK (buyingliabilities >= 0);
ALTER TABLE accounts ADD sellingliabilities BIGINT
    CHECK (sellingliabilities >= 0);
ALTER TABLE trustlines ADD buyingliabilities BIGINT
    CHECK (buyingliabilities >= 0);
ALTER TABLE trustlines ADD sellingliabilities BIGINT
    CHECK (sellingliabilities >= 0);

The operation result code ACCOUNT_MERGE_DEST_FULL also must be added:

enum AccountMergeResultCode
{
    // codes considered as "success" for the operation
    ACCOUNT_MERGE_SUCCESS = 0,
    // codes considered as "failure" for the operation
    ACCOUNT_MERGE_MALFORMED = -1,       // can't merge onto itself
    ACCOUNT_MERGE_NO_ACCOUNT = -2,      // destination does not exist
    ACCOUNT_MERGE_IMMUTABLE_SET = -3,   // source account has AUTH_IMMUTABLE set
    ACCOUNT_MERGE_HAS_SUB_ENTRIES = -4, // account has trust lines/offers
    ACCOUNT_MERGE_SEQNUM_TOO_FAR = -5,  // sequence number is over max allowed
    ACCOUNT_MERGE_DEST_FULL = -6        // can't add source balance to
                                        // destination balance
};

Rationale

The purpose of the asset-backed offers proposal is to maintain the invariant that every offer is IEIF. We begin with a discussion of what can cause offers to no longer be IEIF:

  • Fees
    • Account A is used to pay fees: offers owned by A and selling the native asset may no longer be IEIF
  • AllowTrustOp
    • Revoke authorization from account A to hold non-native asset X: all offers owned by A and either buying or selling X are no longer IEIF
  • ChangeTrustOp
    • Create trust line for account A: offers owned by A and selling the native asset may no longer be IEIF
    • Reduce the limit on a trust line for account A to hold a non-native asset X: offers owned by A and buying X may no longer be IEIF
  • CreateAccountOp
    • Create account using native assets from account A: offers owned by A and selling the native asset may no longer be IEIF
  • InflationOp
    • Account W is an inflation winner: offers owned by W and buying the native asset may no longer be IEIF
  • ManageDataOp
    • Create account data for account A: offers owned by A and selling the native asset may no longer be IEIF
  • ManageOfferOp (and CreatePassiveOfferOp)
    • Account A crosses offer owned by account M selling asset Y for asset X:
      • offers owned by A and selling X may no longer be IEIF
      • offers owned by A and buying Y may no longer be IEIF
      • offers owned by M and selling Y may no longer be IEIF
      • offers owned by M and buying X may no longer be IEIF
    • Create offer for account A selling asset X for asset Y:
      • offers owned by A and selling X may no longer be IEIF
      • offers owned by A and buying Y may no longer be IEIF
      • offers owned by A and selling the native asset may no longer be IEIF
  • MergeOp
    • Account S is merged into account D: offers owned by D and buying the native asset may no longer be IEIF
  • PaymentOp
    • Account S pays asset X to account D:
      • offers owned by S and selling X may no longer be IEIF
      • offers owned by D and buying X may no longer be IEIF
  • PathPaymentOp
    • Account S crosses offer owned by account M selling asset Y for asset X:
      • offers owned by S and selling X may no longer be IEIF
      • offers owned by S and buying Y may no longer be IEIF
      • offers owned by M and selling Y may no longer be IEIF
      • offers owned by M and buying X may no longer be IEIF
    • Account S pays asset X to account D arriving as asset Y:
      • offers owned by S and selling X may no longer be IEIF
      • offers owned by D and buying Y may no longer be IEIF
  • SetOptionsOp
    • Add signer to account A: offers owned by A and selling the native asset may no longer be IEIF

From this analysis, it is clear that any proposal which attempts to modify or delete offers that are no longer IEIF would require maintaining the offer book after fee collection and after each operation. This would be both complicated and inefficient. Instead, we pursue a proposal which modifies the operations such that they guarantee offers remain IEIF. To achieve this, we first define new quantities which are derived data on the ledger:

  • account.sellingLiabilities
    • For account A: the amount of native asset offered to be sold, aggregated over all offers owned by A
  • account.buyingLiabilities
    • For account A: the amount of native asset offered to be bought, aggregated over all offers owned by A
  • trustline.sellingLiabilities
    • For account A and non-native asset X: the amount of X offered to be sold, aggregated over all offers owned by A
  • trustline.buyingLiabilities
    • For account A and non-native asset X: the amount of X offered to be bought, aggregated over all offers owned by A

These quantities will be updated whenever an offer is created, modified, or deleted. When an offer is created, the liabilities for the offer will be calculated and added to buyingLiabilities and sellingLiabilities in the relevant account and/or trust lines. When an offer is deleted, the liabilities for the offer will be calculated and subtracted from buyingLiabilities and sellingLiabilities in the relevant account and/or trust lines. When an offer is modified, it can be viewed as a delete followed by a create so the buyingLiabilities and sellingLiabilities can be updated using the logic from those cases. As we already load accounts and trust lines when interacting with offers, the cost of maintaining these quantities should be minimal.

We will now use these quantities to modify the operations such that they guarantee offers remain IEIF. In what follows, available limit is INT64_MAX for the native asset and limit - buyingLiabilities for non-native assets. Similarly, available balance is balance - reserve - sellingLiabilities for the native asset and balance - sellingLiabilities for non-native assets. In order for issuers to be able to buy or sell any quantity (even exceeding INT64_MAX) of an asset they issued, available limit and available balance will always be INT64_MAX in this case. The asset-backed offers proposal modifies the operations such that all offers remain IEIF after an operation:

  • Fees
    • Account A is used to pay fees: transaction is not valid with result txINSUFFICIENT_BALANCE if new available balance of native asset is negative
  • AllowTrustOp
    • Revoke authorization from account A to hold non-native asset X: all offers owned by A and either buying or selling X are deleted
  • ChangeTrustOp
    • Create trust line for account A: fails with result CHANGE_TRUST_LOW_RESERVE if new available balance of native asset is negative
    • Reduce the limit on a trust line for account A to hold a non-native asset X: fails with result CHANGE_TRUST_INVALID_LIMIT if new available limit is negative
  • CreateAccountOp
    • Create account using native assets from account A: fails with CREATE_ACCOUNT_UNDERFUNDED if new available balance of native asset is negative
  • InflationOp
    • Account W is an inflation winner: inflation winners receive the minimum of their winning and their available limit of native asset, with the residual returned to the inflation pool
  • ManageDataOp
    • Create account data for account A: fails with result MANAGE_DATA_LOW_RESERVE if new available balance of native asset is negative
  • ManageOfferOp (and CreatePassiveOfferOp)
    • Account A crosses offer owned by account M selling asset Y for asset X:
      • A does not buy more Y than available limit
      • A does not sell more X than available balance
      • M does not buy more X than available limit
      • M does not sell more Y than available balance
    • Create offer for account A selling asset X for asset Y:
      • A does not offer to sell more X than available balance
      • A does not offer to buy more Y than available limit
      • fails with result MANAGE_OFFER_LOW_RESERVE if new available balance of native asset is negative
  • MergeOp
    • Account S is merged into account D: fails with result ACCOUNT_MERGE_DEST_FULL if new available limit of native asset is negative
  • PaymentOp
    • Account S pays asset X to account D:
      • fails with result PAYMENT_UNDERFUNDED if new available balance of X in S is negative
      • fails with result PAYMENT_LINE_FULL if new available limit of X in D is negative
  • PathPaymentOp
    • Account S pays asset X to account D arriving as asset Y:
      • fails with result PATH_PAYMENT_UNDERFUNDED if new available balance of X in S is negative
      • fails with result PATH_PAYMENT_LINE_FULL if new available limit of Y in D is negative
    • Account S crosses offer owned by account M selling asset Y for asset X:
      • S does not buy more Y than available limit
      • S does not sell more X than available balance
      • M does not buy more X than available limit
      • M does not sell more Y than available balance
  • SetOptionsOp
    • Add signer to account A: fails with result SET_OPTIONS_LOW_RESERVE if new available balance of native asset is negative

The behavior of ManageOfferOp (and CreatePassiveOfferOp) will undergo a considerable change in order to make the behavior predictable and performant with regard to liabilities. Before crossing any offers, both operations will now enforce the following requirements:

  • If modifying the offer offerID, then the liabilities associated with offer offerID are removed
  • If a new offer is being created, the number of subentries is updated
  • If the buying liabilities associated with the new offer exceed the available limit then the operation fails with MANAGE_OFFER_LINE_FULL
  • If the selling liabilities associated with the new offer exceed the available balance then the operation fails with MANAGE_OFFER_UNDERFUNDED

These updates to ManageOfferOp (and CreatePassiveOfferOp) imply all of the modifications discussed in the previous list for these operations.

Backwards Compatibility

We will denote the protocol version which enables this proposal as PROPOSAL_VERSION. The database schema can be updated to include buyingLiabilities and sellingLiabilities, where these values are set to NULL until the protocol version is at least PROPOSAL_VERSION.

Upgrading the Protocol Version

When the protocol version is upgraded to PROPOSAL_VERSION, the values of buyingLiabilities and sellingLiabilities will need to be calculated for all accounts that own offers. For other accounts these values can either be left as NULL and updated lazily, or they can be updated globally to 0. It would be better to update the values lazily as this would require a much smaller bucket than updating globally to 0.

It is possible, after the protocol version is upgraded to PROPOSAL_VERSION, that there are existing offers which are not IEIF. We propose to resolve this issue by deleting offers owned by accounts with excess liabilities. Specifically, for any account A and assets X and Y, this approach would delete any offer owned by A and selling X in exchange for Y if A has excess selling liabilities of X or excess buying liabilities of Y. As of ledger 18178688, there are a maximum of 6053 offers (out of 12734 total offers) that would be deleted, owned by a maximum of 983 accounts (out of 474454 total accounts). One disadvantage to this approach is that it would likely cause a considerable decrease in available liquidity for some time while new offers are created, although this impact would be smaller than in the alternative approach discussed below. A further disadvantage to this approach is that, for some accounts, some offers may be deleted while others remain which could be undesirable in some cases. Both of these disadvantages could potentially be mitigated by giving an advance notice of a few weeks to the community and developers so that they have time to update their offers such that they do not have excess liabilities. As in the alternative approach, it could occur that it is impossible to recreate some offers. But at least offers selling an asset issued by that account are less likely to be deleted, since there is no limit on liabilities for the issuer of an asset. Regarding the specific offers mentioned in the discussion of the alternative approach, none of the 3 that are selling an asset issued by that account would be deleted.

Alternative Approach: Delete all existing offers

As the description suggests, this approach would delete all existing offers when the protocol is upgraded to PROPOSAL_VERSION. As of ledger 18178688, there are 12734 offers owned by 2653 accounts (out of 474454 total accounts). One disadvantage to this approach is that it would likely cause a considerable decrease in available liquidity for some time while new offers are created. Some offers which have been created belong to accounts that would not be able to recreate them. There are 5 offers owned by 4 accounts with no signers and a master key weight of 0, with 2 of these offers selling an asset issued by the account. There is 1 other offer owned by an account whose total weight of signers and master key does not exceed the medium threshold, and it is also selling an asset issued by the account. It is worth repeating that this is only a simple lower bound on the number of offers that could not be recreated.

Base Reserve

The previous section details only a single point of backward incompatibility, but the process of increasing the base reserve presents a similar issue of backward incompatibility which would be repeatedly possible in the future. The reason for this is that increasing the base reserve could cause offers selling the native asset to no longer be IEIF. The potential solutions presented in the previous section would also apply here, but the same disadvantages would still apply as well.

Test Cases

  • buyingLiabilities and sellingLiabilities are updated when offers are modified by PathPaymentOp, ManageOfferOp, CreatePassiveOfferOp, and AllowTrustOp
  • Each operation should have the new behavior described above

Implementation

stellar/stellar-core#1718

Corresponding commit is git: 4dab9625d42b252d3f11500151ffcc66a1cd5ad2