Commit Graph

203 Commits

Author SHA1 Message Date
Eran Tromer 12c6e21658 Extend profiling code to print parallelism (CPU_time / real_time).
Also tweak formatting formatting of block entry to drop "[0]} and better align with block exit.
Tested only on Linux, might generate compile or (informative) runtime errors on other platforms.
2015-10-13 14:09:38 +03:00
Eran Tromer 8a7512af33 Minor addition to profiling output: annotate whole FFTs (including multiplication by coset, etc.) 2015-10-13 14:09:38 +03:00
Eran Tromer 321a3b687d Use *all* cores for batch/multiexponentiation (was capped at 4).
This speeds up proving by x1.4 to x1.6 on several tested platforms with 6 or 8 cores.
2015-10-13 14:07:41 +03:00
Eran Tromer e2f9fe2949 Makefile fix (*.d cleaning was broken) 2015-10-04 20:26:36 +03:00
Eran Tromer 0c9bd4e205 Makefile fixes
* Use and clean up .d(ependency) files for executables's objects too.
* Rename OBJS and SRCS to LIB_OBJS and LIB_SRCS to clarify these don't include executables.
* Also, add index to libsnark.a and allow it as a target even if doing a non-static build.
2015-10-04 04:26:38 +03:00
Eran Tromer 032f8b1858 Makefile fixes
- Avoid unnecessarily rebuilding executables with unchanged dependencies (bug introduced by commit 998a2373)
- Avoid unnecessarily rebuilding GTest
- Tweak spacing and comments
2015-10-03 18:28:04 +03:00
Eran Tromer fcc4e584a5 "make clean" fix: also delete files that wouldn't be compiled due to NO_{GTEST,SUPERCOP} flags 2015-10-03 06:58:18 +03:00
Eran Tromer e42b38fdae Makefile: use -O3 in PERFORMANCE=1 2015-10-03 04:21:23 +03:00
Eran Tromer 51a5e1c4bd Makefile fix: use our custom g++ rule for executable's .o files too.
This adds the missing -MMD (to trigger recompilation when headers change) and beautifies the parameter order.
2015-10-03 04:21:23 +03:00
Eran Tromer 47ed57669e README.md tweaks 2015-10-03 04:21:23 +03:00
Eran Tromer 2e6fd83e3b README.md updates:
- Reflect many of the recent additions and refactoring in libsnark
  (at least at the level of brief mentions and pointers).
- More build instructions/hints.
- Minor cleanups.
2015-10-02 14:27:44 -04:00
Eran Tromer 998a23735a Makefile and prepare-depends improvements
- Refactor CXXFLAGS so that feature flags and optimization flags can be easily overriden from command line
- Add NO_SUPERCOP=1 option
- Avoid need to manually create ./depinst directory when ./prepare-depends is not needed (i.e., when BN128 and SUPERCOP are not used)
- Fix the flags for static build
- Build executables that need GTest even if we used an existing GTest rather than compiling it
- Minor cleanups and comments
2015-10-02 14:27:44 -04:00
Eran Tromer f403f084dc Fixed 32-bit compilation (std::max needs compatible arguments) 2015-10-02 14:27:44 -04:00
Eran Tromer b9f5cc0611 Fix building with CURVE=MNT4 and CURVE=MNT6 2015-10-02 14:27:44 -04:00
Madars Virza c0699fa8c4 Merge pull request #11 from mbbarbosa/adsnark
adsnark extension to libsnark
2015-09-09 22:23:36 -04:00
mbb 006b118255 adsnark extension 2015-08-20 11:54:02 +01:00
Madars Virza c9c0d51f74 Merge pull request #10 from gstew5/master
Add 'libssl-dev' and 'libboost-all-dev' to Ubuntu package dependencies
2015-08-12 19:02:09 -04:00
Madars Virza 725924fa84 Update .gitignore 2015-08-12 19:00:19 -04:00
Madars Virza da72a20178 Fix incorrect accounting in uscs_verification_key::size_in_bits(). 2015-08-12 18:59:38 -04:00
Madars Virza 51f87c326e Fix double-counting in r1cs_verification_key::size_in_bits().
(Reported by ADSNARK team.)
2015-08-12 18:58:44 -04:00
Gordon Stewart 44f1b2f80c Add 'libssl-dev' and 'libboost-all-dev' to Ubuntu package dependencies 2015-08-12 16:25:59 -04:00
Madars Virza 6739b576db Make sure that -lgtest is only passed for compiling the executables that needs it. 2015-08-12 12:45:25 -04:00
Madars Virza 87f13e5a6d Add a gadget implementation of SHA256. 2015-06-12 15:17:46 -04:00
Madars Virza 9b26563638 Make Merkle tree and set commitment gadgets take hash function as a parameter instead of hard-coding it. 2015-06-12 15:14:10 -04:00
Madars Virza ebdef62f03 Provide more semantic break-down of Merkle tree expected number of constraints. 2015-06-12 15:06:15 -04:00
Madars Virza 2e874fbe8c Provide more fine-grained accounting of expected constraints in knapsack hash. 2015-06-12 15:01:55 -04:00
Madars Virza b63a5c1700 Make HashT::get_block_size() return the block size of a hash function or 0 for variable input hashes. 2015-06-12 15:00:51 -04:00
Madars Virza 14a26c8c92 Remove knapsack-specific initialization from set commitment accumulator. 2015-06-12 14:58:31 -04:00
Madars Virza a6f9d09f3e Merkle tree requires 2*max_idx fit inside size_t. Assert that it is the case. 2015-06-12 14:57:49 -04:00
Madars Virza 124511b425 Silence a warning about signed/unsigned integer comparison. 2015-06-12 14:51:01 -04:00
Madars Virza 7959a22805 Compare sparse vectors according to their contents instead of their representation. 2015-06-12 14:49:17 -04:00
Madars Virza 1767d5d960 Remove an obsolete forward declaration. 2015-05-19 12:10:37 -07:00
Madars Virza eef7c1644a Fix a sort comparison function to properly implement C++ Compare concept. This closes #9. 2015-05-10 14:11:43 -04:00
Madars Virza af725eeb82 Fixes SNARK input consistency soundness bug identified by Bryan Parno.
A soundness bug in the input consistency check, found by Bryan Parno,
has been fixed. We thank Bryan for identifying the bug and for helping
us fix it.

Technical details: The bug affected the R1CS-to-QAP reduction, in that
some rank-1 constraint systems produced distinct, but not linearly
independent, QAP polynomials. The fix ensures independence. The cost
is an increase of QAP degree from cs.num_constraints()+1 to
cs.num_constraints()+cs.num_inputs()+1. Typically, cs.num_inputs() is
dominated by cs.num_constraints() so the degree increase is
negligible. Concretely, our experiments show that the increase is
typically less than 0.007% for all applications reported by us thus
far, including Zerocash [BCGGMTV14, S&P], SNARKs for TinyRAM [BCTV14,
USENIX Security], and Scalable Zero-Knowledge [BCTV14, CRYPTO].

See Remark 2.5 in the (revised) extended version of "Succinct
Non-Interactive Zero Knowledge for a von Neumann Architecture", at
http://eprint.iacr.org/2013/879 .
2015-05-09 17:41:28 -04:00
Madars Virza 650486e5d7 Automatically update the vector of cached knapsack coefficients if, at
the time of the call, it is too small.
2015-04-27 15:39:34 -04:00
Madars Virza da2e417b2b Reduce the redundancy in compliance predicate creation by factoring
out common parts cp_handler's and placing them in compliance predicate
base class. Update compliance_predicate interfaces to account for the
simpler, improved workflow (see changes in tally_cp_handler/run_r1cs_ppzkpcd).
2015-04-27 14:53:55 -04:00
Madars Virza a50f940072 Remove redundant argument. 2015-04-27 14:49:26 -04:00
Madars Virza 452d1fe74a Refactor Merkle tree authentication paths and set membership proofs to
be first class objects in gadgetlib1.
2015-04-27 03:44:26 -04:00
Madars Virza f325da61a7 Make digest_variable and block_variable more gadget-like by replacing
their fill_with_bits method with a corresponding call to
generate_r1cs_witness.
2015-04-27 03:39:49 -04:00
Madars Virza 15a7c06d20 Add tests for set commitment. 2015-04-27 10:03:34 +03:00
Madars Virza 55402f56a4 Add tests for Merkle trees 2015-04-27 10:03:34 +03:00
Madars Virza dfb993bd37 Add tests for knapsack CRH. 2015-04-27 10:03:34 +03:00
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