Front-Running of Trades

[psztorc]

You didn't answer my question.

$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.

You are saying that, were I rich enough to perform "1 + the number of hashes that Bitcoin miners have performed so far" over any length of time, say 10 years, I would therefore also be rich enough to build a separate and longer chain in one second? ..or one nanosecond? Can you prove this extreme claim with citations or elaboration? It sounds nonsensical and physically impossible...electricity and heat-diffusion have speed-limits.

[zack]

It is because scales are different.
Locally, if you zoom in a whole lot to the order of $10 of hashes and a time scale of 1 minute----------------------- (10 minutes is fast enough to catch 50% in a front-runner attack. 1 minute catches more than 90% I estimate (it is an integral over a decreasing exponential))
The price of a hash is really liquid.
The bitcoin network is creating 78,000 petahashes every block. That is worth 25BTC=$15,000

So the price per petahash for SHA256-double is ~5 petahashes per dollar.
The largest mining pool creates 40% of all the petahashes in each block.
If you spend $10=~50 petahashes
To generate $10 of value takes $10*600seconds/$15000<0.5seconds
which is far less than 1 minute minimum, so they could front-run attack over 120 txs per block with over 99% success rate.
In less than the time it takes you to type up your tx, they have already front-ran it.

In the bigger picture, if you zoom out to the block reward size of $15,000 and time scale of 10 minutes-------------------------------------
now you want to buy enough hashes to out-run the entire bitcoin network. So you need more hashes per second than bitcoin has, in order to catch up.
But every computer is already mining bitcoin...
You would have to pay more than 1/2 of the miners to help you cheat. They wouldn't be willing to do it, it would hurt their savings, and their investments in bitcoin mining rigs.
The price per peta-hash is very illiquid at this scale.

I am really bad at explaining things.

[prometheus]

What zack is saying, is that there isn't really a way to tell how long it took someone to compute a POW using the POW algos that we know of. 10 minutes of hashing on a cheap PC is a fraction of a second of hashing on a professional mining rig. A miner can still copy the contents of incoming transactions, perform his own POW, and then include his own transaction rather than the ones people send to him.

[psztorc]

What zack is saying, is that there isn't really a way to tell how long it took someone to compute a POW using the POW algos that we know of. 10 minutes of hashing on a cheap PC is a fraction of a second of hashing on a professional mining rig. A miner can still copy the contents of incoming transactions, perform his own POW, and then include his own transaction rather than the ones people send to him.

It sounds that you are assuming that the tx-PoW would be the same as the Block-PoW (double-sha256)? Of course that would give miners an advantage in capital costs (although you can't hash blocks and tx at the same time, so it would still be costly for Miners to hash, as they are decreasing the liklihood that they will find a block).

As anyone who can scroll up can see...

Nodes could require CPU-intensive >10 minute proof of work.

...I was thinking that nodes would use a different tx-PoW, and even change the tx-PoW often, possibly by choosing it deterministically by taking the 8 or so listed here: http://en.wikipedia.org/wiki/Cryptographic_hash_functions

...and choosing 5 in a deterministic but pseudorandom order. This would have 8^5 = 32,768 possible hash functions (we could even choose 16 or 100). I don't understand computer engineering, but this seems to at least disrupt physical ASIC-creation. Unlike Bitcoin, which has no real benefit to change hashing algo, and constant upward attraction in the block-PoW-hashrate (as you are forced to improve if you, and someone must mine), this mechanism might permanently discourage front-running attempts (you can choose not to play, and no one needs to play). While ASICs are inevitable in block-PoW (where everyone must play and compete) they aren't in tx-PoW (where everyone can choose not to compete), and if ASICs were inevitable they might create perfectly competitive brokerage firms because mining is a nearly-perfectly-competitive industry.

It is disappointing that I have to keep repeating myself, in a written medium.

No one will even answer my direct question:

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?

[zack]

When you switch algorithms around like this a lot, you can force everyone to do CPU type mining.
This incentives the creation of botnets. Botnets would be the most effective way of mining CPU.

Every CPU mining rig can be used to mine every other CPU algorithm just as well, and regular computers are CPU mining rigs. So CPU hashing power is even MORE liquid than SHA-256 hashing power. If you have lots of money, Amazon Cloud will supply you with a very large amount of CPU at short notice. Many alt-coins are mined almost completely in the amazon cloud.

My father rents servers for people in the oil and gas industry. They have to do intense computations to find the oil.
These huge rigs can cost thousands in electricity to run, per day.

There are many industries that have huge computers lying idle for part of that day.
CPU is even more liquid than SHA-256.

It would be possible to spend $100 in under 20 seconds in our hyper-liquid market for CPU.
And it would buy you precisely as many hashes as $100 over 10 minutes.

[psztorc]

When you switch algorithms around like this a lot, you can force everyone to do CPU type mining.
This incentives the creation of botnets. Botnets would be the most effective way of mining CPU.

Every CPU mining rig can be used to mine every other CPU algorithm just as well, and regular computers are CPU mining rigs. So CPU hashing power is even MORE liquid than SHA-256 hashing power. If you have lots of money, Amazon Cloud will supply you with a very large amount of CPU at short notice. Many alt-coins are mined almost completely in the amazon cloud.

My father rents servers for people in the oil and gas industry. They have to do intense computations to find the oil.
These huge rigs can cost thousands in electricity to run, per day.

There are many industries that have huge computers lying idle for part of that day.
CPU is even more liquid than SHA-256.

It would be possible to spend $100 in under 20 seconds in our hyper-liquid market for CPU.
And it would buy you precisely as many hashes as $100 over 10 minutes.

I would rent the Amazon Cloud and use it to CPU mine every transaction and front-run all of them.

This, by definition, costs more for the attacker than the user, which is exactly what I was aiming for. The users can accumulate a small quantity of hashes nearly for free, using idle CPU time and power from an already-on PC, whereas the attacker is spending thousands. Or, the user can rent the Amazon Cloud themselves at high speed for 5 minutes, spending x. Then, releasing the tx, the attacker must hash for at least 5 minutes, or spend >x / <5 minutes to hash at higher-speed. Again, the attacker has outspent the user.

And only half of all trades will be winners (return-adjusted), why would you front-run all of them? You are renting the Amazon Cloud just to generate an expected return of zero. The total revenue is bounded, but the costs of PoW are not. What if users submit billions of tx's for you to front run? It will cost billions of $ and generate only the same small amount of revenue.

If you only front-run a subset of transactions, you had better try to keep your choices secret. Those who learn your front-running tx-selection-method (your employees, competitors who want to be better at front running that you are, market technicians), will definitely release 'fake' transactions for you to front-run, which will not only consume hashing resources but also result in a losing trade going through. Your own employees have an incentive to work 9 to 5, then go home and drag the algo into an unjustified price, just to themselves make a trade restoring the price to its pre-drag value. This generates a return for them and a cost to you.

[zack]

Using your home PC to mine would cost 10x as much in electricity using the amazon cloud. Big servers are a lot more cost effective for cycles per watt than desktops. Cell phones are incapable of POW, since the battery just dies.

Assuming the attacker and defender are spending money as optimally as possible, it costs precisely the same for both of them. It doesn't matter if they spend the money over 10 minutes, or over 5 seconds, they get the same number of hashes.

CPU is MORE LIQUID than SHA-256. It suffers from the same problem, but worse.

Since a miner finds blocks at random, there is no way for the miner or anyone else to predict which blocks will be front-ran, and which ones will not. If you wrote tx in the hopes that they get front-ran, you will probably end up buying shares that you didn't want.

Charging everyone $5 per tx is prohibitively expensive, and there is no benefit to it. It is identical to requiring burning of $5 of truthcoin to send a tx.
Bitcoin fee is $0.06 for comparison.

[zack]

I emailed Vitalik Buterin. His response:
"What you want is a two-step commit protocol. Step 1, you publish a
transaction containing only a hash of the actual order. Step 2, you
publish the order. Orders are only valid if preceded by their hash 6
blocks ago. Assuming a fast block time (eg. 20s as in ethereum starting
PoC6), and that the miners are not all colluding, this basically solves
the problem."

I think he is correct. We need a mandatory waiting period of several blocks.
It is WAY simpler than building the POS thing, and it would actually solve the problem.

[psztorc]

Using your home PC to mine would cost 10x as much in electricity using the amazon cloud. Big servers are a lot more cost effective for cycles per watt than desktops. Cell phones are incapable of POW, since the battery just dies.
I wouldn't mind tx-front-running on the Amazon cloud, because it only costs me 1/10th of what it would cost me if I tried to do this at home.

Assuming the attacker and defender are spending money as optimally as possible, it costs precisely the same for both of them. It doesn't matter if they spend the money over 10 minutes, or over 5 seconds, they get the same number of hashes.
Front running is still possible, because I can tx-hash in 5 seconds and rebroadcast the tx quickly.

CPU is MORE LIQUID than SHA-256. It suffers from the same problem, but worse.

Since a miner finds blocks at random, there is no way for the miner or anyone else to predict which blocks will be front-ran, and which ones will not. If you wrote tx in the hopes that they get front-ran, you will probably end up buying shares that you didn't want.

Charging everyone $5 per tx is prohibitively expensive, and there is no benefit to it. It is identical to requiring burning of $5 of truthcoin to send a tx.
Bitcoin fee is $0.06 for comparison.

How does that change anything? You still have to buy Amazon Cloud services, to get the tx 5 seconds later. You aren't certain that your tx will replace the original in the next block, and you aren't sure that the trade is a winner.

[psztorc]

Step 1, you publish a transaction containing only a hash of the actual order. Step 2, you publish the order. Orders are only valid if preceded by their hash 6 blocks ago. Assuming a fast block time (eg. 20s as in ethereum starting PoC6), and that the miners are not all colluding, this basically solves the problem."

This is one solution, but it suffers from a number of problems, which lead me to save it for a last resort. Firstly, tx are limited to 1 per block, which in this case would be 1 per 10 minutes, which is very slow (eliminating the benefits of SIB). Also, failed trades are all included as hashes, which bloats the blockchain. For an obvious arbitrage trade, at a certain block everyone would see that a price of 5 should become a price of 6, but no one would yet know if someone submitted a trade doing that, so in the 10 minutes between everyone would be submitting 5 -> 6 trades, only one of which would ultimately go through.

So this isn't ideal. I would probably be more likely to do nothing and just allow people to attempt to front-run (for the time being).

[psztorc]

Some other comments:
1) I'm only worried about replacement front-running, not the kind which exploits limit orders (like from the 80's). The tx I had in mind for Truthcoin are like Bitcoin transactions, a movement from here to here with a predefined cost, either valid or invalid. So if XY trades for 4.70 and someone says "Buy XY $4.7 -> $5", there's not necessarily anything to be gained by sneaking in "Buy XY $4.7 -> $4.9", because that would invalidate the $5 transaction. You could say "I bet that transaction will reappear as $4.9 -> $5, but maybe it won't.

2) Noise trades (trades made by someone with no information about the underlying) have been shown to have no adverse effects (and actually some helpful effects). Front-runner-trades are almost noise trades, but they aren't. The front-runner does have some information about the underlying: the trade that they observed and are choosing to front-run. To what extent does this count as information? If x percent of traders are uninformed, perfect-front-running will of course also be noise-trading x percent of the time, but front-runners don't know who they are getting. Does this matter?

3) To produce profitable front-running activities, one would need a reliable strategy. Whereas with centralized services the strategy is simply: get the info earlier, use the info faster, and be closer to the center, with decentralized service I'm not exactly sure the technical details of how one would ensure that their trades replaced those of someone else. It seems clear that, if one could reliably find blocks, one would be able to front-run all the buy/sell orders in a block. But the ability to find blocks is itself a full-time job, under immense competition and likelihood for replacement. Also, if you did find a fr-strategy, others might copy it, diluting the likelihood of the strategy being profitable.

4) Individual miners may attempt to front-run, but I would expect Miners as a group to be anti-front-running, as they want to increase the value of their coins. Mining is perfectly competitive, though, so what economic logic is being employed by miners, I have no idea.

5) It seems that one would need to run a full node to front-run, or at least assemble blocks for timestamping. So at least this may encourage front-running.

6) Sometimes, two people will just create a similar tx at a similar time. One one will win through, more or less randomly, and this is OK.

7) The key to preventing front-running is time. If nodes accept transactions on a first-come-first-serve basis (obviously they would), attackers must then rewrite the transaction and broadcast it to their connections faster than the initial transaction (which of course they wouldn't broadcast) goes around the network. This is why I propose throwing a small PoW problem in front of each buy/sell tx, to delay it by a few seconds or more so that the original can propagate, although zack and others have argued that this won't work because it takes electrical power to run a home PC and that everyone can use Amazon supercomputers for free to instantly solve the PoW, and CPUs are liquid and stuff like that.

Finally: Someone with more relevant skills, in network synchronization or crypto or physics, might think of a better solution later. My current thought is to just ignore this until it becomes a problem (which might be 'never', anyway).

[psztorc]

Satoshi seems to believe that, under certain conditions (incl. a payment processing company connected to many nodes) as little as a 1 second delay can be pivotal in allowing someone to purchase quickly with vanishing risk of double-spend (similar to the front-run problem of this thread).

I'm not sure if that's helpful, other than to say that 1 second can be enough.

It seems that the PoW tie-breaking rule could be abused, as within-block there is no real way to tell 5-milliseconds ago (front run by being quick) from 5 seconds ago (front run by abusing PoW-rule). It would have to be a flat requirement, with the branch setting the flat-level?

[zack]

Sorry it took me so long to understand you Paul.
I see how it stops frontrunners, and why this matters.
I will add a proof of work to the buy_shares transaction type.
How many seconds of work on my CORE i5 laptop is a good POW 2 minutes?

[psztorc]

20 seconds sounds good....the key is that it must be impractical for anyone to do as much work in 1 second. So attacker would see a tx, send it to AWS or something, quickly supercompute the 20-second hash, and then broadcast their front-run. This at least costs them the AWS-fees and has some chance of failure.

Not sure if this is practical, but nodes could also watch other nodes for suspicious behavior (how about "cumulative change in %-agreement-about-next-block-contents upon receiving a new tx"), and start relaying new tx to them last.

[zack]

I added this feature. https://github.com/zack-bitcoin/Truthcoin-POW
functions changed for this are truth_cli.build_buy_shares() and txs_truthcoin.buy_shares_check()