[Sovereign Keys] Parameters for a hash tree

[Erik Tews]

Am Montag, den 21.05.2012, 15:30 -0700 schrieb Peter Eckersley:
> I am persuaded that hash trees are a good addition to the protocol.

Thanks

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

OK, I commented on this:

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

In a nutshell, you can use the intermediate signatures I suggested. If
you do so, you just cache these 65536 intermediate signatures in RAM (a
few MB) and store the hash tree up to this intermediate signature on
disk with the SK database entry. This adds about 416 bytes to each
database entry (keep in mind that this adds redundancy to the data, but
this will help to increase the performance).

Now, there is no noticeable performance decrease, because you get the
hash tree with the same read you use to get the SK database entry. Only
the number of entries that can be cached in memory is slightly
decreased, because a entry is slightly larger and less entries fit in
the memory cache.

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