zkcrypto / bellman Goto Github PK
View Code? Open in Web Editor NEWzk-SNARK library.
License: Other
zk-SNARK library.
License: Other
I'm sorry to ask this question because this question does not involve the correctness of the code, but is purely a question of my own understanding. After inquiring some information, I did not get a suitable answer, so I think I can only ask the question in here it is.
I don't quite understand how the eval_of_tau
function in generator
works.
Here is the eval_at_tau
function:
bellman/src/groth16/generator.rs
Lines 371 to 384 in 9bb30a7
Its second parameter is the QAP polynomial stored in point-valued form:
bellman/src/groth16/generator.rs
Lines 313 to 316 in 9bb30a7
It's first parameter is powers_of_tau
, but this powers_of_tau
confuses me. In the front, this variable is exactly what it says, it is the powers of tau
bellman/src/groth16/generator.rs
Lines 244 to 259 in 9bb30a7
But before actually using it, make the following transformation:
bellman/src/groth16/generator.rs
Lines 294 to 295 in 9bb30a7
So as I understand it, from here on powers_of_tau
becomes the coefficients (a0, a1, ..an) of the polynomial f(x) such that
A polynomial of the form f(x) = a0 + a1 * x + a2 * x^2 .... an * x^n
Satisfy:
f(ฯ0) = tau^0
f(ฯ1) = tau^1
....
In this case, according to the implementation of the eval_at_tau
function
bellman/src/groth16/generator.rs
Lines 375 to 381 in 9bb30a7
How can this be the value of a QAP polynomial at tau?
Because powers_of_tau
has been ifft transformed before, so
powers_of_tau[index].0
here should be the index
th coefficient of f(x). What is the significance of multiplying this coefficient with coeff
?
I guess based on the comments, here is the equivalent to the point value form of QAP by doing Lagrangian interpolation, the formula:
Then coeff
is equivalent to $$ {y}_j $$
Then the j
th item of powers_of_tau
is equal to the l_j(x) corresponding to y_j?
Is this guess correct? Is there any formula to prove that they are indeed equal? Thanks!
Right now we use futures-cpupool
for one purpose (work stealing) and crossbeam
for another (scoped threads). I can get both of these with rayon
, which is also more mature, but in the past when I switched to rayon it was slower.
I think there are tweaks and new features in its API which would allow me to adopt it entirely.
This replaces the groth16
feature flag with a separate crate.
In order to improve performance during verification, it may be useful to precompute windows for input constraint terms during verification key preprocessing.
Lines 124 to 128 in 9bb30a7
// Input constraints to ensure full density of IC query
// x * 0 = 0
for i in 0..assembly.num_inputs {
assembly.enforce(|| "", |lc| lc + Variable(Index::Input(i)), |lc| lc, |lc| lc);
}
Hello,
I'm working on a simple merkle tree snark. I have printed logs to ensure that my circuit is working, but it seems to fail with this error before returning the proof. I'm unsure how to proceed as I'm following examples around the web that seem to work as well. Any ideas why I'm getting this error.
It occurs here: https://github.com/drewstone/rust-miximus/blob/master/src/zk_util.rs#L107
The unwrap fails with exactly this error:
thread 'test::test_generate_params' panicked at 'called `Result::unwrap()` on an `Err` value: IoError(Custom { kind: UnexpectedEof, error: StringError("expected more bases from source") })', src/libcore/result.rs:997:5
error: linking with `cc` failed: exit status: 1
[....]
= note: ld: library not found for -lgmp
clang: error: linker command failed with exit code 1 (use -v to see invocation)
error: could not compile `ecdsa-mpc` due to previous error
Install GMP with homebrew:
brew install gmp
Make sure gmp linked:
brew link --force gmp
Create file .cargo/config
in source code folder:
[target.x86_64-apple-darwin]
rustflags = [
"-L", "/opt/homebrew/lib",
"-L", "/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/lib",
"-C", "link-arg=-undefined",
"-C", "link-arg=dynamic_lookup",
]
[target.aarch64-apple-darwin]
rustflags = [
"-L", "/opt/homebrew/lib",
"-L", "/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/lib",
"-C", "link-arg=-undefined",
"-C", "link-arg=dynamic_lookup",
]
These flags was used to guide rustc
to look up libraries from homebrew. I'm prefer an official patch.
Took me a while to figure this one out, and I'm not entirely sure what the issue may be, but I've definitely narrowed it down to the fact that this API (bellman::groth16::Parameters::read<R: Read>(reader: R, checked: bool) -> Result<Self>
) locks up my machine when I specify checked = true
.
It seems like it works just fine when I don't use it (checked = false
), so I'm curious if the flag is even necessary or what it does where this behavior is encountered.
Hello,
I am looking to generate a trusted setup by usage of an MPC. I was wondering how to do this properly as currently I can only generate the trusted setup by myself.
Thank you
This way the variable assignment closure can query exotic constraint system types in order to optimize away inversions or do other kinds of cached operations.
Hi everyone, I'm new with zk-SNARKs, I'm trying build example with bellman
https://github.com/bui-duc-huy/bellman-example
I didn't knew why my example run very slow when generate_random_parameters
and create_random_proof
Anyone can explained me the reason.
Many thanks.
Ideally this would be a run-time rather than a compile-time option, so that clients of bellman such as zcashd could enable it based on a user setting. I know that constant-time MSM will be significantly slower; that's fine, and I think some people will want to take that trade-off.
It might be worth eliminating gamma from the verification key. I guess this isn't a huge deal, but my understanding from talking to @arielgabizon and Mary Maller is that it isn't actually necessary and you can just use the generator of G2.
This is useful from the point of view of proof composition because it makes the verification key smaller.
Hey everyone,
I want to make a verification system where I have to test the point wise multiplication of arrays. For instance, [20,20]*[1,0] = [20,0] is what I want to verify. So, what I did was I started with a multiplication circuit and then tried to use batch mode on entire array referring to https://github.com/zkcrypto/bellman/blob/main/benches/batch.rs
But, this does not work and gives me an error that bellman::groth16::batch does not exist. Please let me know how will I be able to fix it.
Thanks in advance
Appendix B.2 of the Zcash protocol spec describes how to do batched verification. The Zcash ticket is zcash/zcash#320 .
[Note that bellman can just provide batched and unbatched verification as separate APIs. We don't need to bikeshed here about how these will be used to implement Zcash consensus policy, as happened on the PR to add batched PHGR13 verification to libsnark; please keep that to the Zcash ticket.]
It doesn't really matter whether we use the full field or not (as long as z != 0
), but it makes various scalar mults cheaper.
Originally posted by @str4d in #59 (comment)
By "cost tree" I mean the number of constraints (and possibly other performance-relevant information) of each abstraction and the abstractions that it uses, recursively.
Hello! I am trying to implement a set membership proof circuit and I am having some trouble. I basically get the following error when generating the proof:
thread 'main' panicked at src/main.rs:217:70:
called `Result::unwrap()` on an `Err` value: IoError(Custom { kind: UnexpectedEof, error: "expected more bases from source" })
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Here's my main.rs
code:
use bellman::{
gadgets::{
boolean::{AllocatedBit, Boolean},
multipack,
sha256::sha256,
},
groth16, Circuit, ConstraintSystem, SynthesisError,
};
use bls12_381::Bls12;
use ff::PrimeField;
use merkle_tree::{NodeOrder, ProofListItem};
use rand::rngs::OsRng;
use sha2::{Digest, Sha256};
use crate::merkle_tree::MerkleTree;
mod merkle_tree;
mod utils;
/// Our own SHA-256d gadget. Input and output are in little-endian bit order.
fn sha256d<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
mut cs: CS,
data: &[Boolean],
) -> Result<Vec<Boolean>, SynthesisError> {
// Flip endianness of each input byte
let input: Vec<_> = data
.chunks(8)
.map(|c| c.iter().rev())
.flatten()
.cloned()
.collect();
let res = sha256(cs.namespace(|| "SHA-256(input)"), &input)?;
// Flip endianness of each output byte
Ok(res
.chunks(8)
.map(|c| c.iter().rev())
.flatten()
.cloned()
.collect())
}
fn merkle_proofd<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
mut cs: CS,
mut proof_list: Vec<ProofListItem>,
hashed_file_contents: &[Boolean],
) -> Result<Vec<Boolean>, SynthesisError> {
if proof_list.len() < 2 {
return Ok(Vec::new());
}
let res = contains_hash(
cs.namespace(|| "SHA-256(res)"),
&mut proof_list,
&hashed_file_contents,
);
match res {
Ok(Boolean::Constant(false)) | Err(_) => {
return Ok(Vec::new());
}
_ => {}
}
while proof_list.len() != 1 {
let h1 = proof_list.pop().unwrap();
let h2 = proof_list.pop().unwrap();
match h2.order {
Some(NodeOrder::Left) => {
let combined = [&h2.hash[..], &h1.hash[..]].concat();
let hash = sha256d(cs.namespace(|| "SHA-256(left_leaf)"), &combined).unwrap();
proof_list.push(ProofListItem::new(hash, None));
}
Some(NodeOrder::Right) => {
let combined = [&h1.hash[..], &h2.hash[..]].concat();
let hash = sha256d(cs.namespace(|| "SHA-256(right_leaf)"), &combined).unwrap();
proof_list.push(ProofListItem::new(hash, None));
}
None => {
panic!("Should not be None");
}
}
}
Ok(proof_list.pop().unwrap().hash)
}
fn boolean_or<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
mut cs: CS,
a: &Boolean,
b: &Boolean,
) -> Result<Boolean, SynthesisError> {
let not_a = Boolean::not(a);
let not_b = Boolean::not(b);
let not_a_and_not_b = Boolean::and(cs.namespace(|| "not A AND not B"), ¬_a, ¬_b)?;
Ok(Boolean::not(¬_a_and_not_b))
}
fn contains_hash<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
mut cs: CS,
proof_list: &mut Vec<ProofListItem>,
hash: &[Boolean],
) -> Result<Boolean, SynthesisError> {
let mut found = Boolean::constant(false); // Initially, no match is found.
for (i, item) in proof_list.iter().enumerate() {
if item.hash.len() != hash.len() {
continue; // Skip if lengths differ, cannot be equal.
}
let mut is_equal = Boolean::constant(true); // Assume equal until proven otherwise.
for (j, (a, b)) in item.hash.iter().zip(hash).enumerate() {
let equal_bits =
Boolean::xor(cs.namespace(|| format!("bit {} in item {}", j, i)), a, b)?;
let not_equal_bits = Boolean::not(&equal_bits);
is_equal = Boolean::and(
cs.namespace(|| format!("aggregate equality for item {}", i)),
&is_equal,
¬_equal_bits,
)?;
}
// Aggregate the results with OR across all items using the custom OR function
found = boolean_or(
cs.namespace(|| format!("aggregate found status after item {}", i)),
&found,
&is_equal,
)?;
}
Ok(found)
}
struct MerkleProofCircuit {
proof_list: Option<Vec<ProofListItem>>,
hashed_file_contents: Option<Vec<u8>>,
}
impl<Scalar: PrimeField> Circuit<Scalar> for MerkleProofCircuit {
fn synthesize<CS: ConstraintSystem<Scalar>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
let proof_list = self.proof_list.unwrap_or_default();
let bit_values = if let Some(hashed_file_contents) = self.hashed_file_contents {
hashed_file_contents
.into_iter()
.map(|byte| (0..8).map(move |i| (byte >> i) & 1u8 == 1u8))
.flatten()
.map(|b| Some(b))
.collect()
} else {
vec![None; 32 * 8]
};
assert_eq!(bit_values.len(), 32 * 8);
// Witness the bits of the preimage.
let hashed_file_content_bits = bit_values
.into_iter()
.enumerate()
// Allocate each bit.
.map(|(i, b)| AllocatedBit::alloc(cs.namespace(|| format!("preimage bit {}", i)), b))
// Convert the AllocatedBits into Booleans (required for the sha256 gadget).
.map(|b| b.map(Boolean::from))
.collect::<Result<Vec<_>, _>>()?;
// Now process proof_list, merkle_root, and file_contents in the merkle_proofd function
// Ensure merkle_proofd can handle dummy values correctly
let merkle_root = merkle_proofd(
cs.namespace(|| "merkle_root"),
proof_list,
&hashed_file_content_bits,
)?;
multipack::pack_into_inputs(cs.namespace(|| "pack hash"), &merkle_root)
}
}
fn main() {
let params = {
let c = MerkleProofCircuit {
proof_list: None,
hashed_file_contents: None,
};
groth16::generate_random_parameters::<Bls12, _, _>(c, &mut OsRng).unwrap()
};
let pvk = groth16::prepare_verifying_key(¶ms.vk);
// These are the factors we are proving knowledge of
let files = (1..=8)
.map(|i| {
let file_name = format!("file{}.txt", i);
let file_content = format!("File {} contents", i).into_bytes();
(file_name, file_content)
})
.collect();
let merkle_tree = MerkleTree::new(&files);
let merkle_root = merkle_tree.get_root_hash();
let merkle_proof = merkle_tree
.generate_merkle_proof("file1.txt", &files)
.unwrap();
let file_contents = files.get("file1.txt").unwrap().clone();
let hashed_file_contents: Vec<u8> = Sha256::digest(&file_contents).to_vec();
// Create an instance of our circuit (with the preimage as a witness).
let c = MerkleProofCircuit {
proof_list: Some(merkle_proof),
hashed_file_contents: Some(hashed_file_contents),
};
// Pack the hash as inputs for proof verification.
let hash_bits = multipack::bytes_to_bits_le(&merkle_root);
let inputs = multipack::compute_multipacking(&hash_bits);
let proof = groth16::create_random_proof(c, ¶ms, &mut OsRng).unwrap();
// assert!(groth16::verify_proof(&pvk, &proof, &[public_input]).is_ok());
println!("{:?}", groth16::verify_proof(&pvk, &proof, &inputs));
println!("Merkle Tree Proof verified!");
}
and some auxiliary items
#[derive(Clone, Debug, PartialEq)]
pub enum NodeOrder {
Right,
Left,
}
#[derive(Clone)]
pub struct ProofListItem {
pub hash: Vec<Boolean>,
pub order: Option<NodeOrder>,
}
Can anyone guide me to how to accomplish this? I didn't find any documentation or anything like that just a sha256 example and tried to modify that. I have a very high level understanding of how ZKP works so if its required to dig deeper please let me know. The circuit is supposed to implement the computation of a merkle root from a set of leaves. I assume that root is a public output and the verifier can check their merkle root against it?
It would be useful to add num_constraints
, num_inputs
and num_aux
methods to the ConstraintSystem
trait to get a quick sense of its cost. I think these methods are general enough to apply to all implementors of ConstraintSystem
. If you'd like I can send in a pull request for this as well.
getting an error saying (failed to resolve: could not find pairing
in bellman
)
Good day.
For some reason the libsnark
outputs a verifying key for Groth16 in a form of e(alpha_g1, beta_g2)
and other elements and bellman
has verifying key in a form of separate alpha_g1 and beta_g2
. First form is not verifiable in the current Ethereum EVM, although the second can be. Is there a specific reason why the libsnark
and bellman
formats are different?
Provide for both streamed proving (from a File
).
I'm pretty sure these added constraints are needed only in BCTV to create linear independence of public input polynomials. I don't think it's important for Groth16, could give a slight performance boost to remove them.
Lines 147 to 149 in 10c5010
Any chance this is in the pipeline?
I'll leave this open as a combination of tasks that people getting familiar with rust, zk-snarks, and bellman specifically can do to become proficient contributors to this codebase. Please respond or edit the list below.
I'll try to attempt some of the items mentioned as I get time. Hopefully other newbies to this codebase will also find this useful.
This issue was automatically generated. Feel free to close without ceremony if
you do not agree with re-licensing or if it is not possible for other reasons.
Respond to @cmr with any questions or concerns, or pop over to
#rust-offtopic
on IRC to discuss.
You're receiving this because someone (perhaps the project maintainer)
published a crates.io package with the license as "MIT" xor "Apache-2.0" and
the repository field pointing here.
TL;DR the Rust ecosystem is largely Apache-2.0. Being available under that
license is good for interoperation. The MIT license as an add-on can be nice
for GPLv2 projects to use your code.
The MIT license requires reproducing countless copies of the same copyright
header with different names in the copyright field, for every MIT library in
use. The Apache license does not have this drawback. However, this is not the
primary motivation for me creating these issues. The Apache license also has
protections from patent trolls and an explicit contribution licensing clause.
However, the Apache license is incompatible with GPLv2. This is why Rust is
dual-licensed as MIT/Apache (the "primary" license being Apache, MIT only for
GPLv2 compat), and doing so would be wise for this project. This also makes
this crate suitable for inclusion and unrestricted sharing in the Rust
standard distribution and other projects using dual MIT/Apache, such as my
personal ulterior motive, the Robigalia project.
Some ask, "Does this really apply to binary redistributions? Does MIT really
require reproducing the whole thing?" I'm not a lawyer, and I can't give legal
advice, but some Google Android apps include open source attributions using
this interpretation. Others also agree with
it.
But, again, the copyright notice redistribution is not the primary motivation
for the dual-licensing. It's stronger protections to licensees and better
interoperation with the wider Rust ecosystem.
To do this, get explicit approval from each contributor of copyrightable work
(as not all contributions qualify for copyright, due to not being a "creative
work", e.g. a typo fix) and then add the following to your README:
## License
Licensed under either of
* Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
* MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
at your option.
### Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
additional terms or conditions.
and in your license headers, if you have them, use the following boilerplate
(based on that used in Rust):
// Copyright 2016 bellman developers
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
It's commonly asked whether license headers are required. I'm not comfortable
making an official recommendation either way, but the Apache license
recommends it in their appendix on how to use the license.
Be sure to add the relevant LICENSE-{MIT,APACHE}
files. You can copy these
from the Rust repo for a plain-text
version.
And don't forget to update the license
metadata in your Cargo.toml
to:
license = "MIT/Apache-2.0"
I'll be going through projects which agree to be relicensed and have approval
by the necessary contributors and doing this changes, so feel free to leave
the heavy lifting to me!
To agree to relicensing, comment with :
I license past and future contributions under the dual MIT/Apache-2.0 license, allowing licensees to chose either at their option.
Or, if you're a contributor, you can check the box in this repo next to your
name. My scripts will pick this exact phrase up and check your checkbox, but
I'll come through and manually review this issue later as well.
I don't see any way to serialize the Proof<E>
struct; is something like this planned? (Presumably Zcash will require this as well once Sapling progresses enough).
The above is a great article explaining the details, it mentioned that the point is chosen randomly during setup
, but is it safe to do so? Is it possible that the chosen point has extremely low order?
At Zcon0, some of us had really great conversations on how to speed up SNARKs and some (I believe the codaprotocol folks) mentioned using GPU for parallelize proving. Since SNARKs are highly parallelizable (and since there is some work on showing that), what would it take to implement Bellman to be GPU friendly?
Anyone that in rust/gpu programming expert here?
Snarkjs is a widely used zk-snark library. How can I read the generated files of snarkjs (e.g. proof.json
, public.json
and verification_key.json
)?
I am a bit confused about saving the params
, proofs
and pvk
as JSON files so I can move them between machines.
I've followed the example repo at https://github.com/arcalinea/bellman-examples/blob/master/src/cube.rs#L154 and also see a write implementation on the proof structure here: https://github.com/zkcrypto/bellman/blob/master/src/groth16/mod.rs#L43
Can someone help me export these variables?
bellman/src/gadgets/boolean.rs
Line 474 in 0f2244f
#[derive(Debug, Clone)]
pub enum Boolean {
Constant(bool),
Other,
}
impl Boolean {
pub fn not(&self) -> Self {
match *self {
Boolean::Constant(c) => Boolean::Constant(!c),
_ => unreachable!()
}
}
pub fn xor(&self, other: &Self) -> Self {
match (self, other) {
(&Boolean::Constant(false), x) | (x, &Boolean::Constant(false)) => x.clone(),
(&Boolean::Constant(true), x) | (x, &Boolean::Constant(true)) => x.not(),
_ => unreachable!()
}
}
}
fn main() {
let a = Boolean::Constant(true);
let b = Boolean::Constant(true);
let c = a.xor(&b);
// Question: the result c should be `Boolean::Constant(true)` ?
assert_eq!(c, Boolean::Constant(false));
}
if x
is Boolean::Constant(true)
, will return Ok(Boolean::Constant(false))
. But true BitXor true
should be true
not false
?
With Ethereum now supporting BLAKE2b on-chain explicitly to support the ZCash POW algorithm, there is now an opportunity to use this same operation inside Dapps that parallel SNARK circuits. This allows for newer proving schemes such as commit-and-prove, recursive-, and composable-SNARKs to operate selectively on- or off-chain.
The BLAKE2s hash function is currently supported in gadget and function form but the similar BLAKE2b hash function is not. Would the new gadget and functions be useful?
Groth16 proving and verification key serialization needs to be implemented.
gamma
variable should be removed if it can be proven it's unneeded in Groth's construction.A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.