Author Topic: How BitShares Prevents Front Running [BLOG POST]  (Read 4824 times)

0 Members and 1 Guest are viewing this topic.

Offline starspirit

  • Hero Member
  • *****
  • Posts: 948
  • Financial markets pro over 20 years
    • View Profile
  • BitShares: starspirit
Some questions because I don't fully understand why its preferred to take the difference as a fee:

1. I think the moral and legal issue with front-running at centralised exchanges is that front-runners have privileged information on which to profit. It seems to me that on a block-chain there is no such privileged position, since all order information is immediately public (apart from block-producers, who are subject to our votes). While its true that some market participants can adjust their position more quickly than others based on the public information to get a better outcome for themselves, why should such free action be considered undesirable?

2. Would users prefer to bear the cost of the exchange taking the difference, when that is the maximum cost they would bear with the actions of front-runners? Since front-runners are not perfect, the cost to bear front-running must be less than the exchange taking the entire difference, isn't that correct? Might this not just be perceived by a wider audience as the exchange being greedy?

Thanks
« Last Edit: March 05, 2015, 05:09:43 am by starspirit »

Offline monsterer

A sequence would be ideal. However the order and therefore the associated sequence number that could be derived is a function of network overhead/p2p hops and unrelated to real-time order creation. An alternative would be a client-generated timestamp - but this could be trivially forged by the client.

You only need to number the pending orders as they come in with a temporary sequence. The orders already on the book are all limit orders and therefore will not need a sequencing number - you give them the best price by default. You only need sequence for incoming orders which ought to be trivial. I think. :)

edit: regarding verify-ability, the incoming sequence number that each block producer assigns ought to be saved such that the next block producer in the sequence can verify the orders matched as described with the given sequencing.
« Last Edit: January 30, 2015, 09:50:59 am by monsterer »
My opinions do not represent those of metaexchange unless explicitly stated.
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

julian1

  • Guest
So now all you need to do is identify the means of establishing who gets the benefit of the overlap (buyer or seller)... throw in a small spread for the network and it could be very "traditional" with all of the problems of a traditional system.   Let the "experts" milk inefficiencies.

Here's how I would do it:

* Use the one delegate's eyes only encryption for pending orders
* Number incoming orders sequentially
* Don't match any orders until the block is about to be produced
* Match pending orders against limit orders in the book and themselves
* Sort them by price and then sequence number
* Give best price to the orders with the oldest sequence number
* Don't bother with network spread as the transaction fee already covers it

That's as close as possible to a traditional exchange.

A sequence would be ideal. However the order and therefore the associated sequence number that could be derived is a function of network overhead/p2p hops and unrelated to real-time order creation. An alternative would be a client-generated timestamp - but this could be trivially forged by the client.

In a blockchain, it's the blocks that provide the major sequencing points, hence the suggestion to only match inventory orders against orders already in the prior block to remove front-running profit opportunities.

Combating front-running by having the market-engine itself pessimistically doing the front-running (and then distributing the benefit to extra-contractual parties by burning) isn't a great solution.
« Last Edit: January 30, 2015, 08:44:31 am by julian1 »

Offline monsterer

So now all you need to do is identify the means of establishing who gets the benefit of the overlap (buyer or seller)... throw in a small spread for the network and it could be very "traditional" with all of the problems of a traditional system.   Let the "experts" milk inefficiencies.

Here's how I would do it:

* Use the one delegate's eyes only encryption for pending orders
* Number incoming orders sequentially
* Don't match any orders until the block is about to be produced
* Match pending orders against limit orders in the book and themselves
* Sort them by price and then sequence number
* Give best price to the orders with the oldest sequence number
* Don't bother with network spread as the transaction fee already covers it

That's as close as possible to a traditional exchange.
« Last Edit: January 30, 2015, 08:16:05 am by monsterer »
My opinions do not represent those of metaexchange unless explicitly stated.
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
- front running is only one form of market manipulation, the current order forms *SLOW DOWN* people wishing to move the market which gives everyone a chance to react.

I'm not sure how the slowness provided by YGWYAF orders provides any meaningful reaction time for anyone other than bots or maybe serious traders that are glued to their screens. Right now it appears that a limit order that eats up the asks and short sells in the BTS/BitUSD market up to a new highest ask of 113 BTS/BitUSD (that is over a 15% change in price) could be pretty closely simulated with very little economic inefficiency with around 11 YGWYAF orders (that's less than 2 minutes).

But if you really care about slowing down markets you could build those limitations into the market. Take the average of the highest bid and lowest ask / short sell and call that the instantaneous center price. Restrict the price limit of limit orders to not deviate further than 5% from the active center price. The active center price follows the instantaneous center price with some lag.

Here is one possible implementation. There is source center price, a source time, a target center price, and a time period. The active center price linearly interpolates from the source center price to the target center price where the interpolation parameter (ranging from 0 to 1) is (current time - source time)/(time period). Once the interpolation parameter reaches 1, the old target center price becomes the new source center price, the current time becomes the new source time, the current instantaneous center price becomes the new target center price, and the linear interpolation of active center price starts over again. Choose an appropriate time period and set the 5% deviation limit to whatever other number that is more appropriate.

So now all you need to do is identify the means of establishing who gets the benefit of the overlap (buyer or seller)...

The person who gets the benefit is the one who initiated the limit order that automatically matched existing orders. There is no actual "overlap" in the case of the limit order.

Offline bytemaster

This is all very interesting, but perhaps we are over-thinking this too much.

- front running is only one form of market manipulation, the current order forms *SLOW DOWN* people wishing to move the market which gives everyone a chance to react.

- someone is going to make the money from timing attacks we can go ahead and "let them" make it.  To the average guy he might sometimes get a better deal, but certainly wouldn't get any worse deal. 

So if you want a more traditional order then it may not matter all that much.   

So now all you need to do is identify the means of establishing who gets the benefit of the overlap (buyer or seller)... throw in a small spread for the network and it could be very "traditional" with all of the problems of a traditional system.   Let the "experts" milk inefficiencies.

Just a thought.
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Quote
The potential for front-running exists because a delegate can see the unconfirmed order tx, and has the opportunity to insert a new tx in the block to take advantage of it.

Could this be avoided by simply changing the market-engine so that unconfirmed orders in inventory are only tested/matched against orders that have already been confirmed/written to the blockchain?

If orders in inventory are never matched against each other then won't that eliminate the delegate's ability to front-run the trade?

What are the downsides to this, if any?

I thought about this, and it is an interesting idea. It's not perfect though. Let me explain with an example.

I'll take the scenario from the blog post. Say there are three orders submitted into block 1: 10 coins at $1/coin; 20 coins at $2/coin; and, 20 coins at $3/coin. By block 2, everyone can confirm that these orders exist. Now, let's say Alice wants to buy 50 coins with a limit order. She submits a limit order to buy 50 coins with a price limit at $3/coin and funds it with up to $150. The idea is that this transaction will be included into block 3 and buy up all three orders for $110 and give Alice 50 coins and also leave her with $40.

After Alice submits the transaction to the network, Bob (who let's say is producing block 3) sees this transaction and tries to front run the order. He places the following two orders in block 3 along with Alice's order:
  • A limit order to buy 50 coins with a price limit at $3/coin and funded with $150. This transaction is crafted in a way to be processed before Alice's transaction (after all, all market orders need some deterministic order in which they are processed).
  • An order to sell 50 coins at a price of $3/coin.
What happens while executing block 3 is that the three orders are matched with Bob's order (so he is at -$110 and +50 coins), then Alice's limit order is placed but there are no orders to match against it. Then Bob's sell order at $3/coin is placed but it does not match against Alice's order because they were included in the same block.

Then block 4 executes. The two previous orders that have not been matched but could be matched should probably execute now. However, if they immediately do, then this doesn't solve the front running problem at all (Bob would be at a net +$40 and +0 coins). If they never match, then that could be an annoying problem. There would be two orders sitting there with overlap that refuse to match against each other because they happened to be submitted into the same block. If any new orders did not match against them, the accounts would be forced to cancel the orders and try again.

So what I suggest is that the orders submitted into block 3 that were not matched with orders prior to block 3 should then match with each other (if possible) in the next block (block 4) but only after any market order cancel transactions are first executed. Thus, Alice's client could notice that her limit order did not get matched the way she hoped it would and could automatically submit a cancel order. If her cancel order reached block 4, then it is as if her limit order never happened (other than the two transaction fees). On the other hand, Bob would have spent $110 buying 50 coins with no guarantee that he can sell it soon for more than $110. Alice may or may not be willing to accept Bob's order to sell 50 coins at a price of $3/coin. If she decided to ignore it and hold out for a better deal, Bob is stuck exposed to 50 extra coins he does not want. If the price of those coins goes down, Bob could end up losing money compared to if he had never attempted the front running in the first place. So this now becomes speculation and not front running. There is no guarantee of profit.

Also, instead of requiring Alice's client to send a new cancel transaction, we could simply have a fill-or-kill order type. Either Alice's limit order would get fully matched with any of the orders that existed prior to block 3, or the order would become void. Alice would also want to make the transaction expire after block 3 so that it either gets included in block 3 or becomes void, in order to prevent the delegate producing block 3 from delaying that transaction by a block so that he could get his front-running transaction in. It would also probably be smart for the transaction to be encrypted for the delegate producing block 3 only so that as little information as necessary about Alice's intent is leaked out to the public. If the transaction was killed because someone beat Alice to filling the existing orders, Alice would have to create a new order, perhaps a YGWYAF order that sits in the order book until someone later matches it.

The option of having Alice's client monitor the change in the order book and decide whether to submit a cancel transaction has other merits though. It allows Alice to encode whatever conditions she wants for what a successful "fill" means into the client without the blockchain needing to be aware of it. For example, maybe if the majority of her limit order would be filled but not all of it, that could be considered good enough to Alice and she would prefer not to kill the entire order. Her client can respect those wishes by refusing to submit the cancel order for block 4.

However, the "submit limit order and then submit cancel order immediately afterwards if desired" model has some flaws. If Bob is colluding with the other delegate who is producing block 4, that delegate could simply ignore Alice's cancel order. The delegate order is randomized every round, which helps us. Nevertheless, the colluding delegates can just wait until a round when two of them produce blocks back-to-back to do their front-running with guaranteed profits. In those rounds, they are free to front run any market/limit orders which are not of the fill-or-kill type. If there are two colluding delegates, the probability of a given round being one where they are back-to-back is 2%.

But this is a scenario where statistical analysis by all the live nodes is actually possible, unlike my previous idea of only sending the transaction to the next delegate which gives the delegate plausible deniability because they can just blame it on someone trying to frame them. The market/limit orders would still be encrypted for the delegate producing the very next block (and they would be designed to expire after that block so that they will only be included in that block or they won't be included in the blockchain at all). This would mean that only that delegate (and the submitter of the order) would have the information necessary to do the front running. If clients notice that front running transactions appear to be submitted in block N AND that a cancel transaction for that order is submitted into the network immediately after block N is produced but yet does not get included in block N+1, and they see this happen again and again whenever the delegates producing block N and block N+1 are the same ones from some small set, then they could confidently assume that those delegates in the set are colluding together to front run orders. The cancel transaction part is important. That is something that is in the control of the delegate producing block N+1 and not in the control of the submitter of the order. So an order submitter that was front running himself to try to frame a delegate and get them fired cannot do so in this model because it only counts as a negative mark against the delegate if the cancel transaction was propagated into the network after block N but well before the deadline of block N+1 and yet it was not included in block N+1.

Offline fluxer555

  • Hero Member
  • *****
  • Posts: 749
    • View Profile
Quote
The potential for front-running exists because a delegate can see the unconfirmed order tx, and has the opportunity to insert a new tx in the block to take advantage of it.

Could this be avoided by simply changing the market-engine so that unconfirmed orders in inventory are only tested/matched against orders that have already been confirmed/written to the blockchain?

If orders in inventory are never matched against each other then won't that eliminate the delegate's ability to front-run the trade?

What are the downsides to this, if any?

julian1

  • Guest
I made a comment in technical support about an alternative,

Quote
The potential for front-running exists because a delegate can see the unconfirmed order tx, and has the opportunity to insert a new tx in the block to take advantage of it.

Could this be avoided by simply changing the market-engine so that unconfirmed orders in inventory are only tested/matched against orders that have already been confirmed/written to the blockchain?

If orders in inventory are never matched against each other then won't that eliminate the delegate's ability to front-run the trade?

I'll also add that I don't think the current approach is ideal for a few reasons.

1. There's a whole body of economic theory devoted to studying the principle of Consumer Surplus (http://en.wikipedia.org/wiki/Economic_surplus), which is the difference in price that two parties are willing to contract for according to their preferences compared with the equilibrium market price. It's considered a foundation benefit of the free market by economists, and the Bitshares market-engine currently ends up distributing that benefit to the currency holders via burning instead of the contracting parties by giving a better outcome than a centrally determined option.

2. It's contrary to other market matching engines, and will be very off-putting to any professional (fx)  trader that we might want to attract.

2. For my own project http://xchain.info which is a Bitcoin to Bitshares UIA asset exchange platform, I wanted to offer a Bitcoin to other bitAsset option by playing a market maker. However offloading my own risk by making automated counter trades on an external exchange like bter/btc38 is a lot more difficult due to the different market-engine mechanics.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Yes, I suppose that is prudent. In that case can't the sender just use whatever technology the encrypted memo stuff uses to encrypt the transaction only for the delegates account, or something?

Sure. It can use a one-time public key included in the transaction, EC multiply its corresponding private key with the delegate's public key, and use the corresponding shared secret to do symmetric encryption of any sensitive information in the transaction. Not all information in the transaction would be encrypted. Certainly not the one-time public key, but also the information that proves the transaction signer is paying the appropriate valid transaction fee (or has already paid it with the previous commitment transaction) is important to make public so that the nodes can know to relay the transaction forward and not be susceptible to DDOS attacks. Then when the delegate receives this semi-encrypted transaction it would use its private key and do EC multiplication with the one-time public key to get the shared secret that decrypts the sensitive information, such as the market the limit order is in, the quantity, and the specified price limit of the order.

Offline monsterer

If you want to "buy in bulk" then you can still get good deals, just not "instantly".    The wallet can submit one order every 10 seconds to take the best offer on the table at that point in time.   From the user's perspective it is very similar to a market order it just isn't filled "instantly".

This is a horrible idea in practice, though - you'll wind up missing out on the best price in fast moving markets and you'll pay more in transaction fees to boot. In addition, you'll end up placing limit orders instead of buying the top of the book if someone gets there before you.
My opinions do not represent those of metaexchange unless explicitly stated.
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline bytemaster

I actually dislike the method bitshares uses to achieve this because it results in a lot worse deals for traders who want to buy in bulk from the exchange.

IMO a better idea would be to consider something like the transparent forging proposal in NXT whereby orders are sent only to the next delegate who will produce a block (which is easy to know in advance), thereby preventing anyone but the delegate from performing front-running. Since you're already trusting them to produce blocks, I don't think this changes the risk profile much.

If you want to "buy in bulk" then you can still get good deals, just not "instantly".    The wallet can submit one order every 10 seconds to take the best offer on the table at that point in time.   From the user's perspective it is very similar to a market order it just isn't filled "instantly".
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline monsterer

You don't know the IP address of the delegate to protect against DDOS attacks.

Edit: And even if you did it would still be prudent to encrypt to protect against man-in-the-middle attacks.

Yes, I suppose that is prudent. In that case can't the sender just use whatever technology the encrypted memo stuff uses to encrypt the transaction only for the delegates account, or something?
My opinions do not represent those of metaexchange unless explicitly stated.
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads

Offline liondani

  • Hero Member
  • *****
  • Posts: 3737
  • Inch by inch, play by play
    • View Profile
    • My detailed info
  • BitShares: liondani
  • GitHub: liondani
I actually dislike the method bitshares uses to achieve this because it results in a lot worse deals for traders who want to buy in bulk from the exchange.

IMO a better idea would be to consider something like the transparent forging proposal in NXT whereby orders are sent only to the next delegate who will produce a block (which is easy to know in advance), thereby preventing anyone but the delegate from performing front-running. Since you're already trusting them to produce blocks, I don't think this changes the risk profile much.

Right, if you do what I said in my post above and you encrypt the reveal transaction for only the delegate that is producing the block after the block in which the commitment transaction exists in, and you make sure that YGWYAF orders are executed in the block after they are placed and are all executed before any other market/limit orders that are to be executed in the same block, then we can have a pretty good system.

It would allow people who want to use YGWYAF orders to use them as they usually do and know that the DAC will be the one to front run their order and give the proceeds back to the shareholders. Then anyone who chooses to do a market/limit order will know that only the delegate producing the block that will hold their reveal transaction is the one that can front run their order (and even then there is some probability that they won't be successful at it even if they try).

I am sure Bytemaster will seriously consider your proposals... (at least I hope so)

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Right, if you do what I said in my post above and you encrypt the reveal transaction for only delegate that is producing the block after the block in which the commitment transaction exists in,

Not sure I see the need the need to encrypt anything - if you're only sending orders to the next delegate, no one else sees them anyway?

You don't know the IP address of the delegate to protect against DDOS attacks.

Edit: And even if you did it would still be prudent to encrypt to protect against man-in-the-middle attacks.
« Last Edit: January 29, 2015, 08:56:15 pm by arhag »