7-man EGTB Bounty Reborn - Infrastructure Discussion

[Kirill Kryukov]

Infrastructure is the vital part of this project, so it deserves it's own discussion thread.

Here is a very rough idea. The infrastructure should provide support for the following tasks:

1. Generation of the tables:

• Information support. Centralized database should exist to track the already constructed tables. It should be easy to see what tables have been already built, and what tables can be done next. Multi-metric support (parallel WDL and WDL50 generation).
• Logistics. It should be easy to obtain the already generated sub-endgame tables, that are necessary for building a new table.

2. Sharing the tables:

• Distribution network. Is eMule still practical? All up-to-date solutions have to be evaluated.
• Support for tracking the availability of particular tables. (Something that I have been doing manually for 6-piece sharing project). How many copies of each table are available on network.
• Support for tracking the free space. A participant tells the system "I can host another 1 TB". The system tells the participant: "Such and such tables need more copies, please download from such and such people (priority download)."

2. Remote probing:

• Cenrtalized system to probe the whole already computed dataset, even when tables are stored on thousands of computers.
• Clever load balancing. (For a dumb version, just accept a fixed N requests per minute from any host).
• Participants (those who host the tables) get some probing rate bonus (Dumb version: 10 times the limit compared to non participants).

The community has never seen anything like this before. The 6-piece Nalimov sharing project is the closest, but this time much larger problems will be solved. Is it hard? Yes, but I can dream. Is your dream same with mine?

[koistinen]

Distributed probing should be fun. One way for a server to prove to a client that an honest answer with hash function F constructed using cryptographic hash function H is this:

Code: Select all

F(T)->
  if small_enough(T)->H(T);
  else H([H(first_half(T)),H(second_half(T))]).

Client must know F(Table).
Server has a table with N levels of hashes, N set to whatever is efficient for the server.
The client asks the server for a particular location in the table.
To reply, the server loads everything in the same N-level branch of the tree, constructs the hashes for the branch and sends the small_enough part with the answer to the query together with the hash values the client needs to know the answer is true. (Binary tree.)
If the table size is 325 GB and small_enough is 325 bytes, then 29 hash values would have to be sent and so the answer would be about 1,3 kB long with 256 bit hashing, small enough to fit in a single ethernet packet but still expensive enough that it might be best to make proving an option, say let the client decide if a proof is neccessary or if the server should be trusted for the moment. The good thing about this technique is that it would not be expensive for the server. Main cost would be network bandwidth. Perhaps client could tell server it already has M levels of hashes, shortening the message considerably without requiring much storage for client.