Implementation Notes for Automated Market Makers MVP

[youkaicountry]

Let's begin crystallizing the development direction for Automated Market Makers. Keep in mind we are developing in a bottom-up manner, so we want to essentially extend the SMT MVP to include Market Makers with as bare a feature set as possible.

[theoreticalbts]

The whitepaper says that market maker's state is a tuple (s, t, T, r). This suggests the following struct:

struct market_maker_state
{
   asset steem_balance;    // s in the paper
   asset token_balance;    // t in the paper
   asset token_supply;    // T in the paper
   uint32_t reserve_ratio = 0;    // r in the paper
};

The reserve_ratio is implicitly a fraction with a large denominator, the denominator should be either one billion (the highest power of 10 to fit in 32 bits), or 2^32.

Then there are external flow events:

• The token_supply field will need to be adjusted whenever token creation occurs from any source.
• The steem_balance and token_balance fields will be adjusted when the launch occurs, or when a particular user makes a voluntary donation to the MM.

The equilibrium price p_eq can be computed from the fields using the equation in the whitepaper in the section "Computing the Equilibrium Price."

When any external flow event occurs, there are two possibilities for updating reserve_ratio:

• pay_now : The reserve_ratio is not updated (i.e. it retains the same value).
• pay_later : The reserve_ratio is updated such that p_eq remains the same as it was before the change (i.e. p_eq retains the same value within rounding error). The value of r which will result in a given value of p_eq can be found by solving for r in the equation for p_eq.

We need to determine whether each token flow event is pay_now or pay_later on a case-by-case basis. Effectively pay_now means a (large enough) flow will cause an immediate trade (if the market is liquid enough), while pay_later means no trading will occur right now.

[theoreticalbts]

So how to actually implement trading? I'm thinking we start by defining stops which are simply prices roughly geometrically spaced 5% apart. Then each block:

• Cancel all the MM's unfilled orders.
• Compute the relaxing trade for the next two stops in each direction from p_eq and place it as a normal limit order (if it would be dust, don't place it).

[theoreticalbts]

So there are a few issues left:

Rounding

All the rounding that occurs in the above implementation must be carefully checked so that any rounding errors are in the market maker's favor.

Numerical stability

The MM should suspend all operations when STEEM balance or token balance is less than some minimum threshold, perhaps 10,000 satoshis. Since this balance "should" be unspendable (i.e. the market maker shuts down whenever it's on the verge of spending it), we can do a trick: Simply pretend that the market maker's STEEM and SMT balances are 10,000 satoshis larger than they actually are in the computations to set / compute the equilibrium price. This change will also require us to explicitly forbid the market maker from producing any market orders which would reduce its balance below zero (since it has no way of "knowing" the "phantom" balance isn't spendable, the calculations might end up saying the MM should spend it).

Likewise, the reserve ratio should have a lower bound of 5% and an upper bound of 50% (we may be able to relax these numbers if we do some experiments, or ideally proofs, that it will remain numerically stable).

Decaying reserve ratio

This feature is not necessary for MVP, from the market maker's point of view, it's just an external process that alters reserve_ratio over time.

The whitepaper mentions a setup parameter called DRR. The idea is simple: a token creator can program the reserve ratio to slowly creep at a pre-programmed rate toward a fixed pre-set value over time. We probably want to support creep rates slow enough that the per-block change in (the 32-bit integer value) reserve_ratio is not an integer, which slightly complicates the implementation. DRR is not a feature for MVP.

Gradual seeding

This feature is not necessary for MVP, from the market maker's point of view, it's just another external flow event incrementing its balances.

The idea of this feature is that some / all of the tokens / STEEM created in an ICO will not be directly sent to the market maker, instead they will be placed in a holding object, and a tiny bit of the holding object's balance will trickle into the MM every block until the full balance has moved from the holding object to the MM.

When gradual seeding is combined with DRR, it can be an effective trustless, decentralized way to return excess STEEM to contributors. The gradual seeding trickle raises the DRR (no trading occurs), then the

[theoreticalbts]

Defining ticks

Let's be a little more careful about how we define ticks. Let's get some approximately geometrically evenly spaced numbers between 100 and 1000:

stop_initial_digits = [100, 105, 110, 115, 121, 127, 133, 140, 147, 154, 161, 169, 178, 187, 196, 205, 215, 226, 237, 249, 261, 274, 287, 301, 316, 332, 348, 365, 383, 402, 422, 442, 464, 487, 511, 536, 562, 590, 619, 649, 681, 715, 750, 787, 825, 866, 909, 953]

This sequence may be generated in Python with:

def compute_stop_initial_digits():

    r = 10**(1.0 / 48)
    u = [int(r**x * 100 + 0.5) for x in range(48)]

    deltas = [u[i] - u[i-1] for i in range(1, len(u))]
    deltas.sort()

    u = [100]
    for d in deltas:
        u.append(u[-1]+d)

    return u

Then we define stop to be some element of stop_initial_digits times some power of 10.

Implementing ticks

Given a nonzero price, we need a function to compute the next-highest and next-lowest stop. This may be achieved by repeatedly multiplying or dividing the price by 10 until it is between 100 and 1000, searching the above array for the next-lowest and next-highest element (with appropriate action if it ends up).

A less complicated and error-prone implementation approach that uses a little more memory (but probably performs about equally fast) is to simply pre-compute an array of stops until the numerator / denominator exceeds the integer precision range, then do a binary search on this pre-computed array.

[theoreticalbts]

As a starting point, I've implemented a simple program in this branch to generate ticks. Each tick is price(a, b) for each element [a, b] in the JSON output of this program.

This script is a starting point, we may end up importing the JSON, use it to generate C++ code or array definitions, or we may implement equivalent functionality in C++.

[youkaicountry]

Now that the notes are complete, I am closing.

[youkaicountry]

Regarding token_supply in market_maker_state, isn't this already stored in the database? Is there a reason it should be redundantly stored in the market struct?

[theoreticalbts]

The market maker works by re-computing p_eq (in case of pay_now events) or reserve_ratio (in case of pay_later events). The recomputation [1] of p_eq takes (s, t, T, r) as input, the recomputation of r takes s, t, T, p_eq as input [2].

It is convenient for describing the MM, and perhaps convenient for implementing and testing the MM, to store all of these methods in the same struct. It is certainly possible to have alternative interfaces to the functionality [3].

Where should the token supply go? That depends on where you want to draw the encapsulation boundaries, and how you want to route field updating events. Here are a few possible implementation strategies:

• (a) Have an instance of market_maker_state as a field of smt_token_object, and delete the current_supply field from smt_token_object
• (b) Have market_maker_state_object be its own database object, and delete the current_supply field from smt_token_object
• (c) Have market_maker_state_object be its own database object, and have logic for updating market_maker_state_object.token_supply whenever smt_token_object.current_supply changes.

I personally like option (c), but all of the above strategies are reasonable.

[1] The value of p_eq is always "implied" by the values of fields (s, t, T, r), so it may be the case that p_eq is a const method with no arguments rather than a field.

[2] Since p_eq itself can be computed from the old values of (s, t, T, r), we could equivalently say that re-computing r takes (s, t, T, r) as input.

[3] For example, instead of the function to (re-)compute p_eq being a const member function of a struct with four fields with no arguments, we could instead make p_eq a free-floating global function which takes four arguments. Or we could make p_eq a const member function of a struct with three fields, which takes a single argument.