Batch auctions with uniform clearing price on plasma


#1

In the recent months, Gnosis put a lot of effort into developing market mechanisms on plasma. Today, we are excited to share two papers and we are looking forward to your feedback.

Multi-batch auctions with uniform clearing prices We developed a trading
mechanism between several ERC20 tokens on plasma. Each batch accepts orders to buy any ERC20
token with any other ERC20 token for a maximum specified limit price. All orders are
collected over some time interval and then a uniform clearing price over all token pairs is
calculated for the settlement of all orders.

There are three major advantages of this new market mechanism:

  1. Using batch auctions and DKG encrypted orders eliminates front-running possibilities.
  2. Batch auctions allow accumulating liquidity over time.
  3. Uniform clearing prices allow advanced ring trades between several tokens. This is a useful feature, as it allows to bundle the liquidity between different tokens. Considering the rise of many stable tokens, this will become a great feature: trades between a stable coin and a target token benefit from the liquidity between other stable coins and this target token.

We published two papers. One paper is focused on the plasma implementation and the other one is focused on the optimization of uniform clearing prices.
Here are the links to the papers.

We are looking forward to your feedback.


Futarchy with Bonding Curve Tokens
#2

Here is a paper written about a similar topic, though the goal of that paper is to reduce the arm’s race of high-frequency trading. It’s relevant here because Budish et al. propose frequent batch auctions. I think you could make the case that this frequent auction type market is exceptionally well suited to a blockchain due to it’s sequential and discrete nature. Thought you might want to flick through it, but it looks as though you have hit on a lot of very similar points.


#3

I would be interested in seeing a version of the paper written in plain English, rather than formalized mathematical proofs. For most of these sort of things I can make the jump from a simple English description (written using language anyone can understand without having to lookup words) to the mental proof that it is sound/works. However, trudging through a formal proof is a task so painful that I almost never bother.


#4

Yes, I agree. Batch auctions should be exceptionally well suited to plasma chains, due to their discrete nature. In continuous-trading models on plasma chains, this is even worse than outlined in the article, as the single, unregulated plasma operator would be able to front-run their own markets as they wish.

Currently, we are in the process to generate blog posts with technical writers and presentations. We will also present this topic at Dappcon in Berlin this week.


#5

20 min summary of the concept:


#6

For convenience, here are also the slides used at dappcon:


#7

This is very interesting work. Thanks for sharing!

Have you considered using a commit-reveal scheme similar to the ENS auction registrar as an another alternative to DKG-based encryption for bid submission? Since users are already required to remain online for the double signing, it seems like the reveal phase could probably be integrated with that. The main benefit is that, as commit-reveal depends on a hash, the complexities of key generation and broadcast are avoided.


#8

The problem with commit/reveal is that you can NOT reveal based on the additional information you get (the revealed orders of others). With the double signing you still can opt out of your trade but only at a moment when you still do not have any information about the other trades.


#9

The problem with commit/reveal is that you can NOT reveal based on the additional information

One way to mitigate that problem is to require a deposit with the commit which is forfeited if the reveal does not follow. ENS does this. But I can see in this case that would require some reworking of the utxo exit rules on the plasma chain and maybe becomes untenable, not sure. It also takes away the free option to exit the auction after initial submission, but it’s not obvious to me if that is an essential feature. Thanks for your response and I appreciate any further thoughts on this.


#10

Probably, it is not this straight forward. Where would people post their reveal msg? If people are supposed to post it only on the plasma chain, then this is tricky, as the plasma chain operator has some incentive to exclude your reveal-msg and get your bond. Hence, users should then also have a chance to publish it on the ethereum main chain. But since also the ethereum chain can be censored for some blocks, we would have to wait several blocks looking for the reveal msg. All that would slow everything down significantly and increases the complexity.

DKG has the advantage that ALL orders are revealed with only one private key. This is very favorable, as we do not need to care about a reveal process for single orders. It allows us to cut out quite some complexity and data compared to a simple commit-reveal process.


#11

i agree we do not want to incentivize the plasma operator to intentionally exclude reveals, so paying the full deposit to the operator is probably not a good idea. The operator shouldn’t receive more than whatever the standard fee is for participating in the auction. What to do with the remainder of the deposit is an open question. If nothing else, you could certainly burn it. Or maybe forfeitures can be used to subsidize subsequent auctions. I’m not arguing that commit/reveal is superior to DKG encryption, I was mainly curious how far you explored that possibility.

DKG encryption does place a burden on the user to verify that the DKG participants are currently bonded and that the bonds are appropriate for the estimated value likely to transact in the auction. And, if I understand correctly, the bonds are only slashed if the private key is prematurely revealed on the plasma chain. There is nothing really deterring the DKG participants from colluding over private back channels to generate the private key for just themselves. Conceivably, they could simultaneously be submitting multiple bids into the auction and then selectively double signing a subset of those bids once they have an early peek at the decrypted order book. Perhaps it is assumed that the DKG participants are sharing in the auction fees and therefore have some incentive to maintain the long-term integrity of the auction?


#12

This would be part of the client software. The usual client will not worry about it, as it is all checked by the client software.

There is: If someone asks you to participate in their malicious front-running activity and sends you over their secret DKG messages, then you have the change to call him out on the blockchain. You can publish his secret DKG message before the closing of the auction and then you will get his bonds.

If the DKG participants would trust each other completely, then they could front run. But since they don’t trust each other, as the system is set up in such a way, that there is a huge reward for calling out any misbehavior, I think collusion is very very unlikely.

Even that would open a door for griefing attacks, and push DKG participants out of the system.

Thanks for posting your thoughts, it helps a lot think thorugh a possible commit, reveal scheme.


#13

This is a great point I did not pick up on reading the paper the first couple of times. Basically, you are incentivizing defection from any potential collusive ring. Actually the ring is never established in the first place if its would-be members have to unilaterally surrender their secrets and risk getting slashed before they in turn receive a secret. But is there maybe a fair exchange protocol the members could deploy to work around this problem? I suppose if the group of DKG participants is very dynamic, then it is unlikely they could ever set up a protocol for effective collusion. What’s the process for electing DKG participants and how often does that happen?

Not sure what you have in mind here. If there’s a griefing attack with commit/reveal, it would be on the bidders. Like maybe a griefer could stuff plasma chain blocks to prevent reveals from being accepted by the operator before the deadline.


#14

This is really a tricky question. If there would be a completely trust less oracle, the DKG participants could commit themselves to not slash anyone in the original DKG slashing system. The commitment would just be organized via a smart contract, where the participants would need to post big bonds. These bonds are slashed, if anyone gets slashes in the original DKG bonding sytsem. If this new commitment-bond is much higher than the bond of the original bonding system of the DKG participants, then you can make it unprofitable for anyone to slash someone else in the original DKG bonding contract.

But I am unsure, whether people would commit to such a second bonding scheme, as the risk associated with it is quite high.

Sry, yes I got confused. Burning would be okay, it would only introduce a griefing vector for the plasma operator against the traders. But for sure, the operator would not use it, as otherwise, he will lose traders of his system.


#15

Hi! Appreciate all the work you’re doing with batch auctions. They’re a great mechanism and need a lot of love.

I just got around to reading your paper. I have a question about a specific scenario that might occur. Imagine a user joins a batch auction with a specific order input. The operator is behaving, the order is filled completely, the user now has order output. The user does not spend order output further.

What happens if the user attempts to exit from order input?


#16

If the order output was just created by the operator and has not been spent, then the order output can be exited. For this, we start the exit game by providing the order input, the double signature and the auction price and potentially the order volume . The output of this exit request will then result in the order output - the auction payout.

Order outputs will only be able to be withdrawn, by providing the order inputs.

Order inputs, which were not touched by the auction, can be withdrawn as the original order inputs.


#17

What happens if the operator withholds the order output block? Does the user get to exit from the input to the order?


#18

Generally, the output of an order needs to be withdrawn. If the operator withholds the order output block, then we need to calculate the output of the auction on the root-chain by providing the order input and the auction prices to the exit.


#19

Ah okay. Another question: What happens if the operator publishes an invalid block before the DKG private key is generated and immediately tries to exit? If the operator has control over the DKG participants, then I guess the exit period would need to be long enough for the operator to publish the DKG key and then to publish the auction prices?


#20

Yes, these cases are taken care by setting the right time frames:

If the DKG private key or the bitmap or the snarks proofs are not available, anyone can request the operator to publish them onchain. Then, the operator needs to publish these data within a short time-frame, much shorter than the 7 day exit period. While we have not yet defined this timeframe, we want to keep as short as some hours.

If the operator fails to publish the data, then the chain will be stopped on the root-chain and the last auction will be undone.