secp256k1: Add alternative 64-bit field backend (FieldVal64)

[valery-osheter-cb]

Summary

I'd like to add an alternative 4x64-bit representation of the secp256k1 base
field element (FieldVal64) alongside the current 10x26-bit FieldVal,
selectable at build time. It comes with assembly fast paths for amd64
(BMI2/MULX + ADX) and arm64 (UMULH/MUL), and a portable Go fallback for
all other arches and purego builds. The existing default is unchanged.
I'm opening this before submitting a PR to get maintainer input on the
overall direction.

Motivation

On 64-bit hardware a tightly packed 256-bit representation with a Crandall
reduction performs fewer limb multiplications than the base-2^26 schedule.
In local benchmarks (ECDSA sign/verify, ECDH, pubkey parse/serialize) the
64-bit backend is consistently faster, including under emulation. I'll post
a benchstat comparison in a follow-up comment.

Proposed design

• FieldVal64: four little-endian uint64 limbs, fully reduced after each op,
  matching the existing FieldVal API surface.
• Constant-time throughout: no secret-dependent branches or memory accesses.
  The final conditional subtraction uses CMOVcc (amd64) / CSEL (arm64) and
  arithmetic masking in the portable path.
• Portable building blocks (512-bit multiply/square + Crandall reduce) used on
  all platforms.
• field64Mul / field64Square dispatch:
  • arm64: dedicated asm
  • amd64: MULX/ADX asm, runtime-gated on CPU support, portable fallback
  • everything else / purego: portable Go
• FieldVal type-aliased to FieldVal26 (default) or FieldVal64
  (-tags fieldval64), so curve/ECDSA/Schnorr all run against the chosen type.

Testing

• Differential tests against a math/big oracle and against the portable path
  (asm-vs-Go cross-check), plus edge cases and randomized inputs.

Open questions for maintainers

1. Is a build-tag-selectable alternative backend acceptable, or would you
   prefer a single implementation (e.g. eventually making 64-bit the default
   on 64-bit targets)?
2. CPU feature detection currently uses golang.org/x/sys/cpu. This module
   only depends on blake256 today; would you rather I avoid the new dependency
   and detect BMI2/ADX inline?
3. Any preference on how this is split for review?

Happy to adjust the approach based on your guidance before sending the PR.

[davecgh]

Hey, thanks for reaching out. I'm curious how the performance compares, because I had implemented a 5x52 field (without assembler optimizations or making it selectable since it was exploratory) about 5 years ago and it ultimately ended up slower which was a bit surprising at first, because I had expected a performance advantage due to half as many words versus the 10x26. Ultimately though, because the Go compiler doesn't support 128-bit products via native types (without dropping into asm) it turned out that all of the extra overhead of the bits.Mul64 and bits.Add64 to handle the 128-bit products dominated the savings from fewer overall words. I never spent the time to implement it in asm, but I always suspected it would provide a nice performance enhancement being able to take advantage of native 128-bit/256-bit registers.

I don't see any major issues with the proposed design overall. However, I do have one area of potential concern and a question:

1. Max magnitudes and normalizations vs type alias

This is a particularly tricky area since the existing implementation has several preconditions related to the max magnitudes the values are allowed to reach between normalizations and if FieldVal is swapped out via a type alias, caller's code could very well break if the max magnitudes are smaller.

My gut feeling is that the types will probably ultimately have to be made distinct or a new major API bump will be needed with clear warning about the differences.

2. You mentioned that is would be fully reduced after each op and since it's 4x64, am I correct to assume it will be propagating carries in all of the calculations directly versus allowing them to accumulate internally with periodic normalizations as the existing implementation does?

To answer your questions:

1. A build tag is acceptable. I wouldn't want anything so new to be made the default until it has had significant real-world testing.

2. I really want to avoid any extra dependencies, especially on golang.org/x, because its release policy constantly forces new Go versions and secp256k1 intentionally aims to needlessly avoid force hoisting consumers forward. I'd prefer the CPU feature detection logic to match what I implemented in blake256 (associated asm). It's fully self-contained, commented thoroughly, and easy to extend with new detecting. Plus, the code in the repository will be more consistent that way.

3. Review wise, I personally prefer smaller logical commits that focus on a specific thing while keeping all of the code compiling, working properly, and tests passing. The blake256 full redesign is a good example of a rather significant change that generally exhibits the preferred PR structure. The main thing really is just not dropping a single massive blob of code in a single commit, especially when it's full of asm code that is notoriously difficult to review.

I think starting with the pure Go code + tests in earlier commits and then adding the asm optimizations in later commits is probably the most logical approach since it will provide the full intention and also give a lot more confidence that tests that were originally passing on the pure Go code continue to pass on the asm optimized code paths.

[valery-osheter-cb]

I forked and prepared #3708