rhdl_ed25519_fast_core/

verify.rs

//! High-throughput strict Ed25519 verification for 64-byte messages.
//!
//! [`StrictVerifyCore`] evaluates the complete Ed25519 equation in hardware:
//! SHA-512 challenge hashing, reduction modulo `l`, strict point decoding,
//! fixed-base `[S]B`, variable-base `[k]A`, and the projective equality check.
//! Intermediate points are joined by a 64-entry on-chip context store.  No
//! prehashing, external DRAM, HBM, or host arithmetic is part of the path.

use rhdl::prelude::*;
use rhdl_fpga::core::{
    dff::DFF,
    ram::synchronous::{In as RamIn, SyncBRAM, Write as RamWrite},
};

use crate::{
    equation::{EquationIn, EquationPipe},
    field_parallel::FieldElement51,
    multicomb::{ExtendedPoint, MultiCombMul, MultiCombMulIn},
    point_compress::CompressedPoint,
    point_decode::{PointDecodeIn, PointDecodePipe},
    protocol::{VerifyRequest, Words512},
    scalar::{ScalarWords, scalar_ge_kernel, scalar_l_kernel},
    scalar_parallel::{ScalarReducePipe, ScalarReducePipeIn},
    sha512_parallel::{Sha512Pool, Sha512PoolIn, Sha512PoolRequest},
    variable_base::{VariableBaseIn, VariableBaseMul},
};

/// Verification completed successfully.
pub const VERIFY_OK: u128 = 0;
/// Public-key encoding is not canonical or not on the curve.
pub const VERIFY_BAD_PUBLIC_KEY: u128 = 1;
/// Signature `R` encoding is not canonical or not on the curve.
pub const VERIFY_BAD_R: u128 = 2;
/// Public key is a low-order point.
pub const VERIFY_SMALL_PUBLIC_KEY: u128 = 3;
/// Signature `R` is a low-order point.
pub const VERIFY_SMALL_R: u128 = 4;
/// Signature scalar `S` is not canonical.
pub const VERIFY_NONCANONICAL_S: u128 = 5;
/// The Ed25519 group equation did not hold.
pub const VERIFY_EQUATION_FAILURE: u128 = 6;

/// Input channel of [`StrictVerifyCore`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct StrictVerifyIn {
    /// Marks [`Self::request`] valid when [`StrictVerifyOut::ready`] is high.
    pub valid: bool,
    /// Strict verification request for exactly 64 message bytes.
    pub request: VerifyRequest,
}

/// Output and flow control of [`StrictVerifyCore`].
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
pub struct StrictVerifyOut {
    /// High when the core can accept a request.
    pub ready: bool,
    /// High for one cycle when the decision fields are valid.
    pub valid: bool,
    /// Strict verification result.
    pub ok: bool,
    /// Stable error code; zero means success.
    pub error: b8,
    /// Delayed request tag.
    pub tag: b16,
    /// Number of occupied top-level verification contexts.
    pub occupancy: b7,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct VerifyStatus {
    used: bool,
    tag: b16,
    canonical_s: bool,
    a_ready: bool,
    a_valid: bool,
    a_small: bool,
    r_ready: bool,
    r_valid: bool,
    r_small: bool,
    fixed_ready: bool,
    hash1_pending: bool,
    challenge_ready: bool,
    variable_issued: bool,
    variable_ready: bool,
    variable_lane: bool,
    equation_issued: bool,
}

fn empty_status() -> VerifyStatus {
    VerifyStatus {
        used: false,
        tag: b16(0),
        canonical_s: false,
        a_ready: false,
        a_valid: false,
        a_small: false,
        r_ready: false,
        r_valid: false,
        r_small: false,
        fixed_ready: false,
        hash1_pending: false,
        challenge_ready: false,
        variable_issued: false,
        variable_ready: false,
        variable_lane: false,
        equation_issued: false,
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct Fetch {
    valid: bool,
    context: b6,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct VariableFetch {
    valid: bool,
    context: b6,
    lane: bool,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct HashIssue {
    valid: bool,
    context: b6,
    state: [b64; 8],
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct VerifyControl {
    status: [VerifyStatus; 64],
    hash_fetch: Fetch,
    hash_issue: HashIssue,
    variable_fetch: VariableFetch,
    equation_fetch: Fetch,
    hash_rr: b6,
    variable_rr: b6,
    equation_rr: b6,
    variable_lane_rr: bool,
}

fn reset_control() -> VerifyControl {
    VerifyControl {
        status: [empty_status(); 64],
        hash_fetch: Fetch {
            valid: false,
            context: b6(0),
        },
        hash_issue: HashIssue {
            valid: false,
            context: b6(0),
            state: [b64(0); 8],
        },
        variable_fetch: VariableFetch {
            valid: false,
            context: b6(0),
            lane: false,
        },
        equation_fetch: Fetch {
            valid: false,
            context: b6(0),
        },
        hash_rr: b6(0),
        variable_rr: b6(0),
        equation_rr: b6(0),
        variable_lane_rr: false,
    }
}

/// Point plus affine `2*d*T` retained after strict decoding.
#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct DecodedPoint {
    point: ExtendedPoint,
    t2d: FieldElement51,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct VerifyMemoryIn {
    chain: RamIn<Words512, 6>,
    a: RamIn<DecodedPoint, 6>,
    r: RamIn<DecodedPoint, 6>,
    fixed: RamIn<ExtendedPoint, 6>,
    challenge: RamIn<ScalarWords, 6>,
    variable0: RamIn<ExtendedPoint, 6>,
    variable1: RamIn<ExtendedPoint, 6>,
}

#[derive(Copy, Clone, Debug, PartialEq, Digital)]
#[doc(hidden)]
pub struct VerifyMemoryOut {
    chain: Words512,
    a: DecodedPoint,
    r: DecodedPoint,
    fixed: ExtendedPoint,
    challenge: ScalarWords,
    variable0: ExtendedPoint,
    variable1: ExtendedPoint,
}

/// Independent BRAM banks for the verifier's wide join values.
#[derive(Clone, Debug, Synchronous, SynchronousDQ, Default)]
#[doc(hidden)]
pub struct VerifyMemory {
    chain: SyncBRAM<Words512, 6>,
    a: SyncBRAM<DecodedPoint, 6>,
    r: SyncBRAM<DecodedPoint, 6>,
    fixed: SyncBRAM<ExtendedPoint, 6>,
    challenge: SyncBRAM<ScalarWords, 6>,
    variable0: SyncBRAM<ExtendedPoint, 6>,
    variable1: SyncBRAM<ExtendedPoint, 6>,
}

impl SynchronousIO for VerifyMemory {
    type I = VerifyMemoryIn;
    type O = VerifyMemoryOut;
    type Kernel = verify_memory_kernel;
}

/// Wiring transition for [`VerifyMemory`].
#[kernel]
#[doc(hidden)]
pub fn verify_memory_kernel(
    _cr: ClockReset,
    i: VerifyMemoryIn,
    q: VerifyMemoryQ,
) -> (VerifyMemoryOut, VerifyMemoryD) {
    let output = VerifyMemoryOut {
        chain: q.chain,
        a: q.a,
        r: q.r,
        fixed: q.fixed,
        challenge: q.challenge,
        variable0: q.variable0,
        variable1: q.variable1,
    };
    let mut d = VerifyMemoryD::dont_care();
    d.chain = i.chain;
    d.a = i.a;
    d.r = i.r;
    d.fixed = i.fixed;
    d.challenge = i.challenge;
    d.variable0 = i.variable0;
    d.variable1 = i.variable1;
    (output, d)
}

/// Entire strict verifier, expressed as one synthesizable RHDL module graph.
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
pub struct StrictVerifyCore {
    control: DFF<VerifyControl>,
    memory: VerifyMemory,
    decode_a: PointDecodePipe,
    decode_r: PointDecodePipe,
    sha: Sha512Pool,
    reducer: ScalarReducePipe,
    fixed: MultiCombMul,
    variable0: VariableBaseMul,
    variable1: VariableBaseMul,
    equation: EquationPipe,
}

impl Default for StrictVerifyCore {
    fn default() -> Self {
        Self {
            control: DFF::new(reset_control()),
            memory: VerifyMemory::default(),
            decode_a: PointDecodePipe::default(),
            decode_r: PointDecodePipe::default(),
            sha: Sha512Pool::default(),
            reducer: ScalarReducePipe::default(),
            fixed: MultiCombMul::default(),
            variable0: VariableBaseMul::default(),
            variable1: VariableBaseMul::default(),
            equation: EquationPipe::default(),
        }
    }
}

impl SynchronousIO for StrictVerifyCore {
    type I = StrictVerifyIn;
    type O = StrictVerifyOut;
    type Kernel = strict_verify_kernel;
}

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

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

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

#[kernel]
fn empty_status_kernel(_unused: bool) -> VerifyStatus {
    VerifyStatus {
        used: false,
        tag: b16(0),
        canonical_s: false,
        a_ready: false,
        a_valid: false,
        a_small: false,
        r_ready: false,
        r_valid: false,
        r_small: false,
        fixed_ready: false,
        hash1_pending: false,
        challenge_ready: false,
        variable_issued: false,
        variable_ready: false,
        variable_lane: false,
        equation_issued: false,
    }
}

#[kernel]
fn reverse_bytes(value: b64) -> b64 {
    let mut result = b64(0);
    for byte in 0..8 {
        result |= ((value >> (byte * 8) as u128).resize::<8>()).resize::<64>()
            << ((7 - byte) * 8) as u128;
    }
    result
}

#[kernel]
fn sha_iv() -> [b64; 8] {
    [
        b64(0x6a09e667f3bcc908),
        b64(0xbb67ae8584caa73b),
        b64(0x3c6ef372fe94f82b),
        b64(0xa54ff53a5f1d36f1),
        b64(0x510e527fade682d1),
        b64(0x9b05688c2b3e6c1f),
        b64(0x1f83d9abfb41bd6b),
        b64(0x5be0cd19137e2179),
    ]
}

#[kernel]
fn challenge_block0(request: VerifyRequest) -> [b64; 16] {
    let mut block = [b64(0); 16];
    for index in 0..4 {
        block[index] = reverse_bytes(request.signature.words[index]);
        block[index + 4] = reverse_bytes(request.public_key.words[index]);
    }
    for index in 0..8 {
        block[index + 8] = reverse_bytes(request.message.words[index]);
    }
    block
}

#[kernel]
fn challenge_block1() -> [b64; 16] {
    let mut block = [b64(0); 16];
    block[0] = b64(0x8000000000000000);
    block[15] = b64(0x400);
    block
}

#[kernel]
fn digest_words(state: [b64; 8]) -> Words512 {
    let mut words = [b64(0); 8];
    for index in 0..8 {
        words[index] = reverse_bytes(state[index]);
    }
    Words512 { words }
}

#[kernel]
fn request_r(request: VerifyRequest) -> CompressedPoint {
    CompressedPoint {
        words: [
            request.signature.words[0],
            request.signature.words[1],
            request.signature.words[2],
            request.signature.words[3],
        ],
    }
}

#[kernel]
fn request_s(request: VerifyRequest) -> ScalarWords {
    ScalarWords {
        words: [
            request.signature.words[4],
            request.signature.words[5],
            request.signature.words[6],
            request.signature.words[7],
        ],
    }
}

#[kernel]
fn wrap64(value: b6) -> b6 {
    value
}

#[kernel]
fn no_point_write() -> RamWrite<ExtendedPoint, 6> {
    RamWrite::<ExtendedPoint, 6> {
        addr: b6(0),
        value: identity(),
        enable: false,
    }
}

/// State transition for [`StrictVerifyCore`].
#[kernel]
pub fn strict_verify_kernel(
    _cr: ClockReset,
    i: StrictVerifyIn,
    q: StrictVerifyCoreQ,
) -> (StrictVerifyOut, StrictVerifyCoreD) {
    let r = q.control;
    let mut n = r;
    let zero_words = Words512 { words: [b64(0); 8] };
    let zero_scalar = ScalarWords { words: [b64(0); 4] };
    let empty_decoded = DecodedPoint {
        point: identity(),
        t2d: zero_field(),
    };
    let mut output = StrictVerifyOut {
        ready: false,
        valid: false,
        ok: false,
        error: b8(0),
        tag: b16(0),
        occupancy: b7(0),
    };

    let mut free_found = false;
    let mut free_context = b6(0);
    for context in 0..64 {
        if r.status[context].used {
            output.occupancy += b7(1);
        } else if !free_found {
            free_found = true;
            free_context = b6(context as u128);
        }
    }
    let accept_resources =
        free_found && q.decode_a.ready && q.decode_r.ready && q.fixed.ready && q.sha.request1_ready;
    output.ready = accept_resources;
    let accept = i.valid && accept_resources;

    let mut chain_write = RamWrite::<Words512, 6> {
        addr: b6(0),
        value: zero_words,
        enable: false,
    };
    let mut a_write = RamWrite::<DecodedPoint, 6> {
        addr: b6(0),
        value: empty_decoded,
        enable: false,
    };
    let mut r_write = a_write;
    let mut fixed_write = no_point_write();
    let mut challenge_write = RamWrite::<ScalarWords, 6> {
        addr: b6(0),
        value: zero_scalar,
        enable: false,
    };
    let mut variable0_write = no_point_write();
    let mut variable1_write = no_point_write();

    if accept {
        let scalar = request_s(i.request);
        n.status[free_context] = VerifyStatus {
            used: true,
            tag: i.request.tag,
            canonical_s: !scalar_ge_kernel(scalar, scalar_l_kernel(false)),
            ..empty_status_kernel(false)
        };
    }

    if q.decode_a.valid {
        let context = q.decode_a.tag.resize::<6>();
        n.status[context].a_ready = true;
        n.status[context].a_valid = q.decode_a.point_valid;
        n.status[context].a_small = q.decode_a.small_order;
        a_write = RamWrite::<DecodedPoint, 6> {
            addr: context,
            value: DecodedPoint {
                point: q.decode_a.point,
                t2d: q.decode_a.t2d,
            },
            enable: true,
        };
    }
    if q.decode_r.valid {
        let context = q.decode_r.tag.resize::<6>();
        n.status[context].r_ready = true;
        n.status[context].r_valid = q.decode_r.point_valid;
        n.status[context].r_small = q.decode_r.small_order;
        r_write = RamWrite::<DecodedPoint, 6> {
            addr: context,
            value: DecodedPoint {
                point: q.decode_r.point,
                t2d: q.decode_r.t2d,
            },
            enable: true,
        };
    }
    if q.fixed.valid {
        let context = q.fixed.tag.resize::<6>();
        n.status[context].fixed_ready = true;
        fixed_write = RamWrite::<ExtendedPoint, 6> {
            addr: context,
            value: q.fixed.point,
            enable: true,
        };
    }

    let sha_results = [q.sha.result0, q.sha.result1];
    let mut reducer_input = ScalarReducePipeIn {
        valid: false,
        wide: zero_words,
        tag: b16(0),
    };
    for result_index in 0..2 {
        let result = sha_results[result_index];
        if result.valid {
            let context = result.tag.resize::<6>();
            let second = (result.tag & b9(0x40)) != b9(0);
            if second {
                reducer_input = ScalarReducePipeIn {
                    valid: true,
                    wide: digest_words(result.state),
                    tag: context.resize::<16>(),
                };
            } else {
                n.status[context].hash1_pending = true;
                chain_write = RamWrite::<Words512, 6> {
                    addr: context,
                    value: Words512 {
                        words: result.state,
                    },
                    enable: true,
                };
            }
        }
    }
    if q.reducer.valid {
        let context = q.reducer.tag.resize::<6>();
        n.status[context].challenge_ready = true;
        challenge_write = RamWrite::<ScalarWords, 6> {
            addr: context,
            value: q.reducer.scalar,
            enable: true,
        };
    }

    let hash_issue_accepted = r.hash_issue.valid && q.sha.request0_ready;
    if hash_issue_accepted {
        n.hash_issue.valid = false;
    }
    if r.hash_fetch.valid && (!r.hash_issue.valid || hash_issue_accepted) {
        n.hash_issue = HashIssue {
            valid: true,
            context: r.hash_fetch.context,
            state: q.memory.chain.words,
        };
        n.hash_fetch.valid = false;
    }
    if !n.hash_fetch.valid {
        let mut found = false;
        let mut selected = b6(0);
        for offset in 0..64 {
            let candidate = wrap64(r.hash_rr + b6(offset as u128));
            if !found && r.status[candidate].used && r.status[candidate].hash1_pending {
                found = true;
                selected = candidate;
            }
        }
        if found {
            n.status[selected].hash1_pending = false;
            n.hash_fetch = Fetch {
                valid: true,
                context: selected,
            };
            n.hash_rr = selected + b6(1);
        }
    }

    let lane0_ready = q.variable0.ready;
    let lane1_ready = q.variable1.ready;
    let variable_input_valid = r.variable_fetch.valid;
    let variable_consumed = variable_input_valid
        && if r.variable_fetch.lane {
            lane1_ready
        } else {
            lane0_ready
        };
    if variable_consumed {
        n.variable_fetch.valid = false;
    }
    if !n.variable_fetch.valid {
        let mut found = false;
        let mut selected = b6(0);
        for offset in 0..64 {
            let candidate = wrap64(r.variable_rr + b6(offset as u128));
            let status = r.status[candidate];
            if !found
                && status.used
                && status.a_ready
                && status.challenge_ready
                && !status.variable_issued
            {
                found = true;
                selected = candidate;
            }
        }
        if found && (lane0_ready || lane1_ready) {
            let lane = if lane0_ready && lane1_ready {
                r.variable_lane_rr
            } else {
                lane1_ready
            };
            n.status[selected].variable_issued = true;
            n.status[selected].variable_lane = lane;
            n.variable_fetch = VariableFetch {
                valid: true,
                context: selected,
                lane,
            };
            n.variable_rr = selected + b6(1);
            n.variable_lane_rr = !lane;
        }
    }
    if q.variable0.valid {
        let context = q.variable0.tag.resize::<6>();
        n.status[context].variable_ready = true;
        variable0_write = RamWrite::<ExtendedPoint, 6> {
            addr: context,
            value: q.variable0.point,
            enable: true,
        };
    }
    if q.variable1.valid {
        let context = q.variable1.tag.resize::<6>();
        n.status[context].variable_ready = true;
        variable1_write = RamWrite::<ExtendedPoint, 6> {
            addr: context,
            value: q.variable1.point,
            enable: true,
        };
    }

    let equation_consumed = r.equation_fetch.valid && q.equation.ready;
    if equation_consumed {
        n.equation_fetch.valid = false;
    }
    if !n.equation_fetch.valid {
        let mut found = false;
        let mut selected = b6(0);
        for offset in 0..64 {
            let candidate = wrap64(r.equation_rr + b6(offset as u128));
            let status = r.status[candidate];
            if !found
                && status.used
                && status.r_ready
                && status.fixed_ready
                && status.variable_ready
                && !status.equation_issued
            {
                found = true;
                selected = candidate;
            }
        }
        if found && q.equation.ready {
            n.status[selected].equation_issued = true;
            n.equation_fetch = Fetch {
                valid: true,
                context: selected,
            };
            n.equation_rr = selected + b6(1);
        }
    }

    if q.equation.valid {
        let context = q.equation.tag.resize::<6>();
        let status = r.status[context];
        let error = if !status.a_valid {
            b8(VERIFY_BAD_PUBLIC_KEY)
        } else if !status.r_valid {
            b8(VERIFY_BAD_R)
        } else if status.a_small {
            b8(VERIFY_SMALL_PUBLIC_KEY)
        } else if status.r_small {
            b8(VERIFY_SMALL_R)
        } else if !status.canonical_s {
            b8(VERIFY_NONCANONICAL_S)
        } else if !q.equation.equal {
            b8(VERIFY_EQUATION_FAILURE)
        } else {
            b8(VERIFY_OK)
        };
        output.valid = true;
        output.ok = error == b8(VERIFY_OK);
        output.error = error;
        output.tag = status.tag;
        n.status[context] = empty_status_kernel(false);
    }

    let hash_read = if n.hash_fetch.valid {
        n.hash_fetch.context
    } else {
        r.hash_issue.context
    };
    let variable_read = if n.variable_fetch.valid {
        n.variable_fetch.context
    } else {
        r.variable_fetch.context
    };
    let equation_read = if n.equation_fetch.valid {
        n.equation_fetch.context
    } else {
        r.equation_fetch.context
    };

    let mut d = StrictVerifyCoreD::dont_care();
    d.control = n;
    d.memory = VerifyMemoryIn {
        chain: RamIn::<Words512, 6> {
            read_addr: hash_read,
            write: chain_write,
        },
        a: RamIn::<DecodedPoint, 6> {
            read_addr: variable_read,
            write: a_write,
        },
        r: RamIn::<DecodedPoint, 6> {
            read_addr: equation_read,
            write: r_write,
        },
        fixed: RamIn::<ExtendedPoint, 6> {
            read_addr: equation_read,
            write: fixed_write,
        },
        challenge: RamIn::<ScalarWords, 6> {
            read_addr: variable_read,
            write: challenge_write,
        },
        variable0: RamIn::<ExtendedPoint, 6> {
            read_addr: equation_read,
            write: variable0_write,
        },
        variable1: RamIn::<ExtendedPoint, 6> {
            read_addr: equation_read,
            write: variable1_write,
        },
    };
    d.decode_a = PointDecodeIn {
        valid: accept,
        encoded: CompressedPoint {
            words: i.request.public_key.words,
        },
        tag: free_context.resize::<16>(),
    };
    d.decode_r = PointDecodeIn {
        valid: accept,
        encoded: request_r(i.request),
        tag: free_context.resize::<16>(),
    };
    d.fixed = MultiCombMulIn {
        valid: accept,
        scalar: request_s(i.request),
        tag: free_context.resize::<16>(),
    };
    d.sha = Sha512PoolIn {
        request0: Sha512PoolRequest {
            valid: r.hash_issue.valid,
            tag: b9(0x40) | r.hash_issue.context.resize::<9>(),
            state: r.hash_issue.state,
            block: challenge_block1(),
        },
        request1: Sha512PoolRequest {
            valid: accept,
            tag: free_context.resize::<9>(),
            state: sha_iv(),
            block: challenge_block0(i.request),
        },
    };
    d.reducer = reducer_input;
    let variable_request = VariableBaseIn {
        valid: variable_input_valid,
        point: q.memory.a.point,
        t2d: q.memory.a.t2d,
        scalar: q.memory.challenge,
        tag: r.variable_fetch.context.resize::<16>(),
    };
    d.variable0 = VariableBaseIn {
        valid: variable_request.valid && !r.variable_fetch.lane,
        ..variable_request
    };
    d.variable1 = VariableBaseIn {
        valid: variable_request.valid && r.variable_fetch.lane,
        ..variable_request
    };
    d.equation = EquationIn {
        valid: r.equation_fetch.valid,
        variable: if r.status[r.equation_fetch.context].variable_lane {
            q.memory.variable1
        } else {
            q.memory.variable0
        },
        r: q.memory.r.point,
        r_t2d: q.memory.r.t2d,
        fixed: q.memory.fixed,
        tag: r.equation_fetch.context.resize::<16>(),
    };
    (output, d)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::sha512_parallel::{Sha512Compress, Sha512CompressIn};
    use curve25519_dalek::scalar::Scalar;
    use ed25519_dalek::{Signer, SigningKey};
    use rhdl::core::sim::ResetOrData;
    use sha2::{Digest, Sha512};
    use std::iter;

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

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

    fn idle() -> StrictVerifyIn {
        StrictVerifyIn {
            valid: false,
            request: crate::protocol::zero_verify_request(),
        }
    }

    fn compress_block(state: [b64; 8], block: [b64; 16]) -> [b64; 8] {
        let idle = Sha512CompressIn {
            start: false,
            state: [b64(0); 8],
            block: [b64(0); 16],
        };
        Sha512Compress::default()
            .run(
                iter::once(idle)
                    .chain(iter::once(Sha512CompressIn {
                        start: true,
                        state,
                        block,
                    }))
                    .chain(iter::repeat_n(idle, 250))
                    .with_reset(1)
                    .clock_pos_edge(100),
            )
            .synchronous_sample()
            .map(|sample| sample.output)
            .find(|output| output.valid)
            .unwrap()
            .state
    }

    #[test]
    fn challenge_hash_and_reduction_match_dalek() {
        let seed = [0x31; 32];
        let message = [0x79; 64];
        let key = SigningKey::from_bytes(&seed);
        let signature = key.sign(&message).to_bytes();
        let request = VerifyRequest {
            message: words512(message),
            public_key: scalar_words(key.verifying_key().to_bytes()),
            signature: words512(signature),
            tag: b16(0),
        };
        let first = compress_block(sha_iv(), challenge_block0(request));
        let second = compress_block(first, challenge_block1());
        let wide = digest_words(second);
        let idle = ScalarReducePipeIn {
            valid: false,
            wide: Words512 { words: [b64(0); 8] },
            tag: b16(0),
        };
        let reduced = ScalarReducePipe::default()
            .run(
                iter::once(idle)
                    .chain(iter::once(ScalarReducePipeIn {
                        valid: true,
                        wide,
                        tag: b16(7),
                    }))
                    .chain(iter::repeat_n(idle, 100))
                    .with_reset(1)
                    .clock_pos_edge(100),
            )
            .synchronous_sample()
            .map(|sample| sample.output)
            .find(|output| output.valid)
            .unwrap();
        let mut hasher = Sha512::new();
        hasher.update(&signature[..32]);
        hasher.update(key.verifying_key().to_bytes());
        hasher.update(message);
        let digest: [u8; 64] = hasher.finalize().into();
        let expected = Scalar::from_bytes_mod_order_wide(&digest).to_bytes();
        let actual = std::array::from_fn(|index| {
            ((reduced.scalar.words[index / 8].raw() >> ((index % 8) * 8)) & 0xff) as u8
        });
        assert_eq!(actual, expected);
    }

    #[test]
    fn accepts_valid_and_rejects_modified_message() {
        std::thread::Builder::new()
            .name("strict-verify-sim".into())
            .stack_size(512 * 1024 * 1024)
            .spawn(|| {
                let seed = std::array::from_fn(|index| (index as u8).wrapping_mul(19));
                let message = std::array::from_fn(|index| (index as u8).wrapping_mul(37));
                let key = SigningKey::from_bytes(&seed);
                let signature = key.sign(&message).to_bytes();
                let mut modified = message;
                modified[17] ^= 0x80;
                let valid = StrictVerifyIn {
                    valid: true,
                    request: VerifyRequest {
                        message: words512(message),
                        public_key: scalar_words(key.verifying_key().to_bytes()),
                        signature: words512(signature),
                        tag: b16(0x101),
                    },
                };
                let invalid = StrictVerifyIn {
                    valid: true,
                    request: VerifyRequest {
                        message: words512(modified),
                        tag: b16(0x102),
                        ..valid.request
                    },
                };
                let requests = [valid, invalid];
                let mut need_reset = true;
                let mut request_index = 0usize;
                let mut result_count = 0usize;
                let outputs: Vec<_> = StrictVerifyCore::default()
                    .run_fn(
                        move |output| {
                            if result_count == requests.len() {
                                return None;
                            }
                            if need_reset {
                                need_reset = false;
                                return Some(ResetOrData::Reset);
                            }
                            if output.valid {
                                result_count += 1;
                            }
                            let mut input = idle();
                            if request_index < requests.len() && output.ready {
                                input = requests[request_index];
                                request_index += 1;
                            }
                            Some(ResetOrData::Data(input))
                        },
                        100,
                    )
                    .take_while(|sample| sample.time < 4_000_000)
                    .synchronous_sample()
                    .map(|sample| sample.output)
                    .filter(|output| output.valid)
                    .collect();
                assert_eq!(outputs.len(), 2);
                let accepted = outputs
                    .iter()
                    .find(|output| output.tag == b16(0x101))
                    .unwrap();
                assert!(
                    accepted.ok,
                    "valid signature error={}",
                    accepted.error.raw()
                );
                let rejected = outputs
                    .iter()
                    .find(|output| output.tag == b16(0x102))
                    .unwrap();
                assert!(!rejected.ok);
                assert_eq!(rejected.error, b8(VERIFY_EQUATION_FAILURE));
            })
            .unwrap()
            .join()
            .unwrap();
    }
}