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

オープン
#1,671 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
18/100
issue の種類
リファクタリング
明瞭さ
おおむね明確
活発さ
静か
技術スタック
cpp

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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.
主要言語
C++
スター
979
フォーク
340
平均マージ
12時間 16分
マージ済み PR(30日)
25

環境構築

  • Dockerfile または Docker Compose ファイルあり
  • プルリクエストのテンプレートなし
  • コントリビューションガイドなし

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

ipsilon/evmone のほかの issue

ipsilon/evmone の issue をすべて見る

似ている issue

C++ の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。