Bulletproofs and Bulletproofs+ Rust implementation for Aggregated Range Proofs over multiple elliptic curves

Last update: Dec 13, 2022

Overview

Bulletproofs

This library implements Bulletproofs+ and Bulletproofs aggregated range proofs with multi-exponent verification. The library supports multiple elliptic curves: secp256k1 , ristretto , ed25519

Usage

Control range and batch size using n,m variables. Supported range is any number 0<n<2^64. The library contains multiple test examples that can be followed (run them with Cargo test). To change an elliptic curve, change feature for Curv dependency inside Cargo.toml.

Benchmarks

Run cargo bench. For ristretto the current implementation is ~4x slower than dalek-cryptography.

Contact

Feel free to reach out or join the ZenGo X Telegram for discussions on code and research.

Comments

Non-power of 2 Inner-Product Argument

This Bulletproofs implementation doesn't support inner-product argument generation and verification for inputs of sizes other than powers of 2. How do we use inner-product argument for input sizes not a power of 2? Also, how do we realise it in implementation?

opened by suyash67 4
Not proper expression for formula (7) in Bulletproofs+？

I‘m reading the paper Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger, formular (7) in Page 5 is using z to combine the three contraints into one, but I don't think the expression is right for the following reason:

OR anything wrong for my comprehension?

opened by 3for 2
Inner-Product Verification with Multiexponentiation | Inner-Product Protocol for Non-powers of 2
Faster inner product proof verification using a single multi-exponentiation as described in Section 3.1 of the Bulletproofs paper. Improves the inner product verification by ~30%

Protocols similar in spirit to Bulletproofs require support for inner product protocol with secret vector sizes a non-power of 2. I have added a test demonstrating the same. The idea is simple: 2.1 Append secret vectors with 0's to make them the next power of 2 2.2 Extend the original base vectors to make them too the next power of 2 2.3 Compute vector exponentiations with a condition to check any 0's. This ensures minimum overhead computational cost due to modification of vector sizes to the next power of 2.
opened by suyash67 1
Faster Verification of Bulletproofs and Bulletproofs+

Improved verification speed of BP, BP+ by 1.3X to 2.2X and 1.6X to 2X respectively by compressing all the verification equations into a single multi-exponentiation check. This factor decreases as the number of proofs aggregated increases. A brief write-up about how we reduce verification to a single check is present in this blog.

opened by suyash67 0
Weighted Inner Product Based Range Proofs
Implementing range proofs with size 15% shorter than that of the original Bulletproofs protocol using weighted inner product argument introduced in Bulletproofs+ paper.

[x] Write weighted inner product (wip) prover and verifier functions.

[x] Fasten verification using multi-exponentiation in wip.

[x] Scalar power and multiplication optimisations in wip.

[x] Range proof using wip protocol and comparison with Bulletproofs.

[x] Benchmark wip and the associated range proof.

enhancement
opened by suyash67 0
Generic over choice of curve
PR makes algorithms described in the crate generic over choice of curve.

Blocked on:

[ ] https://github.com/ZenGo-X/curv/pull/96 PR

[ ] Caught a bug. Aggregation range proof doesn't work for p256 curve. Failing test: test_agg_batch_4_range_proof_64_p256. It works for all other curves. All other algorithms work fine with all curves including p256.

[ ] I renamed and rewrote function generate_random_point to support all other curves - now it's derive_point. It worths a quick look if it's fine
opened by survived 0
add interface for zero knowledge interval proof
prove that a pedersen commitment is to a value a<x<b. If b-a is a power of 2 this can be done non interactively with only one range proof assuming the:

prover commits to a value a<x<b

prover generates a pedersen commitment to a value a

prover generates a range proof to commitment that is commitment from 1 minus commitment from 2

prover sends range proof together with the opening of the commitment from 2
opened by omershlo 0

Releases(v1.1.6)

v1.1.6(May 13, 2021)

Source code(tar.gz)
Source code(zip)

Owner

[ZenGo X]

Threshold cryptography for blockchains. Projects with "city" in name are work in progress.

GitHub

Rust implementation of multi-party Schnorr signatures over elliptic curves.

Multi Party Schnorr Signatures This library contains several Rust implementations of multi-signature Schnorr schemes. Generally speaking, these scheme

148 Dec 15, 2022

L2 validity rollup combined with blind signatures over elliptic curves inside zkSNARK, to provide offchain anonymous voting with onchain binding execution on Ethereum

blind-ovote Blind-OVOTE is a L2 voting solution which combines the validity rollup ideas with blind signatures over elliptic curves inside zkSNARK, to