-
Notifications
You must be signed in to change notification settings - Fork 15
White Paper
Contents
- Consensus Protocol
- Why Dfinity Protocol
- High-Level Overview
- Open Participation
- Blockchain State
- Account vs. Unspent Transaction Output
- Concurrent Orders
- On-Chain Matching Engine
- Future Directions
- Validation Sharding and Scalable On-chain Order Book
- Light Client
- Fast Sync
- Discard Finalized Blocks
DEX implemented 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 approach is to select a very few numbers of block producers collectively run a consensus protocol. In my opinion, this introduces severe centralization risks. In comparison, Dfinity contains a decentralized random beacon, generating a stream of outputs over time. Everyone can participate in the block producing, but at each round, only a subset of nodes are selected by the random beacon to produce the block.
Finalization of the traditional blockchain system 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. Near instance finalization is very important for the user experience - the user would not want to execute an order and only to find out the next day that the order execution was reverted.
There are more advantages especially well suited for exchange such as:
- prefer consistency over availability
- more predictable block time than PoW systems
- eliminates selfish mining and nothing-at-stake attack
For details, please refer to the Dfinity consensus paper.
The consensus protocol is defined for a permissioned participation model, anyone can acquire the permission with a chosen kind of Sybil resistance. 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 the blockchain should be able to form new groups over time as a safety requirement. A group is identified by its group public key. 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 set up a new group. I have implemented a DKG proof of concept in a separate repo.
Similar to Ethereum, DEX is account based. 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 architecture, unspent transaction output (UTXO) is another kind of very popular blockchain architecture. It is used by the currency coins such as Bitcoin. It is a very elegant and natural solution for currencies as it mimics the way we track balance on a ledger. The replay attack is prevented by default: a spent transaction output cannot be spent again. In comparison, the account based solution 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 will cause the account nonce increment, so the transaction cannot be spent again.
In my humble opinion, the exchange is not a currency, it requires complex functionality such as order matching and ICO. The UTXO architecture may not be a natural fit. For example, a single order could be filled over time but a transaction consuming UTXOs is atomic. I am sure there are solutions to the problems. However, maybe we need a more general way of expressing blockchain state transitions.
In the account based architecture, 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 implements functions such as placing an order, issuing and sending token. From my experience, this model is easy for development and optimization since this database and 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.
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.
In the same time, sharding order matching is not easy. Different trading pairs share state: the user could want to trade on the ETH_BTC pair after bought some BTC from the BTC_USDT pair. Given the complexity and matching orders is extremely fast, we might not need to shard the order matching. However, another challenge is updating the account states is slow.
One powerful tool the Dfinity consensus protocol provides is once one notarized block is received, one has great confidence on the validity of the block. Otherwise, 400 (the group size) frozen deposits could be taken away as a punishment. One can trust all the transactions in the notarized block is valid without validating each transaction - a fraction of the nodes can verify and report the notarized block if any of the transaction is invalid.
We can partition the network into multiple shards for transaction validation (signature verification and verify the account has sufficient balance for placing an order), each shard will go through the block proposal and the notarization process same as the Dfinity consensus protocol. At last, the notarized blocks from each shard will be merged by a global notarization group, producing a global block.
One interesting observation is the network can be sharded according to the trading pairs: the transactions on a trading pair will only be proposed from its shard. The light client can observe the notarized block from the shard which handles the trading pair they care about, making the networking scalable for light clients. Furthermore, the light client does not have to maintain the entire blockchain state as well. It can simply trust the orders are valid, apply the order matching, and discard the executed orders and do not perform the account updates it doesn't care, making the validation and state transition scalable for light clients. In this way, the user can enjoy a real-time on-chain order book.