-
Notifications
You must be signed in to change notification settings - Fork 15
White Paper
Contents
- Consensus Protocol
- Blockchain State
-
Future Directions
- Validation Sharding and Scalable On-chain Order Book
- Light Client
- Fast Sync
- Discard Finalized Blocks
- P2P Network That Supports Unicast, Multicast and Broadcast
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. 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 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 precisely one notarized block is produced. It explicitly allows multiple notarized blocks, so the consensus is reached overtime. 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 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.
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 set up a new group. 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 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 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 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 common blockchain architecture. 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 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's 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.
A core benefit of a decentralized exchange is the funds 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 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 great 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 and Scalable On-chain Order Book which skips signature validation. The signature does not need to be transmitted to every full node at all. However, this requires that the shard notary 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 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 proposing and the notarization process same as the Dfinity consensus protocol. At last, the notarized partial blocks from each shard will be merged by a global notarization group into a 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 assigned shard. The light client only needs to 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 by not performing the updates for the accounts which it does not 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.
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 client clients should be able to help each other, even better, help the full nodes.