Jump to content
riptidel

When are New Offers "Applied"?

Recommended Posts

Posted (edited)

Greetings fellow XRP'rs! I am currently expanding Offer support in Wipple and am investigating arbitrage and market maker analysis. While I have the basic logic to retrieve and track orders, one particular edge case I'd like to explore is for those engaged in HFT (high-frequency-trading), where orders need to be acted up near-instantaneously, as soon as they are received. Of course the most optimal way to do this would be to embed logic into rippled itself (either the core application or via a plugin) but for our purposes lets assume we are running against an unmodified rippled server, and our client is subscribing to the websocket streams.

As we all know, ledgers are closed every few seconds and after some time validated by the network when concensus is achieved. Before a ledger is closed, validators receive and propagate transactions so that at the time of closure, we have our unique transaction set, which the network can then validate. Transactions modify accounts and their corresponding balances, and the end result winds up as the official ledger for that period.

Now according to the offer lifecycle OfferCreate transactions automatically consume matching / crossing offers when they are "processed". My question is when do this processing occur? If I send an OfferCreate transaction to a validator, I'm assuming that it must propogate this transaction to other validators to be included in a closed ledger before it can do the matching analysis. Thus Offers are not applied until after a ledger is closed correct? Once closed but before (or should I say "during") validation, does rippled analyze the outstanding offers, attempt to match them and then write the final account balances and outstanding offers as the validated ledger? I'm assuming this means that some offers included in a closed ledger can be modified and/or dropped all together from a validated ledger correct? (if the offer is partially or completely filled for example, or perhaps cancelled in the same ledger).

All in all I'm trying to establish when it is best to subscribe to and process offers. If one were to engage in HFT, it seems best to intercept the offers as they are being propagated across the network, before the ledger is closed and offer analysis begins. Outside of modifying rippled to do so as discussed above, we can subscribe to the 'transactions' or 'transactions_proposed' streams to be notified of offers included in closed ledgers, even though ultimately these offers may be automatically matched and may not appear in the validated ledger (and thus without doing the matchmaking analysis ourselves, are rather moot). Of course we can wait until the validated ledger is issued, but by this point it may be too late as other clients may have analyzed the Offers at one of the aforementioned points and issued their own matching offer before we have a chance to issue ours.

Thanks in advance for any insights or thoughts WRT the tradeoffs to monitor offers at various points of the ledger lifecycle.

Edited by riptidel

Share this post


Link to post
Share on other sites

And as a quick followup, does anyone know of any drive to include a 'plugin' framework in rippled? I'm not talking about amendments affecting the protocol per-se, but rather specific hooks / callbacks one could leverage to include analysis logic directly in the rippled process. There'd be no faster way to do this HFT than simply dispatching to custom in-memory logic in rippled itself (afterall if there is a market opportunity, someone is bound to do this in proprietary forks if not included in the 'official' rippled server!)

Share this post


Link to post
Share on other sites

Offers are "processed" (executed) when a ledger closes¹; however, the outcome is not final unless the ledger is validated. You may have a candidate ledger N in which Offer A executes before Offer B, but a competing candidate ledger N´ may have a slightly different transaction set with a completely different canonical ordering where Offer B executes first. If Offers A and B are mutually exclusive, you don't know which one will succeed until you know if N or N´ is validated.

I should add, the XRP Ledger is not ideal for HFT because there's an overall latency of 3-7 seconds for a new ledger to become finalized. The order in which new transactions (offers) execute when they're in the same ledger is intended to be arbitrary and unpredictable, so you don't get a benefit for being faster (as high-frequency traders typically do in most other markets). Which is not to say HFT is pointless, since you can still have a chance of taking a juicy offer the moment it appears. (Either by getting into the same ledger a target offer is created and being lucky enough to be after it but before your competing offers, or if nobody does that, then by getting into the following ledger as early as possible.)

Also, I'm not familiar with any push to add a plugin architecture to rippled.

 

¹Transactions, including offers, are also tentatively processed immediately when they're included in an open "current" ledger, in the order they're received. The results of such processing are tentative, but not final—they're usually right if no mutually-exclusive transactions are received in the same ledger as long as the transaction doesn't fail to be included in the next validated ledger (for example because it was so close to the end of the window between this ledger and the next one that some servers let it in this ledger and others put it off for the next).

Share this post


Link to post
Share on other sites
On 5/31/2018 at 12:04 AM, riptidel said:

one particular edge case I'd like to explore is for those engaged in HFT (high-frequency-trading),

Oh, I'd love to see you race @donch's bots. :D 

 

Share this post


Link to post
Share on other sites
Posted (edited)
6 hours ago, mDuo13 said:

Offers are "processed" (executed) when a ledger closes¹; however, the outcome is not final unless the ledger is validated. You may have a candidate ledger N in which Offer A executes before Offer B, but a competing candidate ledger N´ may have a slightly different transaction set with a completely different canonical ordering where Offer B executes first. If Offers A and B are mutually exclusive, you don't know which one will succeed until you know if N or N´ is validated.

Cool, thanks for the reply @mDuo13 . This is what I figured, though the bit about processing transactions against the open "current" ledger immediately is new to me. From what I understand now, validated ledgers are the true canonical source of which offers were executed and which ones are outstanding. Both Open and Closed ledgers can be used to analyze and predict Order Books and matched orders, with the understanding that these predictions may be wrong, as the network may reach a consensus that is different than the prediction if an alternate ledger is validated (especially in the case of the "open" ledger as new offers may arrive at any point)

 

 

Quote

I should add, the XRP Ledger is not ideal for HFT because there's an overall latency of 3-7 seconds for a new ledger to become finalized. The order in which new transactions (offers) execute when they're in the same ledger is intended to be arbitrary and unpredictable, so you don't get a benefit for being faster (as high-frequency traders typically do in most other markets).

This bit about "arbitrary and unpredictable" ordering is interesting, any way you could elaborate? I thought rippled employed logic to ensure transactions were processed in the order the were received, eg to solve the double spending problem. Is this not the case? Or perhaps it's the case for payments but not offers?

In any case, I love this, another reason I'm a fan of the XRP token / network. It really levels the playing field for the "average joe" trader who may not have the resources a hedge fund does to analyze and jump on offers. Take that anyone who says XRP is not decentralized & for the masses!!!

 

Quote

Which is not to say HFT is pointless, since you can still have a chance of taking a juicy offer the moment it appears. (Either by getting into the same ledger a target offer is created and being lucky enough to be after it but before your competing offers, or if nobody does that, then by getting into the following ledger as early as possible.)

 

Also, I'm not familiar with any push to add a plugin architecture to rippled.

Heh I would offer my services and apply for a job at ripple to work on such a thing but just left a long stint coding for a major tech corp, and am not just ready yet to jump back into the job market! Still exploring topics of interest independently (including the awesomeness of XRP!) 😄

 

Thanks again for the response!

 

Edited by riptidel

Share this post


Link to post
Share on other sites
Posted (edited)
5 hours ago, Graine said:

Oh, I'd love to see you race @donch's bots. :D 

 

Intriguing, I'd love to find out more how they work (care to share secrets @donch ? 😄 )

 

In any case I'm not planning on jumping into HFT, Arbitrage, Market Making, per-se. They are interesting topics but there are many other and I need to pick and choose carefully! More-so looking at this for an analysis perspective, I'd like to understand what opportunities XRP affords, and how various parties can leverage them for various purposes (will keep publishing findings here and via wipple). Again, much obliged for the insights, they help alot!

Edited by riptidel

Share this post


Link to post
Share on other sites
On 5/31/2018 at 10:16 PM, riptidel said:

Both Open and Closed ledgers can be used to analyze and predict Order Books and matched orders, with the understanding that these predictions may be wrong, as the network may reach a consensus that is different than the prediction if an alternate ledger is validated (especially in the case of the "open" ledger as new offers may arrive at any point)

Correct.

 

On 5/31/2018 at 10:16 PM, riptidel said:

This bit about "arbitrary and unpredictable" ordering is interesting, any way you could elaborate? I thought rippled employed logic to ensure transactions were processed in the order the were received, eg to solve the double spending problem. Is this not the case? Or perhaps it's the case for payments but not offers?

rippled / the XRP Ledger does not ensure transactions (of any type) are processed in the order they are received. Doing that is not necessary to solve the double spend problem. To solve the double-spend problem, you must only ensure that every participant agrees on the order in which transactions execute and consequently what their outcomes are. In fact, a big part of the double spend problem is that different parties have different perspectives on the order in which transactions were received.

For the most part, transactions are processed in the next ledger after they're received, with transactions that get into the same ledger being more or less randomly ordered. (It's deterministic, but hard to predict; and also, transactions from the same sender are relatively ordered by increasing sequence number.) The exact canonical ordering code is kind of complicated. You can see some discussion in this GitHub issue. Maybe an example would make this clearer:

 

Suppose Alanis, Beethoven, Ciu, and Deepak each have XRP Ledger accounts and are sending transactions that arrive around the same time. Consensus approves a set of transactions that includes (in no particular order):

  • A1, A2, and A3 sent by Alanis, where A1 is Alanis's lowest sequence transaction and the others are one sequence number higher each
  • B1 and B2 sent by Beethoven, where B1 is Beethoven's lowest sequence number
  • C1, C2, C3, C4, and C5 sent by Ciu, again ordered by increasing sequence number
  • D1 sent by Deepak.

One possible canonical ordering for this set could be:

  1. D1
  2. B1
  3. B2
  4. A1, A2
  5. C1, C2, C3, C4, C5
  6. A3

First, the ordering of accounts is set based on some unpredictable hash (to be honest I don't know exactly how this works). Then all transactions by those accounts are attempted in sequence order. Some transactions may fail but are retriable. (For example, A3 attempted to spend money that isn't received until C4 is processed.) Then retriable transactions are processed.

 

Share this post


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

First, the ordering of accounts is set based on some unpredictable hash (to be honest I don't know exactly how this works).

Something along the lines of:
Take all 11 transactions that should be applied currently
Sort them
Hash them (so everyone with those same 11 transactions will come to the same hash)
Take a PRNG algorithm and use the hash calculated above as the seed
Use that seeded algorithm to determine which account comes first, which second etc.

This leads to an ordering that's dependent on both the content of transactions (which include signatures, wich include a lot of entropy hopefully) as well as the subset of transactions itself (so if Deepak's second transaction makes it to only one validator in time to be evaluated, it'll come to a completely different ordering because it'll look at 12 transactions and will quickly have to change its mind).

Not verified with the actual code, just what I remember from the discussions about the issues with being able to "mine" transactions before this was implemented. Nik or David probably can explain it better.

Share this post


Link to post
Share on other sites

×