Modular arithmetic: compile-time modulus and per-modulus strategy selection
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
evmmaxintoevmone::crypto(#1652) - Rename
modinvtomodinv_pow2(#1657) - Extract
modadd/modsub/modinv_scaledas free functions (#1659) - Fix the modarith benchmarks measuring dead code (#1663)
- Rename
ModArithtoMontgomeryArith,to_monttoto_internal(#1666) - Take the modulus as a template parameter (#1664)
- Drop
FpSpec:FieldElement<Mod>instead ofFieldElement<Spec>. The specs hold only
ORDER, and binding a reference NTTP to astatic constexprmember of the enclosing class
works in both GCC and Clang, so the curve headers keep their shape -
FieldArithconcept andArithForselection - Pseudo-Mersenne backend for secp256k1 (p = 2²⁵⁶ − 2³² − 977, plain representation, so the
conversions are identity) -
sqrin the concept, withmul(x, x)as the fallback - Sparse-modulus refinement in
MontgomeryArith:if constexprdeletes 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, wheremul_amm_256usestarget("bmi2,adx")guarded only by
#ifdef __x86_64__ -
SolinasArithfor 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.textand 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
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- 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.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của ipsilon/evmone
-
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 82/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 3/5 1-2 ngày Mức phù hợp với người mới 56/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 3/5 1-2 ngày Mức phù hợp với người mới 57/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 12/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 4/5 3-5 ngày Mức phù hợp với người mới 52/100
Maintainer thường phản hồi trong vòng 1 ngày
Tất cả issue của ipsilon/evmone
Issue tương tự
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 71/100
ROCm/rocm-libraries#16108 ·
Maintainer thường phản hồi trong vòng 2 ngày
-
asr pass bug intrinsic low priority wrong result
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 67/100
Maintainer thường phản hồi trong vòng 1 ngày
-
👀 needs triage enhancement
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 72/100
rerun-io/rerun#13021 · 1 bình luận ·
Maintainer thường phản hồi trong vòng 2 ngày
-
bug
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 68/100
Maintainer thường phản hồi trong vòng 2 ngày
-
Reference check: findingsĐang mởaudit-reference-check
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
Maintainer thường phản hồi trong vòng 1 ngày