[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Asrg] About that e-postage draft [POSTAGE]

On Feb 20, 2009, at 3:25 PM, Bill Cole wrote:
The bottom line is, redeeming a million tokens per second is practical with processing delay not much greater than network latency. (This was 
not true ten years ago...)
I think I'd quibble with details on that, but they really are not all that 
important.
This is a problem that should be subject to a simplified thought experiment. If you make extremely unrealistic positive assumptions about processing, storage, and bandwidth but recognize that many RTT's between redemption clients and servers will be above 100ms, most above 10ms, and essentially all above 1ms, it is very hard to design a logical system (never mind a collection of hardware) that will handle a million redemption requests per second in a worthwhile manner (i.e. not repudiate valid tokens or validate bogus or redeemed ones by design) when the request stream is being engineered to break the system by parties with tens of thousands of hijacked machines at their disposal.
There are many problems with epostage - fundamentals, social problems and implementation - but this particular aspect isn't one, I don't think. It's a trivially parallelizable problem.
The reliability (SPoF), economics, business and usability issues are likely to be much more of a problem.
I'm pretty sure that I'm not the best systems analyst/designer on this list. I certainly hope I'm not the best one to have thought about e- postage. I'd be happy to learn from a master how it is in fact possible to make an ideally simplified minimal system like this work as a starting point for how to assemble a more complex system that has more elements of reality in it. I think (but may be wrong!) that it isn't possible to design a system that will be theoretically capable of correctly handling a million redemption requests per second of which ~90% are the result of someone working to break the system. 


It's fun to consider, though.
Using your numbers - one million redemption requests a second of which at least 90% are invalid, leads to 100,000 outstanding valid requests per second, which would give around 250 billion outstanding stamps at any one time, if we expire them after a month (expiring would likely involve voiding the unused stamps and issuing new ones in the same amount, but that's a business issue, and doesn't affect the redemption requirements).
Use private-key cryptography to ensure that you reject any stamp you didn't create. This is easy to do in hardware, or to parallelize should you need to. Pick enough machines or asics to meet your throughput goal. (That might well be one).
Hash the stamp to one of a number of redemption machines. This is "just" a network problem.
At each redemption machine, look up the stamp an "I've seen this" associative array. If you've seen it, reject the stamp, otherwise accept it. This is arbitrarily scalable, just by adding enough redemption machines that the memory access time to look up the entry in the associative array is enough to meet your throughput goal, and the size of the number of outstanding stamps fits in the storage space of the machine. Assuming there's a serial number in each stamp, your associative array could simply be 250 gigabits of RAM, so again it's not going to be many machines, maybe one, to do in software.
To me it feels like the hard bit of this is handling a million packets in and out per second reliably, along with the overhead of providing robustness and redundancy, rather than the redemption itself. 

Cheers,
  Steve