Open ledger transaction processing question

Technical questions about the Ripple API, the protocol, etc.

Open ledger transaction processing question

Postby sayright » Mon May 19, 2014 4:51 pm

I red that offer taking is processed in random/deterministic order for new transactions. Is that true for processing all transactions? when a new transaction is received and it could be processed in the middle of the already received transactions - are all queued transactions reapplied to open ledger?
rightZmqbccuR3su3CwWUEzoeQ8DP3fqR
~sayright
User avatar
sayright
 
Posts: 181
Joined: Wed Dec 04, 2013 4:17 pm
Location: Europe

Re: Open ledger transaction processing question

Postby alexdupre » Mon May 19, 2014 5:23 pm

The transactions are definitively applied in a random/deterministic order at the end of the consensus process.
Every server applies the transactions to the open ledger in the order it receives them, but that's only a temporary state.
Alex Dupre
alexdupre
 
Posts: 120
Joined: Mon May 13, 2013 5:57 am

Re: Open ledger transaction processing question

Postby donch » Mon May 19, 2014 5:24 pm

Aren't random and deterministic terms with opposite meanings?
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Re: Open ledger transaction processing question

Postby dchapes » Mon May 19, 2014 5:58 pm

donch wrote:Aren't random and deterministic terms with opposite meanings?

It's "random" only in the sense that it's not predictable by those submitting the transactions and should be thought of as effectively random from their point of view. As you know, once the servers decide on the unordered set of transactions that will be included in the next ledger they all deterministically order them the same (e.g. possibly by the hash of the transaction).

Note that if someone submits two transactions for different accounts (so sequence number of a single account isn't an issue) to the same server then, even if there is an deterministic ordering for the pair if they get into the same ledger, I think it's possible (but rare) that one might be pushed back to the next ledger (say for some reason it doesn't get relayed to sufficient validators in time to be included or something) causing them to be processed in the "opposite order" in separate ledgers. In other words, I think it's a mistake for users to rely on any ordering for multiple inflight transactions with the sole exception being those from the same account with sequential sequence numbers.
OpenPGP KeyID: france short hawaii
Although I moderate and post a lot on the Ripple forum, I am not associated with RippleLabs; I'm just a Ripple user. I speak only for myself.
I am somewhat associated with RippleFederation and a minor financial supporter of RippleUnion.
dchapes
 
Posts: 1445
Joined: Thu Mar 14, 2013 1:08 pm
Location: Ontario, Canada

Re: Open ledger transaction processing question

Postby donch » Mon May 19, 2014 6:29 pm

dchapes wrote:
donch wrote:Aren't random and deterministic terms with opposite meanings?

It's "random" only in the sense that it's not predictable by those submitting the transactions and should be thought of as effectively random from their point of view. As you know, once the servers decide on the unordered set of transactions that will be included in the next ledger they all deterministically order them the same (e.g. possibly by the hash of the transaction).

Note that if someone submits two transactions for different accounts (so sequence number of a single account isn't an issue) to the same server then, even if there is an deterministic ordering for the pair if they get into the same ledger, I think it's possible (but rare) that one might be pushed back to the next ledger (say for some reason it doesn't get relayed to sufficient validators in time to be included or something) causing them to be processed in the "opposite order" in separate ledgers. In other words, I think it's a mistake for users to rely on any ordering for multiple inflight transactions with the sole exception being those from the same account with sequential sequence numbers.


I had a look at the code. The previous ledger hash is used as a salt that gets XOR'ed with the transaction's account and this is the first key in the sort of the ordered map. Transactions with the same account are then ordered by their sequence number.

https://github.com/ripple/rippled/blob/ ... .h#L75-L76
https://github.com/ripple/rippled/blob/ ... et.cpp#L78
https://github.com/ripple/rippled/blob/ ... pp#L22-L33

I believe that it is still game-able though. You could have a large number of funded accounts and once you know the previous ledger hash, you could apply the salt to each and find the one with the lowest or highest value which could give you an advantage in situations like exploiting a whale trade if you submitted it quickly enough with a tfFillOrKill flag.

I guess random-salted determinism could be a new phrase :-)
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Re: Open ledger transaction processing question

Postby sayright » Mon May 19, 2014 6:42 pm

Thats quite a nice solution RL! Thanks donch, that also answers my question about all transactions being 'randomized'.
rightZmqbccuR3su3CwWUEzoeQ8DP3fqR
~sayright
User avatar
sayright
 
Posts: 181
Joined: Wed Dec 04, 2013 4:17 pm
Location: Europe

Re: Open ledger transaction processing question

Postby lid » Tue May 20, 2014 6:58 am

donch wrote:I believe that it is still game-able though. You could have a large number of funded accounts and once you know the previous ledger hash, you could apply the salt to each and find the one with the lowest or highest value which could give you an advantage in situations like exploiting a whale trade if you submitted it quickly enough with a tfFillOrKill flag.

I guess random-salted determinism could be a new phrase :-)

Great analysis, donch!
lid
 
Posts: 70
Joined: Mon Mar 31, 2014 9:28 pm

Re: Open ledger transaction processing question

Postby tulo » Thu Jun 12, 2014 11:22 am

Yeah thanks donch. :+1:

The only thing I don't get is if every validator HAS to use that policy (ledger hash XOR account) to reach consensus with other validators or can use its own policy, so this will become un-exploitable.
And another thing is if some accounts could have always an advantage over others with this policy, because maybe the hash has some particular structure that with XOR is advantaged.
tulo
 
Posts: 827
Joined: Mon Jan 20, 2014 2:38 pm

Re: Open ledger transaction processing question

Postby sayright » Thu Jun 12, 2014 12:20 pm

tulo wrote:Yeah thanks donch. :+1:

The only thing I don't get is if every validator HAS to use that policy (ledger hash XOR account) to reach consensus with other validators or can use its own policy, so this will become un-exploitable.
And another thing is if some accounts could have always an advantage over others with this policy, because maybe the hash has some particular structure that with XOR is advantaged.


I think this is used not during consensus reaching, but when applying the transactions after a consensus is reached
rightZmqbccuR3su3CwWUEzoeQ8DP3fqR
~sayright
User avatar
sayright
 
Posts: 181
Joined: Wed Dec 04, 2013 4:17 pm
Location: Europe

Re: Open ledger transaction processing question

Postby donch » Thu Jun 12, 2014 12:32 pm

sayright wrote:I think this is used not during consensus reaching, but when applying the transactions after a consensus is reached


Not quite. The ordering of transactions is part of the consensus process. The transactions get ordered, processed and applied. This results in account state changes. These both result in changes to the transaction tree and account state tree which reflect in the ledger header's TransactionHash and StateHash fields. The ledger header itself is then hashed and this hash is signed by each validator. All validators check the signatures of all other validations and when 80% plus of the checked validations from validators on the instance's UNL have the same ledger hash, consensus is reached.

At least, that's my understanding :-)
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Next

Return to Developers

Who is online

Users browsing this forum: No registered users and 2 guests