Single signature without merkle path

[curiecrypt]

Single Signatures without Merkle Path

Individual Signature - StmSig

An individual signature StmSig does not contain the Merkle path; instead, it holds the signer's merkle tree index.

• Path removed.
• The list mt_index_path was added; it holds the indexes of the path values for the signer.
• The index of the signer signer_index was added.

Sign Function - StmSigner::sign

Signer does not call get_path, instead it calls get_mt_index_path.

• MerkleTree::get_mt_index_path: This function returns a vector that holds the Merkle tree indexes of the nodes that belongs to the path for the current signer.

Verify Function - StmSig::verify

The verification of a single signature is done without checking the Merkle tree path.

Aggregation - StmClerk::aggregate

The aggregator gets the path (the new path consists of values and indices) for each signature. Single signatures now contain the index of the signer so that the aggregator can get the path with the knowledge of the Merkle tree. The aggregator collects the unique Merkle tree nodes as a proof list.

• Proof List:

  • Proof list is a struct in merkle_tree.rs including values: Vec<Vec<u8>>, indexes: Vec<usize>, and hasher: PhantomData<D>.
  • It implements create, match_val_ind, to_bytes, and from_bytes.

• A new parameter of type ProofList is added to the struct StmAggrSig.

• Aggregator calls generate_proof_list for each signer. This function is similar to get_path, except it also holds the index of the value.

• Only unique path values are collected in proof_list.

• The aggregated signature is generated after getting the proof_list and unique_sigs.

Verify Aggregate - StmAggrSig::verify

• The verifier reconstructs the Merkle path for each signer.
• It matches the mt_index_path of StmSig with proof_list of StmAggrSig and obtains the path.

ToDo:

• [x] The signer should not include index path when generating the signature; the aggregator should do that.
• [x] Proof list of the aggregator should be updated as in ATMS.

Update:

Due to the breaking changes on the main branch, a load of conflicts occurred between the main and signature-without-path, and most of the CI checks failed. So, we decided to rebase the main and handle batch-proof implementations without affecting the rest of the project. The following describes the changes:

• mithril-core is restored from main, so that the batch compatibility can be tested only in core.
• Batch compatibility is implemented in stm_batch_compat.rs.
• To handle the required changes, merkle_tree.rs is updated.
• Tests and benches are created for batch compatibility.

- stm_batch_compat.rs

This module inherits from stm and provides the batch compatibility. It overwrites the structs and functions of stm only where required by batch-compat.

• Individual signature:

  • The struct StmSigBatchCompat is modified from StmSig where the path is removed, and the signer index is added.
  • StmSignerBatchCompat::sign() generates a signature without computing the merkle path.
  • StmSigBatchCompat::verify() does not check the merkle path.

• Aggregation:

  • The batch proof is added to struct StmAggrSigBatchCompat.
  • The type StmClerkBatchCompact is derived from StmClerk.
  • StmClerkBatchCompact::aggregate_batch_compat() aggregates the signature and generates a batch proof for StmAggrSigBatchCompat.

• Verification:

  • Aggregated signature is verified by checking the batch_proof in StmAggrSigBatchCompat::verify().

- merkle_tree.rs

• The struct BatchPath includes the indices and the values of the nodes in the path.
• In order to get the batch path, the number of leaves in the merkle tree is required. So, a new commitment structure MerkleTreeCommitmentBatchCompat that includes nr_leaves besides the root.
• Batch path is computed in MerkleTree::get_batched_path() and checked in MerkleTreeCommitmentBatchCompat::check_batched() with the method used in ATMS.

ToDo:

• [x] Tests for MerkleTreeCommitmentBatchCompat and BatchPath.
• [x] Handle batch features in stm.rs
• [x] Documentation of batch compat in stm.rs
• [ ] Simplify check_batched in merkle_tree.rs
  • [x] Update doc for merkle tree batch compact.
• [x] Revisit integration.
• [x] Revisit bench tests.

Open questions:

• [ ] Is there a way to reduce the lines of code in stm_batch_compat.rs?
• [ ] How can we generate batch path without including nr_leaves in MerkleTreeCommitment? The change in the commitment structure seems to be the reason that we have conflicts with the rest of the project.

This closes #161

[github-actions[bot]]

Unit Test Results

    3 files    28 suites   2m 42s :stopwatch: 326 tests 326 :heavy_check_mark: 0 :zzz: 0 :x: 379 runs  379 :heavy_check_mark: 0 :zzz: 0 :x:

Results for commit a3cad9b7.

:recycle: This comment has been updated with latest results.