Add trivial ecmult_multi algorithm which does not require a scratch space #580

jonasnick commented at 9:33 PM on December 22, 2018: contributor

This commit adds a new ecmult_multi algorithm that is automatically selected when ecmult_multi_var is called with scratch space set to NULL. This is a trivial algorithm that simply multiplies the points with the corresponding scalars and adds them up.

The use case is to allow creating exposed function that uses ecmult_multi but without requiring a scratch space argument. For example, in MuSig when computing the combined public key we need to compute a weighted sum of points but we most likely don't care about the performance. And if we do we can still provide a scratch space. Having the option of not providing a scratch space is useful because creating a scratch space is not entirely trivial. One needs to decide on a size and it needs to be destroyed.

jonasnick cross-referenced this on Dec 22, 2018 from issue Add MuSig module by jonasnick

in src/ecmult_impl.h:1098 in b1214518c5 outdated

1091 | +    secp256k1_gej tmpj;
1092 | +
1093 | +    secp256k1_scalar_set_int(&szero, 0);
1094 | +    /* r = inp_g_sc*G */
1095 | +    secp256k1_gej_set_infinity(r);
1096 | +    secp256k1_ecmult(ctx, r, &tmpj, &szero, inp_g_sc);

real-or-random commented at 9:30 AM on February 11, 2019:

AFAICT this will dereference &tmpj to read from uninitialized memory at https://github.com/bitcoin-core/secp256k1/blob/e34ceb333b1c0e6f4115ecbb80c632ac1042fa49/src/ecmult_impl.h#L469

    secp256k1_gej_set_infinity(&tmpj);
    secp256k1_ecmult(ctx, r, &tmpj, &szero, inp_g_sc);

jonasnick commented at 6:35 PM on February 11, 2019:

Doesn't look like it would to me, but better to properly set it anyway. Fixed.

real-or-random commented at 4:26 PM on February 12, 2019:

Oh oops, I saw your comment only now. Now that you say it, I think you're right, due to the lazy-eval... Whatever, it does not hurt.

in src/ecmult_impl.h:1088 in b1214518c5 outdated

1082 | @@ -1083,6 +1083,32 @@ static size_t secp256k1_pippenger_max_points(secp256k1_scratch *scratch) {
1083 |      return res;
1084 |  }
1085 |  
1086 | +/* Computes ecmult_multi by simply multiplying and adding each point. Does not
1087 | + * require a scratch space */
1088 | +static int secp256k1_ecmult_multi_var_simple(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points) {

real-or-random commented at 10:01 AM on February 11, 2019:

nit: maybe secp256k1_ecmult_multi_simple_var is more consistent with the naming of the other functions

jonasnick commented at 6:16 PM on February 11, 2019:

yup, fixed

real-or-random commented at 6:26 PM on February 11, 2019: contributor

utACK 96839b3

jonasnick force-pushed on Feb 11, 2019

jonasnick commented at 6:42 PM on February 11, 2019: contributor

squashed

apoelstra commented at 4:23 PM on February 12, 2019: contributor

ACK 3f59c4a6511b624ca1803a7126b24de5f8568dd9

outdamud commented at 5:13 PM on February 12, 2019: none

Thank you

Sent from my iPhone

On Feb 11, 2019, at 1:16 PM, Jonas Nick notifications@github.com wrote:

@jonasnick commented on this pull request.

In src/ecmult_impl.h:

@@ -1083,6 +1083,32 @@ static size_t secp256k1_pippenger_max_points(secp256k1_scratch *scratch) { return res; }

+/* Computes ecmult_multi by simply multiplying and adding each point. Does not

require a scratch space */ +static int secp256k1_ecmult_multi_var_simple(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points) { yup, fixed

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

gmaxwell commented at 11:54 PM on February 21, 2019: contributor

This should probably get added to the ecmult bench too.

Add trivial ecmult_multi algorithm. It is selected when no scratch space is given and just multiplies and adds the points. bade617417

jonasnick force-pushed on Feb 23, 2019

Add trivial ecmult_multi to the benchmark tool a697d82da9

jonasnick commented at 8:30 PM on February 23, 2019: contributor

@gmaxwell good point. Added commit with that.

apoelstra commented at 11:15 PM on February 23, 2019: contributor

ACK 11e350b3269e92625038363c04bb6c8f60b8e624

gmaxwell merged this on Feb 24, 2019

gmaxwell closed this on Feb 24, 2019

gmaxwell referenced this in commit 14196379ec on Feb 24, 2019

gmaxwell commented at 3:11 AM on February 24, 2019: contributor

ACK

DeckerSU referenced this in commit 24339be7cd on Mar 1, 2023

DeckerSU cross-referenced this on Mar 1, 2023 from issue secp256k1: fix possible read from uninitialized memory (tmpj) by DeckerSU

DeckerSU referenced this in commit 81e9f3471f on Mar 1, 2023

DeckerSU referenced this in commit 517ae4d0db on Jun 12, 2023

DeckerSU referenced this in commit b96281ea7b on Jun 12, 2023