rhdl_ed25519_fast_core/
multicomb.rs

1//! Twenty-four-context, signed multi-comb Ed25519 fixed-base multiplication.
2//!
3//! The engine overlaps 24 independent scalar multiplications across four
4//! fully pipelined field multipliers, two fully pipelined field add/subtract
5//! lanes, and the four-cycle constant-address table in [`crate::multicomb_table`].
6//! It implements the 4-block, 8-tooth, spacing-8 comb used by the parallel
7//! signing datapath. No secret bit drives a RAM address or changes the formula
8//! sequence.
9
10use rhdl::prelude::*;
11use rhdl_fpga::core::dff::DFF;
12
13use crate::{
14    field_parallel::{
15        FieldAddSubIn, FieldAddSubOut, FieldAddSubPipe, FieldElement51, FieldMulIn, FieldMulOut,
16        FieldMulPipe,
17    },
18    multicomb_table::{MultiCombLookup, MultiCombLookupIn, NielsPoint},
19    scalar::ScalarWords,
20};
21
22const ST_FREE: u128 = 0;
23const ST_LOOKUP: u128 = 1;
24const ST_LOOKUP_WAIT: u128 = 2;
25const ST_ISSUE_A: u128 = 3;
26const ST_WAIT_A: u128 = 4;
27const ST_BUILD_PENDING: u128 = 5;
28const ST_BUILD_WAIT: u128 = 6;
29const ST_ISSUE_B: u128 = 7;
30const ST_WAIT_B: u128 = 8;
31const ST_POST_PENDING: u128 = 9;
32const ST_BUILD2_PENDING: u128 = 10;
33const ST_BUILD2_WAIT: u128 = 11;
34const ST_POST_WAIT: u128 = 12;
35const ST_TWICE_PENDING: u128 = 13;
36const ST_TWICE_WAIT: u128 = 14;
37
38const TASK_BUILD1: u128 = 0;
39const TASK_BUILD2: u128 = 1;
40const TASK_POST: u128 = 2;
41const TASK_TWICE: u128 = 3;
42
43/// Extended Edwards point in canonical radix-`2^51` field coordinates.
44#[derive(Copy, Clone, Debug, PartialEq, Digital)]
45pub struct ExtendedPoint {
46    /// Projective X coordinate.
47    pub x: FieldElement51,
48    /// Projective Y coordinate.
49    pub y: FieldElement51,
50    /// Projective Z coordinate.
51    pub z: FieldElement51,
52    /// Extended T coordinate, satisfying `XY = ZT`.
53    pub t: FieldElement51,
54}
55
56impl ExtendedPoint {
57    /// Edwards identity `(0, 1, 1, 0)`.
58    pub fn identity() -> Self {
59        Self {
60            x: FieldElement51::zero(),
61            y: FieldElement51::one(),
62            z: FieldElement51::one(),
63            t: FieldElement51::zero(),
64        }
65    }
66}
67
68/// Tagged scalar accepted by [`MultiCombMul`].
69#[derive(Copy, Clone, Debug, PartialEq, Digital)]
70pub struct MultiCombMulIn {
71    /// Marks [`Self::scalar`] and [`Self::tag`] valid.
72    pub valid: bool,
73    /// Canonical Ed25519 scalar, little-endian words.
74    pub scalar: ScalarWords,
75    /// Caller-defined transaction tag.
76    pub tag: b16,
77}
78
79/// Flow control and tagged point returned by [`MultiCombMul`].
80#[derive(Copy, Clone, Debug, PartialEq, Digital)]
81pub struct MultiCombMulOut {
82    /// High when one of the 24 contexts can accept a request.
83    pub ready: bool,
84    /// High for one cycle when [`Self::point`] and [`Self::tag`] are valid.
85    pub valid: bool,
86    /// Extended point `[scalar]B`.
87    pub point: ExtendedPoint,
88    /// Delayed caller tag.
89    pub tag: b16,
90    /// Number of occupied multiplication contexts.
91    pub occupancy: b5,
92    /// Sticky completion-buffer overflow (always false in a single engine).
93    pub error: bool,
94}
95
96#[derive(Copy, Clone, Debug, PartialEq, Digital)]
97#[doc(hidden)]
98pub struct ContextControl {
99    state: b4,
100    scalar: ScalarWords,
101    tag: b16,
102    round: b3,
103    block: b3,
104}
105
106#[derive(Copy, Clone, Debug, PartialEq, Digital)]
107#[doc(hidden)]
108pub struct FieldPair {
109    a: FieldElement51,
110    b: FieldElement51,
111}
112
113#[derive(Copy, Clone, Debug, PartialEq, Digital)]
114#[doc(hidden)]
115pub struct FieldTriple {
116    a: FieldElement51,
117    b: FieldElement51,
118    c: FieldElement51,
119}
120
121#[derive(Copy, Clone, Debug, PartialEq, Digital)]
122#[doc(hidden)]
123pub struct ContextBanks {
124    control: [ContextControl; 24],
125    point_xy: [FieldPair; 24],
126    point_zt: [FieldPair; 24],
127    point_sum_difference: [FieldPair; 24],
128    niels: [NielsPoint; 24],
129    temporary01: [FieldPair; 24],
130    temporary23: [FieldPair; 24],
131    completed01: [FieldPair; 24],
132    completed23: [FieldPair; 24],
133    build: [FieldTriple; 24],
134}
135
136fn zero_field() -> FieldElement51 {
137    FieldElement51::zero()
138}
139
140fn reset_context_banks() -> ContextBanks {
141    let zero = zero_field();
142    let pair = FieldPair { a: zero, b: zero };
143    let triple = FieldTriple {
144        a: zero,
145        b: zero,
146        c: zero,
147    };
148    ContextBanks {
149        control: [ContextControl {
150            state: b4(ST_FREE),
151            scalar: ScalarWords { words: [b64(0); 4] },
152            tag: b16(0),
153            round: b3(0),
154            block: b3(0),
155        }; 24],
156        point_xy: [pair; 24],
157        point_zt: [pair; 24],
158        point_sum_difference: [pair; 24],
159        niels: [NielsPoint::zero(); 24],
160        temporary01: [pair; 24],
161        temporary23: [pair; 24],
162        completed01: [pair; 24],
163        completed23: [pair; 24],
164        build: [triple; 24],
165    }
166}
167
168/// Split register bank used to avoid monolithic reset literals and preserve
169/// explicit context-level parallelism in generated RTL.
170#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
171#[doc(hidden)]
172pub struct ContextStore {
173    control: DFF<[ContextControl; 24]>,
174    point_xy: DFF<[FieldPair; 24]>,
175    point_zt: DFF<[FieldPair; 24]>,
176    point_sum_difference: DFF<[FieldPair; 24]>,
177    niels: DFF<[NielsPoint; 24]>,
178    temporary01: DFF<[FieldPair; 24]>,
179    temporary23: DFF<[FieldPair; 24]>,
180    completed01: DFF<[FieldPair; 24]>,
181    completed23: DFF<[FieldPair; 24]>,
182    build: DFF<[FieldTriple; 24]>,
183}
184
185impl Default for ContextStore {
186    fn default() -> Self {
187        let reset = reset_context_banks();
188        Self {
189            control: DFF::new(reset.control),
190            point_xy: DFF::new(reset.point_xy),
191            point_zt: DFF::new(reset.point_zt),
192            point_sum_difference: DFF::new(reset.point_sum_difference),
193            niels: DFF::new(reset.niels),
194            temporary01: DFF::new(reset.temporary01),
195            temporary23: DFF::new(reset.temporary23),
196            completed01: DFF::new(reset.completed01),
197            completed23: DFF::new(reset.completed23),
198            build: DFF::new(reset.build),
199        }
200    }
201}
202
203impl SynchronousIO for ContextStore {
204    type I = ContextBanks;
205    type O = ContextBanks;
206    type Kernel = context_store_kernel;
207}
208
209#[kernel]
210#[doc(hidden)]
211pub fn context_store_kernel(
212    _cr: ClockReset,
213    i: ContextBanks,
214    q: ContextStoreQ,
215) -> (ContextBanks, ContextStoreD) {
216    let output = ContextBanks {
217        control: q.control,
218        point_xy: q.point_xy,
219        point_zt: q.point_zt,
220        point_sum_difference: q.point_sum_difference,
221        niels: q.niels,
222        temporary01: q.temporary01,
223        temporary23: q.temporary23,
224        completed01: q.completed01,
225        completed23: q.completed23,
226        build: q.build,
227    };
228    let mut d = ContextStoreD::dont_care();
229    d.control = i.control;
230    d.point_xy = i.point_xy;
231    d.point_zt = i.point_zt;
232    d.point_sum_difference = i.point_sum_difference;
233    d.niels = i.niels;
234    d.temporary01 = i.temporary01;
235    d.temporary23 = i.temporary23;
236    d.completed01 = i.completed01;
237    d.completed23 = i.completed23;
238    d.build = i.build;
239    (output, d)
240}
241
242#[derive(Copy, Clone, Debug, PartialEq, Digital)]
243#[doc(hidden)]
244pub struct MultiCombMathIn {
245    mul: [FieldMulIn; 4],
246    addsub: [FieldAddSubIn; 2],
247}
248
249#[derive(Copy, Clone, Debug, PartialEq, Digital)]
250#[doc(hidden)]
251pub struct MultiCombMathOut {
252    mul: [FieldMulOut; 4],
253    addsub: [FieldAddSubOut; 2],
254}
255
256/// Four multiplication and two add/subtract pipelines shared by all contexts.
257#[derive(Clone, Debug, Synchronous, SynchronousDQ, Default)]
258#[doc(hidden)]
259pub struct MultiCombMath {
260    mul0: FieldMulPipe,
261    mul1: FieldMulPipe,
262    mul2: FieldMulPipe,
263    mul3: FieldMulPipe,
264    addsub0: FieldAddSubPipe,
265    addsub1: FieldAddSubPipe,
266}
267
268impl SynchronousIO for MultiCombMath {
269    type I = MultiCombMathIn;
270    type O = MultiCombMathOut;
271    type Kernel = multicomb_math_kernel;
272}
273
274#[kernel]
275#[doc(hidden)]
276pub fn multicomb_math_kernel(
277    _cr: ClockReset,
278    i: MultiCombMathIn,
279    q: MultiCombMathQ,
280) -> (MultiCombMathOut, MultiCombMathD) {
281    let output = MultiCombMathOut {
282        mul: [q.mul0, q.mul1, q.mul2, q.mul3],
283        addsub: [q.addsub0, q.addsub1],
284    };
285    let mut d = MultiCombMathD::dont_care();
286    d.mul0 = i.mul[0];
287    d.mul1 = i.mul[1];
288    d.mul2 = i.mul[2];
289    d.mul3 = i.mul[3];
290    d.addsub0 = i.addsub[0];
291    d.addsub1 = i.addsub[1];
292    (output, d)
293}
294
295#[derive(Copy, Clone, Debug, PartialEq, Digital)]
296#[doc(hidden)]
297pub struct MultiCombControl {
298    free_fifo: [b5; 24],
299    free_read: b5,
300    free_write: b5,
301    free_count: b5,
302    lookup_rr: b5,
303    multiply_rr: b5,
304    builder_rr: b5,
305    multiply_valid: [bool; 17],
306    multiply_context: [b5; 17],
307    multiply_second: [bool; 17],
308    task_valid: [bool; 4],
309    task_context: [b5; 4],
310    task_kind: [b2; 4],
311}
312
313fn reset_control() -> MultiCombControl {
314    MultiCombControl {
315        free_fifo: [
316            b5(0),
317            b5(1),
318            b5(2),
319            b5(3),
320            b5(4),
321            b5(5),
322            b5(6),
323            b5(7),
324            b5(8),
325            b5(9),
326            b5(10),
327            b5(11),
328            b5(12),
329            b5(13),
330            b5(14),
331            b5(15),
332            b5(16),
333            b5(17),
334            b5(18),
335            b5(19),
336            b5(20),
337            b5(21),
338            b5(22),
339            b5(23),
340        ],
341        free_read: b5(0),
342        free_write: b5(0),
343        free_count: b5(24),
344        lookup_rr: b5(0),
345        multiply_rr: b5(0),
346        builder_rr: b5(0),
347        multiply_valid: [false; 17],
348        multiply_context: [b5(0); 17],
349        multiply_second: [false; 17],
350        task_valid: [false; 4],
351        task_context: [b5(0); 4],
352        task_kind: [b2(0); 4],
353    }
354}
355
356/// High-throughput fixed-base multiplication black box.
357#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
358#[rhdl(dq_no_prefix)]
359pub struct MultiCombMul {
360    control: DFF<MultiCombControl>,
361    contexts: ContextStore,
362    lookup: MultiCombLookup,
363    math: MultiCombMath,
364}
365
366impl Default for MultiCombMul {
367    fn default() -> Self {
368        Self {
369            control: DFF::new(reset_control()),
370            contexts: ContextStore::default(),
371            lookup: MultiCombLookup::default(),
372            math: MultiCombMath::default(),
373        }
374    }
375}
376
377impl SynchronousIO for MultiCombMul {
378    type I = MultiCombMulIn;
379    type O = MultiCombMulOut;
380    type Kernel = multicomb_mul_kernel;
381}
382
383#[kernel]
384fn signed_scalar(input: ScalarWords) -> ScalarWords {
385    let odd = (input.words[0] & b64(1)) != b64(0);
386    let l = [
387        b64(0x5812631a5cf5d3ed),
388        b64(0x14def9dea2f79cd6),
389        b64(0),
390        b64(0x1000000000000000),
391    ];
392    let mut adjusted = input.words;
393    if !odd {
394        let s0 = input.words[0].resize::<65>() + l[0].resize::<65>();
395        let s1 = input.words[1].resize::<65>() + l[1].resize::<65>() + (s0 >> 64);
396        let s2 = input.words[2].resize::<65>() + l[2].resize::<65>() + (s1 >> 64);
397        let s3 = input.words[3].resize::<65>() + l[3].resize::<65>() + (s2 >> 64);
398        adjusted = [
399            s0.resize::<64>(),
400            s1.resize::<64>(),
401            s2.resize::<64>(),
402            s3.resize::<64>(),
403        ];
404    }
405    ScalarWords {
406        words: [
407            (adjusted[0] >> 1) | (adjusted[1] << 63),
408            (adjusted[1] >> 1) | (adjusted[2] << 63),
409            (adjusted[2] >> 1) | (adjusted[3] << 63),
410            (adjusted[3] >> 1) | b64(0x8000000000000000),
411        ],
412    }
413}
414
415#[kernel]
416fn comb_digit(scalar: ScalarWords, block: b2, round: b3) -> (b7, bool) {
417    let word = if block == b2(0) {
418        scalar.words[0]
419    } else if block == b2(1) {
420        scalar.words[1]
421    } else if block == b2(2) {
422        scalar.words[2]
423    } else {
424        scalar.words[3]
425    };
426    let mut digit = b8(0);
427    for tooth in 0..8 {
428        let bit = b7((tooth * 8 + 7) as u128) - round.resize::<7>();
429        let value = (word >> bit).resize::<1>();
430        digit = digit | (value.resize::<8>() << tooth);
431    }
432    let sign = (digit & b8(0x80)) != b8(0);
433    let candidate = digit.resize::<7>() ^ if sign { b7(0x7f) } else { b7(0) };
434    (candidate, sign)
435}
436
437#[kernel]
438fn next_rr(value: b5) -> b5 {
439    if value == b5(23) {
440        b5(0)
441    } else {
442        value + b5(1)
443    }
444}
445
446#[kernel]
447fn scan_index(start: b5, offset: b5) -> b5 {
448    let sum = start.resize::<6>() + offset.resize::<6>();
449    if sum >= b6(24) {
450        (sum - b6(24)).resize::<5>()
451    } else {
452        sum.resize::<5>()
453    }
454}
455
456/// State transition for [`MultiCombMul`].
457#[kernel]
458pub fn multicomb_mul_kernel(_cr: ClockReset, i: MultiCombMulIn, q: Q) -> (MultiCombMulOut, D) {
459    let r = q.control;
460    let current = q.contexts;
461    let mut contexts = current;
462    let mut n = r;
463    let zero = FieldElement51 { limbs: [b51(0); 5] };
464    let one = FieldElement51 {
465        limbs: [b51(1), b51(0), b51(0), b51(0), b51(0)],
466    };
467    let identity = ExtendedPoint {
468        x: zero,
469        y: one,
470        z: one,
471        t: zero,
472    };
473    let mut output = MultiCombMulOut {
474        error: false,
475        ready: r.free_count != b5(0),
476        valid: false,
477        point: identity,
478        tag: b16(0),
479        occupancy: b5(24) - r.free_count,
480    };
481
482    let mut lookup_found = false;
483    let mut lookup_context = b5(0);
484    if q.lookup.ready {
485        for offset in 0..2 {
486            let candidate = scan_index(r.lookup_rr, b5(offset as u128));
487            if !lookup_found && current.control[candidate].state == b4(ST_LOOKUP) {
488                lookup_found = true;
489                lookup_context = candidate;
490            }
491        }
492    }
493    let lookup_control = current.control[lookup_context];
494    let (lookup_candidate, lookup_sign) = comb_digit(
495        lookup_control.scalar,
496        lookup_control.block.resize::<2>(),
497        lookup_control.round,
498    );
499    let lookup_input = MultiCombLookupIn {
500        valid: lookup_found,
501        block: lookup_control.block.resize::<2>(),
502        candidate: lookup_candidate,
503        sign: lookup_sign,
504        tag: lookup_context.resize::<16>(),
505    };
506    if q.lookup.ready {
507        n.lookup_rr = scan_index(r.lookup_rr, b5(2));
508    }
509    if lookup_found {
510        contexts.control[lookup_context].state = b4(ST_LOOKUP_WAIT);
511    }
512    if q.lookup.valid {
513        let context = q.lookup.tag.resize::<5>();
514        contexts.niels[context] = q.lookup.point;
515        contexts.control[context].state = b4(ST_ISSUE_A);
516    }
517
518    let mul_idle = FieldMulIn {
519        valid: false,
520        a: zero,
521        b: zero,
522    };
523    let mut mul_inputs = [mul_idle; 4];
524    let mut multiply_found = false;
525    let mut multiply_context = b5(0);
526    let mut multiply_second = false;
527    for offset in 0..2 {
528        let candidate = scan_index(r.multiply_rr, b5(offset as u128));
529        let state = current.control[candidate].state;
530        if !multiply_found && (state == b4(ST_ISSUE_A) || state == b4(ST_ISSUE_B)) {
531            multiply_found = true;
532            multiply_context = candidate;
533            multiply_second = state == b4(ST_ISSUE_B);
534        }
535    }
536    if multiply_found {
537        let context = multiply_context;
538        if multiply_second {
539            mul_inputs[0] = FieldMulIn {
540                valid: true,
541                a: current.completed01[context].a,
542                b: current.completed23[context].b,
543            };
544            mul_inputs[1] = FieldMulIn {
545                valid: true,
546                a: current.completed01[context].b,
547                b: current.completed23[context].a,
548            };
549            mul_inputs[2] = FieldMulIn {
550                valid: true,
551                a: current.completed23[context].a,
552                b: current.completed23[context].b,
553            };
554            mul_inputs[3] = FieldMulIn {
555                valid: true,
556                a: current.completed01[context].a,
557                b: current.completed01[context].b,
558            };
559            contexts.control[context].state = b4(ST_WAIT_B);
560        } else if current.control[context].block == b3(4) {
561            mul_inputs[0] = FieldMulIn {
562                valid: true,
563                a: current.point_xy[context].a,
564                b: current.point_xy[context].a,
565            };
566            mul_inputs[1] = FieldMulIn {
567                valid: true,
568                a: current.point_xy[context].b,
569                b: current.point_xy[context].b,
570            };
571            mul_inputs[2] = FieldMulIn {
572                valid: true,
573                a: current.point_zt[context].a,
574                b: current.point_zt[context].a,
575            };
576            mul_inputs[3] = FieldMulIn {
577                valid: true,
578                a: current.point_sum_difference[context].a,
579                b: current.point_sum_difference[context].a,
580            };
581            contexts.control[context].state = b4(ST_WAIT_A);
582        } else {
583            mul_inputs[0] = FieldMulIn {
584                valid: true,
585                a: current.point_sum_difference[context].a,
586                b: current.niels[context].y_plus_x,
587            };
588            mul_inputs[1] = FieldMulIn {
589                valid: true,
590                a: current.point_sum_difference[context].b,
591                b: current.niels[context].y_minus_x,
592            };
593            mul_inputs[2] = FieldMulIn {
594                valid: true,
595                a: current.point_zt[context].b,
596                b: current.niels[context].xy2d,
597            };
598            mul_inputs[3] = FieldMulIn {
599                valid: true,
600                a: current.point_zt[context].a,
601                b: FieldElement51 {
602                    limbs: [b51(2), b51(0), b51(0), b51(0), b51(0)],
603                },
604            };
605            contexts.control[context].state = b4(ST_WAIT_A);
606        }
607    }
608    n.multiply_valid[0] = multiply_found;
609    n.multiply_context[0] = multiply_context;
610    n.multiply_second[0] = multiply_second;
611    for stage in 1..17 {
612        n.multiply_valid[stage] = r.multiply_valid[stage - 1];
613        n.multiply_context[stage] = r.multiply_context[stage - 1];
614        n.multiply_second[stage] = r.multiply_second[stage - 1];
615    }
616    n.multiply_rr = scan_index(r.multiply_rr, b5(2));
617
618    if r.multiply_valid[16]
619        && q.math.mul[0].valid
620        && q.math.mul[1].valid
621        && q.math.mul[2].valid
622        && q.math.mul[3].valid
623    {
624        let context = r.multiply_context[16];
625        if r.multiply_second[16] {
626            contexts.point_xy[context] = FieldPair {
627                a: q.math.mul[0].result,
628                b: q.math.mul[1].result,
629            };
630            contexts.point_zt[context] = FieldPair {
631                a: q.math.mul[2].result,
632                b: q.math.mul[3].result,
633            };
634            contexts.control[context].state = b4(ST_POST_PENDING);
635        } else {
636            contexts.temporary01[context] = FieldPair {
637                a: q.math.mul[0].result,
638                b: q.math.mul[1].result,
639            };
640            contexts.temporary23[context] = FieldPair {
641                a: q.math.mul[2].result,
642                b: q.math.mul[3].result,
643            };
644            contexts.control[context].state = b4(ST_BUILD_PENDING);
645        }
646    }
647
648    let add_idle = FieldAddSubIn {
649        valid: false,
650        subtract: false,
651        a: zero,
652        b: zero,
653    };
654    let mut add_inputs = [add_idle; 2];
655    let mut builder_found = false;
656    let mut builder_context = b5(0);
657    let mut builder_task = b2(TASK_BUILD1);
658    for offset in 0..24 {
659        let candidate = scan_index(r.builder_rr, b5(offset as u128));
660        let state = current.control[candidate].state;
661        let pending = state == b4(ST_BUILD_PENDING)
662            || state == b4(ST_TWICE_PENDING)
663            || state == b4(ST_BUILD2_PENDING)
664            || state == b4(ST_POST_PENDING);
665        if !builder_found && pending {
666            builder_found = true;
667            builder_context = candidate;
668            builder_task = if state == b4(ST_TWICE_PENDING) {
669                b2(TASK_TWICE)
670            } else if state == b4(ST_BUILD2_PENDING) {
671                b2(TASK_BUILD2)
672            } else if state == b4(ST_POST_PENDING) {
673                b2(TASK_POST)
674            } else {
675                b2(TASK_BUILD1)
676            };
677        }
678    }
679    if builder_found {
680        let context = builder_context;
681        if builder_task == b2(TASK_POST) {
682            add_inputs[0] = FieldAddSubIn {
683                valid: true,
684                subtract: false,
685                a: current.point_xy[context].b,
686                b: current.point_xy[context].a,
687            };
688            add_inputs[1] = FieldAddSubIn {
689                valid: true,
690                subtract: true,
691                a: current.point_xy[context].b,
692                b: current.point_xy[context].a,
693            };
694            contexts.control[context].state = b4(ST_POST_WAIT);
695        } else if builder_task == b2(TASK_BUILD2) {
696            if current.control[context].block == b3(4) {
697                add_inputs[0] = FieldAddSubIn {
698                    valid: true,
699                    subtract: true,
700                    a: current.temporary23[context].b,
701                    b: current.build[context].a,
702                };
703                add_inputs[1] = FieldAddSubIn {
704                    valid: true,
705                    subtract: true,
706                    a: current.build[context].c,
707                    b: current.build[context].b,
708                };
709            } else {
710                add_inputs[0] = FieldAddSubIn {
711                    valid: true,
712                    subtract: false,
713                    a: current.build[context].c,
714                    b: current.temporary23[context].a,
715                };
716                add_inputs[1] = FieldAddSubIn {
717                    valid: true,
718                    subtract: true,
719                    a: current.build[context].c,
720                    b: current.temporary23[context].a,
721                };
722            }
723            contexts.control[context].state = b4(ST_BUILD2_WAIT);
724        } else if builder_task == b2(TASK_TWICE) {
725            add_inputs[0] = FieldAddSubIn {
726                valid: true,
727                subtract: false,
728                a: current.temporary23[context].a,
729                b: current.temporary23[context].a,
730            };
731            add_inputs[1] = add_inputs[0];
732            contexts.control[context].state = b4(ST_TWICE_WAIT);
733        } else {
734            let doubling = current.control[context].block == b3(4);
735            add_inputs[0] = FieldAddSubIn {
736                valid: true,
737                subtract: false,
738                a: if doubling {
739                    current.temporary01[context].b
740                } else {
741                    current.temporary01[context].a
742                },
743                b: if doubling {
744                    current.temporary01[context].a
745                } else {
746                    current.temporary01[context].b
747                },
748            };
749            add_inputs[1] = FieldAddSubIn {
750                valid: true,
751                subtract: true,
752                a: add_inputs[0].a,
753                b: add_inputs[0].b,
754            };
755            contexts.control[context].state = b4(ST_BUILD_WAIT);
756        }
757        n.builder_rr = next_rr(context);
758    } else {
759        n.builder_rr = next_rr(r.builder_rr);
760    }
761    n.task_valid[0] = builder_found;
762    n.task_context[0] = builder_context;
763    n.task_kind[0] = builder_task;
764    for stage in 1..4 {
765        n.task_valid[stage] = r.task_valid[stage - 1];
766        n.task_context[stage] = r.task_context[stage - 1];
767        n.task_kind[stage] = r.task_kind[stage - 1];
768    }
769
770    let mut release = false;
771    let mut release_context = b5(0);
772    if r.task_valid[3] && q.math.addsub[0].valid && q.math.addsub[1].valid {
773        let context = r.task_context[3];
774        let task = r.task_kind[3];
775        if task == b2(TASK_BUILD1) {
776            contexts.build[context].a = q.math.addsub[0].result;
777            contexts.build[context].b = q.math.addsub[1].result;
778            if current.control[context].block == b3(4) {
779                contexts.control[context].state = b4(ST_TWICE_PENDING);
780            } else {
781                contexts.build[context].c = current.temporary23[context].b;
782                contexts.control[context].state = b4(ST_BUILD2_PENDING);
783            }
784        } else if task == b2(TASK_TWICE) {
785            contexts.build[context].c = q.math.addsub[0].result;
786            contexts.control[context].state = b4(ST_BUILD2_PENDING);
787        } else if task == b2(TASK_BUILD2) {
788            if current.control[context].block == b3(4) {
789                contexts.completed01[context] = FieldPair {
790                    a: q.math.addsub[0].result,
791                    b: current.build[context].a,
792                };
793                contexts.completed23[context] = FieldPair {
794                    a: current.build[context].b,
795                    b: q.math.addsub[1].result,
796                };
797            } else {
798                contexts.completed01[context] = FieldPair {
799                    a: current.build[context].b,
800                    b: current.build[context].a,
801                };
802                contexts.completed23[context] = FieldPair {
803                    a: q.math.addsub[0].result,
804                    b: q.math.addsub[1].result,
805                };
806            }
807            contexts.control[context].state = b4(ST_ISSUE_B);
808        } else {
809            contexts.point_sum_difference[context] = FieldPair {
810                a: q.math.addsub[0].result,
811                b: q.math.addsub[1].result,
812            };
813            if current.control[context].block == b3(4) {
814                contexts.control[context].round = current.control[context].round + b3(1);
815                contexts.control[context].block = b3(0);
816                contexts.control[context].state = b4(ST_LOOKUP);
817            } else if current.control[context].block < b3(3) {
818                contexts.control[context].block = current.control[context].block + b3(1);
819                contexts.control[context].state = b4(ST_LOOKUP);
820            } else if current.control[context].round < b3(7) {
821                contexts.control[context].block = b3(4);
822                contexts.control[context].state = b4(ST_ISSUE_A);
823            } else {
824                output.valid = true;
825                output.tag = current.control[context].tag;
826                output.point = ExtendedPoint {
827                    x: current.point_xy[context].a,
828                    y: current.point_xy[context].b,
829                    z: current.point_zt[context].a,
830                    t: current.point_zt[context].b,
831                };
832                contexts.control[context].state = b4(ST_FREE);
833                release = true;
834                release_context = context;
835            }
836        }
837    }
838
839    let accept = i.valid && r.free_count != b5(0);
840    if accept {
841        let context = r.free_fifo[r.free_read];
842        contexts.control[context] = ContextControl {
843            state: b4(ST_LOOKUP),
844            scalar: signed_scalar(i.scalar),
845            tag: i.tag,
846            round: b3(0),
847            block: b3(0),
848        };
849        contexts.point_xy[context] = FieldPair { a: zero, b: one };
850        contexts.point_zt[context] = FieldPair { a: one, b: zero };
851        contexts.point_sum_difference[context] = FieldPair { a: one, b: one };
852        n.free_read = next_rr(r.free_read);
853    }
854    if release {
855        n.free_fifo[r.free_write] = release_context;
856        n.free_write = next_rr(r.free_write);
857    }
858    if accept && !release {
859        n.free_count = r.free_count - b5(1);
860    } else if release && !accept {
861        n.free_count = r.free_count + b5(1);
862    }
863
864    let mut d = D::dont_care();
865    d.control = n;
866    d.contexts = contexts;
867    d.lookup = lookup_input;
868    d.math = MultiCombMathIn {
869        mul: mul_inputs,
870        addsub: add_inputs,
871    };
872    (output, d)
873}
874
875#[cfg(test)]
876mod tests {
877    use super::*;
878    use curve25519_dalek::{constants::ED25519_BASEPOINT_POINT, scalar::Scalar};
879    use num_bigint::BigUint;
880    use std::iter;
881
882    fn scalar_words(bytes: [u8; 32]) -> ScalarWords {
883        let mut words = [b64(0); 4];
884        for (index, word) in words.iter_mut().enumerate() {
885            *word = b64(
886                u64::from_le_bytes(bytes[index * 8..index * 8 + 8].try_into().unwrap()) as u128,
887            );
888        }
889        ScalarWords { words }
890    }
891
892    fn field_big(value: FieldElement51) -> BigUint {
893        value
894            .limbs
895            .iter()
896            .enumerate()
897            .fold(BigUint::from(0u8), |sum, (index, limb)| {
898                sum + (BigUint::from(limb.raw()) << (51 * index))
899            })
900    }
901
902    fn compress(point: ExtendedPoint) -> [u8; 32] {
903        let p = (BigUint::from(1u8) << 255) - BigUint::from(19u8);
904        let z = field_big(point.z);
905        let inverse = z.modpow(&(&p - BigUint::from(2u8)), &p);
906        let x = (field_big(point.x) * &inverse) % &p;
907        let y = (field_big(point.y) * inverse) % &p;
908        let mut bytes = y.to_bytes_le();
909        bytes.resize(32, 0);
910        bytes[31] |= ((&x & BigUint::from(1u8))
911            .to_u64_digits()
912            .first()
913            .copied()
914            .unwrap_or(0) as u8)
915            << 7;
916        bytes.try_into().unwrap()
917    }
918
919    fn idle() -> MultiCombMulIn {
920        MultiCombMulIn {
921            valid: false,
922            scalar: ScalarWords { words: [b64(0); 4] },
923            tag: b16(0),
924        }
925    }
926
927    #[test]
928    fn sustained_service_interval_meets_signing_budget() {
929        std::thread::Builder::new()
930            .name("multicomb-throughput-sim".into())
931            .stack_size(256 * 1024 * 1024)
932            .spawn(sustained_service_interval_body)
933            .unwrap()
934            .join()
935            .unwrap();
936    }
937
938    fn sustained_service_interval_body() {
939        let scalar = scalar_words(Scalar::ONE.to_bytes());
940        let input = MultiCombMulIn {
941            valid: true,
942            scalar,
943            tag: b16(1),
944        };
945        let completion_cycles: Vec<_> = MultiCombMul::default()
946            .run(
947                iter::once(idle())
948                    .chain(iter::repeat_n(input, 10_000))
949                    .with_reset(1)
950                    .clock_pos_edge(100),
951            )
952            .synchronous_sample()
953            .enumerate()
954            .filter_map(|(cycle, sample)| sample.output.valid.then_some(cycle))
955            .collect();
956        assert!(
957            completion_cycles.len() >= 24,
958            "only {} completions",
959            completion_cycles.len()
960        );
961        let steady = &completion_cycles[8..];
962        let span = steady.last().unwrap() - steady.first().unwrap();
963        let interval = span as f64 / (steady.len() - 1) as f64;
964        println!(
965            "multi-comb sustained: completions={} first={} last={} interval={interval:.3}",
966            completion_cycles.len(),
967            steady.first().unwrap(),
968            steady.last().unwrap(),
969        );
970        assert!(
971            interval <= 202.0,
972            "{interval:.3}-cycle interval misses signing budget"
973        );
974    }
975
976    #[test]
977    fn compiles_to_native_rhdl_netlist() -> miette::Result<()> {
978        unsafe { std::env::set_var("RHDL_SKIP_IVERILOG_CHECK", "1") };
979        MultiCombMul::default()
980            .descriptor(ScopedName::top())?
981            .hdl()?;
982        Ok(())
983    }
984
985    #[test]
986    fn eight_context_engine_matches_dalek() {
987        std::thread::Builder::new()
988            .name("multicomb-sim".into())
989            .stack_size(256 * 1024 * 1024)
990            .spawn(eight_context_engine_matches_dalek_body)
991            .unwrap()
992            .join()
993            .unwrap();
994    }
995
996    fn eight_context_engine_matches_dalek_body() {
997        let scalars: Vec<_> = (0u64..8)
998            .map(|index| Scalar::from(index * 0x9e37_79b9 + index * index + 1))
999            .collect();
1000        let inputs = scalars
1001            .iter()
1002            .enumerate()
1003            .map(|(index, scalar)| MultiCombMulIn {
1004                valid: true,
1005                scalar: scalar_words(scalar.to_bytes()),
1006                tag: b16(index as u128),
1007            });
1008        let outputs: Vec<_> = MultiCombMul::default()
1009            .run(
1010                iter::once(idle())
1011                    .chain(inputs)
1012                    .chain(iter::repeat_n(idle(), 5_000))
1013                    .with_reset(1)
1014                    .clock_pos_edge(100),
1015            )
1016            .synchronous_sample()
1017            .enumerate()
1018            .filter_map(|(cycle, sample)| sample.output.valid.then_some((cycle, sample.output)))
1019            .take(scalars.len())
1020            .collect();
1021        assert_eq!(outputs.len(), scalars.len());
1022        let completion_span = outputs.last().unwrap().0 - outputs.first().unwrap().0;
1023        println!(
1024            "multi-comb completions: first={} last={} span={} average_spacing={:.2}",
1025            outputs.first().unwrap().0,
1026            outputs.last().unwrap().0,
1027            completion_span,
1028            completion_span as f64 / (outputs.len() - 1) as f64,
1029        );
1030        assert!(
1031            completion_span <= 8 * 205,
1032            "completion span {completion_span} exceeds the 205-cycle service target"
1033        );
1034        for (_, output) in outputs {
1035            let index = output.tag.raw() as usize;
1036            assert_eq!(
1037                compress(output.point),
1038                (scalars[index] * ED25519_BASEPOINT_POINT)
1039                    .compress()
1040                    .to_bytes(),
1041                "scalar index {index}",
1042            );
1043        }
1044    }
1045}
rhdl_ed25519_fast_core/multicomb.rs

rhdl_ed25519_fast_core/
multicomb.rs
