fusotao-greenbook.tex

% Created 2021-10-18 Mon 22:42
% Intended LaTeX compiler: xelatex
\documentclass[a4paper,12pt]{article}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage[margin=1.25in]{geometry}
\usepackage{fourier}
\usepackage{amsmath}
\usepackage[scaled]{helvet}
\linespread{1.10}
\setlength{\parindent}{0pt} %
\author{Fusotao Dev Team}
\date{2021}
\title{Fusotao Greenbook(Draft)\\\medskip
  \large v0.2.3\\\medskip
  \large https://www.fusotao.org}
\hypersetup{
 pdfauthor={Fusotao Dev Team},
 pdftitle={Fusotao Greenbook(Draft)},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 27.2 (Org mode 9.5)}, 
 pdflang={English}}
\begin{document}

\maketitle
\clearpage

\section{Introduction}
\label{sec:org5e9fe25}
Fusotao is a set of network protocols which are composed of either a rule of data consistency or some certain constraints of data modification including not only a transfer constraint but also a matching verification rule. The matching verification sub-protocol, a.k.a Proof of Matching, is the main difference from other blockchains.\\
\section{Matching System}
\label{sec:org29a156e}
Before start introducing Fusotao Protocol, let’s view the basic structure of an order matching system and consider why its outputs should be verified.\\
Matching system is a trading platform that allows users to price orders. The core component of a matching system is a data structure named orderbook which stores all orders that are according to the price and time, and a placed order must follow the sequence to trade if price meets, while the owner of an order would be ignored. Usually, in order to trade on a matching system, users may hand over their account ownership so that the matcher can mutate the accounts, in another word, trading on matchers should reply on human trust.\\
\newtheorem{theorem}{Rule}\\
Any data modifications should obey the rules below:\\
\begin{theorem}
Mutable data should not be shared, and shared data should be immutable.
\end{theorem}
\begin{theorem}
There should be only one associated mutator once data shared.
\end{theorem}
Compared to the transfer transaction, the matcher, as a mutator, must modify the orderbook's state for each order rather than just update the states of sender and receiver. Therefore, a matching system is a strict serial system which could be simply represented by the following procedure:\\
\begin{equation*}
    E_{i} + Orderbook_{i-1} \Rightarrow Orderbook_{i} + R_{i}
\end{equation*}
Consider an order placed. Let \(x\) be a price, \(y\) be an amount,  \((x_{i}, y_{i})\) be the \(i_{th}\) maker by the order of price and time.\\
\begin{equation*}
    mb_{i}=-y_{i}
\end{equation*}
\begin{equation*}
    tb=\sum\limits_{i} y_{i}
\end{equation*}
\begin{equation*}
    mq_{i}=-x_{i} \times y_{i}
\end{equation*}
\begin{equation*}
    tq=\sum\limits_{i} x_{i} \times y_{i}
\end{equation*}
where\\
\begin{itemize}
    \item $mb_{i}$ represents the base currency account of the $maker_{i}$
    \item $mq_{i}$ represents the quote currency account of the $maker_{i}$
    \item $tb$ represents the base currency account of the taker
    \item $tq$ represents the quote currency account of the taker
\end{itemize}
Blockchain is another typical serial system whose key rule is determining the order of all accepted incoming transactions. E.g. the Bitcoin network uses PoW algorithm and the Longest Chain Rule to ensure the global unique sequence of transactions. It seems natural to build a matching system on-chain just like a plain transfer function did. However, due to the limitation of block capacity and high latency, it is not straightforward to do it so.\\
Ideally, to implement a matching system on-chain, an order must occupy 73 bytes at least:\\
\begin{equation*}
ID + Owner + Price + Unfilled + Direction = 73 bytes
\end{equation*}
Imagine there are tens of thousands of orders in a single orderbook, it is not acceptable to store all orders in the blockchain state machine, but only keeping some essential data to validate the matching results is possible. In the next section, we will introduce how to validate the matching results without holding the entire orderbook.\\
\section{Global States}
\label{sec:org9b71832}
Sparse Merkle Tree is a full binary hash tree with fixed-depth which can be used for checking if there is a node belongs to a certain tree. A node of Sparse Merkle Tree can be represented by the following expressions:\\
\begin{equation*}
    \psi_{x} =
    \begin{cases}
      \lambda(\psi_{xL}, \psi_{xR}), \text{ } height \ne 0\\
      v, \text{ } height = 0\\
    \end{cases}
\end{equation*}
where\\
\begin{itemize}
    \item $\lambda$ is the hash function, e.g. sha256
    \item $x$ is the key of a node calculated by $\lambda(value) >> height$, e.g. $0x00...a82e$
\end{itemize}
The capacity of a Sparse Merkle Tree depends on the hash function of the tree, e.g. a Sparse Merkle Tree using Sha256 has \(2^{256}\) leaf nodes with height=256(root excluded).\\
Given a data \(v\), we can simply verify whether it belongs to a certain tree by calculating \(height-1\) times hash function:\\

\noindent\rule{\textwidth}{0.5pt}
\begin{verbatim}
let h = hash(v)
from 0 to 255:
    do h = hash(h, sibling_of_h)
return h == root
\end{verbatim}
\noindent\rule{\textwidth}{0.5pt}
It is quite simple for validators, but it is not good for provers. Storing all \(2^{257}\) (intermediate nodes included) nodes is unpractical for any storage system. Considering the distribution of a real Sparse Merkle Tree, most of the leaf nodes are empty, so are the intermediate nodes, that’s why we call it sparse. In an empty plain Sparse Merkle Tree, a node at height \(h\) has a certain value:\\
\begin{equation*}
    \psi_{h} = \lambda^{h}(\phi, \phi)
\end{equation*}
To avoid pre-calculate hash for each height, we can redefine the hash function like below:\\
\begin{equation*}
    \lambda(\phi, \phi) = \phi
\end{equation*}
\begin{equation*}
    \lambda(\alpha, \phi) = \lambda(\phi, \alpha)
\end{equation*}
For data updates, once a leaf node is inserted, the nodes along the path would be updated until root. Since we have the first optimization, we can infer that there will be a mount of redundant nodes along the path which can be omitted. E.g. when inserting a single node \(n\) with key=0xff..ff, value=\(v\) into an empty Sparse Merkle Tree, the parent node of \(n\) whose key is 0x7f..ff would be value=\(v\) either, so are the rest of the nodes along the path. Thus, we can define the structure of nodes to store the entire tree into an available storage:\\
\begin{equation*}
    \Psi_{k} = (k, l, r, \lambda(\Psi_{k>>l}, \Psi_{k>>r}))
\end{equation*}
Back to the matching procedure, since we've done an optimized Sparse Merkle Tree so can encode the orderbook into it and only store the root hash on chain and leave the entire tree to matchers. Once a matcher executes the \(i_{th}\) event off-chain and proves it by submitting some digests at \(i-1_{th}\), a validator can simply verify the results like above.\\
Fusotao defines 4 types of key as the leaf keys of Sparse Merkle Tree:\\
\begin{equation*}
    orderbook(symbol) = \lambda(1, symbol)
\end{equation*}
\begin{equation*}
    account(currency) = \lambda(0, currency)
\end{equation*}
\begin{equation*}
    bestprice(symbol) = \lambda(2, symbol)
\end{equation*}
\begin{equation*}
    orderpage(symbol, price) = \lambda(3, symbol, price)
\end{equation*}
where\\
\begin{itemize}
    \item $currency$ is a 32-bits unsigned number represented currency
    \item $symbol$ is consisted of $base$ currency and $quote$ currency
    \item $price$ is the index of orderpages sorted from best to worst
\end{itemize}

A matcher has a specific global state at the \(i_{th}\) event which can be verified by the leaf values:\\
\begin{equation*}
    orderbook_{s} = ask_{s} << 128 + bid_{s}
\end{equation*}
\begin{equation*}
    account_{j} = available_{j} << 128 + freezed_{j}
\end{equation*}
\begin{equation*}
    bestprice_{s} = askprice_{s} << 128 + bidprice_{s}
\end{equation*}
\begin{equation*}
    orderpage_{s, p} = vol
\end{equation*}
where\\
\begin{itemize}
  \item $s$ represents the $symbol$
  \item $j$ represents the $j_{th}$ account of current matching results
  \item $p$ represents the $price$
  \item all numerics are 128-bits represented unsigned fixed number with $scale$=18
\end{itemize}

For simplicity, let's define \(a \nabla b\) as \(a << 128 + b\).

\section{Proof of Matching}
\label{sec:org48d64ef}
Given a user-signed event \(E_{i}\) and some merkle paths \(P_{(i-1, j)}\) at \(i-1\), a validator can verify it using a matching procedure with well-known root hash \(S_{i-1}\) stored on-chain:\\
\begin{eqnarray*}
\sum\limits_{j=0}^{n} f(P_{(i-1, j)}, S_{i-1}) = n\\
P_{(i-1, j)} + E_{i} \Rightarrow S_{i} + P_{(i, j)} \\
\sum\limits_{j=0}^{n} f(P_{(i, j)}, S_{i}) = n
\end{eqnarray*}
where
$$
  f(p, s) =
  \begin{cases}
    1, p \in s\\
    0, p \notin s\\
  \end{cases}
$$

A matcher must maintain a Sparse Merkle Tree and update it every time after the event is applied and generate an associated proof which is composed of the origin command and some merkle leaves including value before and after the \(i_{th}\) event executed.\\
Let \((x, y)\) be an ask-limit order's price and amount of symbol \((b/q)\) as the \(i_{th}\) event, \((x_{j}, y_{j})\) be the \(j_{th}\) maker exists at \(i-1\). Then the proof generated by the matcher should be (Fee excluded):\\
\begin{equation*}
    account(b)_{(i, j)}=account(b)_{(i-1,j)} \nabla y_{j}
\end{equation*}
\begin{equation*}
    account(q)_{(i, j)}=account(q)_{(i-1,j)} - x_{j} \times y_{j}
\end{equation*}
\begin{equation*}
    account(b)_{i}=account(b)_{i-1} - (\sum\limits_{j} y_{j} \nabla 0) + (y - \sum\limits_{j} y_{j})
\end{equation*}
\begin{equation*}
    account(q)_{i}=account(q)_{i-1} \nabla \sum\limits_{j} x_{j} \times y_{j}
\end{equation*}
\begin{equation*}
    \sum\limits_{p}^{x} orderpage(b,q)_{(i, p)} = \sum\limits_{p}^{x} orderpage(b,q)_{(i-1, p)} + y - \sum\limits_{j} y_{j}
\end{equation*}
\begin{equation*}
    orderbook(b,q)_{i}=orderbook(b,q)_{i-1} + (y - \sum\limits_{j} y_{j}) \nabla 0 - \sum\limits_{j} y_{j}
\end{equation*}
The equations above are used for verifying the matching procedure with only some essential information by re-calculating on-chain. Once verified, the on-chain accounts state can be updated following the decoded leaves and the root hash stored on-chain to \(S_{i}\).\\
\section{Tokenomics}
Unlike some other crypto tokens based on smart contract, TAO is a native token used for paying gas and staking for provers upon Fusotao. Some TAO tokens are pre-minted at the genesis block, including:
\begin{itemize}
    \item[*] 8,000,000 for the Fusotao Team (locking)
    \item[*] 6,000,000 for the Fusotao Foundation (locking)
    \item[*] 11,500,000 for early investors (8,000,000 in locking state)
    \item[*] 11,000,000 for the initial liquidity and all incentives before mainnet, e.g. advisors, testnet rewards, bug bounties, community airdrop.
\end{itemize}
All accounts of Fusotao have two states $free$ and $reserved$. The most pre-minted TAO tokens at the genesis block are reserved at beginning until the unlocking block comes. The first unlocking block is the $1296000_{th}$ which will unlock 30\% of each reserved account, then 5.8\% will be unlocked automatically in every 432000 blocks after first unlocking event. \\
Apart from genesis block, anyone can mint TAO tokens from void in two ways:
\begin{itemize}
    \item 4109 in every 14400 blocks for Fusotao validator nodes managed by the Octopus Network
    \item 6575$\sim$21000 in every 14400 blocks for rewards of Proof of Matching before the $26280000_{th}$ block
\end{itemize}
Since Fusotao uses the Blind Assignment for Block Extention mechanism(a.k.a. BABE) issued by Parity Team, the validators need to stake some valuable tokens to secure the permissionless network. That's what Octopus Network provides. To run a Fusotao validator node, the maintainer must register on the Octopus Netowork and stake some OCT tokens, and Fusotao network should reward some TAO tokens back. In another word, the security of Fusotao network is leased from the OCT stakers and holders. For more details, please refer to the Octopus Network whitepaper.\\
Another way is to get the trading rewards on arbitrary provers upon Fusotao. Since every trading command must be verified on chain, the trading volume within a set of blocks is visible and deterministic, we call the set of blocks a Trading Era. The TAO rewards per unit in the $i_{th}$ trading era is:
\begin{equation*}
  R_i = \frac{X_{i}}{2\sum\limits t}
\end{equation*}
where\\
\begin{itemize}
\item $X_i$ is the total TAO to be minted in the $i_{th}$ trading era, \begin{math} $X_i$ \in [6575, 21000] \end{math}
\item $t$ is the trading volume of a transaction
\end{itemize}
The most remarkable usage of TAO tokens is to stake for provers upon Fusotao. The stakers of a prover would earn all the quote currency part of the transaction incomes. E.g. for the pair BTC/USDT, stakers will receive the whole USDT part of the transaction fees while the prover reserve the BTC part.\\
Like the trading era, the share is based on a set of blocks as well, we call it a season. Currently, a season equals 43200 blocks. The following formula indicates the shares per TAO staked for a prover at the $i_{th}$ season:
\begin{equation*}
  S_i = \frac{\sum\limits q \mul f}{\sum\limits t}
\end{equation*}
where\\
\begin{itemize}
\item $q$ is the trading volume of a transaction
\item $f$ is the transaction fee ratio
\item $t$ is the staked TAO from a single account
\end{itemize}

\end{document}