Documentation

use hekate_core::errors;
use hekate_gadgets::IntArithmeticChiplet;
use hekate_math::{Block128, TowerField};
use hekate_program::FixedShape;
use hekate_program::chiplet::ChipletDef;
use hekate_program::circuit::{Circuit, CircuitProgram, Col};
use hekate_program::define_columns;

type F = Block128;

define_columns! {
    ProgColumns {
        VAL_A: B32,
        VAL_B: B32,
        VAL_RES: B32,
        OPCODE: B32,
        SELECTOR: Bit,
    }
}

fn build_program(num_rows: usize) -> errors::Result<CircuitProgram<F>> {
    let mut cx = Circuit::<F>::new("Fibonacci", num_rows)?;

    let cpu = cx.schema(&ProgColumns::build_layout());
    let selector = cpu.at(ProgColumns::SELECTOR);
    let a = cpu.at(ProgColumns::VAL_A);
    let b = cpu.at(ProgColumns::VAL_B);
    let res = cpu.at(ProgColumns::VAL_RES);
    let opcode = cpu.at(ProgColumns::OPCODE);

    let cs = cx.cs();
    let col = |c: Col| cs.col(c.index());
    let next = |c: Col| cs.next(c.index());

    cs.constrain(col(selector) * (next(a) + col(b))); // next(a) = b
    cs.constrain(col(selector) * (next(b) + col(res))); // next(b) = res = a + b
    cs.constrain(col(opcode)); // opcode = ADD

    cx.call(
        &IntArithmeticChiplet::service(),
        &[a, b, res, opcode],
        selector,
    )?;

    cx.attach(ChipletDef::from_air(&IntArithmeticChiplet::new(
        32,
        num_rows,
        num_rows - 1,
    )?)?);

    cx.fix(
        selector,
        FixedShape::Cadence {
            stride: 1,
            count: num_rows - 1,
            origin: 0,
            values: vec![F::ONE],
        },
    );

    cx.boundary(a, 0, F::ZERO);
    cx.boundary(b, 0, F::ONE);

    cx.publish(b, num_rows - 1);

    cx.compile()
}

use hekate_core::trace::{ColumnTrace, TraceBuilder};
use hekate_gadgets::{
    ArithmeticOpcode, IntArithmeticLayout, IntArithmeticOp, generate_arithmetic_trace,
};
use hekate_math::{Bit, Block32};

fn generate_traces(num_rows: usize) -> errors::Result<(ColumnTrace, ColumnTrace, u32)> {
    let num_vars = num_rows.trailing_zeros() as usize;

    let mut tb = TraceBuilder::new(&ProgColumns::build_layout(), num_vars)?;
    let mut ops: Vec<IntArithmeticOp> = Vec::with_capacity(num_rows - 1);

    let mut a: u32 = 0;
    let mut b: u32 = 1;

    for i in 0..num_rows - 1 {
        let res = a.wrapping_add(b);

        tb.set_b32(ProgColumns::VAL_A, i, Block32::from(a))?;
        tb.set_b32(ProgColumns::VAL_B, i, Block32::from(b))?;
        tb.set_b32(ProgColumns::VAL_RES, i, Block32::from(res))?;
        tb.set_b32(ProgColumns::OPCODE, i, Block32::from(ArithmeticOpcode::ADD as u32))?;
        tb.set_bit(ProgColumns::SELECTOR, i, Bit::ONE)?;

        ops.push(IntArithmeticOp::U32 {
            op: ArithmeticOpcode::ADD,
            a,
            b,
        });

        a = b;
        b = res;
    }

    // Padding row:
    // selector = 0, val_b carries fib[N-1] for the boundary pin.
    tb.set_b32(ProgColumns::VAL_A, num_rows - 1, Block32::from(a))?;
    tb.set_b32(ProgColumns::VAL_B, num_rows - 1, Block32::from(b))?;

    let cpu_trace = tb.build();

    let arith_layout = IntArithmeticLayout::compute(32);
    let arith_trace = generate_arithmetic_trace(&ops, &arith_layout, num_rows)?;

    Ok((cpu_trace, arith_trace, b))
}

use hekate_core::config::Config;
use hekate_crypto::DefaultHasher;
use hekate_crypto::transcript::Transcript;
use hekate_program::{ProgramInstance, ProgramWitness};
use hekate_prover_sys::prove;
use hekate_verifier::HekateVerifier;
use rand::{TryRng, rngs::SysRng};

fn run(num_rows: usize, audited_id: &[u8; 32]) -> Result<bool, Box<dyn core::error::Error>> {
    let (cpu, arith, fib_n) = generate_traces(num_rows)?;

    let program = build_program(num_rows)?;
    let instance = ProgramInstance::new(num_rows, vec![F::from(fib_n as u128)]);
    let witness = ProgramWitness::new(cpu).with_chiplets(vec![arith]);

    let config = Config::default();

    let mut blinding_seed = [0u8; 32];
    SysRng.try_fill_bytes(&mut blinding_seed)?;

    let proof = prove(
        b"Fibonacci",
        &program,
        &instance,
        &witness,
        &config,
        blinding_seed,
        None,
    )?;

    let mut transcript = Transcript::<DefaultHasher>::new(b"Fibonacci");

    // `audited_id` is a constant of the verifying build,
    // printed once by `digest::program_id_hex`.
    Ok(HekateVerifier::<F, DefaultHasher>::verify(
        audited_id,
        &program,
        &instance,
        &proof,
        &mut transcript,
        &config,
    )?)
}