Merge #480: Enable benchmark building by default

7a78f60 Print whether we're building benchmarks (Pieter Wuille)
4afec9f Build benchmarks by default (Pieter Wuille)

Pull request description:

  Building benchmarks is fast, and I have on more than one occasion forgotten to pass `--enable-benchmark`, resulting in accidentally benchmarking a former build.

  Build them by default.

Tree-SHA512: ce9096e42d9c19b63644f6b7ae153e92f9a37c3727f380329dfa332ce22a5e43151f1525979bd3516dd12f568e5e389b0acda2c383fca0e80c3cadc1d9b1d55a

Merge #486: Add pippenger_wnaf for multi-multiplication

d2f9c6b Use more precise pippenger bucket windows (Jonas Nick)
4c950bb Save some additions per window in _pippenger_wnaf (Peter Dettman)
a58f543 Add flags for choosing algorithm in ecmult_multi benchmark (Jonas Nick)
36b22c9 Use scratch space dependent batching in ecmult_multi (Jonas Nick)
355a38f Add pippenger_wnaf ecmult_multi (Jonas Nick)
bc65aa7 Add bench_ecmult (Pieter Wuille)
dba5471 Add ecmult_multi tests (Andrew Poelstra)
8c1c831 Generalize Strauss to support multiple points (Pieter Wuille)
548de42 add resizeable scratch space API (Andrew Poelstra)

Pull request description:

  This PR is based on #473 and adds a variant of "Pippengers algorithm" (see [Bernstein et al., Faster batch forgery identification](https://eprint.iacr.org/2012/549.pdf), page 15 and https://github.com/scipr-lab/libff/pull/10) for point multi-multiplication that performs better with a large number of points than Strauss' algorithm.

  

  Thanks to @sipa for providing `wnaf_fixed`, benchmarking, and the crucial suggestion to use affine addition.

  The PR also makes `ecmult_multi` decide which algorithm to use, based on the number of points and the available scratch space.
  For restricted scratch spaces this can be further optimized in the future (f.e. a 35kB scratch space allows batches of 11 points with strauss or 95 points with pippenger; choosing pippenger would be 5% faster).

  As soon as this PR has received some feedback I'll repeat the benchmarks to determine the optimal `pippenger_bucket_window` with the new benchmarking code in #473.

Tree-SHA512: 8e155107a00d35f412300275803f912b1d228b7adff578bc4754c5b29641100b51b9d37f989316b636f7144e6b199febe7de302a44f498bbfd8d463bdbe31a5c

Use more precise pippenger bucket windows

Save some additions per window in _pippenger_wnaf

Add flags for choosing algorithm in ecmult_multi benchmark

Use scratch space dependent batching in ecmult_multi

Add pippenger_wnaf ecmult_multi

Add bench_ecmult

Add ecmult_multi tests

Generalize Strauss to support multiple points

API by Andrew Poelstra.

add resizeable scratch space API

Alignment support by Pieter Wuille.

Merge #479: Get rid of reserved _t in type names

d1dc9df Get rid of reserved _t in type names (Pieter Wuille)

Pull request description:

Tree-SHA512: 5da4a2cb15106c47fbe14346562444eff322a5e4e2386af8b0b879b72e22f08d704ac09746d6a22ff76e8892fc20208932b2a45d01de0e2e089686dabe45e633

Print whether we're building benchmarks

Build benchmarks by default

Get rid of reserved _t in type names

Merge #474: Fix header guards using reserved identifiers

abe2d3e Fix header guards using reserved identifiers (Dan Raviv)

Pull request description:

  Identifiers starting with an underscore and followed immediately by a capital letter are reserved by the C++ standard.

  The only header guards not fixed are those in the headers auto-generated from java.

Tree-SHA512: da31b8d718b3c3ffb81b3d12c93ce2d56c176f19a1936776c843fee069dbaa916946556cea16db34e1f977a937924d72c870230ac26e44386706ecd7cb25ba65

Merge #478: Fixed multiple typos

8c7ea22 Fixed multiple typos (Dimitris Tsapakidis)

Pull request description:

  Forward port of fixes introduced in https://github.com/bitcoin/bitcoin/pull/10633 by @dimitris-t.

Tree-SHA512: a979b3e14bf2660cb0fcd809854654bd0f6277399afe948917be6c061a04835d404e590dc58bcb4a9e2ccfbfb38de944cbdba349092465f637606d3bee49fc16

Fixed multiple typos

Fix header guards using reserved identifiers

Identifiers starting with an underscore and followed immediately by a capital letter are reserved by the C++ standard.

The only header guards not fixed are those in the headers auto-generated from java.

Merge #459: Add pubkey prefix constants to include/secp256k1.h

bc61b91 add pubkey prefix constants to include/secp256k1.h (Andrew Poelstra)

Pull request description:

  In future multisig implementations we will need to pass nonces around, which are algebraically pubkeys but should not be decodable as pubkeys. The way to do this is to change the prefix byte from the ordinary 0x02/0x03 to something else. However, some forks (notably `secp256k1-zkp`) have started using some bytes for their own encodings, and if we continue to use hardcoded constants the risk of conflict is increased.

  This commit puts the prefixes used by the main library into the `include/secp256k1.h` so that the constants we're using will at least be in a standard easy-to-reference place.

Tree-SHA512: 37fa25be5074b7c519a9c69421320a62f32a3818f144254eb57f96c6657b993fc01962a5c670574275d1c59b095a6c89e60736123f032d6736907284eac526d7

Merge #470: Fix wnaf_const documentation

768514b Fix wnaf_const documentation with respect to return value and number of words set (Jonas Nick)

Pull request description:

Tree-SHA512: e2e49036c5930c74fff12626957a43000e5f86180791f2b857d279e83c609663ee5cbee4c3380f3df3d29e493f40051d63a8eff1badeea99e06652d9e72f4d29

Fix wnaf_const documentation with respect to return value and number of words set

Merge #458: Fix typo in API documentation

b0452e6 Fix typo in API documentation (Tim Ruffing)

Pull request description:

Tree-SHA512: 0376756fc36004e9bb205c6b811e8b28ecd595db1fc2b577bf27c5c227d81ec8bca2e44cfab91fb76c9640d0f7c99970ce9ab94d72e26289cc8faeb747337309

Merge #440: Fix typos

4c0f32e Fix typo: "Agressive" → "Aggressive" (practicalswift)
73aca83 Fix typo: "exectured" → "executed" (practicalswift)

Pull request description:

Tree-SHA512: 1dbb47789489aec4c133b049ccd007b67d719fe1e2500ba4c6242274a3b537027ceb17a311fca5e0e0324f0ecd48a53e84c0f51514f00fa7ef533ab3e6c87bd3

Merge #468: Remove redundant conditional expression

2e1ccdc Remove redundant conditional expression (Dag Robole)

Pull request description:

Tree-SHA512: 999ed3d9d805ec48a92a17554097fcd9d62c2fe859346d381d3a7b38b767e45f57df6cd71eb6dddbea343e4e180c844900fed37d88d21f5a851bd044212aff2e

Remove redundant conditional expression

add pubkey prefix constants to include/secp256k1.h

Fix typo in API documentation

Merge #454: Remove residual parts from the schnorr expirement.

5e95bf2 Remove residual parts from the schnorr expirement. (Gregory Maxwell)

Tree-SHA512: de1e56cc54443e29a60787996a1b1381b0b84eacb87a8f1af06b5ba3900b1771c3a04fd547c65e21979e3c08c3a45d258d699eb951a956f8e617833c5396ecfe

Remove residual parts from the schnorr expirement.

Merge #452: Minor optimizations to _scalar_inverse to save 4M

465159c Further shorten the addition chain for scalar inversion. (Brian Smith)
cf12fa1 Minor optimizations to _scalar_inverse to save 4M (Peter Dettman)

Tree-SHA512: b03ae53bd48435f8ef8a89ba3b45f9a35f3f3c6cfba7deb6820ab2146205656d198e4317a4cb98a986f434df244ae735313d303d0ce5a5c40519d37621238957

Merge #437: Unroll secp256k1_fe_(get|set)_b32 to make them much faster.

a2b6b19 Fix benchmark print_number infinite loop. (Gregory Maxwell)
8b7680a Unroll secp256k1_fe_(get|set)_b32 for 10x26. (Gregory Maxwell)
aa84990 Unroll secp256k1_fe_(get|set)_b32 for 5x52. (CryptoGuru)

Tree-SHA512: b17fa454dc4ef614305e10575b0f87c3b37d398d6d3996d5bbbb8e27b0d9841aa13b3cffe93d13dc637c8c3071f8565919574ec0b07f02bf3b0eb6faf4b93251

Further shorten the addition chain for scalar inversion.

Reduce the number of squarings by one and reduce the number of
multiplications by three.

Fix benchmark print_number infinite loop.

Unroll secp256k1_fe_(get|set)_b32 for 10x26.

field_get_b32: min 0.890us / avg 0.905us / max 0.956us
field_set_b32: min 1.12us / avg 1.15us / max 1.19us

becomes

field_get_b32: min 0us / avg 0.000000119us / max 0.000000238us
field_set_b32: min 0.0532us / avg 0.0584us / max 0.0782us

Unroll secp256k1_fe_(get|set)_b32 for 5x52.

field_get_b32: min 0.647us / avg 0.666us / max 0.751us
field_set_b32: min 0.551us / avg 0.571us / max 0.624us

becomes

field_get_b32: min 0us / avg 0.0000000477us / max 0.000000238us
field_set_b32: min 0us / avg 0.0000000238us / max 0.000000238us

(Patch from https://bitcointalk.org/index.php?topic=1740973.0
 _get was reversed from the patch because this order appeared
 somewhat faster in testing.)

Signed-off-by: Gregory Maxwell <[email protected]>

Minor optimizations to _scalar_inverse to save 4M

- Precalculate x^5 and use for "01010" patterns during accumulation. (net -2M)
- Further use of x^5 to allow shorter addition chain (net -2M)

Merge #408: Add `secp256k1_ec_pubkey_negate` and `secp256k1_ec_privkey_negate`

8e48aa6 Add `secp256k1_ec_pubkey_negate` and `secp256k1_ec_privkey_negate` (Andrew Poelstra)

Tree-SHA512: 28eeca0b04001958ad86b3c802e33a13273514e9e9802d5b358fd577dc95421a2cffb5591716bea10300717f742f0941c465b9df71dbb4c66d174c643887e06f

Merge #441: secp256k1_context_randomize: document.

72d952c FIXUP: Missing "is" (Rusty Russell)
70ff29b secp256k1_context_randomize: document. (Rusty Russell)

Tree-SHA512: c1f48431e07a23b572838d63250d5a356ff5b321dd242cf0af5227ee89b9795d49a762b0c7311bb7284ccd487c68b3d1f16cf6824eac30fc3f8becdf2b891dad

Merge #444: test: Use checked_alloc

5eb030c test: Use checked_alloc (Wladimir J. van der Laan)

Tree-SHA512: f0fada02664fca3b4f48795ce29a187331f86f80fc1605150fcfc451e7eb4671f7b5dff09105c9927e28af6d1dafd1edad1671dddd412110f4b5950153df499d

Merge #449: Remove executable bit from secp256k1.c

51b77ae Remove executable bit from secp256k1.c (Emil Rus)

Remove executable bit from secp256k1.c

test: Use checked_alloc

FIXUP: Missing "is"

Signed-off-by: Rusty Russell <[email protected]>

secp256k1_context_randomize: document.

I think I summarized it correctly after IRC discussion with gmaxwell
and andytoshi; I didn't know it existed :(

It's regrettable to expose this level of detail, but users need to know
this to make a decision about how to use it.

Signed-off-by: Rusty Russell <[email protected]>

Fix typo: "Agressive" → "Aggressive"

Fix typo: "exectured" → "executed"

Merge #428: Exhaustive recovery

2cee5fd exhaustive tests: add recovery module (Andrew Poelstra)
678b0e5 exhaustive tests: remove erroneous comment from ecdsa_sig_sign (Andrew Poelstra)
03ff8c2 group_impl.h: remove unused `secp256k1_ge_set_infinity` function (Andrew Poelstra)
a724d72 configure: add --enable-coverage to set options for coverage analysis (Andrew Poelstra)
b595163 recovery: add tests to cover API misusage (Andrew Poelstra)
6f8ae2f ecdh: test NULL-checking of arguments (Andrew Poelstra)
25e3cfb ecdsa_impl: replace scalar if-checks with VERIFY_CHECKs in ecdsa_sig_sign (Andrew Poelstra)

Add `secp256k1_ec_pubkey_negate` and `secp256k1_ec_privkey_negate`

exhaustive tests: add recovery module

Merge #433: Make the libcrypto detection fail the newer API.

12de863 Make the libcrypto detection fail the newer API. (Gregory Maxwell)

Make the libcrypto detection fail the newer API.

OpenSSL 1.1 makes ECDSA_SIG opaque and our tests need access
inside this object.

The comparison tests against OpenSSL aren't important for most
users, but the build failing is...

exhaustive tests: remove erroneous comment from ecdsa_sig_sign

Mathematically, we always overflow when using the exhaustive tests (because our
scalar order is 13 and our field order is on the order of 2^256), but the
`overflow` variable returned when parsing a b32 as a scalar is always set
to 0, to prevent infinite (or practically infinite) loops searching for
non-overflowing scalars.

Merge #427: Remove Schnorr from travis as well

8eecc4a Remove Schnorr from travis as well (Pieter Wuille)

group_impl.h: remove unused `secp256k1_ge_set_infinity` function

Also remove `secp256k1_fe_verify` from field_*_.impl.h when VERIFY is not defined

configure: add --enable-coverage to set options for coverage analysis

recovery: add tests to cover API misusage

Remove Schnorr from travis as well

ecdh: test NULL-checking of arguments

Boosts the ECDH module to 100% coverage

ecdsa_impl: replace scalar if-checks with VERIFY_CHECKs in ecdsa_sig_sign

Whenever ecdsa_sig_sign is called, in the case that r == 0 or r overflows,
we want to retry with a different nonce rather than fail signing entirely.
Because of this, we always check the nonce conditions before calling
sig_sign, so these checks should always pass (and in particular, they
are inaccessible through the API and appear as uncovered code in test
coverage).

Merge #310: Add exhaustive test for group functions on a low-order subgroup

b4ceedf Add exhaustive test for verification (Andrew Poelstra)
83836a9 Add exhaustive tests for group arithmetic, signing, and ecmult on a small group (Andrew Poelstra)
20b8877 Add exhaustive test for group functions on a low-order subgroup (Andrew Poelstra)

Add exhaustive test for verification

Add exhaustive tests for group arithmetic, signing, and ecmult on a small group

If you compile without ./configure --enable-exhaustive-tests=no,
this will create a binary ./exhaustive_tests which will execute
every function possible on a group of small order obtained by
moving to a twist of our curve and locating a generator of small
order.

Currently defaults to order 13, though by changing some #ifdefs
you can get a couple other ones. (Currently 199, which will take
forever to run, and 14, which won't work because it's composite.)

TODO exhaustive tests for the various modules

Add exhaustive test for group functions on a low-order subgroup

We observe that when changing the b-value in the elliptic curve formula
`y^2 = x^3 + ax + b`, the group law is unchanged. Therefore our functions
for secp256k1 will be correct if and only if they are correct when applied
to the curve defined by `y^2 = x^3 + 4` defined over the same field. This
curve has a point P of order 199.

This commit adds a test which computes the subgroup generated by P and
exhaustively checks that addition of every pair of points gives the correct
result.

Unfortunately we cannot test const-time scalar multiplication by the same
mechanism. The reason is that these ecmult functions both compute a wNAF
representation of the scalar, and this representation is tied to the order
of the group.

Testing with the incomplete version of gej_add_ge (found in 5de4c5dff^)
shows that this detects the incompleteness when adding P - 106P, which
is exactly what we expected since 106 is a cube root of 1 mod 199.

Merge #425: Remove Schnorr experiment

e06e878 Remove Schnorr experiment (Pieter Wuille)

Remove Schnorr experiment

Merge #407: Modify parameter order of internal functions to match API parameter order

353c1bf Fix secp256k1_ge_set_table_gej_var parameter order (llamasoft)
541b783 Fix secp256k1_ge_set_all_gej_var parameter order (llamasoft)
7d893f4 Fix secp256k1_fe_inv_all_var parameter order (llamasoft)

Merge #411: Remove guarantees about memcmp-ability

91219a1 Remove guarantees about memcmp-ability (Andrew Poelstra)

Merge #421: Update scalar_4x64_impl.h

9d67afa Update scalar_4x64_impl.h (Alex-GR)

Merge #422: Restructure nonce clearing

3769783 Restructure nonce clearing (bgorlick)
0f9e69d Restructure nonce clearing (bgorlick)

Restructure nonce clearing

Make sure we clear the nonce data even if the nonce function fails (it may have written partial data), and call memset only once in the case we iterate to produce a valid signature.

Restructure nonce clearing

Make sure we clear the nonce data even if the nonce function fails (it may have written partial data), and call memset only once in the case we iterate to produce a valid signature.

Update scalar_4x64_impl.h

XOR reg,reg instead of MOV 0 to reg. It should be at least equal in all architectures and faster in some else.

Merge #413: fix auto-enabled static precompuatation

00c5d2e fix auto-enabled static precompuatation (Cory Fields)

fix auto-enabled static precompuatation

This was broken in aa0b1fd14979145d54ef85485cb497a9cdbc22c7

Remove guarantees about memcmp-ability

Merge #410: Add string.h include to ecmult_impl

0bbd5d4 Add string.h include to ecmult_impl (Wladimir J. van der Laan)

Add string.h include to ecmult_impl

`memcpy` and `memset` are used, so include the appropriate header
for the declaration.

Fix secp256k1_ge_set_table_gej_var parameter order

Rearranged secp256k1_ge_set_table_gej_var parameters so length comes last (it modifies both *a and *zr).

Fix secp256k1_ge_set_all_gej_var parameter order

Rearranged secp256k1_ge_set_all_gej_var parameters so length comes after *a.

Fix secp256k1_fe_inv_all_var parameter order

Rearranged secp256k1_fe_inv_all_var parameters so length is after array.
Text editor removed some trailing whitespaces.

Merge #405: Make secp256k1_fe_sqrt constant time

926836a Make secp256k1_fe_sqrt constant time (Pieter Wuille)

Make secp256k1_fe_sqrt constant time

Merge #404: Replace 3M + 4S doubling formula with 2M + 5S one

8ec49d8 Add note about 2M + 5S doubling formula (Andrew Poelstra)

Add note about 2M + 5S doubling formula

Merge #400: A couple minor cleanups

ac01378 build: add -DSECP256K1_BUILD to benchmark_internal build flags (Andrew Poelstra)
a6c6f99 Remove a bunch of unused stdlib #includes (Andrew Poelstra)

build: add -DSECP256K1_BUILD to benchmark_internal build flags

gcc 6 will warn about our non-null checks when SECP256K1_BUILD
our NONNULL marker is nontrivial. This occurs unless SECP256K1_BUILD
is set, which we had forgotten to do for the internal benchmarks,
which compile directly against the library instead of linking.

Remove a bunch of unused stdlib #includes

Merge #403: configure: add flag to disable OpenSSL tests

a9b2a5d configure: add flag to disable OpenSSL tests (Andrew Poelstra)

configure: add flag to disable OpenSSL tests

OpenSSL messes up valgrind.

Merge #402: Add support for testing quadratic residues

e6e9805 Add function for testing quadratic residue field/group elements. (Pieter Wuille)
efd953a Add Jacobi symbol test via GMP (Peter Dettman)

Add function for testing quadratic residue field/group elements.

Add Jacobi symbol test via GMP

Also add native Jacobi symbol test (Andrew)

Rebased-by: Andrew Poelstra
Rebased-by: Pieter Wuille

Merge #401: ecmult_const: unify endomorphism and non-endomorphism skew cases

c6191fd ecmult_const: unify endomorphism and non-endomorphism skew cases (Andrew Poelstra)

ecmult_const: unify endomorphism and non-endomorphism skew cases

We now do a skew correction even without the endomorphism optimization,
which costs one additional group addition but unifies a lot of code.

Merge #378: .gitignore build-aux cleanup

70141a8 Update .gitignore (upgradeadvice)

Merge #384: JNI: align shared files copyright/comments to bitcoinj's

6ceea2c align shared files copyright/comments to bitcoinj's (GreenAddress)

Merge #399: build: verify that the native compiler works for static precomp

aa0b1fd build: verify that the native compiler works for static precomp (Cory Fields)

Merge #398: Test whether ECDH and Schnorr are enabled for JNI

eee808d Test whether ECDH and Schnorr are enabled for JNI (Pieter Wuille)

build: verify that the native compiler works for static precomp