Randomly message "core dumped" on secp256k1_fe_inv

CrunchyFanch commented at 7:13 pm on March 24, 2021: none

Hi, I try to implement a point addition in affine coordinate and to benchmark it. Compilation are ok: gcc -o test2.exe -O2 -I secp256k1/src/ -I secp256k1/ test2.c -lgmp

but i’ve sometimes an error message on program execution (core dumped). Not on every execution.

this is my code :

 0#include "libsecp256k1-config.h"
 1
 2
 3#include <stdio.h>
 4#include <stdlib.h>
 5
 6#include <time.h>
 7
 8#include "include/secp256k1.h"
 9#include "assumptions.h"
10#include "group.h"
11#include "secp256k1.c"
12
13
14#define ROUNDS 100000000`
15
16static void light_add(secp256k1_fe *xr,secp256k1_fe *yr,  const secp256k1_fe *x1, const secp256k1_fe *y1, const secp256k1_fe *x2, const secp256k1_fe *y2){
17        
18        secp256k1_fe xtmp,ytmp,x1neg,x2neg,y2neg,xinv,m;
19        xtmp = *x1;
20        ytmp = *y1;
21        int f;
22
23        secp256k1_fe_negate(&x2neg,x2,f); //x2neg=-x2
24        secp256k1_fe_negate(&y2neg,y2,f);//y2neg=-y2
25        secp256k1_fe_negate(&x1neg,x1,f);//x1neg=-x1
26
27        secp256k1_fe_add(&xtmp,&x2neg); //(x1-x2)
28        secp256k1_fe_add(&ytmp,&y2neg);//(y1-y2)
29     
30        secp256k1_fe_inv_var(&xinv,&xtmp); //inverse_mod(x1-x2,P) 
31
32        secp256k1_fe_mul(&m,&ytmp,&xinv); //m=(y1-y2)*(x1-x2)^-1
33        secp256k1_fe_sqr(xr,&m);//m^2
34
35        secp256k1_fe_add(xr,&x1neg); //xr=m^2-x1
36        secp256k1_fe_add(xr,&x2neg); //xr=m^2-x1-x2
37
38        xtmp = *xr;
39        secp256k1_fe_add(&xtmp,&x1neg); //(xr-x1)
40        secp256k1_fe_mul(&xtmp,&m,&xtmp); //m*(xr-x1)
41        secp256k1_fe_add(&xtmp,y1); //y1+(xr-x1)
42        secp256k1_fe_negate(yr,&xtmp,f); //yr=-(y1+(xr-x1))
43
44}
45
46int main(int argc, char** argv) {
47
48
49    secp256k1_fe xr,yr;
50    secp256k1_ge pt1,pt2;
51    secp256k1_gej pt1j,pt2j;
52    time_t now;
53
54
55    secp256k1_gej_set_ge(&pt2j, &secp256k1_ge_const_g);
56
57    secp256k1_gej_double_var(&pt2j, &pt2j, NULL);
58    secp256k1_ge_set_gej(&pt2, &pt2j);               //pt2=2*G
59
60
61    time(&now);
62    printf("Today is : %s", ctime(&now));
63
64    for (int i=0;i<ROUNDS;i++){
65
66        light_add(&pt2.x,&pt2.y,&pt2.x,&pt2.y,&secp256k1_ge_const_g.x,&secp256k1_ge_const_g.y);
67    }
68    time(&now);
69    printf("Today is : %s", ctime(&now));
70}

The issue is difficult to track on debug mode because it’s happens maybe 1 per 1 billion times additions but it seems to comes from secp256k1_fe_inv_var.

Do you know why there can have is this issue? Regards Crunchy

sipa commented at 7:41 pm on March 24, 2021: contributor

You’re passing an uninitialized variable f as magnitude to fe_negate, that’s unlikely to be correct.

CrunchyFanch commented at 8:17 pm on March 24, 2021: none

Thanks! It seems to works after 10 execs I ve not fully understood what normalization is. after which field operation do I have to normalize my fe type variables?

real-or-random commented at 8:18 pm on March 24, 2021: contributor

By the way, if you update to current master, secp256k1_fe_inv_var will be faster and won’t need gmp / -lgmp anymore.

CrunchyFanch commented at 8:20 pm on March 24, 2021: none

thanks for advice. my version is the current master and it works without -lgmp

sipa commented at 8:22 pm on March 24, 2021: contributor

@CrunchyFanch Adding two fe’s results in an fe whose magnitude is the sum of the input magnitudes. When negating you need to pass the input magnitude explicitly (or an upper bound of it), and the result will be one higher. Multiplication/inverting brings magnitude to 1. Explicit normalization does the same.

sipa commented at 8:22 pm on March 24, 2021: contributor

Compile with -DDEBUG and you’ll get (very likely) errors if your magnitudes/normalization is wrong.

CrunchyFanch commented at 8:29 pm on March 24, 2021: none

@sipa ok so if a fe have a magnitude > 1 it’s means than the number stored in the 5 limbs is > than P ?

sipa commented at 8:31 pm on March 24, 2021: contributor

@CrunchyFanch No, that’s denormalization. Higher magnitude means that the individual limbs are larger some limit (see secp256k1_fe_verify in the individual implementation files).

sipa commented at 8:37 pm on March 24, 2021: contributor

For example for fe_5x52:

magnitude m: limbs 0..3 in range 0..(0xFFFFFFFFFFFFFULL*2m), limb 4 in range 0..(0x0FFFFFFFFFFFF*2m).
normalized: limbs 0..3 in range 0..0xFFFFFFFFFFFFF, limb 4 in range 0..0x0FFFFFFFFFFFF, and represented number is in range 0..p-1.

Normalized implies magnitude is 1, but also means there is just a single representation for any given field number.

CrunchyFanch commented at 8:43 pm on March 24, 2021: none

@sipa ok that’s clear .

CrunchyFanch commented at 8:44 pm on March 24, 2021: none

uses of 52bits for limbs instead of 64 bits is a way to speed up the addition operation between limbs?

CrunchyFanch commented at 8:50 pm on March 24, 2021: none

@real-or-random the cost of the point addition is the purpose of my project. Do you think than gej addition without mod inv will be faster or slower than ge addition with mod_inv?

sipa commented at 8:55 pm on March 24, 2021: contributor

@CrunchyFanch Yes, a lot. The entire reason why jacobian coordinates are used is to avoid inverses.

Since #831 inverses are signigicantly faster, but even with that, I believe ge_add_gej will still be 5x-10x faster than a point addition that needs an inverse.

CrunchyFanch commented at 9:06 pm on March 24, 2021: none

@sipa thanks. that’s what i’ll think too but my benchmark doesn’t find this difference of 5x as expected.

sipa commented at 9:07 pm on March 24, 2021: contributor

@CrunchyFanch Can you paste your full code somewhere?

CrunchyFanch commented at 9:12 pm on March 24, 2021: none

 0int main(int argc, char** argv) {
 1
 2    
 3    secp256k1_fe x1,x2,y1,y2,fe_inv;
 4    secp256k1_fe xr,yr;
 5    secp256k1_gej pt1,pt2,pt3;
 6    unsigned char x_bin[32];
 7    time_t now;
 8
 9    secp256k1_gej_set_ge(&pt1, &secp256k1_ge_const_g);
10
11
12    time(&now);
13    printf("Today is : %s", ctime(&now));
14    for (int i=0;i<ROUNDS;i++){
15        secp256k1_gej_add_ge_var(&pt1,&pt1,&secp256k1_ge_const_g,&xr);
16        // secp256k1_gej_add_ge_var(&diff, &diff, &secp256k1_ge_const_g,  NULL);
17        
18    }
19    time(&now);
20    printf("Today is : %s", ctime(&now));

is slower in execution time than the main() above

sipa commented at 9:28 pm on March 24, 2021: contributor

Your code above is invalid (it still doesn’t set f). Can you update it?

I took the liberty of fixing the formatting.

CrunchyFanch commented at 9:34 pm on March 24, 2021: none

you’re welcome !

CrunchyFanch commented at 9:35 pm on March 24, 2021: none

 0#include "libsecp256k1-config.h"
 1
 2
 3#include <stdio.h>
 4#include <stdlib.h>
 5
 6#include <time.h>
 7
 8#include "include/secp256k1.h"
 9#include "assumptions.h"
10#include "group.h"
11#include "secp256k1.c"
12#include "testrand_impl.h"
13
14#define ROUNDS 10000000
15
16int main(int argc, char** argv) {
17
18    
19    secp256k1_fe x1,x2,y1,y2,fe_inv;
20    secp256k1_fe xr,yr;
21    secp256k1_gej pt1,pt2,pt3;
22
23
24
25    unsigned char x_bin[32];
26    time_t now;
27
28    // secp256k1_gej_set_ge(&pt, &secp256k1_ge_const_g);
29    secp256k1_gej_set_ge(&pt1, &secp256k1_ge_const_g);
30    // secp256k1_gej_set_ge(&pt2, &secp256k1_ge_const_g);
31    
32
33
34    time(&now);
35    printf("Today is : %s", ctime(&now));
36    for (int i=0;i<ROUNDS;i++){
37        secp256k1_gej_add_ge_var(&pt1,&pt1,&secp256k1_ge_const_g,&xr);
38
39    }
40    time(&now);
41    printf("Today is : %s", ctime(&now));
42}

took 16sec on my computer

CrunchyFanch commented at 9:36 pm on March 24, 2021: none

and

 0#include "libsecp256k1-config.h"
 1
 2
 3#include <stdio.h>
 4#include <stdlib.h>
 5
 6#include <time.h>
 7
 8#include "include/secp256k1.h"
 9#include "assumptions.h"
10#include "group.h"
11#include "secp256k1.c"
12
13
14#define ROUNDS 10000000
15
16
17static void light_add(secp256k1_fe *xr,secp256k1_fe *yr,  const secp256k1_fe *x1, const secp256k1_fe *y1, const secp256k1_fe *x2, const secp256k1_fe *y2){
18        
19        secp256k1_fe xtmp,ytmp,x1neg,x2neg,y2neg,xinv,m;
20        xtmp = *x1;
21        ytmp = *y1;
22        int f=1;
23
24        secp256k1_fe_negate(&x2neg,x2,f); //x2neg=-x2
25        secp256k1_fe_negate(&y2neg,y2,f);//y2neg=-y2
26        secp256k1_fe_negate(&x1neg,x1,f);//x1neg=-x1
27
28        secp256k1_fe_add(&xtmp,&x2neg); //(x1-x2)
29        secp256k1_fe_add(&ytmp,&y2neg);//(y1-y2)
30     
31        secp256k1_fe_inv_var(&xinv,&xtmp); //inverse_mod(x1-x2,P)
32        secp256k1_fe_mul(&m,&ytmp,&xinv); //m=(y1-y2)*(x1-x2)^1
33        secp256k1_fe_sqr(xr,&m);//m^2
34
35        secp256k1_fe_add(xr,&x1neg); //xr=m^2-x1
36        secp256k1_fe_add(xr,&x2neg); //xr=m^2-x1-x2
37
38        xtmp = *xr;
39        secp256k1_fe_add(&xtmp,&x1neg); //(xr-x1)
40        secp256k1_fe_mul(&xtmp,&m,&xtmp); //m*(xr-x1)
41        secp256k1_fe_add(&xtmp,y1); //y1+(xr-x1)
42        secp256k1_fe_negate(yr,&xtmp,f); //yr=-(y1+(xr-x1))
43
44}
45
46
47
48int main(int argc, char** argv) {
49
50
51    secp256k1_fe xr,yr;
52    secp256k1_ge pt1,pt2;
53    secp256k1_gej pt1j,pt2j;
54    time_t now;
55
56
57    secp256k1_gej_set_ge(&pt2j, &secp256k1_ge_const_g);
58
59    secp256k1_gej_double_var(&pt2j, &pt2j, NULL);
60    secp256k1_ge_set_gej(&pt2, &pt2j);               //pt2=2*G
61
62
63    time(&now);
64    printf("Today is : %s", ctime(&now));
65
66    for (int i=0;i<ROUNDS;i++){
67
68        light_add(&pt2.x,&pt2.y,&pt2.x,&pt2.y,&secp256k1_ge_const_g.x,&secp256k1_ge_const_g.y);
69    }
70    time(&now);
71    printf("Today is : %s", ctime(&now));
72}

took 17sec

sipa commented at 9:42 pm on March 24, 2021: contributor

2.7s vs. 11.7s here.

sipa commented at 9:44 pm on March 24, 2021: contributor

I also get assertion errors with your code when compiled with -DVERIFY here. Are you sure it’s actually computing the right thing?

sipa commented at 9:47 pm on March 24, 2021: contributor

I suggest adding your code as a benchmark to bench_internal.c, and then running it in the normal compilation environment. If you compile by hand compilation flags or configuration could be off/suboptimal.

CrunchyFanch commented at 9:50 pm on March 24, 2021: none

 0crunchy@crunchy-ESPRIMO-C710:~/PG/c/$ gcc -o test2.exe -O2 -I secp256k1/src/ -I secp256k1/ test2.c 
 1crunchy@crunchy-ESPRIMO-C710:~/PG/c/$ ./test2.exe
 2 
 3Today is : Wed Mar 24 21:30:17 2021
 4Today is : Wed Mar 24 21:30:33 2021
 5
 6crunchy@crunchy-ESPRIMO-C710:~/PG/c/$ gcc -o test3.exe -O2 -I secp256k1/src/ -I secp256k1/ test3.c 
 7crunchy@crunchy-ESPRIMO-C710:~/PG/c/$ ./test3.exe 
 8
 9Today is : Wed Mar 24 21:31:34 2021
10Today is : Wed Mar 24 21:31:49 2021

CrunchyFanch commented at 9:52 pm on March 24, 2021: none

test2.c is the first and test3.c is the second sorry but i ve problem with formatting

CrunchyFanch commented at 9:54 pm on March 24, 2021: none

ok l’ll do your suggestion of compilation

CrunchyFanch commented at 10:10 pm on March 24, 2021: none

Do you want that i close this issue?

sipa commented at 10:10 pm on March 24, 2021: contributor

I think the issue is solved :)

sipa closed this on Mar 24, 2021

Randomly message “core dumped” on secp256k1_fe_inv_var #910