rhdl_ed25519_fast_core/

point_decode.rs

//! Constant-pattern compressed Edwards-point decoding.
//!
//! Ed25519 verification begins by recovering the affine `X` coordinate from a
//! compressed Edwards `Y` coordinate.  [`PointDecodePipe`] runs that square-root
//! calculation entirely in hardware.  Twenty request contexts share one
//! initiation-interval-one radix-`2^51` multiplier; while one context waits for
//! its 17-cycle product, another context issues the next operation.
//!
//! The exponentiation schedule is deliberately simple: a fixed binary
//! square-and-multiply implementation of `(p - 5) / 8`.  Its 516 field products
//! per point are independent of input data.  A verifier can instantiate one
//! lane for public keys and one for signature `R` values, accepting a pair every
//! 516 clocks without external memory.

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

use crate::{
    field_parallel::{
        FieldElement51, FieldMulIn, FieldMulPipe, field_add_kernel, field_eq_kernel,
        field_from_words_kernel, field_neg_kernel, field_sub_kernel, field_to_words_kernel,
    },
    multicomb::ExtendedPoint,
    point_compress::CompressedPoint,
};

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 DecodeStep {
    #[default]
    Y2,
    Dy2,
    V2,
    V3,
    V6,
    V7,
    Uv3,
    Uv7,
    ExpSquare,
    ExpMul,
    Root,
    Root2,
    Check,
    Correct,
    T,
    T2d,
}

/// One compressed point and its caller-selected transaction tag.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct PointDecodeIn {
    /// Marks this request valid when [`PointDecodeOut::ready`] is high.
    pub valid: bool,
    /// Compressed Edwards-Y encoding.
    pub encoded: CompressedPoint,
    /// Tag returned unchanged with the result.
    pub tag: b16,
}

/// Result and flow control from [`PointDecodePipe`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct PointDecodeOut {
    /// High when at least one of the 20 contexts is free.
    pub ready: bool,
    /// High for one cycle when the remaining fields are valid.
    pub valid: bool,
    /// High only for a canonical encoding of a curve point.
    pub point_valid: bool,
    /// High for one of the eight compressed low-order points.
    pub small_order: bool,
    /// Recovered extended point `(X, Y, 1, X*Y)`.
    pub point: ExtendedPoint,
    /// Affine `2*d*T`, precomputed for mixed additions.
    pub t2d: FieldElement51,
    /// Delayed caller tag.
    pub tag: b16,
    /// Number of occupied decoder contexts.
    pub occupancy: b5,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct DecodeContext {
    state: b2,
    step: DecodeStep,
    tag: b16,
    sign: bool,
    canonical: bool,
    small_order: bool,
    square: bool,
    flipped: bool,
    exponent_bit: b8,
    y: FieldElement51,
    u: FieldElement51,
    v: FieldElement51,
    v2: FieldElement51,
    v3: FieldElement51,
    v7: FieldElement51,
    uv3: FieldElement51,
    base: FieldElement51,
    accumulator: FieldElement51,
    root: FieldElement51,
    x: FieldElement51,
    t: FieldElement51,
}

fn empty_context() -> DecodeContext {
    let zero = FieldElement51::zero();
    DecodeContext {
        state: b2(FREE),
        step: DecodeStep::Y2,
        tag: b16(0),
        sign: false,
        canonical: false,
        small_order: false,
        square: false,
        flipped: false,
        exponent_bit: b8(0),
        y: zero,
        u: zero,
        v: zero,
        v2: zero,
        v3: zero,
        v7: zero,
        uv3: zero,
        base: zero,
        accumulator: zero,
        root: zero,
        x: zero,
        t: zero,
    }
}

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

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

/// Twenty-context fixed-schedule Edwards point decoder.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct PointDecodePipe {
    control: DFF<DecodeControl>,
    multiplier: FieldMulPipe,
}

impl Default for PointDecodePipe {
    fn default() -> Self {
        Self {
            control: DFF::new(reset_control()),
            multiplier: FieldMulPipe::default(),
        }
    }
}

impl SynchronousIO for PointDecodePipe {
    type I = PointDecodeIn;
    type O = PointDecodeOut;
    type Kernel = point_decode_kernel;
}

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

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

#[kernel]
fn empty_context_kernel(_unused: bool) -> DecodeContext {
    let zero = field_zero();
    DecodeContext {
        state: b2(FREE),
        step: DecodeStep::Y2,
        tag: b16(0),
        sign: false,
        canonical: false,
        small_order: false,
        square: false,
        flipped: false,
        exponent_bit: b8(0),
        y: zero,
        u: zero,
        v: zero,
        v2: zero,
        v3: zero,
        v7: zero,
        uv3: zero,
        base: zero,
        accumulator: zero,
        root: zero,
        x: zero,
        t: zero,
    }
}

#[kernel]
fn edwards_d() -> FieldElement51 {
    field_from_words_kernel([
        b64(0x75eb4dca135978a3),
        b64(0x00700a4d4141d8ab),
        b64(0x8cc740797779e898),
        b64(0x52036cee2b6ffe73),
    ])
}

#[kernel]
fn sqrt_m1() -> FieldElement51 {
    field_from_words_kernel([
        b64(0xc4ee1b274a0ea0b0),
        b64(0x2f431806ad2fe478),
        b64(0x2b4d00993dfbd7a7),
        b64(0x2b8324804fc1df0b),
    ])
}

#[kernel]
fn edwards_d2() -> FieldElement51 {
    field_from_words_kernel([
        b64(0xebd69b9426b2f159),
        b64(0x00e0149a8283b156),
        b64(0x198e80f2eef3d130),
        b64(0x2406d9dc56dffce7),
    ])
}

#[kernel]
fn words_equal(a: [b64; 4], b: [b64; 4]) -> bool {
    a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]
}

#[kernel]
fn canonical_y(words: [b64; 4]) -> bool {
    let high = words[3] & b64(0x7fff_ffff_ffff_ffff);
    high < b64(0x7fff_ffff_ffff_ffff)
        || (high == b64(0x7fff_ffff_ffff_ffff)
            && words[2] == b64(0xffff_ffff_ffff_ffff)
            && words[1] == b64(0xffff_ffff_ffff_ffff)
            && words[0] < b64(0xffff_ffff_ffff_ffed))
}

#[kernel]
fn small_order_encoding(words: [b64; 4]) -> bool {
    words_equal(words, [b64(1), b64(0), b64(0), b64(0)])
        || words_equal(
            words,
            [
                b64(0x4fd84d3d706a17c7),
                b64(0x0f67100d760b3cba),
                b64(0xc6cc392cfa53202a),
                b64(0x7a03ac9277fdc74e),
            ],
        )
        || words_equal(words, [b64(0), b64(0), b64(0), b64(0x8000_0000_0000_0000)])
        || words_equal(
            words,
            [
                b64(0xb027b2c28f95e826),
                b64(0xf098eff289f4c345),
                b64(0x3933c6d305acdfd5),
                b64(0x05fc536d880238b1),
            ],
        )
        || words_equal(
            words,
            [
                b64(0xffff_ffff_ffff_ffec),
                b64(0xffff_ffff_ffff_ffff),
                b64(0xffff_ffff_ffff_ffff),
                b64(0x7fff_ffff_ffff_ffff),
            ],
        )
        || words_equal(
            words,
            [
                b64(0xb027b2c28f95e826),
                b64(0xf098eff289f4c345),
                b64(0x3933c6d305acdfd5),
                b64(0x85fc536d880238b1),
            ],
        )
        || words_equal(words, [b64(0), b64(0), b64(0), b64(0)])
        || words_equal(
            words,
            [
                b64(0x4fd84d3d706a17c7),
                b64(0x0f67100d760b3cba),
                b64(0xc6cc392cfa53202a),
                b64(0xfa03ac9277fdc74e),
            ],
        )
}

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

#[kernel]
fn signed_root(value: FieldElement51, sign: bool) -> FieldElement51 {
    let odd = (field_to_words_kernel(value)[0] & b64(1)) != b64(0);
    if odd == sign {
        value
    } else {
        field_neg_kernel(value)
    }
}

/// State transition for [`PointDecodePipe`].
#[kernel]
pub fn point_decode_kernel(
    _cr: ClockReset,
    i: PointDecodeIn,
    q: PointDecodePipeQ,
) -> (PointDecodeOut, PointDecodePipeD) {
    let r = q.control;
    let mut n = r;
    let zero = field_zero();
    let one = field_one();
    let mut output = PointDecodeOut {
        ready: false,
        valid: false,
        point_valid: false,
        small_order: false,
        point: ExtendedPoint {
            x: zero,
            y: one,
            z: one,
            t: zero,
        },
        t2d: zero,
        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 operand_a = zero;
    let mut operand_b = zero;
    if issue_found {
        match context.step {
            DecodeStep::Y2 => {
                operand_a = context.y;
                operand_b = context.y;
            }
            DecodeStep::Dy2 => {
                operand_a = field_add_kernel(context.u, one);
                operand_b = edwards_d();
            }
            DecodeStep::V2 => {
                operand_a = context.v;
                operand_b = context.v;
            }
            DecodeStep::V3 => {
                operand_a = context.v2;
                operand_b = context.v;
            }
            DecodeStep::V6 => {
                operand_a = context.v3;
                operand_b = context.v3;
            }
            DecodeStep::V7 => {
                operand_a = context.v2;
                operand_b = context.v;
            }
            DecodeStep::Uv3 => {
                operand_a = context.u;
                operand_b = context.v3;
            }
            DecodeStep::Uv7 => {
                operand_a = context.u;
                operand_b = context.v7;
            }
            DecodeStep::ExpSquare => {
                operand_a = context.accumulator;
                operand_b = context.accumulator;
            }
            DecodeStep::ExpMul => {
                operand_a = context.accumulator;
                operand_b = context.base;
            }
            DecodeStep::Root => {
                operand_a = context.uv3;
                operand_b = context.accumulator;
            }
            DecodeStep::Root2 => {
                operand_a = context.root;
                operand_b = context.root;
            }
            DecodeStep::Check => {
                operand_a = context.v;
                operand_b = context.accumulator;
            }
            DecodeStep::Correct => {
                operand_a = context.root;
                operand_b = if context.flipped { sqrt_m1() } else { one };
            }
            DecodeStep::T => {
                operand_a = context.x;
                operand_b = context.y;
            }
            _ => {
                operand_a = context.t;
                operand_b = edwards_d2();
            }
        }
        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.multiplier.valid {
        let result_context = r.issue_context[16];
        let current = r.contexts[result_context];
        let result = q.multiplier.result;
        n.contexts[result_context].state = b2(READY);
        match current.step {
            DecodeStep::Y2 => {
                n.contexts[result_context].u = field_sub_kernel(result, one);
                n.contexts[result_context].step = DecodeStep::Dy2;
            }
            DecodeStep::Dy2 => {
                n.contexts[result_context].v = field_add_kernel(result, one);
                n.contexts[result_context].step = DecodeStep::V2;
            }
            DecodeStep::V2 => {
                n.contexts[result_context].v2 = result;
                n.contexts[result_context].step = DecodeStep::V3;
            }
            DecodeStep::V3 => {
                n.contexts[result_context].v3 = result;
                n.contexts[result_context].step = DecodeStep::V6;
            }
            DecodeStep::V6 => {
                n.contexts[result_context].v2 = result;
                n.contexts[result_context].step = DecodeStep::V7;
            }
            DecodeStep::V7 => {
                n.contexts[result_context].v7 = result;
                n.contexts[result_context].step = DecodeStep::Uv3;
            }
            DecodeStep::Uv3 => {
                n.contexts[result_context].uv3 = result;
                n.contexts[result_context].step = DecodeStep::Uv7;
            }
            DecodeStep::Uv7 => {
                n.contexts[result_context].base = result;
                n.contexts[result_context].accumulator = one;
                n.contexts[result_context].exponent_bit = b8(251);
                n.contexts[result_context].step = DecodeStep::ExpSquare;
            }
            DecodeStep::ExpSquare => {
                n.contexts[result_context].accumulator = result;
                if current.exponent_bit == b8(1) {
                    n.contexts[result_context].exponent_bit = b8(0);
                    n.contexts[result_context].step = DecodeStep::ExpSquare;
                } else {
                    n.contexts[result_context].step = DecodeStep::ExpMul;
                }
            }
            DecodeStep::ExpMul => {
                n.contexts[result_context].accumulator = result;
                if current.exponent_bit == b8(0) {
                    n.contexts[result_context].step = DecodeStep::Root;
                } else {
                    n.contexts[result_context].exponent_bit = current.exponent_bit - b8(1);
                    n.contexts[result_context].step = DecodeStep::ExpSquare;
                }
            }
            DecodeStep::Root => {
                n.contexts[result_context].root = result;
                n.contexts[result_context].step = DecodeStep::Root2;
            }
            DecodeStep::Root2 => {
                n.contexts[result_context].accumulator = result;
                n.contexts[result_context].step = DecodeStep::Check;
            }
            DecodeStep::Check => {
                let negative_u = field_neg_kernel(current.u);
                n.contexts[result_context].square =
                    field_eq_kernel(result, current.u) || field_eq_kernel(result, negative_u);
                n.contexts[result_context].flipped = !field_eq_kernel(result, current.u);
                n.contexts[result_context].step = DecodeStep::Correct;
            }
            DecodeStep::Correct => {
                let x = signed_root(result, current.sign);
                n.contexts[result_context].x = x;
                n.contexts[result_context].step = DecodeStep::T;
            }
            DecodeStep::T => {
                n.contexts[result_context].t = result;
                n.contexts[result_context].step = DecodeStep::T2d;
            }
            _ => {
                output.valid = true;
                output.point_valid = current.canonical
                    && current.square
                    && !(field_eq_kernel(current.x, zero) && current.sign);
                output.small_order = current.small_order;
                output.point = ExtendedPoint {
                    x: current.x,
                    y: current.y,
                    z: one,
                    t: current.t,
                };
                output.t2d = result;
                output.tag = current.tag;
                n.contexts[result_context] = empty_context_kernel(false);
            }
        }
    }

    if i.valid && free_found {
        let mut y_words = i.encoded.words;
        let sign = (y_words[3] >> 63) != b64(0);
        y_words[3] &= b64(0x7fff_ffff_ffff_ffff);
        n.contexts[free_context] = DecodeContext {
            state: b2(READY),
            step: DecodeStep::Y2,
            tag: i.tag,
            sign,
            canonical: canonical_y(i.encoded.words),
            small_order: small_order_encoding(i.encoded.words),
            exponent_bit: b8(0),
            y: field_from_words_kernel(y_words),
            ..empty_context_kernel(false)
        };
    }

    let mut d = PointDecodePipeD::dont_care();
    d.control = n;
    d.multiplier = FieldMulIn {
        valid: issue_found,
        a: operand_a,
        b: operand_b,
    };
    (output, d)
}

#[cfg(test)]
mod tests {
    use super::*;
    use curve25519_dalek::{constants::ED25519_BASEPOINT_COMPRESSED, edwards::CompressedEdwardsY};
    use ed25519_dalek::{Signer, SigningKey};
    use std::iter;

    fn compressed(bytes: [u8; 32]) -> CompressedPoint {
        CompressedPoint {
            words: std::array::from_fn(|index| {
                b64(u64::from_le_bytes(bytes[index * 8..index * 8 + 8].try_into().unwrap()) as u128)
            }),
        }
    }

    fn point_bytes(point: ExtendedPoint) -> [u8; 32] {
        let mut bytes = [0u8; 32];
        for (index, word) in field_to_words_kernel(point.y).iter().enumerate() {
            bytes[index * 8..index * 8 + 8].copy_from_slice(&(word.raw() as u64).to_le_bytes());
        }
        bytes[31] |= ((field_to_words_kernel(point.x)[0].raw() as u8) & 1) << 7;
        bytes
    }

    fn idle() -> PointDecodeIn {
        PointDecodeIn {
            valid: false,
            encoded: CompressedPoint::zero(),
            tag: b16(0),
        }
    }

    #[test]
    fn decodes_basepoint_and_rejects_noncanonical_and_low_order() {
        std::thread::Builder::new()
            .name("point-decode-sim".into())
            .stack_size(256 * 1024 * 1024)
            .spawn(|| {
                let mut noncanonical = [0xff; 32];
                noncanonical[31] = 0x7f;
                let identity = {
                    let mut value = [0u8; 32];
                    value[0] = 1;
                    value
                };
                let key = SigningKey::from_bytes(&[0x42; 32]);
                let signature = key.sign(&[0x5a; 64]).to_bytes();
                let mut encoded_r = [0u8; 32];
                encoded_r.copy_from_slice(&signature[..32]);
                let public_key = key.verifying_key().to_bytes();
                let requests = [
                    PointDecodeIn {
                        valid: true,
                        encoded: compressed(ED25519_BASEPOINT_COMPRESSED.to_bytes()),
                        tag: b16(1),
                    },
                    PointDecodeIn {
                        valid: true,
                        encoded: compressed(noncanonical),
                        tag: b16(2),
                    },
                    PointDecodeIn {
                        valid: true,
                        encoded: compressed(identity),
                        tag: b16(3),
                    },
                    PointDecodeIn {
                        valid: true,
                        encoded: compressed(public_key),
                        tag: b16(4),
                    },
                    PointDecodeIn {
                        valid: true,
                        encoded: compressed(encoded_r),
                        tag: b16(5),
                    },
                ];
                let outputs: Vec<_> = PointDecodePipe::default()
                    .run(
                        iter::once(idle())
                            .chain(requests)
                            .chain(iter::repeat_n(idle(), 12_000))
                            .with_reset(1)
                            .clock_pos_edge(100),
                    )
                    .synchronous_sample()
                    .map(|sample| sample.output)
                    .filter(|output| output.valid)
                    .collect();
                assert_eq!(outputs.len(), 5);
                let base = outputs.iter().find(|output| output.tag == b16(1)).unwrap();
                assert!(base.point_valid);
                assert!(!base.small_order);
                assert_eq!(
                    CompressedEdwardsY(point_bytes(base.point)),
                    ED25519_BASEPOINT_COMPRESSED
                );
                let bad = outputs.iter().find(|output| output.tag == b16(2)).unwrap();
                assert!(!bad.point_valid);
                let low = outputs.iter().find(|output| output.tag == b16(3)).unwrap();
                assert!(low.point_valid);
                assert!(low.small_order);
                let public = outputs.iter().find(|output| output.tag == b16(4)).unwrap();
                assert!(public.point_valid);
                assert_eq!(point_bytes(public.point), public_key);
                let r = outputs.iter().find(|output| output.tag == b16(5)).unwrap();
                assert!(r.point_valid);
                assert_eq!(point_bytes(r.point), encoded_r);
            })
            .unwrap()
            .join()
            .unwrap();
    }

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