Why are exactly 4 bit windows used in the lookup table of libsecp256k1 to speed up point multiplications?

Question

From the Readme of secp256k1 we can see the following:

Use a precomputed table of multiples of powers of 16 multiplied with the generator, so general multiplication becomes a series of additions.

I was wondering why in particular the table used precomputed table of multiples of 16? I would have expected a higher number or a more dynamic approach which includes dynamic caching.

Let me elaborate a little bit:

With multiples of 16 we always need 4 bit computed in the table. meaning we have 256 / 4 = 64 buckets with 16 entries for each bucket.

Let n be the number of bits in a window for which we compute powers of g this would result in the general formula for the amount of precomputed values in our table for n > 1:

256 / n * 2 ^ n

with n = 4 we have 64 * 16 = 1024 entries.

When choosing n = 8 we would have 32 * 256 = 8192 entries. However when actually computing a multiplication we would only need 32 additions instead of 64. creating a speedup of a factor of 2 for 8 times us much memory usage of our lookup table.

With n = 16 we would have 16 * 65536 = 1048576 or 1M * sizeof(point) of main memory to have only 16 point additions when computing a multiplication.

Obviously such a big lookup table requires some time when setting up the library. Even if the table was already precomputed and in binary shipped with the library.

Anyway I was wondering for the particular choice of 4 bits. I would assume that 8 bits was better and probably even taking 16 bit windows seems fairly reasonable.

Answer 1

What you are talking about is the table used for constant time operations w/ secret values, e.g. for signing and key generation (see the heading "Point multiplication for signing"). To prevent leaking secret key data the entire column must be processed for each digit. More bits in the column increases this work exponentially. From memory, I believe that 5 bits was similar but slightly better performance on systems with big fast caches and memory busses, but worse performance on systems with slow memory.

There are other ways that we could increase performance there (e.g. constant-window NAF, or the techniques from PR546) but we don't generally consider signing/key generation performance to be terribly important. I think generally our only strong goal wrt that performance is to be no slower than less carefully developed alternative software.

You can try changing the sizes with a few lines changed in the software.

The variable time multiplies in the library use much larger tables and fancier techniques.