-
Notifications
You must be signed in to change notification settings - Fork 16
White Paper
Contents
DEX implements the DFINITY consensus protocol from scratch, feel free to refer to the paper for more details.
Fast block time and quick time to finalization are crucial for the exchange's user experience. Binance's "block time" and "time to finalization" are instant - the result of sound engineering and centralized service. How can a decentralized exchange match the high expectation set by the centralized exchanges?
The slow block time comes from the fact that there are too many block producers. The block time cannot be reduced to very low. Otherwise, there will be too many forks. A simple solution is to delegate the block producing right to a small group, which collectively run a Byzantine fault tolerance (BFT) algorithm to reach consensus. Having selected nodes with special powers introduces centralization risk, exacerbated by the fact that BFT algorithm is interactive so that the group size cannot be too big. DFINITY has a fast block time (1s in their private testnet) but without these centralization risks.
Finalization of the proof of work systems such as Bitcoin is likelihood based - there is always a small probability for reorganization however deep is the block buried. In the DFINITY consensus protocol, a transaction is finalized after three confirmations under normal operation. Normal operation is a likely event that happens when there is only one notarized block produced in the round.
In DFINITY, every registered node can participate in producing blocks. But at each round, only a subset of the nodes produce the blocks, dramatically alleviates the high block time problem. Additionally, a notarization concept is introduced. Only notarized blocks can be built upon, and only timely published block can be notarized. This means if a node received a proposed block but have not received the block notarization after a period, it can know for sure that the block proposal's chain is dead. Since without notarization, it can no longer be built upon. A consensus point is reached when there is only a single alive chain/chain prefix.
The notarization process may look similar to a consensus process, but the consensus is reached if precisely one notarized block is produced. Producing multiple notarized blocks is intentionally tolerated, so the consensus can be reached overtime, rather than everyone has to reach consensus before moving on. This is why DFINITY can be so fast.
Random beacon is another core innovation, it generates one random value at each round, selecting the active random beacon generation group, block proposing group and the notarization group for this round. The random value is derived from the group signature of last round's random beacon generation group.
This is possible because the BLS threshold signature scheme is used. The t-of-n BLS threshold signature is unique, meaning whichever t signature shares out of the total of n signature shares are used to recover the group signature, the recovered signature will always be the same. Generating random number with threshold signature means that unless the majority of the group collude, no one can know the random number beforehand, and no one can forfeit the protocol knowing that the outcome is not in his favor.
As mathematically proven in the paper, 400 is a group size that provides a very high level of safety confidence. The BLS threshold signature is viable because it's non-interactive, no multiple rounds of communication are required. Everyone broadcast its signature share, anyone with the threshold number of signature shares can recover the group signature.
The consensus protocol uses a permissioned participation model. Anyone can acquire the permission with the chosen kind of Sybil resistance method. I think it's most suitable to use the proof of frozen fund as the Sybil resistance method for the decentralized exchange.
Any node can register itself on the blockchain with the proof of frozen fund. But the consensus protocol runs with groups, so new groups should be able to form as a safety requirement. The group public key identifies a group. There is no group secret key. Instead, each group members owns a group secret key share. A Distributed Key Generation (DKG) protocol can be used to generate the group public key and the secret shares without revealing any secret key share. I have implemented a DKG proof of concept in a separate repo.
There are more advantages especially well suited for exchange such as:
-
Prefer consistency over availability: if the optic fibers between America and Asia are cut off, the exchange pauses rather than split into two exchanges.
-
More predictable block time than PoW systems: next block does not come from random guessing.
-
Eliminates selfish mining and nothing-at-stake attack: blocks cannot be withheld, only timely published can be notarized and built upon.
Hope now you are as interested with this consensus protocol as I am. For details, please refer to the DFINITY consensus paper.
Similar to Ethereum, DEX uses account based record keep model. It uses the Patricia Trie to save the blockchain state. The Patricia Trie is a modified trie providing O(log(n)) efficiency for inserts, lookups, and deletes. At the same time, very efficient in calculating the state root hash.
Different from the account based record keeping model, unspent transaction output (UTXO) is another common record keeping model. The currency coins such as Bitcoin use it. It is an elegant and natural solution for currencies as it mimics the way we use paper bills. The replay attack is prevented: a spent transaction output cannot be consumed again. In comparison, the account based model needs a nonce variable per account. Each transaction will have a nonce value. The transaction is valid only if the two nonce values match. Applying the transaction causes the account's nonce to increment, so the transaction cannot be applied again.
Exchange requires complex functionality such as order matching and ICO. The UTXO model may not be a natural fit. For example, a single order could be filled over time, but a transaction consumes and outputs UTXOs atomically. Maybe we need a more general way of expressing blockchain state transitions.
In the account record keeping model, Patricia Trie is a database that saves the blockchain states such as account balance and nonce. Transactions can be arbitrary functions that modify the database. DEX natively implements functions such as placing an order, issuing and sending token. From my experience, this model is easy for development and benchmarking since the database and state transition mental model is what engineers familiar with. I did not implement ICO due to time constraint, but it would not be hard to implement with this model.
A core benefit of a decentralized exchange is that the funds are at the user's custody. From this perspective, only the balance and transactions that swap the balances have to be on-chain. The matching service could be setup off-chain by any third party. In my opinion, the off-chain matching engine has several issues:
- Centralization. The third party matching service can censor orders, front run orders and have downtime due to attack or internal error.
- Reduced liquidity. The liquidity is spread across different matching service providers.
The on-chain matching engine does not have these problems but will have higher bandwidth and disk usages. However, the off-chain matching engine will not do an order of magnitude better. The placing order does not have to be on-chain, but canceling the order has to be on-chain. Otherwise, the third party matching service can exploit it at will, a severe risk for the users.
The storage scalability problem can be solved by discarding the finalized blocks. Blocks are used during chain reorganization and helping peers to sync. But with the finalization guarantee, chains whose tip is a finalized block will never reorg. And peers can do fast sync or get the blocks from an archive node which has the full block history. Thus a regular full node can safely discard the finalized blocks.
The network bandwidth scalability problem is hard to solve. One interesting observation is in a serialized place order transaction, the vast majority of bytes is used for signature (64 bytes for an ECDSA signature), the price, quantity, sell side and market information are all small integers that can be compactly encoded using variable length integer. They also have a good compression ratio due to the low information entropy. With this observation, we can go one step further than Validation Sharding which skips signature validation: the signature does not need to be transmitted to every full node at all. However, this requires that the shard notarization group provides a proof that the signatures are stored somewhere distributedly, which can be retrieved for validation when requested.
Signature verification is very slow, according to my benchmark, Ethereum's signature verification implementation can process 8200 verifications per second on a high-end CPU. Two orders of magnitudes slower than Binance's 1.4 million transactions per second. We will come nowhere close if there is no sharding involved.
At the same time, sharding order matching is not easy. Different trading pairs share state: USDT balance is shared between BTC_USDT and ETH_USDT pairs. Given the complexity and matching orders is extremely fast, we might not need to shard the order matching.
One great guarantee the DFINITY consensus protocol provides is once one notarized block is received, one has high confidence on the validity of the block. Because the active notarization group and the group members are selected randomly, and 400 (the group size) frozen deposits could be taken away as a punishment. One can trust all the transactions in the notarized block are valid without validating each transaction. As a safety measure, a fraction of the nodes can verify and report the notarized block if any of the transaction is invalid and receive a reward.
A regular full node does not have to validate transactions of the notarized block, but the block notarization group still has to validate transactions. We can partition the network into multiple shards for transaction validation (signature verification and verify the account meets the required condition for the requested action), each shard will go through the block proposing and the notarization process same as the DFINITY consensus protocol. At last, the notarized shard blocks from each shard will be merged by a global notarization group into a block. The shard notarization group validates the transactions so the global notarization group does not have to validate each transaction.
Validation sharding not only increases computation scalability but also increases network scalability. The transactions can be broadcasted within the shard rather than globally. But even more important, it enables the light clients to only subscribe to the shard blocks produced by the shards that they are interested. Please see Scalable Light Client for details.
Besides the privacy issues, the problem with the current Merkle Tree Proof based light client is that more light clients add more burden to the full nodes. More participants in the network should make the network scales better, not the reverse. The light clients should be able to help each other, even better, help the full nodes.
As mentioned in Validation Sharding, it's highly safe to trust all the transactions in a notarized block are valid. As a result, instead of verifying the Merkle Tree Proof, the light client verifies the block's notarization signature and the transaction signatures' root hash (the block header should contain both transaction bodies' root hash and the transaction signatures' root hash). In this way, the transaction signatures do not need to be transmitted. And the light clients can relay the random beacon, the block header and the block transaction signatures to each other and the full nodes.
Furthermore, with validation sharding, we can use the trading pair as the sharding criteria: the transactions on a trading pair will only include in the shard block that comes from its assigned shard. The light client only needs to observe the notarized shard blocks from the shard which handles the trading pair they care about. Thus, the light client can subscribe to the shards they care about on-demand.
Additionally, the light client does not have to maintain the entire blockchain state. It can simply trust the orders are valid, apply the order matching, and discard the executed orders by not performing the updates for the accounts which it does not care, making the computation scalable for light clients. In this way, the user can enjoy a scalable on-demand on-chain order book.
The basic idea is to download all the random beacon and block headers, and download the blockchain state N blocks ago, and do regular sync and validation afterward. With a sufficiently large N (e.g., 1000), fast sync is very safe.
The fast sync algorithm is similar to Etherem's fast sync with the difference that their algorithm downloads all the block bodies which make the disk consumption substantially larger.
Etherume needs the entire blockchain history because a high percentage of nodes uses full sync that downloads the entire blockchain history, and it needs to support the Merkle Tree Proof based light clients. DEX can use fast sync by default and rely on a low percentage of archive nodes that archive all the blockchain history in case any client wants to do a full sync. With the different light client approach mentioned above, no Merkle Tree Proof is needed, so all the full nodes other than the archive nodes can discard finalized blocks to save disk space substantially.
To make the networking more efficient, we need a routed P2P network that supports unicast, multicast and broadcast. Because the consensus protocol, as well as the sharding mechanism, runs better with multicast. The Distributed Key Generation process runs better with unicast. Currently, my idea is to implement a routed networking library similar to how Kademlia Distributed Hashtable routes the traffic according to the node's hash identification.