Sparse Merkle Tree and System State

Merkle Trees

We use fixed-height Merkle trees to store the state of the system, in a similar way to how Ethereum’s state is stored. This way, we can encode the whole state of the system into a single field element. There are several tree instances used to store users’ balances and orders respectively.

System State

Account State

Each users' account includes their public key and the tokens they own. Tokens are stored in a 16-level tall Merkle tree, which can record up to $2^{16} = 65536$ different tokens. In addition, all users’ accounts are stored in a 24-level tall Merkle tree, which can accommodate up to around 16 million users.

A given user with ID i will be stored at the i-th leaf node starting from the left. The first leaf (0-th) is reserved as the default value of the account.

Order State

A Merkle tree is used to store orders placed by lenders and borrowers in different rounds of auctions. After getting matched, fulfilled orders are removed from the tree, while partially filled orders remain in the tree, with their amount to be filled updated.