rhdl_ed25519_fast_core/

variable_base.rs

//! Constant-pattern variable-base scalar multiplication.
//!
//! [`VariableBaseMul`] computes `[scalar]P` for a decoded affine point.  Every
//! one of the 256 scalar bits executes one complete Edwards doubling and one
//! complete mixed addition; a final multiplexer selects the bit result.  The
//! operation count and memory access pattern therefore do not reveal scalar
//! bits.
//!
//! Four radix-`2^51` multipliers execute each formula round together.  Twenty
//! independent contexts hide their 17-cycle latency, allowing one four-product
//! round to issue each clock.  A lane consumes 1,024 issue clocks per scalar;
//! the strict verifier uses two lanes for a sustained request interval near 512
//! clocks.

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

use crate::{
    field_parallel::{
        FieldElement51, FieldMulIn, FieldMulPipe, field_add_kernel, field_neg_kernel,
        field_sub_kernel,
    },
    multicomb::ExtendedPoint,
    scalar::ScalarWords,
};

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

/// Internal formula phase for one scalar context.
#[derive(Copy, Clone, Debug, Default, PartialEq, Digital)]
#[doc(hidden)]
pub enum VariablePhase {
    /// First four products of a doubling.
    #[default]
    DoubleFirst,
    /// Four coordinate products completing a doubling.
    DoubleSecond,
    /// First three products of a mixed addition.
    AddFirst,
    /// Four coordinate products completing a mixed addition.
    AddSecond,
}

/// Tagged variable-base multiplication request.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct VariableBaseIn {
    /// Marks this request valid when [`VariableBaseOut::ready`] is high.
    pub valid: bool,
    /// Decoded affine point `(X, Y, 1, X*Y)`.
    pub point: ExtendedPoint,
    /// Precomputed affine `2*d*T` returned by the point decoder.
    pub t2d: FieldElement51,
    /// Canonical scalar in little-endian words.
    pub scalar: ScalarWords,
    /// Caller-defined transaction tag.
    pub tag: b16,
}

/// Result and flow control from [`VariableBaseMul`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct VariableBaseOut {
    /// High when at least one context is available.
    pub ready: bool,
    /// High for one cycle when [`Self::point`] is valid.
    pub valid: bool,
    /// Projective extended result `[scalar]P`.
    pub point: ExtendedPoint,
    /// Delayed caller tag.
    pub tag: b16,
    /// Number of occupied scalar contexts.
    pub occupancy: b5,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct VariableContext {
    state: b2,
    phase: VariablePhase,
    bit: b8,
    scalar: ScalarWords,
    tag: b16,
    base: ExtendedPoint,
    base_t2d: FieldElement51,
    accumulator: ExtendedPoint,
    e: FieldElement51,
    f: FieldElement51,
    g: FieldElement51,
    h: FieldElement51,
}

fn empty_context() -> VariableContext {
    let zero = FieldElement51::zero();
    let identity = ExtendedPoint::identity();
    VariableContext {
        state: b2(FREE),
        phase: VariablePhase::DoubleFirst,
        bit: b8(0),
        scalar: ScalarWords { words: [b64(0); 4] },
        tag: b16(0),
        base: identity,
        base_t2d: zero,
        accumulator: identity,
        e: zero,
        f: zero,
        g: zero,
        h: zero,
    }
}

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

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

/// Twenty-context, four-multiplier variable-point scalar engine.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct VariableBaseMul {
    control: DFF<VariableControl>,
    mul0: FieldMulPipe,
    mul1: FieldMulPipe,
    mul2: FieldMulPipe,
    mul3: FieldMulPipe,
}

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

impl SynchronousIO for VariableBaseMul {
    type I = VariableBaseIn;
    type O = VariableBaseOut;
    type Kernel = variable_base_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) -> VariableContext {
    VariableContext {
        state: b2(FREE),
        phase: VariablePhase::DoubleFirst,
        bit: b8(0),
        scalar: ScalarWords { words: [b64(0); 4] },
        tag: b16(0),
        base: identity(),
        base_t2d: zero(),
        accumulator: identity(),
        e: zero(),
        f: zero(),
        g: zero(),
        h: zero(),
    }
}

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

#[kernel]
fn scalar_bit(scalar: ScalarWords, bit: b8) -> bool {
    let word = (bit >> 6).resize::<2>();
    let shift = bit.resize::<6>();
    ((scalar.words[word] >> shift) & b64(1)) != b64(0)
}

/// State transition for [`VariableBaseMul`].
#[kernel]
pub fn variable_base_kernel(
    _cr: ClockReset,
    i: VariableBaseIn,
    q: VariableBaseMulQ,
) -> (VariableBaseOut, VariableBaseMulD) {
    let r = q.control;
    let mut n = r;
    let zero = zero();
    let mut output = VariableBaseOut {
        ready: false,
        valid: false,
        point: identity(),
        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 {
            VariablePhase::DoubleFirst => {
                let sum = field_add_kernel(context.accumulator.x, context.accumulator.y);
                a = [
                    context.accumulator.x,
                    context.accumulator.y,
                    context.accumulator.z,
                    sum,
                ];
                b = a;
            }
            VariablePhase::AddFirst => {
                a[0] = field_sub_kernel(context.accumulator.y, context.accumulator.x);
                b[0] = field_sub_kernel(context.base.y, context.base.x);
                a[1] = field_add_kernel(context.accumulator.y, context.accumulator.x);
                b[1] = field_add_kernel(context.base.y, context.base.x);
                a[2] = context.accumulator.t;
                b[2] = context.base_t2d;
                a[3] = zero;
                b[3] = zero;
            }
            _ => {
                a = [context.e, context.g, context.e, context.f];
                b = [context.f, context.h, context.h, context.g];
            }
        }
        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 {
            VariablePhase::DoubleFirst => {
                let d = field_neg_kernel(q.mul0.result);
                let c = field_add_kernel(q.mul2.result, q.mul2.result);
                let g = field_add_kernel(d, q.mul1.result);
                updated.e = field_sub_kernel(
                    field_sub_kernel(q.mul3.result, q.mul0.result),
                    q.mul1.result,
                );
                updated.f = field_sub_kernel(g, c);
                updated.g = g;
                updated.h = field_sub_kernel(d, q.mul1.result);
                updated.phase = VariablePhase::DoubleSecond;
            }
            VariablePhase::AddFirst => {
                let d = field_add_kernel(current.accumulator.z, current.accumulator.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 = VariablePhase::AddSecond;
            }
            VariablePhase::DoubleSecond => {
                updated.accumulator = ExtendedPoint {
                    x: q.mul0.result,
                    y: q.mul1.result,
                    z: q.mul3.result,
                    t: q.mul2.result,
                };
                updated.phase = VariablePhase::AddFirst;
            }
            VariablePhase::AddSecond => {
                let added = ExtendedPoint {
                    x: q.mul0.result,
                    y: q.mul1.result,
                    z: q.mul3.result,
                    t: q.mul2.result,
                };
                if scalar_bit(current.scalar, current.bit) {
                    updated.accumulator = added;
                }
                if current.bit == b8(0) {
                    output.valid = true;
                    output.point = if scalar_bit(current.scalar, current.bit) {
                        added
                    } else {
                        current.accumulator
                    };
                    output.tag = current.tag;
                    updated = empty_context_kernel(false);
                } else {
                    updated.bit = current.bit - b8(1);
                    updated.phase = VariablePhase::DoubleFirst;
                }
            }
        }
        n.contexts[result_context] = updated;
    }

    if i.valid && free_found {
        n.contexts[free_context] = VariableContext {
            state: b2(READY),
            phase: VariablePhase::DoubleFirst,
            bit: b8(255),
            scalar: i.scalar,
            tag: i.tag,
            base: i.point,
            base_t2d: i.t2d,
            accumulator: identity(),
            e: zero,
            f: zero,
            g: zero,
            h: zero,
        };
    }

    let mut d = VariableBaseMulD::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, field_to_words_kernel};
    use crate::point_compress::CompressedPoint;
    use crate::point_decode::{PointDecodeIn, PointDecodePipe};
    use curve25519_dalek::{
        constants::ED25519_BASEPOINT_POINT, edwards::CompressedEdwardsY, scalar::Scalar,
    };
    use num_bigint::BigUint;
    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,
            ]),
        )
    }

    fn scalar_words(value: Scalar) -> ScalarWords {
        let bytes = value.to_bytes();
        ScalarWords {
            words: std::array::from_fn(|index| {
                b64(u64::from_le_bytes(bytes[index * 8..index * 8 + 8].try_into().unwrap()) as u128)
            }),
        }
    }

    fn compress(point: ExtendedPoint) -> [u8; 32] {
        let p = (BigUint::from(1u8) << 255) - BigUint::from(19u8);
        let value = |field: FieldElement51| {
            field_to_words_kernel(field)
                .iter()
                .enumerate()
                .fold(BigUint::from(0u8), |sum, (index, word)| {
                    sum + (BigUint::from(word.raw()) << (64 * index))
                })
        };
        let inverse = value(point.z).modpow(&(&p - BigUint::from(2u8)), &p);
        let x = (value(point.x) * &inverse) % &p;
        let y = (value(point.y) * inverse) % &p;
        let mut bytes = y.to_bytes_le();
        bytes.resize(32, 0);
        bytes[31] |= ((&x & BigUint::from(1u8))
            .to_u64_digits()
            .first()
            .copied()
            .unwrap_or(0) as u8)
            << 7;
        bytes.try_into().unwrap()
    }

    #[test]
    fn twenty_interleaved_scalars_match_dalek() {
        std::thread::Builder::new()
            .name("variable-base-sim".into())
            .stack_size(256 * 1024 * 1024)
            .spawn(|| {
                let (point, t2d) = basepoint();
                let scalars: Vec<_> = (1u64..=20).map(Scalar::from).collect();
                let requests = scalars
                    .iter()
                    .enumerate()
                    .map(|(index, scalar)| VariableBaseIn {
                        valid: true,
                        point,
                        t2d,
                        scalar: scalar_words(*scalar),
                        tag: b16(index as u128),
                    });
                let idle = VariableBaseIn {
                    valid: false,
                    point: ExtendedPoint::identity(),
                    t2d: FieldElement51::zero(),
                    scalar: scalar_words(Scalar::ZERO),
                    tag: b16(0),
                };
                let outputs: Vec<_> = VariableBaseMul::default()
                    .run(
                        iter::once(idle)
                            .chain(requests)
                            .chain(iter::repeat_n(idle, 24_000))
                            .with_reset(1)
                            .clock_pos_edge(100),
                    )
                    .synchronous_sample()
                    .enumerate()
                    .filter_map(|(cycle, sample)| {
                        sample.output.valid.then_some((cycle, sample.output))
                    })
                    .collect();
                assert_eq!(outputs.len(), scalars.len());
                for (_, output) in &outputs {
                    let scalar = scalars[output.tag.raw() as usize];
                    assert_eq!(
                        compress(output.point),
                        (ED25519_BASEPOINT_POINT * scalar).compress().to_bytes()
                    );
                }
                let span = outputs.last().unwrap().0 - outputs.first().unwrap().0;
                let interval = span as f64 / (outputs.len() - 1) as f64;
                println!("variable-base sustained interval={interval:.3} cycles");
                assert!(interval <= 1_050.0);
            })
            .unwrap()
            .join()
            .unwrap();
    }

    #[test]
    fn decoded_arbitrary_point_multiplies_like_dalek() {
        let source_scalar = Scalar::from(0x1234_5678_u64);
        let source_point = ED25519_BASEPOINT_POINT * source_scalar;
        let encoded = source_point.compress().to_bytes();
        let decode_idle = PointDecodeIn {
            valid: false,
            encoded: CompressedPoint::zero(),
            tag: b16(0),
        };
        let decode_request = PointDecodeIn {
            valid: true,
            encoded: CompressedPoint {
                words: std::array::from_fn(|index| {
                    b64(
                        u64::from_le_bytes(encoded[index * 8..index * 8 + 8].try_into().unwrap())
                            as u128,
                    )
                }),
            },
            tag: b16(9),
        };
        let decoded = PointDecodePipe::default()
            .run(
                iter::once(decode_idle)
                    .chain(iter::once(decode_request))
                    .chain(iter::repeat_n(decode_idle, 12_000))
                    .with_reset(1)
                    .clock_pos_edge(100),
            )
            .synchronous_sample()
            .map(|sample| sample.output)
            .find(|output| output.valid)
            .unwrap();
        assert!(decoded.point_valid);

        let scalar = Scalar::from(0xfeed_beef_u64);
        let request = VariableBaseIn {
            valid: true,
            point: decoded.point,
            t2d: decoded.t2d,
            scalar: scalar_words(scalar),
            tag: b16(10),
        };
        let idle = VariableBaseIn {
            valid: false,
            ..request
        };
        let output = VariableBaseMul::default()
            .run(
                iter::once(idle)
                    .chain(iter::once(request))
                    .chain(iter::repeat_n(idle, 20_000))
                    .with_reset(1)
                    .clock_pos_edge(100),
            )
            .synchronous_sample()
            .map(|sample| sample.output)
            .find(|output| output.valid)
            .unwrap();
        assert_eq!(
            CompressedEdwardsY(compress(output.point)),
            (source_point * scalar).compress()
        );
    }

    #[test]
    fn compiles_to_native_rhdl_netlist() -> miette::Result<()> {
        unsafe { std::env::set_var("RHDL_SKIP_IVERILOG_CHECK", "1") };
        VariableBaseMul::default()
            .descriptor(ScopedName::top())?
            .hdl()?;
        Ok(())
    }
}