Re: [Asrg] 3 (Message Verification) - Viability of hashcash-based signatures (was: E-postage from first principles)

[Jonathan Morton <[e-mail]>]

> - The stamp optionally includes a signature to facilitate 
> whitelisting.  This can reduce the hashcash demanded from regular 
> correspondents to as low as 8 bits, which is computationally 
> trivial...
>
> ...If nobody happens to have a Z80 and a compiler to hand, I'll put in 
> some work and try it for the 6502 instead - I have a handful of old 
> BBC Micros lying around.

To answer my own question, I've worked out that a 6502 can process an 
SHA-1 block in about 40000 cycles, which compares surprisingly well to 
the 68030 (and begs an investigation into precisely why the '030 is so 
inefficient).  This is completely untested code - I didn't even type it 
into the machine, just worked out the timing piecemeal from the 
assembly manual - but the ballpark figure should be accurate.

To put this in perspective, it means that my 1982-vintage BBC Micros 
(with 2MHz 6502 chips) should be able to mint 8-bit hashcash in about 5 
seconds on average, and most other 8-bit accumulator machines 
(including the Z80 family) should be comparable.  This, in turn, means 
that my whitelist-grade signature scheme should be computationally 
feasible for pretty much every "computer" capable of running a TCP/IP 
stack.  This encourages me to continue working on a more detailed spec 
for discussion.

Code size may be more of a problem, however, as the 40000-cycle 
performance assumes a fairly unrolled-loop code configuration, which 
consumes a significant portion of a 16-bit address space (exact size 
not calculated, but 4-8KB is possible).  It also assumes a fixed area 
of RAM, including 25 bytes of zero page and 340 bytes elsewhere, is 
available and hard-coded into the program.  For machines with a paged 
ROM system and a half-decent memory map, this shouldn't be a serious 
problem, but for some microcontrollers it may require a tradeoff of 
code size and/or position-independence against performance.

In any case, it is certainly no problem for any truly 32-bit machine.

--------------------------------------------------------------
from:     Jonathan "Chromatix" Morton
mail:     [e-mail]
website:  http://www.chromatix.uklinux.net/
tagline:  The key to knowledge is not to rely on people to teach you it.


_______________________________________________
Asrg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/asrg