Page MenuHomePhabricator
Differential D5146 Diff 16033 src/secp256k1/src/tests.c

Changeset View

Standalone View

View Options

src/secp256k1/src/tests.c

Show First 20 Lines • Show All 327 Lines • ▼ Show 20 Linesvoid run_context_tests(int use_prealloc) {
} }
/* Defined as no-op. */ /* Defined as no-op. */
secp256k1_context_destroy(NULL); secp256k1_context_destroy(NULL);
secp256k1_context_preallocated_destroy(NULL); secp256k1_context_preallocated_destroy(NULL);
} }
void run_scratch_tests(void) { void run_scratch_tests(void) {
const size_t adj_alloc = ((500 + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT;
int32_t ecount = 0; int32_t ecount = 0;
size_t checkpoint;
size_t checkpoint_2;
secp256k1_context *none = secp256k1_context_create(SECP256K1_CONTEXT_NONE); secp256k1_context *none = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
secp256k1_scratch_space *scratch; secp256k1_scratch_space *scratch;
secp256k1_scratch_space local_scratch;
/* Test public API */ /* Test public API */
secp256k1_context_set_illegal_callback(none, counting_illegal_callback_fn, &ecount); secp256k1_context_set_illegal_callback(none, counting_illegal_callback_fn, &ecount);
secp256k1_context_set_error_callback(none, counting_illegal_callback_fn, &ecount);
scratch = secp256k1_scratch_space_create(none, 1000); scratch = secp256k1_scratch_space_create(none, 1000);
CHECK(scratch != NULL); CHECK(scratch != NULL);
CHECK(ecount == 0); CHECK(ecount == 0);
/* Test internal API */ /* Test internal API */
CHECK(secp256k1_scratch_max_allocation(scratch, 0) == 1000); CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000);
CHECK(secp256k1_scratch_max_allocation(scratch, 1) < 1000); CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) == 1000 - (ALIGNMENT - 1));
CHECK(scratch->alloc_size == 0);
CHECK(scratch->alloc_size % ALIGNMENT == 0);
/* Allocating 500 bytes succeeds */
checkpoint = secp256k1_scratch_checkpoint(&none->error_callback, scratch);
CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) != NULL);
CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000 - adj_alloc);
CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) == 1000 - adj_alloc - (ALIGNMENT - 1));
CHECK(scratch->alloc_size != 0);
CHECK(scratch->alloc_size % ALIGNMENT == 0);
/* Allocating another 500 bytes fails */
CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) == NULL);
CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000 - adj_alloc);
CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) == 1000 - adj_alloc - (ALIGNMENT - 1));
CHECK(scratch->alloc_size != 0);
CHECK(scratch->alloc_size % ALIGNMENT == 0);
/* ...but it succeeds once we apply the checkpoint to undo it */
secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, checkpoint);
CHECK(scratch->alloc_size == 0);
CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000);
CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) != NULL);
CHECK(scratch->alloc_size != 0);
/* try to apply a bad checkpoint */
checkpoint_2 = secp256k1_scratch_checkpoint(&none->error_callback, scratch);
secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, checkpoint);
CHECK(ecount == 0);
secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, checkpoint_2); /* checkpoint_2 is after checkpoint */
CHECK(ecount == 1);
secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, (size_t) -1); /* this is just wildly invalid */
CHECK(ecount == 2);
/* Allocating 500 bytes with no frame fails */ /* try to use badly initialized scratch space */
CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL); secp256k1_scratch_space_destroy(none, scratch);
CHECK(secp256k1_scratch_max_allocation(scratch, 0) == 1000); memset(&local_scratch, 0, sizeof(local_scratch));
scratch = &local_scratch;
/* ...but pushing a new stack frame does affect the max allocation */ CHECK(!secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0));
CHECK(secp256k1_scratch_allocate_frame(scratch, 500, 1) == 1); CHECK(ecount == 3);
CHECK(secp256k1_scratch_max_allocation(scratch, 1) < 500); /* 500 - ALIGNMENT */ CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) == NULL);
CHECK(secp256k1_scratch_alloc(scratch, 500) != NULL); CHECK(ecount == 4);
CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL); secp256k1_scratch_space_destroy(none, scratch);
CHECK(ecount == 5);
CHECK(secp256k1_scratch_allocate_frame(scratch, 500, 1) == 0);
/* ...and this effect is undone by popping the frame */
secp256k1_scratch_deallocate_frame(scratch);
CHECK(secp256k1_scratch_max_allocation(scratch, 0) == 1000);
CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL);
/* cleanup */ /* cleanup */
secp256k1_scratch_space_destroy(scratch); secp256k1_scratch_space_destroy(none, NULL); /* no-op */
secp256k1_context_destroy(none); secp256k1_context_destroy(none);
} }
/***** HASH TESTS *****/ /***** HASH TESTS *****/
void run_sha256_tests(void) { void run_sha256_tests(void) {
static const char *inputs[8] = { static const char *inputs[8] = {
"", "abc", "message digest", "secure hash algorithm", "SHA256 is considered to be safe", "", "abc", "message digest", "secure hash algorithm", "SHA256 is considered to be safe",
▲ Show 20 Lines • Show All 2,272 Lines • ▼ Show 20 Linesvoid test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func ecmult_multi) {
secp256k1_gej r2; secp256k1_gej r2;
ecmult_multi_data data; ecmult_multi_data data;
data.sc = sc; data.sc = sc;
data.pt = pt; data.pt = pt;
secp256k1_scalar_set_int(&szero, 0); secp256k1_scalar_set_int(&szero, 0);
/* No points to multiply */ /* No points to multiply */
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, NULL, ecmult_multi_callback, &data, 0)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, NULL, ecmult_multi_callback, &data, 0));
/* Check 1- and 2-point multiplies against ecmult */ /* Check 1- and 2-point multiplies against ecmult */
for (ncount = 0; ncount < count; ncount++) { for (ncount = 0; ncount < count; ncount++) {
secp256k1_ge ptg; secp256k1_ge ptg;
secp256k1_gej ptgj; secp256k1_gej ptgj;
random_scalar_order(&sc[0]); random_scalar_order(&sc[0]);
random_scalar_order(&sc[1]); random_scalar_order(&sc[1]);
random_group_element_test(&ptg); random_group_element_test(&ptg);
secp256k1_gej_set_ge(&ptgj, &ptg); secp256k1_gej_set_ge(&ptgj, &ptg);
pt[0] = ptg; pt[0] = ptg;
pt[1] = secp256k1_ge_const_g; pt[1] = secp256k1_ge_const_g;
/* only G scalar */ /* only G scalar */
secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &szero, &sc[0]); secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &szero, &sc[0]);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &sc[0], ecmult_multi_callback, &data, 0)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &sc[0], ecmult_multi_callback, &data, 0));
secp256k1_gej_neg(&r2, &r2); secp256k1_gej_neg(&r2, &r2);
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
/* 1-point */ /* 1-point */
secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &szero); secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &szero);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 1)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 1));
secp256k1_gej_neg(&r2, &r2); secp256k1_gej_neg(&r2, &r2);
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
/* Try to multiply 1 point, but callback returns false */ /* Try to multiply 1 point, but callback returns false */
CHECK(!ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_false_callback, &data, 1)); CHECK(!ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_false_callback, &data, 1));
/* 2-point */ /* 2-point */
secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &sc[1]); secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &sc[1]);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 2)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 2));
secp256k1_gej_neg(&r2, &r2); secp256k1_gej_neg(&r2, &r2);
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
/* 2-point with G scalar */ /* 2-point with G scalar */
secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &sc[1]); secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &sc[1]);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &sc[1], ecmult_multi_callback, &data, 1)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &sc[1], ecmult_multi_callback, &data, 1));
secp256k1_gej_neg(&r2, &r2); secp256k1_gej_neg(&r2, &r2);
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
} }
/* Check infinite outputs of various forms */ /* Check infinite outputs of various forms */
for (ncount = 0; ncount < count; ncount++) { for (ncount = 0; ncount < count; ncount++) {
secp256k1_ge ptg; secp256k1_ge ptg;
size_t i, j; size_t i, j;
size_t sizes[] = { 2, 10, 32 }; size_t sizes[] = { 2, 10, 32 };
for (j = 0; j < 3; j++) { for (j = 0; j < 3; j++) {
for (i = 0; i < 32; i++) { for (i = 0; i < 32; i++) {
random_scalar_order(&sc[i]); random_scalar_order(&sc[i]);
secp256k1_ge_set_infinity(&pt[i]); secp256k1_ge_set_infinity(&pt[i]);
} }
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j]));
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
} }
for (j = 0; j < 3; j++) { for (j = 0; j < 3; j++) {
for (i = 0; i < 32; i++) { for (i = 0; i < 32; i++) {
random_group_element_test(&ptg); random_group_element_test(&ptg);
pt[i] = ptg; pt[i] = ptg;
secp256k1_scalar_set_int(&sc[i], 0); secp256k1_scalar_set_int(&sc[i], 0);
} }
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j]));
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
} }
for (j = 0; j < 3; j++) { for (j = 0; j < 3; j++) {
random_group_element_test(&ptg); random_group_element_test(&ptg);
for (i = 0; i < 16; i++) { for (i = 0; i < 16; i++) {
random_scalar_order(&sc[2*i]); random_scalar_order(&sc[2*i]);
secp256k1_scalar_negate(&sc[2*i + 1], &sc[2*i]); secp256k1_scalar_negate(&sc[2*i + 1], &sc[2*i]);
pt[2 * i] = ptg; pt[2 * i] = ptg;
pt[2 * i + 1] = ptg; pt[2 * i + 1] = ptg;
} }
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j]));
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
random_scalar_order(&sc[0]); random_scalar_order(&sc[0]);
for (i = 0; i < 16; i++) { for (i = 0; i < 16; i++) {
random_group_element_test(&ptg); random_group_element_test(&ptg);
sc[2*i] = sc[0]; sc[2*i] = sc[0];
sc[2*i+1] = sc[0]; sc[2*i+1] = sc[0];
pt[2 * i] = ptg; pt[2 * i] = ptg;
secp256k1_ge_neg(&pt[2*i+1], &pt[2*i]); secp256k1_ge_neg(&pt[2*i+1], &pt[2*i]);
} }
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j]));
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
} }
random_group_element_test(&ptg); random_group_element_test(&ptg);
secp256k1_scalar_set_int(&sc[0], 0); secp256k1_scalar_set_int(&sc[0], 0);
pt[0] = ptg; pt[0] = ptg;
for (i = 1; i < 32; i++) { for (i = 1; i < 32; i++) {
pt[i] = ptg; pt[i] = ptg;
random_scalar_order(&sc[i]); random_scalar_order(&sc[i]);
secp256k1_scalar_add(&sc[0], &sc[0], &sc[i]); secp256k1_scalar_add(&sc[0], &sc[0], &sc[i]);
secp256k1_scalar_negate(&sc[i], &sc[i]); secp256k1_scalar_negate(&sc[i], &sc[i]);
} }
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 32)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 32));
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
} }
/* Check random points, constant scalar */ /* Check random points, constant scalar */
for (ncount = 0; ncount < count; ncount++) { for (ncount = 0; ncount < count; ncount++) {
size_t i; size_t i;
secp256k1_gej_set_infinity(&r); secp256k1_gej_set_infinity(&r);
random_scalar_order(&sc[0]); random_scalar_order(&sc[0]);
for (i = 0; i < 20; i++) { for (i = 0; i < 20; i++) {
secp256k1_ge ptg; secp256k1_ge ptg;
sc[i] = sc[0]; sc[i] = sc[0];
random_group_element_test(&ptg); random_group_element_test(&ptg);
pt[i] = ptg; pt[i] = ptg;
secp256k1_gej_add_ge_var(&r, &r, &pt[i], NULL); secp256k1_gej_add_ge_var(&r, &r, &pt[i], NULL);
} }
secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &r, &sc[0], &szero); secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &r, &sc[0], &szero);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20));
secp256k1_gej_neg(&r2, &r2); secp256k1_gej_neg(&r2, &r2);
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
} }
/* Check random scalars, constant point */ /* Check random scalars, constant point */
for (ncount = 0; ncount < count; ncount++) { for (ncount = 0; ncount < count; ncount++) {
size_t i; size_t i;
secp256k1_ge ptg; secp256k1_ge ptg;
secp256k1_gej p0j; secp256k1_gej p0j;
secp256k1_scalar rs; secp256k1_scalar rs;
secp256k1_scalar_set_int(&rs, 0); secp256k1_scalar_set_int(&rs, 0);
random_group_element_test(&ptg); random_group_element_test(&ptg);
for (i = 0; i < 20; i++) { for (i = 0; i < 20; i++) {
random_scalar_order(&sc[i]); random_scalar_order(&sc[i]);
pt[i] = ptg; pt[i] = ptg;
secp256k1_scalar_add(&rs, &rs, &sc[i]); secp256k1_scalar_add(&rs, &rs, &sc[i]);
} }
secp256k1_gej_set_ge(&p0j, &pt[0]); secp256k1_gej_set_ge(&p0j, &pt[0]);
secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &p0j, &rs, &szero); secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &p0j, &rs, &szero);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20));
secp256k1_gej_neg(&r2, &r2); secp256k1_gej_neg(&r2, &r2);
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
} }
/* Sanity check that zero scalars don't cause problems */ /* Sanity check that zero scalars don't cause problems */
for (ncount = 0; ncount < 20; ncount++) { for (ncount = 0; ncount < 20; ncount++) {
random_scalar_order(&sc[ncount]); random_scalar_order(&sc[ncount]);
random_group_element_test(&pt[ncount]); random_group_element_test(&pt[ncount]);
} }
secp256k1_scalar_clear(&sc[0]); secp256k1_scalar_clear(&sc[0]);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20));
secp256k1_scalar_clear(&sc[1]); secp256k1_scalar_clear(&sc[1]);
secp256k1_scalar_clear(&sc[2]); secp256k1_scalar_clear(&sc[2]);
secp256k1_scalar_clear(&sc[3]); secp256k1_scalar_clear(&sc[3]);
secp256k1_scalar_clear(&sc[4]); secp256k1_scalar_clear(&sc[4]);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 6)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 6));
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 5)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 5));
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
/* Run through s0*(t0*P) + s1*(t1*P) exhaustively for many small values of s0, s1, t0, t1 */ /* Run through s0*(t0*P) + s1*(t1*P) exhaustively for many small values of s0, s1, t0, t1 */
{ {
const size_t TOP = 8; const size_t TOP = 8;
size_t s0i, s1i; size_t s0i, s1i;
size_t t0i, t1i; size_t t0i, t1i;
secp256k1_ge ptg; secp256k1_ge ptg;
Show All 28 Lines /* Run through s0*(t0*P) + s1*(t1*P) exhaustively for many small values of s0, s1, t0, t1 */
secp256k1_scalar_set_int(&sc[1], (s1i + 1) / 2); secp256k1_scalar_set_int(&sc[1], (s1i + 1) / 2);
secp256k1_scalar_cond_negate(&sc[1], s1i & 1); secp256k1_scalar_cond_negate(&sc[1], s1i & 1);
secp256k1_scalar_mul(&tmp1, &t0, &sc[0]); secp256k1_scalar_mul(&tmp1, &t0, &sc[0]);
secp256k1_scalar_mul(&tmp2, &t1, &sc[1]); secp256k1_scalar_mul(&tmp2, &t1, &sc[1]);
secp256k1_scalar_add(&tmp1, &tmp1, &tmp2); secp256k1_scalar_add(&tmp1, &tmp1, &tmp2);
secp256k1_ecmult(&ctx->ecmult_ctx, &expected, &ptgj, &tmp1, &szero); secp256k1_ecmult(&ctx->ecmult_ctx, &expected, &ptgj, &tmp1, &szero);
CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &actual, &szero, ecmult_multi_callback, &data, 2)); CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &actual, &szero, ecmult_multi_callback, &data, 2));
secp256k1_gej_neg(&expected, &expected); secp256k1_gej_neg(&expected, &expected);
secp256k1_gej_add_var(&actual, &actual, &expected, NULL); secp256k1_gej_add_var(&actual, &actual, &expected, NULL);
CHECK(secp256k1_gej_is_infinity(&actual)); CHECK(secp256k1_gej_is_infinity(&actual));
} }
} }
} }
} }
} }
} }
void test_ecmult_multi_batch_single(secp256k1_ecmult_multi_func ecmult_multi) { void test_ecmult_multi_batch_single(secp256k1_ecmult_multi_func ecmult_multi) {
secp256k1_scalar szero; secp256k1_scalar szero;
secp256k1_scalar sc[32]; secp256k1_scalar sc[32];
secp256k1_ge pt[32]; secp256k1_ge pt[32];
secp256k1_gej r; secp256k1_gej r;
ecmult_multi_data data; ecmult_multi_data data;
secp256k1_scratch *scratch_empty; secp256k1_scratch *scratch_empty;
data.sc = sc; data.sc = sc;
data.pt = pt; data.pt = pt;
secp256k1_scalar_set_int(&szero, 0); secp256k1_scalar_set_int(&szero, 0);
/* Try to multiply 1 point, but scratch space is empty.*/ /* Try to multiply 1 point, but scratch space is empty.*/
scratch_empty = secp256k1_scratch_create(&ctx->error_callback, 0); scratch_empty = secp256k1_scratch_create(&ctx->error_callback, 0);
CHECK(!ecmult_multi(&ctx->ecmult_ctx, scratch_empty, &r, &szero, ecmult_multi_callback, &data, 1)); CHECK(!ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch_empty, &r, &szero, ecmult_multi_callback, &data, 1));
secp256k1_scratch_destroy(scratch_empty); secp256k1_scratch_destroy(&ctx->error_callback, scratch_empty);
} }
void test_secp256k1_pippenger_bucket_window_inv(void) { void test_secp256k1_pippenger_bucket_window_inv(void) {
int i; int i;
CHECK(secp256k1_pippenger_bucket_window_inv(0) == 0); CHECK(secp256k1_pippenger_bucket_window_inv(0) == 0);
for(i = 1; i <= PIPPENGER_MAX_BUCKET_WINDOW; i++) { for(i = 1; i <= PIPPENGER_MAX_BUCKET_WINDOW; i++) {
#ifdef USE_ENDOMORPHISM #ifdef USE_ENDOMORPHISM
Show All 16 Lines
void test_ecmult_multi_pippenger_max_points(void) { void test_ecmult_multi_pippenger_max_points(void) {
size_t scratch_size = secp256k1_rand_int(256); size_t scratch_size = secp256k1_rand_int(256);
size_t max_size = secp256k1_pippenger_scratch_size(secp256k1_pippenger_bucket_window_inv(PIPPENGER_MAX_BUCKET_WINDOW-1)+512, 12); size_t max_size = secp256k1_pippenger_scratch_size(secp256k1_pippenger_bucket_window_inv(PIPPENGER_MAX_BUCKET_WINDOW-1)+512, 12);
secp256k1_scratch *scratch; secp256k1_scratch *scratch;
size_t n_points_supported; size_t n_points_supported;
int bucket_window = 0; int bucket_window = 0;
for(; scratch_size < max_size; scratch_size+=256) { for(; scratch_size < max_size; scratch_size+=256) {
size_t i;
size_t total_alloc;
size_t checkpoint;
scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size); scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size);
CHECK(scratch != NULL); CHECK(scratch != NULL);
n_points_supported = secp256k1_pippenger_max_points(scratch); checkpoint = secp256k1_scratch_checkpoint(&ctx->error_callback, scratch);
n_points_supported = secp256k1_pippenger_max_points(&ctx->error_callback, scratch);
if (n_points_supported == 0) { if (n_points_supported == 0) {
secp256k1_scratch_destroy(scratch); secp256k1_scratch_destroy(&ctx->error_callback, scratch);
continue; continue;
} }
bucket_window = secp256k1_pippenger_bucket_window(n_points_supported); bucket_window = secp256k1_pippenger_bucket_window(n_points_supported);
CHECK(secp256k1_scratch_allocate_frame(scratch, secp256k1_pippenger_scratch_size(n_points_supported, bucket_window), PIPPENGER_SCRATCH_OBJECTS)); /* allocate `total_alloc` bytes over `PIPPENGER_SCRATCH_OBJECTS` many allocations */
secp256k1_scratch_deallocate_frame(scratch); total_alloc = secp256k1_pippenger_scratch_size(n_points_supported, bucket_window);
secp256k1_scratch_destroy(scratch); for (i = 0; i < PIPPENGER_SCRATCH_OBJECTS - 1; i++) {
CHECK(secp256k1_scratch_alloc(&ctx->error_callback, scratch, 1));
total_alloc--;
}
CHECK(secp256k1_scratch_alloc(&ctx->error_callback, scratch, total_alloc));
secp256k1_scratch_apply_checkpoint(&ctx->error_callback, scratch, checkpoint);
secp256k1_scratch_destroy(&ctx->error_callback, scratch);
} }
CHECK(bucket_window == PIPPENGER_MAX_BUCKET_WINDOW); CHECK(bucket_window == PIPPENGER_MAX_BUCKET_WINDOW);
} }
void test_ecmult_multi_batch_size_helper(void) { void test_ecmult_multi_batch_size_helper(void) {
size_t n_batches, n_batch_points, max_n_batch_points, n; size_t n_batches, n_batch_points, max_n_batch_points, n;
max_n_batch_points = 0; max_n_batch_points = 0;
▲ Show 20 Lines • Show All 71 Lines • ▼ Show 20 Linesvoid test_ecmult_multi_batching(void) {
} }
data.sc = sc; data.sc = sc;
data.pt = pt; data.pt = pt;
secp256k1_gej_neg(&r2, &r2); secp256k1_gej_neg(&r2, &r2);
/* Test with empty scratch space. It should compute the correct result using /* Test with empty scratch space. It should compute the correct result using
* ecmult_mult_simple algorithm which doesn't require a scratch space. */ * ecmult_mult_simple algorithm which doesn't require a scratch space. */
scratch = secp256k1_scratch_create(&ctx->error_callback, 0); scratch = secp256k1_scratch_create(&ctx->error_callback, 0);
CHECK(secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points)); CHECK(secp256k1_ecmult_multi_var(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points));
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
secp256k1_scratch_destroy(scratch); secp256k1_scratch_destroy(&ctx->error_callback, scratch);
/* Test with space for 1 point in pippenger. That's not enough because /* Test with space for 1 point in pippenger. That's not enough because
* ecmult_multi selects strauss which requires more memory. It should * ecmult_multi selects strauss which requires more memory. It should
* therefore select the simple algorithm. */ * therefore select the simple algorithm. */
scratch = secp256k1_scratch_create(&ctx->error_callback, secp256k1_pippenger_scratch_size(1, 1) + PIPPENGER_SCRATCH_OBJECTS*ALIGNMENT); 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, n_points)); CHECK(secp256k1_ecmult_multi_var(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points));
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
secp256k1_scratch_destroy(scratch); secp256k1_scratch_destroy(&ctx->error_callback, scratch);
for(i = 1; i <= n_points; i++) { for(i = 1; i <= n_points; i++) {
if (i > ECMULT_PIPPENGER_THRESHOLD) { if (i > ECMULT_PIPPENGER_THRESHOLD) {
int bucket_window = secp256k1_pippenger_bucket_window(i); int bucket_window = secp256k1_pippenger_bucket_window(i);
size_t scratch_size = secp256k1_pippenger_scratch_size(i, bucket_window); size_t scratch_size = secp256k1_pippenger_scratch_size(i, bucket_window);
scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size + PIPPENGER_SCRATCH_OBJECTS*ALIGNMENT); scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size + PIPPENGER_SCRATCH_OBJECTS*ALIGNMENT);
} else { } else {
size_t scratch_size = secp256k1_strauss_scratch_size(i); size_t scratch_size = secp256k1_strauss_scratch_size(i);
scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size + STRAUSS_SCRATCH_OBJECTS*ALIGNMENT); scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size + STRAUSS_SCRATCH_OBJECTS*ALIGNMENT);
} }
CHECK(secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points)); CHECK(secp256k1_ecmult_multi_var(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points));
secp256k1_gej_add_var(&r, &r, &r2, NULL); secp256k1_gej_add_var(&r, &r, &r2, NULL);
CHECK(secp256k1_gej_is_infinity(&r)); CHECK(secp256k1_gej_is_infinity(&r));
secp256k1_scratch_destroy(scratch); secp256k1_scratch_destroy(&ctx->error_callback, scratch);
} }
free(sc); free(sc);
free(pt); free(pt);
} }
void run_ecmult_multi_tests(void) { void run_ecmult_multi_tests(void) {
secp256k1_scratch *scratch; secp256k1_scratch *scratch;
test_secp256k1_pippenger_bucket_window_inv(); test_secp256k1_pippenger_bucket_window_inv();
test_ecmult_multi_pippenger_max_points(); test_ecmult_multi_pippenger_max_points();
scratch = secp256k1_scratch_create(&ctx->error_callback, 819200); scratch = secp256k1_scratch_create(&ctx->error_callback, 819200);
test_ecmult_multi(scratch, secp256k1_ecmult_multi_var); test_ecmult_multi(scratch, secp256k1_ecmult_multi_var);
test_ecmult_multi(NULL, secp256k1_ecmult_multi_var); test_ecmult_multi(NULL, secp256k1_ecmult_multi_var);
test_ecmult_multi(scratch, secp256k1_ecmult_pippenger_batch_single); test_ecmult_multi(scratch, secp256k1_ecmult_pippenger_batch_single);
test_ecmult_multi_batch_single(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(scratch, secp256k1_ecmult_strauss_batch_single);
test_ecmult_multi_batch_single(secp256k1_ecmult_strauss_batch_single); test_ecmult_multi_batch_single(secp256k1_ecmult_strauss_batch_single);
secp256k1_scratch_destroy(scratch); secp256k1_scratch_destroy(&ctx->error_callback, scratch);
/* Run test_ecmult_multi with space for exactly one point */ /* Run test_ecmult_multi with space for exactly one point */
scratch = secp256k1_scratch_create(&ctx->error_callback, secp256k1_strauss_scratch_size(1) + STRAUSS_SCRATCH_OBJECTS*ALIGNMENT); scratch = secp256k1_scratch_create(&ctx->error_callback, secp256k1_strauss_scratch_size(1) + STRAUSS_SCRATCH_OBJECTS*ALIGNMENT);
test_ecmult_multi(scratch, secp256k1_ecmult_multi_var); test_ecmult_multi(scratch, secp256k1_ecmult_multi_var);
secp256k1_scratch_destroy(scratch); secp256k1_scratch_destroy(&ctx->error_callback, scratch);
test_ecmult_multi_batch_size_helper(); test_ecmult_multi_batch_size_helper();
test_ecmult_multi_batching(); test_ecmult_multi_batching();
} }
void test_wnaf(const secp256k1_scalar *number, int w) { void test_wnaf(const secp256k1_scalar *number, int w) {
secp256k1_scalar x, two, t; secp256k1_scalar x, two, t;
int wnaf[256]; int wnaf[256];
▲ Show 20 Lines • Show All 2,179 Lines • Show Last 20 Lines