Author Topic: Front-Running of Trades  (Read 10830 times)

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Front-Running of Trades
« on: July 24, 2014, 11:19:12 pm »
I was doing the math on people front-running trades, and concluded that it might be a problem after all. Specifically, a blind strategy of copying nearly-all trades that one sees, doesn't have an edge, but does disrupt expectations of normal users (which is a problem).

Luckily, I think there is a solution in good 'ole proof-of-work, on the transactions themselves. Basic game theory tells us that, to reliably sort people into groups, we need something that is more expensive for members of one group than the other. We then reward people who can "send" that "signal". The solution is simple: assuming that a given hash/second costs the same for everyone (unfortunately, this is a weak (the weakest) part of the algorithm), more hashes in the same amount of time would cost more.

For example, assume everyone can hash 1 per second for free, and buy extra hashes/second for 1$ / hash.
If I start hashing at t=0, and hash 60 seconds, I have 60 hashes at t=60. I spent nothing.
If someone else started hashing at t=20, and hash until t=60, I only have 40 hashes at t=60. To get 60 I need to spend $20.

So the idea is to have individuals build a transaction, and then "store up" a required minimum amount of time in that transaction by hashing it to below a certain value. This at least discourages front-running of trades, as it is now costly.

I'm curious as to how developers would implement this solution. Require nodes to do this (possibly doubling as ddos protection)? It seems overkill to hard-code anything into the block-validation rules.

I doubt specialized ASIC-trader-services would emerge, as they only produce revenues if you can hash quickly AND have actionable trading info. If they do emerge, they'll probably be perfectly competitive "brokerage firms", facilitating trades in a very very cheap way (hashes aren't really differentiable).
Nullius In Verba

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Front-Running of Trades
« Reply #1 on: July 24, 2014, 11:19:53 pm »
I'm also curious how anyone else (namely Bitshares, which plans on using order books) plans on addressing this problem.
Nullius In Verba

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Front-Running of Trades
« Reply #2 on: July 25, 2014, 05:29:15 am »
POW is not free. You have to pay for electricity.
For many people, it would be cheaper to use the Amazon cloud to do the hashing for them.

Instead of:
correct author pays $0 and front-runner pays $20

it would be more like:
correct author pays $15 and front-runner pays $20

If the fee is high enough to prohibit front-runners, you will also stop honest traders too.

I'm curious as to how developers would implement this solution.

At line 189 on this page (which is the part that runs checks on any buy transactions):
https://github.com/zack-bitcoin/Truthcoin-POW/blob/master/txs_truthcoin.py

I would insert this line:
if det_hash(tx)>minimum_pow:  return False

At line 92 on this page (this is the part that builds buy transactions):
https://github.com/zack-bitcoin/Truthcoin-POW/blob/master/truthcoin_api.py

I would put:
while det_hash(tx)>minimum_pow:
      tx['nonce']+=1


Why wouldn't transaction fees solve this problem? A person who purchases in both directions has to pay double fees. On average, he loses more than he gains.

I had thought that buy orders were encrypted at first, and decrypted on a later step. Doesn't the encryption stop front runners?

Buying shares increases liquidity... how does this disrupt expectations? I cannot see how the front-runners are a problem.
« Last Edit: July 26, 2014, 09:07:05 pm by zack »

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Front-Running of Trades
« Reply #3 on: July 26, 2014, 02:15:33 am »
Front running is where I submit a trade (Buy 10 shares at 4$ /each) and someone else sees my trade, does not relay it, and instead relays their own trade "Buy 10 shares at 4$ /each". This is a problem because it is easy to do and disrupts the trader's incentives ("I have useful info, but why bother trading, it will just get stolen..."). One can't place fake trades, and hope they will get stolen, because there is no way of forcing a trade to be stolen, if it goes through (the original goal) you are stuck with it.

I had thought that buy orders were encrypted at first, and decrypted on a later step. Doesn't the encryption stop front runners?
You are thinking of Votes, which are sent it two waves to prevent cartels.
Nullius In Verba

Explodicle

  • Newbie
  • *
  • Posts: 1
    • View Profile
Re: Front-Running of Trades
« Reply #4 on: July 26, 2014, 05:36:16 pm »
I had thought that buy orders were encrypted at first, and decrypted on a later step. Doesn't the encryption stop front runners?
You are thinking of Votes, which are sent it two waves to prevent cartels.


That's how Namecoin avoids domain "front-running" too.
https://wiki.namecoin.info/index.php?title=Register_and_Configure_.bit_Domains

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Front-Running of Trades
« Reply #5 on: July 26, 2014, 05:57:29 pm »
My proof-of-stake blockchain solves your problem.

exponential growth of front runners->only miner can front-run-----------------
In a distributed network, when you make a transaction, you tell about 8 peers.
If 6 of them attempt to front-run, there would be 7 copies of an identical buy order.
All 7 would be sent to about 25 peers each, and maybe 20 of those peers replace the buy_transaction with there own...
so now there are 7*20=140 identical buy orders...

The exponential copying of buy orders makes me think that the only person to attempt a front-runner attack is the person who mines the next block. The person who mines a block can decide exactly which transactions to keep, and which to discard.

My POS system-------------------
largely based on slasher https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/
If we wanted to share a cake fairly, one of us would cut it, and the other would choose which side they prefer.
My proof-of-stake blockchain works on the same principle. Many miners do work to create potential blocks, the holders of truthcoin vote on which block they think is best.  The holders of truthcoin are expected to vote to make the value of truthcoin rise.
The holders of truthcoin would not vote for any blocks of suspected front-runners.

I have worked on this stuff a lot on my github. https://github.com/zack-bitcoin

Donations: 1GbpRPE83Vjg73KFvTVZ4EnS2qNkiLY5TT
« Last Edit: July 26, 2014, 09:14:50 pm by zack »

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Front-Running of Trades
« Reply #6 on: July 26, 2014, 09:02:27 pm »
That's how Namecoin avoids domain "front-running" too.
https://wiki.namecoin.info/index.php?title=Register_and_Configure_.bit_Domains
Cool! I didn't know that!

Maybe if we can carefully build the way mining works so that the miners don't have an incentive to try a front-run?
What do you think of the original idea I posted, to require a minimum proof of work per Buy/Sell (not for Transfer/Redeem). Nodes could require CPU-intensive >10 minute proof of work. Miners would have to start hashing a new Buy/Sell immediately upon seeing it, and probably still wouldn't be done by the time Mining was over. Over time they could change those hash functions and requirements around. Node could refuse to forward a block containing any transactions that didn't meet the requirement.

Miners control the hashing power, and double-spend powers, and so could refuse to follow these rules. But that's true for any rule...the group of all Miners would want to be following the most-useful rules.

I just don't know enough about how this is done in other systems. Or how Bitcoin's "transaction standardness" contrast with the ironclad block validation rules.
Nullius In Verba

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Front-Running of Trades
« Reply #7 on: July 26, 2014, 09:11:23 pm »
If you use anything other than my pos system, then you have a miner who can choose transactions.
The miner only gets 1/100th of the blocks, so he can't make things too much worse.
That miner is heavily incentive to replace every transaction he sees with a transaction of his own that buys 1/2 as much.

The problem is that every miner is incentiveized in the same destructive way. Tragedy of the commons.

The best way to select new blocks is to have the holders of truthcoin vote on it. The holders of truthcoin is the only group that is always incentivized to make the value of truthcoin go up.

Donations: 1GbpRPE83Vjg73KFvTVZ4EnS2qNkiLY5TT
« Last Edit: July 26, 2014, 09:15:59 pm by zack »

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Front-Running of Trades
« Reply #8 on: July 26, 2014, 09:49:10 pm »
That miner is heavily incentive to replace every transaction he sees with a transaction of his own that buys 1/2 as much.
No, he isn't. He has to start hashing each individual transaction for 10 minutes. By then, someone will have found a block containing the original transactions.
Nullius In Verba

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Front-Running of Trades
« Reply #9 on: July 26, 2014, 10:05:42 pm »
My laptop does about 2 Megahashes per second https://en.bitcoin.it/wiki/Mining_hardware_comparison#ASIC
ASIC mining equipment does about 1,000,000 per second.

1 second of work for the miner= 1 month for my CPU.

If a block is 10 minutes, I need to be at least 3 blocks ahead... I would need to mine for 1800 months to be secure from this type of attack.

Getting 10 units of mining power for 10 minutes costs exactly the same as getting 100 units of mining power for 1 minute. This service is becoming perfectly liquid.
« Last Edit: July 26, 2014, 10:22:49 pm by zack »

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Front-Running of Trades
« Reply #10 on: July 26, 2014, 10:08:06 pm »
Using a separate time-stamp service, it would be easy to prove that someone front-ran you.
truthcoin holders would vote to keep blocks only from people who don't front-run.

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Front-Running of Trades
« Reply #11 on: July 27, 2014, 12:47:56 am »
Again, you aren't reading what I've written.

I address ASIC's. You can change the tx-hashing algo all you want, there is far less of a need for consistency (as there is in the block-PoW). I also suggested a brokerage firm.

Read!
Nullius In Verba

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Front-Running of Trades
« Reply #12 on: July 27, 2014, 04:27:59 am »
we need something that is more expensive for members of one group than the other

Getting 10 units of mining power for 10 minutes costs exactly the same as getting 100 units of mining power for 1 minute. This service is becoming perfectly liquid.

POW to protect information ownership is no good, because it costs the same for both groups. The POW costs for the attacker are equal to the POW costs for the trader with insider knowledge.
« Last Edit: July 27, 2014, 07:41:23 am by zack »

psztorc

  • Administrator
  • Sr. Member
  • *****
  • Posts: 464
    • View Profile
Re: Front-Running of Trades
« Reply #13 on: July 27, 2014, 04:27:50 pm »
Lets say I build a tx "Buy 2 shares of cx687c.. for 5 TRU, send to 1M5duu.., nonce: 1", and I take this month's hashing algo, X11, and hash my tx with different nonces until it is below a target. This hashing activity cost me 10 minutes of time and $0.50 worth of power.

Then I publish the transaction, and wait for it to be included in a block.

Next month, the new tx-algo will be GOST, as deterministically calculated from something boring, like hash( sum( block hashes) ).

How do you propose to front-run my transaction (getting yours into a block before mine) by only paying $0.50?
« Last Edit: July 27, 2014, 04:50:41 pm by psztorc »
Nullius In Verba

zack

  • Global Moderator
  • Sr. Member
  • *****
  • Posts: 384
    • View Profile
Re: Front-Running of Trades
« Reply #14 on: July 27, 2014, 06:40:46 pm »
$0.50 gets you the same amount of hashes. If you spend it in one second, or if you spend it over a period of 10 minutes, $0.50 of hashes is the same amount of hashes.

If I was a miner, I would front-run every interesting looking transaction. If you revealed information that was protected by $0.50, I would spend that $0.50 so that I could front-run you.
Whoever mines the block can completely control front-running.

The net effect of the $0.50 fee that everyone has to pay: much lower trading volume. The $0.50 fee has a huge cost to the truthcoin network, and zero benefit.

My POS method does not have this short-coming.
In my method, miners would be competing to produce blocks which most increase the value of a truthcoin.
Rewarding shareholders is important, if you want to get investors.