<p>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 <a href="https://github.com/bitcoin-core/secp256k1/blob/master/src/ecmult_gen_impl.h#L148" rel="nofollow noreferrer">processed</a> 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.</p>

<p>There are other ways that we could increase performance there (e.g. constant-window NAF, or the techniques from <a href="https://github.com/bitcoin-core/secp256k1/pull/546/" rel="nofollow noreferrer">PR546</a>) 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.</p>

<p>You can try changing the sizes with a few lines changed in the software.</p>

<p>The variable time multiplies in the library use much larger tables and fancier techniques.</p>

CC BY-SA 4.0
2019-03-12T10:49:01.697Z
2019-03-12T10:54:05.617Z
2019-03-12T10:54:05.617Z
G. Maxwell
<p>From <a href="https://github.com/bitcoin/bitcoin/tree/bccb4d29a8080bf1ecda1fc235415a11d903a680/src/secp256k1" rel="nofollow noreferrer">the Readme of secp256k1</a> we can see the following:</p>
<blockquote>
<p>Use a precomputed table of multiples of powers of 16 multiplied with the generator, so general multiplication becomes a series of additions.</p>
</blockquote>
<p><strong>I was wondering why in particular the table used precomputed table of multiples of <code>16</code>?</strong> I would have expected a higher number or a more dynamic approach which includes dynamic caching.</p>
<p>Let me elaborate a little bit:</p>
<p>With multiples of <code>16</code> we always need <code>4</code> bit computed in the table. meaning we have <code>256 / 4 = 64</code> buckets with <code>16</code> entries for each bucket.</p>
<p>Let <code>n</code> be the number of bits in a window for which we compute powers of <code>g</code> this would result in the general formula for the amount of precomputed values in our table for <code>n &gt; 1</code>:</p>
<p><code>256 / n * 2 ^ n</code></p>
<p>with <code>n = 4</code> we have <code>64 * 16 = 1024</code> entries.</p>
<p>When choosing <code>n = 8</code> 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.</p>
<p>With <code>n = 16</code> we would have <code>16 * 65536 = 1048576</code> or <code>1M * sizeof(point)</code> of main memory to have only 16 point additions when computing a multiplication.</p>
<p>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.</p>
<p>Anyway I was wondering for the particular choice of <code>4</code> bits. I would assume that <code>8</code> bits was better and probably even taking <code>16</code> bit windows seems fairly reasonable.</p>

<ecdsa><library>
Why are exactly 4 bit windows used in the lookup table of libsecp256k1 to speed up point multiplications?
Rene Pickhardt
# Why are exactly 4 bit windows used in the lookup table of libsecp256k1 to speed up point multiplications?

(Asked by: username_0 on 2019-03-12)

From [the Readme of secp256k1](https://github.com/bitcoin/bitcoin/tree/bccb4d29a8080bf1ecda1fc235415a11d903a680/src/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.

**Tags:** ecdsa, library


---

## 1 answers

### Answer by username_1 on 2019-03-12. Score: 2

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](https://github.com/bitcoin-core/secp256k1/blob/master/src/ecmult_gen_impl.h#L148) 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](https://github.com/bitcoin-core/secp256k1/pull/546/)) 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.


---

