[Cfrg] network traffic

["D. J. Bernstein" <[e-mail]>]

Kurt Roeckx writes:
> Depending on who you ask you might get a different
> answer, but I doubt many people here care about bandwidth.

I care very much about network traffic---although it has to be
quantified and put into context, just like CPU time.

As a concrete example, suppose your server resources are ten quad-core
3GHz CPUs and a 100Mbps network connection. Each microsecond the CPUs
will perform a total of 120000 cycles of computation while the network
connection will transmit 100 bits, i.e., 12.5 bytes.

Case study 1: Suppose you save 20000 cycles of computation by replacing
a compressed 32-byte point with an uncompressed 64-byte point. You're

   * saving 0.17 microseconds of computation but
   * costing 2.56 microseconds of network capacity.

Is this a worthwhile tradeoff? The factor 15 imbalance suggests an
answer of "no" (unless your ten servers cost fifteen times more than
your network connection, which I doubt). This isn't a guarantee---maybe
at this instant your CPUs are fully loaded while your network isn't---
but my experience is that if you need to reduce CPU time then there will
be many better ways to reduce CPU time in other parts of the system with
less cost to the network.

For me security and simplicity are ample reasons to require compression,
but this example still illustrates how to think about the performance
impact.

Case study 2: Suppose you save 200000 cycles of computation by switching
from 65-byte numsp512t1 points to 66-byte E-521 points. You're

   * saving 1.67 microseconds of computation but
   * costing 0.08 microseconds of network capacity.

Is this a worthwhile tradeoff? The factor 20 imbalance the other way
suggests an answer of "yes" (unless your network connection costs twenty
times more than your ten servers, which I doubt). This again isn't a
guarantee---maybe at this instant your network is fully loaded while
your CPUs aren't---but my experience is that there will be many better
ways to reduce network traffic in other parts of the system with less
cost to the CPUs.

I should note that a single numsp512t1 coordinate uses only 64 bytes,
but sending a compressed second coordinate spills over into another
byte. Of course, a single-coordinate ladder skips this compressed bit;
there are various cheap tricks to squeeze more bits out of keys; and one
can always squeeze out another bit by doubling the key-generation time.
Any method of saving 1 bit will squeeze numsp512t1 into 64 bytes; any
method of saving 4 bits will squeeze E-521 into 65 bytes; any method of
saving 9 bits will squeeze numsp512t1 into 63 bytes; etc.

---Dan