On 2009-02-23 00:59:10 -0500, Bill Cole wrote:
> Peter J. Holzer wrote, On 2/22/09 6:53 AM:
> >On 2009-02-21 19:07:09 -0500, Bill Cole wrote:
> >>Steve Atkins wrote, On 2/20/09 7:26 PM:
> >>>On Feb 20, 2009, at 3:25 PM, Bill Cole wrote:
> >>[Quoting John Leslie]
> >>>>> 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.
> >>I guess maybe one detail is...
> >>
> >>If the processing delay for every redemption attempt is of the same order
> >>of magnitude as irreducible network latencies, i.e. tens to hundreds of
> >>milliseconds, handling a million one-use token redemption attempts per
> >>second is absolutely hopeless.
> >
> >I think John meant "processing delay" as seen from the client. So this
> >includes a) the time to send the request (tens to hundreds of
> >milliseconds), b) the time it takes the server to process the request
> >(sub-milliseconds?) and c) the time for the response to get back to the
> >client (again tens to hundreds of milliseconds).
> >
> >The number of requests a server can process per second is mostly
> >determined by b). The communication delays only increase the number of
> >open but idle connections (which may also be a problem).
>
> Just in case anyone misconstrues your use of the term "connections":
>
> Using one TCP connection per transaction for a system that needs to
> complete a million transactions per second across the Internet would be a
> ridiculous design flaw.
>
> I therefore assume that you mean "connection" in a more generic sense,
I was generally deliberately vague, but in this paragraph I actually
meant a TCP connection. I assume that many requests can be sent over the
same TCP connection (just as you can send many emails over a TCP
connection using SMTP, and many HTTP/1.1 requests can be sent over a TCP
connection). But many clients won't need to do that. For an MX for a
small personal domain it simply makes no sense to keep permanent TCP
connections to all banks, just because it might need to redeem a token
some time in the next hours. It would close the connection after a
single request unless it needs to redeem another token within a very
short time. For such single-request connections the minimum time is
determined by the RTT.
> and
> indeed that was the core of my argument: if the server has to retain state
> on transactions for typical Internet RTT's
It doesn't, except at the TCP level - naturally, the kernel needs to
keep state for all open TCP connections. But the redeeming agent doesn't
nee
> for a common class of
> transaction, concurrency is likely to become a problem in and of itself.
>
> >So if checking a single token takes 1 millisecond (rather conservative,
> >IMHO), one server can check roughly 1000 tokens per second, so a server
> >farm of 1000 servers can check 1 million tokens per second. That doesn't
> >seem "absolutely hopeless" to me. It's certainly technically possible,
> >although I'm sceptical whether it's economically feasible.
>
> Your hand waves so elegantly when forming the phrase "server farm of 1000
> servers."
;-)
>
> I believe that dividing the workload between multiple front-end machines
> will either create unworkable latencies in the back end to assure that all
> of the front ends see a coherent state database for tokens or else will
> create vulnerabilities that will allow any significant botnet operator to
> effectively eliminate chunks of the system at will. Hand-waving a 1000-node
> server farm doesn't persuade me that I'm wrong.
>
>
> >>>>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).
> >
> >I expect most tokens would be redeemed pretty soon, so you won't have
> >to keep them around for a month, at least not for real-time checking.
>
> Someone who thinks e-postage is workable
I don't think e-postage is workable. AFAICS an early adopter has no
advantages, but a lot of disadvantages. Therefore, e-postage won't
happen in the SMTP world.
> should make a real specification
> that defines "pretty soon" in concrete terms that would support an actual
> protocol design that expires tokens.
As a purely academic exercise, here's a sketch of a protocol and a
server implementation. If anybody wants to run with it, feel free:
Protocol:
Based on TCP. Simple request/response structure, Server and Client
can close the close the connection at any time.
A token consists of two parts, the first is a domain name, the
second is opaque.
The server for redeeming a given token can be found via a SRV
lookup.
Requests:
redeem token account
the token is redeemed and the value is transferred to
account.
responses:
redeemed (+ value)
unknown token (possible reasons: forged or mangled
token, token has already been redeemed, ...)
temporary error (possibly with an estimate when a retry
might make sense)
mint account amount
Create a new token with given value and deduct the amount
from the account. (This needs some kind of authentication,
of course) There may be a variant which creates $n tokens at
once.
response
new token
insufficent funds
account doesn't exist or client doesn't have access
temporary error
Implementation of redemption server:
Keep all valid tokens in memory. Multithreaded to take advantage of
multi-core systems (but almost certainly not 1 thread per connection
- because there will be lots (hundreds of thousands?) simultaneous
TCP connections).
When a redemption request is received, the look up the token in
memory. If it isn't there, send an "unknown token" reply.
Otherwise attempt to lock the token. If this fails, send a
"temporary error" reply to the client.
Otherwise write a "this token has been disabled, transfer $value
$currency to $account" record to a journal, invalidate the token in
memory and unlock it, and finally send a "redeemed" response to the
client.
I think current PC hardware can easily handle several tenthousand
requests per second. I'm less sure about the number of concurrent
TCP connections and connection requests a modern OS can handle.
Redemption Client:
If the client (=SMTP server) needs to redeem a token, it extracts
the host name and does a SRV lookup to find the server. If it
already has a TCP connection to that server, use that, otherwise
open a new connection. A temporary failure can be passed on to the
SMTP client.
Minting:
Each server only mints tokens which it will redeem itself - this
eliminates the need to distribute knowledge about the tokens, but
may create an uneven load. Load balancing is left as an exercise for
the reader.
> > If the
> >redemption fails, the client can simply buy another stamp and send the
> >message again. Delivery of that particular message was now twice as
> >expensive as that of an average message, but if that only happens
> >infrequently it doesn't matter. If it does happen frequently for a
> >particular bank, the affected client(s) will probably be reconfigured to
> >prefer tokens from other banks.
>
> There's not any strong reason for such a problem to be bank-specific. It
> could just as easily be tied to where the redemption attempt is coming from.
If client C has a problem communicating with bank B1, but not with bank
B2, it doesn't matter whether it is the fault of B1 or of C. C will
prefer to use B2.
> >So if your 50k clients try to redeem the same token at the same time,
> >one of these 50k requests will be the first to be processed by the
> >server. The server marks the token as redeemed and sends a positive
> >reply to the client. The other 49999 requests will be denied. If
> >(because of network congestion caused by the 50k nearly simultaneous
> >requests) the reply never reaches the "lucky" client, the token will be
> >lost.
> >
> >Sending 50k requests with the same token is garantueed to yield at most
> >one positive reply in this case. It isn't viable for someone who wants
> >to send many messages, but it may be a viable DoS attack.
>
> Botnet spammers have a history of attacking anti-spam systems. Any mailing
> tactic capable of crippling an e-postage system, even temporarily, will be
> tried.
Of course. But there is no system which is immune to DoS attacks, and I
think DoS attacks and double-spending are sufficiently different
problems that they should be considered separately.
> >>2. If the stamp is left as unredeemed while waiting for the client ack of
> >>success, stamp "reuse" becomes a question of how many redemption
> >>decisions can be made per client RTT.
> >>
> >>The server may have to defer many thousands of clients for scores of
> >>milliseconds while waiting for one to send an ack.
> >
> >Yes, but it only needs to defer those clients which sent a request with
> >the same token. It can process lots of other tokens in the meantime.
>
> If designed correctly, that might be the case. What is that design again?
See above for a few ideas. I won't do a more detailed specification for
two reasons:
1) As I mentioned above, I don't think e-postage has a market in the
SMTP world, so I won't waste time to implement it, and I won't waste
time thinking about details of something I don't plan to implement.
2) If I did change my mind and wanted to implement it, I wouldn't post
a detailed description to a public mailing list :-).
hp
--
_ | Peter J. Holzer | Openmoko has already embedded
|_|_) | Sysadmin WSR | voting system.
| | | hjp at hjp.at | Named "If you want it -- write it"
__/ | http://www.hjp.at/ | -- Ilja O. on community at lists.openmoko.org
Attachment:
signature.asc
Description: Digital signature