arcis-compiler 0.9.6

use crate::{
    core::{
        bounds::FieldBounds,
        circuits::{
            boolean::{boolean_value::BooleanValue, byte::Byte, sha3::SHA3_512},
            traits::{arithmetic_circuit::ArithmeticCircuit, boolean_circuit::BooleanCircuit},
        },
        expressions::{
            expr::{EvalFailure, Expr},
            other_expr::OtherExpr,
        },
        global_value::{curve_value::CurveValue, value::FieldValue},
        mxe_input::{MxeFieldInput, MxeInput, MxeScalarInput},
    },
    traits::{FromLeBits, GetBit, Random, Reveal, Select, ToLeBytes},
    utils::{
        crypto::key::{
            ED25519_SECRET_KEY_COUNT,
            ED25519_SIGNING_KEY_HASH_PREFIX_COUNT,
            MXE_ED25519_SECRET_KEY,
        },
        elliptic_curve::AffineEdwardsPoint,
        field::{BaseField, ScalarField},
    },
};
use ed25519_dalek::{
    hazmat::{raw_sign, raw_verify, ExpandedSecretKey},
    Signature,
    VerifyingKey,
};
use ff::{Field, PrimeField};
use sha3::{Digest, Sha3_512};

#[derive(Clone, Copy)]
pub struct Ed25519SecretKey([Byte<BooleanValue>; 32]);

impl Ed25519SecretKey {
    pub fn new_from_inner(a: [Byte<BooleanValue>; 32]) -> Self {
        Self(a)
    }

    pub fn inner(&self) -> [Byte<BooleanValue>; 32] {
        self.0
    }

    /// Loads the MXE ed25519 secret key.
    #[allow(dead_code)]
    pub fn mxe_secret_key() -> Self {
        Self(
            (0..ED25519_SECRET_KEY_COUNT)
                .map(BooleanValue::ed25519_secret_key)
                .collect::<Vec<BooleanValue>>()
                .chunks(8)
                .map(|chunk| {
                    Byte::new(
                        chunk
                            .to_vec()
                            .try_into()
                            .unwrap_or_else(|v: Vec<BooleanValue>| {
                                panic!("Expected a Vec of length 8 (found {})", v.len())
                            }),
                    )
                })
                .collect::<Vec<Byte<BooleanValue>>>()
                .try_into()
                .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!(
                        "Expected a Vec of length {} (found {})",
                        ED25519_SECRET_KEY_COUNT / 8,
                        v.len()
                    )
                }),
        )
    }

    #[allow(dead_code)]
    pub fn compress(&self) -> [FieldValue<BaseField>; 2] {
        self.0
            .chunks(16)
            .map(|bytes| {
                FieldValue::<BaseField>::from_le_bits(
                    bytes
                        .iter()
                        .flat_map(|byte| byte.to_vec())
                        .collect::<Vec<BooleanValue>>(),
                    false,
                )
            })
            .collect::<Vec<FieldValue<BaseField>>>()
            .try_into()
            .unwrap_or_else(|v: Vec<FieldValue<BaseField>>| {
                panic!("Expected a Vec of length 2 (found {})", v.len())
            })
    }
}

impl Random for Ed25519SecretKey {
    fn random() -> Self {
        Self(
            (0..32)
                .map(|_| Byte::random())
                .collect::<Vec<Byte<BooleanValue>>>()
                .try_into()
                .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!("Expected a Vec of length 32 (found {})", v.len())
                }),
        )
    }
}

/// Encodes an affine point on Edwards25519 to an array of 32 bytes, as specified in
/// <https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.2>.
#[allow(non_snake_case, dead_code)]
fn encode(P: AffineEdwardsPoint<FieldValue<BaseField>>) -> [Byte<BooleanValue>; 32] {
    let (x, y) = P.inner();
    let mut P_encoded = (0..BaseField::NUM_BITS)
        .map(|i| y.get_bit(i as usize, false))
        .collect::<Vec<BooleanValue>>();
    P_encoded.push(x.get_bit(0, false));
    P_encoded
        .chunks(8)
        .map(|chunk| {
            Byte::new(
                chunk
                    .to_vec()
                    .try_into()
                    .unwrap_or_else(|v: Vec<BooleanValue>| {
                        panic!("Expected a Vec of length 8 (found {})", v.len())
                    }),
            )
        })
        .collect::<Vec<Byte<BooleanValue>>>()
        .try_into()
        .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
            panic!("Expected a Vec of length 32 (found {})", v.len())
        })
}

/// Decodes a 32-byte encoding of an affine point on Edwards25519, as specified in
/// <https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.3>.
#[allow(non_snake_case, dead_code)]
fn decode(P: [Byte<BooleanValue>; 32]) -> AffineEdwardsPoint<FieldValue<BaseField>> {
    let mut y_bits = P
        .into_iter()
        .flat_map(|byte| byte.to_vec())
        .collect::<Vec<BooleanValue>>();
    let x_lsb_expected = y_bits.pop().unwrap();
    // the nodes have verified that y_bits represents a number less than 2^255-19
    let y = FieldValue::<BaseField>::from_le_bits(y_bits, false);
    let (_, point) = AffineEdwardsPoint::try_from_y(y);
    let x_lsb = point.x.get_bit(0, false);
    let x = (x_lsb ^ x_lsb_expected).select(-point.x, point.x);
    // we don't know is_on_curve and is_ell_torsion at compile time
    AffineEdwardsPoint::new((x, y), false, false)
}

#[derive(Clone, Copy, Debug)]
#[allow(non_snake_case, dead_code)]
pub struct Ed25519Signature {
    pub R_encoded: [Byte<BooleanValue>; 32],
    pub S: [Byte<BooleanValue>; 32],
}

#[allow(non_snake_case, dead_code)]
impl Ed25519Signature {
    pub fn new(R_encoded: [Byte<BooleanValue>; 32], S: [Byte<BooleanValue>; 32]) -> Self {
        Self { R_encoded, S }
    }

    pub fn from_bytes(bytes: [Byte<BooleanValue>; 64]) -> Self {
        let mut R_encoded = bytes.to_vec();
        let S = R_encoded.split_off(32);
        Self::new(
            R_encoded
                .try_into()
                .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!("Expected a Vec of length 32 (found {})", v.len())
                }),
            S.try_into().unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                panic!("Expected a Vec of length 32 (found {})", v.len())
            }),
        )
    }

    pub fn to_bytes(self) -> [Byte<BooleanValue>; 64] {
        let mut bytes = self.R_encoded.to_vec();
        bytes.append(&mut self.S.to_vec());
        bytes
            .try_into()
            .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                panic!("Expected a Vec of length 64 (found {})", v.len())
            })
    }

    pub fn to_vec(self) -> Vec<Byte<BooleanValue>> {
        self.to_bytes().to_vec()
    }
}

// It is important that the verifying key is part of the signing key to avoid/limit
// possible surface for the attack described [here](https://arxiv.org/pdf/2308.15009).
#[derive(Clone)]
#[allow(dead_code)]
pub struct Ed25519SigningKey {
    // s, following 3. of https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.5
    pub(crate) s: FieldValue<ScalarField>,
    // prefix, following 1. of https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.6
    pub(crate) hash_prefix: [Byte<BooleanValue>; 32],
    pub(crate) verifying_key: Ed25519VerifyingKey,
}

impl Ed25519SigningKey {
    pub fn new(
        s: FieldValue<ScalarField>,
        hash_prefix: [Byte<BooleanValue>; 32],
        verifying_key: Ed25519VerifyingKey,
    ) -> Self {
        Self {
            s,
            hash_prefix,
            verifying_key,
        }
    }

    /// Loads the MXE ed25519 signing key.
    pub fn mxe_signing_key() -> Self {
        Self {
            s: FieldValue::<ScalarField>::from_expr(Expr::Other(OtherExpr::MxeKey(
                MxeInput::ScalarOnly(MxeScalarInput::Ed25519SigningKeyS()),
            ))),
            hash_prefix: (0..ED25519_SIGNING_KEY_HASH_PREFIX_COUNT)
                .map(BooleanValue::ed25519_signing_key_hash_prefix)
                .collect::<Vec<BooleanValue>>()
                .chunks(8)
                .map(|chunk| {
                    Byte::new(
                        chunk
                            .to_vec()
                            .try_into()
                            .unwrap_or_else(|v: Vec<BooleanValue>| {
                                panic!("Expected a Vec of length 8 (found {})", v.len())
                            }),
                    )
                })
                .collect::<Vec<Byte<BooleanValue>>>()
                .try_into()
                .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!(
                        "Expected a Vec of length {} (found {})",
                        ED25519_SIGNING_KEY_HASH_PREFIX_COUNT / 8,
                        v.len()
                    )
                }),
            verifying_key: Ed25519VerifyingKey::new_from_public_key_encoded(
                (0..32)
                    .map(|i| {
                        Byte::from(FieldValue::<BaseField>::from_expr(Expr::Other(
                            OtherExpr::MxeKey(MxeInput::Base(MxeFieldInput::Ed25519VerifyingKey(
                                i,
                            ))),
                        )))
                    })
                    .collect::<Vec<Byte<BooleanValue>>>()
                    .try_into()
                    .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                        panic!("Expected a Vec of length 32 (found {})", v.len())
                    }),
            ),
        }
    }

    #[allow(non_snake_case)]
    pub fn sign(&self, message: Vec<Byte<BooleanValue>>) -> Ed25519Signature {
        let hasher = SHA3_512::new();
        let mut prefix_vec = self.hash_prefix.to_vec();
        prefix_vec.extend(message.iter());
        let r = FieldValue::<ScalarField>::from_le_bits(
            hasher
                .digest(prefix_vec.to_vec())
                .into_iter()
                .flat_map(|byte| byte.to_vec())
                .collect::<Vec<BooleanValue>>(),
            false,
        );
        let R = (r * CurveValue::generator()).to_affine();
        let R_encoded = encode(R);
        let mut R_encoded_vec = R_encoded.to_vec();
        R_encoded_vec.extend(self.verifying_key.public_key_encoded.iter());
        R_encoded_vec.extend(message.iter());
        let k = FieldValue::<ScalarField>::from_le_bits(
            hasher
                .digest(R_encoded_vec)
                .into_iter()
                .flat_map(|byte| byte.to_vec())
                .collect::<Vec<BooleanValue>>(),
            false,
        );
        let S = r + k * self.s;

        Ed25519Signature::new(R_encoded, S.to_le_bytes())
    }
}

impl From<Ed25519SecretKey> for Ed25519SigningKey {
    /// This function hashes the secret key (consisting of 32 random bytes) using sha3-512.
    /// This results in the 64-byte digest h. The lower 32 bytes of h are transformed using the
    /// 'clamping rule' to derive the first return value s, an array of length 251 of
    /// BooleanValues. The second return value are the higher 32 bytes of h.
    /// The third return value is the public key given by the affine point G.mul_clamped(s),
    /// where G is the fixed generator of prime order ell.
    /// The fourth return value is the 32-byte encoding of the public key.
    #[allow(non_snake_case)]
    fn from(value: Ed25519SecretKey) -> Self {
        let hasher = SHA3_512::new();
        let mut h_lo = hasher.digest(value.inner().to_vec()).to_vec();
        let h_hi: [Byte<BooleanValue>; 32] =
            h_lo.split_off(32)
                .try_into()
                .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!("Expected a Vec of length 32 (found {})", v.len())
                });
        let mut s_bits = vec![BooleanValue::from(false); 3];
        s_bits.extend(
            h_lo.into_iter()
                .flat_map(|byte| byte.to_vec())
                .collect::<Vec<BooleanValue>>()[3..254]
                .to_vec(),
        );
        s_bits.push(BooleanValue::from(true));
        let s = FieldValue::<ScalarField>::from_le_bits(s_bits, false);
        let public_key = (s * CurveValue::generator()).to_affine();

        Ed25519SigningKey::new(
            s,
            h_hi,
            Ed25519VerifyingKey::new_from_public_key(public_key),
        )
    }
}

#[derive(Clone, Debug)]
pub struct Ed25519VerifyingKeyFromSecretKey;

impl ArithmeticCircuit<BaseField> for Ed25519VerifyingKeyFromSecretKey {
    fn eval(&self, x: Vec<BaseField>) -> Result<Vec<BaseField>, EvalFailure> {
        assert!(x.len() == 32);
        // all inputs are expected to be bytes
        x.iter()
            .for_each(|byte| assert!(*byte <= BaseField::from(255)));
        let secret_key = x
            .into_iter()
            .map(|val| val.to_le_bytes()[0])
            .collect::<Vec<u8>>();
        let h = Sha3_512::default().chain_update(secret_key).finalize();
        let esk = ExpandedSecretKey::from_bytes(&h.into());
        let verifying_key = VerifyingKey::from(&esk);
        Ok(verifying_key
            .to_bytes()
            .into_iter()
            .map(|byte| BaseField::from(byte as u64))
            .collect::<Vec<BaseField>>())
    }

    fn bounds(&self, _bounds: Vec<FieldBounds<BaseField>>) -> Vec<FieldBounds<BaseField>> {
        vec![FieldBounds::new(BaseField::ZERO, BaseField::from(255)); 32]
    }

    fn run(&self, vals: Vec<FieldValue<BaseField>>) -> Vec<FieldValue<BaseField>> {
        let secret_key = Ed25519SecretKey::new_from_inner(
            vals.into_iter()
                .map(Byte::from)
                .collect::<Vec<Byte<BooleanValue>>>()
                .try_into()
                .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!("Expected a Vec of length 32 (found {})", v.len())
                }),
        );
        let signing_key = Ed25519SigningKey::from(secret_key);
        signing_key
            .verifying_key
            .public_key_encoded
            .into_iter()
            .map(FieldValue::<BaseField>::from)
            .collect::<Vec<FieldValue<BaseField>>>()
    }
}

#[derive(Clone, Debug)]
pub struct Ed25519Sign;

// This is the circuit we want to expose on the interpreter.
impl ArithmeticCircuit<BaseField> for Ed25519Sign {
    fn eval(&self, x: Vec<BaseField>) -> Result<Vec<BaseField>, EvalFailure> {
        // all inputs are expected to be bytes
        x.iter()
            .for_each(|byte| assert!(*byte <= BaseField::from(255)));
        // the first 32 bytes are for the secret key and the remaining bytes are for the message
        assert!(x.len() >= 32);
        let mut secret_key = x
            .into_iter()
            .map(|val| val.to_le_bytes()[0])
            .collect::<Vec<u8>>();
        let message = secret_key.split_off(32);
        let h = Sha3_512::default().chain_update(secret_key).finalize();

        let esk = ExpandedSecretKey::from_bytes(&h.into());
        let verifying_key = VerifyingKey::from(&esk);
        let signature = raw_sign::<Sha3_512>(&esk, &message, &verifying_key);

        Ok(signature
            .to_vec()
            .into_iter()
            .map(|byte| BaseField::from(byte as u64))
            .collect::<Vec<BaseField>>())
    }

    fn bounds(&self, _bounds: Vec<FieldBounds<BaseField>>) -> Vec<FieldBounds<BaseField>> {
        vec![FieldBounds::new(BaseField::ZERO, BaseField::from(255)); 64]
    }

    fn run(&self, vals: Vec<FieldValue<BaseField>>) -> Vec<FieldValue<BaseField>> {
        let mut secret_key = vals
            .into_iter()
            .map(Byte::from)
            .collect::<Vec<Byte<BooleanValue>>>();
        let message = secret_key.split_off(32);
        let secret_key = Ed25519SecretKey::new_from_inner(secret_key.try_into().unwrap_or_else(
            |v: Vec<Byte<BooleanValue>>| panic!("Expected a Vec of length 32 (found {})", v.len()),
        ));

        let signing_key = Ed25519SigningKey::from(secret_key);
        let signature = signing_key.sign(message);

        signature
            .to_vec()
            .into_iter()
            .map(FieldValue::<BaseField>::from)
            .collect::<Vec<FieldValue<BaseField>>>()
    }
}

// This is the circuit we want to test.
impl BooleanCircuit for Ed25519Sign {
    fn eval(&self, x: Vec<bool>) -> Result<Vec<bool>, EvalFailure> {
        let x_byte = x
            .chunks(8)
            .map(|bits| {
                BaseField::from(u8::from(Byte::new(bits.to_vec().try_into().unwrap_or_else(
                    |v: Vec<bool>| panic!("Expected a Vec of length 8 (found {})", v.len()),
                ))) as u64)
            })
            .collect::<Vec<BaseField>>();
        let res = ArithmeticCircuit::eval(self, x_byte)?;
        Ok(res
            .into_iter()
            .flat_map(|byte| Byte::from(byte.to_le_bytes()[0]).to_vec())
            .collect::<Vec<bool>>())
    }

    fn run(&self, vals: Vec<BooleanValue>) -> Vec<BooleanValue> {
        let vals_byte = vals
            .chunks(8)
            .map(|bits| {
                FieldValue::from(Byte::new(bits.to_vec().try_into().unwrap_or_else(
                    |v: Vec<BooleanValue>| panic!("Expected a Vec of length 8 (found {})", v.len()),
                )))
            })
            .collect::<Vec<FieldValue<BaseField>>>();
        let res = ArithmeticCircuit::run(self, vals_byte);
        res.into_iter()
            .flat_map(|byte| byte.to_le_bytes()[0].to_vec())
            .collect::<Vec<BooleanValue>>()
    }
}

#[derive(Clone, Debug)]
pub struct Ed25519MXESign;

// This is the circuit we want to expose on the interpreter.
impl ArithmeticCircuit<BaseField> for Ed25519MXESign {
    fn eval(&self, x: Vec<BaseField>) -> Result<Vec<BaseField>, EvalFailure> {
        // all inputs are expected to be bytes
        x.iter()
            .for_each(|byte| assert!(*byte <= BaseField::from(255)));
        let message = x
            .into_iter()
            .map(|val| val.to_le_bytes()[0])
            .collect::<Vec<u8>>();

        let h = Sha3_512::default()
            .chain_update(MXE_ED25519_SECRET_KEY)
            .finalize();
        let esk = ExpandedSecretKey::from_bytes(&h.into());
        let verifying_key = VerifyingKey::from(&esk);
        let signature = raw_sign::<Sha3_512>(&esk, &message, &verifying_key);

        Ok(signature
            .to_vec()
            .into_iter()
            .map(|byte| BaseField::from(byte as u64))
            .collect::<Vec<BaseField>>())
    }

    fn bounds(&self, _bounds: Vec<FieldBounds<BaseField>>) -> Vec<FieldBounds<BaseField>> {
        vec![FieldBounds::new(BaseField::ZERO, BaseField::from(255)); 64]
    }

    fn run(&self, vals: Vec<FieldValue<BaseField>>) -> Vec<FieldValue<BaseField>> {
        let message = vals
            .into_iter()
            .map(Byte::from)
            .collect::<Vec<Byte<BooleanValue>>>();
        let mxe_signing_key = Ed25519SigningKey::mxe_signing_key();
        let signature = mxe_signing_key.sign(message);

        signature
            .to_vec()
            .into_iter()
            .map(FieldValue::<BaseField>::from)
            .collect::<Vec<FieldValue<BaseField>>>()
    }
}

/// The Arcis ed25519 verifying key type.
/// A verifying key is not necessarily public.
#[derive(Clone, Copy, Debug)]
pub struct Ed25519VerifyingKey {
    pub(crate) public_key: AffineEdwardsPoint<FieldValue<BaseField>>,
    // the encoding of public_key, following https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.2
    pub(crate) public_key_encoded: [Byte<BooleanValue>; 32],
}

#[allow(dead_code)]
impl Ed25519VerifyingKey {
    pub fn new_from_public_key(public_key: AffineEdwardsPoint<FieldValue<BaseField>>) -> Self {
        Self {
            public_key,
            public_key_encoded: encode(public_key),
        }
    }

    pub fn new_from_public_key_encoded(public_key_encoded: [Byte<BooleanValue>; 32]) -> Self {
        Self {
            public_key: decode(public_key_encoded),
            public_key_encoded,
        }
    }

    #[allow(non_snake_case)]
    pub fn verify(
        &self,
        message: Vec<Byte<BooleanValue>>,
        signature: Ed25519Signature,
    ) -> BooleanValue {
        let hasher = SHA3_512::new();
        let R_encoded = signature.R_encoded;
        let R = decode(R_encoded);
        let mut R_encoded_vec = R_encoded.to_vec();
        R_encoded_vec.extend(self.public_key_encoded.iter());
        R_encoded_vec.extend(message.iter());
        let k = FieldValue::<ScalarField>::from_le_bits(
            hasher
                .digest(R_encoded_vec)
                .into_iter()
                .flat_map(|byte| byte.to_vec())
                .collect::<Vec<BooleanValue>>(),
            false,
        );
        // the nodes have verified that signature.S represents a number less than ell (the three
        // most significant bits are 0)
        let S = FieldValue::<ScalarField>::from_le_bits(
            signature
                .S
                .into_iter()
                .flat_map(|byte| byte.to_vec())
                .take(253)
                .collect::<Vec<BooleanValue>>(),
            false,
        );
        let lhs = S * CurveValue::generator() - CurveValue::from_affine(R);
        let rhs = k * CurveValue::from_affine(self.public_key);

        (lhs - rhs).is_identity()
    }
}

impl Reveal for Ed25519VerifyingKey {
    fn reveal(self) -> Self {
        Self {
            public_key: self.public_key.reveal(),
            public_key_encoded: self.public_key_encoded.map(|byte| byte.reveal()),
        }
    }
}

#[derive(Clone, Debug)]
pub struct Ed25519Verify;

impl ArithmeticCircuit<BaseField> for Ed25519Verify {
    fn eval(&self, x: Vec<BaseField>) -> Result<Vec<BaseField>, EvalFailure> {
        // all inputs are expected to be bytes
        x.iter()
            .for_each(|byte| assert!(*byte <= BaseField::from(255)));
        // the first 32 bytes are for the (encoded) verifying key and 64 last bytes are for the
        // signature; the remaining bytes are for the message
        assert!(x.len() >= 96);
        let mut public_key_encoded_bytes = x
            .into_iter()
            .map(|val| val.to_le_bytes()[0])
            .collect::<Vec<u8>>();
        let mut message = public_key_encoded_bytes.split_off(32);
        let len = message.len();
        let signature_bytes = message.split_off(len - 64);
        let verifying_key =
            VerifyingKey::from_bytes(&public_key_encoded_bytes.try_into().unwrap_or_else(
                |v: Vec<u8>| panic!("Expected a Vec of length 32 (found {})", v.len()),
            ))
            .unwrap();
        let signature =
            Signature::from_bytes(&signature_bytes.try_into().unwrap_or_else(|v: Vec<u8>| {
                panic!("Expected a Vec of length 64 (found {})", v.len())
            }));
        let is_valid = raw_verify::<Sha3_512>(&verifying_key, &message, &signature);

        Ok(vec![BaseField::from(is_valid.is_ok())])
    }

    fn bounds(&self, _bounds: Vec<FieldBounds<BaseField>>) -> Vec<FieldBounds<BaseField>> {
        vec![FieldBounds::new(BaseField::ZERO, BaseField::ONE)]
    }

    fn run(&self, vals: Vec<FieldValue<BaseField>>) -> Vec<FieldValue<BaseField>> {
        let mut public_key_encoded_bytes = vals
            .into_iter()
            .map(Byte::from)
            .collect::<Vec<Byte<BooleanValue>>>();
        let mut message = public_key_encoded_bytes.split_off(32);
        let len = message.len();
        let signature_bytes = message.split_off(len - 64);
        let verifying_key = Ed25519VerifyingKey::new_from_public_key_encoded(
            public_key_encoded_bytes
                .try_into()
                .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!("Expected a Vec of length 32 (found {})", v.len())
                }),
        );
        let signature = Ed25519Signature::from_bytes(signature_bytes.try_into().unwrap_or_else(
            |v: Vec<Byte<BooleanValue>>| panic!("Expected a Vec of length 64 (found {})", v.len()),
        ));
        let is_valid = verifying_key.verify(message, signature);

        vec![FieldValue::<BaseField>::from(is_valid)]
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::core::{
        circuits::traits::{
            arithmetic_circuit::tests::TestedArithmeticCircuit,
            boolean_circuit::tests::TestedBooleanCircuit,
        },
        expressions::{
            bit_expr::{BitExpr, BitInputInfo},
            domain::Domain,
            expr::EvalValue,
            InputKind,
        },
        global_value::global_expr_store::with_local_expr_store_as_global,
        ir_builder::{ExprStore, IRBuilder},
    };
    use ed25519_dalek::VerifyingKey;
    use rand::Rng;
    use sha3::Sha3_512;
    use std::rc::Rc;

    impl TestedArithmeticCircuit<BaseField> for Ed25519MXESign {
        fn gen_desc<R: Rng + ?Sized>(_rng: &mut R) -> Self {
            Self
        }

        fn gen_n_inputs<R: Rng + ?Sized>(&self, rng: &mut R) -> usize {
            let mut message_len = 4;
            while rng.gen_bool(0.75) {
                message_len += 3 * 8;
            }
            message_len
        }

        fn gen_input_bounds<R: Rng + ?Sized>(_rng: &mut R) -> FieldBounds<BaseField> {
            FieldBounds::new(BaseField::ZERO, BaseField::from(255))
        }
    }

    #[test]
    fn test_mxe_sign() {
        Ed25519MXESign::test(1, 1)
    }

    impl TestedBooleanCircuit for Ed25519Sign {
        fn gen_desc<R: Rng + ?Sized>(_rng: &mut R) -> Self {
            Self
        }

        fn gen_n_inputs<R: Rng + ?Sized>(&self, rng: &mut R) -> usize {
            // the first 256 bits are the 32-byte long secret key
            // the remaining bytes are for the message
            let mut bits_len = 256 + 12 * 8;
            while rng.gen_bool(0.75) {
                bits_len += 3 * 8;
            }
            bits_len
        }
    }

    #[test]
    fn test_sign() {
        Ed25519Sign::test(1, 1)
    }

    #[test]
    #[allow(non_snake_case)]
    fn test_verify() {
        let rng = &mut crate::utils::test_rng::get();
        // the first 32 bytes are for the secret key and the remaining bytes are for the message
        let mut byte_len = 32 + 12;
        while rng.gen_bool(0.75) {
            byte_len += 3;
        }

        // generate random bits
        let mut secret_key_bits = (0..8 * byte_len)
            .map(|_| rng.gen_bool(0.5))
            .collect::<Vec<bool>>();
        let mut message_bits = secret_key_bits.split_off(256);

        let secret_key = secret_key_bits
            .chunks(8)
            .map(|chunk| {
                u8::from(Byte::new(chunk.to_vec().try_into().unwrap_or_else(
                    |v: Vec<bool>| panic!("Expected a Vec of length 8 (found {})", v.len()),
                )))
            })
            .collect::<Vec<u8>>();
        let message = message_bits
            .chunks(8)
            .map(|chunk| {
                u8::from(Byte::new(chunk.to_vec().try_into().unwrap_or_else(
                    |v: Vec<bool>| panic!("Expected a Vec of length 8 (found {})", v.len()),
                )))
            })
            .collect::<Vec<u8>>();
        let h = Sha3_512::default().chain_update(secret_key).finalize();

        // generate a valid signature of the message
        let esk = ExpandedSecretKey::from_bytes(&h.into());
        let verifying_key = VerifyingKey::from(&esk);
        let signature = raw_sign::<Sha3_512>(&esk, &message, &verifying_key);

        // run the MPC circuit on the ids of the values
        fn run(input_ids: Vec<usize>) -> Vec<usize> {
            let mut secret_key = input_ids
                .chunks(8)
                .map(|chunk| {
                    Byte::new(
                        chunk
                            .iter()
                            .copied()
                            .map(BooleanValue::new)
                            .collect::<Vec<BooleanValue>>()
                            .try_into()
                            .unwrap_or_else(|v: Vec<BooleanValue>| {
                                panic!("Expected a Vec of length 8 (found {})", v.len())
                            }),
                    )
                })
                .collect::<Vec<Byte<BooleanValue>>>();
            let mut message = secret_key.split_off(32);
            let len = message.len();
            let mut R_encoded = message.split_off(len - 64);
            let S = R_encoded.split_off(32);
            let verifying_key = Ed25519SigningKey::from(Ed25519SecretKey::new_from_inner(
                secret_key
                    .try_into()
                    .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                        panic!("Expected a Vec of length 32 (found {})", v.len())
                    }),
            ))
            .verifying_key;
            let signature = Ed25519Signature::new(
                R_encoded
                    .try_into()
                    .unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                        panic!("Expected a Vec of length 32 (found {})", v.len())
                    }),
                S.try_into().unwrap_or_else(|v: Vec<Byte<BooleanValue>>| {
                    panic!("Expected a Vec of length 32 (found {})", v.len())
                }),
            );
            let verification = verifying_key.verify(message, signature);
            vec![verification.get_id()]
        }

        // prepare the MPC run
        let mut inputs = secret_key_bits;
        // We want to test that the MPC circuit correctly verifies the validity of a signature.
        // To make the above generated signature invalid it suffices to change one single bit
        // of the message.
        let is_valid_signature = rng.gen_bool(0.5);
        if !is_valid_signature {
            message_bits[0] = !message_bits[0];
        }
        inputs.append(&mut message_bits);
        inputs.append(
            &mut signature
                .r_bytes()
                .iter()
                .flat_map(|byte| Byte::from(*byte).to_vec())
                .collect::<Vec<bool>>(),
        );
        inputs.append(
            &mut signature
                .s_bytes()
                .iter()
                .flat_map(|byte| Byte::from(*byte).to_vec())
                .collect::<Vec<bool>>(),
        );
        let inputs_len = inputs.len();
        let mut inputs_map = inputs.into_iter().map(EvalValue::Bit).enumerate().collect();

        let mut expr_store = IRBuilder::new(true);
        let input_ids = (0..inputs_len)
            .map(|i| {
                <IRBuilder as ExprStore<BaseField>>::push_bit(
                    &mut expr_store,
                    BitExpr::Input(
                        i,
                        Rc::new(BitInputInfo {
                            kind: InputKind::Secret,
                            ..BitInputInfo::default()
                        }),
                    ),
                )
            })
            .collect::<Vec<usize>>();
        let outputs = with_local_expr_store_as_global(|| run(input_ids.clone()), &mut expr_store);

        let ir = expr_store.into_ir(outputs);
        let result = ir
            .eval(rng, &mut inputs_map)
            .map(|x| x.into_iter().map(bool::unwrap).collect::<Vec<bool>>())
            .unwrap();
        assert_eq!(result[0], is_valid_signature);
    }
}