// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
//
// Copyright (c) DUSK NETWORK. All rights reserved.

#![doc(
    html_logo_url = "https://lh3.googleusercontent.com/SmwswGxtgIANTbDrCOn5EKcRBnVdHjmYsHYxLq2HZNXWCQ9-fZyaea-bNgdX9eR0XGSqiMFi=w128-h128-e365"
)]
#![doc(html_favicon_url = "https://dusk.network/lib/img/favicon-16x16.png")]
//!<a href="https://codecov.io/gh/dusk-network/plonk">
//!  <img src="https://codecov.io/gh/dusk-network/plonk/branch/master/graph/badge.svg" />
//!</a>
//! <a href="https://travis-ci.com/dusk-network/plonk">
//! <img src="https://travis-ci.com/dusk-network/plonk.svg?branch=master" />
//! </a>
//! <a href="https://github.com/dusk-network/plonk">
//! <img alt="GitHub issues" src="https://img.shields.io/github/issues-raw/dusk-network/plonk?style=plastic">
//! </a>
//! <a href="https://github.com/dusk-network/plonk/blob/master/LICENSE">
//! <img alt="GitHub" src="https://img.shields.io/github/license/dusk-network/plonk?color=%230E55EF">
//! </a>
//!
//!
//! Permutations over Lagrange-bases for Oecumenical Noninteractive
//! arguments of Knowledge (PLONK) is a zero knowledge proof system.
//!
//! This protocol was created by:
//! - Ariel Gabizon (Protocol Labs),
//! - Zachary J. Williamson (Aztec Protocol)
//! - Oana Ciobotaru
//!
//! This crate contains a pure-rust implementation done by the [DuskNetwork
//! team](dusk.network) of this algorithm using as a reference implementation
//! this one done by the creators of the protocol:
//!
//! <https://github.com/AztecProtocol/barretenberg/blob/master/barretenberg/src/aztec/plonk/>

// Bitshift/Bitwise ops are allowed to gain performance.
#![allow(clippy::suspicious_arithmetic_impl)]
// Some structs do not have AddAssign or MulAssign impl.
#![allow(clippy::suspicious_op_assign_impl)]
// Witness have always the same names in respect to wires.
#![allow(clippy::many_single_char_names)]
// Bool expr are usually easier to read with match statements.
#![allow(clippy::match_bool)]
// We have quite some functions that require quite some args by it's nature.
// It can be refactored but for now, we avoid these warns.
#![allow(clippy::too_many_arguments)]
#![deny(rustdoc::broken_intra_doc_links)]
#![deny(missing_docs)]
#![cfg_attr(not(feature = "std"), no_std)]

mod permutation;

mod key;
mod prover;
mod verifier;

pub mod gadget;

pub mod commitment_scheme;
pub mod prelude;

#[doc = include_str!("../docs/notes-intro.md")]
pub mod notes {
    #[doc = include_str!("../docs/notes-commitments.md")]
    pub mod commitment_schemes {}
    #[doc = include_str!("../docs/notes-snark.md")]
    pub mod snark_construction {}
    #[doc = include_str!("../docs/notes-prove-verify.md")]
    pub mod prove_verify {}
    #[doc = include_str!("../docs/notes-KZG10.md")]
    pub mod kzg10_docs {}
}

pub use crate::key::PlonkKey;
pub use crate::prover::Prover;
pub use crate::verifier::Verifier;

use bls_12_381::Fr as BlsScalar;
use core::fmt::Debug;
use core::{cmp, ops};
use hashbrown::HashMap;
use jub_jub::compute_windowed_naf;
use sp_std::vec;
use zksnarks::error::Error;
use zksnarks::{
    constraint_system::ConstraintSystem, plonk::wire::PrivateWire, Constraint,
};
use zkstd::common::{
    FftField, Group, Neg, PrimeField, Ring, TwistedEdwardsAffine,
    TwistedEdwardsCurve, TwistedEdwardsExtended, Vec,
};

use crate::gadget::ecc::WnafRound;
use crate::gadget::WitnessPoint;
use crate::permutation::Permutation;
use zksnarks::bit_iterator::BitIterator8;

/// Construct and prove circuits
#[derive(Debug, Clone)]
pub struct Plonk<C: TwistedEdwardsAffine> {
    /// Constraint system gates
    pub(crate) constraints: Vec<Constraint<C::Range>>,

    /// Sparse representation of the public inputs
    pub(crate) instance: HashMap<usize, C::Range>,

    /// Witness values
    pub(crate) witness: Vec<C::Range>,

    /// Permutation argument.
    pub(crate) perm: Permutation<C::Range>,
}

impl<C: TwistedEdwardsAffine> ConstraintSystem<C> for Plonk<C> {
    type Wire = PrivateWire;
    type Constraints = Vec<Constraint<C::Range>>;

    fn initialize() -> Self {
        let mut slf = Self::new();

        let zero = slf.append_witness(0);
        let one = slf.append_witness(1);

        slf.assert_equal_constant(zero, 0, None);
        slf.assert_equal_constant(one, 1, None);

        slf.append_dummy_gates();
        slf.append_dummy_gates();

        slf
    }

    fn m(&self) -> usize {
        self.constraints.len()
    }

    fn alloc_instance(&mut self, instance: C::Range) -> Self::Wire {
        self.append_public(instance)
    }

    fn alloc_witness(&mut self, witness: C::Range) -> Self::Wire {
        self.append_witness(witness)
    }
}

impl<C: TwistedEdwardsAffine> ops::Index<PrivateWire> for Plonk<C> {
    type Output = C::Range;

    fn index(&self, w: PrivateWire) -> &Self::Output {
        &self.witness[w.index()]
    }
}

impl<C: TwistedEdwardsAffine> Plonk<C> {
    fn new() -> Self {
        Self {
            constraints: Vec::default(),
            instance: HashMap::new(),
            witness: Vec::default(),
            perm: Permutation::new(),
        }
    }

    /// Zero representation inside the constraint system.
    ///
    /// A turbo composer expects the first witness to be always present and to
    /// be zero.
    pub const ZERO: PrivateWire = PrivateWire::new(0);

    /// `One` representation inside the constraint system.
    ///
    /// A turbo composer expects the 2nd witness to be always present and to
    /// be one.
    const ONE: PrivateWire = PrivateWire::new(1);

    /// Identity point representation inside the constraint system
    const IDENTITY: WitnessPoint = WitnessPoint::new(Self::ZERO, Self::ONE);

    pub(crate) fn public_input_indexes(&self) -> Vec<usize> {
        let mut public_input_indexes =
            self.instance.keys().copied().collect::<Vec<_>>();

        public_input_indexes.as_mut_slice().sort();

        public_input_indexes
    }

    pub(crate) fn instance(&self) -> Vec<C::Range> {
        self.public_input_indexes()
            .iter()
            .filter_map(|idx| self.instance.get(idx).copied())
            .collect()
    }

    pub(crate) fn dense_public_inputs(
        public_input_indexes: &[usize],
        public_inputs: &[C::Range],
        size: usize,
    ) -> Vec<C::Range> {
        let mut dense_public_inputs = vec![C::Range::zero(); size];

        public_input_indexes
            .iter()
            .zip(public_inputs.iter())
            .for_each(|(idx, pi)| dense_public_inputs[*idx] = *pi);

        dense_public_inputs
    }

    pub(crate) fn m(&self) -> usize {
        self.constraints.len()
    }

    /// Allocate a witness value into the composer and return its index.
    pub fn append_witness<W: Into<C::Range>>(
        &mut self,
        witness: W,
    ) -> PrivateWire {
        self.append_witness_internal(witness.into())
    }

    /// Append a new width-4 poly gate/constraint.
    pub fn append_custom_gate(&mut self, constraint: Constraint<C::Range>) {
        #[allow(deprecated)]
        self.append_custom_gate_internal(constraint)
    }

    ///
    pub fn append_witness_internal(
        &mut self,
        witness: C::Range,
    ) -> PrivateWire {
        let n = self.witness.len();

        // Get a new Witness from the permutation
        self.perm.new_witness();

        // Bind the allocated witness
        self.witness.push(witness);

        PrivateWire::new(n)
    }

    ///
    pub fn append_custom_gate_internal(
        &mut self,
        constraint: Constraint<C::Range>,
    ) {
        let n = self.constraints.len();

        self.constraints.push(constraint);

        if let Some(pi) = constraint.public_input {
            self.instance.insert(n, pi);
        }

        self.perm.add_witnesses_to_map(
            constraint.w_a,
            constraint.w_b,
            constraint.w_o,
            constraint.w_d,
            n,
        );
    }

    /// Performs a logical AND or XOR op between the inputs provided for the
    /// specified number of bits (counting from the least significant bit).
    ///
    /// Each logic gate adds `(num_bits / 2) + 1` gates to the circuit to
    /// perform the whole operation.
    ///
    /// ## Constraint
    /// - is_component_xor = 1 -> Performs XOR between the first `num_bits` for
    ///   `a` and `b`.
    /// - is_component_xor = 0 -> Performs AND between the first `num_bits` for
    ///   `a` and `b`.
    ///
    /// # Panics
    /// This function will panic if the num_bits specified is not even, ie.
    /// `num_bits % 2 != 0`.
    fn append_logic_component(
        &mut self,
        a: PrivateWire,
        b: PrivateWire,
        num_bits: usize,
        is_component_xor: bool,
    ) -> PrivateWire {
        let num_bits = cmp::min(num_bits, 256);
        let num_quads = num_bits >> 1;

        let bls_four = C::Range::from(4u64);
        let mut left_acc = C::Range::zero();
        let mut right_acc = C::Range::zero();
        let mut out_acc = C::Range::zero();

        // skip bits outside of argument `num_bits`
        let a_bit_iter = BitIterator8::new(self[a].to_raw_bytes());
        let a_bits = a_bit_iter.skip(256 - num_bits).collect::<Vec<_>>();
        let b_bit_iter = BitIterator8::new(self[b].to_raw_bytes());
        let b_bits = b_bit_iter.skip(256 - num_bits).collect::<Vec<_>>();

        //
        // * +-----+-----+-----+-----+
        // * |  A  |  B  |  C  |  D  |
        // * +-----+-----+-----+-----+
        // * | 0   | 0   | w1  | 0   |
        // * | a1  | b1  | w2  | d1  |
        // * | a2  | b2  | w3  | d2  |
        // * |  :  |  :  |  :  |  :  |
        // * | an  | bn  | 0   | dn  |
        // * +-----+-----+-----+-----+
        // `an`, `bn` and `dn` are accumulators: `an [& OR ^] bd = dn`
        //
        // each step will shift last computation two bits to the left and add
        // current quad.
        //
        // `wn` product accumulators will safeguard the quotient polynomial.

        let mut constraint = if is_component_xor {
            Constraint::logic_xor(Constraint::default())
        } else {
            Constraint::logic(Constraint::default())
        };

        for i in 0..num_quads {
            // commit every accumulator
            let idx = i * 2;

            let l = (a_bits[idx] as u8) << 1;
            let r = a_bits[idx + 1] as u8;
            let left_quad = l + r;
            let left_quad_bls = C::Range::from(left_quad as u64);

            let l = (b_bits[idx] as u8) << 1;
            let r = b_bits[idx + 1] as u8;
            let right_quad = l + r;
            let right_quad_bls = C::Range::from(right_quad as u64);

            let out_quad_bls = if is_component_xor {
                left_quad ^ right_quad
            } else {
                left_quad & right_quad
            } as u64;
            let out_quad_bls = C::Range::from(out_quad_bls);

            // `w` argument to safeguard the quotient polynomial
            let prod_quad_bls = (left_quad * right_quad) as u64;
            let prod_quad_bls = C::Range::from(prod_quad_bls);

            // Now that we've computed this round results, we need to apply the
            // logic transition constraint that will check that
            //   a_{i+1} - (a_i << 2) < 4
            //   b_{i+1} - (b_i << 2) < 4
            //   d_{i+1} - (d_i << 2) < 4   with d_i = a_i [& OR ^] b_i
            // Note that multiplying by four is the equivalent of shifting the
            // bits two positions to the left.

            left_acc = left_acc * bls_four + left_quad_bls;
            right_acc = right_acc * bls_four + right_quad_bls;
            out_acc = out_acc * bls_four + out_quad_bls;

            let wit_a = self.append_witness(left_acc);
            let wit_b = self.append_witness(right_acc);
            let wit_c = self.append_witness(prod_quad_bls);
            let wit_d = self.append_witness(out_acc);

            constraint = constraint.o(wit_c);

            self.append_custom_gate(constraint);

            constraint = constraint.a(wit_a).b(wit_b).d(wit_d);
        }

        // pad last output with `0`
        // | an  | bn  | 0   | dn  |
        let a = constraint.w_a;
        let b = constraint.w_b;
        let d = constraint.w_d;

        let constraint = Constraint::default().a(a).b(b).d(d);

        self.append_custom_gate(constraint);

        d
    }

    /// Evaluate `jubjub · Generator` as a [`WitnessPoint`]
    ///
    /// `generator` will be appended to the circuit description as constant
    ///
    /// Will error if `jubjub` doesn't fit `Fr`
    pub fn component_mul_generator<A: Into<C::Extended>>(
        &mut self,
        jubjub: PrivateWire,
        generator: A,
    ) -> Result<WitnessPoint, Error> {
        let generator = generator.into();

        // the number of bits is truncated to the maximum possible. however, we
        // could slice off 3 bits from the top of wnaf since Fr price is
        // 252 bits. Alternatively, we could move to base4 and halve the
        // number of gates considering that the product of wnaf adjacent
        // entries is zero.
        let bits: usize = 256;

        // compute 2^iG
        let mut wnaf_point_multiples = {
            let mut multiples = vec![C::Extended::ADDITIVE_IDENTITY; bits];

            multiples[0] = generator;

            for i in 1..bits {
                multiples[i] = multiples[i - 1].double();
            }

            multiples
                .iter()
                .map(|point| C::from(*point))
                .collect::<Vec<_>>()
        };

        wnaf_point_multiples.reverse();

        // we should error instead of producing invalid proofs - otherwise this
        // can easily become an attack vector to either shutdown prover
        // services or create malicious statements
        let scalar = self[jubjub];

        let width = 2;
        let wnaf_entries = compute_windowed_naf(scalar, width);

        debug_assert_eq!(wnaf_entries.len(), bits);

        // initialize the accumulators
        let mut scalar_acc = vec![C::Range::zero()];
        let mut point_acc = vec![C::ADDITIVE_IDENTITY];

        // auxillary point to help with checks on the backend
        let two = C::Range::from(2u64);
        let xy_alphas: Vec<_> = wnaf_entries
            .iter()
            .rev()
            .enumerate()
            .map(|(i, entry)| {
                let (scalar_to_add, point_to_add) = match entry {
                    0 => (C::Range::zero(), C::ADDITIVE_IDENTITY),
                    -1 => (C::Range::one().neg(), -wnaf_point_multiples[i]),
                    1 => (C::Range::one(), wnaf_point_multiples[i]),
                    _ => return Err(Error::UnsupportedWNAF2k),
                };

                let prev_accumulator = two * scalar_acc[i];
                let scalar = prev_accumulator + scalar_to_add;
                scalar_acc.push(scalar);

                let point = point_acc[i] + point_to_add;
                point_acc.push(C::from(point));

                let x_alpha = point_to_add.get_x();
                let y_alpha = point_to_add.get_y();

                Ok(x_alpha * y_alpha)
            })
            .collect::<Result<_, Error>>()?;

        for i in 0..bits {
            let acc_x = self.append_witness(point_acc[i].get_x());
            let acc_y = self.append_witness(point_acc[i].get_y());
            let accumulated_bit = self.append_witness(scalar_acc[i]);

            // the point accumulator must start from identity and its scalar
            // from zero
            if i == 0 {
                self.assert_equal_constant(acc_x, C::Range::zero(), None);
                self.assert_equal_constant(acc_y, C::Range::one(), None);
                self.assert_equal_constant(
                    accumulated_bit,
                    C::Range::zero(),
                    None,
                );
            }

            let x_beta = wnaf_point_multiples[i].get_x();
            let y_beta = wnaf_point_multiples[i].get_y();

            let xy_alpha = self.append_witness(xy_alphas[i]);
            let xy_beta = x_beta * y_beta;

            let wnaf_round = WnafRound::<PrivateWire, C::Range> {
                acc_x,
                acc_y,
                accumulated_bit,
                xy_alpha,
                x_beta,
                y_beta,
                xy_beta,
            };

            let constraint =
                Constraint::group_add_curve_scalar(Constraint::default())
                    .left(wnaf_round.x_beta)
                    .right(wnaf_round.y_beta)
                    .constant(wnaf_round.xy_beta)
                    .a(wnaf_round.acc_x)
                    .b(wnaf_round.acc_y)
                    .o(wnaf_round.xy_alpha)
                    .d(wnaf_round.accumulated_bit);

            self.append_custom_gate(constraint)
        }

        // last gate isn't activated for ecc
        let acc_x = self.append_witness(point_acc[bits].get_x());
        let acc_y = self.append_witness(point_acc[bits].get_y());

        // FIXME this implementation presents a plethora of vulnerabilities and
        // requires reworking
        //
        // we are accepting any scalar argument and trusting it to be the
        // expected input. it happens to be correct in this
        // implementation, but can be exploited by malicious provers who
        // might just input anything here
        let last_accumulated_bit = self.append_witness(scalar_acc[bits]);

        // FIXME the gate isn't checking anything. maybe remove?
        let constraint = Constraint::default()
            .a(acc_x)
            .b(acc_y)
            .d(last_accumulated_bit);
        self.append_gate(constraint);

        // constrain the last element in the accumulator to be equal to the
        // input jubjub scalar
        self.assert_equal(last_accumulated_bit, jubjub);

        Ok(WitnessPoint::new(acc_x, acc_y))
    }

    /// Append a new width-4 poly gate/constraint.
    ///
    /// The constraint added will enforce the following:
    /// `q_m · a · b  + q_l · a + q_r · b + q_o · o + q_4 · d + q_c + PI = 0`.
    pub fn append_gate(&mut self, constraint: Constraint<C::Range>) {
        let constraint = Constraint::arithmetic(constraint);

        self.append_custom_gate(constraint)
    }

    /// Evaluate the polynomial and append an output that satisfies the equation
    ///
    /// Return `None` if the output selector is zero
    pub fn append_evaluated_output(
        &mut self,
        s: Constraint<C::Range>,
    ) -> Option<PrivateWire> {
        let a = s.w_a;
        let b = s.w_b;
        let d = s.w_d;

        let a = self[a];
        let b = self[b];
        let d = self[d];

        let qm = s.q_m;
        let ql = s.q_l;
        let qr = s.q_r;
        let qd = s.q_d;
        let qc = s.q_c;
        let pi = s.public_input.unwrap_or_else(C::Range::zero);

        let x = qm * a * b + ql * a + qr * b + qd * d + qc + pi;

        let y = s.q_o;

        // Invert is an expensive operation; in most cases, `qo` is going to be
        // either 1 or -1, so we can optimize these
        #[allow(dead_code)]
        let o = {
            const ONE: BlsScalar = BlsScalar::one();
            const MINUS_ONE: BlsScalar = BlsScalar([
                0xfffffffd00000003,
                0xfb38ec08fffb13fc,
                0x99ad88181ce5880f,
                0x5bc8f5f97cd877d8,
            ]);

            // Can't use a match pattern here since `BlsScalar` doesn't derive
            // `PartialEq`
            if y == C::Range::one() {
                Some(-x)
            } else if y == -C::Range::one() {
                Some(x)
            } else {
                y.invert().map(|y| x * (-y))
            }
        };

        o.map(|o| self.append_witness(o))
    }

    /// Adds blinding factors to the witness polynomials with two dummy
    /// arithmetic constraints
    pub fn append_dummy_gates(&mut self) {
        let six = self.append_witness(C::Range::from(6));
        let one = self.append_witness(C::Range::from(1));
        let seven = self.append_witness(C::Range::from(7));
        let min_twenty = self.append_witness(-C::Range::from(20));

        // Add a dummy constraint so that we do not have zero polynomials
        let constraint = Constraint::default()
            .mult(1)
            .left(2)
            .right(3)
            .fourth(1)
            .constant(4)
            .output(4)
            .a(six)
            .b(seven)
            .d(one)
            .o(min_twenty);

        self.append_gate(constraint);

        // Add another dummy constraint so that we do not get the identity
        // permutation
        let constraint = Constraint::default()
            .mult(1)
            .left(1)
            .right(1)
            .constant(127)
            .output(1)
            .a(min_twenty)
            .b(six)
            .o(seven);

        self.append_gate(constraint);
    }

    /// Constrain a scalar into the circuit description and return an allocated
    /// [`PrivateWire`] with its value
    pub fn append_constant<A: Into<C::Range>>(
        &mut self,
        constant: A,
    ) -> PrivateWire {
        let constant = constant.into();
        let witness = self.append_witness(constant);

        self.assert_equal_constant(witness, constant, None);

        witness
    }

    /// Appends a point in affine form as [`WitnessPoint`]
    pub fn append_point<A: Into<C>>(&mut self, affine: A) -> WitnessPoint {
        let affine = affine.into();

        let x = self.append_witness(affine.get_x());
        let y = self.append_witness(affine.get_y());

        WitnessPoint::new(x, y)
    }

    /// Constrain a point into the circuit description and return an allocated
    /// [`WitnessPoint`] with its coordinates
    pub fn append_constant_point<A: Into<C>>(
        &mut self,
        affine: A,
    ) -> WitnessPoint {
        let affine = affine.into();

        let x = self.append_constant(affine.get_x());
        let y = self.append_constant(affine.get_y());

        WitnessPoint::new(x, y)
    }

    /// Appends a point in affine form as [`WitnessPoint`]
    ///
    /// Creates two public inputs as `(x, y)`
    pub fn append_public_point<A: Into<C>>(
        &mut self,
        affine: A,
    ) -> WitnessPoint {
        let affine = affine.into();
        let point = self.append_point(affine);

        self.assert_equal_constant(
            *point.x(),
            C::Range::zero(),
            Some(C::Range::into(-affine.get_x())),
        );

        self.assert_equal_constant(
            *point.y(),
            C::Range::zero(),
            Some(C::Range::into(-affine.get_y())),
        );

        point
    }

    /// Allocate a witness value into the composer and return its index.
    ///
    /// Create a public input with the scalar
    pub fn append_public<A: Into<C::Range>>(
        &mut self,
        public: A,
    ) -> PrivateWire {
        let public = public.into();
        let witness = self.append_witness(public);

        self.assert_equal_constant(witness, 0, Some(-public));

        witness
    }

    /// Asserts `a == b` by appending a gate
    pub fn assert_equal(&mut self, a: PrivateWire, b: PrivateWire) {
        let constraint = Constraint::default()
            .left(1)
            .right(-C::Range::one())
            .a(a)
            .b(b);

        self.append_gate(constraint);
    }

    /// Adds a logical AND gate that performs the bitwise AND between two values
    /// for the specified first `num_bits` returning a [`PrivateWire`]
    /// holding the result.
    ///
    /// # Panics
    ///
    /// If the `num_bits` specified in the fn params is odd.
    pub fn append_logic_and(
        &mut self,
        a: PrivateWire,
        b: PrivateWire,
        num_bits: usize,
    ) -> PrivateWire {
        self.append_logic_component(a, b, num_bits, false)
    }

    /// Adds a logical XOR gate that performs the XOR between two values for the
    /// specified first `num_bits` returning a [`PrivateWire`] holding the
    /// result.
    ///
    /// # Panics
    ///
    /// If the `num_bits` specified in the fn params is odd.
    pub fn append_logic_xor(
        &mut self,
        a: PrivateWire,
        b: PrivateWire,
        num_bits: usize,
    ) -> PrivateWire {
        self.append_logic_component(a, b, num_bits, true)
    }

    /// Constrain `a` to be equal to `constant + pi`.
    ///
    /// `constant` will be defined as part of the public circuit description.
    pub fn assert_equal_constant<A: Into<C::Range>>(
        &mut self,
        a: PrivateWire,
        constant: A,
        public: Option<C::Range>,
    ) {
        let constant = constant.into();
        let constraint = Constraint::default().left(1).constant(-constant).a(a);
        let constraint =
            public.map(|p| constraint.public(p)).unwrap_or(constraint);

        self.append_gate(constraint);
    }

    /// Asserts `a == b` by appending two gates
    pub fn assert_equal_point(&mut self, a: WitnessPoint, b: WitnessPoint) {
        self.assert_equal(*a.x(), *b.x());
        self.assert_equal(*a.y(), *b.y());
    }

    /// Asserts `point == public`.
    ///
    /// Will add `public` affine coordinates `(x,y)` as public inputs
    pub fn assert_equal_public_point<A: Into<C>>(
        &mut self,
        point: WitnessPoint,
        public: A,
    ) {
        let public = public.into();

        self.assert_equal_constant(
            *point.x(),
            C::Range::zero(),
            Some(C::Range::into(-public.get_x())),
        );

        self.assert_equal_constant(
            *point.y(),
            C::Range::zero(),
            Some(C::Range::into(-public.get_y())),
        );
    }

    /// Adds two curve points by consuming 2 gates.
    pub fn component_add_point(
        &mut self,
        a: WitnessPoint,
        b: WitnessPoint,
    ) -> WitnessPoint {
        // In order to verify that two points were correctly added
        // without going over a degree 4 polynomial, we will need
        // x_1, y_1, x_2, y_2
        // x_3, y_3, x_1 * y_2

        let x_1 = *a.x();
        let y_1 = *a.y();
        let x_2 = *b.x();
        let y_2 = *b.y();

        let p1 = C::from_raw_unchecked(self[x_1], self[y_1]);
        let p2 = C::from_raw_unchecked(self[x_2], self[y_2]);

        let point = C::from(p1 + p2);

        let x_3 = point.get_x();
        let y_3 = point.get_y();

        let x1_y2 = self[x_1] * self[y_2];

        let x_1_y_2 = self.append_witness(x1_y2);
        let x_3 = self.append_witness(x_3);
        let y_3 = self.append_witness(y_3);

        // Add the rest of the prepared points into the composer
        let constraint = Constraint::default().a(x_1).b(y_1).o(x_2).d(y_2);
        let constraint = Constraint::group_add_curve_addtion(constraint);

        self.append_custom_gate(constraint);

        let constraint = Constraint::default().a(x_3).b(y_3).d(x_1_y_2);

        self.append_custom_gate(constraint);

        WitnessPoint::new(x_3, y_3)
    }

    /// Adds a boolean constraint (also known as binary constraint) where the
    /// gate eq. will enforce that the [`PrivateWire`] received is either `0` or
    /// `1` by adding a constraint in the circuit.
    ///
    /// Note that using this constraint with whatever [`PrivateWire`] that
    /// is not representing a value equalling 0 or 1, will always force the
    /// equation to fail.
    pub fn component_boolean(&mut self, a: PrivateWire) {
        let zero = Self::ZERO;
        let constraint = Constraint::default()
            .mult(1)
            .output(-C::Range::one())
            .a(a)
            .b(a)
            .o(a)
            .d(zero);

        self.append_gate(constraint);
    }

    /// Decomposes `scalar` into an array truncated to `N` bits (max 256).
    ///
    /// Asserts the reconstruction of the bits to be equal to `scalar`.
    ///
    /// Consume `2 · N + 1` gates
    pub fn component_decomposition<const N: usize>(
        &mut self,
        scalar: PrivateWire,
    ) -> [PrivateWire; N] {
        // Static assertion
        assert!(0 < N && N <= 256);

        let mut decomposition = [Self::ZERO; N];

        let acc = Self::ZERO;
        let acc = self[scalar]
            .to_bits()
            .iter()
            .rev()
            .enumerate()
            .zip(decomposition.iter_mut())
            .fold(acc, |acc, ((i, w), d)| {
                *d = self.append_witness(C::Range::from(*w as u64));

                self.component_boolean(*d);

                let constraint = Constraint::default()
                    .left(C::Range::pow_of_2(i as u64))
                    .right(1)
                    .a(*d)
                    .b(acc);

                self.gate_add(constraint)
            });

        self.assert_equal(acc, scalar);

        decomposition
    }

    /// Conditionally selects identity as [`WitnessPoint`] based on an input
    /// bit.
    ///
    /// bit == 1 => a,
    /// bit == 0 => identity,
    ///
    /// `bit` is expected to be constrained by
    /// [`Composer::component_boolean`]
    pub fn component_select_identity(
        &mut self,
        bit: PrivateWire,
        a: WitnessPoint,
    ) -> WitnessPoint {
        let x = self.component_select_zero(bit, *a.x());
        let y = self.component_select_one(bit, *a.y());

        WitnessPoint::new(x, y)
    }

    /// Evaluate `jubjub · point` as a [`WitnessPoint`]
    pub fn component_mul_point(
        &mut self,
        jubjub: PrivateWire,
        point: WitnessPoint,
    ) -> WitnessPoint {
        // Turn scalar into bits
        let scalar_bits = self.component_decomposition::<252>(jubjub);

        let mut result = Self::IDENTITY;

        for bit in scalar_bits.iter().rev() {
            result = self.component_add_point(result, result);

            let point_to_add = self.component_select_identity(*bit, point);
            result = self.component_add_point(result, point_to_add);
        }

        result
    }

    /// Conditionally selects a [`PrivateWire`] based on an input bit.
    ///
    /// bit == 1 => a,
    /// bit == 0 => b,
    ///
    /// `bit` is expected to be constrained by
    /// [`Composer::component_boolean`]
    pub fn component_select(
        &mut self,
        bit: PrivateWire,
        a: PrivateWire,
        b: PrivateWire,
    ) -> PrivateWire {
        // bit * a
        let constraint = Constraint::default().mult(1).a(bit).b(a);
        let bit_times_a = self.gate_mul(constraint);

        // 1 - bit
        let constraint = Constraint::default()
            .left(-C::Range::one())
            .constant(1)
            .a(bit);
        let one_min_bit = self.gate_add(constraint);

        // (1 - bit) * b
        let constraint = Constraint::default().mult(1).a(one_min_bit).b(b);
        let one_min_bit_b = self.gate_mul(constraint);

        // [ (1 - bit) * b ] + [ bit * a ]
        let constraint = Constraint::default()
            .left(1)
            .right(1)
            .a(one_min_bit_b)
            .b(bit_times_a);
        self.gate_add(constraint)
    }

    /// Conditionally selects a [`PrivateWire`] based on an input bit.
    ///
    /// bit == 1 => value,
    /// bit == 0 => 1,
    ///
    /// `bit` is expected to be constrained by
    /// [`Composer::component_boolean`]
    pub fn component_select_one(
        &mut self,
        bit: PrivateWire,
        value: PrivateWire,
    ) -> PrivateWire {
        let b = self[bit];
        let v = self[value];

        let f_x = C::Range::one() - b + (b * v);
        let f_x = self.append_witness(f_x);

        let constraint = Constraint::default()
            .mult(1)
            .left(-C::Range::one())
            .output(-C::Range::one())
            .constant(1)
            .a(bit)
            .b(value)
            .o(f_x);

        self.append_gate(constraint);

        f_x
    }

    /// Conditionally selects a [`WitnessPoint`] based on an input bit.
    ///
    /// bit == 1 => a,
    /// bit == 0 => b,
    ///
    /// `bit` is expected to be constrained by
    /// [`Composer::component_boolean`]
    pub fn component_select_point(
        &mut self,
        bit: PrivateWire,
        a: WitnessPoint,
        b: WitnessPoint,
    ) -> WitnessPoint {
        let x = self.component_select(bit, *a.x(), *b.x());
        let y = self.component_select(bit, *a.y(), *b.y());

        WitnessPoint::new(x, y)
    }

    /// Conditionally selects a [`PrivateWire`] based on an input bit.
    ///
    /// bit == 1 => value,
    /// bit == 0 => 0,
    ///
    /// `bit` is expected to be constrained by
    /// [`Composer::component_boolean`]
    pub fn component_select_zero(
        &mut self,
        bit: PrivateWire,
        value: PrivateWire,
    ) -> PrivateWire {
        let constraint = Constraint::default().mult(1).a(bit).b(value);

        self.gate_mul(constraint)
    }

    /// Adds a range-constraint gate that checks and constrains a
    /// [`PrivateWire`] to be inside of the range \[0,num_bits\].
    ///
    /// This function adds `num_bits/4` gates to the circuit description in
    /// order to add the range constraint.
    ///
    ///# Panics
    /// This function will panic if the num_bits specified is not even, ie.
    /// `num_bits % 2 != 0`.
    pub fn component_range(&mut self, witness: PrivateWire, num_bits: usize) {
        // convert witness to bit representation and reverse
        let bits = self[witness];
        let bit_iter = BitIterator8::new(bits.to_raw_bytes());
        let mut bits: Vec<_> = bit_iter.collect();
        bits.reverse();

        // considering this is a width-4 program, one gate will contain 4
        // accumulators. each accumulator proves that a single quad is a
        // base-4 digit. accumulators are bijective to quads, and these
        // are 2-bits each. given that, one gate accumulates 8 bits.
        let mut num_gates = num_bits >> 3;

        // given each gate accumulates 8 bits, its count must be padded
        if num_bits % 8 != 0 {
            num_gates += 1;
        }

        // a gate holds 4 quads
        let num_quads = num_gates * 4;

        // the wires are left-padded with the difference between the quads count
        // and the bits argument
        let pad = 1 + (((num_quads << 1) - num_bits) >> 1);

        // last gate is reserved for either the genesis quad or the padding
        let used_gates = num_gates + 1;

        let base = Constraint::<C::Range>::default();
        let base = Constraint::range(base);
        let mut constraints = vec![base; used_gates];

        // We collect the set of accumulators to return back to the user
        // and keep a running count of the current accumulator
        let mut accumulators: Vec<PrivateWire> = Vec::new();
        let mut accumulator = C::Range::zero();
        let four = C::Range::from(4);

        for i in pad..=num_quads {
            // convert each pair of bits to quads
            let bit_index = (num_quads - i) << 1;
            let q_0 = bits[bit_index] as u64;
            let q_1 = bits[bit_index + 1] as u64;
            let quad = q_0 + (2 * q_1);

            accumulator = four * accumulator;
            accumulator += C::Range::from(quad);

            let accumulator_var = self.append_witness(accumulator);

            accumulators.push(accumulator_var);

            let idx = i / 4;
            match i % 4 {
                0 => {
                    constraints[idx].w_d = accumulator_var;
                }
                1 => {
                    constraints[idx].w_o = accumulator_var;
                }
                2 => {
                    constraints[idx].w_b = accumulator_var;
                }
                3 => {
                    constraints[idx].w_a = accumulator_var;
                }
                _ => unreachable!(),
            };
        }

        // last constraint is zeroed as it is reserved for the genesis quad or
        // padding
        if let Some(c) = constraints.last_mut() {
            *c = Constraint::default()
        }

        // the accumulators count is a function to the number of quads. hence,
        // this optional gate will not cause different circuits depending on the
        // witness because this computation is bound to the constant bits count
        // alone.
        if let Some(accumulator) = accumulators.last() {
            if let Some(c) = constraints.last_mut() {
                c.w_d = *accumulator
            }
        }

        constraints
            .into_iter()
            .for_each(|c| self.append_custom_gate(c));

        // the accumulators count is a function to the number of quads. hence,
        // this optional gate will not cause different circuits depending on the
        // witness because this computation is bound to the constant bits count
        // alone.
        if let Some(accumulator) = accumulators.last() {
            self.assert_equal(*accumulator, witness);
        }
    }

    /// Evaluate and return `o` by appending a new constraint into the circuit.
    ///
    /// Set `q_o = (-1)` and override the output of the constraint with:
    /// `o := q_l · a + q_r · b + q_4 · d + q_c + PI`
    pub fn gate_add(&mut self, s: Constraint<C::Range>) -> PrivateWire {
        let s = Constraint::arithmetic(s).output(-C::Range::one());

        let o = self
            .append_evaluated_output(s)
            .expect("output selector is -1");
        let s = s.o(o);

        self.append_gate(s);

        o
    }

    /// Evaluate and return `o` by appending a new constraint into the circuit.
    ///
    /// Set `q_o = (-1)` and override the output of the constraint with:
    /// `o := q_m · a · b + q_4 · d + q_c + PI`
    pub fn gate_mul(&mut self, s: Constraint<C::Range>) -> PrivateWire {
        let s = Constraint::arithmetic(s).output(-C::Range::one());

        let o = self
            .append_evaluated_output(s)
            .expect("output selector is -1");
        let s = s.o(o);

        self.append_gate(s);

        o
    }
}