genies/tri/encoding.tri

module genies.encoding

// Fq serialization: convert between Fq (16 x U32 limbs) and byte arrays.
//
// The CSIDH public key is the Montgomery coefficient A in F_q.
// Serialized as 64 bytes in little-endian order (512 bits).
//
// Each U32 limb serializes to 4 bytes in little-endian order.
// Limb l0 occupies bytes 0..3, l1 occupies bytes 4..7, ..., l15 occupies bytes 60..63.
use genies.fq
use vm.core.convert

// ---------------------------------------------------------------------------
// Byte extraction from a U32 limb
// ---------------------------------------------------------------------------

// Extract the 4 bytes of a U32 in little-endian order.
// byte0 is bits 0..7, byte1 is bits 8..15, etc.
// Uses divmod: x /% 256 gives (quotient, remainder=byte).
pub fn u32_to_bytes(x: U32) -> (U32, U32, U32, U32) {
    let mask: U32 = convert.as_u32(255)
    let d256: U32 = convert.as_u32(256)
    // byte 0 = x & 0xFF
    let (q0, b0) = x /% d256
    // byte 1 = (x >> 8) & 0xFF
    let (q1, b1) = q0 /% d256
    // byte 2 = (x >> 16) & 0xFF
    let (q2, b2) = q1 /% d256
    // byte 3 = (x >> 24) & 0xFF (= q2, which fits in a byte)
    let b3: U32 = q2
    (b0, b1, b2, b3)
}

// Reconstruct a U32 from 4 little-endian bytes.
pub fn bytes_to_u32(b0: U32, b1: U32, b2: U32, b3: U32) -> U32 {
    // x = b0 + b1*256 + b2*65536 + b3*16777216
    let f0: Field = convert.as_field(b0)
    let f1: Field = convert.as_field(b1) * convert.as_field(convert.as_u32(256))
    let f2: Field = convert.as_field(b2) * convert.as_field(convert.as_u32(65536))
    let f3: Field = convert.as_field(b3) * convert.as_field(convert.as_u32(16777216))
    let result_f: Field = f0 + f1 + f2 + f3
    convert.as_u32(result_f)
}

// ---------------------------------------------------------------------------
// Fq to 64 bytes (little-endian)
// ---------------------------------------------------------------------------

// A 64-byte array for serialized Fq values.
// Since Trident has no arrays, we use a struct with 64 named U32 fields,
// each holding one byte value (0..255).
pub struct FqBytes {
    b0: U32, b1: U32, b2: U32, b3: U32,
    b4: U32, b5: U32, b6: U32, b7: U32,
    b8: U32, b9: U32, b10: U32, b11: U32,
    b12: U32, b13: U32, b14: U32, b15: U32,
    b16: U32, b17: U32, b18: U32, b19: U32,
    b20: U32, b21: U32, b22: U32, b23: U32,
    b24: U32, b25: U32, b26: U32, b27: U32,
    b28: U32, b29: U32, b30: U32, b31: U32,
    b32: U32, b33: U32, b34: U32, b35: U32,
    b36: U32, b37: U32, b38: U32, b39: U32,
    b40: U32, b41: U32, b42: U32, b43: U32,
    b44: U32, b45: U32, b46: U32, b47: U32,
    b48: U32, b49: U32, b50: U32, b51: U32,
    b52: U32, b53: U32, b54: U32, b55: U32,
    b56: U32, b57: U32, b58: U32, b59: U32,
    b60: U32, b61: U32, b62: U32, b63: U32,
}

// Serialize an Fq element to 64 little-endian bytes.
pub fn fq_to_bytes(x: fq.Fq) -> FqBytes {
    let (b0, b1, b2, b3) = u32_to_bytes(x.l0)
    let (b4, b5, b6, b7) = u32_to_bytes(x.l1)
    let (b8, b9, b10, b11) = u32_to_bytes(x.l2)
    let (b12, b13, b14, b15) = u32_to_bytes(x.l3)
    let (b16, b17, b18, b19) = u32_to_bytes(x.l4)
    let (b20, b21, b22, b23) = u32_to_bytes(x.l5)
    let (b24, b25, b26, b27) = u32_to_bytes(x.l6)
    let (b28, b29, b30, b31) = u32_to_bytes(x.l7)
    let (b32, b33, b34, b35) = u32_to_bytes(x.l8)
    let (b36, b37, b38, b39) = u32_to_bytes(x.l9)
    let (b40, b41, b42, b43) = u32_to_bytes(x.l10)
    let (b44, b45, b46, b47) = u32_to_bytes(x.l11)
    let (b48, b49, b50, b51) = u32_to_bytes(x.l12)
    let (b52, b53, b54, b55) = u32_to_bytes(x.l13)
    let (b56, b57, b58, b59) = u32_to_bytes(x.l14)
    let (b60, b61, b62, b63) = u32_to_bytes(x.l15)
    FqBytes {
        b0: b0, b1: b1, b2: b2, b3: b3,
        b4: b4, b5: b5, b6: b6, b7: b7,
        b8: b8, b9: b9, b10: b10, b11: b11,
        b12: b12, b13: b13, b14: b14, b15: b15,
        b16: b16, b17: b17, b18: b18, b19: b19,
        b20: b20, b21: b21, b22: b22, b23: b23,
        b24: b24, b25: b25, b26: b26, b27: b27,
        b28: b28, b29: b29, b30: b30, b31: b31,
        b32: b32, b33: b33, b34: b34, b35: b35,
        b36: b36, b37: b37, b38: b38, b39: b39,
        b40: b40, b41: b41, b42: b42, b43: b43,
        b44: b44, b45: b45, b46: b46, b47: b47,
        b48: b48, b49: b49, b50: b50, b51: b51,
        b52: b52, b53: b53, b54: b54, b55: b55,
        b56: b56, b57: b57, b58: b58, b59: b59,
        b60: b60, b61: b61, b62: b62, b63: b63,
    }
}

// Deserialize 64 little-endian bytes to an Fq element.
pub fn bytes_to_fq(bs: FqBytes) -> fq.Fq {
    let l0: U32 = bytes_to_u32(bs.b0, bs.b1, bs.b2, bs.b3)
    let l1: U32 = bytes_to_u32(bs.b4, bs.b5, bs.b6, bs.b7)
    let l2: U32 = bytes_to_u32(bs.b8, bs.b9, bs.b10, bs.b11)
    let l3: U32 = bytes_to_u32(bs.b12, bs.b13, bs.b14, bs.b15)
    let l4: U32 = bytes_to_u32(bs.b16, bs.b17, bs.b18, bs.b19)
    let l5: U32 = bytes_to_u32(bs.b20, bs.b21, bs.b22, bs.b23)
    let l6: U32 = bytes_to_u32(bs.b24, bs.b25, bs.b26, bs.b27)
    let l7: U32 = bytes_to_u32(bs.b28, bs.b29, bs.b30, bs.b31)
    let l8: U32 = bytes_to_u32(bs.b32, bs.b33, bs.b34, bs.b35)
    let l9: U32 = bytes_to_u32(bs.b36, bs.b37, bs.b38, bs.b39)
    let l10: U32 = bytes_to_u32(bs.b40, bs.b41, bs.b42, bs.b43)
    let l11: U32 = bytes_to_u32(bs.b44, bs.b45, bs.b46, bs.b47)
    let l12: U32 = bytes_to_u32(bs.b48, bs.b49, bs.b50, bs.b51)
    let l13: U32 = bytes_to_u32(bs.b52, bs.b53, bs.b54, bs.b55)
    let l14: U32 = bytes_to_u32(bs.b56, bs.b57, bs.b58, bs.b59)
    let l15: U32 = bytes_to_u32(bs.b60, bs.b61, bs.b62, bs.b63)
    let result: fq.Fq = fq.Fq {
        l0: l0, l1: l1, l2: l2, l3: l3,
        l4: l4, l5: l5, l6: l6, l7: l7,
        l8: l8, l9: l9, l10: l10, l11: l11,
        l12: l12, l13: l13, l14: l14, l15: l15,
    }
    // Validate: result must be < q
    // The prover ensures this; the circuit verifies via fq_lt.
    result
}

// ---------------------------------------------------------------------------
// Public key encoding
// ---------------------------------------------------------------------------

// Encode a CSIDH public key (Montgomery coefficient A) to bytes.
pub fn encode_pubkey(c: fq.Fq) -> FqBytes {
    fq_to_bytes(c)
}

// Decode a CSIDH public key from bytes.
pub fn decode_pubkey(bs: FqBytes) -> fq.Fq {
    bytes_to_fq(bs)
}