Kernel: Python 3 (Ubuntu Linux)

Protocol for a distributed synthetic market

This is a protocol for matching state contingent contracts that give a payoff linear between an upper and lower bound and at a particular expiry.

For example the contract might pay 1 for each 10mm of rainfall above 30mm. If the amount of rainfall is above 30mm the payoff is $1 and if the outcome is below 30mm the outcome is zero.

These contracts can be combined to construct standard forward and option contracts or event markets (payoffs depending on a discrete set of outcomes).

The protocol uses a chain of signatures to organize buy and sell orders for these contracts. Orders are accepted if they have a valid signature and the trader's positions satisfiy a collateral check across all possible worst outcomes. To maintain an appropriate record of the order book, trades can only be added, and the validity of any trade can be checked by anyone using public keys provided by each participant.

Markets are settled by the market owner adding a new equal upper and lower bound for a market. For example, the lower bound for each market is the highest lower bound for itself of any sub-market or any previous bound on the same market. Market bounds telescope, making a market the underlying asset of its sub-markets.

Data structures

A market

A market is defined by:

'marketRootId': (integer) market id
'marketBranchId': (integer) sub-markets >1 (sub-markets bounded by super-markets)
'marketMin' - (float) minimum possible outcome
'marketMax' - (float) maximum possible outcome
'traderId' - (integer) market owner trader ID
'previousSig'- (bytes) previous market signature
'signatureMsg' - (bytes) message for signature
'signature' - (bytes) signed message

E.g.

Market with (root = 3, branch = 1); market bounded between (0, 1); owned by trader 1 and signed with signature 'sig1'.


testMarket = struct('marketRootId', 3, 'marketBranchId', 1,...
                                'marketMin', 0, 'marketMax', 1,...
                                'traderId', 1, 'previousSig', 'prevSig', 'signatureMsg','sigmsg1',...
                                'signature', 'sig1')

Sub markets have marketMin/marketMax bounded by markets with the same root but lower branch id.
Any amount of valid markets with the same root/branch can be added and the market will take the highest minimum and the lowest maximum.

Market signature chains

A market is signed from the previous valid market which is the last entry in the market table.

An order

An order in a market is defined by:

'tradeRootId': (integer) trade root id
'tradeBranchId': (integer) subtrades (1 for primary, 2 for offset, 3 for match)
'price': (float) price of trade
'quantity': (float) quanitity of trade (positive quantity for bids, negative for offers)
'marketRootId' : (integer) market id
'marketBranchId': (integer) sub-markets > 1 (sub-markets bounded by super-markets)
'traderId': (integer) trade owner trader ID
'previousSig': (bytes) previous trade signature
'signatureMsg' - (bytes) message for signature
'signature' - (bytes) signed message

E.g.

Unmatched primary trade (price = 0.5, quantity = 10) on market (root = 1, branch = 1)


testTrade = struct('traderId', 1, 'tradeRootId', 1, 'tradeBranchId', 1,...
                'price', 0.5,...
                'quantity', 10, 'marketRootId', 3,...
                'marketBranchId', 1,'signatureMsg',...
                'sigMsg', 'signature', 'sig');

Trades can be added to the order book but not removed or changed. A separate cache order book is maintained for offset and matche trades. The cache order book is ignored for collateral calculations.

Geometry of an order

Since orders can only be added to the order book and not subtracted, creating a matched order requires an offset of the unmatched order and a new matched order of equal size.

Consider an order '(p=0.5, q=1)'. For the trade to successfully be matched it requires at minimum:

Primary (p=0.5, q=1, tradeBranchId = 1)
Offset (p=0.5, q=-1, tradeBranchId = 2)
Match (p=0.5, q=1, tradeBranchId = 3)

Geometrically, this set of trades can be represented in (p,q) space with with offset (blue) and match (green):

The offset and match trades are initally held in a separate cache order book and are promoted to the order book when the trade is matched. The cache order book is a place for signed but unused trades and has no implact on collateral calculations.

With a small loss of generality, the mechanics of orders here are all 1 or -1 quantity and there are no partial fills.

Geometry of signature chain

Each trade is chained to a previous trade according to a rule. The order book will require a valid signature (valid signature for message and valid previous trade) and a collateral check to ensure the trader has sufficient collateral. Primary orders are chained to a previous valid order, offset are chained to the primary trade.

The figure below is an order to buy at 0.5 with associated offset and match trades.

If the order is matched by a sell contract at 0.5 the the offset and match contracts are removed from the cache and added to the order book.

Example sequence of orders: Single order perfect match

The simplest case is a perfect match of primary trades. Trader 1 enters the market and posts a bid for 1 contracts at 0.5 into the order book, and a corresponding offset and match order into the cache. Offsets and matches share the same root id.

Trader 1:

1.1 Primary: traderId=1, tradeRootId = 1, tradeBranchId = 1, p=0.5, q=1 (primary)
1.2 Offset: traderId=1, tradeRootId = 1, tradeBranchId = 2, p=0.5, q=-1 (cache)
1.3 Match: traderId=1, tradeRootId = 1, tradeBranchId = 3, p=0.1, q=1 (cache)

Now trader 2 posts a matching bid for -1 contracts at 0.5, with corresponding offset and match in cache:

Trader 2:

2.1 Primary: traderId=2, tradeRootId = 2, tradeBranchId = 1, p=0.5, q=-1 (primary)
2.2 Offset: traderId=2, tradeRootId = 2, tradeBranchId = 2, p=0.5, q=1 (cache)
2.3 Match: traderId=2, tradeRootId = 2, tradeBranchId = 3, p=0.5, q=-1 (cache)

Matching proceeds by adding the the offset and match trades to the order book.

Example sequence of orders: Better price match

Now consider a case where trader 1 has a bid at 0.5 and trader 2 offers at 0.4. The trade still matches at 0.5 since trader 1 was there first. Trader 2's offset for the p=0.4 trade is promoted to the order book.

Example sequence of orders: Chaining to a previous valid order

Continuing from the previous example after the first trade is matched, now suppose trader 3 enters the market with an offer to sell at 0.7 or 0.8. The order is chained to the highest number trade existing in the order book which is (2.3 from the p=0.5 trade). If another trade arrives into the order book it would be chained to 3.1 since it is the furtherst branch on the highest tree of the order book.

Methods

Add a new user to the table by storing their public key. This verifies signatures on markets and trades.

Method: createUser(user)

Inputs


user = struct('verifyKey', 'key');

verifyKey is a unique public key for a user.

Checks

verifyKey doesn't exist in the user table

Process

Add user to table (new traderId = previous traderId +1)

Method: createmarket(market)

Create a new market or alter the bounds on an existing market

Inputs


market = struct('marketRootId', 3, 'marketBranchId', 1,...
                                'marketMin', 0, 'marketMax', 1,...
                                'traderId', 1, 'signatureMsg','sigmsg1',...
                                'signature', 'sig1')

marketRootId,marketBranchId - root and branch number
marketMin,marketMax - maximum and minimum possible values
traderId - id of trader who is entitled to change the market
previousSig,signatureMsg,signature - chain of signatures

Checks

New market is chained to the correct previous market

If marketBranchId = 1, market should be chained to the previous root market
If marketBranchId >1, market should be chained to the previous market on the same root market

Signature is correct (signature is the correct hash of signatureMsg using the verifyKey matching to the traderId)
marketMin < marketMax

Process

Add new market to the market table
Construct all possible final combinations of root markets in outcomeCombinations

Method: createTrade(pTrades, oTrades, mTrades)

Add trade to order book and cache after checking trade is valid.

Inputs


pTrades = struct('traderId', 1, 'tradeRootId', 1, 'tradeBranchId', 1,...
                'price', 0.5,...
                'quantity', 1, 'marketRootId', 3,...
                'marketBranchId', 1, 'previousSig', 'prevsig' signatureMsg',...
                'sigMsg', 'signature', 'sig');

oTrades = struct('traderId', 1, 'tradeRootId', 1, 'tradeBranchId', 2,...
                'price', 0.5,...
                'quantity', -1, 'marketRootId', 3,...
                'marketBranchId', 1, 'previousSig', 'prevsig' signatureMsg',...
                'sigMsg', 'signature', 'sig');

mTrades = struct('traderId', 1, 'tradeRootId', 1, 'tradeBranchId', 3,...
                'price', 0.5,...
                'quantity', 1, 'marketRootId', 3,...
                'marketBranchId', 1, 'previousSig', 'prevsig' signatureMsg',...
                'sigMsg', 'signature', 'sig');

traderId: trader Id
tradeRootId, tradeBranchId: trade root and branch (1 = primary, 2 = offset, 3 = match)
price, quantity
marketRootId, marketBranchId: market root and branch (marketBranchId>1 are submarkets)
previousSig, signatureMsg, signature: signature chain from previous trade

Additional trades better prices can be included. The other trades will be store in cache and used if necessary for matching.


pTrades = struct('traderId', {1, 1}, 'tradeRootId', {1, 1}, 'tradeBranchId', {1, 1},...
                'price', {0.5, 0.4}...
                'quantity', {1, 1} 'marketRootId', {3, 3},...
                'marketBranchId', {1, 1}, 'previousSig', {'prevsig', 'prevsig}' signatureMsg',...
                {'sigMsg', 'sigMsg'} 'signature', {'sig', 'sig'});

Checks

Trade package checks

primary/offset/match trades have the same traderId, tradeRootId
p/o/m trades have the tradeBranchId 1, 2, and 3 respectively
p/o/m trades havethe same price and absolute quantity
p/o/m trades have the same marketRootId, marketBranchId

Valid market checks

Market root and branch combination exists in in the market table

Signature and chain checks

Primary trades

Trade is validly signed (check with public key)
Trade is validly chained to previously valid trade (furtherst branch on the largest root (tree))

Offset trades

Trade is validly signed
Chain is validly chained to its primary trade

Match trades

Trade is validly signed
Trade is validly chined to its offset trade

Collateral check

Run checkCollateral() process to check if the trader will have sufficient collateral for this new trade in the worst possible outcome

Process

(if all checks pass)

Add first primary trade to order book
Add all other trades to cache book
Run matchTrades process to connect bids and offers and to offset any trades that are blocking a potential match.

[createTrade diagram]

Method: checkCollateral(trade)

Check there is sufficient collateral for trade in the worst possible outcome.

Inputs


trade = struct('traderId', 1, 'tradeRootId', 1, 'tradeBranchId', 1,...
                'price', 0.5,...
                'quantity', 1, 'marketRootId', 3,...
                'marketBranchId', 1, 'previousSig', 'prevsig' signatureMsg',...
                'sigMsg', 'signature', 'sig');

Checks

Process

Outcome combinations

Construct all extreme cominations of root market outcomes where trader is active (**constructOutputCombinations(markets))

Payoffs

For each outcome combination:

Construct payoffs for existing matched trades (**constructPayoffs(orderBook, marketTable))
Construct payoffs for existing open trades
Construct payoffs for new trade

Net collateral = sum(matchedTradePayoffs) + min(openTradePayoffs) + min(newTradePayoff)

Collateral check passes if all elements of net collateral > 0

Matrix representation of collateral calculation

The possible set of extreme root market outcomes is a $C \times N$ matrix $\mathbf{M}$ where $C$ is the number of possible market states and $N$ is the number of markets.

At some point there are a set of $T$ trades with prices and quantities $\vec{p} = (p_1 , \ldots, p_T)$ and $\vec{q} = (q_1 , \ldots, q_T)$ .

The net collateral available to $D$ traders in any one of $C$ market states is:

$\underset{C \times D} {\mathbf{NC} } = (\mathbf{M}^* - \mathbf{P}^*)\mathbf{Q}^*$

Where

$\underset{C \times T}{ \mathbf{M}^*} = \underset{C \times N }{\mathbf{M} } \underset{N \times T}{\mathbf{I}^M}$

$\underset{T \times D} {\mathbf{Q}^* } = \underset{T \times D } {[\vec{q}' \ldots \vec{q}'}] . \underset{T \times D } {\mathbf{I}^Q }$

ParseError: KaTeX parse error: Undefined control sequence: \vp at position 62: …t{C \times T}{ \̲v̲p̲ ̲}

Two indicator matricies have $I^{M}_{it} = 1$ if trade $t$ is in market $i$ and $I^{Q}_{td} = 1$ if trade $t$ belongs to trader $d$ .

\def \vp{ \begin{bmatrix} \vec{p} \\ \vec{p} \\ \vdots \\ \vec{p} \end{bmatrix}}

Example

Number of traders $D$ = 2 Number of markets $N$ = 2 (Outcomes between 0 and 1)

Trades:

Trader 1: (1, 0.5) in market 1
Trader 1: (1, 0.4) in market 2
Trader 1: (1, 0.4) in market 2
Trader 2: (-1, 0.9) in market 2

(all trades are with trader 3 who will remain invisible for the moment)

Number of states $C$ = 4

The state of the market is represented by the four possible extreme outcomes:

\mathbf{M}= \begin{bmatrix} 0 & 0 \\ 0 & 1 \\ 1 &0 \\ 1 & 1 \end{bmatrix}

The prices and quantities are arranged in a vector:

\vec{p} = [0.5, 0.4, 0.4, 0.9]

\vec{q} = [1, 1, 1,-1]

The market indicator matrix tracks which market each trade belongs to

\mathbf{I^M}= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix}

The trade indicator matrix tracks which trader each trade belongs to

\mathbf{I^Q}= \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ \end{bmatrix}

Now calculate

\mathbf{M}^* = \mathbf{M} \mathbf{I}^M = \begin{bmatrix} 0& 0& 0& 0\\ 0& 1& 1& 1\\ 1& 0& 0& 0\\ 1& 1& 1& 1 \end{bmatrix}

\mathbf{Q}^* = \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & -1 \\ \end{bmatrix}

\mathbf{I}^Q = \begin{bmatrix} 1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & 1\\ \end{bmatrix}

\mathbf{P}^* = \begin{bmatrix} 0.5 & 0.4 & 0.9 \\ 0.5 & 0.4 & 0.9 \\ 0.5 & 0.4 & 0.9 \\ 0.5 & 0.4 & 0.9 \\ 0.5 & 0.4 & 0.9 \end{bmatrix}

The net collateral is

\mathbf{NC} = (\mathbf{M}^* - \mathbf{P}^*)\mathbf{Q}^* = \begin{bmatrix} -1.3 & 0.9 \\ 0.7 & -0.1 \\ -0.3 & 0.9 \\ 1.7 & -0.1 \end{bmatrix}

The columns of the matrix are the collateral outcomes for each of the two traders in the four possible states. For example the first entry in $\mathbf{NC}$ is trader 1's collateral if both markets settle at 0 (-0.5 + - 0.4 + -0.4 = -1.3).

M = [0 0; 0 1; 1 0; 1 1]
p = [0.5 ,0.4,0.4, 0.9]
q = [1, 1, 1, -1]
IM = [1 0 0 0;0 1 1 1] % Convert from marketId [1 2 2]
IQ = [1 0;1 0;1 0;0 1] % Convert from traderId [1 1 2]
Mstar = M*IM
Qstar = [q',q'].*IQ
Pstar = [p;p;p;p]
NC = (Mstar - Pstar)*Qstar

In [0]:

[diagram for check collateral]

Method: matchTrades()

Inputs

None

Checks

None

Proccess

Get all primary trades with no matching offset or match trade
Of these find the maximum bid and minimum ask
If max bid > min ask, check collateral for both trades
If both collateral checks pass, promote matching offset and match trades to the order book from cache
If either collateral checks fail, promote offset for oldest unmatched trade from cache and start match process over

In [0]:

In [0]:

[Diagram for match trades]