//! Circuit to verify multiple ECDSA secp256k1 signatures.
// This module uses halo2-ecc's ecdsa chip
//  - to prove the correctness of secp signatures
//  - to compute the RLC in circuit
//  - to perform keccak lookup table
//
// Naming notes:
// - *_be: Big-Endian bytes
// - *_le: Little-Endian bytes

#[cfg(any(test, feature = "test-circuits"))]
mod dev;
mod ecdsa;
#[cfg(test)]
mod test;
mod utils;

use crate::{
    evm_circuit::{util::not, EvmCircuit},
    keccak_circuit::KeccakCircuit,
    sig_circuit::{
        ecdsa::ecdsa_verify_no_pubkey_check,
        utils::{calc_required_advices, FpChip},
    },
    table::{KeccakTable, SigTable},
    util::{word::WordLoHi, Challenges, Expr, SubCircuit, SubCircuitConfig},
};
use eth_types::{
    self,
    sign_types::{pk_bytes_le, pk_bytes_swap_endianness, SignData},
    Field,
};
use halo2_base::{
    gates::{range::RangeConfig, GateInstructions, RangeInstructions},
    utils::modulus,
    AssignedValue, Context, QuantumCell, SKIP_FIRST_PASS,
};
use halo2_ecc::{
    bigint::CRTInteger,
    ecc::EccChip,
    fields::{
        fp::{FpConfig, FpStrategy},
        FieldChip,
    },
};
pub(crate) use utils::*;

use halo2_proofs::{
    circuit::{Layouter, Value},
    halo2curves::secp256k1::{Fp, Fq, Secp256k1Affine},
    plonk::{Advice, Column, ConstraintSystem, Error, Expression, Selector},
    poly::Rotation,
};

use ethers_core::utils::keccak256;
use itertools::Itertools;
use log::error;
use std::{iter, marker::PhantomData};

/// Circuit configuration arguments
pub struct SigCircuitConfigArgs<F: Field> {
    /// KeccakTable
    pub _keccak_table: KeccakTable,
    /// SigTable
    pub sig_table: SigTable,
    /// Challenges
    pub challenges: Challenges<Expression<F>>,
}

/// SignVerify Configuration
#[derive(Debug, Clone)]
pub struct SigCircuitConfig<F>
where
    F: Field + halo2_base::utils::ScalarField,
{
    /// ECDSA
    ecdsa_config: FpChip<F>,
    // ecdsa_config: FpConfig<F, Fp>,
    /// An advice column to store RLC witnesses
    rlc_column: Column<Advice>,
    /// selector for keccak lookup table
    q_keccak: Selector,
    /// Used to lookup pk->pk_hash(addr)
    _keccak_table: KeccakTable,
    /// The exposed table to be used by tx circuit and ecrecover
    sig_table: SigTable,
}

impl<F> SubCircuitConfig<F> for SigCircuitConfig<F>
where
    F: Field + halo2_base::utils::ScalarField,
{
    type ConfigArgs = SigCircuitConfigArgs<F>;

    /// Return a new SigConfig
    fn new(
        meta: &mut ConstraintSystem<F>,
        Self::ConfigArgs {
            _keccak_table,
            sig_table,
            challenges: _,
        }: Self::ConfigArgs,
    ) -> Self {
        // need an additional phase 2 column/basic gate to hold the witnesses during RLC
        // computations
        let num_advice = [calc_required_advices(MAX_NUM_SIG), 1];
        let num_lookup_advice = [calc_required_lookup_advices(MAX_NUM_SIG)];
        log::info!("configuring ECDSA chip with multiple phases");

        let ecdsa_config = FpConfig::configure(
            meta,
            FpStrategy::Simple,
            &num_advice,
            &num_lookup_advice,
            1,
            LOG_TOTAL_NUM_ROWS - 1,
            LIMB_BITS,
            NUM_LIMBS,
            modulus::<Fp>(),
            0,
            LOG_TOTAL_NUM_ROWS, // maximum k of the chip
        );

        // we need one phase 2 column to store RLC results
        let rlc_column = meta.advice_column_in(halo2_proofs::plonk::SecondPhase);

        meta.enable_equality(rlc_column);

        meta.enable_equality(sig_table.recovered_addr);
        meta.enable_equality(sig_table.sig_r.lo());
        meta.enable_equality(sig_table.sig_r.hi());
        meta.enable_equality(sig_table.sig_s.lo());
        meta.enable_equality(sig_table.sig_s.hi());
        meta.enable_equality(sig_table.sig_v);
        meta.enable_equality(sig_table.is_valid);
        meta.enable_equality(sig_table.msg_hash.lo());
        meta.enable_equality(sig_table.msg_hash.hi());

        // Ref. spec SignVerifyChip 1. Verify that keccak(pub_key_bytes) = pub_key_hash
        // by keccak table lookup, where pub_key_bytes is built from the pub_key
        // in the ecdsa_chip.
        let q_keccak = meta.complex_selector();

        meta.lookup_any("keccak lookup table", |meta| {
            // When address is 0, we disable the signature verification by using a dummy pk,
            // msg_hash and signature which is not constrained to match msg_hash_rlc nor
            // the address.
            // Layout:
            // | q_keccak |       rlc       |
            // | -------- | --------------- |
            // |     1    | is_address_zero |
            // |          |    pk_rlc       |
            // |          |    pk_hash_lo   |
            // |          |    pk_hash_hi   |
            let q_keccak = meta.query_selector(q_keccak);
            let is_address_zero = meta.query_advice(rlc_column, Rotation::cur());
            let is_enable = q_keccak * not::expr(is_address_zero);

            let input = [
                is_enable.clone(),
                is_enable.clone() * meta.query_advice(rlc_column, Rotation(1)),
                is_enable.clone() * 64usize.expr(),
                is_enable.clone() * meta.query_advice(rlc_column, Rotation(2)),
                is_enable * meta.query_advice(rlc_column, Rotation(3)),
            ];
            let table = [
                meta.query_advice(_keccak_table.is_enabled, Rotation::cur()),
                meta.query_advice(_keccak_table.input_rlc, Rotation::cur()),
                meta.query_advice(_keccak_table.input_len, Rotation::cur()),
                meta.query_advice(_keccak_table.output.lo(), Rotation::cur()),
                meta.query_advice(_keccak_table.output.hi(), Rotation::cur()),
            ];

            input.into_iter().zip(table).collect()
        });

        Self {
            ecdsa_config,
            _keccak_table,
            sig_table,
            q_keccak,
            rlc_column,
        }
    }
}

/// Verify a message hash is signed by the public
/// key corresponding to an Ethereum Address.
#[derive(Clone, Debug, Default)]
pub struct SigCircuit<F: Field> {
    /// Max number of verifications
    pub max_verif: usize,
    /// Without padding
    pub signatures: Vec<SignData>,
    /// Marker
    pub _marker: PhantomData<F>,
}

impl<F: Field + halo2_base::utils::ScalarField> SubCircuit<F> for SigCircuit<F> {
    type Config = SigCircuitConfig<F>;

    fn new_from_block(block: &crate::witness::Block<F>, chunk: &crate::witness::Chunk<F>) -> Self {
        assert!(chunk.fixed_param.max_txs <= MAX_NUM_SIG);

        SigCircuit {
            max_verif: MAX_NUM_SIG,
            signatures: block.get_sign_data(true),
            _marker: Default::default(),
        }
    }

    /// Returns number of unusable rows of the SubCircuit, which should be
    /// `meta.blinding_factors() + 1`.
    fn unusable_rows() -> usize {
        [
            KeccakCircuit::<F>::unusable_rows(),
            EvmCircuit::<F>::unusable_rows(),
            // may include additional subcircuits here
        ]
        .into_iter()
        .max()
        .unwrap()
    }

    fn synthesize_sub(
        &self,
        config: &Self::Config,
        challenges: &Challenges<Value<F>>,
        layouter: &mut impl Layouter<F>,
    ) -> Result<(), Error> {
        config.ecdsa_config.range.load_lookup_table(layouter)?;
        self.assign(config, layouter, &self.signatures, challenges)?;
        Ok(())
    }

    // Since sig circuit / halo2-lib use veticle cell assignment,
    // so the returned pair is consisted of same values
    fn min_num_rows_block(
        block: &crate::witness::Block<F>,
        chunk: &crate::witness::Chunk<F>,
    ) -> (usize, usize) {
        let row_num = if chunk.fixed_param.max_vertical_circuit_rows == 0 {
            Self::min_num_rows()
        } else {
            chunk.fixed_param.max_vertical_circuit_rows
        };

        let ecdsa_verif_count =
            block.txs.len() + block.precompile_events.get_ecrecover_events().len();
        // Reserve one ecdsa verification for padding tx such that the bad case in which some tx
        // calls MAX_NUM_SIG - 1 ecrecover precompile won't happen. If that case happens, the sig
        // circuit won't have more space for the padding tx's ECDSA verification. Then the
        // prover won't be able to produce any valid proof.
        let max_num_verif = MAX_NUM_SIG - 1;

        // Instead of showing actual minimum row usage,
        // halo2-lib based circuits use min_row_num to represent a percentage of total-used capacity
        // This functionality allows l2geth to decide if additional ops can be added.
        let min_row_num = (row_num / max_num_verif) * ecdsa_verif_count;

        (min_row_num, row_num)
    }
}

impl<F: Field + halo2_base::utils::ScalarField> SigCircuit<F> {
    /// Return a new SigCircuit
    pub fn new(max_verif: usize) -> Self {
        Self {
            max_verif,
            signatures: Vec::new(),
            _marker: PhantomData,
        }
    }

    /// Return the minimum number of rows required to prove an input of a
    /// particular size.
    pub fn min_num_rows() -> usize {
        // SigCircuit can't determine usable rows independently.
        // Instead, the blinding area is determined by other advise columns with most counts of
        // rotation queries. This value is typically determined by either the Keccak or EVM
        // circuit.

        // the cells are allocated vertically, i.e., given a TOTAL_NUM_ROWS * NUM_ADVICE
        // matrix, the allocator will try to use all the cells in the first column, then
        // the second column, etc.

        let max_blinding_factor = Self::unusable_rows() - 1;

        // same formula as halo2-lib's FlexGate
        (1 << LOG_TOTAL_NUM_ROWS) - (max_blinding_factor + 3)
    }
}

impl<F: Field + halo2_base::utils::ScalarField> SigCircuit<F> {
    /// Verifies the ecdsa relationship. I.e., prove that the signature
    /// is (in)valid or not under the given public key and the message hash in
    /// the circuit. Does not enforce the signature is valid.
    ///
    /// Returns the cells for
    /// - public keys
    /// - message hashes
    /// - a boolean whether the signature is correct or not
    ///
    /// WARNING: this circuit does not enforce the returned value to be true
    /// make sure the caller checks this result!
    fn assign_ecdsa(
        &self,
        ctx: &mut Context<F>,
        ecdsa_chip: &FpChip<F>,
        sign_data: &SignData,
    ) -> Result<AssignedECDSA<F, FpChip<F>>, Error> {
        let gate = ecdsa_chip.gate();
        let zero = gate.load_zero(ctx);

        let SignData {
            signature,
            pk,
            msg: _,
            msg_hash,
        } = sign_data;
        let (sig_r, sig_s, v) = signature;

        // build ecc chip from Fp chip
        let ecc_chip = EccChip::<F, FpChip<F>>::construct(ecdsa_chip.clone());
        let pk_assigned = ecc_chip.load_private(ctx, (Value::known(pk.x), Value::known(pk.y)));
        let pk_is_valid = ecc_chip.is_on_curve_or_infinity::<Secp256k1Affine>(ctx, &pk_assigned);
        gate.assert_is_const(ctx, &pk_is_valid, F::ONE);

        // build Fq chip from Fp chip
        let fq_chip = FqChip::construct(ecdsa_chip.range.clone(), 88, 3, modulus::<Fq>());
        let integer_r =
            fq_chip.load_private(ctx, FqChip::<F>::fe_to_witness(&Value::known(*sig_r)));
        let integer_s =
            fq_chip.load_private(ctx, FqChip::<F>::fe_to_witness(&Value::known(*sig_s)));
        let msg_hash =
            fq_chip.load_private(ctx, FqChip::<F>::fe_to_witness(&Value::known(*msg_hash)));

        // returns the verification result of ecdsa signature
        //
        // WARNING: this circuit does not enforce the returned value to be true
        // make sure the caller checks this result!
        let (sig_is_valid, pk_is_zero, y_coord, y_coord_is_zero) =
            ecdsa_verify_no_pubkey_check::<F, Fp, Fq, Secp256k1Affine>(
                &ecc_chip.field_chip,
                ctx,
                &pk_assigned,
                &integer_r,
                &integer_s,
                &msg_hash,
                4,
                4,
            );

        // =======================================
        // constrains v == y.is_oddness()
        // =======================================
        assert!(*v == 0 || *v == 1, "v is not boolean");

        // we constrain:
        // - v + 2*tmp = y where y is already range checked (88 bits)
        // - v is a binary
        // - tmp is also < 88 bits (this is crucial otherwise tmp may wrap around and break
        //   soundness)

        let assigned_y_is_odd = gate.load_witness(ctx, Value::known(F::from(*v as u64)));
        gate.assert_bit(ctx, assigned_y_is_odd);

        // the last 88 bits of y
        let assigned_y_limb = &y_coord.limbs()[0];
        let mut y_value = F::ZERO;
        assigned_y_limb.value().map(|&x| y_value = x);

        // y_tmp = (y_value - y_last_bit)/2
        let y_tmp = (y_value - F::from(*v as u64)) * F::TWO_INV;
        let assigned_y_tmp = gate.load_witness(ctx, Value::known(y_tmp));

        // y_tmp_double = (y_value - y_last_bit)
        let y_tmp_double = gate.mul(
            ctx,
            QuantumCell::Existing(assigned_y_tmp),
            QuantumCell::Constant(F::from(2)),
        );
        let y_rec = gate.add(
            ctx,
            QuantumCell::Existing(y_tmp_double),
            QuantumCell::Existing(assigned_y_is_odd),
        );
        let y_is_ok = gate.is_equal(
            ctx,
            QuantumCell::Existing(*assigned_y_limb),
            QuantumCell::Existing(y_rec),
        );

        // last step we want to constrain assigned_y_tmp is 87 bits
        let assigned_y_tmp = gate.select(
            ctx,
            QuantumCell::Existing(zero),
            QuantumCell::Existing(assigned_y_tmp),
            QuantumCell::Existing(y_coord_is_zero),
        );
        ecc_chip
            .field_chip
            .range
            .range_check(ctx, &assigned_y_tmp, 87);

        let y_coord_not_zero = gate.not(ctx, QuantumCell::Existing(y_coord_is_zero));
        let sig_is_valid = gate.and_many(
            ctx,
            vec![
                QuantumCell::Existing(sig_is_valid),
                QuantumCell::Existing(y_is_ok),
                QuantumCell::Existing(y_coord_not_zero),
            ],
        );

        Ok(AssignedECDSA {
            _pk: pk_assigned,
            pk_is_zero,
            msg_hash,
            integer_r,
            integer_s,
            v: assigned_y_is_odd,
            sig_is_valid,
        })
    }

    fn enable_keccak_lookup(
        &self,
        config: &SigCircuitConfig<F>,
        ctx: &mut Context<F>,
        offset: usize,
        is_address_zero: &AssignedValue<F>,
        pk_rlc: &AssignedValue<F>,
        pk_hash: &WordLoHi<AssignedValue<F>>,
    ) -> Result<(), Error> {
        log::trace!("keccak lookup");

        // Layout:
        // | q_keccak |        rlc      |
        // | -------- | --------------- |
        // |     1    | is_address_zero |
        // |          |    pk_rlc       |
        // |          |    pk_hash_lo   |
        // |          |    pk_hash_hi   |
        config.q_keccak.enable(&mut ctx.region, offset)?;

        // is_address_zero
        let tmp_cell = ctx.region.assign_advice(
            || "is_address_zero",
            config.rlc_column,
            offset,
            || is_address_zero.value,
        )?;
        ctx.region
            .constrain_equal(is_address_zero.cell, tmp_cell.cell())?;

        // pk_rlc
        let tmp_cell = ctx.region.assign_advice(
            || "pk_rlc",
            config.rlc_column,
            offset + 1,
            || pk_rlc.value,
        )?;
        ctx.region.constrain_equal(pk_rlc.cell, tmp_cell.cell())?;

        // pk_hash
        let pk_cell_lo = ctx.region.assign_advice(
            || "pk_hash_lo",
            config.rlc_column,
            offset + 2,
            || pk_hash.lo().value,
        )?;
        ctx.region
            .constrain_equal(pk_hash.lo().cell, pk_cell_lo.cell())?;
        let pk_cell_hi = ctx.region.assign_advice(
            || "pk_hash_hi",
            config.rlc_column,
            offset + 3,
            || pk_hash.hi().value,
        )?;
        ctx.region
            .constrain_equal(pk_hash.hi().cell, pk_cell_hi.cell())?;

        log::trace!("finished keccak lookup");
        Ok(())
    }

    /// Input the signature data,
    /// Output the cells for byte decomposition of the keys and messages
    fn sign_data_decomposition(
        &self,
        ctx: &mut Context<F>,
        ecdsa_chip: &FpChip<F>,
        sign_data: &SignData,
        assigned_data: &AssignedECDSA<F, FpChip<F>>,
    ) -> Result<SignDataDecomposed<F>, Error> {
        // build ecc chip from Fp chip
        let ecc_chip = EccChip::<F, FpChip<F>>::construct(ecdsa_chip.clone());

        let zero = ecdsa_chip.range.gate.load_zero(ctx);

        // ================================================
        // step 0. powers of aux parameters
        // ================================================
        let word_lo_hi_powers =
            iter::successors(Some(F::ONE), |coeff| Some(F::from(256) * coeff)).take(32);
        let powers_of_256_cells = word_lo_hi_powers
            .map(|x| QuantumCell::Constant(x))
            .collect_vec();

        // ================================================
        // pk hash cells
        // ================================================
        let pk_le = pk_bytes_le(&sign_data.pk);
        let pk_be = pk_bytes_swap_endianness(&pk_le);
        let pk_hash = keccak256(pk_be).map(|byte| Value::known(F::from(byte as u64)));

        log::trace!("pk hash {:0x?}", pk_hash);
        let pk_hash_cells = pk_hash
            .iter()
            .map(|&x| QuantumCell::Witness(x))
            .rev()
            .collect_vec();

        // address is the random linear combination of the public key
        // it is fine to use a phase 1 gate here
        let address = ecdsa_chip.range.gate.inner_product(
            ctx,
            powers_of_256_cells[..20].to_vec(),
            pk_hash_cells[..20].to_vec(),
        );
        let address = ecdsa_chip.range.gate.select(
            ctx,
            QuantumCell::Existing(zero),
            QuantumCell::Existing(address),
            QuantumCell::Existing(assigned_data.pk_is_zero),
        );
        let is_address_zero = ecdsa_chip.range.gate.is_equal(
            ctx,
            QuantumCell::Existing(address),
            QuantumCell::Existing(zero),
        );
        log::trace!("address: {:?}", address.value());

        // ================================================
        // message hash cells
        // ================================================

        let assert_crt = |ctx: &mut Context<F>,
                          bytes: [u8; 32],
                          crt_integer: &CRTInteger<F>|
         -> Result<_, Error> {
            let byte_cells: Vec<QuantumCell<F>> = bytes
                .iter()
                .map(|&x| QuantumCell::Witness(Value::known(F::from(x as u64))))
                .collect_vec();
            self.assert_crt_int_byte_repr(
                ctx,
                &ecdsa_chip.range,
                crt_integer,
                &byte_cells,
                &powers_of_256_cells,
            )?;
            Ok(byte_cells)
        };

        // assert the assigned_msg_hash_le is the right decomposition of msg_hash
        // msg_hash is an overflowing integer with 3 limbs, of sizes 88, 88, and 80
        let assigned_msg_hash_le =
            assert_crt(ctx, sign_data.msg_hash.to_bytes(), &assigned_data.msg_hash)?;

        // ================================================
        // pk cells
        // ================================================
        let pk_x_le = sign_data
            .pk
            .x
            .to_bytes()
            .iter()
            .map(|&x| QuantumCell::Witness(Value::known(F::from_u128(x as u128))))
            .collect_vec();
        let pk_y_le = sign_data
            .pk
            .y
            .to_bytes()
            .iter()
            .map(|&y| QuantumCell::Witness(Value::known(F::from_u128(y as u128))))
            .collect_vec();
        let pk_assigned = ecc_chip.load_private(
            ctx,
            (Value::known(sign_data.pk.x), Value::known(sign_data.pk.y)),
        );

        self.assert_crt_int_byte_repr(
            ctx,
            &ecdsa_chip.range,
            &pk_assigned.x,
            &pk_x_le,
            &powers_of_256_cells,
        )?;
        self.assert_crt_int_byte_repr(
            ctx,
            &ecdsa_chip.range,
            &pk_assigned.y,
            &pk_y_le,
            &powers_of_256_cells,
        )?;

        let assigned_pk_le_selected = [pk_y_le, pk_x_le].concat();
        log::trace!("finished data decomposition");

        let r_cells = assert_crt(
            ctx,
            sign_data.signature.0.to_bytes(),
            &assigned_data.integer_r,
        )?;
        let s_cells = assert_crt(
            ctx,
            sign_data.signature.1.to_bytes(),
            &assigned_data.integer_s,
        )?;

        Ok(SignDataDecomposed {
            pk_hash_cells,
            msg_hash_cells: assigned_msg_hash_le,
            pk_cells: assigned_pk_le_selected,
            address,
            is_address_zero,
            r_cells,
            s_cells,
        })
    }

    #[allow(clippy::too_many_arguments)]
    fn assign_sig_verify(
        &self,
        ctx: &mut Context<F>,
        rlc_chip: &RangeConfig<F>,
        sign_data_decomposed: &SignDataDecomposed<F>,
        challenges: &Challenges<Value<F>>,
        assigned_ecdsa: &AssignedECDSA<F, FpChip<F>>,
    ) -> Result<([AssignedValue<F>; 4], AssignedSignatureVerify<F>), Error> {
        // ================================================
        // step 0. powers of aux parameters
        // ================================================
        let word_lo_hi_powers = iter::successors(Some(Value::known(F::ONE)), |coeff| {
            Some(Value::known(F::from(256)) * coeff)
        })
        .take(16)
        .map(|x| QuantumCell::Witness(x))
        .collect_vec();

        let keccak_challenge_powers = iter::successors(Some(Value::known(F::ONE)), |coeff| {
            Some(challenges.keccak_input() * coeff)
        })
        .take(64)
        .map(|x| QuantumCell::Witness(x))
        .collect_vec();

        // ================================================
        // step 1 message hash
        // ================================================
        // Ref. spec SignVerifyChip 3. Verify that the signed message in the ecdsa_chip
        // corresponds to msg_hash
        let msg_hash_cells = {
            let msg_hash_lo_cell_bytes = &sign_data_decomposed.msg_hash_cells[..16];
            let msg_hash_hi_cell_bytes = &sign_data_decomposed.msg_hash_cells[16..];

            let msg_hash_cell_lo = rlc_chip.gate.inner_product(
                ctx,
                msg_hash_lo_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers.clone(),
            );
            let msg_hash_cell_hi = rlc_chip.gate.inner_product(
                ctx,
                msg_hash_hi_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers.clone(),
            );

            WordLoHi::new([msg_hash_cell_lo, msg_hash_cell_hi])
        };

        log::trace!(
            "assigned msg hash: ({:?}, {:?})",
            msg_hash_cells.lo().value(),
            msg_hash_cells.hi().value()
        );

        // ================================================
        // step 2 random linear combination of pk
        // ================================================
        let pk_rlc = rlc_chip.gate.inner_product(
            ctx,
            sign_data_decomposed.pk_cells.clone(),
            keccak_challenge_powers,
        );
        log::trace!("pk rlc: {:?}", pk_rlc.value());

        // ================================================
        // step 3 pk_hash
        // ================================================
        let pk_hash_cells = {
            let pk_hash_lo_cell_bytes = &sign_data_decomposed.pk_hash_cells[..16];
            let pk_hash_hi_cell_bytes = &sign_data_decomposed.pk_hash_cells[16..];

            let pk_hash_cell_lo = rlc_chip.gate.inner_product(
                ctx,
                pk_hash_lo_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers.clone(),
            );
            let pk_hash_cell_hi = rlc_chip.gate.inner_product(
                ctx,
                pk_hash_hi_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers.clone(),
            );

            WordLoHi::new([pk_hash_cell_lo, pk_hash_cell_hi])
        };

        // step 4: r,s
        let r_cells = {
            let r_lo_cell_bytes = &sign_data_decomposed.r_cells[..16];
            let r_hi_cell_bytes = &sign_data_decomposed.r_cells[16..];

            let r_cell_lo = rlc_chip.gate.inner_product(
                ctx,
                r_lo_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers.clone(),
            );
            let r_cell_hi = rlc_chip.gate.inner_product(
                ctx,
                r_hi_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers.clone(),
            );

            WordLoHi::new([r_cell_lo, r_cell_hi])
        };
        let s_cells = {
            let s_lo_cell_bytes = &sign_data_decomposed.s_cells[..16];
            let s_hi_cell_bytes = &sign_data_decomposed.s_cells[16..];

            let s_cell_lo = rlc_chip.gate.inner_product(
                ctx,
                s_lo_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers.clone(),
            );
            let s_cell_hi = rlc_chip.gate.inner_product(
                ctx,
                s_hi_cell_bytes.iter().cloned().collect_vec(),
                word_lo_hi_powers,
            );

            WordLoHi::new([s_cell_lo, s_cell_hi])
        };

        log::trace!(
            "pk hash halo2ecc: ({:?}, {:?})",
            pk_hash_cells.lo().value(),
            pk_hash_cells.lo().value()
        );
        log::trace!("finished sign verify");

        let to_be_keccak_checked = [
            sign_data_decomposed.is_address_zero,
            pk_rlc,
            pk_hash_cells.lo(),
            pk_hash_cells.hi(),
        ];
        let assigned_sig_verif = AssignedSignatureVerify {
            address: sign_data_decomposed.address,
            // msg_len: sign_data.msg.len(),
            // msg_rlc: challenges
            //     .keccak_input()
            //     .map(|r| rlc::value(sign_data.msg.iter().rev(), r)),
            msg_hash: msg_hash_cells,
            sig_is_valid: assigned_ecdsa.sig_is_valid,
            r: r_cells,
            s: s_cells,
            v: assigned_ecdsa.v,
        };
        Ok((to_be_keccak_checked, assigned_sig_verif))
    }

    /// Assign witness data to the sig circuit.
    pub(crate) fn assign(
        &self,
        config: &SigCircuitConfig<F>,
        layouter: &mut impl Layouter<F>,
        signatures: &[SignData],
        challenges: &Challenges<Value<F>>,
    ) -> Result<Vec<AssignedSignatureVerify<F>>, Error> {
        if signatures.len() > self.max_verif {
            error!(
                "signatures.len() = {} > max_verif = {}",
                signatures.len(),
                self.max_verif
            );
            return Err(Error::Synthesis);
        }
        let mut first_pass = SKIP_FIRST_PASS;
        let ecdsa_chip = &config.ecdsa_config;

        let assigned_sig_verifs = layouter.assign_region(
            || "ecdsa chip verification",
            |region| {
                if first_pass {
                    first_pass = false;
                    return Ok(vec![]);
                }

                let mut ctx = ecdsa_chip.new_context(region);

                // ================================================
                // step 1: assert the signature is valid in circuit
                // ================================================
                let assigned_ecdsas = signatures
                    .iter()
                    .chain(std::iter::repeat(&SignData::default()))
                    .take(self.max_verif)
                    .map(|sign_data| self.assign_ecdsa(&mut ctx, ecdsa_chip, sign_data))
                    .collect::<Result<Vec<AssignedECDSA<F, FpChip<F>>>, Error>>()?;

                // ================================================
                // step 2: decompose the keys and messages
                // ================================================
                let sign_data_decomposed = signatures
                    .iter()
                    .chain(std::iter::repeat(&SignData::default()))
                    .take(self.max_verif)
                    .zip_eq(assigned_ecdsas.iter())
                    .map(|(sign_data, assigned_ecdsa)| {
                        self.sign_data_decomposition(
                            &mut ctx,
                            ecdsa_chip,
                            sign_data,
                            assigned_ecdsa,
                        )
                    })
                    .collect::<Result<Vec<SignDataDecomposed<F>>, Error>>()?;

                // IMPORTANT: Move to Phase2 before RLC
                log::info!("before proceeding to the next phase");

                // finalize the current lookup table before moving to next phase
                ecdsa_chip.finalize(&mut ctx);
                ctx.print_stats(&["ECDSA context"]);
                ctx.next_phase();

                // ================================================
                // step 3: compute RLC of keys and messages
                // ================================================
                let (assigned_keccak_values, assigned_sig_values): (
                    Vec<[AssignedValue<F>; 4]>,
                    Vec<AssignedSignatureVerify<F>>,
                ) = signatures
                    .iter()
                    .chain(std::iter::repeat(&SignData::default()))
                    .take(self.max_verif)
                    .zip_eq(assigned_ecdsas.iter())
                    .zip_eq(sign_data_decomposed.iter())
                    .map(|((_, assigned_ecdsa), sign_data_decomp)| {
                        self.assign_sig_verify(
                            &mut ctx,
                            &ecdsa_chip.range,
                            sign_data_decomp,
                            challenges,
                            assigned_ecdsa,
                        )
                    })
                    .collect::<Result<
                        Vec<([AssignedValue<F>; 4], AssignedSignatureVerify<F>)>,
                        Error,
                    >>()?
                    .into_iter()
                    .unzip();

                // ================================================
                // step 4: deferred keccak checks
                // ================================================
                for (i, [is_address_zero, pk_rlc, pk_hash_lo, pk_hash_hi]) in
                    assigned_keccak_values.iter().enumerate()
                {
                    let offset = i * 4;
                    self.enable_keccak_lookup(
                        config,
                        &mut ctx,
                        offset,
                        is_address_zero,
                        pk_rlc,
                        &WordLoHi::new([*pk_hash_lo, *pk_hash_hi]),
                    )?;
                }

                // IMPORTANT: this assigns all constants to the fixed columns
                // IMPORTANT: this copies cells to the lookup advice column to perform range
                // check lookups
                // This is not optional.
                let lookup_cells = ecdsa_chip.finalize(&mut ctx);
                log::info!("total number of lookup cells: {}", lookup_cells);

                ctx.print_stats(&["ECDSA context"]);
                Ok(assigned_sig_values)
            },
        )?;

        layouter.assign_region(
            || "expose sig table",
            |mut region| {
                // step 5: export as a lookup table
                for (idx, assigned_sig_verif) in assigned_sig_verifs.iter().enumerate() {
                    region.assign_fixed(
                        || "assign sig_table selector",
                        config.sig_table.q_enable,
                        idx,
                        || Value::known(F::ONE),
                    )?;

                    assigned_sig_verif
                        .v
                        .copy_advice(&mut region, config.sig_table.sig_v, idx);

                    assigned_sig_verif.r.lo().copy_advice(
                        &mut region,
                        config.sig_table.sig_r.lo(),
                        idx,
                    );
                    assigned_sig_verif.r.hi().copy_advice(
                        &mut region,
                        config.sig_table.sig_r.hi(),
                        idx,
                    );

                    assigned_sig_verif.s.lo().copy_advice(
                        &mut region,
                        config.sig_table.sig_s.lo(),
                        idx,
                    );
                    assigned_sig_verif.s.hi().copy_advice(
                        &mut region,
                        config.sig_table.sig_s.hi(),
                        idx,
                    );

                    assigned_sig_verif.address.copy_advice(
                        &mut region,
                        config.sig_table.recovered_addr,
                        idx,
                    );

                    assigned_sig_verif.sig_is_valid.copy_advice(
                        &mut region,
                        config.sig_table.is_valid,
                        idx,
                    );

                    assigned_sig_verif.msg_hash.lo().copy_advice(
                        &mut region,
                        config.sig_table.msg_hash.lo(),
                        idx,
                    );
                    assigned_sig_verif.msg_hash.hi().copy_advice(
                        &mut region,
                        config.sig_table.msg_hash.hi(),
                        idx,
                    );
                }
                Ok(())
            },
        )?;

        Ok(assigned_sig_verifs)
    }

    /// Assert an CRTInteger's byte representation is correct.
    /// inputs
    /// - crt_int with 3 limbs [88, 88, 80]
    /// - byte representation of the integer
    /// - a sequence of [1, 2^8, 2^16, ...]
    /// - a overriding flag that sets output to 0 if set
    fn assert_crt_int_byte_repr(
        &self,
        ctx: &mut Context<F>,
        range_chip: &RangeConfig<F>,
        crt_int: &CRTInteger<F>,
        byte_repr: &[QuantumCell<F>],
        word_lo_hi_powers: &[QuantumCell<F>],
    ) -> Result<(), Error> {
        // length of byte representation is 32
        assert_eq!(byte_repr.len(), 32);
        // need to support decomposition of up to 88 bits
        assert!(word_lo_hi_powers.len() >= 11);

        let flex_gate_chip = &range_chip.gate;

        // apply the overriding flag
        let limb1_value = crt_int.truncation.limbs[0];
        let limb2_value = crt_int.truncation.limbs[1];
        let limb3_value = crt_int.truncation.limbs[2];

        // assert the byte_repr is the right decomposition of overflow_int
        // overflow_int is an overflowing integer with 3 limbs, of sizes 88, 88, and 80
        // we reconstruct the three limbs from the bytes repr, and
        // then enforce equality with the CRT integer
        let limb1_recover = flex_gate_chip.inner_product(
            ctx,
            byte_repr[0..11].to_vec(),
            word_lo_hi_powers[0..11].to_vec(),
        );
        let limb2_recover = flex_gate_chip.inner_product(
            ctx,
            byte_repr[11..22].to_vec(),
            word_lo_hi_powers[0..11].to_vec(),
        );
        let limb3_recover = flex_gate_chip.inner_product(
            ctx,
            byte_repr[22..].to_vec(),
            word_lo_hi_powers[0..10].to_vec(),
        );
        flex_gate_chip.assert_equal(
            ctx,
            QuantumCell::Existing(limb1_value),
            QuantumCell::Existing(limb1_recover),
        );
        flex_gate_chip.assert_equal(
            ctx,
            QuantumCell::Existing(limb2_value),
            QuantumCell::Existing(limb2_recover),
        );
        flex_gate_chip.assert_equal(
            ctx,
            QuantumCell::Existing(limb3_value),
            QuantumCell::Existing(limb3_recover),
        );
        log::trace!(
            "limb 1 \ninput {:?}\nreconstructed {:?}",
            limb1_value.value(),
            limb1_recover.value()
        );
        log::trace!(
            "limb 2 \ninput {:?}\nreconstructed {:?}",
            limb2_value.value(),
            limb2_recover.value()
        );
        log::trace!(
            "limb 3 \ninput {:?}\nreconstructed {:?}",
            limb3_value.value(),
            limb3_recover.value()
        );

        Ok(())
    }
}