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

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(_dot_)at         | Named "If you want it -- write it"
__/   | http://www.hjp.at/ |  -- Ilja O. on 
community(_at_)lists(_dot_)openmoko(_dot_)org

signature.asc
Description: Digital signature

_______________________________________________
Asrg mailing list
Asrg(_at_)irtf(_dot_)org
http://www.irtf.org/mailman/listinfo/asrg