Jump to content
Eik

Front-running (?) and other questions

Recommended Posts

On 4/14/2017 at 2:50 PM, tulo said:

This was a doubt I have. If the transaction arrives to the server, then it is put on the open ledger, and after that a lot of transactions with higher cost arrive (in the same open ledger time frame), the transaction to front run can be queued afterward or it's over?

Transactions in the same ledger always execute for real in "canonical" order, which is deterministic but hard to predict.

When submitted live to the network, transactions can execute in any number of orders, but if the fees are sufficient, they'll execute in the order in which they are received. This means that servers will temporarily disagree on their consequences.

For example, suppose I send a payment transaction with a sufficient fee to get in the open ledger. Regardless of whether the payment can be made successfully or not, the transaction will get in the ledger. Whether it successfully delivers funds or not, however, can depend on what transactions execute before it in canonical order.

The same is true of offers. You can check the current state of the open ledger and submit an offer based on it. But your offer might not even get into the same ledger you checked, and even if it does, the transactions in that ledger will likely execute in a different sequence. It is generally unwise to expect your transaction to execute with the ledger in any specific state. Instead, craft your transaction so that it gives you the results you want regardless of the ledger state. If the state changes too drastically, let your transaction fail and you can resubmit it.

Share this post


Link to post
Share on other sites

Also, just a clarification on Eik's post regarding trying to pack transactions into the same ledger so that one of them executes before the transaction you're front-running:

It doesn't help to send multiple transactions from a single address. As I recall, if a sender has multiple transactions with different sequence numbers in a ledger, everything past the first gets bumped to the end of the canonical order (and then sorted by sequence). If the transactions have the same sequence number, you have no control which one makes it into the ledger (and it increases the chance that none of them will) so you're not increasing your chances that you'll get one in before the targeted transaction.

You could do the same thing with separate sending addresses for each transaction without encountering this issue, but:

- it becomes harder to make sure that only one of them succeeds

- you're on the hook for funding the reserve of that many more accounts

Share this post


Link to post
Share on other sites
2 minutes ago, mDuo13 said:

As I recall, if a sender has multiple transactions with different sequence numbers in a ledger, everything past the first gets bumped to the end of the canonical order (and then sorted by sequence).

What is canonical order? Do you mean that all the transactions of one account are treated as one in the ordering and then executed in sequence. So let's say there are 5 transactions of 5 different accounts and 10 transactions of my account. It's like having 6 transactions, which are ordered and when it's the turn of my transaction pack, all 10 transactions are executed in sequence?

Share this post


Link to post
Share on other sites
Just now, tulo said:

What is canonical order? Do you mean that all the transactions of one account are treated as one in the ordering and then executed in sequence. So let's say there are 5 transactions of 5 different accounts and 10 transactions of my account. It's like having 6 transactions, which are ordered and when it's the turn of my transaction pack, all 10 transactions are executed in sequence?

The "canonical order" is the order the transactions are executed in, when a ledger closes. (Transactions are always executed in canonical order in closed and validated ledgers. In the open ledger, transactions are executed in the order they arrived instead. This is why transactions that tentatively failed can succeed and vice versa.)

So if the transactions that make it into a ledger are 5 transactions from different accounts and 6 transactions from tulo, the canonical ordering is something like this:

  1. Take tulo's first transaction (by sequence number) and add it to the 5 transactions from different accounts
  2. Sort this set by transaction hash
  3. Start at a pseudo-random point in this set, using the final contents of the ledger as the seed value so everyone picks the same pseudo-random value
  4. Execute the transactions in order from the chosen starting point, looping around to the beginning until you've executed all the transactions in this set
  5. Now sort tulo's remaining transactions and sort them by sequence number
  6. Execute those transactions in order from lowest sequence to highest

Maybe it would make more sense to visualize it like this:

Transactions in the ledger:

  • a, b, c, d, e, t1, t2, t3, t4, t5, t6

Set of transactions to be executed first:

  • a, b, c, d, e, t1

Set of transactions, ordered according to a random starting point (for example, d):

  • d, e, t1, a, b, c

Tulo's remaining transactions:

  • t2, t3, t4, t5, t6

Canonical order:

  • d, e, t1, a, b, c, t2, t3, t4, t5, t6

Share this post


Link to post
Share on other sites
2 minutes ago, mDuo13 said:

Canonical order:

  • d, e, t1, a, b, c, t2, t3, t4, t5, t6

Really?

I'd expect at least something like:

  • d, e, t1,t2, t3, t4, t5, t6, a, b, c

and still it would be pretty strange.

So if an account sends more transactions, the first has a chance to arrive first, but all the others will be the last? And what if more than one account has more transactions in a ledger?

Share this post


Link to post
Share on other sites

@mDuo13, thanks for the explanation! It is clear that the described method does not successfully do front-running with just one wallet. But,

14 hours ago, mDuo13 said:

The "canonical order" is the order the transactions are executed in, when a ledger closes. (Transactions are always executed in canonical order in closed and validated ledgers. In the open ledger, transactions are executed in the order they arrived instead. This is why transactions that tentatively failed can succeed and vice versa.)

So if the transactions that make it into a ledger are 5 transactions from different accounts and 6 transactions from tulo, the canonical ordering is something like this:

  1. Take tulo's first transaction (by sequence number) and add it to the 5 transactions from different accounts
  2. Sort this set by transaction hash
  3. Start at a pseudo-random point in this set, using the final contents of the ledger as the seed value so everyone picks the same pseudo-random value
  4. Execute the transactions in order from the chosen starting point, looping around to the beginning until you've executed all the transactions in this set
  5. Now sort tulo's remaining transactions and sort them by sequence number
  6. Execute those transactions in order from lowest sequence to highest

[...]

doesn't this leave options to still do front-running the old fashioned way? I.e. transaction hash 'mining'.

Say from all transaction in the open ledger {A, B, C, D, E}, transaction D is the one you want to front-run with a buy transaction and a sell transaction. You create two transactions, say T1_buy, and T2_sell from two different wallets of which you make sure that the transaction hash is just below the transaction hash of D by brute-forcing ('mining') a good hash.
This will bring the transaction order in point 2 to {A, B, C, T1_buy, T2_sell, D, E}
The starting point chosen in point 3 will be pseudo-random between 1-7.
The front-running will only fail if the starting point is chosen to be 5 (starting at T2_sell) or 6 (starting at D), but all other chosen starting points will yield a successful front-running. E.g. starting point 7 yields {E, A, B, C, T1_buy, T2_sell, D}.
You can increase your chances by spamming the open ledger with meaningless transactions all from different wallets. E.g. if you fill it up until transaction Z (28 transaction in total), you will have a 2/28 chance the front-running fails, 26/28 chance the front-running succeeds.

I.e. why is in point 3 only the starting point chosen pseudo-randomly and in point 4 cycled in order? Why not reorder the entire set pseudo-randomly and execute them in that order?

 

 

Edited by Eik
@ tag

Share this post


Link to post
Share on other sites

I see now that in your example you did not do the ordering on transaction hash, but you take the first-come first-serve order. This is not likely to be correct, right? (because different servers have different orders in which transactions are received)

Share this post


Link to post
Share on other sites

Looking at transaction hashes and TransactionIndex in recent ledgers using e.g. Data API v2 Tool, we can easily see that the entire execution ordering is (pseudo-)random, and not in a cyclic ordered loop, starting at a pseudo random point as suggested by @mDuo13.

Example ledger (Transaction hash  - Transaction index)
06DA... - 30
08E3... - 3
11E3... - 15
13CF... - 42
14FE... - 13
160A... - 23
1FEB... - 11
...

I guess that shows for sure now that front-running by working the transaction hashes is indeed not possible anymore.

I am relieved that I can't think of more ways that front-running can be performed :)

 

Share this post


Link to post
Share on other sites
1 hour ago, Professor Hantzen said:

Just run an exchange ;)

Lol, yeah there tons of ways to make some dirty profit in crypto-land.

I am just happy RCL is (/became) a more rigid/integrous system. I had the feeling front-running not only allowed some quick buck for some people, but mainly that it would disrupt RCL in other ways.

Share this post


Link to post
Share on other sites

The codes related to transaction ordering: https://github.com/ripple/rippled/blob/master/src/ripple/app/misc/CanonicalTXSet.cpp#L78-L98

in human language, the ordering is determined by:

  1. calculate the "random" seed. (hash of transaction-set)
  2. each account is XOR with the seed. (let's call the XOR result "accountkey")
  3. sort all the transactions according to:
    1.  "accountKey",
    2. Sequence,
    3. Transation_ID.

As we can see, randomization (XOR) only applied on account, not sequence, nor txn_id...
that means, txns from same account are always executed in ascending Sequence, consecutively.

For example, let's say account-A, and account-B had each submitted three txns into a ledger, (A1, A2, A3, B1, B2, B3), and we had other txns from accounts C, D, E.
and say after the randomization, ordering of accounts looks like: B, D, E, A, C.

Then the canonical set of transaction will be: B1, B2, B3, D, E, A1, A2, A3, C.

 

 

 

Share this post


Link to post
Share on other sites

Success rate of front-running will be high, if you had enough capital to send txns from several accounts.

For e.g. if you are operating with 4 accounts, and all of them able to send a set of front-running-txns into the same ledge, then you will have an 80% chances of success.

Edited by ripplerm

Share this post


Link to post
Share on other sites
17 minutes ago, ripplerm said:

As we can see, randomization (XOR) only applied on account, not sequence, nor txn_id...
that means, txns from same account are always executed in ascending Sequence, consecutively.

No!?! Plot twist! :o:aggressive:

Edited by Eik

Share this post


Link to post
Share on other sites
1 hour ago, ripplerm said:

The codes related to transaction ordering: https://github.com/ripple/rippled/blob/master/src/ripple/app/misc/CanonicalTXSet.cpp#L78-L98

in human language, the ordering is determined by:

  1. calculate the "random" seed. (hash of transaction-set)
  2. each account is XOR with the seed. (let's call the XOR result "accountkey")
  3. sort all the transactions according to:
    1.  "accountKey",
    2. Sequence,
    3. Transation_ID.

As we can see, randomization (XOR) only applied on account, not sequence, nor txn_id...
that means, txns from same account are always executed in ascending Sequence, consecutively.

For example, let's say account-A, and account-B had each submitted three txns into a ledger, (A1, A2, A3, B1, B2, B3), and we had other txns from accounts C, D, E.
and say after the randomization, ordering of accounts looks like: B, D, E, A, C.

Then the canonical set of transaction will be: B1, B2, B3, D, E, A1, A2, A3, C.

Ok, that's what I thought...thanks.

And do the HASH of transactions are random, or there is a higher chance of some values? Because otherwise one could "mine" account addresses that have an higher probability of low values being XORed with the hash seed.

Edited by tulo

Share this post


Link to post
Share on other sites

I couldn't interpret the rippled code that @ripplerm was linking to, but a complete look at a recent ledger (instead of a very quick partial one I did before), confirms this ordering:

ledger_ordering.thumb.png.e826c914df974e66343be28eba25ab3f.png

I assume this was an honest mistake of @mDuo13? Or was the silence of the last days in this topic because it was known to be wrong? This ordering indeed leaves options open to do front-running, at least 50% chance using one wallet. Keeping my original question: "Why not reorder the entire set pseudo-randomly and execute them in that order?". Is there an rippled optimization reason why you would want to cluster all orders of one account together? @JoelKatz@nikb

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...