Cryptographic accumulators in Rust.
Home Page: https://cambrian.github.io/accumulator
License: MIT License
Cryptographic accumulators in Rust, implemented over a generic group interface. Batteries (RSA and class group implementations) included!
# Cargo.toml
[dependencies]
accumulator = { git = "https://github.com/cambrian/accumulator.git", tag = "v0.2.1" }Available here, and feel free to reach out with any questions.
We have a proof-of-concept for stateless Bitcoin nodes.
Please see our contribution guide. We are looking for long-term maintainers!
Sorry for the second issue
Here is a MWE for my issue on macOS 10.15.4
Run cargo new accumulatortest
Add accumulator dependency to cargo.toml
the last few lines of the terminal output are:
--- stderr
toom_interpolate_5pts.c:70:19: warning: expression result unused [-Wunused-value]
ASSERT_NOCARRY (mpn_divexact_by3 (v2, v2, kk1)); /* v2 <- v2 / 3 */
../../gmp-src/gmp-impl.h:1662:6: note: expanded from macro 'mpn_divexact_by3'
(3 & mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 3)))
~ ^
../../gmp-src/gmp-impl.h:2459:33: note: expanded from macro 'ASSERT_NOCARRY'
#define ASSERT_NOCARRY(expr) (expr)
^~~~
1 warning generated.
toom_interpolate_8pts.c:163:18: warning: expression result unused [-Wunused-value]
ASSERT_NOCARRY(mpn_divexact_by3 (r5, r5, 3 * n + 1));
~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../../gmp-src/gmp-impl.h:1662:6: note: expanded from macro 'mpn_divexact_by3'
(3 & mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 3)))
~ ^
../../gmp-src/gmp-impl.h:2459:33: note: expanded from macro 'ASSERT_NOCARRY'
#define ASSERT_NOCARRY(expr) (expr)
^~~~
1 warning generated.
../../gmp-src/mpz/mul.c:112:2: warning: add explicit braces to avoid dangling else [-Wdangling-else]
else
^
1 warning generated.
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(obprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(obvprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(obprntffuns.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(repl-vsnprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(obprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(obvprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(obprntffuns.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libprintf.a(repl-vsnprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(mp_clz_tab.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(obprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(obvprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(obprntffuns.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(repl-vsnprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(mp_clz_tab.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(obprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(obvprintf.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(obprntffuns.o) has no symbols
/Library/Developer/CommandLineTools/usr/bin/ranlib: file: .libs/libgmp.a(repl-vsnprintf.o) has no symbols
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: '-no-install' is ignored for kabylake-apple-darwin19.4.0
libtool: warning: assuming '-no-fast-install' instead
libtool: warning: assuming '-no-fast-install' instead
../../../gmp-src/test-driver: line 107: 26838 Segmentation fault: 11 "$@" > $log_file 2>&1
make[5]: *** [test-suite.log] Error 1
make[4]: *** [check-TESTS] Error 2
make[3]: *** [check-am] Error 2
make[2]: *** [check-recursive] Error 1
make[1]: *** [check-recursive] Error 1
make: *** [check] Error 2
thread 'main' panicked at 'Program failed with code 2: "make" "-j" "8" "check"', /Users/boltonbailey/.cargo/registry/src/github.com-1ecc6299db9ec823/gmp-mpfr-sys-1.2.2/build.rs:1147:13
because it's currently an 800-line blob of a file. See u256.rs in the zero branch.
A good thing to do would be to deduplicate the U256/U512 shared logic with a macro. The mul instance for U256 can probably be changed to return a U256, and a full_mul function could be added to replace what I currently have.
If you're curious, using the zero-allocation code speeds up the primality checkers by anywhere between 10 and 25%. The runtime can in theory be reduced by another few pct by eliminating intermediate conversions between U256s and U512s, after which I would call it Done™. Updating the multiplication functions should facilitate this.
This should be answered by aggressive testing on all accumulator implementations, involving O(10^9) additions + inclusion/exclusion proofs. Though no composite has been found which passes BPSW (i.e. a number which is both a base-2 Fermat and strong Lucas pseudoprime), could an attack be constructed if one were found?
(Tasks are roughly ordered.)
Code Tasks:
vc branch)bulletproofs library, we might want to have an explanatory notes module (see their lib.rs and docs).vscode folder and VS Code setup suggestions is fine, particularly for newbies trying to contribute; still, something to think about)CONTRIBUTING.md for external folks (see here for an example)rustfmt and compilation succeed. Since master is protected and since our contributor guide will discuss standards for code hygiene, this is mostly a sanity check mechanismCargo.tomlLaunch Tasks:
We need to agree on some mechanism to signal to an end-user that lower-level routines should be used with care, whether that be via good docs, Rust visibility modifiers, or something else.
See #31.
I have a simple (and perhaps very naive) question about the membership witness update. Is there a way around requiring the caller to provide the tracked_elements? We are trying to use the accumulator to avoid everyone having to maintain the full list of tracked elements.
Thanks for your help, and apologies if this is a very naive question.
edit: looking at the code, it seems that carrying around the prime hash product of the tracked elements would eliminate the need to provide them in full. Is this a correct understanding?
There is currently no type-level enforcement of class group elements being reduced and/or normalized. They always need to be reduced and normalized except when benchmarking/testing.
This enables us to write
#[deriving (Hash)]
struct X { ... }
to get hash(&self, hasher: &mut H)
instead of manually defining how to feed values into the hasher.
As part of this we'll be able to define hashes without having to go through the indirection of serialization, which is nice
I'll handle this myself over the next few days, but feedback is welcome
Current solution duplicates a lot of code. Benchmarks use macros, but tests are more complicated due to function tags. Should still be possible though.
Assume that I have access to all the elements of the set.
How do I accomplish [1-5]?
let acc = Accumulator::<Rsa2048, &'static str>::empty();
let acc = acc.add(&["dog"]); // A = {"dog"}
let acc = acc.add(&["cat"]); // A = {"dog", "cat"}
let acc = acc.add(&["cow"]); // A = {"dog", "cat", "cow"}
// 1. Get Membership proof of "dog" given acc and all elements in A
// 2. Get Non-Membership proof of "pig", given acc and all elements in A
// 3. Get Batch Membership proof of "dog" and "cat", given acc and all elements in A
// 4. Verify Membership proof of "dog" using acc and proof from 1.
// 5. Verify Batch Membership proof of "dog" and "cat" using acc and proof from 3.I prefer not using the update_membership_witness.
Thanks in advance!
Currently the test_reduce_basic function in src/group/class.rs reduces an element that becomes reduced after performing normalization. This causes the main while loop in reduce to remain untested. An element that remains unreduced after being normalized should be chosen instead.
For example, we can generalize
Accumulator<G: UnknownOrderGroup>
to
Accumulator<T: Hash, G: UnknownOrderGroup>
and add goes from
fn add(self, elems: &[Integer]) -> (Self, MembershipProof<G>)
to
fn add(self, elems: &[T]) -> (Self, MembershipProof<T, G>)
The type parameter T in the accumulator struct would be a phantom type to help prevent mixing accumulators for different element types
I'm reading the implementation, there is no reduce operation in _op, can reduce improve the performance?
Hi,
I've been trying to implement this zero knowledge proof of membership technique. I was wondering if you had any advice on the following regarding design:
Where to put the code to create a random group generator (I had thought I could just write G::elem(Integer) where Integer is the group generator, but that doesn't seem to work--the compiler complains that there is no variant elem. Perhaps it is better to implement the random group generator function inside the group implementations?
Thanks. Apologies if not clear or if I just missed something painfully obvious.
Hi,
I have one conceptual question and I would really appreciate it if you could give me an answer... What is your rule of selecting the generator g? Is g any number random selected between 1 and pq? Or is there more constraint on it?
And I read that g is a generator of an RSA group, but I didn't quite understand this... What does it mean by an RSA group? Is this a ring Z_N where N=pq? I don't think g can generate all numbers between 0 and N-1.
hash_to_prime is slow, and (unless I'm mistaken) the only property of it that we use is that it's a 256-bit number. Can this be replaced with a constant?
Not a milestone issue, but:
It'd be cool if we could compile the accumulators to WASM and create a browser demo. Rust that relies on I/O (and maybe also the threading runtime) is off-limits for this purpose, so there might be some fiddling to do based on our dependencies.
Let's visit this after the open-sourcing?
We should provide newtypes/structs for accumulators and their proofs so we're not working with raw group elements/exponents.
In
accumulator/src/proof/poke2.rs
Line 19 in c1450aa
And
accumulator/src/proof/poke2.rs
Line 32 in c1450aa
The NI-PoKE2 implementation uses the group generator, however the BBF'18 paper denotes that g ← H_𝔾(u,w) in the non-interactive context. (see pg42, appendix D)
I think this is significant, in the non-interactive context, because it ensures the whole equation is parameterised by u and w, whereas without the 'hash to group' function being used for the generator of g^x you potentially weaken the proof.
I can't see a 'hash to group' function in the source code.
What are your thoughts?
Two question:
pub static ref NEW_MAX_SAFE_EXPONENT: Integer = {
//2^\{252\} + 27742317777372353535851937790883648493
let str_max_scalar = "7237005577332262213973186563042994240857116359379907606001950938285454250989";
Integer::from_str_radix(str_max_scalar, 10).unwrap()
};
pub static ref NEW_MAX_SAFE_SCALAR: Scalar = {
let mut digits: [u8; 32] = [0; 32];
NEW_MAX_SAFE_EXPONENT.write_digits(&mut digits, Order::LsfLe);
Scalar::from_bytes_mod_order(digits)
};
remaining >= *MAX_SAFE_EXPONENT the while loop is not proper for it will break the binding property ----for different values can be opened to the same commitment. let exp_c = Ristretto::exp(&bp, &(NEW_MAX_SAFE_EXPONENT.clone() + &int(20)));
let exp_d = Ristretto::exp(&bp, &int(20));
let exp_e = Ristretto::exp(&bp, &(NEW_MAX_SAFE_EXPONENT.clone() * &int(11) + &int(20)));
assert_eq!(exp_c, exp_d); //break commitment binding property
assert_eq!(exp_e, exp_d); //break commitment binding property
Cargo bench gives me the following error:
error[E0308]: mismatched types
--> src/uint.rs:53:16
|
53 | d: self.data(),
| ^^^^^^^^^^^ expected struct NonNull, found *-ptr
...
418 | u_types!(U256, 4, U512, 8);
| --------------------------- in this macro invocation
|
= note: expected struct NonNull<u64>
found raw pointer *mut u64
= note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
error[E0308]: mismatched types
--> src/uint.rs:536:8
|
536 | d: mut_ptr(&data),
| ^^^^^^^^^^^^^^ expected struct NonNull, found *-ptr
|
= note: expected struct NonNull<u64>
found raw pointer *mut &mut u64
Did anyone else got this? Is there a quick solution?
I run to BadWitness error when I try to generate membership proof for an element from the output of compute_individual_witnesses.
In this example, I am trying to verify the membership of "cat" in the set after performing batch add. However, I run into errors at prove_membership.
let acc = Accumulator::<G, &'static str>::empty();
let (acc, proof) = acc.add_with_proof(&["dog", "cat", "cow"]);
let witness = Witness(acc.clone());
let indv_witness = witness.compute_individual_witnesses(&["dog", "cat", "cow"]);
let proof_cat = acc.prove_membership(&[indv_witness[1].clone()]).unwrap(); // Bad witness
println!("Cat: {:?}", acc.verify_membership(&"cat", &proof_cat));thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: BadWitness', src/libcore/result.rs:999:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.I think we don't have the function for Witness generation for a particular element, except for using add_with_proof function when adding. But if I want to get the witness for an existing element inside the accumulator, how can I implement that?
1 cd accumulator then i execute cargo test or cargo bench
2 error message displays 'failed to run custom build command for 'gmp-mpfr-sys v1.2.4' '
3 How to solve this problem？How to run this code in vscode？ can you trouble write it in more detail？thank you
Attempting to install using the instructions on the readme, I get the following error:
$ cargo run
Updating git repository `https://github.com/cambrian/accumulator.git`
error: failed to load source for a dependency on `accumulator`
Caused by:
Unable to update https://github.com/cambrian/accumulator.git
Caused by:
failed to update submodule `docs`
Caused by:
failed to fetch submodule `docs` from ssh://[email protected]/cambrian/accumulator.git
Caused by:
failed to authenticate when downloading repository
attempted ssh-agent authentication, but none of the usernames `git` succeeded
Caused by:
no authentication available
It'd be cool if we could compile the accumulators to WASM and create a browser demo. Rust that relies on I/O (and maybe also the threading runtime) is off-limits for this purpose, so there might be some fiddling to do based on our dependencies.
React
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
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
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.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.