Dual Authoring — Loopring’s Solution to Front-Running
Loopring is a protocol for building decentralized exchanges. In this post, we will briefly talk about the front-running issue in decentralized exchanges and will elaborate on how we solve it by using Daniel’s Dual Authoring solution.
An early version has been archived in IPFS: QmX48qyrSUdcvrJ2rFVrmvPxk6dkdoYKTGVBMRHC3ahzMh (PDF).
Daniel Wang, our founder, has researched and developed an enhanced solution for front-running prevention called Dual Authoring. We have applied for patents and coded the solution into our smart contracts. This feature will be deployed as part of our 1.2 protocol release. We believe Dual Authoring will bring us a very good competitive advantage.
Front-Running in Decentralized Exchanges
“Front running is the illegal practice of a stockbroker executing orders on a security for its own account while taking advantage of advance knowledge of pending orders from its customers.” [wikipedia]
In decentralized exchanges, front-running is when someone tries to mine transactions, before mining other transactions that are already in the pending transaction pool (mempool). This can be achieved by specifying a higher transaction fee (gas price), and if the front-runner happens to be a miner he can order pending transactions in a way that benefits himself.
The major scheme of front-running in Loopring (and any protocol for order-matching) are order-filch and ring-filch. Order-filch is when a front-runner steals one or more orders from a pending ring settlement transaction, and ring-filch is when a front-runner steals the entire ring from the pending transaction.
Before continuing, it is worth mentioning that the default Loopring match-engine does not guarantee First-Come-First-Serve (instead, it uses the over-the-counter or OTC model), meaning that orders’ timestamps are totally ignored. This further implies that front-running a trade has no impact on the actual price of that trade — Loopring only supports limit-price orders.
Anatomy of Orders and Rings in Loopring 1.0 & 1.1
Orders and Signatures
Orders in Loopring are created by wallets and tools that can help to manage a user’s private keys. Orders are JSON snippets and are transferred to relays in the form of a JSON payload via APIs. Here is an example of an order in Loopring 1.0 release:
Where the ownerfield represents the order’s owner_address from which tokens will be transferred once the order is filled. The order (including the owner_address) must be signed with owner_address’s private key. The order is valid only if the order_signature (represented by the r, v, and s) is valid.
As illustrated by the diagram below, the order_signature is actually signed against the order’s hash (or order_hash), which is the keccak256 function output of all other fields except r, v, and s.
It is easy to compute theorder_hash which is then used to verify whether the signing address is indeed the owner_address in the order or not. Relays will verify the signature of each order they receive; the Loopring Protocol smart-contract also verifies order signatures when 1) orders are submitted as part of a ring and 2) orders are submitted for cancellation.
Rings and Signatures
Rings don’t take a JSON form, rather, they are represented by all the parameters of the submitRing function provided by the Loopring Protocol. But if we visualize a ring, it will look like something below — it encapsulates all the data of its orders (a ring can have 2 to 10 orders). The miner of the ring will also populate its address (the miner_address) and other mining parameters (or ring parameters) into the ring so that the submitRing function will behave differently based on these input parameters.
Miners need to sign a ring’s hash ( ring_hash), together with all mining parameters with the private key of the miner_address. The ring_hash can be calculated as the XOR op-result of all the order_hashs or using other hash functions.
Please notice that the protocol does not require msg.senderto sign anything. In order words, a ring — as the submitRing transaction payload — can be signed by a mining address and the blockchain transaction itself can be signed (and broadcasted) by a different transacting address. The decoupling of mining address and transacting address provides extra flexibility and additional security advantage.
The diagram below illustrates the payload (or the parameters) of a submitRing transaction for a ring of 3 orders.
Why do miners need to sign rings? We need to make sure all trading stats are calculated/updated for the correct miners. These stats may be used by members in the consortium liquidity-sharing blockchain to calculate each member’s order production and consumption to consolidate inter-consortium payments.
Front-Running and Ring Filch
As describe the section above, when a submitRing transaction is not confirmed and still in the pending transaction pool, anyone can easily spot such a transaction and replace miner_address with his own address (the filcher_address) , then he can re-sign the payload with filcher_address to replace the ring’s signature. The fincher can set a higher gas price and submit a new transaction hoping block miners will pick his new transaction into the next block instead of the original submitRing transaction.
The Solution in 1.0 and 1.1
In v1.0 and 1.1, we allow ring miners to call either batchSubmitRinghash or submitRinghash function to reserve ring hashes before submitting the actual rings. When a ring is submitted, the protocol checks whether the hash of the ring has already been submitted/reserved by other miners if so, the protocol will reject the ring and the submitRing transaction will fail.
There are some downsides in this solution: it requires more transactions thus cost miners more gas, and it takes at least twice the block time to settle a ring. This is quite unacceptable.
Dual Authoring — Our New Solution
Our new solution involves the mechanism of setting up two levels of authorization for orders: one for settlement, and one for mining. We call it Dual Authoring.
How It Works
Here is how Dual Authoring works:
1. For each order, the wallet software will generate a random public- key/private key pair, and put the key pair into the order’s JSON snippet. (An alternative is to use the address derived from the public- key instead of the public-key itself to reduce byte size. We use auth_address to represent such an address, and auth_private_key to represent auth_addres’s matching private-key).
2. All fields in the order except auth_private_key is signed using the owner_address’s private-key (not auth_private_key) as shown in the image below.
3. The wallet will send the order, together with the auth_private_key to miners (relays) for matching. The miner will verify that auth_private_key and auth_address are correctly paired and the order’s signature is valid with respect to owner_address.
4. When a ring is identified, the miner will use each order’s auth_private_key to sign the ring_hash, miner_address, and all the mining_parameters. In the example below, the ring contains 3 orders, therefore there will be 3 signatures by the 3 auth_private_keys. We call these signatures the auth_signatures. The miner also needs to sign the ring_hash together with all mining parameters using miner_address’s private key in the same way as in protocol v1.0 and 1.1.
5. The miner calls the submitRing function with all the parameters in v1.0 and 1.1, as well as the 3 extra auth_signatures. Notice that auth_private_keys are NOT part of the on-chain transaction and thus remains unknown to people other than the relay itself, as shown in the image below.
6. The Loopring Protocol will now verify each auth_signature against the corresponding ofauth_address of each order and reject the ring if any auth_signature is invalid.
Why It Works
Now a ring cannot be stolen by anyone unless he has all the auth_private_keys of all enclosed orders. This is because:
- The order’s signature (by the private-key of the
ower_address) guarantees the order cannot be modified, including theauth_address. - The miner’s signature (by the private-key of the
miner_address) guarantees nobody can use his identity to mine a ring. - The
auth_signatures guarantees the entire ring cannot be modified, includingminer_address. And since ring-filchers do not have access toauth_private_keys, they cannot regenerate a new set ofauth_signatures thus are unable to generate a filch transaction.
Variants of Dual Authoring
Partial Dual Authoring
Dual Authoring requires signatures by all theauth_private_keys in a ring. A variant of Dual Authoring is to require one or only a few auth_signatures. This Partial Dual Authoring scheme also guarantees a ring as a whole cannot be stolen, but it is still subject to order-filch, and the filcher can use stolen orders in another Partial Dual Authoring enabled ring settlement transaction where the stolen orders auth_private_keys are not required at all.
Key-Sharing Dual Authoring
A relay may generate an auth_address /auth_private_keypair and requires all wallets connecting to it to use the same shared auth_addressfor all orders (since wallets do not have the auth_private_key, this field is missing from order’s JSON API payload). This Key-Sharing Dual Authoring scheme only allows only the relay to miner the orders it generates auth_address /auth_private_key pair for. Therefore, wallets do not have the option of sharing orders with other relays.
Implementation
Dual Authoring has been implemented in our protocol repository, the pull request is currently being reviewed, and tests will be updated soon.
Summary
Daniel’s Dual Authoring solution prevents ring-filch and order-filch while still ensures the settlement of rings can be done in one single transaction. In addition, Dual Authoring opens a door for relays to share orders in two ways: non-matchable sharing and matchable sharing.
If you have questions or suggestions regarding Dual Authoring, feel free to email Daniel directly.
Update: We decided to release this feature as part of v1.1.
For more up-to-date information, join us on social media:
⭑ Twitter: twitter.com/loopringorg
⭑ Reddit: reddit.com/r/loopringorg
⭑ Telegram: t.me/loopring_en & t.me/loopringfans (Chinese)
⭑ Discord: discord.gg/KkYccYp
⭑ GitHub: https://github.com/Loopring
⭑ Kakao: open.kakao.com/o/gJbSZdF (Korean)
