Pushing genesis back to 0

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

Pushing genesis back to 0

Postby Sukrim » Tue Sep 03, 2013 7:16 pm

As written by JoelKatz 2 months ago (https://bitcointalk.org/index.php?topic ... msg2352658):
Unfortunately, due to a server bug, some history was lost. You can't trace all the way back to the genesis ledger. You can trace back to ledger 32,570. All history after the beta was opened is available. All that was lost was the ledger headers -- all the transactions are still available, so there's some hope that the history may still be recovered.


Well, how about we actually do this!? :)

There is still an issue with recovering the full headers for these 32570 headers (0-32569) that would require a bit of computational power:
The only real lead is that the header hash of 32569 is 60A01EBF11537D8394EA1235253293508BDA7131D5F8710EFE9413AA129653A2 (see the header of 32570 for that).

Depending on how these old transactions are formatted/stored, it might be hard to find out in which exact ledger they were actually stored. The accountState list of 32570 hints at least at quite a few of them + their ledger height and there are max. 388 transactions since "real" genesis anyways, Still if these old transactions don't include their ledger height, there might be still quite a bit more guesswork (=brute force) required.

I would hope that ledger height is actually known for each of these tx (afaik node_db stores this along with the raw tx), so the only unknown parts from the ledger header chain would be the timestamps. These could be actually bruteforceable (I've read somewhere that the genesis ledger 0 was created sometime on December 21st, so there are only 8640 possible starting points), it would be just a matter of creating header chains with increasing timestamps (and probably slightly varying starting times + delays/imperfections in between) until one ends up at 60A01EBF11537D8394EA1235253293508BDA7131D5F8710EFE9413AA129653A2. Still a lot of CPU cycles to be wasted, but definitely not impossible.

In case you were wondering, there is no real way to trace back from 32570 unfortunately, as 32569 contains the hash of 32568 and that is definitely a much harder target to brute force than calculating a few thousand hashes in a chain starting from 0.

As far as I understand it, once this endeavor actually yields a result (unfortunately there will be 0 sign of progress and no hints that everything was done correctly until the chain is actually found - one can only try the same method for some later ledgers for testing purposes to verify it might work) it should be possible to feed this missing chain back to rippled and it will automatically back trace and publish the REAL genesis ledger 0 with 100 billion XRP henceforth.

Another hope would be that someone still has some older ledger headers (pre-32570) or at least ledger hashes. Wisepass for example seems to report sometimes weird, sometimes quite plausible values for ledgers before 32570. This would (together with the transactions) allow to shorten the bruteforcing required significantly if that data can be trusted (eventually once still needs to arrive at 32570 with the correct hash).

Still the first and most important ingredient for this would be the set of the <=388 missing transactions with as much meta data as possible (especially ledger height). Could please someone with access to them (querying s1.ripple.com for transactions referenced as previous transactions in the accountState of 32570 gives no results... which is a bit worrying!) post them here please? JoelKatz, I summon thee!
Sukrim
 
Posts: 1825
Joined: Mon May 20, 2013 10:44 am

Re: Pushing genesis back to 0

Postby JoelKatz » Tue Sep 03, 2013 9:43 pm

The trick is figuring out which transactions went in which ledgers, making sure to replicate the transaction logic that was in used at the time, and (the hardest part) to build the right header for ledger X, you need to know the hash of ledger X-1, which makes working backwards hard. On the bright side, most of the time you can assume the previous ledger closed 20 seconds ago and had no transactions.

I do have all the records from that time and a tool that analyzes what's missing. I can't find any output from the tool though, so I'll have to get the reconstruction environment working again to give a status report. I can make all the data I do have public.
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 yvv » Tue Sep 03, 2013 10:26 pm

I don't get how a history in distributed ledger can be lost? Was there just one copy?
yvv
 
Posts: 1269
Joined: Sat Apr 13, 2013 11:47 am

Re: Pushing genesis back to 0

Postby Sukrim » Wed Sep 04, 2013 2:55 am

JoelKatz wrote:The trick is figuring out which transactions went in which ledgers, making sure to replicate the transaction logic that was in used at the time, and (the hardest part) to build the right header for ledger X, you need to know the hash of ledger X-1, which makes working backwards hard. On the bright side, most of the time you can assume the previous ledger closed 20 seconds ago and had no transactions.

Yes, that's what I thought - bruteforcing forwards towards 32570 s probably much easier than working backwards towards 32569 as there is the big question mark of the ledger hash for 32568 which is far more difficult to crack than trying all useful combinations of timestamps and transactions for the ledgers since genesis.

The header for the genesis block 0 should be known and only vary in the timestamp field anyways.

JoelKatz wrote:I do have all the records from that time and a tool that analyzes what's missing. I can't find any output from the tool though, so I'll have to get the reconstruction environment working again to give a status report. I can make all the data I do have public.

That would be great - I bet the first thing criticised after releasing any source code for rippled would be then "but we can't see the crucial first few hundred transactions!". I anyways plan to learn more about the transaction format etc. so this would be a great exercise.

PS:
s1.ripple.com reports since a few days that it also has the ledgers 1-2 complete. I doubt that this is erally the case and when querying for them, they do not return timestamps for example, something I find kinda strange.
Sukrim
 
Posts: 1825
Joined: Mon May 20, 2013 10:44 am

Re: Pushing genesis back to 0

Postby JoelKatz » Wed Sep 04, 2013 5:02 pm

yvv wrote:I don't get how a history in distributed ledger can be lost? Was there just one copy?
There was a bug that caused ledger headers not to be properly saved. All the servers running at the time had the same bug. Transactions were properly saved as were, I believe, all the nodes inside the ledgers. Only the ledger headers are missing. I tried to reconstruct the headers but got stuck on 32,569.
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 Sukrim » Tue Sep 17, 2013 9:45 am

Any news/database dumps/code that I missed? My holidays are nearly over and I'd still like to tackle this challenge...
Sukrim
 
Posts: 1825
Joined: Mon May 20, 2013 10:44 am

Re: Pushing genesis back to 0

Postby Sukrim » Tue Oct 01, 2013 10:52 am

JoelKatz wrote:I do have all the records from that time and a tool that analyzes what's missing. I can't find any output from the tool though, so I'll have to get the reconstruction environment working again to give a status report. I can make all the data I do have public.

Please do so, even if it is messy and/or hard to work through...
Sukrim
 
Posts: 1825
Joined: Mon May 20, 2013 10:44 am

Re: Pushing genesis back to 0

Postby Sukrim » Fri Jan 03, 2014 12:11 pm

JoelKatz wrote:I do have all the records from that time and a tool that analyzes what's missing. I can't find any output from the tool though, so I'll have to get the reconstruction environment working again to give a status report. I can make all the data I do have public.
Now that the ledger is more than 1 year old, could you please release this data?
Sukrim
 
Posts: 1825
Joined: Mon May 20, 2013 10:44 am

Re: Pushing genesis back to 0

Postby donch » Fri Jan 03, 2014 1:11 pm

Is this not just a combinatorical problem? If there are less than 400 transactions, isn't it just a case of iterating all possible transaction orders until a ledger is achieved which yields a state which is equivalent to the one at 32570? If so, only the single hash at 32569 needs to be brute forced, which admittedly does sound complicated...

I guess if transactions had a submitted time field, like ledger headers have a CloseTime field, this would have been a considerably easier task :-)

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...

P.S. if the raw transactions for 0-32570 are to be released, can this be in conjunction with a full dump of all raw transactions? I've been asking on this forum, IRC and Github or access to the data. Rippled does not get this data fast enough and it is vital for third party software development. Sorry to sound like I'm moaning, I just need the data :-)
donch
 
Posts: 796
Joined: Mon Nov 18, 2013 8:07 pm

Re: Pushing genesis back to 0

Postby Sukrim » Fri Jan 03, 2014 4:32 pm

There are already a few earlier transaction hashes known (they are referenced in ledger 32570), however there are still a few that are not easily reconstructed - and since the signature part of them should better not be bruteforceable (else we'd have a problem!) there is no real way of reconstructing history by just guessing how each transaction might have looked like.

Even if I get the ordering and values of transactions completely right, as far as I understand it the hashes of these transactions also depend on the signature of the sender and this means that it is currently impossible to bruteforce. Without the signatures on these transactions there is nothing you can realistically do, ideally JoelKatz would either work on his secret stuff on his own and just push it to the RippleLabs servers soon or finally publish the database dump or whatever he seems to have of these old transaction and node data for others to try. Once I have the transactions, I can try the combinatorial approach, as suggested already (ordering should be quite clear anyways, it's mostly a matter of which ledger has which transactions + account state). Until then - 0 chance.


Rippled (dev branch) is getting better in fetching history reasonably fast by the way! :)
You might wanna try to compile and run a bleeding edge version. Unfortunately my Windows builds still error out after a while and I was still not able to really debug them (my Linux machines are too slow I/O wise for rippled and I dislike VisualStudio, also I'm not too sure what the problem really is and how to debug an application that randomly crashes inconsistently, sometimes after hours or days).
Sukrim
 
Posts: 1825
Joined: Mon May 20, 2013 10:44 am

Next

Return to Developers

Who is online

Users browsing this forum: No registered users and 6 guests