fiat-crypto + CryptOpt tracking issue

[real-or-random]

fiat-crypto can generate verified field code for multiple targets, e.g., C and x86_64 asm. It has algorithm templates for our mul and sqr algorithm (under the name "Dettman") for secp256k1's field. But the current implementation misses at least one optimization that we have in our C code (but not asm), namely the one #810.

CryptOpt can optimize fiat-crypto's output, producing significantly faster asm while retaining the formal guarantees.

A plausible route towards using these projects in this library is:

• Optimize the algorithm template in fiat-crypto code further by implementing the optimization from Avoid overly-wide multiplications in 5x52 field mul/sqr #810 and perhaps further refinements. This is tracked in Possible optimization for secp256k1 mit-plv/fiat-crypto#1582. This would ideally be done by the fiat-crypto folks (in particular @OwenConoly who contributed the initial implementation).
• If fiat-crypto's C output is fast enough (ideally on par with our current C code), replace the current C code by fiat-crypto's C code.
• If CryptoOpt provides a significant enough further speedup, replace the current x86_64 asm by fiat-crypto + CryptOpt x86_64 asm. Since the current output of CryptOpt is not fully generic x86_64 asm, we need either of these two:
  • Add CPU id on our side
  • Modify CryptOpt so that it uses only instructions available on all x86_64 CPUs

[dderjoel]

Hi everyone, It took me a bit but I now have some numbers.

I've used those nine machines

CPU	𝜇-architecture
Intel Core i7-6770HQ	Skylake-H
Intel Core i7-10710U	Comet Lake-U
Intel Core i9-10900K	Comet Lake-S
Intel Core i7-11700KF	Rocket Lake-S
Intel Core i9-13900KF	Raptor Lake-S
AMD Ryzen Theadr. 1900X	Zen 1
AMD Ryzen 7 5800X	Zen 3
AMD Ryzen 9 5950X	Zen 3
AMD Ryzen 9 7950X	Zen 4

I've created a little project here, which takes this library as the base.
For default_asm, it compiles with ./configure --with-asm=x86_64 using the current asm implementation.
For default_c, it compiles with ./configure --with-asm=no using the current c implementation.
For default_c52, it replaces the c-implementation with the version before the PR #810 , then compiles with ./configure --with-asm=no. I've included that to compare that with fiat_c.
For fiat_c, it replaces the c implementation with the Fiat Cryptography implementation (which does not feature the #810 optimization.)
For fiat_cryptopt, it uses Fiat as a starting point, then optimizes mul and square on all those machines, and I've included the 'on average best' one.
So on average, we see that for the ecmult_gen the fiat_c is more performant than the default_asm and fiat_cryptopt is even faster than that and the current default_c.

Numbers for the secp256k1 benchmarks ./bench_internal simple and ./bench_ecmult (I've commented out the multi_benches to succeed in a timely manner.)

Geometric mean over nine machines (per-machine tables at the end of the post)

implementation	default_asm	default_c	default_c52	fiat_c	fiat_cryptopt
ecmult_gen	24.6435	23.2049	24.7301	24.1802	22.8905
ecmult_const	46.798	43.8816	47.4836	45.7434	42.6387
ecmult_1p	37.0311	34.1909	37.06	35.7762	33.1715
ecmult_0p_g	25.3775	23.7174	26.1944	25.0963	23.3779
ecmult_1p_g	21.6629	19.9417	21.5685	20.8703	19.412
field_half	0.00333343	0.00333149	0.00334944	0.00342343	0.0033374
field_normalize	0.0112975	0.0113496	0.0113459	0.0112799	0.0112925
field_normalize_weak	0.00447881	0.00451408	0.00449407	0.00450251	0.00453795
field_sqr	0.0215233	0.0194716	0.0213214	0.0189657	0.0190589
field_mul	0.0258206	0.0219956	0.0244374	0.0240141	0.0226145
field_inverse	2.13491	2.13158	2.13192	2.13569	2.14261
field_inverse_var	1.39323	1.39281	1.3899	1.39515	1.39883
field_is_square_var	1.82198	1.83353	1.84074	1.83197	1.82702
field_sqrt	5.94338	5.4591	5.88598	5.29186	5.28916

In addition to the benchmarks of the library, I also used the SUPERCOP framework, in which I've included implementations with the same mul/square.. This is similar to the table in the paper, but instead of optimizing and comparing on one single machine (not shown in the table below) I've included one particular implementation which I ran on all machines. The numbers are cycles for four scalar multiplications (two base point, two variable point). We see that on GM, the fiat_cryptopt is again the most performant one.

Implementation	Lang.	1900X	5800X	5950X	7950X	i7 6G	i7 10G	i9 10G	i7 11G	i9 13G	G.M.
(default_asm) libsecp256k1 [Bitcoin Core 2021]	asm	720k (1.07x)	567k (1.05x)	567k (1.05x)	560k (1.06x)	565k (1.06x)	564k (1.06x)	564k (1.06x)	539k (1.08x)	439k (1.06x)	561k (1.06x)
libsecp256k1+Best (Opt)	asm	712k (1.06x)	545k (1.01x)	545k (1.01x)	543k (1.02x)	541k (1.01x)	541k (1.02x)	541k (1.02x)	512k (1.03x)	448k (1.08x)	544k (1.02x)
(default_c52) libsecp256k1 [Bitcoin Core 2021] (w/o 810)	C	699k (1.04x)	561k (1.04x)	559k (1.04x)	546k (1.03x)	575k (1.08x)	574k (1.08x)	572k (1.08x)	538k (1.08x)	454k (1.09x)	561k (1.06x)
(default_c) libsecp256k1 [Bitcoin Core 2021] (w/ 810)	C	671k (1.00x)	538k (1.00x)	538k (1.00x)	530k (1.00x)	561k (1.05x)	563k (1.06x)	562k (1.06x)	508k (1.02x)	435k (1.05x)	542k (1.02x)
(fiat_c) libsecp256k1 + Fiat-C	C	671k (1.00x)	541k (1.00x)	540k (1.00x)	537k (1.01x)	551k (1.03x)	551k (1.04x)	550k (1.04x)	508k (1.02x)	425k (1.02x)	538k (1.01x)
(fiat_cryptopt) libsecp256k1+Best (Fiat)	asm	703k (1.05x)	539k (1.00x)	539k (1.00x)	536k (1.01x)	533k (1.00x)	530k (1.00x)	531k (1.00x)	498k (1.00x)	415k (1.00x)	532k (1.00x)

Intel Core i7-6770HQ

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	29.3	29.1	30.2	30.1	27.1
ecmult_const	54.9	55.0	57.6	57.0	49.6
ecmult_1p	42.8	42.7	44.8	44.3	38.3
ecmult_0p_g	29.3	29.6	31.7	31.3	27.0
ecmult_1p_g	25.1	24.9	26.1	25.9	22.5
field_half	0.00425	0.00425	0.00429	0.00429	0.00424
field_normalize	0.0143	0.0144	0.0145	0.0143	0.0144
field_normalize_weak	0.00566	0.00585	0.00566	0.00566	0.00584
field_sqr	0.0243	0.0237	0.0242	0.0218	0.0214
field_mul	0.0302	0.0266	0.0285	0.0305	0.0253
field_inverse	2.70	2.69	2.69	2.70	2.68
field_inverse_var	1.82	1.80	1.80	1.80	1.80
field_is_square_var	2.31	2.34	2.36	2.30	2.32
field_sqrt	6.79	6.50	6.58	6.10	5.87

Intel Core i7-10710U

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	70.0	69.3	72.1	71.7	64.7
ecmult_const	131.0	131.0	137.0	136.0	118.0
ecmult_1p	102.0	102.0	107.0	106.0	91.5
ecmult_0p_g	70.0	70.9	74.7	73.6	63.4
ecmult_1p_g	59.9	59.6	62.4	61.8	53.8
field_half	0.00997	0.00993	0.0101	0.0105	0.00994
field_normalize	0.0344	0.0344	0.0344	0.0344	0.0345
field_normalize_weak	0.0132	0.0137	0.0132	0.0132	0.0137
field_sqr	0.0576	0.0559	0.0572	0.0515	0.0507
field_mul	0.0714	0.0629	0.0722	0.0676	0.0599
field_inverse	6.16	6.16	6.11	6.15	6.15
field_inverse_var	4.33	4.32	4.32	4.36	4.32
field_is_square_var	5.65	5.59	5.63	5.68	5.59
field_sqrt	16.2	15.5	15.7	14.5	14.0

Intel Core i9-10900K

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	20.5	20.4	21.1	21.1	19.0
ecmult_const	38.4	38.5	40.3	39.8	34.7
ecmult_1p	30.0	29.9	31.3	31.0	26.8
ecmult_0p_g	20.6	20.7	21.8	21.5	18.5
ecmult_1p_g	17.6	17.4	18.3	18.1	15.7
field_half	0.00296	0.00296	0.00297	0.00293	0.00298
field_normalize	0.0101	0.0101	0.0101	0.0101	0.0101
field_normalize_weak	0.00393	0.00393	0.00392	0.00393	0.00392
field_sqr	0.0171	0.0166	0.0171	0.0153	0.0151
field_mul	0.0212	0.0187	0.0201	0.0201	0.0178
field_inverse	1.80	1.80	1.80	1.80	1.80
field_inverse_var	1.27	1.27	1.27	1.27	1.26
field_is_square_var	1.62	1.65	1.64	1.62	1.62
field_sqrt	4.75	4.54	4.62	4.26	4.10

Intel Core i7-11700KF

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	19.9	17.8	19.3	18.8	17.8
ecmult_const	38.3	34.2	37.1	35.4	33.4
ecmult_1p	29.9	26.4	28.9	27.3	26.0
ecmult_0p_g	20.9	18.4	20.1	18.8	18.1
ecmult_1p_g	17.5	15.5	16.7	15.9	15.3
field_half	0.00304	0.00303	0.00303	0.00303	0.00305
field_normalize	0.0102	0.0105	0.0104	0.0101	0.0101
field_normalize_weak	0.00394	0.00394	0.00410	0.00415	0.00416
field_sqr	0.0195	0.0171	0.0181	0.0170	0.0164
field_mul	0.0225	0.0182	0.0191	0.0196	0.0203
field_inverse	1.89	1.89	1.89	1.89	1.97
field_inverse_var	1.22	1.22	1.21	1.22	1.25
field_is_square_var	1.67	1.67	1.68	1.67	1.68
field_sqrt	5.35	4.69	5.12	4.51	4.65

Intel Core i9-13900KF

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	19.5	17.8	18.6	17.9	17.6
ecmult_const	38.4	34.3	36.2	34.6	33.8
ecmult_1p	30.7	27.3	28.8	27.5	26.8
ecmult_0p_g	21.4	18.8	20.0	19.1	18.6
ecmult_1p_g	18.0	16.0	16.8	16.1	15.7
field_half	0.00330	0.00332	0.00337	0.00335	0.00333
field_normalize	0.0109	0.0110	0.0110	0.0109	0.0109
field_normalize_weak	0.00452	0.00451	0.00449	0.00450	0.00451
field_sqr	0.0191	0.0169	0.0193	0.0167	0.0177
field_mul	0.0256	0.0202	0.0210	0.0196	0.0191
field_inverse	2.13	2.12	2.13	2.13	2.13
field_inverse_var	1.37	1.37	1.37	1.36	1.38
field_is_square_var	1.88	1.87	1.87	1.88	1.88
field_sqrt	5.43	4.97	5.56	4.82	5.04

AMD Ryzen Theadripper 1900X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	25.7	23.5	26.0	24.4	25.1
ecmult_const	50.9	45.9	51.4	47.4	48.5
ecmult_1p	39.6	35.5	40.0	37.1	37.1
ecmult_0p_g	27.5	24.7	28.5	26.3	26.6
ecmult_1p_g	23.0	20.6	23.2	21.6	21.5
field_half	0.00270	0.00270	0.00271	0.00293	0.00269
field_normalize	0.0104	0.0104	0.0104	0.0104	0.0104
field_normalize_weak	0.00365	0.00365	0.00365	0.00365	0.00365
field_sqr	0.0216	0.0202	0.0224	0.0198	0.0202
field_mul	0.0267	0.0235	0.0263	0.0246	0.0244
field_inverse	2.04	2.04	2.05	2.05	2.04
field_inverse_var	1.21	1.22	1.21	1.22	1.21
field_is_square_var	1.51	1.50	1.53	1.51	1.56
field_sqrt	5.96	5.60	6.10	5.50	5.54

AMD Ryzen 5800X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	20.6	19.2	20.7	20.3	19.3
ecmult_const	38.2	35.2	39.3	37.6	35.5
ecmult_1p	31.4	27.5	30.6	29.5	27.7
ecmult_0p_g	20.9	19.1	21.6	20.5	19.4
ecmult_1p_g	18.4	16.0	17.8	17.2	16.2
field_half	0.00252	0.00251	0.00251	0.00264	0.00251
field_normalize	0.00818	0.00818	0.00818	0.00819	0.00818
field_normalize_weak	0.00343	0.00343	0.00343	0.00343	0.00343
field_sqr	0.0180	0.0147	0.0177	0.0152	0.0157
field_mul	0.0199	0.0167	0.0194	0.0195	0.0191
field_inverse	1.58	1.58	1.58	1.58	1.58
field_inverse_var	1.03	1.03	1.03	1.03	1.03
field_is_square_var	1.37	1.38	1.38	1.38	1.36
field_sqrt	4.72	4.23	4.83	4.30	4.35

AMD Ryzen 5950X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	23.1	21.4	23.2	22.7	21.6
ecmult_const	42.6	39.3	43.9	42.0	39.6
ecmult_1p	34.9	30.7	34.1	32.9	30.9
ecmult_0p_g	23.1	21.2	24.7	23.4	22.3
ecmult_1p_g	20.4	17.9	19.9	19.2	18.1
field_half	0.00280	0.00280	0.00280	0.00294	0.00280
field_normalize	0.00914	0.00912	0.00913	0.00913	0.00913
field_normalize_weak	0.00382	0.00383	0.00382	0.00382	0.00382
field_sqr	0.0200	0.0164	0.0197	0.0169	0.0176
field_mul	0.0221	0.0188	0.0216	0.0216	0.0213
field_inverse	1.77	1.76	1.76	1.77	1.77
field_inverse_var	1.15	1.15	1.15	1.15	1.18
field_is_square_var	1.52	1.54	1.54	1.54	1.52
field_sqrt	5.26	4.71	5.39	4.80	4.85

AMD Ryzen 7950X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	16.8	15.5	16.8	16.4	15.8
ecmult_const	32.0	29.2	32.4	31.0	29.8
ecmult_1p	25.1	22.7	25.3	24.4	23.4
ecmult_0p_g	17.4	15.8	18.4	17.6	17.0
ecmult_1p_g	14.6	13.2	14.7	14.2	13.6
field_half	0.00212	0.00212	0.00212	0.00212	0.00213
field_normalize	0.00698	0.00697	0.00696	0.00695	0.00696
field_normalize_weak	0.00290	0.00290	0.00290	0.00290	0.00290
field_sqr	0.0143	0.0130	0.0141	0.0128	0.0125
field_mul	0.0165	0.0142	0.0170	0.0161	0.0149
field_inverse	1.34	1.34	1.34	1.34	1.34
field_inverse_var	0.825	0.827	0.825	0.838	0.825
field_is_square_var	1.06	1.09	1.09	1.09	1.06
field_sqrt	4.12	3.62	3.93	3.50	3.51

[dderjoel]

In regards to merging this, In the I've included the implementations as .c files. And the methods are not static.
In the case for the libsecp-benchmarks
I've added the implementation as a c-source to the bench{,_internal,_ecmult}_SOURCES targets (see here).

Side note, I wanted to include the implementations as .asm files first (as those are formally verified) but then I think we would be in trouble once we compile for non System V- ABI's. So I've used nasm to assemble the asm files and objdump to dump the code in at&t syntax (afaik, otherwise clang complains sometimes) and include them into the c-source.
With that, I hope the compiler is able (if needed) swap registers of the arguments if one compiles for non System V.
And when I tried to include the methods as inline static in .h files, any optimization-level of the compiler resulted in segfaults, because the registers were not set correctly. (I'm too unfamiliar with this inline-asm notation).

In regards to "tell cryptopt to emit general code (i.e. no mulx, adox, adcx) That is not too trivial. I'll see what I can do, but I don't think we should expect anything here too soon.

[real-or-random]

Thanks, you have a nice benchmark suite. :) Interestingly, fiat_c beats default_c on SUPERCOP, but not in the other benchmarks. Any idea why this is the case?

Anyway, I don't think that any of this should change the plan sketched above. Since we're not in a hurry, it would be awesome to have mit-plv/fiat-crypto#1582 solved first.

In regards to "tell cryptopt to emit general code (i.e. no mulx, adox, adcx) That is not too trivial. I'll see what I can do, but I don't think we should expect anything here too soon.

Oh okay, we assumed it's a simple change. Anyway, should we decide that we want asm, which is anyway CPU-specific, then I think it makes sense to go 100% for it and use CPUID.

[dderjoel]

fiat_c beats default_c on SUPERCOP, but not in the other benchmarks. Any idea why this is the case?

SUPERCOP tries many different compiler / compiler settings (see below) , whereas for the ./bench_{} I've just used the default flags (see below output of ./configure). I'm happy to do that with other compilers, too, if you think that's useful.

Oh okay, we assumed it's a simple change. Anyway, should we decide that we want asm, which is anyway CPU-specific, then I think it makes sense to go 100% for it and use CPUID.

I'll keep it in mind. I'm a bit divided on this though. CPUs since Oct '14 (Broadwell) support BMI2 / ADX. So it feel's wrong to not use them. Would be interesting to see what the usage of this library is distributed... On the other hand I do understand to be as flexible as possible.

I'm using Clang 15 and GCC 12.

---

Supercop compiler settings

gcc -march=native -mtune=native -O3 -fomit-frame-pointer -fwrapv -fPIC -fPIE
gcc -march=native -mtune=native -Os -fomit-frame-pointer -fwrapv -fPIC -fPIE
gcc -march=native -mtune=native -O2 -fomit-frame-pointer -fwrapv -fPIC -fPIE
gcc -march=native -mtune=native -O -fomit-frame-pointer -fwrapv -fPIC -fPIE
clang -march=native -O3 -fomit-frame-pointer -fwrapv -Qunused-arguments -fPIC -fPIE
clang -march=native -Os -fomit-frame-pointer -fwrapv -Qunused-arguments -fPIC -fPIE
clang -march=native -O2 -fomit-frame-pointer -fwrapv -Qunused-arguments -fPIC -fPIE
clang -march=native -O -fomit-frame-pointer -fwrapv -Qunused-arguments -fPIC -fPIE
clang -mcpu=native -O3 -fomit-frame-pointer -fwrapv -Qunused-arguments -fPIC -fPIE

output of ./configure on i7-11700K, ./fiat_cryptopt

Build Options:
  with external callbacks = no
  with benchmarks         = yes
  with tests              = yes
  with ctime tests        = yes
  with coverage           = no
  with examples           = no
  module ecdh             = yes
  module recovery         = no
  module extrakeys        = yes
  module schnorrsig       = yes

  asm                     = x86_64
  ecmult window size      = 15
  ecmult gen prec. bits   = 4

  valgrind                = yes
  CC                      = gcc
  CPPFLAGS                =  
  SECP_CFLAGS             = -O2  -std=c89 -pedantic -Wno-long-long -Wnested-externs -Wshadow -Wstrict-prototypes -Wundef -Wno-overlength-strings -Wall -Wno-unused-function -Wextra -Wcast-align -Wcast-align=strict -fvisibility=hidden 
  CFLAGS                  = -g -O2
  LDFLAGS                 = 

[real-or-random]

SUPERCOP tries many different compiler / compiler settings (see below) , whereas for the ./bench_{} I've just used the default flags (see below output of ./configure).

Makes sense.

I'm happy to do that with other compilers, too, if you think that's useful.

I'm not convinced that it will provide much more insight right now.

CPUs since Oct '14 (Broadwell) support BMI2 / ADX. So it feel's wrong to not use them. Would be interesting to see what the usage of this library is distributed...

Yep, exactly my thoughts. If you really have an older CPU, the C code will serve you well.

[jonasnick]

Concept ACK on investigating fiat-crypto and (longer term) cryptopt. Would be great to have a verified implementation that's only slightly slower or even faster.

Thanks @dderjoel for the benchmarks.

[dderjoel]

Owen implemented #810 in the Fiat repo (see PR mit-plv/fiat-crypto#1582), it's not yet fully merged, but I could not wait to benchmark it.

I've updated secp_bench and supercop with the new C and CryptOpt-optimized versions.

I've also added our 12th Gen machine back into the benchmark suite, here the updated numbers (copied post from above, indicating changes):

I've used those nine ten machines

CPU	𝜇-architecture
Intel Core i7-6770HQ	Skylake-H
Intel Core i7-10710U	Comet Lake-U
Intel Core i9-10900K	Comet Lake-S
Intel Core i7-11700KF	Rocket Lake-S
Intel Core i9-12900KF	Alder Lake-S
Intel Core i9-13900KF	Raptor Lake-S
AMD Ryzen Theadr. 1900X	Zen 1
AMD Ryzen 7 5800X	Zen 3
AMD Ryzen 9 5950X	Zen 3
AMD Ryzen 9 7950X	Zen 4

I've created a little project here, which takes this library as the base.
For default_asm, it compiles with ./configure --with-asm=x86_64 using the current asm implementation.
For default_c, it compiles with ./configure --with-asm=no using the current c implementation.
For default_c52, it replaces the c-implementation with the version before the PR #810 , then compiles with ./configure --with-asm=no. I've included that to compare that with fiat_c.
For fiat_c, it replaces the c implementation with the Fiat Cryptography implementation (which does not feature the #810 optimization.) the Merge-in-progess Fiat Cryptography implementation, now featuring the #810 optimization.
For fiat_cryptopt, it uses Fiat as a starting point, then optimizes mul and square on all those machines, and I've included the 'on average best' one. (implicitly also now using the optimization)
So on average, we see that for the ecmult_gen the fiat_c is more performant than the default_asm and slightly more performant than default_c (plus giving formal assurance) and fiat_cryptopt is even faster than that and the current default_c. *the fastest (plus formal assurance) *.

Numbers for the secp256k1 benchmarks ./bench_internal simple and ./bench_ecmult (I've commented out the multi_benches to succeed in a timely manner.)

Geometric mean over nine ten machines (per-machine tables at the end of the post)

implementation	default_asm	default_c	default_c52	fiat_c	fiat_cryptopt
ecmult_gen	16.1257	14.9874	15.8764	14.9714	14.1071
ecmult_const	30.3317	28.2041	30.3634	28.1846	26.1778
ecmult_1p	23.9575	22.0809	23.641	22.1608	20.5615
ecmult_0p_g	16.9942	15.8604	16.9429	15.9223	14.7684
ecmult_1p_g	14.0591	12.8636	13.7521	12.9906	12.0012
field_half	0.0024964	0.0024537	0.00237626	0.0023697	0.00237259
field_normalize	0.00737954	0.00744617	0.00736519	0.00732155	0.00733252
field_normalize_weak	0.00294988	0.00295974	0.00293822	0.00295422	0.00294591
field_sqr	0.014059	0.0126383	0.0137789	0.0123009	0.0119273
field_mul	0.0170241	0.0144868	0.0156579	0.014689	0.0144257
field_inverse	1.40048	1.40896	1.39608	1.38928	1.3986
field_inverse_var	0.915942	0.919022	0.912739	0.907769	0.910547
field_is_square_var	1.20313	1.21123	1.20451	1.19417	1.19385
field_sqrt	3.87547	3.56868	3.82354	3.44445	3.35331

In addition to the benchmarks of the library, I also used the SUPERCOP framework, in which I've included implementations with the same mul/square.. This is similar to the table in the paper, but instead of optimizing and comparing on one single machine (not shown in the table below) I've included one particular implementation which I ran on all machines. The numbers are cycles for four scalar multiplications (two base point, two variable point). We see that on GM, the fiat_cryptopt is again the most performant one. (In fact everywhere except on 1900X, where the Fiat-C is the most performant one)

Implementation	Lang.	1900X	5800X	5950X	7950X	i7 6G	i7 10G	i9 10G	i7 11G	i9 12G	i9 13G	G.M.
(default_asm) libsecp256k1 [Bitcoin Core 2021]	asm	719k (1.11x)	571k (1.11x)	567k (1.10x)	560k (1.11x)	565k (1.07x)	565k (1.08x)	564k (1.08x)	540k (1.13x)	438k (1.09x)	439k (1.11x)	548k (1.09x)
libsecp256k1+Best (Opt)	asm	712k (1.10x)	543k (1.06x)	545k (1.06x)	544k (1.08x)	541k (1.03x)	541k (1.03x)	542k (1.04x)	512k (1.07x)	449k (1.12x)	447k (1.13x)	533k (1.07x)
(default_c52) libsecp256k1 [Bitcoin Core 2021] (w/o 810)	C	699k (1.08x)	560k (1.09x)	561k (1.09x)	547k (1.09x)	574k (1.09x)	574k (1.10x)	573k (1.10x)	536k (1.12x)	459k (1.14x)	456k (1.15x)	550k (1.10x)
(default_c) libsecp256k1 [Bitcoin Core 2021] (w/ 810)	C	671k (1.04x)	538k (1.05x)	537k (1.04x)	531k (1.06x)	567k (1.08x)	563k (1.07x)	562k (1.08x)	504k (1.06x)	440k (1.09x)	439k (1.11x)	531k (1.06x)
(fiat_c) libsecp256k1 + Fiat-C	C	648k (1.00x)	537k (1.05x)	536k (1.04x)	536k (1.07x)	549k (1.04x)	546k (1.04x)	548k (1.05x)	492k (1.03x)	418k (1.04x)	418k (1.05x)	519k (1.04x)
(fiat_cryptopt) libsecp256k1+Best (Fiat)	asm	675k (1.04x)	514k (1.00x)	515k (1.00x)	503k (1.00x)	526k (1.00x)	524k (1.00x)	523k (1.00x)	477k (1.00x)	402k (1.00x)	397k (1.00x)	500k (1.00x)

Intel Core i7-6770HQ

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	21.9	21.6	22.4	22.2	20.0
ecmult_const	40.7	40.8	42.7	41.7	36.4
ecmult_1p	31.8	31.7	33.2	32.4	28.1
ecmult_0p_g	22.7	22.9	24.0	23.4	20.2
ecmult_1p_g	18.6	18.5	19.4	18.9	16.5
field_half	0.00470	0.00441	0.00364	0.00436	0.00378
field_normalize	0.0106	0.0108	0.0107	0.0107	0.0107
field_normalize_weak	0.00420	0.00420	0.00421	0.00422	0.00421
field_sqr	0.0184	0.0175	0.0180	0.0169	0.0162
field_mul	0.0224	0.0198	0.0213	0.0221	0.0181
field_inverse	1.99	2.00	2.01	1.99	2.00
field_inverse_var	1.36	1.34	1.34	1.34	1.34
field_is_square_var	1.73	1.74	1.74	1.72	1.73
field_sqrt	5.04	4.83	4.90	4.66	4.44

Intel Core i7-10710U

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	19.8	19.3	20.1	19.7	17.8
ecmult_const	35.8	35.7	37.4	36.4	31.9
ecmult_1p	28.1	28.2	29.4	28.6	24.9
ecmult_0p_g	20.3	20.6	21.4	21.0	18.2
ecmult_1p_g	16.5	16.4	17.2	16.8	14.6
field_half	0.00327	0.00370	0.00356	0.00280	0.00368
field_normalize	0.00956	0.00956	0.00932	0.00954	0.00932
field_normalize_weak	0.00373	0.00373	0.00364	0.00387	0.00364
field_sqr	0.0167	0.0157	0.0157	0.0151	0.0144
field_mul	0.0201	0.0177	0.0188	0.0186	0.0163
field_inverse	1.71	1.72	1.72	1.71	1.72
field_inverse_var	1.21	1.21	1.21	1.22	1.22
field_is_square_var	1.60	1.54	1.56	1.57	1.56
field_sqrt	4.50	4.22	4.30	4.09	3.90

Intel Core i9-10900K

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	14.9	14.8	15.3	15.1	13.6
ecmult_const	27.9	27.9	29.5	28.5	24.9
ecmult_1p	21.8	21.7	22.7	22.2	19.3
ecmult_0p_g	15.0	15.2	15.8	15.4	13.3
ecmult_1p_g	12.8	12.6	13.3	13.0	11.3
field_half	0.00222	0.00218	0.00218	0.00215	0.00218
field_normalize	0.00739	0.00731	0.00731	0.00733	0.00731
field_normalize_weak	0.00285	0.00285	0.00286	0.00285	0.00285
field_sqr	0.0125	0.0120	0.0123	0.0115	0.0111
field_mul	0.0154	0.0136	0.0145	0.0142	0.0125
field_inverse	1.31	1.31	1.31	1.31	1.31
field_inverse_var	0.920	0.920	0.919	0.920	0.917
field_is_square_var	1.18	1.19	1.19	1.17	1.17
field_sqrt	3.44	3.30	3.35	3.18	3.04

Intel Core i7-11700KF

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	17.1	14.4	15.1	13.1	12.7
ecmult_const	31.5	27.3	28.0	24.5	23.5
ecmult_1p	23.7	21.2	20.6	19.5	19.5
ecmult_0p_g	16.6	14.7	14.4	14.3	13.6
ecmult_1p_g	14.0	12.2	12.1	11.6	11.4
field_half	0.00239	0.00237	0.00240	0.00223	0.00227
field_normalize	0.00779	0.00837	0.00805	0.00730	0.00740
field_normalize_weak	0.00320	0.00327	0.00325	0.00296	0.00313
field_sqr	0.0155	0.0136	0.0142	0.0125	0.0114
field_mul	0.0175	0.0145	0.0150	0.0128	0.0144
field_inverse	1.48	1.50	1.48	1.36	1.36
field_inverse_var	0.951	0.969	0.961	0.877	0.877
field_is_square_var	1.32	1.33	1.32	1.20	1.20
field_sqrt	4.18	3.74	3.92	3.37	3.15

Intel Core i9-12900KF

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	11.6	10.6	11.0	10.4	9.96
ecmult_const	22.6	20.2	21.3	19.9	18.9
ecmult_1p	18.1	16.0	17.0	15.8	15.0
ecmult_0p_g	13.5	11.8	12.5	11.6	11.9
ecmult_1p_g	10.6	9.37	9.92	9.23	8.80
field_half	0.00197	0.00198	0.00196	0.00197	0.00199
field_normalize	0.00638	0.00626	0.00639	0.00641	0.00637
field_normalize_weak	0.00266	0.00261	0.00264	0.00266	0.00266
field_sqr	0.0114	0.00948	0.0114	0.00946	0.00978
field_mul	0.0152	0.0115	0.0122	0.0113	0.0122
field_inverse	1.25	1.23	1.25	1.25	1.25
field_inverse_var	0.807	0.794	0.814	0.807	0.814
field_is_square_var	1.10	1.08	1.10	1.10	1.10
field_sqrt	3.26	2.91	3.25	2.82	2.84

Intel Core i9-13900KF

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	10.7	9.23	9.61	9.10	8.70
ecmult_const	20.1	17.7	18.7	17.5	16.6
ecmult_1p	15.9	14.1	14.9	13.9	13.2
ecmult_0p_g	11.4	9.95	10.5	9.66	9.18
ecmult_1p_g	9.30	8.23	8.72	8.12	7.74
field_half	0.00183	0.00183	0.00171	0.00178	0.00183
field_normalize	0.00562	0.00602	0.00571	0.00568	0.00595
field_normalize_weak	0.00235	0.00247	0.00233	0.00233	0.00247
field_sqr	0.00978	0.00932	0.00986	0.00837	0.00905
field_mul	0.0132	0.0113	0.0107	0.0102	0.0113
field_inverse	1.10	1.16	1.10	1.10	1.16
field_inverse_var	0.705	0.747	0.709	0.707	0.745
field_is_square_var	0.970	1.02	0.967	0.972	1.02
field_sqrt	2.80	2.71	2.88	2.44	2.63

AMD Ryzen Theadripper 1900X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	23.6	21.7	23.9	22.1	22.5
ecmult_const	46.6	42.1	47.1	42.7	43.4
ecmult_1p	36.1	32.4	36.4	33.0	32.9
ecmult_0p_g	25.8	23.4	26.2	23.6	23.2
ecmult_1p_g	21.0	18.9	21.2	19.2	19.1
field_half	0.00264	0.00273	0.00270	0.00270	0.00275
field_normalize	0.00960	0.00941	0.00962	0.00942	0.00942
field_normalize_weak	0.00330	0.00332	0.00333	0.00355	0.00332
field_sqr	0.0196	0.0184	0.0204	0.0175	0.0172
field_mul	0.0241	0.0214	0.0240	0.0219	0.0218
field_inverse	1.82	1.86	1.84	1.84	1.86
field_inverse_var	1.11	1.11	1.11	1.10	1.10
field_is_square_var	1.36	1.39	1.40	1.39	1.41
field_sqrt	5.38	5.08	5.56	4.82	4.77

AMD Ryzen 5800X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	16.3	15.4	16.8	15.6	14.5
ecmult_const	30.1	28.1	31.9	28.8	26.6
ecmult_1p	24.7	22.0	24.8	22.8	20.8
ecmult_0p_g	16.5	15.5	17.5	15.7	14.5
ecmult_1p_g	14.6	12.9	14.4	13.2	12.1
field_half	0.00255	0.00219	0.00221	0.00238	0.00199
field_normalize	0.00661	0.00646	0.00647	0.00655	0.00647
field_normalize_weak	0.00275	0.00270	0.00270	0.00272	0.00270
field_sqr	0.0142	0.0117	0.0140	0.0124	0.0115
field_mul	0.0161	0.0136	0.0155	0.0144	0.0142
field_inverse	1.28	1.26	1.25	1.27	1.26
field_inverse_var	0.833	0.822	0.815	0.826	0.816
field_is_square_var	1.10	1.09	1.09	1.10	1.07
field_sqrt	3.81	3.35	3.84	3.47	3.30

AMD Ryzen 5950X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	16.1	15.5	16.7	15.3	14.6
ecmult_const	30.6	28.4	31.6	28.1	26.7
ecmult_1p	25.4	22.4	25.0	22.1	20.8
ecmult_0p_g	17.7	16.5	18.0	16.3	15.3
ecmult_1p_g	15.0	13.1	14.1	13.2	12.2
field_half	0.00223	0.00221	0.00224	0.00224	0.00218
field_normalize	0.00649	0.00642	0.00642	0.00643	0.00645
field_normalize_weak	0.00270	0.00267	0.00267	0.00267	0.00267
field_sqr	0.0142	0.0115	0.0139	0.0121	0.0114
field_mul	0.0158	0.0132	0.0154	0.0140	0.0140
field_inverse	1.26	1.24	1.24	1.25	1.25
field_inverse_var	0.819	0.808	0.817	0.816	0.811
field_is_square_var	1.08	1.08	1.08	1.08	1.07
field_sqrt	3.75	3.33	3.81	3.39	3.27

AMD Ryzen 7950X

bench	asm	c	c52	fiat_c	fiat_cryptopt
ecmult_gen	14.0	12.7	13.8	13.1	12.3
ecmult_const	26.4	23.9	26.7	24.8	23.0
ecmult_1p	20.7	18.6	20.9	19.5	18.2
ecmult_0p_g	15.1	13.6	15.4	14.3	13.2
ecmult_1p_g	12.1	10.8	12.1	11.4	10.4
field_half	0.00213	0.00196	0.00189	0.00189	0.00189
field_normalize	0.00556	0.00564	0.00549	0.00561	0.00559
field_normalize_weak	0.00228	0.00229	0.00228	0.00230	0.00229
field_sqr	0.0115	0.0106	0.0112	0.0104	0.00989
field_mul	0.0137	0.0118	0.0136	0.0123	0.0123
field_inverse	1.09	1.10	1.07	1.10	1.10
field_inverse_var	0.670	0.680	0.657	0.681	0.675
field_is_square_var	0.855	0.889	0.860	0.881	0.857
field_sqrt	3.34	2.98	3.17	2.95	2.82

[dderjoel]

Hi everyone,
I've integrated the new implementations (CryptOpt Assembly and Fiat-C) into my fork, and it works with ./configure --with-asm=no and ./configure --with-asm=x86_64.
I am unsure how to run the ci, to see if it works (especially on Windows).

Also, the current commits don't check if the CPU features flags BMI2 nor ADX. Is the idea to check that at runtime or compile time or both?
Also, I can't figure out how I would make the field arithmetic static and inline again (if that is needed).

I'm happy to do the bulk work but I'd need some guidance on the following

• CPU flags check on compile / run time
• Where to put implementations (I've currently put them into src/third_party) and whether to force them to be static
• If not static, then we need CMake integration (to compile ./third_party/*.c)

[dderjoel]

Hi everyone,

I've updated my fork in three ways:

1. I've included the up to date version from Fiat, i.e. without the unnecessary AND's
2. I've included the CryptOpt-generated versions into the header files, (as opposed to earlier where I've put them into separate C files).
   One problem was that the inline assembly did not specify that caller-save registers will be overwritten.
   Another problem was that rdx and rdi were also overwritten. Now, I've added two instructions to the end, which restore rdx and rdi. (Does anyone know hot to tell CC that those are clobbered AND read at the same time)?
3. I've included CPU flag detection macros into ./build-aux/m4/bitcoin_secp.m4. I've found existing macros to check common cpu features and to check via builtin already, but I was unable to reliably detect adx (especially with clang, which does not support those in __builtin_cpu_supports. c.f. the list of supported flags

I believe the last thing for a PR would be to check during the CMAKE build process, if BMI2 and ADX are available. Does anyone have other ideas on what we need here?

[sipa]

@dderjoel Thanks for the updates, I'm very glad to see the progress here.

My thinking is that we'll actually want to split this into two separate efforts, which we can discuss and consider with different timelines:

• Replacing the pure-C code with Fiat-Crypto generated C code.
• Introducing CryptoOpt-generated assembly code.

The first is straightforward, I think: your benchmarks show that the Fiat-Crypto generated C code (with the #810 optimization) is competitive with the C code we already have, so I think there is little reason not to just outright replace that code. Since there is no reason to keep the old code too, we don't need any decision logic or build system support to choose one over the other. I have some comments on the implementation, but that can wait for a PR. Overall, this feels very close to usable.

Introducing CryptoOpt is a more complex matter, because of the use of ADCX/ADOX/MULX it cannot be a drop-in replacement for the assembly code we already have. While I have no problem with optimizing exclusively for architectures which do have these, we can't just drop support for those who don't (but falling back to the C implementation, or another less-optimized asm implementation, on those is ok, IMO). There are a number of options:

• Modify CryptoOpt to not use the new instructions, allowing us to use it as a drop-in replacement for the existing asm code. There are of course alternatives to this, like using the output of a well-known, stable, C compiler on the Fiat-Crypto generated C code, and include that output directly as asm code. Either of these options would essentially give us the same level of assurance in the asm code as fiat-crypto-output-fed-to-c-compiler, which is more than what we currently have for the asm code.
• No autodetection, and only enable it when explicitly requested at configure time, which someone can do if they know it'll be run on a machine that supports the new instructions. This could be a first step to introduce the CryptoOpt code to the codebase, but it won't see widespread use in this mode.
• Have runtime autodetection, to determine whether the machine the code is running on (not the compiler host machine as I have the impression your branch is trying to do) has support for the relevant instructions, and use that to determine which code to use. The CPU feature detection code isn't hard to write, but it may involve some changes to the library to have any kind of runtime-switchable features (e.g. when does the autodetect code run, does it need to go into the context for thread-safety, ...) that we'd need to have a discussion about.