0xproject / openzkp Goto Github PK

impl ShrAssign<usize> for U256 {
    fn shr_assign(&mut self, rhs: usize) {
        // Note: If RHS is a compile time constant then inlining will allow
        // the branches to be optimized away.
        // TODO: Test optimizing for RHS being exactly 0, 64, 128, ...
        // Note: Test small values first, they are expected to be more common.
        if rhs == 0 {
        } else if rhs < 64 {
            self.c0 >>= rhs;
            self.c0 |= self.c1 << (64 - rhs);
            self.c1 >>= rhs;

        let commitment = tree.commitment().clone();
        Ok((commitment, tree))
    }
}

// TODO ExactSizeIterator + Index<usize>

impl<Leaf: Hashable + Clone + Sync> VectorCommitment for Vec<Leaf> {
    type Leaf = Leaf;

    fn len(&self) -> usize {

    .unwrap_or_else(|err: syn::Error| err.to_compile_error())
}

pub fn u256h(input: TokenStream) -> TokenStream {
    (|| {
        // TODO: Also accept integer literals
        let bytes = parse_hex(input)?;
        let limbs = bytes_to_limbs(bytes.as_slice())?;
        let c0 = Literal::u64_suffixed(limbs[0]);
        let c1 = Literal::u64_suffixed(limbs[1]);
        let c2 = Literal::u64_suffixed(limbs[2]);

    pub fn coefficients(&self) -> &[FieldElement] {
        &self.0
    }

    // TODO: The zero polynomial is assigned a degree of 0, but it is
    // more correctly left undefined or sometimes assigned `-1` or `-∞`.
    pub fn degree(&self) -> usize {
        let mut degree = self.len() - 1;
        while self.0[degree] == FieldElement::ZERO && degree > 0 {
            degree -= 1;
        }

    alloc::{GlobalAlloc, Layout, System},
    ptr::null_mut,
    sync::atomic::{AtomicUsize, Ordering::SeqCst},
};

// TODO: Make it store a static ref to an inner allocator (defaults to System)
#[cfg_attr(feature = "std", derive(Debug))]
pub struct LoggingAllocator {
    info:      usize,
    warn:      usize,
    error:     usize,

impl<T: Clone> MmapVec<T> {
    pub fn with_capacity(capacity: usize) -> Self {
        // From https://docs.rs/tempfile/3.1.0/tempfile/: tempfile() relies on
        // the OS to remove the temporary file once the last handle is closed.
        let file = tempfile().expect("cannot create temporary file");
        // TODO: Round up to nearest 4KB
        // Note: mmaped files can not be empty, so we use at leas one byte.
        let size = max(1, capacity * size_of::<T>());
        info!("Allocating {} MB in temp file", size / 1_000_000);
        file.set_len(size as u64)
            .expect("cannot set mmap file length");
        let mmap = unsafe { MmapOptions::new().len(size).map_mut(&file) }

/// Our approach is similar to Cohen, but instead doing the second round
/// on the same matrix, we start we a fresh matrix and multiply both in the
/// end. This requires 8 additional multiplications, but allows us to use
/// the tighter stopping conditions from Jebelean. It also seems the simplest
/// out of these solutions.
// OPT: We can update r0 and r1 in place. This won't remove the partially
// redundant call to lehmer_update, but it reduces memory usage.
// We shadow s for readability.
#[allow(clippy::shadow_unrelated)]
fn lehmer_double(mut r0: U256, mut r1: U256) -> Matrix {
    debug_assert!(r0 >= r1);
    if r0.bits() < 64 {
        debug_assert!(r1.bits() < 64);

        if s.is_empty() {
            return Err(ParseError::Empty);
        }
        // TODO: Support other radices
        // TODO: Implement as trait
        // OPT: Convert 19 digits at a time using u64.
        let mut result = Self::ZERO;
        for (i, _c) in s.chars().enumerate() {
            if result > max10 {
                return Err(ParseError::Overflow);
            }

        assert_eq!(quotient, 1);
    }

    #[quickcheck]
    fn div_3by2_correct(q: u64, d0: u64, d1: u64) -> bool {
        // TODO: Add remainder
        let d1 = d1 | (1 << 63);
        let n = U256::from_limbs(d0, d1, 0, 0) * &U256::from(q);
        debug_assert!(n.c3 == 0);
        let qhat = div_3by2(&[n.c0, n.c1, n.c2], &[d0, d1]);
        qhat == q

/// Compute a - (b * c + borrow), returning the result and the new borrow.
#[inline(always)]
pub const fn msb(a: u64, b: u64, c: u64, borrow: u64) -> (u64, u64) {
    let ret = (a as u128).wrapping_sub((b as u128) * (c as u128) + (borrow as u128));
    // TODO: Why is this wrapping_sub required?
    // We want truncation here
    #[allow(clippy::cast_possible_truncation)]
    (ret as u64, 0_u64.wrapping_sub((ret >> 64) as u64))
}

/// Compute <hi, lo> / d, returning the quotient and the remainder.

// TODO: This seems out of scope for U256 to export.
pub mod utils;

pub use crate::u256::U256;

// TODO: Make member functions of U256?
pub use gcd::{gcd, gcd_extended};
#[cfg(not(feature = "std"))]
extern crate no_std_compat as std;

    prelude::v1::*,
    slice,
};
use tempfile::tempfile;

// TODO: Variant of MmapVec where it switched between Vec and Mmap after
//       a treshold size.

#[derive(Debug)] // TODO: Custom implementation
pub struct MmapVec<T: Clone> {
    mmap:     MmapMut,
    length:   usize,

    while r1 != U256::ZERO {
        let q = lehmer_double(r0.clone(), r1.clone());
        if q == Matrix::IDENTITY {
            // Do a full precision Euclid step. q is at least a halfword.
            // This should happen zero or one time, seldom more.
            // OPT: use single limb version when q is small enough?
            let q = &r0 / &r1;
            let t = r0 - &q * &r1;
            r0 = r1;
            r1 = t;
            let t = s0 - &q * &s1;

        let mut keccak = Keccak::new_keccak256();
        let mut digest = [0_u8; 32];
        keccak.update(&self.seed);
        keccak.update(&(response.nonce.to_be_bytes()));
        keccak.finalize(&mut digest);
        // OPT: Check performance impact of conversion
        let work = U256::from_bytes_be(&digest).leading_zeros();
        work >= self.difficulty
    }
}

/// Merkle trees over trace table LDE and constraint LDE
// Clippy false positive
#[allow(clippy::use_self)]
impl VectorCommitment for PolyLDE {
    // TODO: Copy free implementation. Maybe have index as a leaf type.
    type Leaf = Vec<U256>;

    fn len(&self) -> usize {
        self.0.first().map_or(0, MmapVec::len)
    }

}

/// Compute the Lehmer update matrix for small values.
///
/// This is essentialy Euclids extended GCD algorithm for 64 bits.
// OPT: Would this be faster using extended binary gcd?
// We shadow q for readability.
#[allow(clippy::shadow_unrelated)]
fn lehmer_small(mut r0: u64, mut r1: u64) -> Matrix {
    debug_assert!(r0 >= r1);
    if r1 == 0_u64 {
        return Matrix::IDENTITY;

        );
        assert_eq!(
            hex(quote! {123}).to_string(),
            quote! {compile_error ! { "Expected hexadecimal string" }}.to_string()
        );
        // TODO: This test unstable, depending on the build environment
        // (rustc version?) it requires the single quotes to be escaped or not.
        let result = hex(quote! {"hello!"}).to_string();
        let expected_1 = quote! {compile_error ! { "Invalid hexadecimal string: Invalid character 'h' at position 0" }}.to_string();
        let expected_2 = quote! {compile_error ! { "Invalid hexadecimal string: Invalid character \'h\' at position 0" }}.to_string();
        assert!(result == expected_1 || result == expected_2);
    }

    let input: Expr = syn::parse2(input)?;
    let result = match input {
        Expr::Lit(expr_lit) => {
            match expr_lit.lit {
                Lit::Str(s) => Some(s),
                // TODO: A literal large integer (> u64) would show up as
                // Lit::Verbatim(v) =>
                _ => None,
            }
        }
        _ => None,
    };

    .unwrap_or_else(|err: syn::Error| err.to_compile_error())
}

pub fn field_element(input: TokenStream) -> TokenStream {
    (|| {
        // TODO: Also accept integer literals
        let bytes = parse_hex(input)?;
        let limbs = bytes_to_limbs(bytes.as_slice())?;
        let (c0, c1, c2, c3) = montgomery_convert((limbs[0], limbs[1], limbs[2], limbs[3]));
        let c0 = Literal::u64_suffixed(c0);
        let c1 = Literal::u64_suffixed(c1);

// HACK: This sequence needs to be repeated in each project.
//       See https://github.com/rust-lang/cargo/issues/5034
// For clippy lints see: https://rust-lang.github.io/rust-clippy/master
// For rustc lints see: https://doc.rust-lang.org/rustc/lints/index.html
#![cfg_attr(not(feature = "std"), no_std)]
#![forbid(unsafe_code)]
#![warn(
    // Enable sets of warnings
    clippy::all,

}

impl<T: Clone> Extend<T> for MmapVec<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        // The function signature is for compatibility with Vec::extend.
        // OPT: Specialize for SliceIterator
        for i in iter {
            self.push(i)
        }
    }
}

            lehmer_update(&mut s0, &mut s1, &q);
            lehmer_update(&mut t0, &mut t1, &q);
            even ^= !q.4;
        }
    }
    // TODO: Compute using absolute value instead of patching sign.
    if even {
        // t negative
        t0 = U256::ZERO - t0;
    } else {
        // s negative

        result
    }

    #[cfg(feature = "std")]
    pub fn low_degree_extension(&self, blowup: usize) -> MmapVec<FieldElement> {
        // TODO: shift polynomial by FieldElement::GENERATOR outside of this function.
        const SHIFT_FACTOR: FieldElement = FieldElement::GENERATOR;
        let length = self.len() * blowup;
        let generator =
            FieldElement::root(length).expect("No generator for extended_domain_length.");
        let mut result: MmapVec<FieldElement> = MmapVec::with_capacity(length);

    }
    Ok(result)
}

// This function and constants are taken from primefield::montgomery
// TODO: Drop this in favour of a `const fn` call.
// These constants are copied, but we don't have u256h! to format them here.
#[allow(clippy::unreadable_literal)]
// Variables are relabeled in ways that confuse clippy.
#[allow(clippy::shadow_unrelated)]
fn montgomery_convert(x: (u64, u64, u64, u64)) -> (u64, u64, u64, u64) {
    const M64: u64 = 0xffff_ffff_ffff_ffff;

/// Implements Vector Commitments using Merkle Trees.
///
/// <https://eprint.iacr.org/2011/495.pdf>
// TODO: Spin of to it's own crate.
// TODO: Implement sparse Merkle trees.
// TODO: Generalize over hash implementations.
mod index;
mod node;
mod proof;
mod result;

    debug_assert!(divisor.len() >= 2);
    debug_assert!(numerator.len() > divisor.len());
    debug_assert!(*divisor.last().unwrap() > 0);
    debug_assert!(*numerator.last().unwrap() == 0);
    // OPT: Once const generics are in, unroll for lengths.
    // OPT: We can use macro generated specializations till then.
    let n = divisor.len();
    let m = numerator.len() - n - 1;

    // D1. Normalize.
    let shift = divisor[n - 1].leading_zeros();

    }
}

// False positive: `for<'a>` annotation is required.
#[allow(single_use_lifetimes)]
// TODO: Simplify
#[allow(clippy::cognitive_complexity)]
pub fn stark_proof<Claim: Verifiable, Witness: Provable<Claim>>(
    claim: &Claim,
    witness: &Witness,
    params: &ProofParams,

use tempfile::tempfile;

// TODO: Variant of MmapVec where it switched between Vec and Mmap after
//       a treshold size.

#[derive(Debug)] // TODO: Custom implementation
pub struct MmapVec<T: Clone> {
    mmap:     MmapMut,
    length:   usize,
    capacity: usize,
    _t:       PhantomData<T>,

/// Compute <hi, lo> / d, returning the quotient and the remainder.
// TODO: Make sure it uses divq on x86_64.
// See http://lists.llvm.org/pipermail/llvm-dev/2017-October/118323.html
// (Note that we require d > hi for this)
// TODO: If divq is not supported, use a fast software implementation:
// See https://gmplib.org/~tege/division-paper.pdf
fn divrem_2by1(lo: u64, hi: u64, d: u64) -> (u64, u64) {
    debug_assert!(d > 0);
    debug_assert!(d > hi);
    let d = u128::from(d);
    let n = val_2(lo, hi);

        // assert!(depth < USIZE_BITS);
        1_usize << depth
    }

    pub fn depth_for_size(size: usize) -> usize {
        // TODO: Add checks
        size.next_power_of_two().trailing_zeros() as usize
    }

    pub const fn root() -> Self {
        Self(1)

#![forbid(unsafe_code)]
#![warn(
    // Enable sets of warnings
    clippy::all,
    clippy::pedantic,
    // TODO: clippy::cargo,
    rust_2018_idioms,
    future_incompatible,
    unused,

    // Additional unused warnings (not included in `unused`)

        // Note: a clone is necessary
        impl $trait<$type> for &$type {
            type Output = $type;

            fn $trait_fn(self, rhs: $type) -> $type {
                // TODO: Use places-reversed version of in-place operator instead.
                self.clone().$trait_fn(rhs)
            }
        }

        // Reference <op> reference

        let c0 = Literal::u64_suffixed(limbs[0]);
        let c1 = Literal::u64_suffixed(limbs[1]);
        let c2 = Literal::u64_suffixed(limbs[2]);
        let c3 = Literal::u64_suffixed(limbs[3]);

        // TODO: Ideally we'd locally import U256 here and
        // use $crate::U256 here, but this leads to a circular
        // dependency.
        Ok(quote! { U256::from_limbs(#c0, #c1, #c2, #c3) })
    })()
    .unwrap_or_else(|err: syn::Error| err.to_compile_error())
}

/// Compute <hi, lo> / d, returning the quotient and the remainder.
#[inline(always)]
pub const fn div_2_1(lo: u64, hi: u64, d: u64) -> (u64, u64) {
    let n = ((hi as u128) << 64) | (lo as u128);
    let q = n / (d as u128);
    // TODO: Not supported in cost fn:
    // debug_assert!(q < 0x1_0000_0000_0000_0000_u128);
    let r = n % (d as u128);
    // We want truncation here
    #[allow(clippy::cast_possible_truncation)]
    (q as u64, r as u64)
}

            .map(|nonce| Response { nonce })
            .find(|&response| self.verify(response))
            .expect("No valid nonce found")
    }

    // TODO: Make tests compatible with the proof of work values from this function
    #[cfg(feature = "std")]
    // False positive, constant is used when `std` is set
    #[allow(dead_code)]
    fn solve_threaded(&self) -> Response {
        info!(

            while remaining_exponent > 0 {
                if remaining_exponent % 2 == 1 {
                    result *= □
                }
                remaining_exponent >>= 1;
                // OPT - eliminate .clone()
                square *= square.clone();
            }
            Some(result)
        }
    }

    // We can return q here and have a perfectly valid single-word Lehmer GCD.
    // return q;

    // Recompute r0 and r1 and take the high bits.
    // OPT: This does not need full precision.
    // OPT: Can we reuse the shifted variables here?
    lehmer_update(&mut r0, &mut r1, &q);
    let s = r0.leading_zeros();
    let r0s = r0.clone() << s;
    let r1s = r1.clone() << s;
    let qn = lehmer_loop(r0s.c3, r1s.c3);

    deprecated_in_future,
    elided_lifetimes_in_paths,
    explicit_outlives_requirements,
    keyword_idents,
    macro_use_extern_crate,
    // TODO: missing_docs,
    missing_doc_code_examples,
    private_doc_tests,
    single_use_lifetimes,
    trivial_casts,
    trivial_numeric_casts,

            Self::from_limbs(r4, r5, r6, r7),
        )
    }

    // Short division
    // TODO: Can be computed in-place
    pub fn divrem_u64(&self, rhs: u64) -> Option<(Self, u64)> {
        if rhs == 0 {
            None
        } else {
            // Knuth Algorithm S

        let generator =
            FieldElement::root(length).expect("No generator for extended_domain_length.");
        let mut result: MmapVec<FieldElement> = MmapVec::with_capacity(length);

        // Initialize to zero
        // TODO: Avoid initialization
        result.resize(length, FieldElement::ZERO);

        // Compute cosets in parallel
        result
            .as_mut_slice()

            Self::from_limbs(numerator[0], numerator[1], 0, 0)
        } else if modulus.c0 > 0 {
            let remainder = divrem_nby1(&mut numerator, modulus.c0);
            Self::from_limbs(remainder, 0, 0, 0)
        } else {
            panic!(); // TODO: return Option<>
        }
    }

    // Computes the inverse modulo 2^256
    pub fn invmod256(&self) -> Option<Self> {

// TODO: Naming?
#![allow(clippy::module_name_repetitions)]
use mmap_vec::MmapVec;
#[cfg(feature = "std")]
use primefield::fft::{fft_cofactor_permuted, permute_index};
use primefield::FieldElement;

            .iter()
            .map(DensePolynomial::degree)
            .collect::<Vec<_>>()
    );

    // OPT: It may be faster to compute the constraint LDE from the trace LDE,
    // instead of using an FFT.
    info!("Compute the low degree extension of constraint polynomials.");
    let constraint_lde = PolyLDE(
        constraint_polynomials
            .par_iter()
            .map(|p| p.low_degree_extension(params.blowup))

            u64::arbitrary(g),
        )
    }
}

// TODO: Replace literals with u256h!
#[allow(clippy::unreadable_literal)]
// Quickcheck requires pass by value
#[allow(clippy::needless_pass_by_value)]
#[cfg(test)]
mod tests {

}

impl Challenge {
    pub(crate) fn verify(&self, response: Response) -> bool {
        // TODO: return Result<()>
        // OPT: Inline Keccak256 and work directly on buffer using 'keccakf'
        let mut keccak = Keccak::new_keccak256();
        let mut digest = [0_u8; 32];
        keccak.update(&self.seed);
        keccak.update(&(response.nonce.to_be_bytes()));
        keccak.finalize(&mut digest);

    let trace = witness.trace(claim);
    let constraints = claim.constraints();

    info!("Starting Stark proof.");
    info!("Proof parameters: {:?}", params);
    // TODO: Use a proper size human formating function
    #[allow(clippy::cast_precision_loss)]
    let size_mb = (trace.num_rows() * trace.num_columns() * 32) as f64 / 1_000_000_f64;
    info!(
        "Trace table {} rows {} columns ({} MB)",
        trace.num_rows(),

mod binops;
mod division;
mod gcd;
mod u256;

// TODO: This seems out of scope for U256 to export.
pub mod utils;

pub use crate::u256::U256;

// TODO: Make member functions of U256?

}

/// Compute a - (b + borrow), returning the result and the new borrow.
#[inline(always)]
pub const fn sbb(a: u64, b: u64, borrow: u64) -> (u64, u64) {
    // TODO: Why this shift on borrow?
    let ret = (a as u128).wrapping_sub((b as u128) + ((borrow >> 63) as u128));
    // We want truncation here
    #[allow(clippy::cast_possible_truncation)]
    (ret as u64, (ret >> 64) as u64)
}

            return "0".to_string();
        }
        let mut result = String::new();
        let mut copy = self.clone();
        while copy > Self::ZERO {
            // OPT: Convert 19 digits at a time using u64.
            let digit = (&copy % Self::from(10_u64)).c0;
            result.push_str(&digit.to_string());
            copy /= Self::from(10_u64);
        }
        // Reverse digits

    while r1 != U256::ZERO {
        let q = lehmer_double(r0.clone(), r1.clone());
        if q == Matrix::IDENTITY {
            // Do a full precision Euclid step. q is at least a halfword.
            // This should happen zero or one time, seldom more.
            // OPT: use single limb version when q is small enough?
            let q = &r0 / &r1;
            let t = r0 - &q * &r1;
            r0 = r1;
            r1 = t;
        } else {