Exploiting Ripple Transaction Ordering For Fun And Profit
Below is a copy of a security report submitted to Ripple Labs on 18th May 2015. Unfortunately, after more than three months, no fix has been released and no acknowledgment of whether the exploit is regarded as neeeding a fix has been given. Fair disclosure suggests it is better to make the exploit public after this period of time. Github links have been updated to the current code. Unfortunately JIRA links are now broken due to the bug tracker being made private.
Full disclosure: I have received numerous bounties for security and bug reports in the past and was employed as a contractor for Ripple Labs for a period of time.
tl;dr It is possible to "mine" transactions ids which give you a better chance of exploiting the state of the Ripple ledger for financial gain.
Exploiting Ripple Transaction Ordering For Fun And Profit
Ripple transactions are serializable to a custom binary format that is cryptographically hashed and then signed by one of two schemes (ECDSA and EdDSA). This signature is then inserted back into the binary serialized form which is hashed again to produce a transaction id through which it can be uniquely identified. Transactions are submitted to a rippled node, which verifies that the signature matches the public key and the hash of the public key (account id) and if the signature is good, it disseminates the transaction to the other rippled nodes operating on the same network that it knows about. These instances pass that transaction on to nodes that it did not receive it from and this flooding should result in it being considered for adoption in a ledger by the validators running in the network by the process of consensus. All non-validating nodes do actually process the transactions, but only the agreed ledger of the trusted validators counts for all intents and purposes.
Consensus requires that these transactions be ordered so that all validators can apply them in the same order and reach the same result. There is some confusion amongst the community and no conclusive documentation on this ordering. So, as is often the case, we need to read the code. First, let’s look at an example ledger that show some interesting characteristics:
SELECT at.TransId, ...> at.TxnSeq, ...> at.Account, ...> t.FromSeq ...> FROM AccountTransactions at ...> INNER JOIN Transactions t ...> ON at.Transid=t.Transid ...> AND t.FromAcct=at.Account ...> WHERE at.LedgerSeq=13304583 ...> ORDER BY at.TxnSeq; TransID TxnSeq Account FromSeq ---------------------------------------------------------------- ---------- --------------------------------- ---------- 013BDF50F3D6FE5684935D1BB63DDE5DF3994C533F87D4C5C8DCF37047C42B71 0 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18514 03415480457F5BDDC6FDE019A9BB6E6B8DF45A1111375B08CAB64A099C8C01D1 1 rfRQfYGrs8BoyS4duDjWDH11yq5JVX46A 32642 03C181BF1A23A85521970EBF5A144E09B74FC0D6B0A9C7CC4B11EEA14C8C5794 2 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18515 044F9A749F75545937FF37560A8EF325D2EDED25E44AD59FD3B5E01CD8D43A01 3 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18516 079E0378F417F1380FF4BB25A5865DC749FF145B2C1FCCCD02A740EC8AC06028 4 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18517 0829279565D00E649CF673E36FE599F6F0D421175C9FCF04CF97CACC8334F054 5 rEaWE52vbfqoHCbaidH4oE32DYfbQtw9c 144527 0999C5ACA9588F003A5676DEECA3FE7D8B02605F6706C33E6BA72CB8820F5103 6 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18518 0BC5C5BC792A2AE9B5B5733BE017041143C5FAC902BCE80095C00DA9FDF64729 7 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18519 0C2DD73CB47045E52F4D9F1DAAD42A9E375EC3502F7F5FF24FAA5D2EF6B34942 8 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18520 0C67BE5505C301A4B78853BDA1A8167C0BF61EF040AC2C67278329054581DD48 9 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 18521 44FCFD01470516ABBD293C2414A4F5B61408F53B5FD8CD69EDFD2DC8024DFFF3 10 rBN3aEzHtDMPtkW2ci1PJNFxXLi4DUT1E 76770 5CCCC475B697777C251578B7360202C33052753C9114C088229FB8E110D487AF 11 rKkhd9rTV2fJR59DgsFQG67GFcqoNVgSN 10352 8C644A85749C0C5618B7D7DA7BAAFC1F9779118DBCCB3D328FC9ADA44664DD83 12 rDaeHQrL8bEbPuQGx7rkb1vCwUbPqGdDt 22113 97B42105AE8154B80B7065559DF2EE82C4F470AE3A582855FEAE635C8E5DC9EA 13 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270095 A968BBA4412E7D6358520DC3E7702079BD35DCABB67AAEA96CC9675D9EF61FD3 14 rDN91UzG9HyDyGuoNpuyCxKdw1FcFA9bA 41608 AB506718DE4CA503DAF42D562ABC407B882428F5C658D65B4605A9D21ADC6F50 15 rEaWE52vbfqoHCbaidH4oE32DYfbQtw9c 144528 AE03E8C3097CBA89F1F30A788553321BD1472E7EB7885A9545A0C185CB7E586A 16 rDN91UzG9HyDyGuoNpuyCxKdw1FcFA9bA 41609 C5837574AC71F9F12C5EA1D32D8F74CF53FC1B6FC7FEC8F2CB459AE19176DC6F 17 rEqm4WyqHqHoLYKM9fwDkpnK3Adi2yJdD 23391 C9C63127696EBBA8D4115B4BD672C64B85E7B9C6CBCB5536A2F081A2A9F0F1C0 18 rUY4bFSz4y6gsGvedGmKoLngMnvMoawej 42738 DA2A6FB112C476A264EE11A0C616B71F5F578A84AF986A9A13F79855109C5AE0 19 rGcSxmn1ibh5ZfCMAEu2iy7mnrb5nE6fb 14931 F8D9BF6ECA2083482C27A4CF45A25690427671E5928A7E740A4691BEF91A6AA5 20 rBN3aEzHtDMPtkW2ci1PJNFxXLi4DUT1E 76771 064F9CD745883CD69F2284ECE789827232EF5A339FDAF78CD260D60BA1F2EDF2 21 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270096 FA51521273C46C5984693BBB48E3421AF07D51C2D303C48365F7AB5630D689D6 22 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270097 A29C7AB2CEE16436B367DCB0C810127135DD0C5524A84854853CD67EC0CAFF58 23 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270098 9B3E3F55F0D5BA7A6FD962154E28FFE886D36E902CBD50D64DD01DA2A5DD513F 24 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270099 E47F0AC7185B9EBD920D85D15296E80E66EC559D6812D893DBA4E315BA2B3B11 25 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270100 24C80472F6716CC2B1211A665B3CF14D9775A6C74337D59C70156F4E3447AF48 26 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270101 0A66B53BBB40A5057CADAFA0FFB0AC2BAB41D2889D1DAD6178D41DD023CD2DD6 27 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270102 D44DD02D5A454F16ABB90EAE71BBB2F90549BB2764F8D12B117F646E34BAE4A9 28 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270103 0AC2D4A67D6349E2ECF1722BA6A9AA45F02195DA0EB2B4417AEBDE767A7E7EB7 29 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLE 5270104 4465966BBE18C0038FE5CEDA93E1E3D437258881D76678353D209F4841185EED 30 rDaeHQrL8bEbPuQGx7rkb1vCwUbPqGdDt 22114 578214C13AD9FFA75EBD721BA67EE33AFF0570284FEF292B207F80FAF8D31BD0 31 rEaWE52vbfqoHCbaidH4oE32DYfbQtw9c 144529 94A52C051E01A91282955DF70284288DEAE4B4555315681C52AB9CD31827D725 32 rGcSxmn1ibh5ZfCMAEu2iy7mnrb5nE6fb 14932
- Transactions 0 to 20 are ordered by transaction id, with multiple accounts being intermingled, but for each account, the account sequence and transaction id have a congruent order, this being the default case for an account with a single transaction in a particular ledger.
- Transactions 21 to 29 are transactions for a single account, this time with transactions being ordered by account sequence (note 5270095 though).
- Transactions 30 to 32 are for accounts that already have transactions earlier on, but for which the transaction id is lexicographically before the id of one of the earlier transactions for the same account.
So back to the code. It is tempting to say that the linked code is almost impossible to understand without the aid of a lot of logging. There are three places where transactions received from the network are applied to a ledger:
But as far as I can tell it is only the application on line 1009 that actually matters for the transaction ordering of a closed and final ledger. So if we move into applyTransactions() we can see what decides that order:
Iterates set in transaction id order, putting any failures of the transaction engine into retriableTransactions which is seeded by the root hash of the transaction ShaMap:
and ordered by a XOR-ing of the transaction root hash with the account id, by account sequence and then (irrelevantly?) transaction id.
These retriabletransactions are then iterated up to three times to apply them to the end of the ledger. In some ways it doesn’t really matter what anyone thinks the code is doing or is intended to do (the code itself makes that task very hard), only the observed behaviour matters. Which brings us on to a pair of exploits that take advantage of this observed transaction ordering behaviour.
Advantageous Arbitrage Transaction Placement
Arbitrage is the taking advantage of different prices in different markets to collect the difference minus any applicable transaction fees. It’s free money that doesn’t last for long and its effect is to remove liquidity and at the same time bring equality to markets and inform speculators of correct prices given the state of all markets. The Ripple network is ripe for arbitrage given the abundance of currencies and multiple markets for each of those currencies. The problem of finding opportunities can be speedily solved by recursively applying a FIFO queue-based Bellman Ford algorithm to a graph of the negated logarithms of the ratios of the funded tips of all order books to find negative cycles and removing the smallest offer in each cycle on each recursion. For each path apply transaction fees and see if gain, given available liquidity of the account and the path, is greater than cost. This way many, and indeed complex, paths can be found (trade secret revealed!).
However, arbitrage is a race and there are two ways to win. Find paths that no-one else has found or exploit paths before anyone else does. The author was initially motivated by the first challenge but soon also found a solution to the second. The exploit follows:
- Build a list of profitable paths.
- Build OfferCreate transactions for each path with
tfImmediateOrCancel|tfSellflags set and append them to an ordered list.
LastLedgerSequenceto current ledger+1 (+2 can still work when the market is busy and submission times are universally slow).
- For each transaction set
SourceTagto an incrementing counter (nonce) between 1 and n, sign the transaction and determine the transaction id.
- For first transaction select the nonce which yields the lexicographically lowest transaction id. For subsequent transactions select the nonce which yields the lowest transaction id greater than the id of the previous transaction.
- Sign once more and submit transactions to the network.
The effect of the above process is that with high likelihood your transactions will be processed before those of most other accounts in a ledger, dependent on how high your value of n is. If another arbitrageur has found the same path and submitted similar transactions, they are more likely to fail in their aim of exploiting the path as maximally as you. Of course this depends on the liquidity of the path and the available funds of each arbitrageur.
Obviously there are tight time constraints to find opportunities in a ledger, sign number of trades x n and make sure all the transactions reach the validators before the next ledger closes. For this reason using a programming language with a fast native version of the signature generation scheme helps. In benchmarks, using an optimised native Ed25519 implementation, it has been found that a path of 7 transactions can be signed 256 times each with a different nonce in 360ms to “mine” a preferable transaction id. The author is certain that this benchmark could be improved. Following is an example ledger where many arbitrage bots are fighting to exploit the same opportunity. One aptly named account seems to be winning the race, but see later analysis of all accounts for some interesting observations.
SELECT at.TransId, ...> at.TxnSeq, ...> at.Account, ...> t.FromSeq ...> FROM AccountTransactions at ...> INNER JOIN Transactions t ...> ON at.Transid=t.Transid ...> AND t.FromAcct=at.Account ...> WHERE at.LedgerSeq=13432605 ...> ORDER BY at.TxnSeq; TransID TxnSeq Account FromSeq ---------------------------------------------------------------- ---------- ---------------------------------- ---------- 0014BE643C33325E2484C7AB4E86BD86C0015847199566A7CC7658DBD663E57C 0 rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 16434 0100B6409A32F45C73FA26365EC234F34B16011A8F22B2A52DA1BAD8F0D33244 1 rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 16435 03603F21BCC62C4E2E47A023B286E31A4FA78ACF5A0BB4930CACA7DEC0265734 2 rfTiZ53FW6aXcY9TFXQbZMsHQeP4h6Dgkh 395872 041436C67D9FF4504391D88620BCE1755EA7D67804D609B839CA2F88D3CF891C 3 rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 16436 042CB042F781ABFE30BC7DD3AB5EA6444DC7EF0AE389FE7CD3E52F6D9E151A83 4 rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 16437 050364F43BD4214B1A8ECDB3DA7F1EACAEE378B949AD317072C5162ABFED3FDC 5 rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 16438 06CE55196A621A0B77226D96CE2C6F648FD850F52CC09F530A7F0B7C4B39B188 6 rHv4gWtQL4PEaUij1kEyAVea7Cyn8f4aAp 17775 07C26F2A99D4AD883C3A1785442FA9402D1EC63359BE2C19EA372FD4FAEE89C4 7 rHsZHqa5oMQNL5hFm4kfLd47aEMYjPstpg 17792925 0A75C1FC810C5FDB91986E54CCFA9187D86663BBDD8249411D6F88A14DFFA140 8 r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT 737230 147E6661059DE6470A4D7699158595E7C81C5141FAF87A49A1392D4DA3D53AF8 9 r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT 737231 18EBF244FBBA4A4C25DDD6B94462724598D2C02040D04D904B2E6E5404465FEA 10 r4Ci6dk2QmwUdb8ixWn17VkwjaLJATc6zN 51 2773523702A7957343703241EDF9BA75EFBE5057B5E827ECADE650B1E3EBC7DE 11 r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT 737232 30150098887D26D466CABDE4B41B2309A73AA285E450CDF4972E20C2112766B9 12 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385151 3F5B2965201784B44CAE2247E5EA7645B17F5449472D42B6BEC778EE713B7D3E 13 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574424 41AD7B7ABFEF0C00B05413A48E72095ACA4DF443A9B256A6EE388DA0D0041EE6 14 r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT 737233 4C0C28EFAEA3E164AF8CB101172A112DD4534262996B8424FBD7C42513F2F7E7 15 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574425 5904D28C6515772BD586CFC4425EBB25AE5D4079177F9EEAA7E166BDD3F73F54 16 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124709 5B79BBA28245DA38CE395FB07E09E17BF3CDCD8A246CAC63667262A84F4183DC 17 rHaLk9zSC1JPmbDiWAgWTgjcEacHzGbqf 217829 72E10D6FDE8A94F12BC7C8A8BBE601621B3698954C8F25E756F3E415EF77A43B 18 rpqvwJNV9skJzWH6TyJakRcMSCzn1hrBP9 2588 78124D5741A8C923BCD4A6809B1E2D09AB596F944623C97E28414164C16B26B7 19 r4rCiFc9jpMeCpKioVJUMbT1hU4kj3XiSt 244401 7B756E3D2E9F1D56927923D491FD7ED586C027AA2F34B2946799A4D0923B6E13 20 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574426 885617C50CF625BD0179F3F8F6E3923DD971A70C115AF71999753DAE05EF863C 21 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLEw 5440938 A1EE0FDBFC6CFB386C54CDA8F8A1247A6F748BC50090FB2A00929FEC33673832 22 rHaLk9zSC1JPmbDiWAgWTgjcEacHzGbqf 217830 A5E0AAD9C0433FC4E8BB59DC94FB2C6B119F54E1F1A0737BC3E31E9C3701EFAC 23 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244287 AFA03913F8C1DE800D8F0230F1C3048F8D6F81C6E9AC7ACB1F10AA59C7F70C0C 24 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385152 B736FE19327C0E0A69B286C5FA200EA7AECDE0498E9DE8C21B70980DF0031139 25 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLEw 5440939 B85B2CFD61C26B65F13D26778C503C54E26DE204C5171C29BBB10C9220BBEB39 26 r4rCiFc9jpMeCpKioVJUMbT1hU4kj3XiSt 244402 B86DAD614BB672C0F5028DDE41E7B8C2A68985091D040060664966DA2A767441 27 rDaMQ1kD7E2xjQUBK2ghaebRFqQ5jZ1FFA 224819 C5F0C886C195FDDA7190A3D2439B67607ECB576498F28A5F34F4D1FC1BBE07B2 28 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129519 C8313039F341ECD699D8199FFD8FF9223A9548C7B187E5F77EB1F9C4F6FB21AA 29 rfTiZ53FW6aXcY9TFXQbZMsHQeP4h6Dgkh 395873 F2CB2930BF5F15B19D5AF952B4832A01905EA71A764510F8B05A9DA0A49FDD02 30 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450206 9E92505E21304EF2016401E2FE0C9197B55977BEDAC1B99D14C31FF1AF32D54E 31 r4rCiFc9jpMeCpKioVJUMbT1hU4kj3XiSt 244403 B43690DBF69479AB3D848BBA5E777DE53255D12D419CCD3F1B9D4AE8DD91D99F 32 r4rCiFc9jpMeCpKioVJUMbT1hU4kj3XiSt 244404 2731280F64FF4FC8B76280BE674D1EB38635EC7FFEC88237AB4A16CBD2A3A597 33 r4rCiFc9jpMeCpKioVJUMbT1hU4kj3XiSt 244405 16FDA2B9C38AC42D8D8C3211D49CDF358BA58180100ABBA988C77A5050A807BB 34 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574427 2E77F446844242DD0D350A8281996B1B65EC25CD6C421C4262B05D91563CE771 35 rfTiZ53FW6aXcY9TFXQbZMsHQeP4h6Dgkh 395874 82AEEB52DB86DD92A506C44F34F5AB59ED21ED06320B0E895517718D6A01CE7F 36 rfTiZ53FW6aXcY9TFXQbZMsHQeP4h6Dgkh 395875 95C7CCD5F22C1053EB1114346776C589192545FDB8F74891EA1E0A57E427F0BA 37 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385153 68930C664F756F3447CB3E14CB52D01C2DFA72570DC4A0AD375B9291559E54B9 38 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385154 2981CAB2C09D32D2A9640231DADF866C0708AAC7800F1CBCB5D723C306D8C3AF 39 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450207 75151DDC65E013BF736BC78148B590B3F6C9C243559D96C35386EF0312F4D928 40 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450208 896DEE1F537C2BE6FA0DF4775BEC8BD177668F1B7B34824E79BAFAAFA7CE4804 41 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450209 210AAB246C1D49C6AC36E4D7539891CD32082159269F68324B17A38843537F8D 42 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450210 D0FAE9BB1FEF7675D82F6F8D3F319F62D60A51F49E2EC14C515568876D676EA4 43 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450211 C9882626D9AF34FCA09E56A14CD7528E0C97A91A4ADC981732F6B2F92A0D792F 44 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450212 63F18D5ABF3C1ACBDDEEF988438C23AA2D919E47CBF7D601713A267B7EA4814D 45 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450213 CD486E649516E10490C6CBCCDEF3487CAFDE05DD45CEB9317B19D1B86535E669 46 rfU3YWd1TnYryvryQTQ9xwyCSqzMTbnyW6 450214 4437EABCAA7BDFF75CDC97F913A6D1EA90E59FFD032B22A4E278AEA753110BAD 47 rfCFLzNJYvvnoGHWQYACmJpTgkLUaugLEw 5440940 030F0E810C2813CA8CD9B7F240E3026D1E871CF375A8466CEE0B268F088507A5 48 r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT 737234 163CE9D4FD2D846C161B2BA87E145A14A96DD9CA694CF70BDDE975FF39C404CB 49 r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT 737235 19752025CA06FD505839733B248064F54460A4077A7BADA12633CC35EBD60DA5 50 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124710 DDF3E5C89C4D34502ECF5973AA5EB723CA6ADA3F9B6D5BA5FEFC4A1E0915C9C7 51 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124711 B0FE03C3C0E6F010680866015AEB6BC36F25FBE5B9FB983D598D4FE5BA61978B 52 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124712 07B8F5ADD3CADE1706AFC05313ECAFF10C5DF4350CD1798765EC1743E9D6B5D6 53 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124713 04374A7D4D84F0B9DFFF0F7ADFCD2C450F70F37E712BD4268CA9995F568F2FA6 54 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124714 FA19C9A89AD3AC34DE13197E62CD745E1E2D3B06C7DB036C33CF1D82AA908D17 55 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124715 06F33A4A3FDC83094A395E52264FD04C99E75711A7062BAB7ED0083FC81D8F28 56 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124716 3F7E2AC93989AB57BC30969E0284E2E1303EEA3DCD5F71483DF25069FD76F687 57 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124717 FAB4183A845C47C008CBF103DC7CD1C97B7944DE2B8530A98A04CBBF3B456567 58 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124718 F3E1173903A355797EFC4D2C8B48D6DAA5C5041112B412D6D31E4450E585F344 59 rPC4bKCkZn2uNS3AhFMcsazG9D95dJufFA 124719 AC9CFC8971B55E010217EBD164A1E3C5D3ED3A2A22EA4962219374BDD6F9ECF0 60 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574428 9BC622B074C2733B4EDFA15F62A16A20A605581CCE9623781C4D7C4C0B3C440C 61 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574429 06374FE96539789AA32C958057F4271E72B47FBBFCEA394AC46BF61F717D8E27 62 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574430 E10026EBE74A943E77C2047F048B749859BB39A7E98E28AF635E5108F340DDB4 63 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574431 FA3E5DF5EB9C677E9FD21337B1D588E4182585667D75E7C155F6B919E0CABD25 64 rPCFVxAqP2XdaPmih1ZSjmCPNxoyMiy2ne 574432 C6D8D316C8A76C2B35CAEFBD29DDC25D8A2BF381A708DE2A0FCE61FD1D491F3C 65 rfTiZ53FW6aXcY9TFXQbZMsHQeP4h6Dgkh 395876 D999CC183F9C9D591200A1E1CB5B0F7F853FF025CF7DB62E0C18230706D815E3 66 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385155 4DFA74AE71F7003CB992D059DDE2B97410E85D1B3D496D17CD704FFEDDA6A224 67 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385156 D9D3930B6DDF81BB4E4F724708FFBC6FF231791B25F1927BEEB23699A80A47C5 68 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385157 4D94E196976861C3E9CFB7727E28EC70145485D868B69C08D191CAC0AAA5D9E0 69 rfZ4YjC4CyaKFx9cgzYNKk4E2zTXRJif26 385158 B21FD6EE4F006ED839E3876C5078B5B01F6A75A872A278ECF4774BF624C0A33E 70 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244288 EA9B32D8DC4C6EE45AD9FDB8078734C5AE922CF174108E7D7DA42188B2A8F9C8 71 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244289 BAC6BE3AA19ECFD73A0296B9AFFF3AAF2D685C4C85B1E0E9BBC50361EABD16EC 72 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244290 8312E8C18FC886B0097B8382DE1D175A334F4D9A7FBF6C4CB176EB8C682139D7 73 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244291 DFBCD7C92B523B23F30F0AD891C826038857F957B70F22B57E95FE68687A9B47 74 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244292 D545D29699E2C739F74EA54E47173B766594ABA92C675A5A851D10F1518D2625 75 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244293 878CCE1456A776A422CCA6D63552A58B37DC556FA2652C73088F66F4E7FFF93E 76 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244294 6741CED9D585CEADCB0B1953F3A3AA40916579E3874F4CDA5F4C11364C2CA7A9 77 rn3x9UZcrb6tEWzu7nXSMEtJsHX2tT6xuF 244295 2A1CAFBE7ACBA2876243D1090CFFC1A7EC543C6E55C0D3C911E09B4C05E7DB6D 78 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129520 818899490B360D3C83693CAE057DBE0F90589EC942B0D203FBB12D769A0EDD59 79 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129521 1E2325594547696BF988358C9CD2A31B9D997895307DCADDFCE396D4B70BA1EC 80 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129522 AB886755511D069CC086E61194EF563B69881B69320DBFCB464B17EACAEF6204 81 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129523 5DABC2F63D0B2E98310C499377CEE8FFFAC9DB2A61DFDDA7C3AD545CC1E5AB87 82 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129524 73015BF2D2991633636A380487B36DF448F281995ECEB0EAA31ABFAFDF9F0523 83 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129525 72CDB07181629CAAD7C68374AAA3E1CC0418326A9BD7C5502EE20987950CEAB2 84 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129526 1ACCAFF7797275B81BB209554005E6AA357042D488DB41ACD8FC6C32F7579F5E 85 raT8RBKLgP3WmKtCy5TWjcUrPUBEBfgJ3k 129527
To summarise and generalise the exploit, to get your trade(s) considered first in a ledger, make sure that your transaction ids are as low as possible, using a nonce (SourceTag, Memo or tiny fractional amounts on TakerPays or TakerGets), and make sure the order of the transaction ids matches the order of the account sequence field to avoid relegation to the retriabletransactions doghouse at the end of the ledger.
Large Trade Front Running
As discussed at length in the book Flash Boys, given enough relative time advantage, it is possible for one actor to discover a large trade and execute other trades in advance to take advantage of that initial trade executing, often to the disadvantage of the original trader. This is a controversial topic that has created much anger directed towards High Frequency Trading. Ripple is hardly suitable for HFT, but it does share one thing in common with HFT markets, and that is that there is latency between a trade being known to the network and it being executed and applied to a closed ledger. Given the previous exploit of being able to manipulate transaction order a slightly more terrifying exploit presents itself:
- Monitor all incoming proposals for OfferCreate transactions.
- Check funding of transaction against in memory, up to date record of all account balances (using ledger_data and AffectedNodes).
- If OfferCreate crosses completely at least one other Offer, create an OfferCreate transaction A to fully consume the first existing Offer. Create OfferCreate transaction B to sell acquired asset at the price of the next highest Offer in the same order book minus a very small fractional amount.
LastLedgerSequencefor A and B to be current ledger+1.
- “Mine” a transaction id for B which is less than the transaction id of the incoming proposed transaction, but as close as possible.
- “Mine” a transaction id for A which is less than the transaction id of B, but as close as possible.
- Submit A and then B.
The above exploit effectively lets you buy an asset and then sell it at a higher price with the assurance that it will be bought in the same ledger. The effect of this will be that the original buyer will receive less of the asset than he or she might have expected. The wider the gap between the funded tip of an order book and the next funded offer, the greater the profit. The exploit could be extended to consume multiple offers dependent on the size of the incoming proposed transaction. There are risks to the strategy, in that it possible that the incoming proposed transaction might not make it into the expected ledger (disputed process) but experimentation would probably provide more data on that likelihood. This exploit is unexploited by the author.
Risks, Mitigation And Observations
The two above exploits would very likely undermine public confidence in a market as operating “fairly”. Defining fair is a hard task, especially in a distributed context where latencies are wildly variable. There is no such thing as strict time ordering on a global scale of independent machines each with their own clock and network routes to each other. However, the current system clearly favours those with an understanding of the protocol’s signature generation scheme.
What’s a better solution? Well, strictly ordering by Account and then Sequence with the Account order seeded by a root hash of all other transactions to be considered makes a lot of sense, as any new transactions changes the order for all other transactions and is very hard to know for certain unless your transaction is the last one to be submitted to the network in time for that particular ledger. Why this isn’t the case already is a source of confusion. Perhaps the end of ledger “reshuffling” is an attempt to solve the order of dependent transactions, for situations such as a funding payment for an account and that new account creating an Offer in the same ledger. Disallowing edge case scenarios like that would certainly simplify things.
The key observation and suggestion I’d like to make is that it is perfectly reasonable for a trader to want to make a series of transactions which are dependent on the outcome of the previous one, to take advantage of opportunities such as arbitrage. However, the current unpredictability of which transactions will succeed and which will fail means that there is a high chance of getting stuck with an undesired asset, which is why this exploit is so useful. It vastly increases the chances of success of all transactions based on a fixed model of the previous ledger. However, it would be preferable and more “fair” for the chain of transactions to always all succeed or all fail, and the chance of success is based on a lottery of account ordering. To achieve this requires a unit of atomicity greater than a single transaction.
Payments, on paper, are meant to offer this. But they don’t have much flexibility at all. As far as I have been able to determine, creating custom paths which hop between more than two order books is impossible. The condition of using an account with rippling enabled as an “in-between” stage is nonsensical when the trader does not at any point want to hold the “in-between” asset. It seems like an awful lot of complexity was added to facilitate the idea of temporary credit in payments, but is poorly understood, hardly documented and used by very few people and results in not very much gain. Study of the ledger history shows that Dan Miller/pigeons is about the only person who really tries to make use of it.
What would be much more ideal is being able to submit a batch of OfferCreate transactions which either all succeed or all fail. Either that, or Payments are modified to support circular paths along up to say 16 order books without the need for rippling enabled intermediaries. Payments are better in the sense that they have support for the flag combination
tfLimitQuality|tfPartialPayment|tfNoDirectRipple, which is exactly what an arbitrageur would want if it actually worked for a circular path!
There is some discussion here: RIPD-829 but the explanation doesn’t really add up. If the author can calculate a sequence of offer amounts that take the maximum available liquidity from a chain of existing offers, why can’t rippled? The only challenge for the arbitrageur should be then to find the best possible paths, initial input amounts and minimum expected gain (sendmax/amount ratio) and see if anyone else’s payment with the same path gets picked first by virtue of the account ordering. An extra benefit of this would be much reduced transaction size, many OfferCreates reduced to a single Payment.
In The Wild
The author has demonstrated that the transaction ordering can be fixed with two accounts. Initially
roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ used ECDSA signatures to “spin/mine” transaction ids that ensured best placement in a ledger to exploit arbitrage opportunities. It soon became apparent that EdDSA would offer even faster creation of desired transaction ids and so
rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 made use of these features:
Within the space of a few weeks around 900 XRP has been turned into 57,737 XRP, “unfairly” displacing other arbitrageurs’ chances of success in the process. The next obvious question is whether this exploit is known to others. The answer is yes:
SELECT MIN(LedgerSeq),MAX(LedgerSeq) FROM Transactions; MIN(LedgerSeq) MAX(LedgerSeq) -------------- -------------- 13243962 13483930 Unfortunately not much history... SELECT Account, SUM(Zero), SUM(NotZero), COUNT(*), CAST(SUM(Zero) AS REAL)/CAST (COUNT(*) AS REAL)*100 As Percent FROM( SELECT FromAcct AS Account, CASE WHEN SUBSTR(Transid,1,1)='0' THEN 1 ELSE 0 END AS Zero, CASE WHEN SUBSTR(Transid,1,1)='0' THEN 0 ELSE 1 END AS NotZero FROM Transactions ) GROUP BY Account HAVING COUNT(*)>32 ORDER BY Percent DESC LIMIT 30; Account SUM(Zero) SUM(NotZero) COUNT(*) Percent ---------------------------------- ---------- ------------ ---------- ---------------- rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 17924 2 17926 99.9888430213098 roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ 6512 67 6579 98.9816081471348 r3pFpfYfCoj9Sm5cpRwc4iD4mFPoF9HDVf 36 8 44 81.8181818181818 r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT 1195 3604 4799 24.9010210460513 rBApdygJewirS7hmF3rsSDfN9VvLiJ4uM8 6 28 34 17.6470588235294 rwzNnh868djfPPsN77GYwH8xYbiAXoKW3E 7 34 41 17.0731707317073 r93NwTGcTMXVAJmujHHYihezSxPLuRym5M 5 29 34 14.7058823529412 r4PowrZ7KZw83oWDYxzY82ht2kgDmFUpB7 8 48 56 14.2857142857143 raL1xU5rggQZ8cw1MUhiVRF7NzNsy7UyLB 9 55 64 14.0625 r42Ccnr9HS77UciZ8kkUe3dRsY7tXqm5M3 6 37 43 13.953488372093 rhotcWYdfn6qxhVMbPKGDF3XCKqwXar5J4 5 31 36 13.8888888888889 rHDQcQNWTV1jrBNyLJoeYDiL7Z9CbPyjLF 6 38 44 13.6363636363636 rBRXcf7BYs2CN7GfAAXjLQPEh7d46BP9RE 5 32 37 13.5135135135135 rUgsWsFYsLJwK1YCJHqofX9Sd9oVA6mgMe 5 34 39 12.8205128205128 rJRi8WW24gt9X85PHAxfWNPCizMMhqUQwg 15 106 121 12.396694214876 ra94ZuJRF8yt6Yv7GvwDoNcdaQKV5zLhnZ 7 50 57 12.280701754386 rrsGUZnvUE5jiG1jw1YpSLz8fPz7QNYBNL 5 36 41 12.1951219512195 r9JvBskaY32NQxHjEz63eJXfx9tQrSdrdr 12 88 100 12.0 rhWFasnjCuk2unVvAmqtArhYux6MNb1FUY 9 66 75 12.0 rHsZHqa5oMQNL5hFm4kfLd47aEMYjPstpg 29710 218477 248187 11.9708123310246 rHJ7KLBwbGL1Nxv15zWucqMsKDs2793cRe 5 37 42 11.9047619047619 r3cw8TWbYnsJuMKs5jnLUzsq9NBNo41E2Y 6 45 51 11.7647058823529 rhBUWH1rM8EzY3E1CN186CkTZ2KPv7pvke 8 61 69 11.5942028985507 rH5vgPUmMU5yyroKMEYUqrjjZBjrBU91hV 6 46 52 11.5384615384615 r47GLMFhJPjshD65J8TJSWZJzM3jPHcJdZ 7 54 61 11.4754098360656 rBAfbNiNHNrdbSPrxy28S5C3oZsXkgWbVy 4 31 35 11.4285714285714 raRt2xRmnnLGWYXD5VqtqKfuy4KM324Q3g 5 39 44 11.3636363636364 r429uRzCoM48x9JFaqyefwKJ9GQNrnceRb 24 192 216 11.1111111111111 rEwy79WnbBb2TxERquM1sotKUy5TLkeVZQ 6 48 54 11.1111111111111 rK3hATVGb61XjjUFTG1q9UUAzAoDufhmoo 8 64 72 11.1111111111111
Accounts with small transaction counts would be expected to turn up in a normal distribution of the transaction id front nibble, the expected median percentage being 6.25%. This query would be much more conclusive with more history (and even better in a real SQL database that has UNHEX()) but the accounts that are definitely “spinning” to some degree on transaction ids include:
rapido5rxPmP4YkMZZEeXSHqWefxHEkqv6 Author’s EdDSA arbitrage bot roverTeW1kfwHb9WZyoJW9M6sP4nC6BuJ Author’s ECDSA arbitrage bot r3pFpfYfCoj9Sm5cpRwc4iD4mFPoF9HDVf Possible trade front-runner r2d2iZiCcJmNL6vhUGFjs8U8BuUq6BnmT Another arbitrage bot rHsZHqa5oMQNL5hFm4kfLd47aEMYjPstpg One of the most frequently appearing market-making bots
To ensure confidence in the Ripple network operating fairly the above described two exploits should be made impossible by fixing the transaction ordering to prevent unfair transaction placement for canny operators. Perversely, the desire to save energy by not using proof of work to agree on ledger outcomes has been countermanded by an exploit that uses the same concepts to “mine” transaction ids.