1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

#![cfg_attr(not(feature = "std"), no_std)]

//! The goal of this crate is to allow creating and combining zero knowledge proofs by executing several
//! protocols as sub-protocols.
//!
//! The idea is to represent each relation to be proved as a [`Statement`], and any relations between
//! [`Statement`]s as a [`MetaStatement`]. Both of these types contain public (known to both prover
//! and verifier) information and are contained in a [`ProofSpec`] whose goal is to unambiguously
//! define what needs to be proven. Some [`Statement`]s are specific to either the prover or the verifier
//! as those protocols require prover and verifier to use different public parameters. An example is Groth16
//! based SNARK protocols where the prover needs to have a proving key and the verifier needs to
//! have a verifying key. Both the prover and verifier can know both the proving and verifying key but
//! they don't need to. Thus for such protocols, there are different [`Statement`]s for prover and verifier,
//! like [`SaverProver`] and [`SaverVerifier`] are statements for prover and verifier respectively,
//! executing SAVER protocol.
//!
//! Several [`Statement`]s might need same public parameters like proving knowledge of several BBS+
//! from the same signer, or verifiable encryption of several messages for the same decryptor. Its not
//! very efficient to pass the same parameters to each [`Statement`] especially when using this code's WASM
//! bindings as the same values will be serialized and deserialized every time. To avoid this, caller can
//! put all such public parameters as [`SetupParams`] in an array and then reference those by their index
//! while creating an [`Statement`]. This array of [`SetupParams`] is then included in the [`ProofSpec`]
//! and used by the prover and verifier during proof creation and verification respectively.
//!
//! A common requirement is to prove equality of certain [`Witness`]s of certain [`Statement`]s. This
//! is done by using the [`EqualWitnesses`] meta-statement. For each set of [`Witness`]s (from the same or different [`Statement`]s)
//! that need to proven equal, a [`EqualWitnesses`] is created which is a set of witness references [`WitnessRef`].
//! Each [`WitnessRef`] contains the [`Statement`] index and the [`Witness`] index in that [`Statement`] and
//! thus uniquely identifies any [`Witness`] across [`Statement`]s. The [`EqualWitnesses`] meta-statement is also
//! used to prove predicates over signed messages in zero knowledge, when doing a range-proof over a
//! signed message (using BBS+), the [`EqualWitnesses`] will refer [`Witness`]s from `Statement::PoKBBSSignatureG1`
//! statement and `Statement::BoundCheckLegoGroth16` statement. Following are some illustrations of [`EqualWitnesses`]
//!
//! ```text
//!  ┌────────────────────────────┐    ┌──────────────────────────────┐     ┌────────────────────────────┐
//!  │ PokBBSSignatureG1          │    │ PokBBSSignatureG1            │     │ PokBBSSignatureG1          │
//!  │ Statement 1                │    │ Statement 2                  │     │ Statement 3                │
//!  ├────────────────────────────┤    ├──────────────────────────────┤     ├────────────────────────────┤
//!  │ A1, A2, A3, A4, A5         │    │ B1, B2, B3, B4               │     │ C1, C2, C3, C4, C5, C6     │
//!  └─────────▲──────────────────┘    └─────▲────────▲───────────────┘     └─▲────────────────▲─────────┘
//!            │                             │        │                       │                │
//!            │                             │        │                       │                │
//!            │                             │        │                       │                │
//!            │                             │        │                       │                │
//!            │            ┌-───────────────┴────────┴───┬───────────────────┼──────┬─────────┴──────────────────┐
//!            └────────────┼(0, 2), (1, 1), (2, 0)       ├───────────────────┘      │ (2, 3), (3, 4)             │
//!                         ├-────────────────────────────┤                          ├────────────────────────────┤
//!                         │       EqualWitnesses        │                          │  EqualWitnesses            │
//!                         │       MetaStatement 1       │                          │  MetaStatement 2           │
//!                         │ A3, B2 and C1 are equal     │                          │  B4 and C5 are equal       │
//!                         └─────────────────────────────┘                          └────────────────────────────┘
//! ```
//!
//!        For proving certain messages from 3 BBS+ signatures are equal. Here there 2 sets of equalities,
//!        1. message A3 from 1st signature, B2 from 2nd signature and C1 from 3rd signature
//!        2. message B4 from 2nd signature and C5 from 3rd signature
//!
//!        Thus 3 statements, one for each signature, and 2 meta statements, one for each equality
//!---------------------------------------------------------------------------------------------------------------------------------------------------
//! ```text
//!  ┌────────────────────────────┐    ┌──────────────────────────────┐     ┌────────────────────────────┐
//!  │ PokBBSSignatureG1          │    │ BoundCheckLegoGroth16        │     │ SAVER                      │
//!  │ Statement 1                │    │ Statement 2                  │     │ Statement 3                │
//!  ├────────────────────────────┤    ├──────────────────────────────┤     ├────────────────────────────┤
//!  │ A1, A2, A3, A4, A5         │    │     B1                       │     │             C1             │
//!  └─────────▲───────▲──────────┘    └─────▲────────-───────────────┘     └───────────────▲────-───────┘
//!            │       |─────────────────|   │                                              │
//!            │                         |   │                                              │
//!            │                         |──-│-────────────────────|                        │
//!            │                             │                     |                        |───|
//!            │            ┌-───────────────┴────────-───┬────────|───────────────────────────-|─────────────────┐
//!            └────────────┼(0, 2),  (1, 0)              |        |─────────────────│── (0, 4), (2, 1)           │
//!                         ├-────────────────────────────┤                          ├────────────────────────────┤
//!                         │       EqualWitnesses        │                          │  EqualWitnesses            │
//!                         │       MetaStatement 1       │                          │  MetaStatement 2           │
//!                         │ A3 and  B1 are equal        │                          │  A5 and C1 are equal       │
//!                         └─────────────────────────────┘                          └────────────────────────────┘
//! ```
//!        For proving certain messages from a BBS+ signature satisfy 2 predicates,
//!         1) message A3 satisfies bounds specified in statement 2
//!         2) message A5 has been verifiably encrypted as per statement 3.
//!
//!       Thus 3 statements, one for a signature, and one each for a predicate. 2 meta statements, one each
//!       for proving equality of the message of the signature and the witness of the predicate
//! --------------------------------------------------------------------------------------------------------------------------------
//!
//! After creating the [`ProofSpec`], the prover uses a [`Witness`] per [`Statement`] and creates a
//! corresponding [`StatementProof`]. All [`StatementProof`]s are grouped together in a [`Proof`].
//! The verifier also creates its [`ProofSpec`] and uses it to verify the given proof. Currently it is
//! assumed that there is one [`StatementProof`] per [`Statement`] and one [`Witness`] per [`Statement`]
//! and [`StatementProof`]s appear in the same order in [`Proof`] as [`Statement`]s do in [`ProofSpec`].
//!
//! [`Statement`], [`Witness`] and [`StatementProof`] are enums whose variants will be entities from different
//! protocols. Each of these protocols are variants of the enum [`SubProtocol`]. [`SubProtocol`]s can internally
//! call other [`SubProtocol`]s, eg [`SaverProtocol`] invokes several [`SchnorrProtocol`]s
//!
//! Currently supports
//! - proof of knowledge of a BBS or BBS+ or PS signature and signed messages
//! - proof of knowledge of multiple BBS or BBS+ or PS signature and equality of certain messages
//! - proof of knowledge of multiple BBS or BBS+ or PS signature and inequality of certain messages with public values
//! - proof of knowledge of accumulator membership and non-membership
//! - proof of knowledge of Pedersen commitment opening.
//! - proof of knowledge of BBS or BBS+ or PS signature(s) and that certain message(s) satisfy given bounds (range proof)
//! - verifiable encryption of messages in a BBS or BBS+ or PS signature
//! - proof of knowledge of BBS or BBS+ signature(s) and that certain message(s) satisfy given R1CS. The R1CS is generated
//!   from [Circom](https://github.com/iden3/circom) and the proof system used is [LegoGroth16](https://github.com/lovesh/legogro16).
//!   LegoGroth16 is similar to Groth16 but in addition to the zero knowledge proof, it provides a Pedersen
//!   commitment to the witness (signed messages in our case). This commitment allows us to prove that the witness in
//!   the proof protocol are the same as the signed messages using the Schnorr proof of knowledge protocol.
//!
//! See following tests for examples:
//!
//! - test `pok_of_3_bbs_plus_sig_and_message_equality` proves knowledge of 3 BBS+ signatures and also that certain
//!   messages are equal among them without revealing them.
//! - test `pok_of_bbs_plus_sig_and_accumulator` proves knowledge of a BBS+ signature and also that certain messages
//!   are present and absent in the 2 accumulators respectively.
//! - test `pok_of_knowledge_in_pedersen_commitment_and_bbs_plus_sig` proves knowledge of a BBS+ signature and opening
//!   of a Pedersen commitment.
//! - test `requesting_partially_blind_bbs_plus_sig` shows how to request a blind BBS+ signature by proving opening of
//!   a Pedersen commitment.
//! - test `verifier_local_linkability` shows how a verifier can link separate proofs from a prover (with prover's
//!   permission) and assign a unique identifier to the prover without learning any message from the BBS+ signature.
//!   Also this identifier cannot be linked across different verifiers (intentional by the prover).
//! - test `pok_of_bbs_plus_sig_and_bounded_message` shows proving knowledge of a BBS+ signature and that a specific
//!   message satisfies some upper and lower bounds i.e. min <= signed message <= max. This is a range proof.
//! - test `pok_of_bbs_plus_sig_and_verifiable_encryption` shows how to verifiably encrypt a message signed with BBS+ such
//!   that the verifier cannot decrypt it but still ensure that it is encrypted correctly for the specified decryptor.
//! - test `pok_of_bbs_plus_sig_with_reusing_setup_params` shows proving knowledge of several BBS+ signatures
//!   using [`SetupParams`]s. Here the same signers are used in multiple signatures thus their public params
//!   can be put as a variant of enum [`SetupParams`]. Similarly test
//!   `pok_of_knowledge_in_pedersen_commitment_and_equality_with_commitment_key_reuse` shows use of [`SetupParams`]
//!   when the same commitment key is reused in several commitments and test `pok_of_bbs_plus_sig_and_verifiable_encryption_of_many_messages`
//!   shows use of [`SetupParams`] when several messages are used in verifiable encryption for the same decryptor.
//! - For R1CS/Circom, see various tests like using less than, not-equals comparison operators on messages signed with BBS+, proving
//!   that the preimage of an MiMC hash is the message signed with BBS+, sum of certain signed messages (from same or different signatures)
//!   is bounded by a given value, etc [here](tests/r1cs). The Circom compiler output and circuits are [here](tests/r1cs/circom).
//!   The circuits were compiled and tested for BLS12-381 curve.
//!
//! *Note*: This design is largely inspired from my work at Hyperledger Ursa.
//!
//! *Note*: The design is tentative and will likely change as more protocols are integrated.
//!
//! *TODO*: Each of the above protocol uses a Schnorr protocol and the response for that protocol's witness is compared for
//! equality with the response for Schnorr protocol used in BBS+/PS signatures (see `check_resp_for_equalities`). This cost (verify time and proof size)
//! can be avoided by making protocols except the ones proving knowledge of BBS+/PS signatures not generate Schnorr responses.
//!
//! [`Statement`]: crate::statement::Statement
//! [`MetaStatement`]: crate::meta_statement::MetaStatement
//! [`EqualWitnesses`]: crate::meta_statement::EqualWitnesses
//! [`WitnessRef`]: crate::meta_statement::WitnessRef
//! [`SaverProver`]: crate::statement::saver::SaverProver
//! [`SaverVerifier`]: crate::statement::saver::SaverVerifier
//! [`SetupParams`]: crate::setup_params::SetupParams
//! [`ProofSpec`]: crate::proof_spec::ProofSpec
//! [`Witness`]: crate::witness::Witness
//! [`StatementProof`]: crate::statement_proof::StatementProof
//! [`Proof`]: proof::Proof
//! [`SubProtocol`]: crate::sub_protocols::SubProtocol
//! [`SaverProtocol`]: crate::sub_protocols::saver::SaverProtocol
//! [`SchnorrProtocol`]: crate::sub_protocols::schnorr::SchnorrProtocol

extern crate core;

#[macro_use]
pub mod setup_params;
#[macro_use]
mod derived_params;
mod constants;
pub mod error;
mod macros;
pub mod meta_statement;
pub mod proof;
pub mod proof_spec;
pub mod prover;
pub mod statement;
pub mod statement_proof;
pub mod sub_protocols;
pub mod verifier;
pub mod witness;

pub mod prelude {
    pub use crate::{
        error::ProofSystemError, meta_statement::*, proof::*, proof_spec::*, prover::*,
        setup_params::*, statement::*, statement_proof::*,
        sub_protocols::bound_check_legogroth16::generate_snark_srs_bound_check, verifier::*,
        witness::*,
    };
}