- Trades 1 _half for 3 _mul_int and 2 _normalize_weak
- Updated formula and comments in _gej_add_ge
- Added internal benchmark for _fe_half

At count=64, this makes the test take around 1% of the total time.

Python 3 often returns iterable map objects where Python 2 returned
list. We can just them down to lists explicitly.

Overlooked in 13c88ef.

- Add field method _fe_get_bounds

- formula_secp256k1_gej_double_var
- formula_secp256k1_gej_add_ge

According to [autoconf 2.70](https://www.gnu.org/software/autoconf/manual/autoconf-2.70/html_node/Obsolete-Macros.html)
documentation, the `AC_PROG_CC_C89' is replaced by `AC_PROG_CC`, which
defines the same variable `ac_cv_prog_cc_c89`.

Avoids the following message:
```
configure.ac:23: warning: The macro `AC_PROG_CC_C89' is obsolete.
```

Also, remove deprecated `AM_PROG_CC_C_O`.

The macOS CI tasks often error fail when doing `brew update` with
git fetch errors:
```
remote: fatal: packfile /data/repositories/b/nw/b6/07/5c/123272362/network.git/objects/pack/pack-2139bd07361b62a358e380a0e7d58ec35593d191.pack cannot be accessed
fatal: protocol error: bad pack header
Error: Fetching /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core failed!
```
Superficially this seems to be a problem on the GitHub server because
the message shows a "remote" error. But it seems we're the only one in
the world running into this specific issue when doing `brew update`, so
it's more likely that the something else is the culprit, and this error
message is just a symptom.

This commit replaces `brew update` with a complete reinstallation of
brew. This is essentially a shot in the dark but it's worth a try, and
I doubt it's significantly more expensive. If that won't work, we may
consider simply retrying `brew update` a few times.

The prover, when run on recent sage versions,  failed to prove some of its
goals due to a change in sage. This commit adapts our code accordingly.
The prover passes again after this commit.

Even if they are constants created in the formula functions. We now
lift integer constants to fastfracs.

ebb1bee sage: Ensure that constraints are always fastfracs (Tim Ruffing)
d8d5485 ci: Run sage prover on CI (Tim Ruffing)
77cfa98 sage: Normalize sign of polynomial factors in prover (Tim Ruffing)
eae7586 sage: Exit with non-zero status in case of failures (Tim Ruffing)
b54d843 sage: Fix printing of errors (Tim Ruffing)
e108d00 sage: Fix incompatibility with sage 9.4 (Tim Ruffing)

Pull request description:

ACKs for top commit:
  sipa:
    ACK ebb1bee
  jonasnick:
    ACK ebb1bee

Tree-SHA512: 7a4732fd31d925d3dff471911183acc465ddcadbb5c88c46995502df61a913433c7639cb52fad3db72373b7cc47b9b0f063f7f5d5f8189c9ef998955e409479f

d9396a5 ci: Attempt to make macOS builds more reliable (Tim Ruffing)

Pull request description:

ACKs for top commit:
  jonasnick:
    ACK d9396a5

Tree-SHA512: 68df44107d74671de148e9c3e6dbc6b16bec937137d7d9771efce10f5d66459559b372346d05ecc23237b2e3af9479156f733219717cb93f5204f9ea5b2636a9

…cro AC_PROG_CC_C89

e0db3f8 build: Replace use of deprecated autoconf macro AC_PROG_CC_C89 (laanwj)

Pull request description:

ACKs for top commit:
  real-or-random:
    utACK e0db3f8
  jonasnick:
    ACK e0db3f8

Tree-SHA512: 00d6719fcdea69d002c795bbed07ccbd69900fef7dcba8ee42aa4e77765034feeb036ac9147b7fccc88b41623f735f62d4c72e25b3a1e68caad08a1237d6c5f5

This reverts commit d9396a5, which
didn't have the desired effect.

…andom failures

e51ad3b ci: Retry `brew update` a few times to avoid random failures (Tim Ruffing)
b1cb969 ci: Revert "Attempt to make macOS builds more reliable" (Tim Ruffing)

Pull request description:

ACKs for top commit:
  jonasnick:
    ACK e51ad3b

Tree-SHA512: cb0b81ac8d81fe8ea58afa7382d3f922bd4eb713645c5d0b99f9de963c9906273f5d573a9272e8f6cdb16ffcca5e162c088cc2b0772278f68930f8cb726824be

Co-authored-by: Elliott Jin <elliott.jin@gmail.com>

…oint with random inputs

3531a43 ecdh: Make generator_basepoint test depend on global iteration count (Tim Ruffing)
c881dd4 ecdh: Add test computing shared_secret=basepoint with random inputs (Tim Ruffing)

Pull request description:

ACKs for top commit:
  jonasnick:
    ACK 3531a43

Tree-SHA512: 5a2e47bad7ec5b3fd9033283fe00e54563b7b1655baf2b8ca39718deceddcc816bb8fcda0d07af6f1f8a785642da5dc69b7df52a1ddd445a3a98a5d5ecff6780

…_double

e848c37 Update sage files for new formulae (Peter Dettman)
d64bb5d Add fe_half tests for worst-case inputs (Peter Dettman)
4eb8b93 Further improve doubling formula using fe_half (Peter Dettman)
557b31f Doubling formula using fe_half (Pieter Wuille)
2cbb4b1 Run more iterations of run_field_misc (Pieter Wuille)
9cc5c25 Add test for secp256k1_fe_half (Pieter Wuille)
925f78d Add _fe_half and use in _gej_add_ge (Peter Dettman)

Pull request description:

  - Trades 1 _half for 3 _mul_int and 2 _normalize_weak

  Gives around 2-3% faster signing and ECDH, depending on compiler/platform.

ACKs for top commit:
  sipa:
    utACK e848c37
  jonasnick:
    ACK e848c37
  real-or-random:
    ACK e848c37

Tree-SHA512: 81a6c93b3d983f1b48ec8e8b6f262ba914215045a95415147f41ee6e85296aa4d0cbbad9f370cdf475571447baad861d2cc8e0b04a71202d48959cb8a098f584

Co-authored-by: Jonas Nick <jonasd.nick@gmail.com>

Co-authored-by: Jonas Nick <jonasd.nick@gmail.com>

Co-authored-by: Jonas Nick <jonasd.nick@gmail.com>

21b2eba configure: Remove redundant pkg-config code (Tim Ruffing)

Pull request description:

  This removes code that detects the pkg-config tool. We used this
  back in the days when we had dependencies. ;) It can always be brought
  back if we'll need it in the future.

  Note that we still deliver a .pc file for this library, and there is
  code in Makefile.am to install it. But this does not require the
  pkg-config tool; only consumers of the .pc file will need it. This can
  be verified by running `make install` (maybe after `mkdir /tmp/pre` and
  `./configure --prefix=/tmp/pre` and checking that the .pc file is
  installed correctly.

ACKs for top commit:
  theuni:
    ACK 21b2eba.
  fanquake:
    ACK 21b2eba

Tree-SHA512: 07affcd0e85f59d10479f279c832b1384208bead2fd152e0d1e3d99167dba4e14dbe87b0bc9c367f0f18da3d37f1d51de064689bff329ee5b01cacfe54e5ede7

_tagged_sha256 simply cannot have invalid inputs.

The other functions could in some sense have invalid inputs but only in
violation of the type system. For example, a pubkey could be invalid but
invalid objects of type secp256k1_pubkey either can't be obtained
via the API or will be caught by an ARG_CHECK when calling pubkey_load.

This is consistent with similar functions in the public API, e.g.,
_ec_pubkey_negate or _ec_pubkey_serialize.

…t64_t

f8d9174 Add SHA256 bit counter tests (Tim Ruffing)
9b514ce Add test vector for very long SHA256 messages (Tim Ruffing)
8e3dde1 Simplify struct initializer for SHA256 padding (Tim Ruffing)
eb28464 Change SHA256 byte counter from size_t to uint64_t (Tim Ruffing)

Pull request description:

  This avoids that the SHA256 implementation would produce wrong paddings
  and thus wrong digests for messages of length >= 2^32 bytes on 32-bit
  platforms.

  This is not exploitable in any way since the SHA256 API is an internal
  API and we never call it with that long messages.

  This also simplifies the struct initializer for the padding.
  Since missing elements are initialized with zeros, this change is
  purely syntactical.

ACKs for top commit:
  sipa:
    utACK f8d9174
  jonasnick:
    ACK f8d9174

Tree-SHA512: 4fba64b255ef34bb144e4ac6d796798d620d6a7a0f3be409a46b98a8aedb129be19a6816b07caa4d1a3862a01769b42ce70240690fddc6231d591e6c06252750

b8f8b99 docs: Fix return value for functions that don't have invalid inputs (Tim Ruffing)
f813bb0 schnorrsig: Adapt example to new API (Tim Ruffing)
99e6568 schnorrsig: Rename schnorrsig_sign to schnorsig_sign32 and deprecate (Tim Ruffing)
fc94a2d Use SECP256K1_DEPRECATED for existing deprecated API functions (Tim Ruffing)
3db0560 Add SECP256K1_DEPRECATED attribute for marking API parts as deprecated (Tim Ruffing)

Pull request description:

  Should be merged before bitcoin-core#995 if we want this.

  I suspect the only change here which is debatable on a conceptual level is the renaming. I can drop this of course.

ACKs for top commit:
  sipa:
    utACK b8f8b99
  jonasnick:
    ACK b8f8b99

Tree-SHA512: 7c5b9715013002eecbf2e649032673204f6eaffe156f20e3ddf51fab938643847d23068f11b127ef3d7fe759e42a20ecaf2ec98718d901ef9eaadbc9853c1dfe

…dules as experimental

7f09d0f README: mention that ARM assembly is experimental (Jonas Nick)
80cf4ee build: stop treating schnorrsig, extrakeys modules as experimental (Jonas Nick)

Pull request description:

  Fixes bitcoin-core#992

ACKs for top commit:
  real-or-random:
    ACK 7f09d0f
  fanquake:
    ACK 7f09d0f - When this is in, I think we'll do a subtree update in Core, and prune some build cruft on our side.

Tree-SHA512: 13deb82dcca88bacb2cd5c1c589a8d4af2277c4d675262337ae4d7e93eb41d43825dda4945ca1c202c36aaa2e6fd42de9c6d711fe8d71bce578368281db698b2

Recent compilers compile the two new functions to very efficient code
on various platforms. In particular, already GCC >= 5 and clang >= 5
understand do this for the read function, which is the one critical
for performance (called 16 times per SHA256 transform).

Fixes bitcoin-core#1080.

…dules

55512d3 doc: clean up module help text in configure.ac (Elliott Jin)
d9d94a9 doc: mention optional modules in README (Elliott Jin)

Pull request description:

ACKs for top commit:
  real-or-random:
    utACK 55512d3
  jonasnick:
    ACK 55512d3

Tree-SHA512: ae4ec355730983117c5e9a8a8abd17aaf42afe6f8f8f7474a551df6269a62094883e0827d2f3642e3ed6eb26cf71982c20f7ac27498cb4bd7e4aea57ec308d6a

- Updated _gej_add_var, _gej_add_ge_var, _gej_add_zinv_var
- 2 fewer _fe_negate in each method
- Updated operation counts and standardize layout
- Added internal benchmark for _gej_add_zinv_var
- Update sage files (fixed by Tim Ruffing)

37d3692 tests: Add tests for _read_be32 and _write_be32 (Tim Ruffing)
616b43d util: Remove endianness detection (Tim Ruffing)
8d89b9e hash: Make code agnostic of endianness (Tim Ruffing)

Pull request description:

  Recent compilers compile the two new functions to very efficient code
  on various platforms. In particular, already GCC >= 5 and clang >= 5
  understand do this for the read function, which is the one critical
  for performance (called 16 times per SHA256 transform).

  Fixes bitcoin-core#1080.

ACKs for top commit:
  sipa:
    utACK 37d3692
  robot-dreams:
    ACK 37d3692

Tree-SHA512: b03cec67756fb3c94ca8e7e06f974136050efd5065f392dba6eed4d0dbe61dbf93dad054627267225bac1bb302bb025f86588612ef7d4beeb834466686c70b8f

2f984ff Save negations in var-time group addition (Peter Dettman)

Pull request description:

  - Updated _gej_add_var, _gej_add_ge_var, _gej_add_zinv_var
  - 2 fewer _fe_negate in each method
  - Updated operation counts and standardize layout
  - Added internal benchmark for _gej_add_zinv_var

  benchmark_internal shows about 2% speedup in each method as a result (64bit).

ACKs for top commit:
  real-or-random:
    ACK 2f984ff
  jonasnick:
    ACK 2f984ff

Tree-SHA512: 01366fa23c83a8dd37c9a0a24e0acc53ce38a201607fe4da6672ea5618d82c62d1299f0e0aa50317883821539af739ea52b6561faff230c148e6fdc5bc5af30b

…ECK`

7efc983 Fix the false positive of `SECP_64BIT_ASM_CHECK` (Sprite)

Pull request description:

  I'm trying to compile this project for RISC-V architecture, and I encountered errors:
  ```
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r15' in 'asm'
     28 | __asm__ __volatile__(
        | ^
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r14' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r13' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r12' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r11' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r10' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r9' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%r8' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%rdx' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%rcx' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: unknown register name '%rax' in 'asm'
  src/field_5x52_asm_impl.h:28:1: error: output number 0 not directly addressable
  src/field_5x52_asm_impl.h: In function 'secp256k1_fe_sqr':
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r15' in 'asm'
    298 | __asm__ __volatile__(
        | ^
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r14' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r13' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r12' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r11' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r10' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r9' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%r8' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%rdx' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%rcx' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%rbx' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: unknown register name '%rax' in 'asm'
  src/field_5x52_asm_impl.h:298:1: error: output number 0 not directly addressable
  ```

  After further investigation I found that for RISC-V, macro `USE_ASM_X86_64` was defined unexpectedly, and `checking for x86_64 assembly availability... yes` appeared in the compilation log file, which means `SECP_64BIT_ASM_CHECK` was not working as expected.

  For unknown reasons, `AC_COMPILE_IFELSE` does not check if `__asm__` can be compiled, and an example can verify this point:
  ```m4
  AC_DEFUN([SECP_64BIT_ASM_CHECK],[
  AC_MSG_CHECKING(for x86_64 assembly availability)
  AC_COMPILE_IFELSE([AC_LANG_PROGRAM([[
    #include <stdint.h>]],[[
    __asm__ __volatile__("this is obviously wrong");
    ]])],[has_64bit_asm=yes],[has_64bit_asm=no])
  AC_MSG_RESULT([$has_64bit_asm])
  ])
  ```

  It always gives results: `checking for x86_64 assembly availability... yes`

  After testing, replacing `AC_COMPILE_IFELSE` with `AC_LINK_IFELSE` can correctly check if `__asm__` can be compiled and make the project able to compile for RISC-V.

ACKs for top commit:
  real-or-random:
    ACK 7efc983

Tree-SHA512: 7318dd42004b2930cfcd6541c5a9ce0aa186e2179a668b76089a908bea8d9f70fcfdb264512f971e395a3ce9dc7f9ca24c8f3d46175cad2972a2d713f518ed85

- `schnorrsig_batch_context_create`
- `schnorrsig_batch_context_destroy`
- simple test that calls both create and destroy (failing)

destroying the scratch space when its alloc_size > 0 leads to an error

…d points) scratch space

added two new arguments to strauss_batch:
1. scratch_sclrs
2. scratch_pts

if scrach_sclrs = scratch_pts = NULL: strauss_batch allocates points and scalars
else strauss assumes (points, scalars) are already present in scratch

secp256k1_context obj is used for its error_callback function