Modular arithmetic: compile-time modulus and per-modulus strategy selection

Đang mở
#1,671 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
18/100
Loại issue
Tái cấu trúc
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Ít trao đổi
Công nghệ
cpp
Lĩnh vực
blockchain, cryptography

Hướng nghiên cứu

Start from lib/evmone_precompiles/modarith.hpp and the already-landed steps listed in the issue (#1652, #1657, #1659, #1663). Follow the remaining checklist: rename ModArith/to_mont (#1666), take the modulus as an NTTP (#1664), drop FpSpec for FieldElement<Mod>, then ArithFor and backends. Done means the two-layer design, concept, and backends land with the listed multiplication counts beaten in the precompiles benchmark disassembly; resolve the CodSpeed vs hardware-counter mismatch before treating regressions as real.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Rework the modular arithmetic in lib/evmone_precompiles/modarith.hpp into two layers: a
FieldElement value type over an arithmetic backend picked per modulus. Both keyed by a
const auto& reference to the modulus, so a backend can classify the modulus itself and no
per-curve tagging is needed:

template <const auto& Mod>
using ArithFor = std::conditional_t<pseudo_mersenne_c(Mod) != 0,
    PseudoMersenneArith<Mod>, MontgomeryArith<Mod>>;
Steps
  • Move evmmax into evmone::crypto (#1652)
  • Rename modinv to modinv_pow2 (#1657)
  • Extract modadd/modsub/modinv_scaled as free functions (#1659)
  • Fix the modarith benchmarks measuring dead code (#1663)
  • Rename ModArith to MontgomeryArith, to_mont to to_internal (#1666)
  • Take the modulus as a template parameter (#1664)
  • Drop FpSpec: FieldElement<Mod> instead of FieldElement<Spec>. The specs hold only
    ORDER, and binding a reference NTTP to a static constexpr member of the enclosing class
    works in both GCC and Clang, so the curve headers keep their shape
  • FieldArith concept and ArithFor selection
  • Pseudo-Mersenne backend for secp256k1 (p = 2²⁵⁶ − 2³² − 977, plain representation, so the
    conversions are identity)
  • sqr in the concept, with mul(x, x) as the fallback
  • Sparse-modulus refinement in MontgomeryArith: if constexpr deletes the carry tracking.
    Requires extracting the multiplication out of the class
  • Asm kernels with constructor-based cpuid dispatch. Also fixes the latent SIGILL on
    crypto/modexp_asm, where mul_amm_256 uses target("bmi2,adx") guarded only by
    #ifdef __x86_64__
  • SolinasArith for p256, only if it beats the baseline below
Baseline to beat

Multiplications per 256-bit Montgomery multiplication, counted in the disassembly of the linked
precompiles benchmark (GCC 15.2, -O3, x86-64-v2):

modulus multiplications of which imul body
bn254 Fp 36 4 319 insns
secp256k1 Fp 28 4 300 insns
secp256k1 Fr 36 4 317 insns
secp256r1 Fp 28 0 289 insns
secp256r1 n 36 4 319 insns

secp256k1 loses 8 multiplications to its three all-ones limbs, secp256r1 loses 8 to its zero limb
and all four imul because N′ == 1. Both come from constant folding alone, so a hand-written
strategy has to beat 28, not 36.

GCC already clones the multiplication per modulus. Before #1664 it also kept one unspecialised copy
with the modulus loaded from memory, called from secp256k1_ecdsa_recover (8 sites),
secp256r1::verify (7), ecpairing_execute (6), ecadd_execute (6), ecmul_execute (4) and
add_affine<bn254> (4).

Open
  • Distinct backend types plus ArithFor, or one template dispatching internally with
    if constexpr? The internal representation differs per strategy, so the conversions branch too.
  • Redundant limb layouts (5×52) are out of scope.
  • CodSpeed simulation reports 2–10% regressions on #1664 where hardware counters show ≤2% change in
    instructions and a flat wall clock. #1666 has byte-identical .text and CodSpeed reports no
    change on it, so the baseline is not stale. Worth resolving before the gate drives decisions here.
Ngôn ngữ chính
C++
Star
979
Fork
340
Merge trung bình
12 giờ 16 phút
Pull request đã merge (30 ngày)
25

Chuẩn bị môi trường

  • Có Dockerfile hoặc tệp Docker Compose
  • Không có mẫu pull request
  • Không có hướng dẫn đóng góp

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của ipsilon/evmone

Tất cả issue của ipsilon/evmone

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.