# Prepared Multiscalar Zero-Checks for Halo 2 Verification This engineering page describes Zakura's in-development work specializing the multiscalar multiplication (MSM) that ends Halo 2 proof verification. The verifier's final equation is evaluated over the Vesta curve, most of its bases are fixed, and its result is only ever compared against the group identity. The page describes preparing transformed versions of those fixed bases, recoding scalars jointly over the Eisenstein integers, and replacing a large coefficient-bucket alphabet with a small prepared codebook. Neither the human page nor this alternate names pull requests or tracks the merge status of individual changes. ## The workload A Halo 2 verifier accumulates polynomial commitments and other terms into an equation S = sum_i [k_i] P_i and accepts when S is the group identity O. The workload differs from a generic MSM in four ways: the generators of the fixed uniform random string (URS) and the fixed points w and u are reused across proofs; the scalars vary and should be treated as uniformly distributed; a relatively small number of proof commitments contribute non-fixed points; and the caller needs only the Boolean result S = O, never the point S itself. The check is exact: it evaluates the group equation itself, not a probabilistic substitute. The page covers only this single-equation, single-proof check. All scalars and points in this workload are public verifier data, so variable-time algorithms are appropriate. None of this transfers to secret-dependent scalar multiplication, which keeps its constant-time paths. ## Joint Eisenstein recoding and the orbit backend Vesta has j-invariant zero and a cheap order-three endomorphism phi(x, y) = (zeta x, y), acting on the prime-order group as multiplication by a known scalar lambda. GLV decomposes a scalar as k = a + b*lambda (mod r) with a and b about 127 bits each. Rather than windowing a and b independently, this work treats them as one Eisenstein integer z = a + b*omega in Z[omega] (omega^2 + omega + 1 = 0, realized on the curve by phi) and recodes z in radix B = 2^c directly over the Eisenstein integers. The joint Eisenstein view is shared with Zakura's key-agreement work, which develops it in full; there the recoding is a sparse width-3 NAF, here it is windowed for bucket MSMs. Z[omega] has six units {±1, ±omega, ±omega^2}. Every nonzero digit factors as d = u*delta with u a unit and delta a canonical orbit representative. Units are nearly free on the curve: powers of omega select one of the three x-coordinates x, zeta*x, zeta^2*x (with zeta^2*x = -x - zeta*x, all three available after one field multiplication) and the sign flips y. A radix-2^c Eisenstein window has (4^c + 2)/6 nonzero unit orbits and visits each scalar once per window instead of visiting two GLV components. After bucket accumulation, a window's weighted sum C = sum_delta [delta] Q_delta is integrated by a hexagonal reducer: a spanning tree over the wedge of canonical representatives whose edges differ by 1 or by 1 + omega = -omega^2, giving exactly 2m - 2 group additions for m buckets plus one endomorphism application. Bucket contents are reduced with the batch-affine machinery already used elsewhere in Zakura's curve code, where independent affine additions at one tree level share one field inversion; bucket reduction dominates, roughly three quarters of the zero-check time in phase measurements. The recoder stores window codes window-major (codes[window][base]) with per-window bucket histograms built during recoding, so staging a window is one contiguous placement pass and parallel window tasks do not stride through a shared matrix. This yields a general-purpose Eisenstein-orbit MSM backend, independent of any preparation. A planner chooses between it and the existing Signed-Booth GLV backend using a magnitude profile rather than the term count alone: prover MSMs are not uniformly random (boolean columns, byte-sized values, zero padding), and the joint Eisenstein representation uses more narrow windows than Booth, so a count-only model would overestimate its cost on full-width inputs and underestimate it on small ones. The planner decomposes the scalars first, records how many GLV components and joint scalars reach each bit position, and counts for each backend only the windows and assignments it would actually process. ## Prepared fixed bases and the codebook For fixed bases, a chosen set of Eisenstein multipliers eta is applied once, retaining the exact points [eta]P_i. A radix digit then factors as d = u*eta*delta (mod B): u is a free rotation/sign, eta selects a prepared point, delta selects a coefficient bucket. The online contribution is [delta]([u*eta]P_i); the extra multiplier changes only which prepared affine point is loaded. The default codebook uses B = 128 and the subgroup G = of the unit group of Z[omega]/128Z[omega], where alpha = 1 - omega (norm 3) and beta = 2 - omega (norm 7). That gives 256 prepared variants per fixed base, 32 coefficient buckets per window, and 19 main windows for the roughly 127-bit GLV components. Each prepared point stores (x, zeta*x, y), 96 bytes; at about 2,000 fixed bases the table occupies about 48 MiB. One prepared point stands in for an entire residue class under the CM action, which is why this beats a generic time-memory tradeoff. alpha and beta act as non-unit complex-multiplication endomorphisms of degrees 3 and 7 (their Eisenstein norms), not extra automorphisms. On a j = 0 curve y^2 = x^3 + b, with s = 1 - zeta, the degree-3 map is alpha(x, y) = ((x^3 + 4b)/(s^2 x^2), y(x^3 - 8b)/(s^3 x^3)). These maps are batch-evaluated with shared inversions only during the preparation-time relation scan (beta(P) = P + alpha(P) reuses the alpha images; there is no dedicated degree-7 formula); the hot loop never evaluates an isogeny per digit. The relation scan detects fixed bases related by u, u*alpha, or u*beta; when a relation is found, one base is removed from the live prepared set and its scalar is folded into the related base before recoding. The prepared tables are not built by repeated isogeny application: alpha-only codebooks seed two batched odd-multiple chains from P and alpha(P), and the default beta-subgroup codebook, like the other modes, evaluates its remaining exact multipliers with the existing shared GLV batch ladder. Correctness relies on exact lifts, not just residues: the recurrence z' = (z - d)/B must subtract the same exact Eisenstein integer whose point image is used, so the codebook stores an exact integer lift and carry for every residue. The codebook constructor independently derives and checks the prepared residue classes (including subgroup closure for subgroup modes), the unit cosets or exponent-box coordinates used as variants, the coefficient orbits or tiles, every exact lift, coverage of every nonzero residue, and every carry; these are not unchecked generated constants. The prepared digit set is not a canonical number system, so the recoder runs a fixed number L of main windows and leaves a bounded residual t (z = sum_(j