Tadanori TERUYA
Sean Bowe
Daira Hopwood
+ @mugatu on forum.z.cash
+ David Mercer
+ Joshua Yabut
#* @copyright MIT license (see LICENSE file)
#*******************************************************************************/
+# Determine building operating system
+ifeq ($(OS),Windows_NT)
+ uname_S := Windows
+else
+ uname_S := $(shell uname -s)
+endif
+
# To override these, use "make OPTFLAGS=..." etc.
CURVE = BN128
OPTFLAGS = -O2 -march=native -mtune=native
EXECUTABLES_WITH_SUPERCOP = \
libsnark/zk_proof_systems/ppzkadsnark/r1cs_ppzkadsnark/examples/demo_r1cs_ppzkadsnark
-GTEST_TESTS = libsnark/gtests
+GTEST_TESTS =
-GTEST_SRCS = \
- libsnark/algebra/curves/tests/test_bilinearity.cpp \
- libsnark/algebra/curves/tests/test_groups.cpp \
- libsnark/algebra/fields/tests/test_bigint.cpp \
- libsnark/algebra/fields/tests/test_fields.cpp \
- libsnark/gadgetlib1/gadgets/hashes/sha256/tests/test_sha256_gadget.cpp \
- libsnark/gadgetlib1/gadgets/merkle_tree/tests/test_merkle_tree_gadgets.cpp \
- libsnark/relations/arithmetic_programs/qap/tests/test_qap.cpp \
- libsnark/zk_proof_systems/ppzksnark/r1cs_ppzksnark/tests/test_r1cs_ppzksnark.cpp \
- libsnark/gtests.cpp
+GTEST_SRCS =
DOCS = README.html
$(if $(NO_GTEST),,$(EXECUTABLES_WITH_GTEST) $(GTEST_TESTS)) \
$(if $(NO_SUPERCOP),,$(EXECUTABLES_WITH_SUPERCOP)) \
$(EXECUTABLES) \
+ $(LIBSNARK_A) \
$(if $(NO_DOCS),,doc)
doc: $(DOCS)
[TOC]
<!---
- NOTE: the file you are reading is in Markdown format, which is fairly readable
+ NOTE: the file you are reading is in Markdown format, which is is fairly readable
directly, but can be converted into an HTML file with much nicer formatting.
To do so, run "make doc" (this requires the python-markdown package) and view
the resulting file README.html. Alternatively, view the latest HTML version at
This is easily adapted to any other Random Access Machine that satisfies a
simple load-store interface.
3. A scalable for TinyRAM using Proof-Carrying Data, as explained in \[BCTV14b]
- 4. Zero-knowledge cluster MapReduce, as explained in \[CTV15].
+ 4. Zero-knowldge cluster MapReduce, as explained in \[CTV15].
The zkSNARK construction implemented by libsnark follows, extends, and
optimizes the approach described in \[BCTV14], itself an extension of
$ make lib STATIC=1
Note that static compilation requires static versions of all libraries it depends on.
-It may help to minimize these dependencies by appending
+It may help to minize these dependencies by appending
`CURVE=ALT_BN128 NO_PROCPS=1 NO_GTEST=1 NO_SUPERCOP=1`. On Fedora 21, the requisite
library RPM dependencies are then:
`boost-static glibc-static gmp-static libstdc++-static openssl-static zlib-static
* `make MULTICORE=1`
Enable parallelized execution of the ppzkSNARK generator and prover, using OpenMP.
- This will utilize all cores on the CPU for heavyweight parallelizable operations such as
+ This will utilize all cores on the CPU for heavyweight parallelizabe operations such as
FFT and multiexponentiation. The default is single-core.
To override the maximum number of cores used, set the environment variable `OMP_NUM_THREADS`
*****************************************************************************/
#include "algebra/curves/alt_bn128/alt_bn128_g1.hpp"
+#include "common/assert_except.hpp"
namespace libsnark {
#ifdef PROFILE_OP_COUNTS
-long long alt_bn128_G1::add_cnt = 0;
-long long alt_bn128_G1::dbl_cnt = 0;
+int64_t alt_bn128_G1::add_cnt = 0;
+int64_t alt_bn128_G1::dbl_cnt = 0;
#endif
-std::vector<size_t> alt_bn128_G1::wnaf_window_table;
-std::vector<size_t> alt_bn128_G1::fixed_base_exp_window_table;
+std::vector<uint64_t> alt_bn128_G1::wnaf_window_table;
+std::vector<uint64_t> alt_bn128_G1::fixed_base_exp_window_table;
alt_bn128_G1 alt_bn128_G1::G1_zero;
alt_bn128_G1 alt_bn128_G1::G1_one;
alt_bn128_G1 alt_bn128_G1::mixed_add(const alt_bn128_G1 &other) const
{
#ifdef DEBUG
- assert(other.is_special());
+ assert_except(other.is_special());
#endif
// handle special cases having to do with O
class alt_bn128_G1 {
public:
#ifdef PROFILE_OP_COUNTS
- static long long add_cnt;
- static long long dbl_cnt;
+ static int64_t add_cnt;
+ static int64_t dbl_cnt;
#endif
- static std::vector<size_t> wnaf_window_table;
- static std::vector<size_t> fixed_base_exp_window_table;
+ static std::vector<uint64_t> wnaf_window_table;
+ static std::vector<uint64_t> fixed_base_exp_window_table;
static alt_bn128_G1 G1_zero;
static alt_bn128_G1 G1_one;
*****************************************************************************/
#include "algebra/curves/alt_bn128/alt_bn128_g2.hpp"
+#include "common/assert_except.hpp"
namespace libsnark {
#ifdef PROFILE_OP_COUNTS
-long long alt_bn128_G2::add_cnt = 0;
-long long alt_bn128_G2::dbl_cnt = 0;
+int64_t alt_bn128_G2::add_cnt = 0;
+int64_t alt_bn128_G2::dbl_cnt = 0;
#endif
-std::vector<size_t> alt_bn128_G2::wnaf_window_table;
-std::vector<size_t> alt_bn128_G2::fixed_base_exp_window_table;
+std::vector<uint64_t> alt_bn128_G2::wnaf_window_table;
+std::vector<uint64_t> alt_bn128_G2::fixed_base_exp_window_table;
alt_bn128_G2 alt_bn128_G2::G2_zero;
alt_bn128_G2 alt_bn128_G2::G2_one;
alt_bn128_G2 alt_bn128_G2::mixed_add(const alt_bn128_G2 &other) const
{
#ifdef DEBUG
- assert(other.is_special());
+ assert_except(other.is_special());
#endif
// handle special cases having to do with O
class alt_bn128_G2 {
public:
#ifdef PROFILE_OP_COUNTS
- static long long add_cnt;
- static long long dbl_cnt;
+ static int64_t add_cnt;
+ static int64_t dbl_cnt;
#endif
- static std::vector<size_t> wnaf_window_table;
- static std::vector<size_t> fixed_base_exp_window_table;
+ static std::vector<uint64_t> wnaf_window_table;
+ static std::vector<uint64_t> fixed_base_exp_window_table;
static alt_bn128_G2 G2_zero;
static alt_bn128_G2 G2_one;
bool found_one = false;
alt_bn128_ate_ell_coeffs c;
- for (long i = loop_count.max_bits(); i >= 0; --i)
+ for (int64_t i = loop_count.max_bits(); i >= 0; --i)
{
const bool bit = loop_count.test_bit(i);
if (!found_one)
const bigint<alt_bn128_Fr::num_limbs> &loop_count = alt_bn128_ate_loop_count;
alt_bn128_ate_ell_coeffs c;
- for (long i = loop_count.max_bits(); i >= 0; --i)
+ for (int64_t i = loop_count.max_bits(); i >= 0; --i)
{
const bool bit = loop_count.test_bit(i);
if (!found_one)
size_t idx = 0;
const bigint<alt_bn128_Fr::num_limbs> &loop_count = alt_bn128_ate_loop_count;
- for (long i = loop_count.max_bits(); i >= 0; --i)
+ for (int64_t i = loop_count.max_bits(); i >= 0; --i)
{
const bool bit = loop_count.test_bit(i);
if (!found_one)
GroupT result = GroupT::zero();
bool found_one = false;
- for (long i = scalar.max_bits() - 1; i >= 0; --i)
+ for (int64_t i = scalar.max_bits() - 1; i >= 0; --i)
{
if (found_one)
{
* and contributors (see AUTHORS).
* @copyright MIT license (see LICENSE file)
*****************************************************************************/
+#include <iostream>
#include "common/profiling.hpp"
+//#include "algebra/curves/edwards/edwards_pp.hpp"
#ifdef CURVE_BN128
#include "algebra/curves/bn128/bn128_pp.hpp"
#endif
#include "algebra/curves/alt_bn128/alt_bn128_pp.hpp"
-
-#include <gtest/gtest.h>
+//#include "algebra/curves/mnt/mnt4/mnt4_pp.hpp"
+//#include "algebra/curves/mnt/mnt6/mnt6_pp.hpp"
+#include "algebra/curves/alt_bn128/alt_bn128_pairing.hpp"
+#include "algebra/curves/alt_bn128/alt_bn128_pairing.cpp"
using namespace libsnark;
ans1.print();
ans2.print();
ans3.print();
- EXPECT_EQ(ans1, ans2);
- EXPECT_EQ(ans2, ans3);
+ assert(ans1 == ans2);
+ assert(ans2 == ans3);
- EXPECT_NE(ans1, GT_one);
- EXPECT_EQ((ans1^Fr<ppT>::field_char()), GT_one);
+ assert(ans1 != GT_one);
+ assert((ans1^Fr<ppT>::field_char()) == GT_one);
printf("\n\n");
}
const Fqk<ppT> ans_1 = ppT::miller_loop(prec_P1, prec_Q1);
const Fqk<ppT> ans_2 = ppT::miller_loop(prec_P2, prec_Q2);
const Fqk<ppT> ans_12 = ppT::double_miller_loop(prec_P1, prec_Q1, prec_P2, prec_Q2);
- EXPECT_EQ(ans_1 * ans_2, ans_12);
+ assert(ans_1 * ans_2 == ans_12);
}
template<typename ppT>
ans1.print();
ans2.print();
ans3.print();
- EXPECT_EQ(ans1, ans2);
- EXPECT_EQ(ans2, ans3);
+ assert(ans1 == ans2);
+ assert(ans2 == ans3);
- EXPECT_NE(ans1, GT_one);
- EXPECT_EQ((ans1^Fr<ppT>::field_char()), GT_one);
+ assert(ans1 != GT_one);
+ assert((ans1^Fr<ppT>::field_char()) == GT_one);
printf("\n\n");
}
-TEST(algebra, bilinearity)
+int main(void)
{
start_profiling();
+ edwards_pp::init_public_params();
+ pairing_test<edwards_pp>();
+ double_miller_loop_test<edwards_pp>();
+
+ mnt6_pp::init_public_params();
+ pairing_test<mnt6_pp>();
+ double_miller_loop_test<mnt6_pp>();
+ affine_pairing_test<mnt6_pp>();
+
+ mnt4_pp::init_public_params();
+ pairing_test<mnt4_pp>();
+ double_miller_loop_test<mnt4_pp>();
+ affine_pairing_test<mnt4_pp>();
+
alt_bn128_pp::init_public_params();
pairing_test<alt_bn128_pp>();
double_miller_loop_test<alt_bn128_pp>();
* @copyright MIT license (see LICENSE file)
*****************************************************************************/
#include "common/profiling.hpp"
+//#include "algebra/curves/edwards/edwards_pp.hpp"
+//#include "algebra/curves/mnt/mnt4/mnt4_pp.hpp"
+//#include "algebra/curves/mnt/mnt6/mnt6_pp.hpp"
#ifdef CURVE_BN128
#include "algebra/curves/bn128/bn128_pp.hpp"
#endif
#include "algebra/curves/alt_bn128/alt_bn128_pp.hpp"
#include <sstream>
-#include <gtest/gtest.h>
-
using namespace libsnark;
template<typename GroupT>
el = GroupT::zero();
el.to_special();
result = base.mixed_add(el);
- EXPECT_EQ(result, base + el);
+ assert(result == base + el);
base = GroupT::zero();
el = GroupT::random_element();
el.to_special();
result = base.mixed_add(el);
- EXPECT_EQ(result, base + el);
+ assert(result == base + el);
base = GroupT::random_element();
el = GroupT::zero();
el.to_special();
result = base.mixed_add(el);
- EXPECT_EQ(result, base + el);
+ assert(result == base + el);
base = GroupT::random_element();
el = GroupT::random_element();
el.to_special();
result = base.mixed_add(el);
- EXPECT_EQ(result, base + el);
+ assert(result == base + el);
base = GroupT::random_element();
el = base;
el.to_special();
result = base.mixed_add(el);
- EXPECT_EQ(result, base.dbl());
+ assert(result == base.dbl());
}
template<typename GroupT>
bigint<1> randsum = bigint<1>("121160274");
GroupT zero = GroupT::zero();
- EXPECT_EQ(zero, zero);
+ assert(zero == zero);
GroupT one = GroupT::one();
- EXPECT_EQ(one, one);
+ assert(one == one);
GroupT two = bigint<1>(2l) * GroupT::one();
- EXPECT_EQ(two, two);
+ assert(two == two);
GroupT five = bigint<1>(5l) * GroupT::one();
GroupT three = bigint<1>(3l) * GroupT::one();
GroupT four = bigint<1>(4l) * GroupT::one();
- EXPECT_EQ(two+five, three+four);
+ assert(two+five == three+four);
GroupT a = GroupT::random_element();
GroupT b = GroupT::random_element();
- EXPECT_NE(one, zero);
- EXPECT_NE(a, zero);
- EXPECT_NE(a, one);
+ assert(one != zero);
+ assert(a != zero);
+ assert(a != one);
- EXPECT_NE(b, zero);
- EXPECT_NE(b, one);
+ assert(b != zero);
+ assert(b != one);
- EXPECT_EQ(a.dbl(), a + a);
- EXPECT_EQ(b.dbl(), b + b);
- EXPECT_EQ(one.add(two), three);
- EXPECT_EQ(two.add(one), three);
- EXPECT_EQ(a + b, b + a);
- EXPECT_EQ(a - a, zero);
- EXPECT_EQ(a - b, a + (-b));
- EXPECT_EQ(a - b, (-b) + a);
+ assert(a.dbl() == a + a);
+ assert(b.dbl() == b + b);
+ assert(one.add(two) == three);
+ assert(two.add(one) == three);
+ assert(a + b == b + a);
+ assert(a - a == zero);
+ assert(a - b == a + (-b));
+ assert(a - b == (-b) + a);
// handle special cases
- EXPECT_EQ(zero + (-a), -a);
- EXPECT_EQ(zero - a, -a);
- EXPECT_EQ(a - zero, a);
- EXPECT_EQ(a + zero, a);
- EXPECT_EQ(zero + a, a);
+ assert(zero + (-a) == -a);
+ assert(zero - a == -a);
+ assert(a - zero == a);
+ assert(a + zero == a);
+ assert(zero + a == a);
- EXPECT_EQ((a + b).dbl(), (a + b) + (b + a));
- EXPECT_EQ(bigint<1>("2") * (a + b), (a + b) + (b + a));
+ assert((a + b).dbl() == (a + b) + (b + a));
+ assert(bigint<1>("2") * (a + b) == (a + b) + (b + a));
- EXPECT_EQ((rand1 * a) + (rand2 * a), (randsum * a));
+ assert((rand1 * a) + (rand2 * a) == (randsum * a));
- EXPECT_EQ(GroupT::order() * a, zero);
- EXPECT_EQ(GroupT::order() * one, zero);
- EXPECT_NE((GroupT::order() * a) - a, zero);
- EXPECT_NE((GroupT::order() * one) - one, zero);
+ assert(GroupT::order() * a == zero);
+ assert(GroupT::order() * one == zero);
+ assert((GroupT::order() * a) - a != zero);
+ assert((GroupT::order() * one) - one != zero);
test_mixed_add<GroupT>();
}
void test_mul_by_q()
{
GroupT a = GroupT::random_element();
- EXPECT_EQ((GroupT::base_field_char()*a), a.mul_by_q());
+ assert((GroupT::base_field_char()*a) == a.mul_by_q());
}
template<typename GroupT>
ss << g;
GroupT gg;
ss >> gg;
- EXPECT_EQ(g, gg);
+ assert(g == gg);
/* use a random point in next iteration */
g = GroupT::random_element();
}
}
-TEST(algebra, groups)
+int main(void)
{
+/*
+ edwards_pp::init_public_params();
+ test_group<G1<edwards_pp> >();
+ test_output<G1<edwards_pp> >();
+ test_group<G2<edwards_pp> >();
+ test_output<G2<edwards_pp> >();
+ test_mul_by_q<G2<edwards_pp> >();
+
+ mnt4_pp::init_public_params();
+ test_group<G1<mnt4_pp> >();
+ test_output<G1<mnt4_pp> >();
+ test_group<G2<mnt4_pp> >();
+ test_output<G2<mnt4_pp> >();
+ test_mul_by_q<G2<mnt4_pp> >();
+
+ mnt6_pp::init_public_params();
+ test_group<G1<mnt6_pp> >();
+ test_output<G1<mnt6_pp> >();
+ test_group<G2<mnt6_pp> >();
+ test_output<G2<mnt6_pp> >();
+ test_mul_by_q<G2<mnt6_pp> >();
+*/
alt_bn128_pp::init_public_params();
test_group<G1<alt_bn128_pp> >();
test_output<G1<alt_bn128_pp> >();
#define BASIC_RADIX2_DOMAIN_TCC_
#include "algebra/evaluation_domain/domains/basic_radix2_domain_aux.hpp"
+#include "common/assert_except.hpp"
namespace libsnark {
template<typename FieldT>
basic_radix2_domain<FieldT>::basic_radix2_domain(const size_t m) : evaluation_domain<FieldT>(m)
{
- assert(m > 1);
+ assert_except(m > 1);
const size_t logm = log2(m);
- assert(logm <= (FieldT::s));
+ assert_except(logm <= (FieldT::s));
omega = get_root_of_unity<FieldT>(m);
}
void basic_radix2_domain<FieldT>::FFT(std::vector<FieldT> &a)
{
enter_block("Execute FFT");
- assert(a.size() == this->m);
+ assert_except(a.size() == this->m);
_basic_radix2_FFT(a, omega);
leave_block("Execute FFT");
}
void basic_radix2_domain<FieldT>::iFFT(std::vector<FieldT> &a)
{
enter_block("Execute inverse FFT");
- assert(a.size() == this->m);
+ assert_except(a.size() == this->m);
_basic_radix2_FFT(a, omega.inverse());
const FieldT sconst = FieldT(a.size()).inverse();
template<typename FieldT>
void basic_radix2_domain<FieldT>::add_poly_Z(const FieldT &coeff, std::vector<FieldT> &H)
{
- assert(H.size() == this->m+1);
+ assert_except(H.size() == this->m+1);
H[this->m] += coeff;
H[0] -= coeff;
}
#include "algebra/fields/field_utils.hpp"
#include "common/profiling.hpp"
#include "common/utils.hpp"
+#include "common/assert_except.hpp"
namespace libsnark {
void _basic_serial_radix2_FFT(std::vector<FieldT> &a, const FieldT &omega)
{
const size_t n = a.size(), logn = log2(n);
- assert(n == (1u << logn));
+ assert_except(n == (1u << logn));
/* swapping in place (from Storer's book) */
for (size_t k = 0; k < n; ++k)
template<typename FieldT>
void _basic_parallel_radix2_FFT_inner(std::vector<FieldT> &a, const FieldT &omega, const size_t log_cpus)
{
- const size_t num_cpus = 1ul<<log_cpus;
+ const size_t num_cpus = UINT64_C(1)<<log_cpus;
const size_t m = a.size();
const size_t log_m = log2(m);
- assert(m == 1ul<<log_m);
+ assert_except(m == UINT64_C(1)<<log_m);
if (log_m < log_cpus)
{
std::vector<std::vector<FieldT> > tmp(num_cpus);
for (size_t j = 0; j < num_cpus; ++j)
{
- tmp[j].resize(1ul<<(log_m-log_cpus), FieldT::zero());
+ tmp[j].resize(UINT64_C(1)<<(log_m-log_cpus), FieldT::zero());
}
#ifdef MULTICORE
const FieldT omega_step = omega^(j<<(log_m - log_cpus));
FieldT elt = FieldT::one();
- for (size_t i = 0; i < 1ul<<(log_m - log_cpus); ++i)
+ for (size_t i = 0; i < UINT64_C(1)<<(log_m - log_cpus); ++i)
{
for (size_t s = 0; s < num_cpus; ++s)
{
#endif
for (size_t i = 0; i < num_cpus; ++i)
{
- for (size_t j = 0; j < 1ul<<(log_m - log_cpus); ++j)
+ for (size_t j = 0; j < UINT64_C(1)<<(log_m - log_cpus); ++j)
{
// now: i = idx >> (log_m - log_cpus) and j = idx % (1u << (log_m - log_cpus)), for idx = ((i<<(log_m-log_cpus))+j) % (1u << log_m)
a[(j<<log_cpus) + i] = tmp[i][j];
return std::vector<FieldT>(1, FieldT::one());
}
- assert(m == (1u << log2(m)));
+ assert_except(m == (1u << log2(m)));
const FieldT omega = get_root_of_unity<FieldT>(m);
a choice of domain S with size ~m that has been selected so to optimize
- computations of Lagrange polynomials, and
- FFT/iFFT computations.
- An evaluation domain also provides other functions, e.g., accessing
+ An evaluation domain also provides other other functions, e.g., accessing
individual elements in S or evaluating its vanishing polynomial.
The descriptions below make use of the definition of a *Lagrange polynomial*,
* The inputs are:
* - an integer m
* - a domain S = (a_{0},...,a_{m-1}) of size m
- * - a field element t
+ * - a field element element t
* - an index idx in {0,...,m-1}
* The output is the polynomial L_{idx,S}(z) evaluated at z = t.
*/
#include <cassert>
#include "algebra/fields/field_utils.hpp"
#include "algebra/evaluation_domain/domains/basic_radix2_domain.hpp"
+#include "common/assert_except.hpp"
namespace libsnark {
template<typename FieldT>
std::shared_ptr<evaluation_domain<FieldT> > get_evaluation_domain(const size_t min_size)
{
- assert(min_size > 1);
+ assert_except(min_size > 1);
const size_t log_min_size = log2(min_size);
- assert(log_min_size <= (FieldT::s+1));
+ assert_except(log_min_size <= (FieldT::s+1));
std::shared_ptr<evaluation_domain<FieldT> > result;
if (min_size == (1u << log_min_size))
{
print_indent(); printf("* Selected domain: extended_radix2\n");
}
- assert(0);
+ assert_except(0);
}
else
{
}
else
{
- const size_t big = 1ul<<(log2(min_size)-1);
+ const size_t big = UINT64_C(1)<<(log2(min_size)-1);
const size_t small = min_size - big;
- const size_t rounded_small = (1ul<<log2(small));
+ const size_t rounded_small = (UINT64_C(1)<<log2(small));
if (big == rounded_small)
{
if (log2(big + rounded_small) < FieldT::s+1)
{
print_indent(); printf("* Selected domain: extended_radix2\n");
}
- assert(0);
+ assert_except(0);
}
}
else
{
print_indent(); printf("* Selected domain: step_radix2\n");
}
- assert(0);
+ assert_except(0);
}
}
template<typename FieldT>
FieldT lagrange_eval(const size_t m, const std::vector<FieldT> &domain, const FieldT &t, const size_t idx)
{
- assert(m == domain.size());
- assert(idx < m);
+ assert_except(m == domain.size());
+ assert_except(idx < m);
FieldT num = FieldT::one();
FieldT denom = FieldT::one();
FieldT power(const FieldT &base, const bigint<m> &exponent);
template<typename FieldT>
-FieldT power(const FieldT &base, const unsigned long exponent);
+FieldT power(const FieldT &base, const uint64_t exponent);
} // libsnark
bool found_one = false;
- for (long i = exponent.max_bits() - 1; i >= 0; --i)
+ for (int64_t i = exponent.max_bits() - 1; i >= 0; --i)
{
if (found_one)
{
}
template<typename FieldT>
-FieldT power(const FieldT &base, const unsigned long exponent)
+FieldT power(const FieldT &base, const uint64_t exponent)
{
return power<FieldT>(base, bigint<1>(exponent));
}
mp_limb_t data[n] = {0};
bigint() = default;
- bigint(const unsigned long x); /// Initialize from a small integer
+ bigint(const uint64_t x); /// Initalize from a small integer
bigint(const char* s); /// Initialize from a string containing an integer in decimal notation
bigint(const mpz_t r); /// Initialize from MPZ element
size_t max_bits() const { return n * GMP_NUMB_BITS; }
size_t num_bits() const;
- unsigned long as_ulong() const; /* return the last limb of the integer */
+ uint64_t as_ulong() const; /* return the last limb of the integer */
void to_mpz(mpz_t r) const;
bool test_bit(const std::size_t bitno) const;
#include <climits>
#include <cstring>
#include "sodium.h"
+#include "common/assert_except.hpp"
namespace libsnark {
template<mp_size_t n>
-bigint<n>::bigint(const unsigned long x) /// Initialize from a small integer
+bigint<n>::bigint(const uint64_t x) /// Initalize from a small integer
{
- static_assert(ULONG_MAX <= GMP_NUMB_MAX, "unsigned long does not fit in a GMP limb");
+ static_assert(UINT64_MAX <= GMP_NUMB_MAX, "uint64_t does not fit in a GMP limb");
this->data[0] = x;
}
for (size_t i = 0; i < l; ++i)
{
- assert(s[i] >= '0' && s[i] <= '9');
+ assert_except(s[i] >= '0' && s[i] <= '9');
s_copy[i] = s[i] - '0';
}
mp_size_t limbs_written = mpn_set_str(this->data, s_copy, l, 10);
- assert(limbs_written <= n);
+ assert_except(limbs_written <= n);
delete[] s_copy;
}
mpz_fdiv_q_2exp(k, k, GMP_NUMB_BITS);
}
- assert(mpz_sgn(k) == 0);
+ assert_except(mpz_sgn(k) == 0);
mpz_clear(k);
}
size_t bigint<n>::num_bits() const
{
/*
- for (long i = max_bits(); i >= 0; --i)
+ for (int64_t i = max_bits(); i >= 0; --i)
{
if (this->test_bit(i))
{
return 0;
*/
- for (long i = n-1; i >= 0; --i)
+ for (int64_t i = n-1; i >= 0; --i)
{
mp_limb_t x = this->data[i];
if (x == 0)
}
else
{
- return ((i+1) * GMP_NUMB_BITS) - __builtin_clzl(x);
+ return ((i+1) * GMP_NUMB_BITS) - __builtin_clzll(x);
}
}
return 0;
}
template<mp_size_t n>
-unsigned long bigint<n>::as_ulong() const
+uint64_t bigint<n>::as_ulong() const
{
return this->data[0];
}
const bigint<n>& dividend, const bigint<d>& divisor)
{
static_assert(n >= d, "dividend must not be smaller than divisor for bigint::div_qr");
- assert(divisor.data[d-1] != 0);
+ assert_except(divisor.data[d-1] != 0);
mpn_tdiv_qr(quotient.data, remainder.data, 0, dividend.data, n, divisor.data, d);
}
template<mp_size_t n>
bigint<n>& bigint<n>::randomize()
{
- assert(GMP_NUMB_BITS == sizeof(mp_limb_t) * 8);
+ assert_except(GMP_NUMB_BITS == sizeof(mp_limb_t) * 8);
randombytes_buf(this->data, sizeof(mp_limb_t) * n);
for (size_t i = 0; i < l; ++i)
{
- assert(s[i] >= '0' && s[i] <= '9');
+ assert_except(s[i] >= '0' && s[i] <= '9');
s_copy[i] = s[i] - '0';
}
mp_size_t limbs_written = mpn_set_str(b.data, s_copy, l, 10);
- assert(limbs_written <= n);
+ assert_except(limbs_written <= n);
delete[] s_copy;
#endif
// returns root of unity of order n (for n a power of 2), if one exists
template<typename FieldT>
-FieldT get_root_of_unity(const size_t n);
+FieldT get_root_of_unity(const uint64_t n);
template<typename FieldT>
-std::vector<FieldT> pack_int_vector_into_field_element_vector(const std::vector<size_t> &v, const size_t w);
+std::vector<FieldT> pack_int_vector_into_field_element_vector(const std::vector<uint64_t> &v, const uint64_t w);
template<typename FieldT>
-std::vector<FieldT> pack_bit_vector_into_field_element_vector(const bit_vector &v, const size_t chunk_bits);
+std::vector<FieldT> pack_bit_vector_into_field_element_vector(const bit_vector &v, const uint64_t chunk_bits);
template<typename FieldT>
std::vector<FieldT> pack_bit_vector_into_field_element_vector(const bit_vector &v);
bit_vector convert_field_element_to_bit_vector(const FieldT &el);
template<typename FieldT>
-bit_vector convert_field_element_to_bit_vector(const FieldT &el, const size_t bitcount);
+bit_vector convert_field_element_to_bit_vector(const FieldT &el, const uint64_t bitcount);
template<typename FieldT>
FieldT convert_bit_vector_to_field_element(const bit_vector &v);
#define FIELD_UTILS_TCC_
#include "common/utils.hpp"
+#include "common/assert_except.hpp"
namespace libsnark {
}
template<typename FieldT>
-FieldT get_root_of_unity(const size_t n)
+FieldT get_root_of_unity(const uint64_t n)
{
- const size_t logn = log2(n);
- assert(n == (1u << logn));
- assert(logn <= FieldT::s);
+ const uint64_t logn = log2(n);
+ assert_except(n == (1u << logn));
+ assert_except(logn <= FieldT::s);
FieldT omega = FieldT::root_of_unity;
- for (size_t i = FieldT::s; i > logn; --i)
+ for (uint64_t i = FieldT::s; i > logn; --i)
{
omega *= omega;
}
}
template<typename FieldT>
-std::vector<FieldT> pack_int_vector_into_field_element_vector(const std::vector<size_t> &v, const size_t w)
+std::vector<FieldT> pack_int_vector_into_field_element_vector(const std::vector<uint64_t> &v, const uint64_t w)
{
- const size_t chunk_bits = FieldT::capacity();
- const size_t repacked_size = div_ceil(v.size() * w, chunk_bits);
+ const uint64_t chunk_bits = FieldT::capacity();
+ const uint64_t repacked_size = div_ceil(v.size() * w, chunk_bits);
std::vector<FieldT> result(repacked_size);
- for (size_t i = 0; i < repacked_size; ++i)
+ for (uint64_t i = 0; i < repacked_size; ++i)
{
bigint<FieldT::num_limbs> b;
- for (size_t j = 0; j < chunk_bits; ++j)
+ for (uint64_t j = 0; j < chunk_bits; ++j)
{
- const size_t word_index = (i * chunk_bits + j) / w;
- const size_t pos_in_word = (i * chunk_bits + j) % w;
- const size_t word_or_0 = (word_index < v.size() ? v[word_index] : 0);
- const size_t bit = (word_or_0 >> pos_in_word) & 1;
+ const uint64_t word_index = (i * chunk_bits + j) / w;
+ const uint64_t pos_in_word = (i * chunk_bits + j) % w;
+ const uint64_t word_or_0 = (word_index < v.size() ? v[word_index] : 0);
+ const uint64_t bit = (word_or_0 >> pos_in_word) & 1;
b.data[j / GMP_NUMB_BITS] |= bit << (j % GMP_NUMB_BITS);
}
}
template<typename FieldT>
-std::vector<FieldT> pack_bit_vector_into_field_element_vector(const bit_vector &v, const size_t chunk_bits)
+std::vector<FieldT> pack_bit_vector_into_field_element_vector(const bit_vector &v, const uint64_t chunk_bits)
{
- assert(chunk_bits <= FieldT::capacity());
+ assert_except(chunk_bits <= FieldT::capacity());
- const size_t repacked_size = div_ceil(v.size(), chunk_bits);
+ const uint64_t repacked_size = div_ceil(v.size(), chunk_bits);
std::vector<FieldT> result(repacked_size);
for (size_t i = 0; i < repacked_size; ++i)
}
template<typename FieldT>
-bit_vector convert_field_element_to_bit_vector(const FieldT &el, const size_t bitcount)
+bit_vector convert_field_element_to_bit_vector(const FieldT &el, const uint64_t bitcount)
{
bit_vector result = convert_field_element_to_bit_vector(el);
result.resize(bitcount);
template<typename FieldT>
FieldT convert_bit_vector_to_field_element(const bit_vector &v)
{
- assert(v.size() <= FieldT::size_in_bits());
+ assert_except(v.size() <= FieldT::size_in_bits());
FieldT res = FieldT::zero();
FieldT c = FieldT::one();
for (auto el : vec)
{
- assert(!el.is_zero());
+ assert_except(!el.is_zero());
prod.emplace_back(acc);
acc = acc * el;
}
FieldT acc_inverse = acc.inverse();
- for (long i = vec.size()-1; i >= 0; --i)
+ for (int64_t i = vec.size()-1; i >= 0; --i)
{
const FieldT old_el = vec[i];
vec[i] = acc_inverse * prod[i];
* The implementation is mostly a wrapper around GMP's MPN (constant-size integers).
* But for the integer sizes of interest for libsnark (3 to 5 limbs of 64 bits each),
* we implement performance-critical routines, like addition and multiplication,
- * using hand-optimized assembly code.
+ * using hand-optimzied assembly code.
*/
template<mp_size_t n, const bigint<n>& modulus>
class Fp_model {
static const mp_size_t num_limbs = n;
static const constexpr bigint<n>& mod = modulus;
#ifdef PROFILE_OP_COUNTS
- static long long add_cnt;
- static long long sub_cnt;
- static long long mul_cnt;
- static long long sqr_cnt;
- static long long inv_cnt;
+ static int64_t add_cnt;
+ static int64_t sub_cnt;
+ static int64_t mul_cnt;
+ static int64_t sqr_cnt;
+ static int64_t inv_cnt;
#endif
- static size_t num_bits;
+ static uint64_t num_bits;
static bigint<n> euler; // (modulus-1)/2
- static size_t s; // modulus = 2^s * t + 1
+ static uint64_t s; // modulus = 2^s * t + 1
static bigint<n> t; // with t odd
static bigint<n> t_minus_1_over_2; // (t-1)/2
static Fp_model<n, modulus> nqr; // a quadratic nonresidue
Fp_model() {};
Fp_model(const bigint<n> &b);
- Fp_model(const long x, const bool is_unsigned=false);
+ Fp_model(const int64_t x, const bool is_unsigned=false);
- void set_ulong(const unsigned long x);
+ void set_ulong(const uint64_t x);
void mul_reduce(const bigint<n> &other);
/* Return the last limb of the standard representation of the
field element. E.g. on 64-bit architectures Fp(123).as_ulong()
and Fp(2^64+123).as_ulong() would both return 123. */
- unsigned long as_ulong() const;
+ uint64_t as_ulong() const;
bool operator==(const Fp_model& other) const;
bool operator!=(const Fp_model& other) const;
Fp_model& operator+=(const Fp_model& other);
Fp_model& operator-=(const Fp_model& other);
Fp_model& operator*=(const Fp_model& other);
- Fp_model& operator^=(const unsigned long pow);
+ Fp_model& operator^=(const uint64_t pow);
template<mp_size_t m>
Fp_model& operator^=(const bigint<m> &pow);
Fp_model inverse() const;
Fp_model sqrt() const; // HAS TO BE A SQUARE (else does not terminate)
- Fp_model operator^(const unsigned long pow) const;
+ Fp_model operator^(const uint64_t pow) const;
template<mp_size_t m>
Fp_model operator^(const bigint<m> &pow) const;
- static size_t size_in_bits() { return num_bits; }
- static size_t capacity() { return num_bits - 1; }
+ static uint64_t size_in_bits() { return num_bits; }
+ static uint64_t capacity() { return num_bits - 1; }
static bigint<n> field_char() { return modulus; }
static Fp_model<n, modulus> zero();
#ifdef PROFILE_OP_COUNTS
template<mp_size_t n, const bigint<n>& modulus>
-long long Fp_model<n, modulus>::add_cnt = 0;
+int64_t Fp_model<n, modulus>::add_cnt = 0;
template<mp_size_t n, const bigint<n>& modulus>
-long long Fp_model<n, modulus>::sub_cnt = 0;
+int64_t Fp_model<n, modulus>::sub_cnt = 0;
template<mp_size_t n, const bigint<n>& modulus>
-long long Fp_model<n, modulus>::mul_cnt = 0;
+int64_t Fp_model<n, modulus>::mul_cnt = 0;
template<mp_size_t n, const bigint<n>& modulus>
-long long Fp_model<n, modulus>::sqr_cnt = 0;
+int64_t Fp_model<n, modulus>::sqr_cnt = 0;
template<mp_size_t n, const bigint<n>& modulus>
-long long Fp_model<n, modulus>::inv_cnt = 0;
+int64_t Fp_model<n, modulus>::inv_cnt = 0;
#endif
template<mp_size_t n, const bigint<n>& modulus>
-size_t Fp_model<n, modulus>::num_bits;
+uint64_t Fp_model<n, modulus>::num_bits;
template<mp_size_t n, const bigint<n>& modulus>
bigint<n> Fp_model<n, modulus>::euler;
template<mp_size_t n, const bigint<n>& modulus>
-size_t Fp_model<n, modulus>::s;
+uint64_t Fp_model<n, modulus>::s;
template<mp_size_t n, const bigint<n>& modulus>
bigint<n> Fp_model<n, modulus>::t;
/* calculate res = res + k * mod * b^i */
mp_limb_t carryout = mpn_addmul_1(res+i, modulus.data, n, k);
carryout = mpn_add_1(res+n+i, res+n+i, n-i, carryout);
- assert(carryout == 0);
+ assert_except(carryout == 0);
}
if (mpn_cmp(res+n, modulus.data, n) >= 0)
{
const mp_limb_t borrow = mpn_sub(res+n, res+n, n, modulus.data, n);
- assert(borrow == 0);
+ assert_except(borrow == 0);
}
mpn_copyi(this->mont_repr.data, res+n, n);
}
template<mp_size_t n, const bigint<n>& modulus>
-Fp_model<n,modulus>::Fp_model(const long x, const bool is_unsigned)
+Fp_model<n,modulus>::Fp_model(const int64_t x, const bool is_unsigned)
{
if (is_unsigned || x >= 0)
{
else
{
const mp_limb_t borrow = mpn_sub_1(this->mont_repr.data, modulus.data, n, -x);
- assert(borrow == 0);
+ assert_except(borrow == 0);
}
mul_reduce(Rsquared);
}
template<mp_size_t n, const bigint<n>& modulus>
-void Fp_model<n,modulus>::set_ulong(const unsigned long x)
+void Fp_model<n,modulus>::set_ulong(const uint64_t x)
{
this->mont_repr.clear();
this->mont_repr.data[0] = x;
}
template<mp_size_t n, const bigint<n>& modulus>
-unsigned long Fp_model<n,modulus>::as_ulong() const
+uint64_t Fp_model<n,modulus>::as_ulong() const
{
return this->as_bigint().as_ulong();
}
if (carry || mpn_cmp(scratch, modulus.data, n) >= 0)
{
const mp_limb_t borrow = mpn_sub(scratch, scratch, n+1, modulus.data, n);
- assert(borrow == 0);
+ assert_except(borrow == 0);
}
mpn_copyi(this->mont_repr.data, scratch, n);
}
const mp_limb_t borrow = mpn_sub(scratch, scratch, n+1, other.mont_repr.data, n);
- assert(borrow == 0);
+ assert_except(borrow == 0);
mpn_copyi(this->mont_repr.data, scratch, n);
}
}
template<mp_size_t n, const bigint<n>& modulus>
-Fp_model<n,modulus>& Fp_model<n,modulus>::operator^=(const unsigned long pow)
+Fp_model<n,modulus>& Fp_model<n,modulus>::operator^=(const uint64_t pow)
{
(*this) = power<Fp_model<n, modulus> >(*this, pow);
return (*this);
}
template<mp_size_t n, const bigint<n>& modulus>
-Fp_model<n,modulus> Fp_model<n,modulus>::operator^(const unsigned long pow) const
+Fp_model<n,modulus> Fp_model<n,modulus>::operator^(const uint64_t pow) const
{
Fp_model<n, modulus> r(*this);
return (r ^= pow);
this->inv_cnt++;
#endif
- assert(!this->is_zero());
+ assert_except(!this->is_zero());
bigint<n> g; /* gp should have room for vn = n limbs */
/* computes gcd(u, v) = g = u*s + v*t, so s*u will be 1 (mod v) */
const mp_size_t gn = mpn_gcdext(g.data, s, &sn, this->mont_repr.data, n, v.data, n);
- assert(gn == 1 && g.data[0] == 1); /* inverse exists */
+ assert_except(gn == 1 && g.data[0] == 1); /* inverse exists */
mp_limb_t q; /* division result fits into q, as sn <= n+1 */
/* sn < 0 indicates negative sn; will fix up later */
if (sn < 0)
{
const mp_limb_t borrow = mpn_sub_n(this->mont_repr.data, modulus.data, this->mont_repr.data, n);
- assert(borrow == 0);
+ assert_except(borrow == 0);
}
mul_reduce(Rcubed);
r.mont_repr.randomize();
/* clear all bits higher than MSB of modulus */
- size_t bitno = GMP_NUMB_BITS * n - 1;
+ uint64_t bitno = GMP_NUMB_BITS * n - 1;
while (modulus.test_bit(bitno) == false)
{
- const std::size_t part = bitno/GMP_NUMB_BITS;
- const std::size_t bit = bitno - (GMP_NUMB_BITS*part);
+ const uint64_t part = bitno/GMP_NUMB_BITS;
+ const uint64_t bit = bitno - (GMP_NUMB_BITS*part);
- r.mont_repr.data[part] &= ~(1ul<<bit);
+ r.mont_repr.data[part] &= ~(1ull<<bit);
bitno--;
}
Fp_model<n,modulus> one = Fp_model<n,modulus>::one();
- size_t v = Fp_model<n,modulus>::s;
+ uint64_t v = Fp_model<n,modulus>::s;
Fp_model<n,modulus> z = Fp_model<n,modulus>::nqr_to_t;
Fp_model<n,modulus> w = (*this)^Fp_model<n,modulus>::t_minus_1_over_2;
Fp_model<n,modulus> x = (*this) * w;
while (b != one)
{
- size_t m = 0;
+ uint64_t m = 0;
Fp_model<n,modulus> b2m = b;
while (b2m != one)
{
Fp12_2over3over2_model squared_karatsuba() const;
Fp12_2over3over2_model squared_complex() const;
Fp12_2over3over2_model inverse() const;
- Fp12_2over3over2_model Frobenius_map(unsigned long power) const;
+ Fp12_2over3over2_model Frobenius_map(uint64_t power) const;
Fp12_2over3over2_model unitary_inverse() const;
Fp12_2over3over2_model cyclotomic_squared() const;
Fp12_2over3over2_model cyclotomic_exp(const bigint<m> &exponent) const;
static bigint<n> base_field_char() { return modulus; }
- static size_t extension_degree() { return 12; }
+ static uint64_t extension_degree() { return 12; }
friend std::ostream& operator<< <n, modulus>(std::ostream &out, const Fp12_2over3over2_model<n, modulus> &el);
friend std::istream& operator>> <n, modulus>(std::istream &in, Fp12_2over3over2_model<n, modulus> &el);
}
template<mp_size_t n, const bigint<n>& modulus>
-Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::Frobenius_map(unsigned long power) const
+Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::Frobenius_map(uint64_t power) const
{
return Fp12_2over3over2_model<n,modulus>(c0.Frobenius_map(power),
Frobenius_coeffs_c1[power % 12] * c1.Frobenius_map(power));
Fp12_2over3over2_model<n,modulus> res = Fp12_2over3over2_model<n,modulus>::one();
bool found_one = false;
- for (long i = m-1; i >= 0; --i)
+ for (int64_t i = m-1; i >= 0; --i)
{
- for (long j = GMP_NUMB_BITS - 1; j >= 0; --j)
+ for (int64_t j = GMP_NUMB_BITS - 1; j >= 0; --j)
{
if (found_one)
{
res = res.cyclotomic_squared();
}
- if (exponent.data[i] & (1ul<<j))
+ if (exponent.data[i] & (UINT64_C(1)<<j))
{
found_one = true;
res = res * (*this);
{
v.clear();
- size_t s;
+ uint64_t s;
in >> s;
char b;
typedef Fp_model<n, modulus> my_Fp;
static bigint<2*n> euler; // (modulus^2-1)/2
- static size_t s; // modulus^2 = 2^s * t + 1
+ static uint64_t s; // modulus^2 = 2^s * t + 1
static bigint<2*n> t; // with t odd
static bigint<2*n> t_minus_1_over_2; // (t-1)/2
static my_Fp non_residue; // X^4-non_residue irreducible over Fp; used for constructing Fp2 = Fp[X] / (X^2 - non_residue)
Fp2_model operator-() const;
Fp2_model squared() const; // default is squared_complex
Fp2_model inverse() const;
- Fp2_model Frobenius_map(unsigned long power) const;
+ Fp2_model Frobenius_map(uint64_t power) const;
Fp2_model sqrt() const; // HAS TO BE A SQUARE (else does not terminate)
Fp2_model squared_karatsuba() const;
Fp2_model squared_complex() const;
template<mp_size_t m>
Fp2_model operator^(const bigint<m> &other) const;
- static size_t size_in_bits() { return 2*my_Fp::size_in_bits(); }
+ static uint64_t size_in_bits() { return 2*my_Fp::size_in_bits(); }
static bigint<n> base_field_char() { return modulus; }
friend std::ostream& operator<< <n, modulus>(std::ostream &out, const Fp2_model<n, modulus> &el);
bigint<2*n> Fp2_model<n, modulus>::euler;
template<mp_size_t n, const bigint<n>& modulus>
-size_t Fp2_model<n, modulus>::s;
+uint64_t Fp2_model<n, modulus>::s;
template<mp_size_t n, const bigint<n>& modulus>
bigint<2*n> Fp2_model<n, modulus>::t;
}
template<mp_size_t n, const bigint<n>& modulus>
-Fp2_model<n,modulus> Fp2_model<n,modulus>::Frobenius_map(unsigned long power) const
+Fp2_model<n,modulus> Fp2_model<n,modulus>::Frobenius_map(uint64_t power) const
{
return Fp2_model<n,modulus>(c0,
Frobenius_coeffs_c1[power % 2] * c1);
Fp2_model<n,modulus> one = Fp2_model<n,modulus>::one();
- size_t v = Fp2_model<n,modulus>::s;
+ unsigned long long v = Fp2_model<n,modulus>::s;
Fp2_model<n,modulus> z = Fp2_model<n,modulus>::nqr_to_t;
Fp2_model<n,modulus> w = (*this)^Fp2_model<n,modulus>::t_minus_1_over_2;
Fp2_model<n,modulus> x = (*this) * w;
while (b != one)
{
- size_t m = 0;
+ unsigned long long m = 0;
Fp2_model<n,modulus> b2m = b;
while (b2m != one)
{
{
v.clear();
- size_t s;
+ unsigned long long s;
in >> s;
char b;
Fp6_3over2_model operator-() const;
Fp6_3over2_model squared() const;
Fp6_3over2_model inverse() const;
- Fp6_3over2_model Frobenius_map(unsigned long power) const;
+ Fp6_3over2_model Frobenius_map(uint64_t power) const;
static my_Fp2 mul_by_non_residue(const my_Fp2 &elt);
Fp6_3over2_model operator^(const bigint<m> &other) const;
static bigint<n> base_field_char() { return modulus; }
- static size_t extension_degree() { return 6; }
+ static uint64_t extension_degree() { return 6; }
friend std::ostream& operator<< <n, modulus>(std::ostream &out, const Fp6_3over2_model<n, modulus> &el);
friend std::istream& operator>> <n, modulus>(std::istream &in, Fp6_3over2_model<n, modulus> &el);
}
template<mp_size_t n, const bigint<n>& modulus>
-Fp6_3over2_model<n,modulus> Fp6_3over2_model<n,modulus>::Frobenius_map(unsigned long power) const
+Fp6_3over2_model<n,modulus> Fp6_3over2_model<n,modulus>::Frobenius_map(uint64_t power) const
{
return Fp6_3over2_model<n,modulus>(c0.Frobenius_map(power),
Frobenius_coeffs_c1[power % 6] * c1.Frobenius_map(power),
{
v.clear();
- size_t s;
+ uint64_t s;
in >> s;
char b;
#include "algebra/fields/bigint.hpp"
-#include <gtest/gtest.h>
-
using namespace libsnark;
-TEST(algebra, bigint)
+void test_bigint()
{
- static_assert(ULONG_MAX == 0xFFFFFFFFFFFFFFFFul, "unsigned long not 64-bit");
+ static_assert(UINT64_MAX == 0xFFFFFFFFFFFFFFFFul, "uint64_t not 64-bit");
static_assert(GMP_NUMB_BITS == 64, "GMP limb not 64-bit");
const char *b1_decimal = "76749407";
const char *b2_binary = "0000000000000000000000000000010101111101101000000110100001011010"
"1101101010001001000001101000101000100110011001110001111110100010";
- bigint<1> b0 = bigint<1>(0ul);
+ bigint<1> b0 = bigint<1>(UINT64_C(0));
bigint<1> b1 = bigint<1>(b1_decimal);
bigint<2> b2 = bigint<2>(b2_decimal);
- EXPECT_EQ(b0.as_ulong(), 0ul);
- EXPECT_TRUE(b0.is_zero());
- EXPECT_EQ(b1.as_ulong(), 76749407ul);
- EXPECT_FALSE(b1.is_zero());
- EXPECT_EQ(b2.as_ulong(), 15747124762497195938ul);
- EXPECT_FALSE(b2.is_zero());
- EXPECT_NE(b0, b1);
- EXPECT_FALSE(b0 == b1);
-
- EXPECT_EQ(b2.max_bits(), 128);
- EXPECT_EQ(b2.num_bits(), 99);
+ assert(b0.as_ulong() == UINT64_C(0));
+ assert(b0.is_zero());
+ assert(b1.as_ulong() == UINT64_C(76749407));
+ assert(!(b1.is_zero()));
+ assert(b2.as_ulong() == UINT64_C(15747124762497195938));
+ assert(!(b2.is_zero()));
+ assert(b0 != b1);
+ assert(!(b0 == b1));
+
+ assert(b2.max_bits() == 128);
+ assert(b2.num_bits() == 99);
for (size_t i = 0; i < 128; i++) {
- EXPECT_EQ(b2.test_bit(i), (b2_binary[127-i] == '1'));
+ assert(b2.test_bit(i) == (b2_binary[127-i] == '1'));
}
bigint<3> b3 = b2 * b1;
- EXPECT_EQ(b3, bigint<3>(b3_decimal));
- EXPECT_FALSE(b3.is_zero());
+ assert(b3 == bigint<3>(b3_decimal));
+ assert(!(b3.is_zero()));
bigint<3> b3a { b3 };
- EXPECT_EQ(b3a, bigint<3>(b3_decimal));
- EXPECT_EQ(b3a, b3);
- EXPECT_FALSE(b3a.is_zero());
+ assert(b3a == bigint<3>(b3_decimal));
+ assert(b3a == b3);
+ assert(!(b3a.is_zero()));
mpz_t m3;
mpz_init(m3);
b3.to_mpz(m3);
bigint<3> b3b { m3 };
- EXPECT_EQ(b3b, b3);
+ assert(b3b == b3);
bigint<2> quotient;
bigint<2> remainder;
bigint<3>::div_qr(quotient, remainder, b3, b2);
- EXPECT_LT(quotient.num_bits(), GMP_NUMB_BITS);
- EXPECT_EQ(quotient.as_ulong(), b1.as_ulong());
+ assert(quotient.num_bits() < GMP_NUMB_BITS);
+ assert(quotient.as_ulong() == b1.as_ulong());
bigint<1> b1inc = bigint<1>("76749408");
bigint<1> b1a = quotient.shorten(b1inc, "test");
- EXPECT_EQ(b1a, b1);
- EXPECT_TRUE(remainder.is_zero());
+ assert(b1a == b1);
+ assert(remainder.is_zero());
remainder.limit(b2, "test");
- EXPECT_THROW((void)(quotient.shorten(b1, "test")), std::domain_error);
- EXPECT_THROW(remainder.limit(remainder, "test"), std::domain_error);
+ try {
+ (void)(quotient.shorten(b1, "test"));
+ assert(false);
+ } catch (std::domain_error) {}
+ try {
+ remainder.limit(remainder, "test");
+ assert(false);
+ } catch (std::domain_error) {}
bigint<1> br = bigint<1>("42");
b3 += br;
- EXPECT_NE(b3, b3a);
- EXPECT_GT(b3, b3a);
- EXPECT_FALSE(b3a > b3);
+ assert(b3 != b3a);
+ assert(b3 > b3a);
+ assert(!(b3a > b3));
bigint<3>::div_qr(quotient, remainder, b3, b2);
- EXPECT_LT(quotient.num_bits(), GMP_NUMB_BITS);
- EXPECT_EQ(quotient.as_ulong(), b1.as_ulong());
- EXPECT_LT(remainder.num_bits(), GMP_NUMB_BITS);
- EXPECT_EQ(remainder.as_ulong(), 42);
+ assert(quotient.num_bits() < GMP_NUMB_BITS);
+ assert(quotient.as_ulong() == b1.as_ulong());
+ assert(remainder.num_bits() < GMP_NUMB_BITS);
+ assert(remainder.as_ulong() == 42);
b3a.clear();
- EXPECT_TRUE(b3a.is_zero());
- EXPECT_EQ(b3a.num_bits(), 0);
- EXPECT_FALSE(b3.is_zero());
+ assert(b3a.is_zero());
+ assert(b3a.num_bits() == 0);
+ assert(!(b3.is_zero()));
bigint<4> bx = bigint<4>().randomize();
bigint<4> by = bigint<4>().randomize();
- EXPECT_FALSE(bx == by);
+ assert(!(bx == by));
// TODO: test serialization
}
+int main(void)
+{
+ test_bigint();
+ return 0;
+}
+
* @copyright MIT license (see LICENSE file)
*****************************************************************************/
#include "common/profiling.hpp"
+#include "algebra/curves/edwards/edwards_pp.hpp"
+#include "algebra/curves/mnt/mnt4/mnt4_pp.hpp"
+#include "algebra/curves/mnt/mnt6/mnt6_pp.hpp"
#ifdef CURVE_BN128
#include "algebra/curves/bn128/bn128_pp.hpp"
#endif
#include "algebra/fields/fp6_3over2.hpp"
#include "algebra/fields/fp12_2over3over2.hpp"
-#include <gtest/gtest.h>
-
using namespace libsnark;
template<typename FieldT>
FieldT a = FieldT::random_element();
FieldT a_ser;
a_ser = reserialize<FieldT>(a);
- EXPECT_EQ(a_ser, a);
+ assert(a_ser == a);
FieldT b = FieldT::random_element();
FieldT c = FieldT::random_element();
FieldT d = FieldT::random_element();
- EXPECT_NE(a, zero);
- EXPECT_NE(a, one);
+ assert(a != zero);
+ assert(a != one);
- EXPECT_EQ(a * a, a.squared());
- EXPECT_EQ((a + b).squared(), a.squared() + a*b + b*a + b.squared());
- EXPECT_EQ((a + b)*(c + d), a*c + a*d + b*c + b*d);
- EXPECT_EQ(a - b, a + (-b));
- EXPECT_EQ(a - b, (-b) + a);
+ assert(a * a == a.squared());
+ assert((a + b).squared() == a.squared() + a*b + b*a + b.squared());
+ assert((a + b)*(c + d) == a*c + a*d + b*c + b*d);
+ assert(a - b == a + (-b));
+ assert(a - b == (-b) + a);
- EXPECT_EQ((a ^ rand1) * (a ^ rand2), (a^randsum));
+ assert((a ^ rand1) * (a ^ rand2) == (a^randsum));
- EXPECT_EQ(a * a.inverse(), one);
- EXPECT_EQ((a + b) * c.inverse(), a * c.inverse() + (b.inverse() * c).inverse());
+ assert(a * a.inverse() == one);
+ assert((a + b) * c.inverse() == a * c.inverse() + (b.inverse() * c).inverse());
}
{
FieldT a = FieldT::random_element();
FieldT asq = a.squared();
- EXPECT_TRUE(asq.sqrt() == a || asq.sqrt() == -a);
+ assert(asq.sqrt() == a || asq.sqrt() == -a);
}
}
void test_two_squarings()
{
FieldT a = FieldT::random_element();
- EXPECT_EQ(a.squared(), a * a);
- EXPECT_EQ(a.squared(), a.squared_complex());
- EXPECT_EQ(a.squared(), a.squared_karatsuba());
+ assert(a.squared() == a * a);
+ assert(a.squared() == a.squared_complex());
+ assert(a.squared() == a.squared_karatsuba());
}
template<typename FieldT>
void test_Frobenius()
{
FieldT a = FieldT::random_element();
- EXPECT_EQ(a.Frobenius_map(0), a);
+ assert(a.Frobenius_map(0) == a);
FieldT a_q = a ^ FieldT::base_field_char();
for (size_t power = 1; power < 10; ++power)
{
const FieldT a_qi = a.Frobenius_map(power);
- EXPECT_EQ(a_qi, a_q);
+ assert(a_qi == a_q);
a_q = a_q ^ FieldT::base_field_char();
}
template<typename FieldT>
void test_unitary_inverse()
{
- EXPECT_EQ(FieldT::extension_degree() % 2, 0);
+ assert(FieldT::extension_degree() % 2 == 0);
FieldT a = FieldT::random_element();
FieldT aqcubed_minus1 = a.Frobenius_map(FieldT::extension_degree()/2) * a.inverse();
- EXPECT_EQ(aqcubed_minus1.inverse(), aqcubed_minus1.unitary_inverse());
+ assert(aqcubed_minus1.inverse() == aqcubed_minus1.unitary_inverse());
+}
+
+template<typename FieldT>
+void test_cyclotomic_squaring();
+
+template<>
+void test_cyclotomic_squaring<Fqk<edwards_pp> >()
+{
+ typedef Fqk<edwards_pp> FieldT;
+ assert(FieldT::extension_degree() % 2 == 0);
+ FieldT a = FieldT::random_element();
+ FieldT a_unitary = a.Frobenius_map(FieldT::extension_degree()/2) * a.inverse();
+ // beta = a^((q^(k/2)-1)*(q+1))
+ FieldT beta = a_unitary.Frobenius_map(1) * a_unitary;
+ assert(beta.cyclotomic_squared() == beta.squared());
+}
+
+template<>
+void test_cyclotomic_squaring<Fqk<mnt4_pp> >()
+{
+ typedef Fqk<mnt4_pp> FieldT;
+ assert(FieldT::extension_degree() % 2 == 0);
+ FieldT a = FieldT::random_element();
+ FieldT a_unitary = a.Frobenius_map(FieldT::extension_degree()/2) * a.inverse();
+ // beta = a^(q^(k/2)-1)
+ FieldT beta = a_unitary;
+ assert(beta.cyclotomic_squared() == beta.squared());
+}
+
+template<>
+void test_cyclotomic_squaring<Fqk<mnt6_pp> >()
+{
+ typedef Fqk<mnt6_pp> FieldT;
+ assert(FieldT::extension_degree() % 2 == 0);
+ FieldT a = FieldT::random_element();
+ FieldT a_unitary = a.Frobenius_map(FieldT::extension_degree()/2) * a.inverse();
+ // beta = a^((q^(k/2)-1)*(q+1))
+ FieldT beta = a_unitary.Frobenius_map(1) * a_unitary;
+ assert(beta.cyclotomic_squared() == beta.squared());
}
template<typename ppT>
c2 = - (FieldT(5)*(FieldT(4).inverse()))* v0 + (FieldT(2)*(FieldT(3).inverse()))*(v1 + v2) - FieldT(24).inverse()*(v3 + v4) + FieldT(4)*v6 + beta*v6;
c3 = FieldT(12).inverse() * (FieldT(5)*v0 - FieldT(7)*v1) - FieldT(24).inverse()*(v2 - FieldT(7)*v3 + v4 + v5) + FieldT(15)*v6;
- EXPECT_EQ(res, correct_res);
+ assert(res == correct_res);
// {v0, v3, v4, v5}
const FieldT u = (FieldT::one() - beta).inverse();
- EXPECT_EQ(v0, u * c0 + beta * u * c2 - beta * u * FieldT(2).inverse() * v1 - beta * u * FieldT(2).inverse() * v2 + beta * v6);
- EXPECT_EQ(v3, - FieldT(15) * u * c0 - FieldT(30) * u * c1 - FieldT(3) * (FieldT(4) + beta) * u * c2 - FieldT(6) * (FieldT(4) + beta) * u * c3 + (FieldT(24) - FieldT(3) * beta * FieldT(2).inverse()) * u * v1 + (-FieldT(8) + beta * FieldT(2).inverse()) * u * v2
+ assert(v0 == u * c0 + beta * u * c2 - beta * u * FieldT(2).inverse() * v1 - beta * u * FieldT(2).inverse() * v2 + beta * v6);
+ assert(v3 == - FieldT(15) * u * c0 - FieldT(30) * u * c1 - FieldT(3) * (FieldT(4) + beta) * u * c2 - FieldT(6) * (FieldT(4) + beta) * u * c3 + (FieldT(24) - FieldT(3) * beta * FieldT(2).inverse()) * u * v1 + (-FieldT(8) + beta * FieldT(2).inverse()) * u * v2
- FieldT(3) * (-FieldT(16) + beta) * v6);
- EXPECT_EQ(v4, - FieldT(15) * u * c0 + FieldT(30) * u * c1 - FieldT(3) * (FieldT(4) + beta) * u * c2 + FieldT(6) * (FieldT(4) + beta) * u * c3 + (FieldT(24) - FieldT(3) * beta * FieldT(2).inverse()) * u * v2 + (-FieldT(8) + beta * FieldT(2).inverse()) * u * v1
+ assert(v4 == - FieldT(15) * u * c0 + FieldT(30) * u * c1 - FieldT(3) * (FieldT(4) + beta) * u * c2 + FieldT(6) * (FieldT(4) + beta) * u * c3 + (FieldT(24) - FieldT(3) * beta * FieldT(2).inverse()) * u * v2 + (-FieldT(8) + beta * FieldT(2).inverse()) * u * v1
- FieldT(3) * (-FieldT(16) + beta) * v6);
- EXPECT_EQ(v5, - FieldT(80) * u * c0 - FieldT(240) * u * c1 - FieldT(8) * (FieldT(9) + beta) * u * c2 - FieldT(24) * (FieldT(9) + beta) * u * c3 - FieldT(2) * (-FieldT(81) + beta) * u * v1 + (-FieldT(81) + beta) * u * v2
+ assert(v5 == - FieldT(80) * u * c0 - FieldT(240) * u * c1 - FieldT(8) * (FieldT(9) + beta) * u * c2 - FieldT(24) * (FieldT(9) + beta) * u * c3 - FieldT(2) * (-FieldT(81) + beta) * u * v1 + (-FieldT(81) + beta) * u * v2
- FieldT(8) * (-FieldT(81) + beta) * v6);
// c0 + beta c2 - (beta v1)/2 - (beta v2)/ 2 - (-1 + beta) beta v6,
}
}
-TEST(algebra, fields)
+int main(void)
{
+ edwards_pp::init_public_params();
+ test_all_fields<edwards_pp>();
+ test_cyclotomic_squaring<Fqk<edwards_pp> >();
+
+ mnt4_pp::init_public_params();
+ test_all_fields<mnt4_pp>();
+ test_Fp4_tom_cook<mnt4_Fq4>();
+ test_two_squarings<Fqe<mnt4_pp> >();
+ test_cyclotomic_squaring<Fqk<mnt4_pp> >();
+
+ mnt6_pp::init_public_params();
+ test_all_fields<mnt6_pp>();
+ test_cyclotomic_squaring<Fqk<mnt6_pp> >();
+
alt_bn128_pp::init_public_params();
test_field<alt_bn128_Fq6>();
test_Frobenius<alt_bn128_Fq6>();
/*
Split out from multiexp to prevent cyclical
- dependencies. I.e. previously multiexp depended on
- knowledge_commitment, which depended on sparse_vector, which
- depended on multiexp (to do accumulate).
+ dependencies. I.e. previously multiexp dependend on
+ knowledge_commitment, which dependend on sparse_vector, which
+ dependend on multiexp (to do accumulate).
Will probably go away in more general exp refactoring.
*/
#ifndef KC_MULTIEXP_TCC_
#define KC_MULTIEXP_TCC_
+#include "common/assert_except.hpp"
+
namespace libsnark {
template<typename T1, typename T2, mp_size_t n>
while (index_it != vec.indices.end() && *index_it < max_idx)
{
const size_t scalar_position = (*index_it) - min_idx;
- assert(scalar_position < scalar_length);
+ assert_except(scalar_position < scalar_length);
const FieldT scalar = *(scalar_start + scalar_position);
#include "common/profiling.hpp"
#include "common/utils.hpp"
+#include "common/assert_except.hpp"
#include "algebra/scalar_multiplication/wnaf.hpp"
namespace libsnark {
#if defined(__x86_64__) && defined(USE_ASM)
if (n == 3)
{
- long res;
+ int64_t res;
__asm__
("// check for overflow \n\t"
"mov $0, %[res] \n\t"
}
else if (n == 4)
{
- long res;
+ int64_t res;
__asm__
("// check for overflow \n\t"
"mov $0, %[res] \n\t"
}
else if (n == 5)
{
- long res;
+ int64_t res;
__asm__
("// check for overflow \n\t"
"mov $0, %[res] \n\t"
bigint<FieldT::num_limbs> scalar_bigint = scalar_it->as_bigint();
result = result + opt_window_wnaf_exp(*vec_it, scalar_bigint, scalar_bigint.num_bits());
}
- assert(scalar_it == scalar_end);
+ assert_except(scalar_it == scalar_end);
return result;
}
{
result = result + (*scalar_it) * (*vec_it);
}
- assert(scalar_it == scalar_end);
+ assert_except(scalar_it == scalar_end);
return result;
}
opt_q.emplace_back(ordered_exponent<n>(i, scalar_it->as_bigint()));
}
std::make_heap(opt_q.begin(),opt_q.end());
- assert(scalar_it == scalar_end);
+ assert_except(scalar_it == scalar_end);
if (vec_len != odd_vec_len)
{
g.emplace_back(T::zero());
- opt_q.emplace_back(ordered_exponent<n>(odd_vec_len - 1, bigint<n>(0ul)));
+ opt_q.emplace_back(ordered_exponent<n>(odd_vec_len - 1, bigint<n>(UINT64_C(0))));
}
- assert(g.size() % 2 == 1);
- assert(opt_q.size() == g.size());
+ assert_except(g.size() % 2 == 1);
+ assert_except(opt_q.size() == g.size());
T opt_result = T::zero();
const size_t bbits = b.r.num_bits();
const size_t limit = (abits-bbits >= 20 ? 20 : abits-bbits);
- if (bbits < 1ul<<limit)
+ if (bbits < UINT64_C(1)<<limit)
{
/*
In this case, exponentiating to the power of a is cheaper than
const size_t chunks,
const bool use_multiexp)
{
- assert(std::distance(vec_start, vec_end) == std::distance(scalar_start, scalar_end));
+ assert_except(std::distance(vec_start, vec_end) == std::distance(scalar_start, scalar_end));
enter_block("Process scalar vector");
auto value_it = vec_start;
auto scalar_it = scalar_start;
#endif
}
size_t window = 1;
- for (long i = T::fixed_base_exp_window_table.size()-1; i >= 0; --i)
+ for (int64_t i = T::fixed_base_exp_window_table.size()-1; i >= 0; --i)
{
#ifdef DEBUG
if (!inhibit_profiling_info)
const size_t window,
const T &g)
{
- const size_t in_window = 1ul<<window;
+ const size_t in_window = UINT64_C(1)<<window;
const size_t outerc = (scalar_size+window-1)/window;
- const size_t last_in_window = 1ul<<(scalar_size - (outerc-1)*window);
+ const size_t last_in_window = UINT64_C(1)<<(scalar_size - (outerc-1)*window);
#ifdef DEBUG
if (!inhibit_profiling_info)
{
* Find the wNAF representation of the given scalar relative to the given window size.
*/
template<mp_size_t n>
-std::vector<long> find_wnaf(const size_t window_size, const bigint<n> &scalar);
+std::vector<int64_t> find_wnaf(const size_t window_size, const bigint<n> &scalar);
/**
* In additive notation, use wNAF exponentiation (with the given window size) to compute scalar * base.
namespace libsnark {
template<mp_size_t n>
-std::vector<long> find_wnaf(const size_t window_size, const bigint<n> &scalar)
+std::vector<int64_t> find_wnaf(const size_t window_size, const bigint<n> &scalar)
{
const size_t length = scalar.max_bits(); // upper bound
- std::vector<long> res(length+1);
+ std::vector<int64_t> res(length+1);
bigint<n> c = scalar;
- long j = 0;
+ int64_t j = 0;
while (!c.is_zero())
{
- long u;
+ int64_t u;
if ((c.data[0] & 1) == 1)
{
u = c.data[0] % (1u << (window_size+1));
template<typename T, mp_size_t n>
T fixed_window_wnaf_exp(const size_t window_size, const T &base, const bigint<n> &scalar)
{
- std::vector<long> naf = find_wnaf(window_size, scalar);
- std::vector<T> table(1ul<<(window_size-1));
+ std::vector<int64_t> naf = find_wnaf(window_size, scalar);
+ std::vector<T> table(UINT64_C(1)<<(window_size-1));
T tmp = base;
T dbl = base.dbl();
- for (size_t i = 0; i < 1ul<<(window_size-1); ++i)
+ for (size_t i = 0; i < UINT64_C(1)<<(window_size-1); ++i)
{
table[i] = tmp;
tmp = tmp + dbl;
T res = T::zero();
bool found_nonzero = false;
- for (long i = naf.size()-1; i >= 0; --i)
+ for (int64_t i = naf.size()-1; i >= 0; --i)
{
if (found_nonzero)
{
T opt_window_wnaf_exp(const T &base, const bigint<n> &scalar, const size_t scalar_bits)
{
size_t best = 0;
- for (long i = T::wnaf_window_table.size() - 1; i >= 0; --i)
+ for (int64_t i = T::wnaf_window_table.size() - 1; i >= 0; --i)
{
if (scalar_bits >= T::wnaf_window_table[i])
{
assert(log2(contents_as_vector.size()) <= depth);
for (size_t address = 0; address < contents_as_vector.size(); ++address)
{
- const size_t idx = address + (1ul<<depth) - 1;
+ const size_t idx = address + (UINT64_C(1)<<depth) - 1;
values[idx] = contents_as_vector[address];
hashes[idx] = contents_as_vector[address];
hashes[idx].resize(digest_size);
}
- size_t idx_begin = (1ul<<depth) - 1;
- size_t idx_end = contents_as_vector.size() + ((1ul<<depth) - 1);
+ size_t idx_begin = (UINT64_C(1)<<depth) - 1;
+ size_t idx_end = contents_as_vector.size() + ((UINT64_C(1)<<depth) - 1);
for (int layer = depth; layer > 0; --layer)
{
if (!contents.empty())
{
- assert(contents.rbegin()->first < 1ul<<depth);
+ assert(contents.rbegin()->first < UINT64_C(1)<<depth);
for (auto it = contents.begin(); it != contents.end(); ++it)
{
const size_t address = it->first;
const bit_vector value = it->second;
- const size_t idx = address + (1ul<<depth) - 1;
+ const size_t idx = address + (UINT64_C(1)<<depth) - 1;
values[address] = value;
hashes[idx] = value;
const bit_vector &value)
{
assert(log2(address) <= depth);
- size_t idx = address + (1ul<<depth) - 1;
+ size_t idx = address + (UINT64_C(1)<<depth) - 1;
assert(value.size() == value_size);
values[address] = value;
{
typename HashT::merkle_authentication_path_type result(depth);
assert(log2(address) <= depth);
- size_t idx = address + (1ul<<depth) - 1;
+ size_t idx = address + (UINT64_C(1)<<depth) - 1;
for (size_t layer = depth; layer > 0; --layer)
{
auto it = hashes.find(sibling_idx);
if (layer == depth)
{
- auto it2 = values.find(sibling_idx - ((1ul<<depth) - 1));
+ auto it2 = values.find(sibling_idx - ((UINT64_C(1)<<depth) - 1));
result[layer-1] = (it2 == values.end() ? bit_vector(value_size, false) : it2->second);
result[layer-1].resize(digest_size);
}
template<typename HashT>
void merkle_tree<HashT>::dump() const
{
- for (size_t i = 0; i < 1ul<<depth; ++i)
+ for (size_t i = 0; i < UINT64_C(1)<<depth; ++i)
{
auto it = values.find(i);
printf("[%zu] -> ", i);
template<typename T>
struct sparse_vector {
- std::vector<size_t> indices;
+ std::vector<uint64_t> indices;
std::vector<T> values;
- size_t domain_size_ = 0;
+ uint64_t domain_size_ = 0;
sparse_vector() = default;
sparse_vector(const sparse_vector<T> &other) = default;
sparse_vector<T>& operator=(const sparse_vector<T> &other) = default;
sparse_vector<T>& operator=(sparse_vector<T> &&other) = default;
- T operator[](const size_t idx) const;
+ T operator[](const uint64_t idx) const;
bool operator==(const sparse_vector<T> &other) const;
bool operator==(const std::vector<T> &other) const;
bool is_valid() const;
bool empty() const;
- size_t domain_size() const; // return domain_size_
- size_t size() const; // return the number of indices (representing the number of non-zero entries)
- size_t size_in_bits() const; // return the number bits needed to store the sparse vector
+ uint64_t domain_size() const; // return domain_size_
+ uint64_t size() const; // return the number of indices (representing the number of non-zero entries)
+ uint64_t size_in_bits() const; // return the number bits needed to store the sparse vector
- /* return a pair consisting of the accumulated value and the sparse vector of non-accumulated values */
+ /* return a pair consisting of the accumulated value and the sparse vector of non-accumuated values */
template<typename FieldT>
std::pair<T, sparse_vector<T> > accumulate(const typename std::vector<FieldT>::const_iterator &it_begin,
const typename std::vector<FieldT>::const_iterator &it_end,
- const size_t offset) const;
+ const uint64_t offset) const;
friend std::ostream& operator<< <T>(std::ostream &out, const sparse_vector<T> &v);
friend std::istream& operator>> <T>(std::istream &in, sparse_vector<T> &v);
}
template<typename T>
-T sparse_vector<T>::operator[](const size_t idx) const
+T sparse_vector<T>::operator[](const uint64_t idx) const
{
auto it = std::lower_bound(indices.begin(), indices.end(), idx);
return (it != indices.end() && *it == idx) ? values[it - indices.begin()] : T();
return false;
}
- size_t this_pos = 0, other_pos = 0;
+ uint64_t this_pos = 0, other_pos = 0;
while (this_pos < this->indices.size() && other_pos < other.indices.size())
{
if (this->indices[this_pos] == other.indices[other_pos])
return false;
}
- size_t j = 0;
- for (size_t i = 0; i < other.size(); ++i)
+ uint64_t j = 0;
+ for (uint64_t i = 0; i < other.size(); ++i)
{
if (this->indices[j] == i)
{
return false;
}
- for (size_t i = 0; i + 1 < indices.size(); ++i)
+ for (uint64_t i = 0; i + 1 < indices.size(); ++i)
{
if (indices[i] >= indices[i+1])
{
}
template<typename T>
-size_t sparse_vector<T>::domain_size() const
+uint64_t sparse_vector<T>::domain_size() const
{
return domain_size_;
}
template<typename T>
-size_t sparse_vector<T>::size() const
+uint64_t sparse_vector<T>::size() const
{
return indices.size();
}
template<typename T>
-size_t sparse_vector<T>::size_in_bits() const
+uint64_t sparse_vector<T>::size_in_bits() const
{
- return indices.size() * (sizeof(size_t) * 8 + T::size_in_bits());
+ return indices.size() * (sizeof(uint64_t) * 8 + T::size_in_bits());
}
template<typename T>
template<typename FieldT>
std::pair<T, sparse_vector<T> > sparse_vector<T>::accumulate(const typename std::vector<FieldT>::const_iterator &it_begin,
const typename std::vector<FieldT>::const_iterator &it_end,
- const size_t offset) const
+ const uint64_t offset) const
{
// TODO: does not really belong here.
- const size_t chunks = 1;
+ const uint64_t chunks = 1;
const bool use_multiexp = true;
T accumulated_value = T::zero();
sparse_vector<T> resulting_vector;
resulting_vector.domain_size_ = domain_size_;
- const size_t range_len = it_end - it_begin;
+ const uint64_t range_len = it_end - it_begin;
bool in_block = false;
- size_t first_pos = -1, last_pos = -1; // g++ -flto emits unitialized warning, even though in_block guards for such cases.
+ uint64_t first_pos = -1, last_pos = -1; // g++ -flto emits unitialized warning, even though in_block guards for such cases.
- for (size_t i = 0; i < indices.size(); ++i)
+ for (uint64_t i = 0; i < indices.size(); ++i)
{
const bool matching_pos = (offset <= indices[i] && indices[i] < offset + range_len);
// printf("i = %zu, pos[i] = %zu, offset = %zu, w_size = %zu\n", i, indices[i], offset, w_size);
{
out << v.domain_size_ << "\n";
out << v.indices.size() << "\n";
- for (const size_t& i : v.indices)
+ for (const uint64_t& i : v.indices)
{
out << i << "\n";
}
in >> v.domain_size_;
consume_newline(in);
- size_t s;
+ uint64_t s;
in >> s;
consume_newline(in);
v.indices.resize(s);
- for (size_t i = 0; i < s; ++i)
+ for (uint64_t i = 0; i < s; ++i)
{
in >> v.indices[i];
consume_newline(in);
consume_newline(in);
v.values.reserve(s);
- for (size_t i = 0; i < s; ++i)
+ for (uint64_t i = 0; i < s; ++i)
{
T t;
in >> t;
#include <proc/readproc.h>
#endif
+#ifdef __MACH__ // required to build on MacOS
+#include <time.h>
+#include <sys/time.h>
+#include <mach/clock.h>
+#include <mach/mach.h>
+#endif
+
namespace libsnark {
-long long get_nsec_time()
+int64_t get_nsec_time()
{
auto timepoint = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::nanoseconds>(timepoint.time_since_epoch()).count();
}
-/* Return total CPU time consumed by all threads of the process, in nanoseconds. */
-long long get_nsec_cpu_time()
+/* Return total CPU time consumsed by all threads of the process, in nanoseconds. */
+int64_t get_nsec_cpu_time()
{
::timespec ts;
+ #ifdef __MACH__
+ clock_serv_t cclock;
+ mach_timespec_t mts;
+ host_get_clock_service(mach_host_self(), CALENDAR_CLOCK, &cclock);
+ clock_get_time(cclock, &mts);
+ mach_port_deallocate(mach_task_self(), cclock);
+ ts.tv_sec = mts.tv_sec;
+ ts.tv_nsec = mts.tv_nsec;
+ #else
if ( ::clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts) )
throw ::std::runtime_error("clock_gettime(CLOCK_PROCESS_CPUTIME_ID) failed");
// If we expected this to work, don't silently ignore failures, because that would hide the problem and incur an unnecessarily system-call overhead. So if we ever observe this exception, we should probably add a suitable #ifdef .
//TODO: clock_gettime(CLOCK_PROCESS_CPUTIME_ID) is not supported by native Windows. What about Cygwin? Should we #ifdef on CLOCK_PROCESS_CPUTIME_ID or on __linux__?
+ #endif
return ts.tv_sec * 1000000000ll + ts.tv_nsec;
}
-long long start_time, last_time;
-long long start_cpu_time, last_cpu_time;
+int64_t start_time, last_time;
+int64_t start_cpu_time, last_cpu_time;
void start_profiling()
{
}
std::map<std::string, size_t> invocation_counts;
-std::map<std::string, long long> enter_times;
-std::map<std::string, long long> last_times;
-std::map<std::string, long long> cumulative_times;
+std::map<std::string, int64_t> enter_times;
+std::map<std::string, int64_t> last_times;
+std::map<std::string, int64_t> cumulative_times;
//TODO: Instead of analogous maps for time and cpu_time, use a single struct-valued map
-std::map<std::string, long long> enter_cpu_times;
-std::map<std::string, long long> last_cpu_times;
-std::map<std::pair<std::string, std::string>, long long> op_counts;
-std::map<std::pair<std::string, std::string>, long long> cumulative_op_counts; // ((msg, data_point), value)
+std::map<std::string, int64_t> enter_cpu_times;
+std::map<std::string, int64_t> last_cpu_times;
+std::map<std::pair<std::string, std::string>, int64_t> op_counts;
+std::map<std::pair<std::string, std::string>, int64_t> cumulative_op_counts; // ((msg, data_point), value)
// TODO: Convert op_counts and cumulative_op_counts from pair to structs
size_t indentation = 0;
std::vector<std::string> block_names;
-std::list<std::pair<std::string, long long*> > op_data_points = {
+std::list<std::pair<std::string, int64_t*> > op_data_points = {
#ifdef PROFILE_OP_COUNTS
std::make_pair("Fradd", &Fr<default_ec_pp>::add_cnt),
std::make_pair("Frsub", &Fr<default_ec_pp>::sub_cnt),
cumulative_times.clear();
}
-void print_cumulative_time_entry(const std::string &key, const long long factor)
+void print_cumulative_time_entry(const std::string &key, const int64_t factor)
{
const double total_ms = (cumulative_times.at(key) * 1e-6);
const size_t cnt = invocation_counts.at(key);
printf(" %-45s: %12.5fms = %lld * %0.5fms (%zu invocations, %0.5fms = %lld * %0.5fms per invocation)\n", key.c_str(), total_ms, factor, total_ms/factor, cnt, avg_ms, factor, avg_ms/factor);
}
-void print_cumulative_times(const long long factor)
+void print_cumulative_times(const int64_t factor)
{
printf("Dumping times:\n");
for (auto& kv : cumulative_times)
printf("(opcounts) = (");
bool first = true;
- for (std::pair<std::string, long long*> p : op_data_points)
+ for (std::pair<std::string, int64_t*> p : op_data_points)
{
if (!first)
{
#endif
}
-static void print_times_from_last_and_start(long long now, long long last,
- long long cpu_now, long long cpu_last)
+static void print_times_from_last_and_start(int64_t now, int64_t last,
+ int64_t cpu_now, int64_t cpu_last)
{
- long long time_from_start = now - start_time;
- long long time_from_last = now - last;
+ int64_t time_from_start = now - start_time;
+ int64_t time_from_last = now - last;
- long long cpu_time_from_start = cpu_now - start_cpu_time;
- long long cpu_time_from_last = cpu_now - cpu_last;
+ int64_t cpu_time_from_start = cpu_now - start_cpu_time;
+ int64_t cpu_time_from_last = cpu_now - cpu_last;
if (time_from_last != 0) {
double parallelism_from_last = 1.0 * cpu_time_from_last / time_from_last;
return;
}
- long long now = get_nsec_time();
- long long cpu_now = get_nsec_cpu_time();
+ int64_t now = get_nsec_time();
+ int64_t cpu_now = get_nsec_cpu_time();
printf("%-35s\t", msg);
print_times_from_last_and_start(now, last_time, cpu_now, last_cpu_time);
void op_profiling_enter(const std::string &msg)
{
- for (std::pair<std::string, long long*> p : op_data_points)
+ for (std::pair<std::string, int64_t*> p : op_data_points)
{
op_counts[std::make_pair(msg, p.first)] = *(p.second);
}
}
block_names.emplace_back(msg);
- long long t = get_nsec_time();
+ int64_t t = get_nsec_time();
enter_times[msg] = t;
- long long cpu_t = get_nsec_cpu_time();
+ int64_t cpu_t = get_nsec_cpu_time();
enter_cpu_times[msg] = cpu_t;
if (inhibit_profiling_info)
++invocation_counts[msg];
- long long t = get_nsec_time();
+ int64_t t = get_nsec_time();
last_times[msg] = (t - enter_times[msg]);
cumulative_times[msg] += (t - enter_times[msg]);
- long long cpu_t = get_nsec_cpu_time();
+ int64_t cpu_t = get_nsec_cpu_time();
last_cpu_times[msg] = (cpu_t - enter_cpu_times[msg]);
#ifdef PROFILE_OP_COUNTS
- for (std::pair<std::string, long long*> p : op_data_points)
+ for (std::pair<std::string, int64_t*> p : op_data_points)
{
cumulative_op_counts[std::make_pair(msg, p.first)] += *(p.second)-op_counts[std::make_pair(msg, p.first)];
}
namespace libsnark {
void start_profiling();
-long long get_nsec_time();
+int64_t get_nsec_time();
void print_time(const char* msg);
void print_header(const char* msg);
extern bool inhibit_profiling_info;
extern bool inhibit_profiling_counters;
extern std::map<std::string, size_t> invocation_counts;
-extern std::map<std::string, long long> last_times;
-extern std::map<std::string, long long> cumulative_times;
+extern std::map<std::string, int64_t> last_times;
+extern std::map<std::string, int64_t> cumulative_times;
void clear_profiling_counters();
-void print_cumulative_time_entry(const std::string &key, const long long factor=1);
-void print_cumulative_times(const long long factor=1);
+void print_cumulative_time_entry(const std::string &key, const int64_t factor=1);
+void print_cumulative_times(const int64_t factor=1);
void print_cumulative_op_counts(const bool only_fq=false);
void enter_block(const std::string &msg, const bool indent=true);
/*
* @todo
- * The serialization is fragile. Should be rewritten using a standard, portable-format
+ * The serialization is fragile. Shoud be rewritten using a standard, portable-format
* library like boost::serialize.
*
* However, for now the following conventions are used within the code.
#include <cassert>
#include <sstream>
#include "common/utils.hpp"
+#include "common/assert_except.hpp"
namespace libsnark {
ss << obj;
T tmp;
ss >> tmp;
- assert(obj == tmp);
+ assert_except(obj == tmp);
return tmp;
}
namespace libsnark {
-size_t log2(size_t n)
+uint64_t log2(uint64_t n)
/* returns ceil(log2(n)), so 1ul<<log2(n) is the smallest power of 2,
that is not less than n. */
{
- size_t r = ((n & (n-1)) == 0 ? 0 : 1); // add 1 if n is not power of 2
+ uint64_t r = ((n & (n-1)) == 0 ? 0 : 1); // add 1 if n is not power of 2
while (n > 1)
{
return r;
}
-size_t bitreverse(size_t n, const size_t l)
+uint64_t bitreverse(uint64_t n, const uint64_t l)
{
- size_t r = 0;
- for (size_t k = 0; k < l; ++k)
+ uint64_t r = 0;
+ for (uint64_t k = 0; k < l; ++k)
{
r = (r << 1) | (n & 1);
n >>= 1;
return r;
}
-bit_vector int_list_to_bits(const std::initializer_list<unsigned long> &l, const size_t wordsize)
+bit_vector int_list_to_bits(const std::initializer_list<uint64_t> &l, const size_t wordsize)
{
bit_vector res(wordsize*l.size());
- for (size_t i = 0; i < l.size(); ++i)
+ for (uint64_t i = 0; i < l.size(); ++i)
{
- for (size_t j = 0; j < wordsize; ++j)
+ for (uint64_t j = 0; j < wordsize; ++j)
{
- res[i*wordsize + j] = (*(l.begin()+i) & (1ul<<(wordsize-1-j)));
+ res[i*wordsize + j] = (*(l.begin()+i) & (UINT64_C(1)<<(wordsize-1-j)));
}
}
return res;
}
-long long div_ceil(long long x, long long y)
+int64_t div_ceil(int64_t x, int64_t y)
{
return (x + (y-1)) / y;
}
std::string FORMAT(const std::string &prefix, const char* format, ...)
{
- const static size_t MAX_FMT = 256;
+ const static uint64_t MAX_FMT = 256;
char buf[MAX_FMT];
va_list args;
va_start(args, format);
void serialize_bit_vector(std::ostream &out, const bit_vector &v)
{
out << v.size() << "\n";
- for (size_t i = 0; i < v.size(); ++i)
+ for (uint64_t i = 0; i < v.size(); ++i)
{
out << v[i] << "\n";
}
void deserialize_bit_vector(std::istream &in, bit_vector &v)
{
- size_t size;
+ uint64_t size;
in >> size;
v.resize(size);
- for (size_t i = 0; i < size; ++i)
+ for (uint64_t i = 0; i < size; ++i)
{
bool b;
in >> b;
typedef std::vector<bool> bit_vector;
/// returns ceil(log2(n)), so 1ul<<log2(n) is the smallest power of 2, that is not less than n
-size_t log2(size_t n);
+uint64_t log2(uint64_t n);
-inline size_t exp2(size_t k) { return 1ul << k; }
+inline uint64_t exp2(uint64_t k) { return 1ull << k; }
-size_t bitreverse(size_t n, const size_t l);
-bit_vector int_list_to_bits(const std::initializer_list<unsigned long> &l, const size_t wordsize);
-long long div_ceil(long long x, long long y);
+uint64_t bitreverse(uint64_t n, const uint64_t l);
+bit_vector int_list_to_bits(const std::initializer_list<uint64_t> &l, const uint64_t wordsize);
+int64_t div_ceil(int64_t x, int64_t y);
bool is_little_endian();
void serialize_bit_vector(std::ostream &out, const bit_vector &v);
void deserialize_bit_vector(std::istream &in, bit_vector &v);
+#ifdef __APPLE__
template<typename T>
-size_t size_in_bits(const std::vector<T> &v);
+unsigned long size_in_bits(const std::vector<T> &v);
+#else
+template<typename T>
+uint64_t size_in_bits(const std::vector<T> &v);
+#endif
#define ARRAY_SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
namespace libsnark {
+#ifdef __APPLE__
+template<typename T>
+unsigned long size_in_bits(const std::vector<T> &v)
+{
+ return v.size() * T::size_in_bits();
+}
+#else
template<typename T>
size_t size_in_bits(const std::vector<T> &v)
{
return v.size() * T::size_in_bits();
}
+#endif
} // libsnark
disjunction_gadget<FieldT> d(pb, inputs, output, "d");
d.generate_r1cs_constraints();
- for (size_t w = 0; w < 1ul<<n; ++w)
+ for (size_t w = 0; w < UINT64_C(1)<<n; ++w)
{
for (size_t j = 0; j < n; ++j)
{
- pb.val(inputs[j]) = FieldT((w & (1ul<<j)) ? 1 : 0);
+ pb.val(inputs[j]) = FieldT((w & (UINT64_C(1)<<j)) ? 1 : 0);
}
d.generate_r1cs_witness();
conjunction_gadget<FieldT> c(pb, inputs, output, "c");
c.generate_r1cs_constraints();
- for (size_t w = 0; w < 1ul<<n; ++w)
+ for (size_t w = 0; w < UINT64_C(1)<<n; ++w)
{
for (size_t j = 0; j < n; ++j)
{
- pb.val(inputs[j]) = (w & (1ul<<j)) ? FieldT::one() : FieldT::zero();
+ pb.val(inputs[j]) = (w & (UINT64_C(1)<<j)) ? FieldT::one() : FieldT::zero();
}
c.generate_r1cs_witness();
#ifdef DEBUG
printf("positive test for %zu\n", w);
#endif
- assert(pb.val(output) == (w == (1ul<<n) - 1 ? FieldT::one() : FieldT::zero()));
+ assert(pb.val(output) == (w == (UINT64_C(1)<<n) - 1 ? FieldT::one() : FieldT::zero()));
assert(pb.is_satisfied());
#ifdef DEBUG
printf("negative test for %zu\n", w);
#endif
- pb.val(output) = (w == (1ul<<n) - 1 ? FieldT::zero() : FieldT::one());
+ pb.val(output) = (w == (UINT64_C(1)<<n) - 1 ? FieldT::zero() : FieldT::one());
assert(!pb.is_satisfied());
}
comparison_gadget<FieldT> cmp(pb, n, A, B, less, less_or_eq, "cmp");
cmp.generate_r1cs_constraints();
- for (size_t a = 0; a < 1ul<<n; ++a)
+ for (size_t a = 0; a < UINT64_C(1)<<n; ++a)
{
- for (size_t b = 0; b < 1ul<<n; ++b)
+ for (size_t b = 0; b < UINT64_C(1)<<n; ++b)
{
pb.val(A) = FieldT(a);
pb.val(B) = FieldT(b);
inner_product_gadget<FieldT> g(pb, A, B, result, "g");
g.generate_r1cs_constraints();
- for (size_t i = 0; i < 1ul<<n; ++i)
+ for (size_t i = 0; i < UINT64_C(1)<<n; ++i)
{
- for (size_t j = 0; j < 1ul<<n; ++j)
+ for (size_t j = 0; j < UINT64_C(1)<<n; ++j)
{
size_t correct = 0;
for (size_t k = 0; k < n; ++k)
{
- pb.val(A[k]) = (i & (1ul<<k) ? FieldT::one() : FieldT::zero());
- pb.val(B[k]) = (j & (1ul<<k) ? FieldT::one() : FieldT::zero());
- correct += ((i & (1ul<<k)) && (j & (1ul<<k)) ? 1 : 0);
+ pb.val(A[k]) = (i & (UINT64_C(1)<<k) ? FieldT::one() : FieldT::zero());
+ pb.val(B[k]) = (j & (UINT64_C(1)<<k) ? FieldT::one() : FieldT::zero());
+ correct += ((i & (UINT64_C(1)<<k)) && (j & (UINT64_C(1)<<k)) ? 1 : 0);
}
g.generate_r1cs_witness();
{
/* assumes that idx can be fit in ulong; true for our purposes for now */
const bigint<FieldT::num_limbs> valint = this->pb.val(index).as_bigint();
- unsigned long idx = valint.as_ulong();
+ uint64_t idx = valint.as_ulong();
const bigint<FieldT::num_limbs> arrsize(arr.size());
if (idx >= arr.size() || mpn_cmp(valint.data, arrsize.data, FieldT::num_limbs) >= 0)
protoboard<FieldT> pb;
pb_variable_array<FieldT> arr;
- arr.allocate(pb, 1ul<<n, "arr");
+ arr.allocate(pb, UINT64_C(1)<<n, "arr");
pb_variable<FieldT> index, result, success_flag;
index.allocate(pb, "index");
result.allocate(pb, "result");
loose_multiplexing_gadget<FieldT> g(pb, arr, index, result, success_flag, "g");
g.generate_r1cs_constraints();
- for (size_t i = 0; i < 1ul<<n; ++i)
+ for (size_t i = 0; i < UINT64_C(1)<<n; ++i)
{
- pb.val(arr[i]) = FieldT((19*i) % (1ul<<n));
+ pb.val(arr[i]) = FieldT((19*i) % (UINT64_C(1)<<n));
}
- for (int idx = -1; idx <= (int)(1ul<<n); ++idx)
+ for (int idx = -1; idx <= (int)(UINT64_C(1)<<n); ++idx)
{
pb.val(index) = FieldT(idx);
g.generate_r1cs_witness();
- if (0 <= idx && idx <= (int)(1ul<<n) - 1)
+ if (0 <= idx && idx <= (int)(UINT64_C(1)<<n) - 1)
{
printf("demuxing element %d (in bounds)\n", idx);
- assert(pb.val(result) == FieldT((19*idx) % (1ul<<n)));
+ assert(pb.val(result) == FieldT((19*idx) % (UINT64_C(1)<<n)));
assert(pb.val(success_flag) == FieldT::one());
assert(pb.is_satisfied());
pb.val(result) -= FieldT::one();
{
for (size_t i = 0; i < 32; ++i)
{
- const long v = (this->pb.lc_val(X[i]) + this->pb.lc_val(Y[i]) + this->pb.lc_val(Z[i])).as_ulong();
+ const int64_t v = (this->pb.lc_val(X[i]) + this->pb.lc_val(Y[i]) + this->pb.lc_val(Z[i])).as_ulong();
this->pb.val(result_bits[i]) = FieldT(v / 2);
}
pb_linear_combination_array<FieldT> g;
pb_linear_combination_array<FieldT> h;
pb_variable<FieldT> W;
- long K;
+ int64_t K;
pb_linear_combination_array<FieldT> new_a;
pb_linear_combination_array<FieldT> new_e;
const pb_linear_combination_array<FieldT> &g,
const pb_linear_combination_array<FieldT> &h,
const pb_variable<FieldT> &W,
- const long &K,
+ const int64_t &K,
const pb_linear_combination_array<FieldT> &new_a,
const pb_linear_combination_array<FieldT> &new_e,
const std::string &annotation_prefix);
namespace libsnark {
-const unsigned long SHA256_K[64] = {
+const uint64_t SHA256_K[64] = {
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};
-const unsigned long SHA256_H[8] = {
+const uint64_t SHA256_H[8] = {
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
};
const pb_linear_combination_array<FieldT> &g,
const pb_linear_combination_array<FieldT> &h,
const pb_variable<FieldT> &W,
- const long &K,
+ const int64_t &K,
const pb_linear_combination_array<FieldT> &new_a,
const pb_linear_combination_array<FieldT> &new_e,
const std::string &annotation_prefix) :
#include "common/profiling.hpp"
#include "gadgetlib1/gadgets/hashes/sha256/sha256_gadget.hpp"
-#include <gtest/gtest.h>
-
using namespace libsnark;
template<typename FieldT>
f.generate_r1cs_witness();
output.generate_r1cs_witness(hash_bv);
- EXPECT_TRUE(pb.is_satisfied());
+ assert(pb.is_satisfied());
}
-TEST(gadgetlib1, sha256)
+int main(void)
{
start_profiling();
default_ec_pp::init_public_params();
for (size_t i = 0; i < tree_depth; ++i)
{
- if (address & (1ul << (tree_depth-1-i)))
+ if (address & (UINT64_C(1) << (tree_depth-1-i)))
{
left_digests[i].generate_r1cs_witness(path[i]);
}
merkle_authentication_path result;
for (size_t i = 0; i < tree_depth; ++i)
{
- if (address & (1ul << (tree_depth-1-i)))
+ if (address & (UINT64_C(1) << (tree_depth-1-i)))
{
result.emplace_back(left_digests[i].get_digest());
}
bit_vector address_bits;
size_t address = 0;
- for (long level = tree_depth-1; level >= 0; --level)
+ for (int64_t level = tree_depth-1; level >= 0; --level)
{
const bool computed_is_right = (std::rand() % 2);
- address |= (computed_is_right ? 1ul << (tree_depth-1-level) : 0);
+ address |= (computed_is_right ? UINT64_C(1) << (tree_depth-1-level) : 0);
address_bits.push_back(computed_is_right);
bit_vector other(digest_len);
std::generate(other.begin(), other.end(), [&]() { return std::rand() % 2; });
#include "common/data_structures/merkle_tree.hpp"
#include "gadgetlib1/gadget.hpp"
+#include "gadgetlib1/gadgets/hashes/crh_gadget.hpp"
#include "gadgetlib1/gadgets/hashes/hash_io.hpp"
#include "gadgetlib1/gadgets/hashes/digest_selector_gadget.hpp"
#include "gadgetlib1/gadgets/merkle_tree/merkle_authentication_path_variable.hpp"
bit_vector address_bits;
size_t address = 0;
- for (long level = tree_depth-1; level >= 0; --level)
+ for (int64_t level = tree_depth-1; level >= 0; --level)
{
const bool computed_is_right = (std::rand() % 2);
- address |= (computed_is_right ? 1ul << (tree_depth-1-level) : 0);
+ address |= (computed_is_right ? UINT64_C(1) << (tree_depth-1-level) : 0);
address_bits.push_back(computed_is_right);
bit_vector other(digest_len);
std::generate(other.begin(), other.end(), [&]() { return std::rand() % 2; });
* @copyright MIT license (see LICENSE file)
*****************************************************************************/
-#include "algebra/curves/alt_bn128/alt_bn128_pp.hpp"
#ifdef CURVE_BN128
#include "algebra/curves/bn128/bn128_pp.hpp"
#endif
+#include "algebra/curves/edwards/edwards_pp.hpp"
+#include "algebra/curves/mnt/mnt4/mnt4_pp.hpp"
+#include "algebra/curves/mnt/mnt6/mnt6_pp.hpp"
#include "gadgetlib1/gadgets/merkle_tree/merkle_tree_check_read_gadget.hpp"
#include "gadgetlib1/gadgets/merkle_tree/merkle_tree_check_update_gadget.hpp"
#include "gadgetlib1/gadgets/hashes/sha256/sha256_gadget.hpp"
-#include <gtest/gtest.h>
-
using namespace libsnark;
template<typename ppT>
void test_all_merkle_tree_gadgets()
{
typedef Fr<ppT> FieldT;
+ test_merkle_tree_check_read_gadget<FieldT, CRH_with_bit_out_gadget<FieldT> >();
test_merkle_tree_check_read_gadget<FieldT, sha256_two_to_one_hash_gadget<FieldT> >();
+ test_merkle_tree_check_update_gadget<FieldT, CRH_with_bit_out_gadget<FieldT> >();
test_merkle_tree_check_update_gadget<FieldT, sha256_two_to_one_hash_gadget<FieldT> >();
}
-TEST(gadgetlib1, merkle_tree)
+int main(void)
{
start_profiling();
- alt_bn128_pp::init_public_params();
- test_all_merkle_tree_gadgets<alt_bn128_pp>();
-
#ifdef CURVE_BN128 // BN128 has fancy dependencies so it may be disabled
bn128_pp::init_public_params();
test_all_merkle_tree_gadgets<bn128_pp>();
#endif
+
+ edwards_pp::init_public_params();
+ test_all_merkle_tree_gadgets<edwards_pp>();
+
+ mnt4_pp::init_public_params();
+ test_all_merkle_tree_gadgets<mnt4_pp>();
+
+ mnt6_pp::init_public_params();
+ test_all_merkle_tree_gadgets<mnt6_pp>();
}
void fill_with_field_elements(protoboard<FieldT> &pb, const std::vector<FieldT>& vals) const;
void fill_with_bits(protoboard<FieldT> &pb, const bit_vector& bits) const;
- void fill_with_bits_of_ulong(protoboard<FieldT> &pb, const unsigned long i) const;
+ void fill_with_bits_of_ulong(protoboard<FieldT> &pb, const uint64_t i) const;
void fill_with_bits_of_field_element(protoboard<FieldT> &pb, const FieldT &r) const;
std::vector<FieldT> get_vals(const protoboard<FieldT> &pb) const;
void fill_with_field_elements(protoboard<FieldT> &pb, const std::vector<FieldT>& vals) const;
void fill_with_bits(protoboard<FieldT> &pb, const bit_vector& bits) const;
- void fill_with_bits_of_ulong(protoboard<FieldT> &pb, const unsigned long i) const;
+ void fill_with_bits_of_ulong(protoboard<FieldT> &pb, const uint64_t i) const;
void fill_with_bits_of_field_element(protoboard<FieldT> &pb, const FieldT &r) const;
std::vector<FieldT> get_vals(const protoboard<FieldT> &pb) const;
}
template<typename FieldT>
-void pb_variable_array<FieldT>::fill_with_bits_of_ulong(protoboard<FieldT> &pb, const unsigned long i) const
+void pb_variable_array<FieldT>::fill_with_bits_of_ulong(protoboard<FieldT> &pb, const uint64_t i) const
{
this->fill_with_bits_of_field_element(pb, FieldT(i, true));
}
}
template<typename FieldT>
-void pb_linear_combination_array<FieldT>::fill_with_bits_of_ulong(protoboard<FieldT> &pb, const unsigned long i) const
+void pb_linear_combination_array<FieldT>::fill_with_bits_of_ulong(protoboard<FieldT> &pb, const uint64_t i) const
{
this->fill_with_bits_of_field_element(pb, FieldT(i));
}
#include "common/profiling.hpp"
int main(int argc, char **argv) {
- /*libsnark::inhibit_profiling_info = true;
+ libsnark::inhibit_profiling_info = true;
libsnark::inhibit_profiling_counters = true;
testing::InitGoogleTest(&argc, argv);
- return RUN_ALL_TESTS();*/
- return(0);
+ return RUN_ALL_TESTS();
}
Declaration of interfaces for a R1CS-to-QAP reduction, that is, constructing
a QAP ("Quadratic Arithmetic Program") from a R1CS ("Rank-1 Constraint System").
- QAPs are defined in \[GGPR13], and constructed for R1CS also in \[GGPR13].
+ QAPs are defined in \[GGPR13], and construced for R1CS also in \[GGPR13].
The implementation of the reduction follows, extends, and optimizes
the efficient approach described in Appendix E of \[BCGTV13].
#include <cstring>
#include <vector>
-#include "algebra/curves/alt_bn128/alt_bn128_pp.hpp"
+#include "algebra/curves/mnt/mnt6/mnt6_pp.hpp"
#include "algebra/fields/field_utils.hpp"
#include "common/profiling.hpp"
#include "common/utils.hpp"
#include "reductions/r1cs_to_qap/r1cs_to_qap.hpp"
#include "relations/constraint_satisfaction_problems/r1cs/examples/r1cs_examples.hpp"
-#include <gtest/gtest.h>
-
using namespace libsnark;
template<typename FieldT>
See the transformation from R1CS to QAP for why this is the case.
So we need that qap_degree >= num_inputs + 1.
*/
- ASSERT_LE(num_inputs + 1, qap_degree);
+ assert(num_inputs + 1 <= qap_degree);
enter_block("Call to test_qap");
const size_t num_constraints = qap_degree - num_inputs - 1;
leave_block("Generate constraint system and assignment");
enter_block("Check satisfiability of constraint system");
- EXPECT_TRUE(example.constraint_system.is_satisfied(example.primary_input, example.auxiliary_input));
+ assert(example.constraint_system.is_satisfied(example.primary_input, example.auxiliary_input));
leave_block("Check satisfiability of constraint system");
const FieldT t = FieldT::random_element(),
leave_block("Compute QAP witness");
enter_block("Check satisfiability of QAP instance 1");
- EXPECT_TRUE(qap_inst_1.is_satisfied(qap_wit));
+ assert(qap_inst_1.is_satisfied(qap_wit));
leave_block("Check satisfiability of QAP instance 1");
enter_block("Check satisfiability of QAP instance 2");
- EXPECT_TRUE(qap_inst_2.is_satisfied(qap_wit));
+ assert(qap_inst_2.is_satisfied(qap_wit));
leave_block("Check satisfiability of QAP instance 2");
leave_block("Call to test_qap");
}
-TEST(relations, qap)
+int main()
{
start_profiling();
+ mnt6_pp::init_public_params();
+
const size_t num_inputs = 10;
+ const size_t basic_domain_size = UINT64_C(1)<<mnt6_Fr::s;
+ const size_t step_domain_size = (UINT64_C(1)<<10) + (UINT64_C(1)<<8);
+ const size_t extended_domain_size = UINT64_C(1)<<(mnt6_Fr::s+1);
+ const size_t extended_domain_size_special = extended_domain_size-1;
+
enter_block("Test QAP with binary input");
- test_qap<Fr<alt_bn128_pp> >(1ul << 21, num_inputs, true);
+ test_qap<Fr<mnt6_pp> >(basic_domain_size, num_inputs, true);
+ test_qap<Fr<mnt6_pp> >(step_domain_size, num_inputs, true);
+ test_qap<Fr<mnt6_pp> >(extended_domain_size, num_inputs, true);
+ test_qap<Fr<mnt6_pp> >(extended_domain_size_special, num_inputs, true);
leave_block("Test QAP with binary input");
enter_block("Test QAP with field input");
- test_qap<Fr<alt_bn128_pp> >(1ul << 21, num_inputs, false);
+ test_qap<Fr<mnt6_pp> >(basic_domain_size, num_inputs, false);
+ test_qap<Fr<mnt6_pp> >(step_domain_size, num_inputs, false);
+ test_qap<Fr<mnt6_pp> >(extended_domain_size, num_inputs, false);
+ test_qap<Fr<mnt6_pp> >(extended_domain_size_special, num_inputs, false);
leave_block("Test QAP with field input");
}
* Mnemonic typedefs.
*/
typedef size_t var_index_t;
-typedef long integer_coeff_t;
+typedef int64_t integer_coeff_t;
/**
* Forward declaration.
/********************************* Variable **********************************/
/**
- * A variable represents a formal expression of the form "x_{index}".
+ * A variable represents a formal expresison of the form "x_{index}".
*/
template<typename FieldT>
class variable {
}
print_header("R1CS ppzkSNARK Prover");
- r1cs_ppzksnark_proof<ppT> proof = r1cs_ppzksnark_prover<ppT>(keypair.pk, example.primary_input, example.auxiliary_input, example.constraint_system);
+ r1cs_ppzksnark_proof<ppT> proof = r1cs_ppzksnark_prover<ppT>(keypair.pk, example.primary_input, example.auxiliary_input);
printf("\n"); print_indent(); print_mem("after prover");
if (test_serialization)
* A proof for the R1CS ppzkSNARK.
*
* While the proof has a structure, externally one merely opaquely produces,
- * serializes/deserializes, and verifies proofs. We only expose some information
+ * seralizes/deserializes, and verifies proofs. We only expose some information
* about the structure for statistics purposes.
*/
template<typename ppT>
template<typename ppT>
r1cs_ppzksnark_proof<ppT> r1cs_ppzksnark_prover(const r1cs_ppzksnark_proving_key<ppT> &pk,
const r1cs_ppzksnark_primary_input<ppT> &primary_input,
- const r1cs_ppzksnark_auxiliary_input<ppT> &auxiliary_input,
- const r1cs_ppzksnark_constraint_system<ppT> &constraint_system);
+ const r1cs_ppzksnark_auxiliary_input<ppT> &auxiliary_input);
template<typename ppT>
r1cs_ppzksnark_proof<ppT> r1cs_ppzksnark_prover_streaming(std::ifstream &proving_key_file,
const Fr<ppT> rC = rA * rB;
- // construct the same-coefficient-check query (must happen before zeroing out the prefix of At)
+ // consrtuct the same-coefficient-check query (must happen before zeroing out the prefix of At)
Fr_vector<ppT> Kt;
Kt.reserve(qap_inst.num_variables()+4);
for (size_t i = 0; i < qap_inst.num_variables()+1; ++i)
#include <cassert>
#include <cstdio>
-#include "algebra/curves/alt_bn128/alt_bn128_pp.hpp"
+#include "common/default_types/r1cs_ppzksnark_pp.hpp"
#include "common/profiling.hpp"
#include "common/utils.hpp"
#include "relations/constraint_satisfaction_problems/r1cs/examples/r1cs_examples.hpp"
#include "zk_proof_systems/ppzksnark/r1cs_ppzksnark/examples/run_r1cs_ppzksnark.hpp"
-#include <gtest/gtest.h>
-
using namespace libsnark;
template<typename ppT>
const bool test_serialization = true;
r1cs_example<Fr<ppT> > example = generate_r1cs_example_with_binary_input<Fr<ppT> >(num_constraints, input_size);
- example.constraint_system.swap_AB_if_beneficial();
const bool bit = run_r1cs_ppzksnark<ppT>(example, test_serialization);
- EXPECT_TRUE(bit);
+ assert(bit);
print_header("(leave) Test R1CS ppzkSNARK");
}
-TEST(zk_proof_systems, r1cs_ppzksnark)
+int main()
{
+ default_r1cs_ppzksnark_pp::init_public_params();
start_profiling();
- test_r1cs_ppzksnark<alt_bn128_pp>(1000, 20);
+ test_r1cs_ppzksnark<default_r1cs_ppzksnark_pp>(1000, 100);
}
projects / VerusCoin.git / commitdiff