复合证明系统

此包的目的是通过执行多个子协议，允许创建和组合零知识证明。

思路是将每个需要证明的关系表示为 Statement，将 Statement 之间的任何关系表示为 MetaStatement。这两种类型都包含公共（双方都知道）信息，并包含在 ProofSpec 中，其目的是明确定义需要证明的内容。一些 Statement 是针对证明者或验证者的，因为这些协议要求证明者和验证者使用不同的公共参数。例如，基于 Groth16 的 SNARK 协议，其中证明者需要证明密钥，验证者需要验证密钥。证明者和验证者可以知道证明密钥和验证密钥，但不必这么做。因此，对于此类协议，证明者和验证者有不同的 Statement，例如 SaverProver 和 SaverVerifier 分别是针对证明者和验证者的陈述，执行 SAVER 协议。

可能需要为多个 Statement 使用相同的公共参数，例如证明同一签署者拥有多个 BBS+ 的知识，或为同一解密者验证多个消息的加密。将相同的参数传递给每个 Statement 并不高效，尤其是当使用此代码的 WASM 绑定时，因为这些值将被序列化和反序列化。为了避免这种情况，调用者可以将所有此类公共参数作为 SetupParams 放入数组中，并在创建 Statement 时通过它们的索引来引用。然后，这个 SetupParams 数组将包含在 ProofSpec 中，并在证明创建和验证期间分别由验证者和证明者使用。

一个常见的需求是证明某些 Witness 在某些 Statement 中的相等性。这通过使用 EqualWitnesses 元陈述来完成。对于需要证明相等的每个 Witness 集合（来自相同的或不同的 Statement），将创建一个 EqualWitnesses，它是一组见证引用 WitnessRef。每个 WitnessRef 包含了该 Statement 中的 Statement 索引和 Witness 索引，从而唯一地识别了 Statement 之间的任何 Witness。EqualWitnesses 元陈述还用于在零知识中证明关于签名消息的谓词，在执行对签名消息的范围证明时（使用 BBS+），EqualWitnesses 将引用 Statement::PoKBBSSignatureG1 陈述和 Statement::BoundCheckLegoGroth16 陈述中的 Witness。以下是 EqualWitnesses 的一些示例。

 ┌────────────────────────────┐    ┌──────────────────────────────┐     ┌────────────────────────────┐
 │ 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

 ┌────────────────────────────┐    ┌──────────────────────────────┐     ┌────────────────────────────┐
 │ 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

在创建ProofSpec之后，证明者针对每个Statement使用一个Witness并创建相应的StatementProof。所有的StatementProof都组成了一个Proof。验证者也会创建其ProofSpec并使用它来验证给定的证明。目前假定每个StatementProof对应一个Statement，每个Statement对应一个Witness，并且StatementProof在Proof中的顺序与Statement在ProofSpec中的顺序相同。

Statement、Witness和StatementProof是枚举类型，其变体会是来自不同协议的实体。这些协议中的每一个都是枚举SubProtocol的变体。SubProtocol可以内部调用其他SubProtocol，例如SaverProtocol调用了多个SchnorrProtocol。

目前支持

• BBS或BBS+签名和签名消息的知识证明
• 多个BBS或BBS+签名以及某些消息相等性的知识证明
• 累积成员和非成员知识证明
• Pedersen承诺开头的知识证明
• BBS或BBS+签名及其满足给定界限的某些消息的知识证明（范围证明）
• BBS或BBS+签名中的消息的可验证加密
• BBS或BBS+签名及其满足给定R1CS的知识证明。R1CS由Circom生成，使用的证明系统是LegoGroth16。LegoGroth16与Groth16类似，但除了零知识证明外，它还为见证（在我们的情况下是签名消息）提供了Pedersen承诺。这种承诺使我们能够使用Schnorr知识证明协议来证明证明协议中的见证与签名消息相同。

以下测试示例请参考

• 测试pok_of_3_bbs_plus_sig_and_message_equality证明了3个BBS+签名以及某些消息之间相等性的知识，而不泄露它们。
• 测试 pok_of_bbs_plus_sig_and_accumulator 证明了关于 BBS+ 签名的知识，同时也证明了某些消息分别存在于两个累加器中。
• 测试 pok_of_knowledge_in_pedersen_commitment_and_bbs_plus_sig 证明了关于 BBS+ 签名的知识以及 Pedersen 承诺的开启。
• 测试 requesting_partially_blind_bbs_plus_sig 展示了如何通过证明 Pedersen 承诺的开启来请求盲 BBS+ 签名。
• 测试 verifier_local_linkability 展示了验证者如何（在提供者同意的情况下）将提供者的多个证明联系起来，并为提供者分配一个唯一的标识符，而不需要从 BBS+ 签名中学习任何消息。此外，这个标识符不能在不同验证者之间链接（这是由提供者有意为之的）。
• 测试 pok_of_bbs_plus_sig_and_bounded_message 展示了如何证明关于 BBS+ 签名的知识，以及特定的消息满足某些上限和下限，即 min <= 签名消息 <= max。这是一个范围证明。
• 测试 pok_of_bbs_plus_sig_and_verifiable_encryption 展示了如何对使用 BBS+ 签名的消息进行可验证加密，使得验证者无法解密它，但仍能确保它对指定的解密者是正确加密的。
• 测试 pok_of_bbs_plus_sig_with_reusing_setup_params 展示了使用 SetupParams 来证明多个 BBS+ 签名的知识。在这里，相同的签名者在多个签名中使用，因此它们的公共参数可以作为一个枚举 SetupParams 的变体。类似地，测试 pok_of_knowledge_in_pedersen_commitment_and_equality_with_commitment_key_reuse 展示了在多个承诺中重复使用相同的承诺密钥时使用 SetupParams，而测试 pok_of_bbs_plus_sig_and_verifiable_encryption_of_many_messages 展示了在为同一解密者进行可验证加密时使用 SetupParams。
• 对于 R1CS/Circom，请参阅各种测试，例如在用 BBS+ 签名的消息上使用小于、不等于比较运算符，证明 MiMC 哈希的前像是用 BBS+ 签名的消息，某些签名消息（来自同一或不同的签名）的总和受给定值的限制等。请参阅这里。Circom 编译器的输出和电路请参阅这里。电路是为 BLS12-381 曲线编译和测试的。

注意：这个设计主要受我在 Hyperledger Ursa 的工作的启发。

注意：设计是试探性的，随着更多协议的集成，可能会发生变化。