rhdl_ed25519_fast_core/

equation.rs

//! Projective Ed25519 verification equation.
//!
//! This stage adds affine `R` to projective `[k]A`, then compares the result
//! with projective `[S]B` using cross-products.  No inversion or compression is
//! required.  Twenty contexts share four field multipliers and each request
//! occupies exactly three multiplier issue cycles.

use rhdl::prelude::*;
use rhdl_fpga::core::dff::DFF;

use crate::{
    field_parallel::{
        FieldElement51, FieldMulIn, FieldMulPipe, field_add_kernel, field_eq_kernel,
        field_sub_kernel,
    },
    multicomb::ExtendedPoint,
};

const CONTEXTS: usize = 20;
const FREE: u128 = 0;
const READY: u128 = 1;
const WAIT: u128 = 2;

#[derive(Copy, Clone, Debug, Default, PartialEq, Digital)]
#[doc(hidden)]
pub enum EquationPhase {
    #[default]
    AddFirst,
    AddSecond,
    Compare,
}

/// One strict projective-equation request.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct EquationIn {
    /// Marks this request valid when [`EquationOut::ready`] is high.
    pub valid: bool,
    /// Variable-base product `[k]A`.
    pub variable: ExtendedPoint,
    /// Decoded affine signature point `R`.
    pub r: ExtendedPoint,
    /// Precomputed affine `2*d*T_R`.
    pub r_t2d: FieldElement51,
    /// Fixed-base product `[S]B`.
    pub fixed: ExtendedPoint,
    /// Caller-defined transaction tag.
    pub tag: b16,
}

/// Flow control and equality result from [`EquationPipe`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct EquationOut {
    /// High when an equation context can be accepted.
    pub ready: bool,
    /// High for one cycle when [`Self::equal`] is valid.
    pub valid: bool,
    /// Projective equality decision.
    pub equal: bool,
    /// Delayed caller tag.
    pub tag: b16,
    /// Number of occupied contexts.
    pub occupancy: b5,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct EquationContext {
    state: b2,
    phase: EquationPhase,
    tag: b16,
    variable: ExtendedPoint,
    r: ExtendedPoint,
    r_t2d: FieldElement51,
    fixed: ExtendedPoint,
    e: FieldElement51,
    f: FieldElement51,
    g: FieldElement51,
    h: FieldElement51,
    sum: ExtendedPoint,
}

fn empty_context() -> EquationContext {
    EquationContext {
        state: b2(FREE),
        phase: EquationPhase::AddFirst,
        tag: b16(0),
        variable: ExtendedPoint::identity(),
        r: ExtendedPoint::identity(),
        r_t2d: FieldElement51::zero(),
        fixed: ExtendedPoint::identity(),
        e: FieldElement51::zero(),
        f: FieldElement51::zero(),
        g: FieldElement51::zero(),
        h: FieldElement51::zero(),
        sum: ExtendedPoint::identity(),
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct EquationControl {
    contexts: [EquationContext; CONTEXTS],
    issue_valid: [bool; 17],
    issue_context: [b5; 17],
    round_robin: b5,
}

fn reset_control() -> EquationControl {
    EquationControl {
        contexts: [empty_context(); CONTEXTS],
        issue_valid: [false; 17],
        issue_context: [b5(0); 17],
        round_robin: b5(0),
    }
}

/// Twenty-context strict projective equation pipeline.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct EquationPipe {
    control: DFF<EquationControl>,
    mul0: FieldMulPipe,
    mul1: FieldMulPipe,
    mul2: FieldMulPipe,
    mul3: FieldMulPipe,
}

impl Default for EquationPipe {
    fn default() -> Self {
        Self {
            control: DFF::new(reset_control()),
            mul0: FieldMulPipe::default(),
            mul1: FieldMulPipe::default(),
            mul2: FieldMulPipe::default(),
            mul3: FieldMulPipe::default(),
        }
    }
}

impl SynchronousIO for EquationPipe {
    type I = EquationIn;
    type O = EquationOut;
    type Kernel = equation_kernel;
}

#[kernel]
fn zero() -> FieldElement51 {
    FieldElement51 { limbs: [b51(0); 5] }
}

#[kernel]
fn one() -> FieldElement51 {
    FieldElement51 {
        limbs: [b51(1), b51(0), b51(0), b51(0), b51(0)],
    }
}

#[kernel]
fn identity() -> ExtendedPoint {
    ExtendedPoint {
        x: zero(),
        y: one(),
        z: one(),
        t: zero(),
    }
}

#[kernel]
fn empty_context_kernel(_unused: bool) -> EquationContext {
    EquationContext {
        state: b2(FREE),
        phase: EquationPhase::AddFirst,
        tag: b16(0),
        variable: identity(),
        r: identity(),
        r_t2d: zero(),
        fixed: identity(),
        e: zero(),
        f: zero(),
        g: zero(),
        h: zero(),
        sum: identity(),
    }
}

#[kernel]
fn wrap20(value: b5) -> b5 {
    if value >= b5(20) {
        value - b5(20)
    } else {
        value
    }
}

/// State transition for [`EquationPipe`].
#[kernel]
pub fn equation_kernel(
    _cr: ClockReset,
    i: EquationIn,
    q: EquationPipeQ,
) -> (EquationOut, EquationPipeD) {
    let r = q.control;
    let mut n = r;
    let zero = zero();
    let mut output = EquationOut {
        ready: false,
        valid: false,
        equal: false,
        tag: b16(0),
        occupancy: b5(0),
    };

    let mut free_found = false;
    let mut free_context = b5(0);
    for index in 0..CONTEXTS {
        if r.contexts[index].state != b2(FREE) {
            output.occupancy += b5(1);
        } else if !free_found {
            free_found = true;
            free_context = b5(index as u128);
        }
    }
    output.ready = free_found;

    let mut issue_found = false;
    let mut issue_context = b5(0);
    for offset in 0..CONTEXTS {
        let candidate = wrap20(r.round_robin + b5(offset as u128));
        if !issue_found && r.contexts[candidate].state == b2(READY) {
            issue_found = true;
            issue_context = candidate;
        }
    }
    let context = r.contexts[issue_context];
    let mut a = [zero; 4];
    let mut b = [zero; 4];
    if issue_found {
        match context.phase {
            EquationPhase::AddFirst => {
                a[0] = field_sub_kernel(context.variable.y, context.variable.x);
                b[0] = field_sub_kernel(context.r.y, context.r.x);
                a[1] = field_add_kernel(context.variable.y, context.variable.x);
                b[1] = field_add_kernel(context.r.y, context.r.x);
                a[2] = context.variable.t;
                b[2] = context.r_t2d;
            }
            EquationPhase::AddSecond => {
                a = [context.e, context.g, context.e, context.f];
                b = [context.f, context.h, context.h, context.g];
            }
            EquationPhase::Compare => {
                a = [
                    context.sum.x,
                    context.fixed.x,
                    context.sum.y,
                    context.fixed.y,
                ];
                b = [
                    context.fixed.z,
                    context.sum.z,
                    context.fixed.z,
                    context.sum.z,
                ];
            }
        }
        n.contexts[issue_context].state = b2(WAIT);
        n.round_robin = wrap20(issue_context + b5(1));
    }

    n.issue_valid[0] = issue_found;
    n.issue_context[0] = issue_context;
    for stage in 1..17 {
        n.issue_valid[stage] = r.issue_valid[stage - 1];
        n.issue_context[stage] = r.issue_context[stage - 1];
    }

    if r.issue_valid[16] && q.mul0.valid && q.mul1.valid && q.mul2.valid && q.mul3.valid {
        let result_context = r.issue_context[16];
        let current = r.contexts[result_context];
        let mut updated = current;
        updated.state = b2(READY);
        match current.phase {
            EquationPhase::AddFirst => {
                let d = field_add_kernel(current.variable.z, current.variable.z);
                updated.e = field_sub_kernel(q.mul1.result, q.mul0.result);
                updated.f = field_sub_kernel(d, q.mul2.result);
                updated.g = field_add_kernel(d, q.mul2.result);
                updated.h = field_add_kernel(q.mul1.result, q.mul0.result);
                updated.phase = EquationPhase::AddSecond;
            }
            EquationPhase::AddSecond => {
                updated.sum = ExtendedPoint {
                    x: q.mul0.result,
                    y: q.mul1.result,
                    z: q.mul3.result,
                    t: q.mul2.result,
                };
                updated.phase = EquationPhase::Compare;
            }
            EquationPhase::Compare => {
                output.valid = true;
                output.equal = field_eq_kernel(q.mul0.result, q.mul1.result)
                    && field_eq_kernel(q.mul2.result, q.mul3.result);
                output.tag = current.tag;
                updated = empty_context_kernel(false);
            }
        }
        n.contexts[result_context] = updated;
    }

    if i.valid && free_found {
        n.contexts[free_context] = EquationContext {
            state: b2(READY),
            phase: EquationPhase::AddFirst,
            tag: i.tag,
            variable: i.variable,
            r: i.r,
            r_t2d: i.r_t2d,
            fixed: i.fixed,
            e: zero,
            f: zero,
            g: zero,
            h: zero,
            sum: identity(),
        };
    }

    let mut d = EquationPipeD::dont_care();
    d.control = n;
    d.mul0 = FieldMulIn {
        valid: issue_found,
        a: a[0],
        b: b[0],
    };
    d.mul1 = FieldMulIn {
        valid: issue_found,
        a: a[1],
        b: b[1],
    };
    d.mul2 = FieldMulIn {
        valid: issue_found,
        a: a[2],
        b: b[2],
    };
    d.mul3 = FieldMulIn {
        valid: issue_found,
        a: a[3],
        b: b[3],
    };
    (output, d)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::field_parallel::field_from_words_kernel;
    use std::iter;

    fn field(words: [u64; 4]) -> FieldElement51 {
        field_from_words_kernel(words.map(|word| b64(word as u128)))
    }

    fn basepoint() -> (ExtendedPoint, FieldElement51) {
        (
            ExtendedPoint {
                x: field([
                    0xc9562d608f25d51a,
                    0x692cc7609525a7b2,
                    0xc0a4e231fdd6dc5c,
                    0x216936d3cd6e53fe,
                ]),
                y: field([
                    0x6666666666666658,
                    0x6666666666666666,
                    0x6666666666666666,
                    0x6666666666666666,
                ]),
                z: FieldElement51::one(),
                t: field([
                    0x6dde8ab3a5b7dda3,
                    0x20f09f80775152f5,
                    0x66ea4e8e64abe37d,
                    0x67875f0fd78b7665,
                ]),
            },
            field([
                0xabc91205877aaa68,
                0x26d9e823ccaac49e,
                0x5a1b7dcbdd43598c,
                0x6f117b689f0c65a8,
            ]),
        )
    }

    #[test]
    fn identity_plus_basepoint_compares_equal_to_basepoint() {
        let (base, t2d) = basepoint();
        let request = EquationIn {
            valid: true,
            variable: ExtendedPoint::identity(),
            r: base,
            r_t2d: t2d,
            fixed: base,
            tag: b16(7),
        };
        let idle = EquationIn {
            valid: false,
            ..request
        };
        let outputs: Vec<_> = EquationPipe::default()
            .run(
                iter::once(idle)
                    .chain(iter::once(request))
                    .chain(iter::repeat_n(idle, 100))
                    .with_reset(1)
                    .clock_pos_edge(100),
            )
            .synchronous_sample()
            .map(|sample| sample.output)
            .filter(|output| output.valid)
            .collect();
        assert_eq!(outputs.len(), 1);
        assert!(outputs[0].equal);
        assert_eq!(outputs[0].tag, b16(7));
    }

    #[test]
    fn basepoint_plus_basepoint_compares_equal_to_double() {
        let (base, t2d) = basepoint();
        let double = ExtendedPoint {
            x: field([
                0x83c5a14e2843ce0e,
                0x080d8e4515d7a45f,
                0x3d043b7d1833e7ac,
                0x36ab384c9f5a046c,
            ]),
            y: field([
                0x0e5f46ae6af8a3c9,
                0x97390f5164385156,
                0x1da25ee8c9a21f56,
                0x2260cdf3092329c2,
            ]),
            z: FieldElement51::one(),
            t: field([
                0xb71a3f556d69b401,
                0x5d79acc9c1f72402,
                0x1de55f087303b413,
                0x2498a7850b2f68dc,
            ]),
        };
        let request = EquationIn {
            valid: true,
            variable: base,
            r: base,
            r_t2d: t2d,
            fixed: double,
            tag: b16(8),
        };
        let idle = EquationIn {
            valid: false,
            ..request
        };
        let output = EquationPipe::default()
            .run(
                iter::once(idle)
                    .chain(iter::once(request))
                    .chain(iter::repeat_n(idle, 100))
                    .with_reset(1)
                    .clock_pos_edge(100),
            )
            .synchronous_sample()
            .map(|sample| sample.output)
            .find(|output| output.valid)
            .unwrap();
        assert!(output.equal);
        assert_eq!(output.tag, b16(8));
    }
}