[Sovereign Keys] Parameters for a hash tree

[Peter Eckersley]

I am persuaded that hash trees are a good addition to the protocol.

I only have one niggling concern about them, which is the IO/memory requirements
for mirrors, which are required to compute the alternative hash paths
necessary to answer each client's query.

Keeping the entire hash tree in memory for this purpose might become an
unreasonable requirement for mirror operators one day (for 2x10^8 timeline
entries and 256 bit hashes, that's 100GB of RAM), but computing everything on
the fly sounds problematic too.  However, I think there are plausible caching
strategies where you keep the topmost and frequently-queried portions of the
hash tree in RAM, but go to disk 1-3 times for unusual queries.


On Mon, Apr 16, 2012 at 04:59:20PM +0200, Erik Tews wrote:
> Hi
> 
> I did some calculations how one could build a hash tree to verify that a
> response from a mirror is really correct and based on a current database
> from a timeline server. I pushed some notes to github:
> 
> https://github.com/eriktews/Sovereign-Keys/commit/f1983f6ad810c7c28fa27041d6bf710d2f1e0cca
> 
> And you can find a google docs spreadsheet online where you can play a
> bit with the parameters:
> 
> https://docs.google.com/spreadsheet/ccc?key=0Ak_UqCvQqMRAdGVMTU9KRVZLQUFKUENyZzdfYUkzUEE
> 



-- 
Peter Eckersley                            pde at eff.org
Technology Projects Director      Tel  +1 415 436 9333 x131
Electronic Frontier Foundation    Fax  +1 415 436 9993