-
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 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. To reduce the numbers of block producers, a simple solution is to delegate the block producing right to a small group, which collectively run a Byzantine fault tolerance (BFT) algorithm. This 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 node produces the blocks. This greatly 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 of time, it can know for sure that 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 it only tries to reach consensus if exactly one notarized block is produced. It explicitly allows multiple notarized blocks, the consensus is reached overtime. This is exactly 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 threshold BLS signature scheme is used. The t-of-n BLS threshold signature is unique, meaning whichever t signature out of a total of n signature shares is used to recover the group signature, the recovered signature will always be same and unique. 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.
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 goes into "maintenance" 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 as of now, you are as interested with this consensus protocol as I am. 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 causes the account nonce increment, so the transaction cannot be spent again.
Exchange 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 and outputting 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.