[tahoe-dev] Hash based Signatures for Tahoe LAFS

[Zooko O'Whielacronx]

Hello Julian:

Thank you for your letter. I have time tonight to respond to only one bit of it:

2011/2/16 Julian Wälde <jwaelde at cdc.informatik.tu-darmstadt.de>:
>
> There is no way in hell that these stateless merkle schemes can compete
> with ecdsa or rsa in terms of speed/signature size ... the fastest
> stateless scheme (meaning that the privatekey does not change with every
> signature) was still 5 times slower than rsa4k and had ~40kb per signature.

Hm, I guess "competitive with ECDSA or RSA" is the wrong measure. How
about "efficient enough for all practical purposes" instead?

Let's see, there are basically three places where we might need to do
digital signatures:

1. A Tahoe-LAFS gateway running locally to a user, e.g. on their
workstation, laptop, or handheld.

2. A Tahoe-LAFS gateway running remotely, and possibly serving many
users at once.

3. A Tahoe-LAFS storage server (if, in the future, storage servers
verify digital signatures on shares, which I hope they do in order to
provide simple and strong resistance against denial-of-service by
scribbling attacks).

In particular, I want to be able to do verifications on a cheap little
low-power 32-bit ARM storage servers. Let's say as a
shooting-from-the-hip goal that I would like to do 50 verifications
per second. I come up with that number by the following sequence of
rough estimates. (The roughness of some of the numbers is indicated
with *'s.)

The number of disk seeks that the storage server would have to do to
accept a share would be 4 **, and one seek-and-read or seek-and-write
takes about 20 ms * [1], so a single spinning disk can't really accept
upload of more than 12.5 shares per second. One cheap ARM server can
manage 4 * spinning disks, so one cheap ARM server might be able to
accept upload of 50 shares per second.

A cheap ARM server might have a 1.2 GHz * CPU, so that gives us a
budget of 60 million instructions per upload, if we could spend 100%
of the CPU time doing verifications. Let's guess that we need 50% ***
of the CPU time for other tasks, so now we have only 30 million
instructions left to do signature verification on each share as it is
uploaded. Is that achievable with hash-based digital signatures?

For what it is worth, I suspect that the other two deployment
situations will have even looser constraints on the speed of the
digital signature algorithm. The personal-to-one-user gateway doesn't
have that high of a load of requests -- its constraint is more about
not imposing a time penalty that is noticeable on a human scale (tens
of milliseconds) and not wasting the user's battery life. The
many-users gateway can perhaps have more specialized hardware such as
a high-powered 64-bit CPU or a GPU. Or alternately the many-users
gateway can be horizontally load-balanced into many small, cheap
gateways, thus making it have similar performance needs as the cheap
storage servers.

The size of the signature in a hash-based signature system maybe be a
worse problem than the CPU time to verify it.

Regards,

Zooko

[1] http://www.storagereview.com/western_digital_caviar_green_3tb_review_wd30ezrsdtl

P.S. Apologies if there are glaring errors or omissions in the above.
It is late! I've now satisfied my goal of at least one reply to
tahoe-dev per night. :-)