[hashcash] memory vs cpu bound (Re: Re: Sample code for Dworkian memory-bound POW)
- From: Adam Back <adam@xxxxxxxxxxxxxxx>
- To: hashcash@xxxxxxxxxxxxx
- Date: Mon, 24 May 2004 09:29:16 -0400
On Mon, May 24, 2004 at 07:47:25AM -0400, Eric S. Johansson wrote:
> proof of work puzzles are all about transistors. The number of
> transistors you can use for computation and storage. Dworkian
> puzzles can be thought of as hashcash whose storage requirements
> exceed the size of today's cache. As soon as you can put enough
> memory on to the cache, memory bound POW loses its advantage.
Yes. So that is the trade-off with Dwork MB proof-of-work: there is
smaller time to compute discrepency between low-end and high-end
machines, but it ties down memory to the amount which is a balance
between the memory of a small device, and the cache of a high-end
device. There is some conflict there, some high-end processors have
multi-megabyte caches.
> another question is can the MB POW be solved faster if you shrink
> its memory requirements and put it into cash (i.e. a spammer cheat)
That is essentially what happened with the first PoW paper by Abadi et
al, "Modereately Hard, Memory-bound Functions"; the 2nd paper by Dwork
et al starts by breaking the first scheme. Breaking in the sense of
showing a space-time tradeoff, where you can use a fast processor to
get away with having less memory than intended.
But both the 1st and 2nd approaches try to prevent you doing this.
But the other argument is economic, and if you read the last paragraph
from the Dwork et al paper, they conclude perhaps hashcash-like is
better economically:
| At first blush egalitarianism seems like a wonderful property in a
| pricing function. However, on reflection it may not be so
| desirable. Since the approach is an economic one it may be
| counterproductive to design functions that can be computed just as
| quickly on extremely cheap processors as on supercomputers after
| all, we are trying to force the spammers to expend resources, and it
| is the volume of mail sent by the spammers that should make their
| lives intolerable while the total computational effort expended by
| ordinary senders remains benign. So perhaps less egalitarian is
| better, and users with weak or slow machines, including PDAs and
| cell phones, could subscribe to a service that does the necessary
| computation on their behalf. In any case, small-memory machines
| cannot be supported, since the large caches are so very large, so in
| any real implementation of computational spam fighting some kind of
| computation service must be made available.
ie if you make low-end machines not that much slower than high-end
machines, that helps spammers because they just go buy low-end
machines.
Adam
Other related posts:
- » [hashcash] memory vs cpu bound (Re: Re: Sample code for Dworkian memory-bound POW)
