CodeChain DEX protocol
CodeChain DEX protocol
Author: JinGyeong Jeong <[email protected]>, Joonmo Yang <[email protected]>
Created: 2019-09-18
Centralized exchanges are often criticized for unscrupulous practices, such as practicing unfair listing processes and front-running[1] users’ trades. Most centralized exchanges have exclusive rights to listings, allowing these exchanges to make unreasonable demands. Also, they are often accused for allegedly front-running some customers for their own profits. As an alternative, a variety of DEXs, such as 0x, Bancor and Binance DEX, were surged and introduced in the market. These DEXs solved many problems created by central exchanges, but they failed to address front-running attacks.
On contrary to common belief, DEXs are vulnerable to front-running attacks due to their decentralized and transparent nature. Binance DEX tried to mitigate front-running attacks by introducing fill price and batch auction, but the validators can still efficiently front-run the transactions. Recent proposals[2][3] utilize the commit-reveal scheme to solve this issue, but they suffer from usability issues due to requiring participants to engage in extensive amounts of interactions.
To circumvent this problem, we suggest a commit-reveal scheme that does not require any interaction between the participants, allowing traders to send orders non-interactively to the network. We also propose a listing process that is operated by the stakeholders’ delegations. The delegation system encourages stakeholders not only to list assets that are in great demand, but also delist assets that are in poor demand.
In CodeChain’s previous DEX protocol[4], the OrderOnTransfer field existed in the TransferAsset transaction to support an off-chain order book and on-chain execution. For off-chain DEXs, such as the 0x-protocol, an order book is controlled by a centralized server called a relayer. A relayer submits transactions to the blockchain only when orders are matched. This approach helps reduce transaction fees, but it does not prevent relayers themselves from front-running the users. Also, the off-chain DEX protocol causes usability issues for other applications since orders are stored only in the centralized server, preventing them from knowing which UTXOs are available to use, unless they communicate with each other.
In general, exchanges process orders in a FIFO manner. A front-running attack[5] describes the act of taking profits not only by cutting in line, but also by attacking a specific transaction. For example, let’s assume that Alice wants to cancel her buy-order because there was an announcement that predicted the asset’s price to go down. Mallory, who runs a non-validator node, can see the cancel transaction of Alice and front-run by sending a sell-order with a higher transaction fee. A regular validator will sort transactions by its fee, resulting in Mallory’s transaction being executed before Alice’s. In case Mallory is a block proposer, she would not even have to pay a transaction fee since she can simply refuse to include Alice’s transaction into the block at all.
One of the popular methods for preventing front-running attacks is by ensuring confidentiality with commit-reveal schemes. In this scheme, users first send a cryptographic hash or encrypted data, which is called the commitment of a transaction. The original transaction remains unknown until it is revealed by the users later. Since attackers can’t extract any information from the commitments, it is impossible for them to front-run the transaction before it is revealed.
All committed transactions should be revealed regardless of the users’ preference. However, the common problem of the existing schemes is that there could be a user who knows the result before the transaction is revealed. If this user discovers that not revealing the transaction is more profitable, the user would refuse to reveal it. This can be mitigated by requiring the users to deposit some funds and slashing them if they don’t reveal a transaction. However, users will still refuse to reveal the transaction if they think it’s more profitable to do so.
THORchain[6] proposed a method where users encrypt the message with the public key of the upcoming validator. The validator must decrypt the message in the upcoming block. The pitfall of this method is that the validator itself can leak the decrypted message or front-run the transaction. Moreover, a validator can fail to propose a block due to various reasons such as network congestion and blackouts. If so, the committed orders cannot be executed. Another limitation of this method is that it depends on the consensus algorithm. For example, it’s easy to select the upcoming validator in a round-robin algorithm. However, it’s impossible to select one in a randomized leader election method[7] because there is no guarantee that the selected validator will create a block within time.
BIP32, which is known as HD wallet, describes an algorithm for deriving a private/public key from the root private/public key and an arbitrary key path. It’s usually used for managing many keypairs without having to remember their full key values. The most important feature is that if we use the same key path, the private key derived from the root private key corresponds to the public key derived from the root public key. A detailed explanation can be found in the BIP document[8].
Shamir’s secret sharing[9] is an algorithm for distributing knowledge about a single secret into multiple parts. It can specify the number of parts to share and the minimum required number of shares to recover the original secret. It uses the mathematical property that k-degree polynomial’s coefficients are uniquely decided by k+1 different points that resides on the polynomial’s graph. The algorithm for sharing the secret into n parts with threshold th is as follows:
- Pick a random secret
s - Pick
nrandom numbersa1, …,an - Define
f(x) = s + a1x1 + … + ath-1xth-1(mod p)wherepis a large prime number. -
(1, f(1)), …,(n, f(n))are the secret shares
Time-release encryption protocols are used when the message should not be decrypted before a predefined length of time passes. It’s usually referred to as “sending information into the future”. According to Rivest, Shamir, and Wagner[10], we can construct time-release encryption by either using VDFs[11] or relying on trusted agents. Using VDFs would seem promising, but there are some pitfalls for real-world usage. The LCS35 puzzle, which was expected to take 35 years of computations in 1999, was solved in 2 months with the modern ASIC design. There is much difficulty involved when ensuring whether the parameters we select will be working as we intended.
The trusted agent based time-release encryption described in [10] relies on entities called “trusted agents” that periodically disclose the secret keys to the public. It assumes that the agents are always online and responds to all encryption requests from the clients. Messages are encrypted with the secret key that is expected to be published in the future, and they are revealed once the trusted agent publishes the secret key. This scheme is not appropriate to use in blockchains because it requires the agents to always be online while the protocol is running. There is an offline variant of this system, but it requires all the public keys that will be used to be published at the start of the protocol, making it inappropriate as well.
This section describes an on-chain DEX protocol designed for CodeChain. Section 3.1. Listing and Delisting explains how trading pairs are listed or delisted by CodeChain stakeholders and asset issuers. Sections 3.2. Order and 3.4. Order Matches define a matching engine that is fair to everyone. Section 3.3. Commit-Reveal Scheme proposes a solution to front-running attacks.
Stakeholders can control trading pairs of the DEX by delegating their CCS to trading pair proposals. DEX delegation should not be confused with delegation for validators. Stakeholders earn trading fees from the markets that they delegate their CCS to. Delegating CCS incurs an opportunity cost. It is in stakeholders’ interests to stop delegating their CCS in unprofitable markets and move them to new lucrative markets.
To list a trading pair, a ProposeList transaction must be confirmed. Only the registrar or the approver[12], who are considered to be controlling the asset, are allowed to send the ProposeList transaction.The proposal must get a fixed quantity of CCS delegation to be activated. Let’s say the fixed quantity is 10,000 CCS for the sake of simplicity in this document, but a value would be decided by stakeholders. A ProposeList transaction must contain the following:
- Trading pair (currency and asset)
- Tick sizes for price ranges
- Lot size
- Maker/taker fee rate
- Order cancellation fee (fixed value, but not 0)
- Proposer fee rate
- Proposer’s asset address
The proposer fee is a reward for the proposer of the market and has a value between 0 and 1. Before distributing the trading fee to the stakeholders, the specified rate of the total trading fee goes to the proposer’s address and the remaining amount is distributed amongst the stakeholders.
Once a proposal is submitted, stakeholders can delegate as much of their CCS as they wish. They earn trading fees proportional to their delegation amount. If the total CCS delegation is greater than or equal to 10,000 CCS, then the trading pair is listed right away. The trading fee from the listed trading pair goes to the stakeholders (proportional to the amount of delegation). A stakeholder must provide an asset address when delegating because the trading fee is paid out in the respective currency of the trading pair, not CCC.
Thus, a DEX delegation transaction must contain the following:
- Delegation quantity
- Stakeholder’s asset address
The unregulated assets are the assets that have no registrar or approver in the asset scheme. For unregulated assets, any user can send a ProposeList transaction. The proposer fee doesn’t exist because there is no reason why stakeholders would share the trading fee with the proposer. One of the stakeholders can send a proposal with zero proposer fee.
Stakeholders are always able to revoke their delegated CCS if it’s more profitable to delegate it to another trading pair. If the total CCS delegation becomes less than 10,000 CCS, any new orders are rejected except for cancellations. A delisted trading pair can be re-listed later when it gets enough CCS delegation(s) without the need to submit another ProposeList transaction.
Changing the market parameters, such as tick sizes and fee rates, can be done by sending another ProposeList transaction. Multiple markets can coexist for the same trading pair, but with different market parameters, as long as they receive enough delegations.
For a regulated asset, the registrar can be changed through a ChangeAssetScheme transaction[12], which means that the right to earn the proposer fee can be transferred. In that case, a new registrar should change the proposer’s asset address. Unlike other fields in the ProposeList transaction, the proposer’s asset address can be changed without submitting a new proposal.
When it comes to DEX delegation, stakeholders want to earn as much trading fees as possible. For larger markets, there are always trading fees that can satisfy a number of stakeholders, so the market will remain active unless it becomes smaller. A single huge market does not consume all the delegations because profits per delegation would become smaller as the total delegation grows larger. If one’s profit diminishes, they would try to discover new markets. Stakeholders should keep an eye on which markets are most profitable for themselves.
Once a market is activated by the proposer and the stakeholders, users can send buy or sell orders to the market by consuming the UTXOs they have. An order contains the following information:
- Market ID
- Side (buy or sell)
- Price
- Quantity
Users can also cancel the order by simply designating the order to cancel. Orders that are not matched for a long time will be expired. The expiration period is decided by stakeholders.
To prevent front-running, users can encrypt the orders with the scheme explained in 3.3.2. For verification purposes, the UTXOs consumed by the orders are not encrypted. In other words, only the order-related information (price, quantity, order id that is canceled, …) is encrypted. The amount of assets the order is consuming must be equal to the quantity of the order plus the trading fee calculated by the policy in 3.5. Similarly, cancelations must consume the cancelation fee of the market and produce an asset of the quantity equal to the canceled order.
The commit-reveal scheme comes with overhead on the transaction size and a risk of not being decrypted. Traders can choose to send orders without encryption to avoid these issues. It’s vulnerable to front-running attacks, but it can be a good choice if the trader doesn’t think it’s going to happen (eg. for passive orders).
The main purpose of the commit-reveal scheme is to hide the content of the transaction so that attackers cannot front-run the traders’ orders. In short, the traders encrypt their transactions with a random secret key and encrypt the secret with publicly known encryption keys. The decryption keys are published later by the entities called reveal agents, and the transactions are decrypted and executed when the decryption keys are revealed. The reveal agents are rewarded by publishing their decryption keys on time, so the committed orders are revealed and executed with high possibility.
Reveal agents are entities that are responsible for publishing a new secret key for every block. Any account can try to register itself as an agent by sending CCC as a deposit. If the deposit becomes larger than MIN_DEPOSIT, the account is recognized as a valid reveal agent and the public key of the account is recorded in the state. Only valid reveal agents can publish secret keys to the blockchain, so secret keys can no longer be published if the deposit becomes lower than MIN_DEPOSIT.
The secret key must correspond to the public key derived from the reveal agent’s public key. Keys are derived with the HD key algorithm, and the key path is derived from the block number where the secret key is revealed. In other words, if the agent with secret key s wants to reveal the secret key r in the nth block, then r must be derived from s and n. The algorithm for generating key path from the block number n is as follows:
k = []
while n > 0:
k.push(n % 231 + 231)
n = n / 231
k.push(0)
return k
In case the agents were not able to submit the secret key to the chain in the block number they wanted, they can still reveal the secret keys in one of the subsequent blocks if the execution block (see 3.4.3) has not passed.
As explained in 3.2., the order commitment encrypts some part of the transaction with a random secret key. The secret key is separated into multiple parts and encrypted with the reveal agents’ public keys. The detailed steps for generating a commitment is as follows:
- Pick a random secret key
s - Encrypt the transaction with
s(->E) - Pick the total number of responsible agents
m, and the minimum required number of revealsth - Split s into m parts with threshold
thvia secret sharing scheme (->s1, …,sm+ metadata) - Pick the target reveal block number
n - Get the derived public keys at block number
nfor each responsible agent (->P1, …,Pm) - Encrypt
s1, …,smwithP1, …,Pm(->r1, …,rm) - Commitment is (
E,r1, …,rm,n, metadata)
Note that agents are expected to publish their secret keys at block number n, so the order can be decrypted publicly if at least m agents reveal the secret keys on time.
When a sufficient amount of reveal agents’ secret keys are published, the original secret key of the committed transaction can be recovered and the contents of the transaction can be decrypted. The decrypted transactions are executed at the execution block, which is calculated as n + EXECUTE_BUFFER. If the agents didn’t submit enough secret keys to reveal a transaction until the execution block, or if the decrypted commitment was an invalid transaction, the transaction is not executed and the trading fee is charged. The remaining associated assets, except for the trading fees, are refunded.
Agents must be rewarded since they are in charge of monitoring the network and sending reveal transactions. There are three candidates for reserving a fund for the reward:
- Charge users a fee when sending commitments
- Reserve CCC from CCS sales
- Adjust the minimum/express fee structure
The first candidate has a simpler model. Users pay fees for an encryption service and the agents provide the service. The last two candidates are models that charge the stakeholders a fee. It also makes sense because stakeholders earn trading fees from the DEX while agents help run the DEX.
Since the commit-reveal scheme can be applied not only for the DEX, but also any other transactions, it can be resolved in a broader discussion. In the later part of this document, it is assumed that there are reserved CCCs for the reward.
Agents are rewarded at the end of each term. A term is a set of consecutive blocks to distribute rewards and apply penalties in a batch. It will be explained in the “Reward Term” section. The total amount of reward at each term is fixed and the fixed amount is decided by the stakeholders. The reward distributed to the agents is proportional to the level of contribution, implying that the stakeholders control the number of agents.
In the agent’s point of view, it has to send all its reveal transactions to maximize the reward and not lose any deposits. In (a), the term reward weight increases only when the agent reveals the transaction. Agents can decrease the denominator by unrevealing some transactions, but the penalty is always bigger because it decreases the term reward weight and they receive a penalty.
.png)
(a)
In (b), for each agent, keep in mind that there is at most one reveal transaction per block.
.png)
(b)
By (c), the agent should be selected by as many users as possible. By (d), the agent should be highly trusted by users so that users don’t need to select others. Users will select more agents and set a high threshold if the agents aren’t credible enough, which means that each agent receives less reward for the same service.
.png)
(c)
.png)
(d)
The agent’s deposit is confiscated if they don’t send a reveal transaction in time. Since transactions can be excluded from the block for reasons such as network congestion or unprovoked rejection by validators, a minor mistake doesn’t impose a huge penalty. The penalty grows exponentially only when they don’t send reveal transactions consecutively. In (f), the exponential factor e starts from 1 and multiplied by 2 every consecutive unrevealed block. Table A shows an example of the exponential factor e.
.png)
(e)
.png)
(f)
.png)
(g)
.png)
(h)
| Block Number | Action | Factor e |
|---|---|---|
| 1 | Revealed | |
| 2 | Unrevealed | 1 |
| 3 | No commitment to reveal | |
| 4 | Unrevealed | 2 |
| 5 | Unrevealed | 4 |
| 6 | Unrevealed | 8 |
| 7 | Revealed | |
| 8 | Unrevealed | 1 |
| 9 | Unrevealed | 2 |
| 10 | Unrevealed | 4 |
The length of a term is decided by stakeholders. A term is not supposed to be too short because each term has a fixed amount of rewards. For example, if a term is one block, it is profitable to be the only agent in that block. Thus, validators can run their own agents and censor the transactions of other agents. If a term is long enough, attacking individual blocks is not profitable.
It might be confusing to know which term a transaction belongs to if the transaction is committed in the previous term and then revealed in the current term. Every transaction must be either executed or dropped at the execution block as explained in the “Revealing the commitments” section. The term reward calculation only takes the execution block into consideration.
Orders have priorities. The order that has a higher priority is matched first. The most important priority is price aggressiveness. For sell orders, a lower price gets a higher priority. Conversely, for buy orders, a higher price gets a higher priority. For cancel orders, they will have the same price priority with the limit order that it’s trying to cancel. What has second priority is the execution time of the order. If there is more than one order at the same price, the order executed earlier gets a higher priority. If orders have the same price and the same execution time, they are matched all together. This is explained further in the “Batch Trading” section.
Order transactions must be executed to take effect. Confirming an order transaction does not mean executing it right away. As explained in section “3.3.3. Revealing the commitments”, EXECUTE_BUFFER exists for encrypted orders. Encrypted orders are executed at the end of the buffer. For unencrypted orders, they must be executed after waiting for EXECUTE_BUFFER + 1 blocks. Otherwise, there is a chance to attack encrypted orders by cutting in line with unencrypted orders.
For each trading pair, the matching algorithm works as follows:
- Combine the orders on the orderbook and the orders executed at the current block.
- The best sell orders match the best buy orders, where the highest buy price is greater than or equal to the lowest sell price. See the “Batch Trading” section for the details.
- Repeat step 2 until there are no more orders to match.
- Apply the remaining cancel orders.
- Remaining orders go to the orderbook.
It’s possible that orders have the same priority, which means they have the same price and the same execution time. In this case, each order is matched in proportional to its quantity. For example, there are 4 sell orders with quantities (100, 250, 250, 400) and 2 buy orders with quantities (100, 300) respectively. 400 are matched in total. Table B shows that the sell orders are matched (40, 100, 100, 160) respectively.
Table B
| Selling Quantity | Proportion for Total Selling (1000) | Matched Quantity |
|---|---|---|
| 100 | 10% | 40 |
| 250 | 25% | 100 |
| 250 | 25% | 100 |
| 400 | 40% | 160 |
| 1000 | 100% | 400 |
In the example above, if the seller 100 canceled the order at the same execution time, the cancel order competes with the buy orders which has total quantity of 400. Accordingly, 20% will be canceled first. If there is more than one cancel order, they compete independently. Table C shows the canceled quantities when the seller 100 and seller 400 are trying to cancel. In Table D, there are values below the decimal point. Since these values cannot be divided equally, some orders are selected randomly and matched afterwards. For example, in Table D, there are 2 unmatched units among 4 orders. 2 of the 4 orders are selected randomly by using a cryptographic hash or a VRF and each order takes one unit respectively. After matching, there can be remaining quantity for the orders that were attempted to be canceled. These orders are eventually canceled by step 4 in the “Matching Logic” section.
Table C
| Canceling Quantity | Proportion for Total Buying (400 + Canceling Quantity) | Cancelled Quantity |
|---|---|---|
| 100 | 20% | 20 |
| 400 | 50% | 200 |
Table D
| Selling Quantity (After cancellation) | Proportion for Total Selling (780) | Matched Quantity |
|---|---|---|
| 80 | 10.2% | 40 (40.8) |
| 250 | 32.1% | 128 (128.4) |
| 250 | 32.1% | 128 (128.4) |
| 200 | 25.6% | 102 (102.4) |
| 780 | 100% | 398 (400) |
A block proposer has full control over the transaction sequence in the block but they can’t manipulate the matching result because execution and matching are done in batches. One possibility is rejecting all orders except for their own orders, which requires the validator to give up the validator fee.
The execution time of the order determines whether it’s a maker order or a taker order. An order is a taker order if it’s executed at the current block. It’s possible that both sides are takers.
There are two types of fees in DEX-related transactions: the transaction fee and the trading fee. To avoid situations where the traders have to manage both CCC(transaction fee) and the currency(trading fee), there are no minimum transaction fees for placing/canceling orders. However, like any other transactions in CodeChain, the traders are free to add transaction fees to orders if they want their transactions to be prioritized.
The trading fee is paid when creating an order, and the required amount is calculated as the maximum of the following three values:
- Cancel fee
- Maker fee (= Order price * Order volume * Maker fee rate)
- Taker fee (= Order price * Order volume * Taker fee rate)
The trading fee is refunded if there are leftovers after charging the fees for matching or canceling the order. The charged fee for each situation is as follows:
| Action or Event | Fee |
|---|---|
| Order cancel | Fixed amount specified in the listing |
| Order expire | All the remaining trading fee |
| Order match(Taker) | Matched volume in currency * Taker fee rate |
| Order match(Maker) | Matched volume in currency * Maker fee rate |
- Tick sizes and lot sizes
- Fair cancellation in Batch Trading
- Censorship-proof
- Cancel/Expire fee
[1] Protecting Against Front-Running and Transaction Reordering https://forum.openzeppelin.com/t/protecting-against-front-running-and-transaction-reordering/1314
[2] Anonymous Auction Protocol Based on Time-Released Encryption atop Consortium Blockchain https://arxiv.org/abs/1903.03285
[3] Keeping Time-Release Secrets through Smart Contracts https://eprint.iacr.org/2018/1166
[4] CodeChain Specification - Asset Exchange Protocol (outdated) https://github.com/CodeChain-io/codechain/blob/cf4ca475e62381404674b082b90296e9df4968d7/spec/Asset-Exchange-Protocol.md
[5] SoK: Transparent Dishonesty: front-running attacks on Blockchain https://users.encs.concordia.ca/~clark/papers/2019_wtsc_front.pdf
[6] Reducing front-running on a DEX https://medium.com/@thorchain/reducing-front-running-on-a-dex-3c44ea00293a
[7] Randomized leader election using VRF https://research.codechain.io/t/randomized-leader-election-using-vrf/17
[8] BIP 32 - Hierarchical Deterministic Wallets https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
[9] How to Share a Secret https://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf
[10] Time-lock puzzles and timed-release Crypto https://people.csail.mit.edu/rivest/pubs/RSW96.pdf
[11] Verifiable Delay Functions https://eprint.iacr.org/2018/601.pdf
[12] CodeChain Specification - Transaction https://github.com/CodeChain-io/codechain/blob/master/spec/Transaction.md
jmyang This protocol relies on the BIP32 key derivation, but I found out that we can't use it because of the following reasons.
- If we use normal(non-hardened) derivation, root private key can be extracted from the child private key.
- If we use hardened derivation, child public key can't be derived from the root public key.
We need to find a new way of solving this situation.
jmyang We had a seminar about this proposal yesterday. Here's the link for the slides: https://docs.google.com/presentation/d/1oIRKYmwrYI9l2gMQ_SV7LBUDN8D0taRmBwD9-gcwldc
spkim What happens if malicious reveal agents reveal wrong secrets? To recover a secret key for decrypting a transaction, users need partial secrets split by secret sharing. Suppose a secret sharing scheme set 20-of-30 threshold and 24 pieces are collected, but 4 of them are corrupted by malicious reveal agents. Should a user try all 24C20 possibilities to recover the secret key?
jmyang Since the root public keys of the agents are recorded in the blockchain state, anyone can verify if the secret is correct by comparing it with the derived public key. If the secret key was malicious, it’s public key will be different from the child public key derived from the root public key.
We can filter out those invalid secret keys and recover the original secret key of the commitment only with the valid secrets.
spkim Then, is there an incentive system to punish such malicious users? It seems there is no distinction between malicious secret giver and non-giver until now.
jmyang There’s no penalty for that yet, and I think it’d be better to have one. Maybe slashing all the deposits of the malicious agent would be enough. It’s the similar rule with the double-voting validators.