Pushing genesis back to 0

Technical questions about the Ripple API, the protocol, etc.
Google [Bot] like(s) this thread.

Re: Pushing genesis back to 0

Postby freequant » Tue Mar 11, 2014 6:28 pm

+3.
Period of prescription is over. Please release the classified data!
freequant
 
Posts: 894
Joined: Sat Apr 20, 2013 12:11 pm

Re: Pushing genesis back to 0

Postby ChartGuy » Tue Mar 11, 2014 7:32 pm

ahbritto wrote:
donch wrote:I do think this needs to be done - without the genesis ledger being viewable and the initial distribution of XRP being auditable, it is hard for Ripple to be 100% credible...

Do you think people do not find you 100% credible as they don't know your complete ancestry? ;)


Are you serious ??
ChartGuy
 
Posts: 580
Joined: Wed Oct 30, 2013 5:56 am

Re: Pushing genesis back to 0

Postby JoelKatz » Tue Mar 11, 2014 8:15 pm

Looking more closely at this issue, I think recovering the ledgers will be impossible. The main problem is that to confirm you've got ledger N correct, you need the hash of ledger N-1.

However, it occurs to me that there's a way to recover the history without recovering the ledgers. When a transaction is signed, a random factor is used to produce the signature. If you look at ledger 32,570, you'll see entries like this:

Code: Select all
            {
               "Account" : "rLs1MzkFWCxTbuAHgjeTZK4fcCDDnf2KRv",
               "Balance" : "10000000000",
               "Flags" : 0,
               "LedgerEntryType" : "AccountRoot",
               "OwnerCount" : 0,
               "PreviousTxnID" : "DF530FB14C5304852F20080B0A8EEF3A6BDD044F41F4EBBD68B8B321145FE4FF",
               "PreviousTxnLgrSeq" : 7,
               "Sequence" : 1,
               "index" : "032D4205B5D7DCEC8A4E56851C44555F6DC7D410AA823AE140C78674B8734DBF"
            },


One of the things this tells us is that transaction "DF530FB14C5304852F20080B0A8EEF3A6BDD044F41F4EBBD68B8B321145FE4FF" was applied in official ledger 7. Since that transaction is presumably unique to the correct ledger stream (due to the signature being partially random), any metadata we have for this transaction is likely the right metadata. That will not only recover some information about movement of funds prior to 32,570, but it will also contain another PreviousTxnID field. This could potentially allow us to continue finding transactions and reconstructing more history.

I was so focused on recovering ledgers that I didn't consider other ways to recover history.
User avatar
JoelKatz
Ripple
Ripple
 
Posts: 1859
Joined: Sun Dec 23, 2012 3:45 pm
Location: Oakland, CA

Re: Pushing genesis back to 0

Postby donch » Tue Mar 11, 2014 8:38 pm

I think this is the perfect opportunity to crowdsource the solution. Release the transactions that you have mentioned previously as having kept and we can all collectively have a look. From my analysis, there were 140 accounts which had in total 534 sequence incrementing transactions at ledger 32570. Obviously we can't generate the validations of the ledgers with the nodes' private keys as only you have access to them, but we can certainly help generating the AccountState and TransactionState trees and hashes for the ledgers...
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Re: Pushing genesis back to 0

Postby Sukrim » Tue Mar 11, 2014 9:52 pm

What does ledger 0 look like anyways? Is there any custom random element in there or is the only variable the timestamp? All ledger chains start with 100 billion XRP in the root account after all and that's it. Once we have all transactions and at least their ordering, it's just about trial and error and a much smaller numbers game to reach 32570 again from 0. All that is needed are the missing transactions (and of course any meta data that comes with them - as JoelKatz said, this can help a lot as there can be some info what has been stored where), there are not THAT many possibilities after this.

Also as said, on ripplewise some hashes and data of ledgers earlier than 32570 is available. No idea how trustworthy, but might be worth a shot too.

First things first, it would be really great to have the transactions, so we at least know what was going on in the end of December 2012. Once this is figured and sorted out, we can see if it might be feasible to bruteforce the missing data structures with this too and how much work that would mean. As far as I understand it, all you need to reconstruct a ledger is a genesis one, all transactions since then, their ordering and time stamps(?). We're currently missing all three of these, the genesis ledger might be deterministic though and the time stamps can definitely be bruteforced. For transactions it might also be bruteforceable once we know the ordering of them. A good part of them are already fixed through the PreviousTxnLgrSeq field in 32570, the remaining have to fit in between and while there are still a lot of possibilities, they are maybe manageable.

Thanks for dropping by in this topic by the way! :)
Sukrim
 
Posts: 1826
Joined: Mon May 20, 2013 10:44 am

Re: Pushing genesis back to 0

Postby donch » Tue Mar 11, 2014 10:13 pm

If it helps, I have code that can parse all transactions, inner nodes, ledger entries and ledger headers from a dump of a leveldb/hyperleveldb/rocksdb nodestore. So if all you actually have is a frozen nodestore from around 32570, I can process it down into its constituent parts probably more easily than you might be able to by having to write some custom C++ and include in parts of rippled...

Share whatever you have :-)
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Re: Pushing genesis back to 0

Postby JoelKatz » Tue Mar 11, 2014 11:09 pm

Sukrim wrote:What does ledger 0 look like anyways? Is there any custom random element in there or is the only variable the timestamp? All ledger chains start with 100 billion XRP in the root account after all and that's it. Once we have all transactions and at least their ordering, it's just about trial and error and a much smaller numbers game to reach 32570 again from 0.
The problem is that it will be hard for us to know if we're right. We can build a ledger 0, but how will we know if it's the right one? We don't know the hash of the genesis ledger.

Hey, I just thought of something. What if we found leaf nodes that had blocks of ledger hashes? Any such node that had at least one hash that was known to be in the chain would almost certainly have all its other hashes also in the chain.

Also, we have the hash of every 256th ledger, starting with 256, since it's in ledger 32,570.

And if we have the hash of both ledger N and ledger N-1, the chance of being able to recover ledger N goes *way* up. If we have its ledger hash state node, then it's also much more likely to be possible. We may recover the ledgers yet!
User avatar
JoelKatz
Ripple
Ripple
 
Posts: 1859
Joined: Sun Dec 23, 2012 3:45 pm
Location: Oakland, CA

Re: Pushing genesis back to 0

Postby donch » Tue Mar 11, 2014 11:19 pm

JoelKatz wrote:Hey, I just thought of something. What if we found leaf nodes that had blocks of ledger hashes? Any such node that had at least one hash that was known to be in the chain would almost certainly have all its other hashes also in the chain.

Also, we have the hash of every 256th ledger, starting with 256, since it's in ledger 32,570.

And if we have the hash of both ledger N and ledger N-1, the chance of being able to recover ledger N goes *way* up. If we have its ledger hash state node, then it's also much more likely to be possible. We may recover the ledgers yet!


If you want to extract all the LedgerHashes skip lists from your 32570 node store, you can do:

Code: Select all
../rocksdb/ldb --db=path/to/leveldb_like_dir dump --hex | egrep "==> 0x[0-9|A-F]{18}4D4C4E00110068"


You need to build RocksDB separately to get the ldb tool, but it is extremely useful :-)

Edit: Or alternatively, make public a gzip of the db directory that you have :-) I've done enough reverse engineering of rippled to actually want to do this :-)
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Re: Pushing genesis back to 0

Postby donch » Tue Mar 11, 2014 11:27 pm

Just re-reading what you've written. Are you saying that the node store contains all the correct ShaMapNodes, but you just don't know the hash/index/nodeid (these terms seem very interchangeable in rippled source code!) of the LedgerMaster nodes? Or are you saying that the LedgerMaster nodes never got saved into the nodestore?
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Re: Pushing genesis back to 0

Postby Sukrim » Tue Mar 11, 2014 11:33 pm

JoelKatz wrote:The problem is that it will be hard for us to know if we're right. We can build a ledger 0, but how will we know if it's the right one? We don't know the hash of the genesis ledger.

We can create a ledger 0, use its hash for ledger 1, use its hash for ledger 2 etc. until we reach a ledger we know the hash of. I thought that would be 32569, but apparently that could be as small as 256.

This means we would need to try to create one ledger 0 for every 10 seconds of December 21st, build ledgers until 256 and one of these (in case there were no transactions in between) must fit the known hash for ledger 256. Since there were transactions, these need to be factored in and applied in the correct ledgers. this makes it more difficult (since the ledgers then contain more elements or we might not know if a transaction was applied in ledger 111 or 112 or 113 etc.) but still possible, since there are only a few dozen potential transactions in a few dozen potential places anyways and a few ten thousand possible timestamps for ledgers. Building a couple million small ledger chains until one fits might take some time, but definitely not forever.
Sukrim
 
Posts: 1826
Joined: Mon May 20, 2013 10:44 am

PreviousNext

Return to Developers

Who is online

Users browsing this forum: No registered users and 4 guests
cron