Author Topic: Ripple goes from adjacent-possible to REAL.  (Read 5620 times)

0 Members and 1 Guest are viewing this topic.

Offline alexkravets

  • Full Member
  • ***
  • Posts: 81
    • View Profile
More detailed specifications and English explanations of path finding weather client-specified or server-provided is here https://wiki.ripple.com/Payment_paths

Thanks. So reading that I conclude the path finding is actually what I would call "client-determined", which of course is what makes the most sense. To me server-determined would be the Ripple nodes trying to solve the problem between ledger closes, which would be a computationally demanding process. It makes far more sense for the entity interested in such a transaction (or another entity helping them out) to solve the path finding problem with the most recent state of the ledger, then crafting the transaction (with appropriate limits on conversion costs) to submit to the network. I still call it "client-determined" even when the light client delegates that task to one or more servers with full access to the most recent database and then chooses the best result.


Indeed it is a computationally demanding process, but it IS currently performed by rippled instances when the clients (in Ripple this means currently web-based ripple-lib clients that signed the transaction and then relayed it to one of the servers (rippled instances)) which is a default when the transaction is a payment that attempts to pay using USD to a recipient who prefers, say, BTC or JPY.  THIS used to be the major advertized feature of Ripple, i.e. its "babel-fish of money" instant cross currency payments which would allow you to pay in, say Peso's to a merchant that wanted Yen. 

Quote
Within a single ledger context the transactions are ordered by impossible-to-know-ahead-of-time-yet-fully-deterministic algorithm:
lexicographic ordering based on the transaction hash.

To me this isn't quite good enough to satisfy the "impossible-to-know-ahead-of-time". A Ripple node has the opportunity to front run an order it has in its queue by adjusting a small insignificant parameter in the transaction such that its transaction hash lexicographically precedes the hash of the target transaction. It shouldn't be too hard to iterate this nonce to achieve this result before the ledger closes (in 50% of cases, there is a 50% chance or better of success for each iteration, meaning that for these 50% of cases after only 7 iterations there is a greater than 99% chance of obtaining the desired front running transaction).

Indeed, it possible to tweak some things within the binary representation to achieve a high or low lexicographic hash
(see https://ripple.com/build/transactions/#offercreate for possible fields to tweak) and such kind of jumping-the-queue might be viable except there is still uncertainty of propagation delays which might defer the transaction into the subsequent ledger, i.e. a rippled instance doesn't solve or sign a block, it basically shouts in a crowded room hoping that next validated ledger would included it but w/o a guarantee of such.

I would also like to direct your attention to the following upcoming big change to Ripple, It's called Offer Auto-bridging
https://ripple.com/introducing-offer-autobridging/  This change has been a maturing pull-request that's been reviewed for a while and it might make it into the next version real-soon-now https://github.com/ripple/rippled/pull/689

Auto-bridging extends Ripple's promise of payments or trading "at best available rates" it's quite a powerful mechanism.




Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
More detailed specifications and English explanations of path finding weather client-specified or server-provided is here https://wiki.ripple.com/Payment_paths

Thanks. So reading that I conclude the path finding is actually what I would call "client-determined", which of course is what makes the most sense. To me server-determined would be the Ripple nodes trying to solve the problem between ledger closes, which would be a computationally demanding process. It makes far more sense for the entity interested in such a transaction (or another entity helping them out) to solve the path finding problem with the most recent state of the ledger, then crafting the transaction (with appropriate limits on conversion costs) to submit to the network. I still call it "client-determined" even when the light client delegates that task to one or more servers with full access to the most recent database and then chooses the best result.

Within a single ledger context the transactions are ordered by impossible-to-know-ahead-of-time-yet-fully-deterministic algorithm:
lexicographic ordering based on the transaction hash.

To me this isn't quite good enough to satisfy the "impossible-to-know-ahead-of-time". A Ripple node has the opportunity to front run an order it has in its queue by adjusting a small insignificant parameter in the transaction such that its transaction hash lexicographically precedes the hash of the target transaction. It shouldn't be too hard to iterate this nonce to achieve this result before the ledger closes (in 50% of cases, there is a 50% chance or better of success for each iteration, meaning that for these 50% of cases after only 7 iterations there is a greater than 99% chance of obtaining the desired front running transaction).

Assuming we don't want to give up on limit orders to prevent front running (as BitShares currently does), there are a few solutions to this problem. One is to just include these market orders in one ledger close but only act on them in the very next ledger close. The order in which the market orders of the previous ledger are processed depends on the ledger hash of the previous closed ledger, for example lexicographical ordering based on hash(hash(transaction) || hash(previous ledger)). Since no one can know for sure what that hash of the closed ledger will be until the ledger has actually closed, no one can know for sure what order the submitted market orders will be processed, and thus there is a chance that the front running will not lead to guaranteed profits.

The other solution that I discuss here, is to separate these market orders into two stages: a commitment to the order and then the actual order that must be submitted within a specific narrow time interval after the commitment transaction. I prefer this solution more because the front runner doesn't have any information about what front running order to construct until it is too late. Thus any attempt at front running would really just be a shot in the dark, whereas with the previous solution they at least knew the transaction to craft that would give them some (albeit <50%) probability of success.

Offline alexkravets

  • Full Member
  • ***
  • Posts: 81
    • View Profile
I haven't gone into depth with Ripple. I looked through this (https://ripple.com/files/ripple_mm.pdf).
Section 7 briefly discusses the path finding algorithm. I haven't yet been able to find more details about it. Bitsapphire, you seem to know something about this. Can you point me to resources to read that discuss what Ripple is doing exactly?

More detailed specifications and English explanations of path finding weather client-specified or server-provided is here https://wiki.ripple.com/Payment_paths

Quote
By the way Rune, section 11 talks about the order queue. Based on my reading, it appears that it does have limit orders and doesn't really do anything to prevent front running. Someone please correct my if I am wrong. Section 10 tries to argue that because the servers are distributed it is actually a fairer situation than with traditional exchanges.
And I agree with this. But I wouldn't quite call it a "level playing field for all market participants" since I imagine there will still be some better connected servers that can get user's submitted transactions and quickly respond to it by crafting a transaction to front run the order.

This is correct.  All offers are limit offers and lack of a single solver or singer node is probably good enough to prevent vast majority of front running attacks, it's a bit like Nasdaq market makers, they can all see each others' Level 2 & 3 quotes but ultimately nobody really has the global view of the incoming client-supplied order flows so nobody really has the privileged position of a NYSE market maker

Quote
I don't know the details of how Ripple orders transactions in the same ledger (same timestamp), but I imagine it would require the front running server to quickly adjust some nonce in the transaction to ensure it comes ahead of the transaction it is trying to front run based on the deterministic ordering algorithm.

Within a single ledger context the transactions are ordered by impossible-to-know-ahead-of-time-yet-fully-deterministic algorithm:
lexicographic ordering based on the transaction hash.

Quote
Why hard code it? Let the client determine it. The client (not the blockchain) should determine the most efficient path to convert asset A into asset E. Maybe it chooses A -> B -> E or maybe A -> C -> D -> E is more efficient. Now at the time the order is actually being executed by the blockchain the chosen path may not be the most efficient one, but this is a good enough approximation that takes computational work off the validation servers. The client chooses the path based on the current order books then creates a transaction indicating the path to take, the E/A price limit it is willing to accept for the overall conversion process, and either a max quantity of asset A to convert from or a max quantity of asset E to convert to. The blockchain then receives this transaction and tries to carry out any fraction of it atomically (meaning it could do half of the order if it fits the price limit restriction and leave the other half for later when it can without violating the price limit restriction). Alternatively, the transaction could specify all-or-nothing, so that all of the transaction quantity needs to be fulfilled or the entire transaction does not go through. This could be useful if an extra operation is appended to the atomic transaction to then transfer the asset E to another party. That feature could then allow for example atomically paying someone 10 BitEUR by withdrawing as much as necessary from their balance of >0.0102 BitGold with a specified price limit of 980 BitEUR/BitGold, and using BitUSD as the intermediate asset (transaction crafted to atomically trade X BitGold of user A -> BitUSD -> 10 BitEUR of user B with a restriction that X <= 0.0102).

Ripple allows both client-specified and server solved path finding, see above link for details.

Offline Rune

  • Hero Member
  • *****
  • Posts: 1120
    • View Profile
Quote
Why hard code it? Let the client determine it. The client (not the blockchain) should determine the most efficient path to convert asset A into asset E. Maybe it chooses A -> B -> E or maybe A -> C -> D -> E is more efficient. Now at the time the order is actually being executed by the blockchain the chosen path may not be the most efficient one, but this is a good enough approximation that takes computational work off the validation servers. The client chooses the path based on the current order books then creates a transaction indicating the path to take, the E/A price limit it is willing to accept for the overall conversion process, and either a max quantity of asset A to convert from or a max quantity of asset E to convert to. The blockchain then receives this transaction and tries to carry out any fraction of it atomically (meaning it could do half of the order if it fits the price limit restriction and leave the other half for later when it can without violating the price limit restriction). Alternatively, the transaction could specify all-or-nothing, so that all of the transaction quantity needs to be fulfilled or the entire transaction does not go through. This could be useful if an extra operation is appended to the atomic transaction to then transfer the asset E to another party. That feature could then allow for example atomically paying someone 10 BitEUR by withdrawing as much as necessary from their balance of >0.0102 BitGold with a specified price limit of 980 BitEUR/BitGold, and using BitUSD as the intermediate asset (transaction crafted to atomically trade X BitGold of user A -> BitUSD -> 10 BitEUR of user B with a restriction that X <= 0.0102).

Having the client determine it is definitely a better option. But I'm convinced all liquidity will converge on pairs with the least volatile asset (most likely bitUSD) and thus we will end up in a situation where pathfinding isn't really necessary since the answer will always be X -> bitUSD -> Y. The only exception will be bitasset/BTS pairs which will all have high liquidity.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Maybe alexkravets can provide more details?

I haven't gone into depth with Ripple. I looked through this (https://ripple.com/files/ripple_mm.pdf).

Section 7 briefly discusses the path finding algorithm. I haven't yet been able to find more details about it. Bitsapphire, you seem to know something about this. Can you point me to resources to read that discuss what Ripple is doing exactly?

By the way Rune, section 11 talks about the order queue. Based on my reading, it appears that it does have limit orders and doesn't really do anything to prevent front running. Someone please correct my if I am wrong. Section 10 tries to argue that because the servers are distributed it is actually a fairer situation than with traditional exchanges. And I agree with this. But I wouldn't quite call it a "level playing field for all market participants" since I imagine there will still be some better connected servers that can get user's submitted transactions and quickly respond to it by crafting a transaction to front run the order. I don't know the details of how Ripple orders transactions in the same ledger (same timestamp), but I imagine it would require the front running server to quickly adjust some nonce in the transaction to ensure it comes ahead of the transaction it is trying to front run based on the deterministic ordering algorithm.

Tbh, if implementing a full pathfinding algorithm on our blockchain were too problematic in the beginning, I wouldn't even be oppossed to simply have bitUSD as a hardcoded global steiner point, because I think it would end up as that anyway (until the USD tanks that is).

Why hard code it? Let the client determine it. The client (not the blockchain) should determine the most efficient path to convert asset A into asset E. Maybe it chooses A -> B -> E or maybe A -> C -> D -> E is more efficient. Now at the time the order is actually being executed by the blockchain the chosen path may not be the most efficient one, but this is a good enough approximation that takes computational work off the validation servers. The client chooses the path based on the current order books then creates a transaction indicating the path to take, the E/A price limit it is willing to accept for the overall conversion process, and either a max quantity of asset A to convert from or a max quantity of asset E to convert to. The blockchain then receives this transaction and tries to carry out any fraction of it atomically (meaning it could do half of the order if it fits the price limit restriction and leave the other half for later when it can without violating the price limit restriction). Alternatively, the transaction could specify all-or-nothing, so that all of the transaction quantity needs to be fulfilled or the entire transaction does not go through. This could be useful if an extra operation is appended to the atomic transaction to then transfer the asset E to another party. That feature could then allow for example atomically paying someone 10 BitEUR by withdrawing as much as necessary from their balance of >0.0102 BitGold with a specified price limit of 980 BitEUR/BitGold, and using BitUSD as the intermediate asset (transaction crafted to atomically trade X BitGold of user A -> BitUSD -> 10 BitEUR of user B with a restriction that X <= 0.0102).
« Last Edit: December 21, 2014, 12:52:57 am by arhag »

Offline Rune

  • Hero Member
  • *****
  • Posts: 1120
    • View Profile
Quote
Bitshares could easily create a much more efficient solution by allowing any and all assets (UIA and Bitassets) to be used for collateral of bitAssets. In the case of UIA usage for bitAsset collateralization new problems of defaults can arise though. However, if implemented properly then bitAssets would become the ultimate pathfinding mechanism as they are effectively Steiner Points, or in other words solving the Steiner Tree http://en.wikipedia.org/wiki/Steiner_tree_problem.

I don't think it will be possible to have bitassets collateralized by anything other than BTS. Differently collateralized bitassets wouldn't be fungible, and if they were collateralized by an IOU they would actually hurt the value of bitshares. But I agree that bitassets are the perfect "middlemen" for conversions. In fact I suspect it will be most efficient to have only a single central bitasset that has active markets with every other asset, and that everything else is traded through: the least volatile asset. This will most likely be bitUSD in the early years.

Tbh, if implementing a full pathfinding algorithm on our blockchain were too problematic in the beginning, I wouldn't even be oppossed to simply have bitUSD as a hardcoded global steiner point, because I think it would end up as that anyway (until the USD tanks that is).

Offline Rune

  • Hero Member
  • *****
  • Posts: 1120
    • View Profile

I didn't even realize how much of an achievement the ripple path-finding algorithm is, I'm pretty amazed that it was already fully functional years ago. It's probably gonna take at least a year before bitshares will have that copied.

Could you go into this a bit more?  What are they accomplishing?

Arhag made a nice explanation of what is needed to do what ripple does:

However I still think we're still a quite a while off before we can fully compete with ripple on convenience, because right now I don't think it's possible to do several market orders in a single bitshares transaction (and thus jump 2 pairs in one block, making our transaction speed competitive).

According to this post, that is not true.

Yes you can make several orders in a single transaction, but I don't think you can make an order with an asset that you don't own yet. e.g. if you only have a USD IOU, you can't buy bitUSD and then instantly buy a JPY IOU with that bitUSD in the same transaction (resulting in no bitUSD ever touching your wallet, you just used them as a liquidity token).

Oh, I see. You are talking about Ripple's path finding algorithm.

You don't want to just atomically place asks and bids in different markets, you want to ensure the order is atomically matched so that you are never left holding the intermediate asset (in this case BitUSD). And it would be even better if you could simply place an order that provides a source amount (balance and asset type) and the destination asset type (and possibility a limit price on source to destination conversion), and let the blockchain find the most efficient path to get there.

Of course that creates some of the order types of typical exchanges that BitShares currently doesn't have. Without the price limit restriction, the previous system could be used to do market orders. With the price limit, the previous system could be used to do limit orders. In either case, this allows for front running, which is why BitShares has the "you only get the price you ask for" order types. It also reduces market fee revenue for the DAC because overlaps would disappear, but that is less of an issue to me.

I wonder whether or not the "you only get the price you ask for" model is the best way to fight against front running. Why not just have exchange orders (other than cancelling existing orders or covering shorts) be a two stage transaction? The first stage requires submitting a commitment of your order to the blockchain which expires in 50 seconds but requires you to wait 30 seconds before the second stage is valid. The second stage requires submitting the actual order within the appropriate time interval. By the time someone sees the actual order, submits a new commitment, and gets the second stage of their front running order accepted into the blockchain, the original order has either already been accepted (and potentially matched) or it has not and has in fact become invalid. If it did become invalid, the original order submitter then has the ability to reevaluate the order book and decide whether to resubmit the order or modify it. In that case, the person attempting to front run will not necessarily get guaranteed profits.


There's also the issue of IOU's having their transaction fees in BTS. It needs to be possible to pay the transaction fee by automatically selling IOU for BTS in in the IOU transaction itself. I'm sure all these things will come within the next 6 months though.

Yes, that is annoying. It would be nice to at least be able to pay the IOU transfer fees with BitUSD. This would require the blockchain to be able to convert between the various assets it collects by placing its own orders on the exchanges. But that would provide so many advantages. People could pay transaction fees in any asset they want (the blockchain would automatically deduct the necessary amount of the asset to fulfill a market order to convert into the necessary amount of the desired fee asset type, whether that is BTS or better yet BitUSD). The blockchain could also pay delegates and workers in BitUSD (or other BitCurrencies) and it can could convert diluted BTS into BitUSD through the exchanges as necessary to meet the delegate/worker salary liabilities (within the dilution cap limits of course).

I do hope that all of these enhancements will eventually come to BitShares, but I suspect it won't be in the next 6 months.

So basically ripple doesn't just have a decentralized exchange, it has some complicated order types that allows you to place several orders in a single transaction and be guaranteed that they will all be matched, all while somehow preventing front running and still keeping transaction speed at 5 seconds. It's pretty neat, but it's also something that will be a lot easier to copy than to come up with in the first place.

Offline bitsapphire


I didn't even realize how much of an achievement the ripple path-finding algorithm is, I'm pretty amazed that it was already fully functional years ago. It's probably gonna take at least a year before bitshares will have that copied.

Could you go into this a bit more?  What are they accomplishing?

Ripple solved the pathfinding problem through a node-based solution implementing. It solved it by utilizing known solutions to the Minimum Spanning Tree problem http://en.wikipedia.org/wiki/Minimum_spanning_tree.

Bitshares could easily create a much more efficient solution by allowing any and all assets (UIA and Bitassets) to be used for collateral of bitAssets. In the case of UIA usage for bitAsset collateralization new problems of defaults can arise though. However, if implemented properly then bitAssets would become the ultimate pathfinding mechanism as they are effectively Steiner Points, or in other words solving the Steiner Tree http://en.wikipedia.org/wiki/Steiner_tree_problem.
Register and get your personal Moonstone Wallet Beta here: https://moonstone.io/login-register.html

Offline gamey

  • Hero Member
  • *****
  • Posts: 2253
    • View Profile

I didn't even realize how much of an achievement the ripple path-finding algorithm is, I'm pretty amazed that it was already fully functional years ago. It's probably gonna take at least a year before bitshares will have that copied.

Could you go into this a bit more?  What are they accomplishing?
I speak for myself and only myself.

Offline Rune

  • Hero Member
  • *****
  • Posts: 1120
    • View Profile
As XRP liquidity increases it ends up becoming cheaper to go through XRP than trading anything directly. XRP is valuable because it's needed to earn these high volume low spreads. BitUSD will have even lower spreads in the long run because it has lower volatility.

Rune,

That sounds plausible and amen to that, however the SUFFICIENT condition for this to happen is the depth and liquidity of BitUSD trading vs BTS and other Bit* pairs

Absolutely. And BTS also needs to be finished and actually useable first :P

I didn't even realize how much of an achievement the ripple path-finding algorithm is, I'm pretty amazed that it was already fully functional years ago. It's probably gonna take at least a year before bitshares will have that copied. I suspect ripple will be a huge deal by then, much bigger than bitcoin currently is. But long term it doesn't seem likely that ripple will be able to compete with a decentralized exchange powered by bitUSD, since there will be almost no friction for ripple gateways to also support bitshares.

Offline alexkravets

  • Full Member
  • ***
  • Posts: 81
    • View Profile
As XRP liquidity increases it ends up becoming cheaper to go through XRP than trading anything directly. XRP is valuable because it's needed to earn these high volume low spreads. BitUSD will have even lower spreads in the long run because it has lower volatility.

Rune,

That sounds plausible and amen to that, however the SUFFICIENT condition for this to happen is the depth and liquidity of BitUSD trading vs BTS and other Bit* pairs

Offline Rune

  • Hero Member
  • *****
  • Posts: 1120
    • View Profile
Ripple is a great technology, but could you explain what makes XRP currency valuable? As I understand, it's needed only for exchanging exotic pairs of currencies for which there is no direct market. Any reason for someone to have a large reserve of XRP other than speculation?

What would be a reasonable market cap for XRP in your opinion if Ripple protocol gets a wide adoption?

Fidor bank transaction just hit Ripple ledger and funds were transferred from Germany to a US recipient.

https://xrptalk.org/topic/3781-fidor-bank-testing-the-auslands%C3%BCberweisung-%C3%BCber-ripple/page-4

Transaction details are here

http://ripplebot.com/4F88B09740DC70A8CA7658ADD183903D47BC1A503273A9899BB216AA229BDA11/


Gentlemen,

Today December 19th, 2014 is the birthday of the new global Monetary / Settlement system.


P.S. This is a calendar of upcoming Ripple events https://ripple.com/events/

This thing is going mainstream .... fast

As XRP liquidity increases it ends up becoming cheaper to go through XRP than trading anything directly. XRP is valuable because it's needed to earn these high volume low spreads. BitUSD will have even lower spreads in the long run because it has lower volatility.

Offline kisa

  • Sr. Member
  • ****
  • Posts: 240
    • View Profile
Ripple is a great technology, but could you explain what makes XRP currency valuable? As I understand, it's needed only for exchanging exotic pairs of currencies for which there is no direct market. Any reason for someone to have a large reserve of XRP other than speculation?

What would be a reasonable market cap for XRP in your opinion if Ripple protocol gets a wide adoption?

Fidor bank transaction just hit Ripple ledger and funds were transferred from Germany to a US recipient.

https://xrptalk.org/topic/3781-fidor-bank-testing-the-auslands%C3%BCberweisung-%C3%BCber-ripple/page-4

Transaction details are here

http://ripplebot.com/4F88B09740DC70A8CA7658ADD183903D47BC1A503273A9899BB216AA229BDA11/


Gentlemen,

Today December 19th, 2014 is the birthday of the new global Monetary / Settlement system.


P.S. This is a calendar of upcoming Ripple events https://ripple.com/events/

This thing is going mainstream .... fast

Here in the following thread this was discussed...
https://bitsharestalk.org/index.php?topic=11636.msg155639#msg155639

busygin

  • Guest
Ripple is a great technology, but could you explain what makes XRP currency valuable? As I understand, it's needed only for exchanging exotic pairs of currencies for which there is no direct market. Any reason for someone to have a large reserve of XRP other than speculation?

What would be a reasonable market cap for XRP in your opinion if Ripple protocol gets a wide adoption?

Fidor bank transaction just hit Ripple ledger and funds were transferred from Germany to a US recipient.

https://xrptalk.org/topic/3781-fidor-bank-testing-the-auslands%C3%BCberweisung-%C3%BCber-ripple/page-4

Transaction details are here

http://ripplebot.com/4F88B09740DC70A8CA7658ADD183903D47BC1A503273A9899BB216AA229BDA11/


Gentlemen,

Today December 19th, 2014 is the birthday of the new global Monetary / Settlement system.


P.S. This is a calendar of upcoming Ripple events https://ripple.com/events/

This thing is going mainstream .... fast

Offline celticwarrior72

  • Jr. Member
  • **
  • Posts: 25
    • View Profile
Fidor bank...hmmm far from mainstream

First adopters invariably are.