Repository: bitcoin-core/secp256k1
Pull request #592 (2019-02-27 10:50:15)

Use trivial algorithm in ecmult_multi if scratch space is small
`ecmult_multi` already selects the trivial algorithm if the scratch space is NULL. With this PR the trivial algorithm is also selected if the scratch space is too small to use pippenger or strauss instead of returning 0. That makes it more easier to avoid consensus relevant inconsistencies just because scratch space construction was messed up.

real-or-random: I think that's a good idea. But the drawback is that now you won't notice that you use the slow algorithm. Do you think we can somehow get the best of both worlds, i.e., fall back to the trivial algorithm but somehow indicate that something is wrong? I don't see a convincing way to do this: 
 - we cannot just print a warning from the library
 - we can't use the current callbacks because they'll abort the process (and introducing another callback for that single case is probably overkill)
 - maybe using a second non-failing return value? (also not great and changes the API)
jonasnick: > But the drawback is that now you won't notice that you use the slow algorithm

You have that problem anyway even without this PR because you can have a scratch space which only fits a single point. Or if you make a scratch space fitting 2 points but you have a 1000 to multiply.

You'll notice that you're using a slow algorithm if you benchmark your program which presumably you do if you use ecmult_multi or batch_verify. You might have a problem if the size of the scratch space is attacker controlled and you assume something about timings of ecmult_multi, but this PR is a strict improvement in that case. I don't have anything against multiple return values per se, but it's not a panacea because you need to make implementer check for the various error types.
real-or-random: utACK
gmaxwell: Concept ACK.

I share the concern that users will get poor performance by surprise, but I think the right way for us to address that would be to in the future provide an API that doesn't require manual scratch space handling, even at the expense of wasting memory. "Fast by default".

In the absence of that, I'd much rather it fail slow than fail fail.



Patch:
diff --git a/Makefile.am b/Makefile.am
index 9e5b7dc..80fca49 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -114,7 +114,7 @@ exhaustive_tests_CPPFLAGS = -DSECP256K1_BUILD -I$(top_srcdir)/src $(SECP_INCLUDE
 if !ENABLE_COVERAGE
 exhaustive_tests_CPPFLAGS += -DVERIFY
 endif
-exhaustive_tests_LDADD = $(SECP_LIBS) $(COMMON_LIB)
+exhaustive_tests_LDADD = $(SECP_LIBS)
 exhaustive_tests_LDFLAGS = -static
 TESTS += exhaustive_tests
 endif
diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h
index cbafd07..2587709 100644
--- a/src/ecmult_impl.h
+++ b/src/ecmult_impl.h
@@ -1152,16 +1152,18 @@ static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp2
         return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n);
     }
 
-    /* Compute the batch sizes for pippenger given a scratch space. If it's greater than a threshold
-     * use pippenger. Otherwise use strauss */
+    /* Compute the batch sizes for Pippenger's algorithm given a scratch space. If it's greater than
+     * a threshold use Pippenger's algorithm. Otherwise use Strauss' algorithm.
+     * As a first step check if there's enough space for Pippenger's algo (which requires less space
+     * than Strauss' algo) and if not, use the simple algorithm. */
     if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(scratch), n)) {
-        return 0;
+        return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n);
     }
     if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) {
         f = secp256k1_ecmult_pippenger_batch;
     } else {
         if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(scratch), n)) {
-            return 0;
+            return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n);
         }
         f = secp256k1_ecmult_strauss_batch;
     }
diff --git a/src/scalar_4x64_impl.h b/src/scalar_4x64_impl.h
index d378335..db1ebf9 100644
--- a/src/scalar_4x64_impl.h
+++ b/src/scalar_4x64_impl.h
@@ -376,7 +376,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l)
     /* extract m6 */
     "movq %%r8, %q6\n"
     : "=g"(m0), "=g"(m1), "=g"(m2), "=g"(m3), "=g"(m4), "=g"(m5), "=g"(m6)
-    : "S"(l), "i"(SECP256K1_N_C_0), "i"(SECP256K1_N_C_1)
+    : "S"(l), "n"(SECP256K1_N_C_0), "n"(SECP256K1_N_C_1)
     : "rax", "rdx", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "cc");
 
     /* Reduce 385 bits into 258. */
@@ -455,7 +455,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l)
     /* extract p4 */
     "movq %%r9, %q4\n"
     : "=&g"(p0), "=&g"(p1), "=&g"(p2), "=g"(p3), "=g"(p4)
-    : "g"(m0), "g"(m1), "g"(m2), "g"(m3), "g"(m4), "g"(m5), "g"(m6), "i"(SECP256K1_N_C_0), "i"(SECP256K1_N_C_1)
+    : "g"(m0), "g"(m1), "g"(m2), "g"(m3), "g"(m4), "g"(m5), "g"(m6), "n"(SECP256K1_N_C_0), "n"(SECP256K1_N_C_1)
     : "rax", "rdx", "r8", "r9", "r10", "r11", "r12", "r13", "cc");
 
     /* Reduce 258 bits into 256. */
@@ -501,7 +501,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l)
     /* Extract c */
     "movq %%r9, %q0\n"
     : "=g"(c)
-    : "g"(p0), "g"(p1), "g"(p2), "g"(p3), "g"(p4), "D"(r), "i"(SECP256K1_N_C_0), "i"(SECP256K1_N_C_1)
+    : "g"(p0), "g"(p1), "g"(p2), "g"(p3), "g"(p4), "D"(r), "n"(SECP256K1_N_C_0), "n"(SECP256K1_N_C_1)
     : "rax", "rdx", "r8", "r9", "r10", "cc", "memory");
 #else
     uint128_t c;


Test patch:
diff --git a/src/tests.c b/src/tests.c
index f1c4db9..7c24482 100644
--- a/src/tests.c
+++ b/src/tests.c
@@ -2572,7 +2572,6 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e
     secp256k1_gej r;
     secp256k1_gej r2;
     ecmult_multi_data data;
-    secp256k1_scratch *scratch_empty;
 
     data.sc = sc;
     data.pt = pt;
@@ -2607,11 +2606,6 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e
         secp256k1_gej_add_var(&r, &r, &r2, NULL);
         CHECK(secp256k1_gej_is_infinity(&r));
 
-        /* Try to multiply 1 point, but scratch space is empty */
-        scratch_empty = secp256k1_scratch_create(&ctx->error_callback, 0);
-        CHECK(!ecmult_multi(&ctx->ecmult_ctx, scratch_empty, &r, &szero, ecmult_multi_callback, &data, 1));
-        secp256k1_scratch_destroy(scratch_empty);
-
         /* Try to multiply 1 point, but callback returns false */
         CHECK(!ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_false_callback, &data, 1));
 
@@ -2809,6 +2803,24 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e
     }
 }
 
+void test_ecmult_multi_batch_single(secp256k1_ecmult_multi_func ecmult_multi) {
+    secp256k1_scalar szero;
+    secp256k1_scalar sc[32];
+    secp256k1_ge pt[32];
+    secp256k1_gej r;
+    ecmult_multi_data data;
+    secp256k1_scratch *scratch_empty;
+
+    data.sc = sc;
+    data.pt = pt;
+    secp256k1_scalar_set_int(&szero, 0);
+
+    /* Try to multiply 1 point, but scratch space is empty.*/
+    scratch_empty = secp256k1_scratch_create(&ctx->error_callback, 0);
+    CHECK(!ecmult_multi(&ctx->ecmult_ctx, scratch_empty, &r, &szero, ecmult_multi_callback, &data, 1));
+    secp256k1_scratch_destroy(scratch_empty);
+}
+
 void test_secp256k1_pippenger_bucket_window_inv(void) {
     int i;
 
@@ -2932,19 +2944,25 @@ void test_ecmult_multi_batching(void) {
     }
     data.sc = sc;
     data.pt = pt;
+    secp256k1_gej_neg(&r2, &r2);
 
-    /* Test with empty scratch space */
+    /* Test with empty scratch space. It should compute the correct result using 
+     * ecmult_mult_simple algorithm which doesn't require a scratch space. */
     scratch = secp256k1_scratch_create(&ctx->error_callback, 0);
-    CHECK(!secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, 1));
+    CHECK(secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points));
+    secp256k1_gej_add_var(&r, &r, &r2, NULL);
+    CHECK(secp256k1_gej_is_infinity(&r));
     secp256k1_scratch_destroy(scratch);
 
     /* Test with space for 1 point in pippenger. That's not enough because
-     * ecmult_multi selects strauss which requires more memory. */
+     * ecmult_multi selects strauss which requires more memory. It should
+     * therefore select the simple algorithm. */
     scratch = secp256k1_scratch_create(&ctx->error_callback, secp256k1_pippenger_scratch_size(1, 1) + PIPPENGER_SCRATCH_OBJECTS*ALIGNMENT);
-    CHECK(!secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, 1));
+    CHECK(secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points));
+    secp256k1_gej_add_var(&r, &r, &r2, NULL);
+    CHECK(secp256k1_gej_is_infinity(&r));
     secp256k1_scratch_destroy(scratch);
 
-    secp256k1_gej_neg(&r2, &r2);
     for(i = 1; i <= n_points; i++) {
         if (i > ECMULT_PIPPENGER_THRESHOLD) {
             int bucket_window = secp256k1_pippenger_bucket_window(i);
@@ -2972,7 +2990,9 @@ void run_ecmult_multi_tests(void) {
     test_ecmult_multi(scratch, secp256k1_ecmult_multi_var);
     test_ecmult_multi(NULL, secp256k1_ecmult_multi_var);
     test_ecmult_multi(scratch, secp256k1_ecmult_pippenger_batch_single);
+    test_ecmult_multi_batch_single(secp256k1_ecmult_pippenger_batch_single);
     test_ecmult_multi(scratch, secp256k1_ecmult_strauss_batch_single);
+    test_ecmult_multi_batch_single(secp256k1_ecmult_strauss_batch_single);
     secp256k1_scratch_destroy(scratch);
 
     /* Run test_ecmult_multi with space for exactly one point */