Commit Graph

211 Commits

Author SHA1 Message Date
Madars Virza abf63ed568 Document mixed addition optimization. 2015-04-27 10:03:34 +03:00
Madars Virza 94d1b48032 Add more debugging printouts for gadget_from_r1cs 2015-04-27 10:03:34 +03:00
Madars Virza 446eb80296 Specify license for the TBCS to USCS reduction script. 2015-04-27 10:03:33 +03:00
Madars Virza 859905fc64 operator+ for linear_combination is a linear time operation, so
building a O(n)-sized linear combination by repeatedly concatenating
O(1)-sized linear combinations is O(n^2) operation. (This is akin to
the caveat for Python strings.)

This commit optimizes the constructions of CRH and packing gadgets to
be quasi-linear time operations, down from previously quadratic time.
2015-04-27 10:03:33 +03:00
Madars Virza 99d9676152 Add an option to switch between Montgomery and equivalence class representations for field element output. 2015-04-27 10:03:33 +03:00
Madars Virza e1693483fb Fix a typo in include path; this closes #7. 2015-04-08 23:10:15 -04:00
Madars Virza 15034efe66 Add an implementation of a zk-SNARK for multi-predicate PCD, based on [CTV15]. 2015-03-27 02:13:09 -04:00
Madars Virza 0817f115ca Extend compliance predicate interfaces and PCD tally example to provide information about accepted input types. 2015-03-27 02:12:13 -04:00
Madars Virza dacd5e8b9b Fix off-by-one error in method that converts PCD auxiliary input to R1CS auxiliary input. 2015-03-27 02:12:13 -04:00
Madars Virza 8f00e426b1 Enable serialization testing for single-predicate PCD; small cosmetic fixes. 2015-03-27 02:12:13 -04:00
Madars Virza 69234ed071 Update tally PCD example in preparation for multiple predicates. 2015-03-27 02:12:13 -04:00
Madars Virza 82ac1014bf Add native and constraints implementations for Merkle-tree based commitments to sets. 2015-03-27 02:12:06 -04:00
Madars Virza c7bb97a958 Simplify RAM zkSNARK compliance predicate implementation, based on refactored interfaces. 2015-03-27 01:02:25 -04:00
Madars Virza c298ce6d33 Factor out native and constraints implementations of Merkle tree. 2015-03-27 00:59:41 -04:00
Madars Virza 797e5da7ee Make more gadgets accept linear combinations. 2015-03-27 00:51:53 -04:00
Madars Virza 6f2ed7d850 Remove obsolete vector comparator. 2015-03-27 00:46:01 -04:00
Madars Virza d0abffae2f Update gadgetlib2 to account for split R1CS variable assignment. 2015-03-05 15:47:22 -05:00
Madars Virza 81387cef8f Add tests for QAP and SSP. 2015-03-05 15:47:22 -05:00
Madars Virza 9a4fa87f4c Fix warnings about unused variables. 2015-03-05 15:47:22 -05:00
Madars Virza 826d9be011 Update Makefile and .gitignore 2015-03-05 15:47:22 -05:00
Madars Virza 93434b3fde Add an implementation of fully scalable zk-SNARK, based on BCTV14b. 2015-03-05 15:47:22 -05:00
Madars Virza 5fbf26f364 Add an implementation of proof-carrying data, based on BCTV14b. 2015-03-05 15:47:22 -05:00
Madars Virza 6596016b40 Add implementation of mnt4 and mnt6 curve choices. Add tests for curves and fields and affine verifier support for R1CS. 2015-03-05 15:47:22 -05:00
Madars Virza fb78e52c08 Update Makefile 2015-03-05 15:47:22 -05:00
Madars Virza 9a716cf291 Add an implementation of TinyRAM and the BCTV14 reduction. 2015-03-05 15:47:22 -05:00
Madars Virza b1edf64b11 Specify USCS relation in terms of primary input and auxiliary input 2015-03-05 15:47:22 -05:00
Madars Virza 3473d8f02b Specify R1CS relation in terms of primary input and auxiliary input (we previously had input = primary_input and witness = concat(primary_input, auxiliary_input) 2015-03-05 15:47:22 -05:00
Madars Virza ddf6e433b4 Introduce convenience template aliases for BACS and TBCS ppZKSNARK parameters. 2015-03-05 15:47:22 -05:00
Madars Virza 30ee4a347d Improve const correctness in gadgetlib1. Introduce pb_packing_sum, that returns a linear combination expressing a packing relationship. 2015-03-05 15:47:22 -05:00
Madars Virza 8e73fc8948 Make more gadgetlib1 gadgets accept linear combinations; introduce dual variable gadget; other small tweaks 2015-03-05 15:47:22 -05:00
Madars Virza 9b68c4b8aa More semantic naming in variable.hpp/tcc 2015-03-05 15:47:22 -05:00
Madars Virza 45fc3775a9 Split out demo files for ppzkSNARK proof systems into separate profiling and test files. 2015-03-05 15:47:22 -05:00
Madars Virza 6e0d6acf8e Fix validity checks for BACS and TBCS circuit satisfication problems and add additional debugging infrastructure. 2015-03-05 15:47:22 -05:00
Madars Virza f83c6e0715 Small tweaks in files under src/common. 2015-03-05 15:47:22 -05:00
Madars Virza 6867714837 Various fixes in scalar multiplication, in particular ensure correct operation when number of cores exceeds the number of scalars. 2015-03-05 15:47:22 -05:00
Madars Virza 8af91c8c51 Make field_utils functions consistently use size_in_bits()/capacity() methods of a field element. 2015-03-05 15:47:22 -05:00
Madars Virza ece441f780 Fix comments for exponentiation. 2015-03-05 15:47:22 -05:00
Madars Virza 134f1c91c6 Another cpplint fix: use pass-by-reference in evaluation domain; also ensure that we use long integers in computations. 2015-03-05 15:47:22 -05:00
Madars Virza dca74cf226 Add input/output operators for Fp6 (as 2-over-3 tower) 2015-03-05 15:47:22 -05:00
Madars Virza 22aacb5b5c Fix off-by-one error in field element randomization 2015-03-05 15:47:22 -05:00
Madars Virza 4fee16edf3 Process cpplint results: use pass by reference in Fp_model 2015-03-05 15:47:22 -05:00
Madars Virza ba350d2e48 Use standard terminology for curve point addition in special form. 2015-03-05 15:47:22 -05:00
Madars Virza da87e6891e Refactor public parameters 2015-03-05 15:47:22 -05:00
Madars Virza ee4922fd64 Factor out multiexp again. 2015-03-05 15:47:22 -05:00
Madars Virza 71912b6bcc Factor out exponentiation. 2015-03-05 15:47:22 -05:00
Madars Virza be61e9b815 Fix bn128_GT serialization bug and work around problems in upstream equality testing code. 2015-03-05 15:47:22 -05:00
Madars Virza a8faf9acdc The great reshuffling. 2015-03-05 15:47:22 -05:00
Madars Virza 2474695678 Add a preprocessing zkSNARK for Bilinear Arithmetic Circuit Satisfiability problem, based on R1CS ppzkSNARK. 2015-03-05 15:47:22 -05:00
Madars Virza 51d070398f Add a preprocessing zkSNARK for Two-input Boolean Circuit Satisfiability problem, based on USCS ppzkSNARK. 2015-03-05 15:47:22 -05:00
Madars Virza e48c501e08 Add preprocessing zkSNARK for Unitary-Square Constraint Systems. 2015-03-05 15:47:22 -05:00