Optimize lagrange coef computation

[survived]

When we do interpolation for VSS keys, we calculate lagrange coefficients (we do that in key share validation, in DKG and signing protocols). Each lagrange coef computation does a modular inversion which could be expensive. Recall that the formula for computing lagrange coef is:

$$\text{coef}(j, x, \vec x) = \frac{\prod_{m \ne j} x - \vec xm}{\prod{m \ne j} \vec x_j - \vec x_m}$$

(it's defined here)

Note that the denominator is independent of $x$ and that $\vec x$ is fixed at DKG. We can precompute in advance a table $T_{i,j} = (\vec x_i - \vec x_j)^{-1}$ for each $i < j$ (which will have size $\frac{n^2}{2}$), so we never have to do a modular inversion ever again when computing lagrange coefficient.

[maurges]

Good idea. I think we might rather put it to generic-ec

[maurges]

Looking at some usages, an interface that might work is fn lagrange_coefficients(x, xs, t) -> impl Iterator<Item = Scalar>

[survived]

This is also a valid approach, tho here I'm suggesting to store additional data in the key share so we actually don't need to do a modular inversion. I'll open a separate issue in generic-ec

[survived]

Opened https://github.com/dfns/generic-ec/issues/39

[maurges]

I'm vary to increase our keyshare size. I think rather than that, when we fix the signer indexes in clusters, the xs will not change between key shares, so we can precompute denominators for a whole signer, not for a key.

[survived]

We don't necessarily need to store that information on the disk, we can update the key share before invoking signing, for instance

[maurges]

Hm, but how is that better than using the optimized generic-ec function? I see we only create lagrange coefficients once per protocol. With fixed indexes that's a certain optimization though.

[survived]

Usually, we do optimization only when we are explicitly asked to. E.g. when you generate aux data, you can ask it to optimize the aux data by calling Builder::precompute_multiexp_tables method. Otherwise, it's still possible to optimize the key share after aux gen is done by calling AuxInfo::precompute_multiexp_tables.

I was thinking about similar approach: DKG may or may not precompute a table for lagrange coefs. Then we'd add something like KeyShare::build_lagrange_table. So we can extract lagrange table before serializing, and put it back after deserializing.

Alternatively, lagrange table could be separated from key share completely and provided as an optional input to the protocol. I'm not sure which approach is nicer. Whoever gets to implement this optimization gotta examine all options and choose a better one :)

[survived]

Oh I misunderstood your question...

Hm, but how is that better than using the optimized generic-ec function? I see we only create lagrange coefficients once per protocol. With fixed indexes that's a certain optimization though.

I was suggesting that we store lagrange table on disk, we don't necessarily need to store them within key share. As you noticed, in our use-case for every key share the table will be the same, so we can store that table in one place, and populate deserialized key shares with the table before invoking the protocol