docknetwork / crypto Goto Github PK

Rust crypto library for data privacy tools

License: Apache License 2.0

Rust 64.99% Sage 0.18% Circom 34.76% C 0.07%

cryptography accumulator zero-knowledge-proofs signatures anonymous-credentials distributed-key-generation dkg pairing-cryptography schnorr zk-snarks

crypto's Introduction

TBD

Library providing privacy enhancing cryptographic primitives.

Primitives

Schnorr proof of knowledge protocol to prove knowledge of discrete log and inequality of discrete logs. This is a good reference.
BBS and BBS+ signatures for anonymous credentials. BBS+ is based on the paper Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited and BBS is based on the paper Revisiting BBS Signatures. Also implements the threshold variants of these based on the paper Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance
Dynamic accumulators, both positive and universal. Based on the papers Dynamic Universal Accumulator with Batch Update over Bilinear Groups and Efficient Constructions of Pairing Based Accumulators
Composite proof system that combines above primitives for use cases like
- prove knowledge of a BBS+ signature and the corresponding messages
- prove knowledge of a modified PS signature and the corresponding messages
- equality of signed messages (from same or different signatures) in zero knowledge
- the (non)membership of a certain signed message(s)in the accumulator
- numeric bounds (min, max) on the messages can be proved in zero-knowledge
- verifiable encryption of signed messages under BBS+.
- zk-SNARK created from R1CS and WASM generated by Circom with witnesses as BBS+ signed messages (not exclusively though).
Verifiable encryption using SAVER.
Compression and amortization of Sigma protocols. This is PoC implementation.
Secret sharing schemes and DKG. Implements verifiable secret sharing schemes and DKG from Gennaro and FROST. Also implements protocol to do a distributed DLOG check.
Cocount and PS signatures. Based on the paper Security Analysis of Coconut, an Attribute-Based Credential Scheme with Threshold Issuance
LegoGroth16. LegoGroth16, the LegoSNARK variant of Groth16 zkSNARK proof system
Oblivious Transfer (OT) and Oblivious Transfer Extensions (OTE).
Short group signatures. BB signature and weak-BB signature and their proofs of knowledge based on the papers Short Signatures Without Random Oracles and Scalable Revocation Scheme for Anonymous Credentials Based on n-times Unlinkable Proofs.

Composite proof system

The proof system that uses above-mentioned primitives.

Build

cargo build or cargo build --release

By default, it uses standard library and rayon for parallelization

To build with standard library but without parallelization, use cargo build --no-default-features --features=std

For no_std support, build as cargo build --no-default-features --features=wasmer-sys

For WASM, build as cargo build --no-default-features --features=wasmer-js --target wasm32-unknown-unknown

Test

cargo test

The above maybe slower as it runs the tests in debug mode and some tests work on large inputs. For running tests faster, run cargo test --release

Benchmarking

Criterion benchmarks here

Some tests also print time consumed by the operations, run cargo test --release -- --nocapture [test name]

WASM wrapper

A WASM wrapper has been created over this repo here. The wrapper is then used to create this Typescript library which is more ergonomic than using the wrapper as the wrapper contains free floating functions.

crypto's People

Contributors

Stargazers

Watchers

crypto's Issues

Can BBS+ signature be a delegatable credentials

I am new to zero-knowledge proofs and would like to ask how the contents of the delegatable_credentials/ directory can be combined with BBS+signatures. Can a BBS+ signature be a delegatable credential？

`disjoint_witness_equalities` does not ensure disjoint lists

There is a bug in disjoint_witness_equalities, which results in not ensuring disjoint lists. The problem is that, when merging current with an overlapping list here, this may introduce a transitive equality with a list that we've already skipped and not merged.

The result is that verify fails, even though the given witnesses do meet all requirements.

A simple solution is to run the algorithm repeatedly until the number of lists does not change.

I'm not in a position to make a pull request, I'm afraid, but I can offer the following to aid with reproducing and testing a fix.

        let input_eqs =
              vec![
                  vec![(0, 1), (2, 0)],
                  vec![(0, 5), (1, 2)],
                  vec![(0, 5), (3, 0)],
                  vec![(1, 3), (5, 0)],
                  vec![(1, 2), (4, 0)],
              ];

        let current_result =
              vec![
                  vec![(0, 1), (2, 0)],
                  vec![(1, 3), (5, 0)],
                  vec![(0, 5), (1, 2), (4, 0)],  // NOTE: (0,5) is in both of the last
                  vec![(0, 5), (3, 0)]           // two, so these are not disjoint
              ];

        let one_correct_result =
              vec![
                vec![(0, 1), (2, 0)],
                vec![(0, 5), (1, 2), (3, 0), (4, 0)],
                vec![(1, 3), (5, 0)]
            ];

        // This passes
        check!(input_eqs.clone(), current_result);

        // This fails
        check!(input_eqs, one_correct_result);

First part of if condition redundant

crypto/compressed_sigma/src/amortized_homomorphism.rs

Line 79 in 2eee4a6

if witnesses.len() > j && witnesses[j].len() > i {

We check if witnesses.len() > j, but j < witnesses.len() by definition so this is trivially true.

ps_proof benchmark fails

Hi I'm 0xvon. I'd like to compare some algorithms for blind signatures and its SPKs.
That library especially seems to be so helpful for the performance analysis. However, I failed running ps_proof benchmark due to an error.

Issue Description

When I run the benchmark of ps signature's SPK whis that command:

cargo bench --bench=ps_proof

The error causes with that message.

...
Creating proof for Proof-of-knowledge of signature and corresponding multi-message of size 4/Reveali... #4
                        time:   [6.5353 ms 6.6979 ms 6.8960 ms]
                        change: [-3.8391% +0.2687% +4.7065%] (p = 0.89 > 0.05)
                        No change in performance detected.
Found 12 outliers among 100 measurements (12.00%)
  1 (1.00%) high mild
  11 (11.00%) high severe
thread 'main' panicked at benches/benches/ps_proof.rs:150:14:
called `Result::unwrap()` on an `Err` value: MessageInputError(NoMessagesProvided)
stack backtrace:
   0: _rust_begin_unwind
   1: core::panicking::panic_fmt
   2: core::result::unwrap_failed
   3: ps_proof::main
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
error: bench failed, to rerun pass `-p benches --bench ps_proof`

cause

I guess the function UnpackedBlindedMessages::new() doesn't allow empty messages.

solution

I propose two directions to fix this issue. Can you please give me some comments for it?
If you don't take time to fix that quickly, I can help.

Fix benches to skip for empty messages
Fix impl to allow empty messages

some crates use path to reference other creates, others do not: leading to "two version" problem

I am compiling some code I added to a custom crate (here called xxxx).
It has been compiling fine until I rebased to f5b61cd.
Now I am getting several errors like:

error[E0308]: arguments to this function are incorrect
   --> xxxx/src/proofsystem_algo.rs:102:20
    |
102 |     statements.add(PoKSignatureBBSG1Stmt::new_statement_from_params(
    |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
note: expected struct `bbs_plus::setup::SignatureParamsG1`, found struct `SignatureParamsG1`
   --> xxxx/src/proofsystem_algo.rs:103:9
    |
103 |         sig_params.clone(),
    |         ^^^^^^^^^^^^^^^^^^
    = note: struct `SignatureParamsG1` and struct `bbs_plus::setup::SignatureParamsG1` have similar names, but are actually distinct types
note: struct `SignatureParamsG1` is defined in crate `bbs_plus`
   --> /Users/me/ws/OLABS/github-docknetwork-crypto-NEW-f5b61cd/bbs_plus/src/setup.rs:343:1
    |
343 | impl_sig_params!(SignatureParamsG1, G1Affine, G1, G2Affine, G2);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: struct `bbs_plus::setup::SignatureParamsG1` is defined in crate `bbs_plus`
   --> /Users/me/.cargo/registry/src/github.com-1ecc6299db9ec823/bbs_plus-0.11.0/src/setup.rs:343:1
    |
343 | impl_sig_params!(SignatureParamsG1, G1Affine, G1, G2Affine, G2);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: perhaps two different versions of crate `bbs_plus` are being used?

This might be related to a cargo issue: rust-lang/cargo#11490

Note, the top-level Cargo.lock file does have two versions of bbs_plus in it:

name = "bbs_plus"
version = "0.11.0"
dependencies = [
 "ark-bls12-381",
 "ark-ec 0.4.1",
 "ark-ff 0.4.1",
 "ark-serialize 0.4.1",
 "ark-std 0.4.0",
 "blake2",
 "digest 0.10.6",
 "dock_crypto_utils 0.9.0",
 "rayon",
 "rmp-serde",
 "schnorr_pok 0.9.0",
 "serde",
 "serde_json",
 "serde_with",
 "zeroize",
]

[[package]]
name = "bbs_plus"
version = "0.11.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f9007b7a0f5ce3fe4b22e3acbbd05d7fbb13e722cb6380254ed0ae3684764602"
dependencies = [
 "ark-ec 0.4.1",
 "ark-ff 0.4.1",
 "ark-serialize 0.4.1",
 "ark-std 0.4.0",
 "digest 0.10.6",
 "dock_crypto_utils 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
 "rayon",
 "schnorr_pok 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
 "serde",
 "serde_with",
 "zeroize",
]

I also note that some of the docknetwork/crypto crate's Cargo.toml include a path to other crates in the repo while others do not.
For example: see proof_system compared to bbs_plus below.

The following output is editted and formatted for readability:

find . -type f -exec grep --color=auto -nH --null -e "version =" \{\} +

./compressed_sigma/Cargo.toml�17:dock_crypto_utils = { version = "0.9.0", default-features = false }

./test_utils/Cargo.toml�9:bbs_plus = { version = "0.11.0", default-features = false }
./test_utils/Cargo.toml�10:schnorr_pok = { version = "0.9.0", default-features = false }
./test_utils/Cargo.toml�11:vb_accumulator = { version = "0.12.0", default-features = false }
./test_utils/Cargo.toml�18:proof_system = { version = "0.18.0", default-features = false, path = "../proof_system" }

./saver/Cargo.toml�20:dock_crypto_utils = { version = "0.9.0", default-features = false }

./proof_system/Cargo.toml�21:bbs_plus = { version = "0.11.0", default-features = false }
./proof_system/Cargo.toml�22:schnorr_pok = { version = "0.9.0", default-features = false }
./proof_system/Cargo.toml�23:vb_accumulator = { version = "0.12.0", default-features = false }
./proof_system/Cargo.toml�24:dock_crypto_utils = { version = "0.9.0", default-features = false }
./proof_system/Cargo.toml�25:saver = { version = "0.9.0", default-features = false }

./delegatable_credentials/Cargo.toml�20:dock_crypto_utils = { version = "0.9.0", default-features = false }
./delegatable_credentials/Cargo.toml�23:schnorr_pok = { version = "0.9.0", default-features = false }

./schnorr_pok/Cargo.toml�21:dock_crypto_utils = { version = "0.9.0", default-features = false, path = "../utils" }

./vb_accumulator/Cargo.toml�25:schnorr_pok = { version = "0.9.0", default-features = false, path = "../schnorr_pok" }
./vb_accumulator/Cargo.toml�26:dock_crypto_utils = { version = "0.9.0", default-features = false, path = "../utils" }

./benches/Cargo.toml�9:bbs_plus = { version = "0.11.0", default-features = false, path = "../bbs_plus" }
./benches/Cargo.toml�10:schnorr_pok = { version = "0.9.0", default-features = false, path = "../schnorr_pok" }
./benches/Cargo.toml�11:vb_accumulator = { version = "0.12.0", default-features = false, path = "../vb_accumulator" }
./benches/Cargo.toml�12:test_utils = { version = "0.1.0", default-features = false, path = "../test_utils" }

./secret_sharing_and_dkg/Cargo.toml�21:dock_crypto_utils = { version = "0.9.0", default-features = false }
./secret_sharing_and_dkg/Cargo.toml�22:schnorr_pok = { version = "0.9.0", default-features = false }

./bbs_plus/Cargo.toml�21:schnorr_pok = { version = "0.9.0", default-features = false, path = "../schnorr_pok" }
./bbs_plus/Cargo.toml�22:dock_crypto_utils = { version = "0.9.0", default-features = false, path = "../utils" }

One last thing. `saver/Cargo.toml' seems to indicate the need for paths:

./saver/Cargo.toml�33:#proof_system = { path = "../proof_system" }
./saver/Cargo.toml�34:#bbs_plus = { path = "../bbs_plus" }

Bottom line: the rust compiler can't tell the difference between what is in the local registry and what is available via path.

I am assuming that is my problem, but maybe not.

Thank you,
H

> cargo --version
cargo 1.67.1 (8ecd4f20a 2023-01-10)
> rustc --version
rustc 1.67.1 (d5a82bbd2 2023-02-07)

Question: Witness (terminology and implementation)

Hi 👋 I am still admiring your work!

I am wondering about the terminology of the witness and its "implementation".

From the docs:

Witness - Private data that needs to be kept hidden from the verifier. This can be the messages/attributes that are not being disclosed, the signature itself, the accumulator member, accumulator witness. Every witness corresponds to some Statement.

So:

Is the witness the actual secret value, or is it some wrapper around it, e.g., a commitment (or rather, the value commited to and opening of said commitment)?

And, for two statements (e.g. for POKS and set membership), the witnesses are distinct objects in code, but "reference" the same value. This equality of the witnesses is what we prove with witnessEquality in the metaStatements.

This equality proof is done via Schnorr, as far as I understand, where we prove knowledge of the commited value (the witness?) and the opening for the commitment (also part of the witness then?) that is used in the particular other proofs (POKS, set membership, etc). What is part of the witness here?

I feel that the term witness is used quite heterogeneously on the Web - and, FWIW, Rannenberg, Camenisch and Sabouri don't even mention that term in their work on Attribute-based Credentials for Trust.
I'd appreciate if you could clarify your understanding of the term witness and how it relates to the composite proofs.

Cheers
Christoph

Benchmarks for BBS+/PS

Hi @lovesh , thank you for reviewing my previous PR.

1. Abstract

In this issue, let me report the benchmark result for BBS+ and PS signature.
After this, I'd like to discuss:

if the result makes sense or not (compared to math theory)
which algorithm is better (for each cases)
where we can improve the implementation
where we can improve the benchmark (to measure more other metrics)

2. Machine Spec (Local)

Macbook Pro 13-inch
M1 2020
16GB Memory
macOS Ventura 13.5.2
512GB Storage

3. Benchmark Steps

git clone [email protected]:docknetwork/crypto.git && cd crypto
cargo bench --bench=bbs_plus_signature
cargo bench --bench=bbs_plus_proof
cargo bench --bench=ps_signature
cargo bench --bench=ps_proof

4. Metrics

As the benchmark, I plotted these 4 metrics with changing the number of messages(attributes) for the statement.

GenSig Time
VerSig Time
GenProof Time
VerProof Time
(GenKey Time)
(SigSize)
(ProofSize)

5. Benchmark Results

I'll show 2 table and 4 graphs to compare the performance.
*the first row's label means num of messages(attributes)
*the unit is ms

$2~ $5 changes the number of revealed messages

Table 5-1: Metrics Result for BBS+

		2	4	8	15	20	30	40	60
BBS+ GenSig[ms]	$1	0.62183	0.64961	0.71722	0.827	0.90691	1.045	1.1586	1.3416
	$2	1.7734	1.8958	2.0983	2.4408	2.6355	2.9816	3.4678	3.9194
	ave.	1.197615	1.272705	1.40776	1.6339	1.771205	2.0133	2.3132	2.6305
BBS+ VerSig[ms]	$1	2.7016	2.6374	2.7036	2.8611	2.9737	3.0657	3.1599	3.3106
	$2	3.2652	3.4031	3.6543	3.8949	4.0533	4.436	4.9669	5.4332
	ave.	2.9834	3.02025	3.17895	3.378	3.5135	3.75085	4.0634	4.3719
BBS+ GenProof[ms]	$1	2.0099	2.1014	2.8049	2.2209	2.7935	2.9676	3.2108	3.5762
	$2	1.96	2.067	2.8871	2.5812	2.735	2.9154	3.2154	3.6223
	$3		2.0406	2.5583	2.5471	2.7057	2.8124	3.046	3.5096
	$4		2.0601	2.3759	2.4619	2.6178	2.6977	2.9467	3.2454
	$5				2.361	2.4378	2.4847	2.6728	2.806
	max.	2.0099	2.1014	2.8871	2.5812	2.7935	2.9676	3.2154	3.6223
BBS+ VerProof[ms]	$1	3.5296	3.6233	3.7149	3.7544	3.8783	3.9414	4.0455	4.27
	$2	3.5781	3.624	3.6392	3.7953	3.8829	3.9481	4.1603	4.3722
	$3		3.6087	3.6367	3.8269	3.8823	4.007	4.2378	4.4628
	$4		3.5764	3.685	3.843	3.8835	4.0056	4.2087	4.593
	$5			3.7057	3.8491	3.8423	3.9704	4.182	4.3449
	max.	3.5781	3.624	3.7149	3.8491	3.8835	4.007	4.2378	4.593

Table 5-2: Metrics Result for PS

		2	4	8	15	20	30	40	60
PS GenSig[ms]	$1	0.51308	0.53232	0.56112	0.5592	0.56739	0.55512	0.57305	0.56861
	$2	0.51673	0.54085	0.5582	0.56925	0.56855	0.5598	0.56941	0.56456
	ave.	0.514905	0.536585	0.55966	0.564225	0.56797	0.55746	0.57123	0.566585
PS VerSig[ms]	$1	7.7095	7.7969	8.3695	9.0656	9.3218	10.162	10.586	12.122
	$2	7.3306	7.9236	7.9625	8.6113	9.0243	9.8657	10.314	11.564
	ave.	7.52005	7.86025	8.166	8.83845	9.17305	10.01385	10.45	11.843
PS GenProof[ms]	$1	5.9315	6.1475	6.6131	7.9361	8.0812	9.3107	10.846	12.102
	$2	5.7042	5.8307	6.5255	7.3908	8.0245	9.1593	10.259	11.957
	$3		5.7572	6.4059	7.225	7.7813	8.7491	9.765	11.255
	$4		5.419	6.2343	6.9428	7.3541	8.1313	8.5433	9.9965
	$5			5.6496	6.0622	6.2131	6.6925	6.622	7.3308
	max.	5.9315	6.1475	6.6131	7.9361	8.0812	9.3107	10.846	12.102
PS VerProof[ms]	$1	7.2431	7.4569	7.8751	8.3666	9.3701	9.656	10.866	12.167
	$2	7.327	7.5439	8.0123	8.4641	9.2729	9.6978	11.127	12.12
	$3	7.4569	7.5204	7.9836	8.5934	8.9852	9.8368	11.128	12.588
	$4		7.6356	8.0263	8.6903	9.0409	9.9549	11	12.433
	$5			7.9485	9.2128	9.0994	10.027	10.877	12.275
	max.	7.4569	7.6356	8.0263	9.2128	9.3701	10.027	11.128	12.588

And these graphs reflects the table.

Graph 5-1: Performance for GenSig/VerSig

Graph 5-2: Performance for GenProof/VerProof

6. Discussion

The result tells them:

PS is better for GenSig, but BBS+ is better for VerSig, GenProof and VerProof.
GenSig time takes less than 1ms and looks almost constant (on PS).
VerSig time on PS takes almost twice than on BBS+.
GenProof time is positive for number of blinding messages (on both BBS+/PS).
VerProof time is constant for any number of blinding messages (on both BBS+/PS).

I'll also provide a theoretical computation cost for each algorithm.
*L: message length, d: open length, d’: hidden length, R: generate random, E: exponation, P: pairing
*(XX) means time for message which has 30 attributes

Table 6-1. Computation Cost Theory for BBS+/PS

	GenKey	GenSig	VerSig	GenProof	VerProof
BBS+	(L+1)RG1+1EG1	2RZp+(L+2)EG1(2.01ms)	(L+1)EG1 + 1EG2+2P(3.75ms)	2RZp+(d’+8)EG1+1EG2(2.96ms)	(L+3)EG1+2P(4.01ms)
PS	(L+1)RG1+(L+1)EG2	1RG1+1EG1(0.557ms)	LEG2+2P(10.01ms)	(d’+3)RZp+3EG1+(2d’+2)EG2(9.31ms)	(L+1)EG2+2P(10.03ms)

In my opinion:

The result matches the theory.
- PS signature looks less computation than BBS+ one, but PS mainly executes the multiplications on G2, which takes more time than G1.
PS signature needs much less computation on GenSig, but needs much more computation on GenKey instead.
BBS+ seems better because we mainly have less computation power in VerSig/GenProof/VerProof, which processes on the holder/verifier's mobile devices.

C interface to "crypto"

Could a C interface be provide (like is done for Hyperledger Ursa)?
That would make it possible to use the crypto library from other languages.

Question: Composite Proofs

Hi! 👋
Thank you for your great work! (Especially all the comments in the code!)

I was looking at how the composite proof system works, especially focusing on BBS+ with LegoGroth16.
From [1] I gather that everything is kinda glued together via Schnorr. Is there a formal description on how this works? I am really curious about this...

I recently looked into combining BBS+ and Bulletproofs (with Hyperledger Ursa) but got stuck at exactly that point...
Could not think of how to prove the usage of the witness from the BBS+ in the range proof (...still learning...).
As a side question: Would there be anything blocking the combination of the two from the get-go or could one "plug in" Bulletproofs (to avoid the trusted setup) using the same approach to composite proofs (i.e. adding to this repo)?