Repository: input-output-hk/mithril
Pull request #484 (2022-09-06 16:50:48)

Single signature without merkle path
Single Signatures without Merkle Path
===

`mithril-core` now provides single signatures that do not contain Merkle tree path. The membership of the signers who issued single signatures is checked by the batch proof that is created in aggregation phase. This update offers a remarkable improvement considering the size of single signatures, aggregate signature, and computation time.
The related changes are as follows:

### `merkle_tree.rs`
- Struct `BatchPath` is added. This struct holds the path of hashes for a batch of indices that contains the hashes and the corresponding merkle tree indices of given batch.
- A new struct `MerkleTreeCommitmentBatchCompat` is added. This is the merkle tree commitment that contains the number of leaves in the merkle tree in addition to the root. 
- `MerkleTree::get_batched_path()` creates the batch path for given list of indices.
- `MerkleTreeCommitmentBatchCompat::check()` checks whether given given list of merkle tree leaves verifies against the given `BatchPath`.

### `stm.rs`
- `Path` removed from `StmSig` and merkle tree index of the signer is included in the single signature.
- `StmSigner::sign()` does not compute the merkle tree path of the signer.
- `StmSig::verify()` does not check the merkle tree path.
- `BatchPath` is included in `StmAggrSig` struct.
- `StmClerk::aggregate()` computes the `batch_proof` by using the signers' merkle tree indexes contained in `StmSig`.
- Since the merkle tree commitment has changed to include the number of leaves in the tree, `StmAggrVerificationKey` now includes `MerkleTreeCommitmentBatchCompat`.

## Performance

We have run the benchmarks on an Apple M1 Pro machine with 16 GB of RAM, on macOS 12.6.


```shell
+----------------------+
| Size of benchmarks   |
+----------------------+
| Results obtained by using the parameters suggested in paper.
+----------------------+
+----------------------+
| Aggregate signatures |
+----------------------+
+----------------------+
| Hash: Blake2b 512    |
+----------------------+
k = 445 | m = 2728 | nr parties = 3000; 118760 bytes (old version = 356632 bytes)
+----------------------+
| Hash: Blake2b 256    |
+----------------------+
k = 445 | m = 2728 | nr parties = 3000; 99384 bytes (old version = 222536 bytes)
+----------------------+
+----------------------+
| Aggregate signatures |
+----------------------+
| Hash: Blake2b 512    |
+----------------------+
k = 554 | m = 3597 | nr parties = 3000; 133936 bytes (old version = 419808 bytes)
+----------------------+
| Hash: Blake2b 256    |
+----------------------+
k = 554 | m = 3597 | nr parties = 3000; 113728 bytes (old version = 261488 bytes)

```

**Note that single signatures in batch compat version does not depend on any variable and size of an individual signature is `176` bytes.**

```shell
STM/Blake2b/Key registration/k: 25, m: 150, nr_parties: 300
                        time:   [409.70 ms 426.81 ms 446.30 ms]
STM/Blake2b/Play all lotteries/k: 25, m: 150, nr_parties: 300
                        time:   [696.58 µs 697.62 µs 698.75 µs]
STM/Blake2b/Aggregation/k: 25, m: 150, nr_parties: 300
                        time:   [18.765 ms 18.775 ms 18.785 ms]
STM/Blake2b/Verification/k: 25, m: 150, nr_parties: 300
                        time:   [2.1577 ms 2.1715 ms 2.1915 ms]

STM/Blake2b/Key registration/k: 250, m: 1523, nr_parties: 2000
                        time:   [2.5807 s 2.5880 s 2.5961 s]
STM/Blake2b/Play all lotteries/k: 250, m: 1523, nr_parties: 2000
                        time:   [5.9318 ms 5.9447 ms 5.9582 ms]
STM/Blake2b/Aggregation/k: 250, m: 1523, nr_parties: 2000
                        time:   [190.81 ms 191.15 ms 191.54 ms]
STM/Blake2b/Verification/k: 250, m: 1523, nr_parties: 2000
                        time:   [13.944 ms 14.010 ms 14.077 ms]


```


github-actions[bot]: ## Unit Test Results
    6 files   -   1    19 suites   - 3   10s [:stopwatch:](https://github.com/EnricoMi/publish-unit-test-result-action/blob/v1.20/README.md#the-symbols "duration of all tests") - 1m 55s
265 tests  - 29  265 [:heavy_check_mark:](https://github.com/EnricoMi/publish-unit-test-result-action/blob/v1.20/README.md#the-symbols "passed tests")  - 29  0 [:zzz:](https://github.com/EnricoMi/publish-unit-test-result-action/blob/v1.20/README.md#the-symbols "skipped / disabled tests") ±0  0 [:x:](https://github.com/EnricoMi/publish-unit-test-result-action/blob/v1.20/README.md#the-symbols "failed tests") ±0 
266 runs   - 29  266 [:heavy_check_mark:](https://github.com/EnricoMi/publish-unit-test-result-action/blob/v1.20/README.md#the-symbols "passed tests")  - 29  0 [:zzz:](https://github.com/EnricoMi/publish-unit-test-result-action/blob/v1.20/README.md#the-symbols "skipped / disabled tests") ±0  0 [:x:](https://github.com/EnricoMi/publish-unit-test-result-action/blob/v1.20/README.md#the-symbols "failed tests") ±0 

Results for commit 5ac7fc9a. ± Comparison against base commit 88c21dfc.

<details>
  <summary>This pull request <b>removes</b> 29 tests.</summary>

```
dense_mapping::tests ‑ test_precision_approximation
key_reg::tests ‑ test_keyreg
merkle_tree::tests ‑ test_bytes_path
merkle_tree::tests ‑ test_bytes_tree
merkle_tree::tests ‑ test_bytes_tree_commitment
merkle_tree::tests ‑ test_create_invalid_proof
merkle_tree::tests ‑ test_create_proof
multi_sig::tests ‑ serialize_deserialize_pk
multi_sig::tests ‑ serialize_deserialize_sk
multi_sig::tests ‑ test_aggregate_sig
…
```
</details>

[test-results]:data:application/gzip;base64,H4sIADJ7F2MC/13MSw7CIBSF4a00jB2UFi7iZhqeCbEthseoce9SrFIdfufm/huybjYR3Tq4dChmlyowL9I5iOT8ursvLqe0HwegH00xK/U/3d2jTN+PyQo3/wwmBB+OJeT13YQDLdmWVqw+BavPPeWXxaUCRIViVnGhmdSEgMQMpLWcAue0v+oRazIaSQb0fAEI8glABQEAAA==


Patch:
diff --git a/clippy b/clippy
new file mode 100644
index 000000000..e69de29bb
diff --git a/demo/protocol-demo/src/demonstrator.rs b/demo/protocol-demo/src/demonstrator.rs
index 88211e704..053d282ca 100644
--- a/demo/protocol-demo/src/demonstrator.rs
+++ b/demo/protocol-demo/src/demonstrator.rs
@@ -1,6 +1,5 @@
 use hex::ToHex;
-use rand_chacha::ChaCha20Rng;
-use rand_core::{RngCore, SeedableRng};
+use rand_core::{CryptoRng, RngCore};
 use serde::{Deserialize, Serialize};
 use std::collections::HashMap;
 use std::env;
@@ -42,7 +41,7 @@ struct MultiSignatureArtifact {
 }
 
 /// Party represents a signing protocol participant
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct Party {
     /// Party's identifier
     party_id: ProtocolPartyId,
@@ -50,6 +49,8 @@ pub struct Party {
     stake: ProtocolStake,
     /// Protocol parameters
     params: Option<ProtocolParameters>,
+    /// Protocol initializer
+    initializer: Option<ProtocolInitializerNotCertified>,
     /// Protocol signer
     signer: Option<ProtocolSigner>,
     /// Protocol clerk
@@ -66,6 +67,7 @@ impl Party {
             party_id: format!("{}", party_id) as ProtocolPartyId,
             stake: stake as ProtocolStake,
             params: None,
+            initializer: None,
             signer: None,
             clerk: None,
             msigs: HashMap::new(),
@@ -105,10 +107,13 @@ impl Party {
         }
         let closed_reg = key_reg.close();
 
-        let seed = [0u8; 32];
-        let mut rng = ChaCha20Rng::from_seed(seed);
-        let p = ProtocolInitializerNotCertified::setup(self.params.unwrap(), self.stake, &mut rng);
-        self.signer = Some(p.new_signer(closed_reg).unwrap());
+        let signer = self
+            .initializer
+            .clone()
+            .unwrap()
+            .new_signer(closed_reg)
+            .unwrap();
+        self.signer = Some(signer);
         self.clerk = Some(ProtocolClerk::from_signer(self.signer.as_ref().unwrap()));
     }
 
@@ -296,10 +301,8 @@ pub struct Demonstrator {
 
 impl Demonstrator {
     /// Demonstrator factory
-    pub fn new(config: &crate::Config) -> Self {
+    pub fn new<R: RngCore + CryptoRng>(config: &crate::Config, rng: &mut R) -> Self {
         // Generate parties
-        let seed = [0u8; 32];
-        let mut rng = ChaCha20Rng::from_seed(seed);
         let parties = (0..config.nparties)
             .into_iter()
             .map(|party_id| Party::new(party_id, 1 + rng.next_u64() % 999))
@@ -328,7 +331,7 @@ pub trait ProtocolDemonstrator {
     fn establish(&mut self);
 
     /// Initialization phase of the protocol
-    fn initialize(&mut self);
+    fn initialize<R: RngCore + CryptoRng>(&mut self, rng: &mut R);
 
     /// Issue certificates
     fn issue_certificates(&mut self);
@@ -349,7 +352,7 @@ impl ProtocolDemonstrator for Demonstrator {
     }
 
     /// Initialization phase of the protocol
-    fn initialize(&mut self) {
+    fn initialize<R: RngCore + CryptoRng>(&mut self, rng: &mut R) {
         // Retrieve protocol parameters
         let mut verifier = Verifier::new();
         verifier.update_params(&self.params.unwrap());
@@ -358,25 +361,17 @@ impl ProtocolDemonstrator for Demonstrator {
         }
 
         // Register keys
-        let seed = [0u8; 32];
-        let mut rng = ChaCha20Rng::from_seed(seed);
-        let players = self
-            .parties
-            .iter()
-            .map(|party| (party.party_id.to_owned(), party.stake))
-            .collect::<Vec<_>>();
         let mut players_artifacts = Vec::new();
-        for (party_id, stake) in players {
+        for party in self.parties.iter_mut() {
             let protocol_initializer =
-                ProtocolInitializerNotCertified::setup(self.params.unwrap(), stake, &mut rng);
-            let verification_key: ProtocolSignerVerificationKey =
-                protocol_initializer.verification_key();
+                ProtocolInitializerNotCertified::setup(self.params.unwrap(), party.stake, rng);
             players_artifacts.push(PlayerArtifact {
-                party_id,
-                stake,
-                verification_key: key_encode_hex(verification_key).unwrap(),
-                initializer: key_encode_hex(protocol_initializer).unwrap(),
-            })
+                party_id: party.clone().party_id,
+                stake: party.stake,
+                verification_key: key_encode_hex(protocol_initializer.verification_key()).unwrap(),
+                initializer: key_encode_hex(protocol_initializer.clone()).unwrap(),
+            });
+            party.initializer = Some(protocol_initializer);
         }
         let players_with_keys = players_artifacts
             .iter()
@@ -487,6 +482,8 @@ pub fn write_artifacts<T: Serialize>(artifact_name: &str, value: &T) {
 #[cfg(test)]
 mod tests {
     use super::*;
+    use rand_chacha::ChaCha20Rng;
+    use rand_core::SeedableRng;
 
     fn setup_protocol_parameters() -> ProtocolParameters {
         ProtocolParameters {
@@ -510,14 +507,18 @@ mod tests {
     #[test]
     fn test_demonstrator_new() {
         let config = default_config();
-        let demo = Demonstrator::new(&config);
+        let seed = [0u8; 32];
+        let mut rng = ChaCha20Rng::from_seed(seed);
+        let demo = Demonstrator::new(&config, &mut rng);
         assert_eq!(demo.config, config);
     }
 
     #[test]
     fn test_demonstrator_establish() {
         let config = default_config();
-        let mut demo = Demonstrator::new(&config);
+        let seed = [0u8; 32];
+        let mut rng = ChaCha20Rng::from_seed(seed);
+        let mut demo = Demonstrator::new(&config, &mut rng);
         demo.establish();
         assert_eq!(demo.params.unwrap().m, config.m);
         assert_eq!(demo.params.unwrap().k, config.k);
@@ -527,9 +528,11 @@ mod tests {
     #[test]
     fn test_demonstrator_initialize() {
         let config = default_config();
-        let mut demo = Demonstrator::new(&config);
+        let seed = [0u8; 32];
+        let mut rng = ChaCha20Rng::from_seed(seed);
+        let mut demo = Demonstrator::new(&config, &mut rng);
         demo.establish();
-        demo.initialize();
+        demo.initialize(&mut rng);
         assert_eq!(demo.parties.len(), config.nparties);
         assert_eq!(demo.messages.len(), config.nmessages);
         for party in demo.parties {
@@ -543,9 +546,11 @@ mod tests {
     #[test]
     fn test_demonstrator_issue_certificates_ok() {
         let config = default_config();
-        let mut demo = Demonstrator::new(&config);
+        let seed = [0u8; 32];
+        let mut rng = ChaCha20Rng::from_seed(seed);
+        let mut demo = Demonstrator::new(&config, &mut rng);
         demo.establish();
-        demo.initialize();
+        demo.initialize(&mut rng);
         demo.issue_certificates();
         assert_eq!(demo.parties.len(), config.nparties);
         assert_eq!(demo.messages.len(), config.nmessages);
@@ -559,9 +564,11 @@ mod tests {
         let mut config = default_config();
         config.k = 10000;
         config.m = 10;
-        let mut demo = Demonstrator::new(&config);
+        let seed = [0u8; 32];
+        let mut rng = ChaCha20Rng::from_seed(seed);
+        let mut demo = Demonstrator::new(&config, &mut rng);
         demo.establish();
-        demo.initialize();
+        demo.initialize(&mut rng);
         demo.issue_certificates();
         assert_eq!(demo.parties.len(), config.nparties);
         assert_eq!(demo.messages.len(), config.nmessages);
@@ -573,9 +580,11 @@ mod tests {
     #[test]
     fn test_demonstrator_verify_certificates_ok() {
         let config = default_config();
-        let mut demo = Demonstrator::new(&config);
+        let seed = [0u8; 32];
+        let mut rng = ChaCha20Rng::from_seed(seed);
+        let mut demo = Demonstrator::new(&config, &mut rng);
         demo.establish();
-        demo.initialize();
+        demo.initialize(&mut rng);
         demo.issue_certificates();
         assert_eq!(demo.parties.len(), config.nparties);
         assert_eq!(demo.messages.len(), config.nmessages);
@@ -587,9 +596,11 @@ mod tests {
         let mut config = default_config();
         config.k = 10000;
         config.m = 10;
-        let mut demo = Demonstrator::new(&config);
+        let seed = [0u8; 32];
+        let mut rng = ChaCha20Rng::from_seed(seed);
+        let mut demo = Demonstrator::new(&config, &mut rng);
         demo.establish();
-        demo.initialize();
+        demo.initialize(&mut rng);
         demo.issue_certificates();
         assert_eq!(demo.parties.len(), config.nparties);
         assert_eq!(demo.messages.len(), config.nmessages);
diff --git a/demo/protocol-demo/src/main.rs b/demo/protocol-demo/src/main.rs
index 58626cbc0..cb8dde27d 100644
--- a/demo/protocol-demo/src/main.rs
+++ b/demo/protocol-demo/src/main.rs
@@ -2,6 +2,8 @@ mod demonstrator;
 
 use crate::demonstrator::{Demonstrator, ProtocolDemonstrator};
 use clap::Parser;
+use rand_chacha::ChaCha20Rng;
+use rand_core::SeedableRng;
 
 /// Simple demonstration of the Mithril protocol
 #[derive(Parser, Debug, PartialEq, Clone, Copy)]
@@ -40,7 +42,9 @@ fn main() {
     /////////////////////
 
     println!("\n>> Protocol establish phase");
-    let mut mithril_protocol = Demonstrator::new(&config);
+    let seed = [0u8; 32];
+    let mut rng = ChaCha20Rng::from_seed(seed);
+    let mut mithril_protocol = Demonstrator::new(&config, &mut rng);
     mithril_protocol.establish();
 
     //////////////////////////
@@ -48,7 +52,7 @@ fn main() {
     /////////////////////////
 
     println!("\n>> Protocol initialize phase:");
-    mithril_protocol.initialize();
+    mithril_protocol.initialize(&mut rng);
 
     //////////////////////
     // operations phase //
diff --git a/mithril-common/src/crypto_helper/cardano/key_certification.rs b/mithril-common/src/crypto_helper/cardano/key_certification.rs
index 9a842078f..4a2a3f73a 100644
--- a/mithril-common/src/crypto_helper/cardano/key_certification.rs
+++ b/mithril-common/src/crypto_helper/cardano/key_certification.rs
@@ -13,7 +13,10 @@ use mithril::key_reg::{ClosedKeyReg, KeyReg};
 use mithril::stm::{Stake, StmInitializer, StmParameters, StmSigner, StmVerificationKeyPoP};
 use mithril::RegisterError;
 
-use blake2::{digest::consts::U32, Blake2b, Digest};
+use blake2::{
+    digest::{consts::U32, FixedOutput},
+    Blake2b, Digest,
+};
 use kes_summed_ed25519::kes::{Sum6Kes, Sum6KesSig};
 use kes_summed_ed25519::traits::{KesSig, KesSk};
 use rand_core::{CryptoRng, RngCore};
@@ -255,7 +258,7 @@ impl KeyRegWrapper {
 
     /// Finalize the key registration.
     /// This function disables `KeyReg::register`, consumes the instance of `self`, and returns a `ClosedKeyReg`.
-    pub fn close<D: Digest>(self) -> ClosedKeyReg<D> {
+    pub fn close<D: Digest + FixedOutput>(self) -> ClosedKeyReg<D> {
         self.stm_key_reg.close()
     }
 }
diff --git a/mithril-common/src/crypto_helper/types.rs b/mithril-common/src/crypto_helper/types.rs
index e112b43eb..c87d63221 100644
--- a/mithril-common/src/crypto_helper/types.rs
+++ b/mithril-common/src/crypto_helper/types.rs
@@ -49,7 +49,7 @@ pub type ProtocolClerk = StmClerk<D>;
 pub type ProtocolKeyRegistration = KeyRegWrapper;
 
 /// Alias of [MithrilCore:StmSig](struct@mithril::stm::StmSig).
-pub type ProtocolSingleSignature = StmSig<D>;
+pub type ProtocolSingleSignature = StmSig;
 
 /// Alias of [MithrilCore:StmAggrSig](struct@mithril::stm::StmAggrSig).
 pub type ProtocolMultiSignature = StmAggrSig<D>;
diff --git a/mithril-core/README.md b/mithril-core/README.md
index 8b5c3465e..378ac8d19 100644
--- a/mithril-core/README.md
+++ b/mithril-core/README.md
@@ -5,12 +5,12 @@ This crate is ongoing work, has not been audited, and it's API is by no means fi
 ### A rust implementation of Stake-based Threshold Multisignatures (STMs)
 `mithril-core` implements Stake-based Threshold Multisignatures as described in the paper
 [Mithril: Stake-based Threshold Multisignatures](https://eprint.iacr.org/2021/916.pdf), by
-Pyrros Chaidos and Aggelos Kiayias. 
+Pyrros Chaidos and Aggelos Kiayias.
 
 This library uses zkcrypto's implementation of curve [BLS12-381](https://github.com/zkcrypto/bls12_381)
-by default for implementing the multisignature scheme. One can optionally choose the 
-[blst](https://github.com/supranational/blst) backend (by using the feature `blast`), 
-but this is not recommended due to some [flaky tests](https://github.com/input-output-hk/mithril/issues/207) 
+by default for implementing the multisignature scheme. One can optionally choose the
+[blst](https://github.com/supranational/blst) backend (by using the feature `blast`),
+but this is not recommended due to some [flaky tests](https://github.com/input-output-hk/mithril/issues/207)
 That are still being resolved. We
 currently only support the trivial concatenation proof system (Section 4.3) and do not support
 other proof systems such as Bulletproofs or Halo2.
@@ -90,7 +90,7 @@ fn main() {
 
     // Aggregate with random parties
     let msig = clerk.aggregate(&sigs, &msg);
-    
+
     assert!(msig.is_ok(), "aggregation failed");
     assert!(msig.unwrap().verify(&msg, &clerk.compute_avk(), &params).is_ok());
 }
@@ -101,55 +101,62 @@ You can run tests of the library using `cargo test` (we recommend to use the `--
 the tests might take a while) and run benchmarks using `cargo bench`. This crate uses `criterion` to run
 benchmarks.
 
-We have run the benchmarks on a 2,7 GHz Quad-Core Intel Core i7 machine with 16 GB of RAM, on macOS 12.1. 
+We have run the benchmarks on an Apple M1 Pro machine with 16 GB of RAM, on macOS 12.6.
+
+Note that single signatures in batch compat version does not depend on any variable and size of an individual signature is `176` bytes.
 
 ```shell
-+-------------------+
-|   Size of proofs  |
-+-------------------+
-|-------------------|
-|   Trivial proofs  |
-+-------------------+
-| This gives and upper bound of the size
-| as it assumes that at most one signature
-| is provided by each participant.
-+-------------------+
-+-------------------+
-| Hash: Blake2b 512 |
-+-------------------+
-k = 25 | nr parties = 300; 19000 bytes
-+-------------------+
-| Hash:    SHA256   |
-+-------------------+
-k = 25 | nr parties = 300; 11800 bytes
-+-------------------+
-| Hash: Blake2b 512 |
-+-------------------+
-k = 250 | nr parties = 2000; 222000 bytes
-+-------------------+
-| Hash:    SHA256   |
-+-------------------+
-k = 250 | nr parties = 2000; 134000 bytes
++----------------------+
+| Size of benchmarks   |
++----------------------+
+| Results obtained by using the parameters suggested in paper.
++----------------------+
++----------------------+
+| Aggregate signatures |
++----------------------+
++----------------------+
+| Hash: Blake2b 512    |
++----------------------+
+k = 445 | m = 2728 | nr parties = 3000; 118760 bytes (old version = 356632 bytes)
++----------------------+
+| Hash: Blake2b 256    |
++----------------------+
+k = 445 | m = 2728 | nr parties = 3000; 99384 bytes (old version = 222536 bytes)
++----------------------+
++----------------------+
+| Aggregate signatures |
++----------------------+
+| Hash: Blake2b 512    |
++----------------------+
+k = 554 | m = 3597 | nr parties = 3000; 133936 bytes (old version = 419808 bytes)
++----------------------+
+| Hash: Blake2b 256    |
++----------------------+
+k = 554 | m = 3597 | nr parties = 3000; 113728 bytes (old version = 261488 bytes)
+make build && ./mithrildemo --nparties 16 -k 5 -m 5 --phi-f 0.9
 
 ```
 
 ```shell
-STM/Blake2b/Key registration/k: 25, m: 150, nr_parties: 300                                                                            
-                        time:   [1.4680 s 1.4706 s 1.4734 s]
-STM/Blake2b/Play all lotteries/k: 25, m: 150, nr_parties: 300                                                                             
-                        time:   [5.1228 ms 5.1296 ms 5.1361 ms]
-STM/Blake2b/Aggregation/k: 25, m: 150, nr_parties: 300                                                                            
-                        time:   [89.231 ms 89.371 ms 89.495 ms]
-STM/Blake2b/Verification/k: 25, m: 150, nr_parties: 300                                                                            
-                        time:   [33.170 ms 33.225 ms 33.292 ms] 
-STM/Blake2b/Key registration/k: 250, m: 1523, nr_parties: 2000                                                                            
-                        time:   [9.8741 s 9.9102 s 9.9644 s]
-STM/Blake2b/Play all lotteries/k: 250, m: 1523, nr_parties: 2000                                                                            
-                        time:   [48.935 ms 49.058 ms 49.185 ms]
-STM/Blake2b/Aggregation/k: 250, m: 1523, nr_parties: 2000                                                                            
-                        time:   [816.11 ms 817.55 ms 819.00 ms]
-STM/Blake2b/Verification/k: 250, m: 1523, nr_parties: 2000                                                                            
-                        time:   [293.18 ms 293.63 ms 294.19 ms]      
+STM/Blake2b/Key registration/k: 25, m: 150, nr_parties: 300
+                        time:   [409.70 ms 426.81 ms 446.30 ms]
+STM/Blake2b/Play all lotteries/k: 25, m: 150, nr_parties: 300
+                        time:   [696.58 µs 697.62 µs 698.75 µs]
+STM/Blake2b/Aggregation/k: 25, m: 150, nr_parties: 300
+                        time:   [18.765 ms 18.775 ms 18.785 ms]
+STM/Blake2b/Verification/k: 25, m: 150, nr_parties: 300
+                        time:   [2.1577 ms 2.1715 ms 2.1915 ms]
+
+STM/Blake2b/Key registration/k: 250, m: 1523, nr_parties: 2000
+                        time:   [2.5807 s 2.5880 s 2.5961 s]
+STM/Blake2b/Play all lotteries/k: 250, m: 1523, nr_parties: 2000
+                        time:   [5.9318 ms 5.9447 ms 5.9582 ms]
+STM/Blake2b/Aggregation/k: 250, m: 1523, nr_parties: 2000
+                        time:   [190.81 ms 191.15 ms 191.54 ms]
+STM/Blake2b/Verification/k: 250, m: 1523, nr_parties: 2000
+                        time:   [13.944 ms 14.010 ms 14.077 ms]
+
+
 ```
 
 # ToDo list once we go public
diff --git a/mithril-core/benches/size_benches.rs b/mithril-core/benches/size_benches.rs
index 7f380f426..7b0867ec6 100644
--- a/mithril-core/benches/size_benches.rs
+++ b/mithril-core/benches/size_benches.rs
@@ -1,15 +1,18 @@
+use blake2::digest::FixedOutput;
 use blake2::{
     digest::consts::{U32, U64},
     Blake2b, Digest,
 };
 use mithril::key_reg::KeyReg;
-use mithril::stm::{StmInitializer, StmParameters};
+use mithril::stm::{StmClerk, StmInitializer, StmParameters, StmSig, StmSigner};
 use rand_chacha::ChaCha20Rng;
 use rand_core::{RngCore, SeedableRng};
+use rayon::iter::ParallelIterator;
+use rayon::prelude::{IntoParallelIterator, IntoParallelRefIterator};
 
-fn size<H>(k: u64, nparties: usize, hash_name: &str)
+fn size<H>(k: u64, m: u64, nparties: usize, hash_name: &str)
 where
-    H: Digest + Clone + Sync + Send,
+    H: Digest + Clone + Sync + Send + Default + FixedOutput,
 {
     println!("+-------------------+");
     println!("| Hash: {} |", hash_name);
@@ -24,12 +27,7 @@ where
         .collect::<Vec<_>>();
 
     let mut ps: Vec<StmInitializer> = Vec::with_capacity(nparties);
-    let params = StmParameters {
-        k,
-        // m equal to one, to get an upper bound were a signer can only submit a single signature
-        m: 1,
-        phi_f: 1.0,
-    };
+    let params = StmParameters { k, m, phi_f: 0.2 };
 
     let mut key_reg = KeyReg::init();
     for stake in parties {
@@ -40,33 +38,39 @@ where
 
     let closed_reg = key_reg.close::<H>();
 
-    let signer = ps[0].clone().new_signer(closed_reg).unwrap();
-    let sig = signer.sign(&msg).unwrap();
+    let ps = ps
+        .into_par_iter()
+        .map(|p| p.new_signer(closed_reg.clone()).unwrap())
+        .collect::<Vec<StmSigner<H>>>();
+
+    let sigs = ps
+        .par_iter()
+        .filter_map(|p| p.sign(&msg))
+        .collect::<Vec<StmSig>>();
+    let clerk = StmClerk::from_signer(&ps[0]);
+
+    // Aggregate with random parties
+    let aggr = clerk.aggregate(&sigs, &msg).unwrap();
 
     println!(
-        "k = {} | nr parties = {}; {} bytes",
+        "k = {} | m = {} | nr parties = {}; {} bytes",
         k,
+        m,
         nparties,
-        sig.to_bytes().len() * k as usize
+        aggr.to_bytes().len() as usize,
     );
 }
 
 fn main() {
-    // Upper bound on the size. We only allow one signature per party. In practice
-    // a party with a lot of stake might win more than one lottery. The paths depend
-    // on the number of signers, so we need to iterate over that as well
     println!("+-------------------+");
     println!("|   Size of proofs  |");
     println!("+-------------------+");
-    println!("|-------------------|");
-    println!("|   Trivial proofs  |");
-    println!("+-------------------+");
-    println!("| This gives and upper bound of the size\n| as it assumes that at most one signature\n| is provided by each participant.");
+    println!("| Results obtained by using the parameters suggested in paper.");
     println!("+-------------------+");
 
-    let params: [(u64, usize); 2] = [(25, 300), (250, 2000)];
-    for (k, nparties) in params {
-        size::<Blake2b<U64>>(k, nparties, "Blake2b 512");
-        size::<Blake2b<U32>>(k, nparties, "Blake2b 256");
+    let params: [(u64, u64, usize); 2] = [(445, 2728, 3000), (554, 3597, 3000)];
+    for (k, m, nparties) in params {
+        size::<Blake2b<U64>>(k, m, nparties, "Blake2b 512");
+        size::<Blake2b<U32>>(k, m, nparties, "Blake2b 256");
     }
 }
diff --git a/mithril-core/benches/stm.rs b/mithril-core/benches/stm.rs
index 8749c2765..56671e8e7 100644
--- a/mithril-core/benches/stm.rs
+++ b/mithril-core/benches/stm.rs
@@ -1,4 +1,4 @@
-use blake2::digest::Digest;
+use blake2::digest::{Digest, FixedOutput};
 use blake2::{digest::consts::U32, Blake2b};
 use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
 use mithril::key_reg::KeyReg;
@@ -18,7 +18,7 @@ use std::fmt::Debug;
 
 fn stm_benches<H>(c: &mut Criterion, nr_parties: usize, params: StmParameters, hashing_alg: &str)
 where
-    H: Clone + Debug + Digest + Send + Sync,
+    H: Clone + Debug + Digest + Send + Sync + FixedOutput + Default,
 {
     let mut group = c.benchmark_group(format!("STM/{}", hashing_alg));
     let mut rng = ChaCha20Rng::from_seed([0u8; 32]);
diff --git a/mithril-core/src/error.rs b/mithril-core/src/error.rs
index 491d677c5..94e2f0fed 100644
--- a/mithril-core/src/error.rs
+++ b/mithril-core/src/error.rs
@@ -1,7 +1,7 @@
 //! Crate specific errors
 
-use crate::merkle_tree::Path;
-use blake2::digest::Digest;
+use crate::merkle_tree::{BatchPath, Path};
+use blake2::digest::{Digest, FixedOutput};
 use {
     crate::multi_sig::{Signature, VerificationKey, VerificationKeyPoP},
     blst::BLST_ERROR,
@@ -27,33 +27,13 @@ pub enum MultiSignatureError {
     KeyInvalid(Box<VerificationKeyPoP>),
 }
 
-/// Errors which can be output by Mithril verification.
+/// Errors which can be output by Mithril single signature verification.
 #[derive(Debug, Clone, thiserror::Error)]
-pub enum StmSignatureError<D: Digest> {
-    /// No quorum was found
-    #[error("No Quorum was found.")]
-    NoQuorum,
-
-    /// The IVK is invalid after aggregating the keys
-    #[error("Aggregated key does not correspond to the expected key.")]
-    IvkInvalid(VerificationKey),
-
-    /// Mu is not the sum of the signatures
-    #[error("Aggregated signature does not correspond to the expected signature.")]
-    SumInvalid(Signature),
-
+pub enum StmSignatureError {
     /// There is an index out of bounds
     #[error("Received index, {0}, is higher than what the security parameter allows, {1}.")]
     IndexBoundFailed(u64, u64),
 
-    /// There is a duplicate index
-    #[error("Indeces are not unique.")]
-    IndexNotUnique,
-
-    /// The path is not valid for the Merkle Tree
-    #[error("The path of the Merkle Tree is invalid.")]
-    PathInvalid(Path<D>),
-
     /// MSP.Eval was computed incorrectly
     #[error("The claimed evaluation of function phi is incorrect.")]
     EvalInvalid([u8; 64]),
@@ -64,15 +44,43 @@ pub enum StmSignatureError<D: Digest> {
 
     /// A party submitted an invalid signature
     #[error("A provided signature is invalid")]
-    SingleSignatureInvalid(Signature),
+    SignatureInvalid(Signature),
+
+    /// This error occurs when the the serialization of the raw bytes failed
+    #[error("Invalid bytes")]
+    SerializationError,
+}
+
+/// Errors which can be output by Mithril aggregate verification.
+#[derive(Debug, Clone, thiserror::Error)]
+pub enum StmAggregateSignatureError<D: Digest + FixedOutput> {
+    /// No quorum was found
+    #[error("No Quorum was found.")]
+    NoQuorum,
+
+    /// The IVK is invalid after aggregating the keys
+    #[error("Aggregated key does not correspond to the expected key.")]
+    IvkInvalid(VerificationKey),
+
+    /// There is a duplicate index
+    #[error("Indices are not unique.")]
+    IndexNotUnique,
 
     /// The aggregated signature is invalid
     #[error("Aggregate signature is invalid")]
-    SignatureInvalid,
+    AggregateSignatureInvalid,
+
+    /// One of the aggregated signatures is invalid
+    #[error("Individual signature is invalid: {0}")]
+    IndividualSignatureInvalid(StmSignatureError),
 
     /// This error occurs when the the serialization of the raw bytes failed
     #[error("Invalid bytes")]
     SerializationError,
+
+    /// Invalid merkle batch path
+    #[error("Batch path does not verify against root")]
+    PathInvalid(BatchPath<D>),
 }
 
 /// Error types for aggregation.
@@ -89,7 +97,7 @@ pub enum AggregationError {
 
 /// Error types related to merkle trees.
 #[derive(Debug, Clone, thiserror::Error)]
-pub enum MerkleTreeError<D: Digest> {
+pub enum MerkleTreeError<D: Digest + FixedOutput> {
     /// Serialization error
     #[error("Serialization of a merkle tree failed")]
     SerializationError,
@@ -97,6 +105,10 @@ pub enum MerkleTreeError<D: Digest> {
     /// Invalid merkle path
     #[error("Path does not verify against root")]
     PathInvalid(Path<D>),
+
+    /// Invalid merkle batch path
+    #[error("Batch path does not verify against root")]
+    BatchPathInvalid(BatchPath<D>),
 }
 
 /// Errors which can be outputted by key registration.
@@ -119,37 +131,44 @@ pub enum RegisterError {
     UnregisteredInitializer,
 }
 
-impl<D: Digest> From<RegisterError> for StmSignatureError<D> {
-    fn from(e: RegisterError) -> Self {
+impl<D: Digest + FixedOutput> From<MerkleTreeError<D>> for StmAggregateSignatureError<D> {
+    fn from(e: MerkleTreeError<D>) -> Self {
         match e {
-            RegisterError::SerializationError => Self::SerializationError,
-            RegisterError::KeyInvalid(e) => Self::IvkInvalid(e.vk),
-            RegisterError::KeyRegistered(_) => unreachable!(),
-            RegisterError::UnregisteredInitializer => unreachable!(),
+            MerkleTreeError::BatchPathInvalid(e) => Self::PathInvalid(e),
+            MerkleTreeError::SerializationError => Self::SerializationError,
+            MerkleTreeError::PathInvalid(_e) => unreachable!(),
         }
     }
 }
 
-impl<D: Digest> From<MerkleTreeError<D>> for StmSignatureError<D> {
-    fn from(e: MerkleTreeError<D>) -> Self {
+impl From<MultiSignatureError> for StmSignatureError {
+    fn from(e: MultiSignatureError) -> Self {
         match e {
-            MerkleTreeError::PathInvalid(e) => Self::PathInvalid(e),
-            MerkleTreeError::SerializationError => Self::SerializationError,
+            MultiSignatureError::SerializationError => Self::SerializationError,
+            MultiSignatureError::SignatureInvalid(e) => Self::SignatureInvalid(e),
+            MultiSignatureError::KeyInvalid(_) => unreachable!(),
+            MultiSignatureError::AggregateSignatureInvalid => unreachable!(),
         }
     }
 }
 
-impl<D: Digest> From<MultiSignatureError> for StmSignatureError<D> {
+impl<D: Digest + FixedOutput> From<MultiSignatureError> for StmAggregateSignatureError<D> {
     fn from(e: MultiSignatureError) -> Self {
         match e {
-            MultiSignatureError::SerializationError => Self::SerializationError,
-            MultiSignatureError::KeyInvalid(e) => Self::IvkInvalid(e.vk),
-            MultiSignatureError::SignatureInvalid(e) => Self::SingleSignatureInvalid(e),
-            MultiSignatureError::AggregateSignatureInvalid => Self::SignatureInvalid,
+            MultiSignatureError::AggregateSignatureInvalid => Self::AggregateSignatureInvalid,
+            MultiSignatureError::SerializationError => unreachable!(),
+            MultiSignatureError::KeyInvalid(_) => unreachable!(),
+            MultiSignatureError::SignatureInvalid(_e) => unreachable!(),
         }
     }
 }
 
+impl<D: Digest + FixedOutput> From<StmSignatureError> for StmAggregateSignatureError<D> {
+    fn from(e: StmSignatureError) -> Self {
+        StmAggregateSignatureError::IndividualSignatureInvalid(e)
+    }
+}
+
 impl From<MultiSignatureError> for RegisterError {
     fn from(e: MultiSignatureError) -> Self {
         match e {
diff --git a/mithril-core/src/key_reg.rs b/mithril-core/src/key_reg.rs
index 85261a502..65d696fa6 100644
--- a/mithril-core/src/key_reg.rs
+++ b/mithril-core/src/key_reg.rs
@@ -3,7 +3,7 @@ use super::stm::Stake;
 use crate::error::RegisterError;
 use crate::merkle_tree::{MTLeaf, MerkleTree};
 use crate::multi_sig::{VerificationKey, VerificationKeyPoP};
-use blake2::digest::Digest;
+use blake2::digest::{Digest, FixedOutput};
 use std::collections::hash_map::Entry;
 use std::collections::HashMap;
 use std::sync::Arc;
@@ -57,7 +57,10 @@ impl KeyReg {
 
     /// Finalize the key registration.
     /// This function disables `KeyReg::register`, consumes the instance of `self`, and returns a `ClosedKeyReg`.
-    pub fn close<D: Digest>(self) -> ClosedKeyReg<D> {
+    pub fn close<D>(self) -> ClosedKeyReg<D>
+    where
+        D: Digest + FixedOutput,
+    {
         let mut total_stake: Stake = 0;
         let mut reg_parties = self
             .keys
diff --git a/mithril-core/src/merkle_tree.rs b/mithril-core/src/merkle_tree.rs
index 906ed87d0..b01688c07 100644
--- a/mithril-core/src/merkle_tree.rs
+++ b/mithril-core/src/merkle_tree.rs
@@ -2,7 +2,7 @@
 use crate::error::MerkleTreeError;
 use crate::multi_sig::VerificationKey;
 use crate::stm::Stake;
-use blake2::digest::Digest;
+use blake2::digest::{Digest, FixedOutput};
 use serde::{Deserialize, Serialize};
 use std::cmp::Ordering;
 use std::convert::TryFrom;
@@ -17,13 +17,23 @@ pub struct MTLeaf(pub VerificationKey, pub Stake);
 /// Path of hashes from root to leaf in a Merkle Tree.
 /// Contains all hashes on the path, and the index of the leaf.
 /// Used to verify that signatures come from eligible signers.
-#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
+#[derive(Default, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
 pub struct Path<D: Digest> {
     pub(crate) values: Vec<Vec<u8>>,
     pub(crate) index: usize,
     hasher: PhantomData<D>,
 }
 
+/// Path of hashes for a batch of indices.
+/// Contains the hashes and the corresponding merkle tree indices of given batch.
+/// Used to verify the signatures are issued by the registered signers.
+#[derive(Default, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
+pub struct BatchPath<D: Digest + FixedOutput> {
+    pub(crate) values: Vec<Vec<u8>>,
+    pub(crate) indices: Vec<usize>,
+    pub(crate) hasher: PhantomData<D>,
+}
+
 /// `MerkleTree` commitment.
 /// This structure differs from `MerkleTree` in that it does not contain all elements, which are not always necessary.
 /// Instead, it only contains the root of the tree.
@@ -34,6 +44,18 @@ pub struct MerkleTreeCommitment<D: Digest> {
     hasher: PhantomData<D>,
 }
 
+/// Batch compatible `MerkleTree` commitment .
+/// This structure differs from `MerkleTreeCommitment` in that it stores the number of leaves in the tree
+/// as well as the root of the tree.
+/// Number of leaves is required by the batch path generation/verification.
+#[derive(Debug, Clone, Serialize, Deserialize)]
+pub struct MerkleTreeCommitmentBatchCompat<D: Digest> {
+    /// Root of the merkle commitment.
+    pub root: Vec<u8>,
+    nr_leaves: usize,
+    hasher: PhantomData<D>,
+}
+
 /// Tree of hashes, providing a commitment of data and its ordering.
 #[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
 pub struct MerkleTree<D: Digest> {
@@ -78,7 +100,7 @@ impl Ord for MTLeaf {
     }
 }
 
-impl<D: Digest + Clone> Path<D> {
+impl<D: Digest + Clone + FixedOutput> Path<D> {
     /// Convert to bytes
     /// # Layout
     /// * Index representing the position in the Merkle Tree
@@ -123,7 +145,73 @@ impl<D: Digest + Clone> Path<D> {
     }
 }
 
-impl<D: Clone + Digest> MerkleTreeCommitment<D> {
+impl<D: Digest + FixedOutput> BatchPath<D> {
+    /// Convert the `BatchPath` into byte representation.
+    ///
+    /// # Layout
+    /// The layout of a `BatchPath` is
+    /// * Length of values
+    /// * Length of indices
+    /// * Values
+    /// * Indices
+    pub fn to_bytes(&self) -> Vec<u8> {
+        let mut output = Vec::new();
+        let len_v = self.values.len();
+        let len_i = self.indices.len();
+
+        output.extend_from_slice(&u64::try_from(len_v).unwrap().to_be_bytes());
+        output.extend_from_slice(&u64::try_from(len_i).unwrap().to_be_bytes());
+
+        for value in &self.values {
+            output.extend_from_slice(value.as_slice())
+        }
+
+        for &index in &self.indices {
+            output.extend_from_slice(&u64::try_from(index).unwrap().to_be_bytes());
+        }
+        output
+    }
+
+    /// Try to convert a byte string into a `BatchPath`.
+    // todo: We should not panic if the size of the slice is invalid (I believe `bytes[offset + i * 8..offset + (i + 1) * 8]` will panic if bytes is not large enough.
+    pub fn from_bytes(bytes: &[u8]) -> Result<Self, MerkleTreeError<D>> {
+        let mut u64_bytes = [0u8; 8];
+        u64_bytes.copy_from_slice(&bytes[..8]);
+        let len_v = usize::try_from(u64::from_be_bytes(u64_bytes))
+            .map_err(|_| MerkleTreeError::SerializationError)?;
+
+        u64_bytes.copy_from_slice(&bytes[8..16]);
+        let len_i = usize::try_from(u64::from_be_bytes(u64_bytes))
+            .map_err(|_| MerkleTreeError::SerializationError)?;
+
+        let mut values = Vec::with_capacity(len_v);
+        for i in 0..len_v {
+            values.push(
+                bytes[16 + i * <D as Digest>::output_size()
+                    ..16 + (i + 1) * <D as Digest>::output_size()]
+                    .to_vec(),
+            );
+        }
+        let offset = 16 + len_v * <D as Digest>::output_size();
+
+        let mut indices = Vec::with_capacity(len_v);
+        for i in 0..len_i {
+            u64_bytes.copy_from_slice(&bytes[offset + i * 8..offset + (i + 1) * 8]);
+            indices.push(
+                usize::try_from(u64::from_be_bytes(u64_bytes))
+                    .map_err(|_| MerkleTreeError::SerializationError)?,
+            );
+        }
+
+        Ok(BatchPath {
+            values,
+            indices,
+            hasher: Default::default(),
+        })
+    }
+}
+
+impl<D: Clone + Digest + FixedOutput> MerkleTreeCommitment<D> {
     /// Check an inclusion proof that `val` is part of the tree by traveling the whole path until the root.
     /// # Error
     /// If the merkle tree path is invalid, then the function fails.
@@ -160,7 +248,123 @@ impl<D: Clone + Digest> MerkleTreeCommitment<D> {
     }
 }
 
-impl<D: Digest> MerkleTree<D> {
+impl<D: Clone + Digest> MerkleTreeCommitmentBatchCompat<D> {
+    /// Serializes the Merkle Tree commitment together with a message in a single vector of bytes.
+    /// Outputs `msg || self` as a vector of bytes.
+    // todo: Do we need to concat msg to whole commitment (nr_leaves and root) or just the root?
+    pub fn concat_with_msg(&self, msg: &[u8]) -> Vec<u8>
+    where
+        D: Digest,
+    {
+        let mut msgp = msg.to_vec();
+        let mut bytes = self.root.clone();
+        msgp.append(&mut bytes);
+
+        msgp
+    }
+
+    /// Check a proof of a batched opening. The indices must be ordered.
+    ///
+    /// # Error
+    /// Returns an error if the proof is invalid.
+    // todo: Update doc.
+    // todo: Simplify the algorithm.
+    // todo: Maybe we want more granular errors, rather than only `BatchPathInvalid`
+    pub fn check(
+        &self,
+        batch_val: &Vec<MTLeaf>,
+        proof: &BatchPath<D>,
+    ) -> Result<(), MerkleTreeError<D>>
+    where
+        D: FixedOutput,
+    {
+        if batch_val.len() != proof.indices.len() {
+            return Err(MerkleTreeError::BatchPathInvalid(proof.clone()));
+        }
+        let mut ordered_indices: Vec<usize> = proof.indices.clone();
+        ordered_indices.sort_unstable();
+
+        if ordered_indices != proof.indices {
+            return Err(MerkleTreeError::BatchPathInvalid(proof.clone()));
+        }
+
+        let nr_nodes = self.nr_leaves + self.nr_leaves.next_power_of_two() - 1;
+
+        ordered_indices = ordered_indices
+            .into_iter()
+            .map(|i| i + self.nr_leaves.next_power_of_two() - 1)
+            .collect();
+
+        let mut idx = ordered_indices[0];
+        // First we need to hash the leave values
+        let mut leaves: Vec<Vec<u8>> = batch_val
+            .iter()
+            .map(|val| D::digest(val.to_bytes()).to_vec())
+            .collect();
+
+        let mut values = proof.values.clone();
+
+        while idx > 0 {
+            let mut new_hashes = Vec::with_capacity(ordered_indices.len());
+            let mut new_indices = Vec::with_capacity(ordered_indices.len());
+            let mut i = 0;
+            idx = parent(idx);
+            while i < ordered_indices.len() {
+                new_indices.push(parent(ordered_indices[i]));
+                if ordered_indices[i] & 1 == 0 {
+                    new_hashes.push(
+                        D::new()
+                            .chain(&values.get(0).ok_or(MerkleTreeError::SerializationError)?)
+                            .chain(&leaves[i])
+                            .finalize()
+                            .to_vec(),
+                    );
+                    values.remove(0);
+                } else {
+                    let sibling = sibling(ordered_indices[i]);
+                    if i < ordered_indices.len() - 1 && ordered_indices[i + 1] == sibling {
+                        new_hashes.push(
+                            D::new()
+                                .chain(&leaves[i])
+                                .chain(&leaves[i + 1])
+                                .finalize()
+                                .to_vec(),
+                        );
+                        i += 1;
+                    } else if sibling < nr_nodes {
+                        new_hashes.push(
+                            D::new()
+                                .chain(&leaves[i])
+                                .chain(&values.get(0).ok_or(MerkleTreeError::SerializationError)?)
+                                .finalize()
+                                .to_vec(),
+                        );
+                        values.remove(0);
+                    } else {
+                        new_hashes.push(
+                            D::new()
+                                .chain(&leaves[i])
+                                .chain(&D::digest(&[0u8]))
+                                .finalize()
+                                .to_vec(),
+                        );
+                    }
+                }
+                i += 1;
+            }
+            leaves = new_hashes.clone();
+            ordered_indices = new_indices.clone();
+        }
+
+        if leaves.len() == 1 && leaves[0] == self.root {
+            return Ok(());
+        }
+
+        Err(MerkleTreeError::BatchPathInvalid(proof.clone()))
+    }
+}
+
+impl<D: Digest + FixedOutput> MerkleTree<D> {
     /// Provided a non-empty list of leaves, `create` generates its corresponding `MerkleTree`.
     pub fn create(leaves: &[MTLeaf]) -> MerkleTree<D> {
         let n = leaves.len();
@@ -209,6 +413,16 @@ impl<D: Digest> MerkleTree<D> {
         }
     }
 
+    /// Convert merkle tree to a batch compatible commitment.
+    /// This function simply returns the root and the number of leaves in the tree.
+    pub fn to_commitment_batch_compat(&self) -> MerkleTreeCommitmentBatchCompat<D> {
+        MerkleTreeCommitmentBatchCompat {
+            root: self.nodes[0].clone(),
+            nr_leaves: self.n,
+            hasher: self.hasher,
+        }
+    }
+
     /// Get the root of the tree.
     pub fn root(&self) -> &Vec<u8> {
         &self.nodes[0]
@@ -244,6 +458,76 @@ impl<D: Digest> MerkleTree<D> {
         }
     }
 
+    /// Get a path for a batch of leaves. The indices must be ordered. We use the Octopus algorithm to
+    /// avoid redundancy with nodes in the path. Let `x1, . . . , xk` be the indices of elements we
+    /// want to produce an opening for. The algorithm takes as input `x1, . . ., xk`, and  proceeds as follows:
+    /// 1. Initialise the proof vector, `proof = []`.
+    /// 2. Given an input vector `v = v1, . . .,vl`, if `v.len() == 1`, return `proof`, else, continue.
+    /// 3. Map each `vi` to the corresponding number of the leaf (by adding the offset).
+    /// 4. Initialise a new empty vector `p = []`. Next, iterate over each element `vi`
+    ///     a. Append the parent of `vi` to `p`
+    ///     b. Compute the sibling, `si` of `vi`
+    ///     c. If `si == v(i+1)` then do nothing, and skip step four for `v(i+1)`. Else append `si` to `proof`
+    /// 5. Iterate from step 2 with input vector `p`
+    ///
+    /// # Panics
+    /// If the indices provided are out of bounds (higher than the number of elements
+    /// committed in the `MerkleTree`) or are not ordered, the function fails.
+    // todo: Update doc.
+    pub fn get_batched_path(&self, indices: Vec<usize>) -> BatchPath<D>
+    where
+        D: FixedOutput,
+    {
+        assert!(
+            !indices.is_empty(),
+            "get_batched_path() called with no indices"
+        );
+        for i in &indices {
+            assert!(
+                i < &self.n,
+                "Proof index out of bounds: asked for {} out of {}",
+                i,
+                self.n
+            );
+        }
+
+        let mut ordered_indices: Vec<usize> = indices.clone();
+        ordered_indices.sort_unstable();
+
+        assert_eq!(ordered_indices, indices, "Indices should be ordered");
+
+        ordered_indices = ordered_indices
+            .into_iter()
+            .map(|i| self.idx_of_leaf(i))
+            .collect();
+
+        let mut idx = ordered_indices[0];
+        let mut proof = Vec::new();
+
+        while idx > 0 {
+            let mut new_indices = Vec::with_capacity(ordered_indices.len());
+            let mut i = 0;
+            idx = parent(idx);
+            while i < ordered_indices.len() {
+                new_indices.push(parent(ordered_indices[i]));
+                let sibling = sibling(ordered_indices[i]);
+                if i < ordered_indices.len() - 1 && ordered_indices[i + 1] == sibling {
+                    i += 1;
+                } else if sibling < self.nodes.len() {
+                    proof.push(self.nodes[sibling].clone());
+                }
+                i += 1;
+            }
+            ordered_indices = new_indices.clone();
+        }
+
+        BatchPath {
+            values: proof,
+            indices,
+            hasher: Default::default(),
+        }
+    }
+
     /// Return the index of the leaf.
     fn idx_of_leaf(&self, i: usize) -> usize {
         self.leaf_off + i
@@ -364,6 +648,14 @@ mod tests {
             })
         }
 
+        #[test]
+        fn test_bytes_tree_commitment((t, values) in arb_tree(5)) {
+            let encoded = bincode::serialize(&t.to_commitment()).unwrap();
+            let decoded: MerkleTreeCommitment::<Blake2b<U32>> = bincode::deserialize(&encoded).unwrap();
+            let tree_commitment = MerkleTree::<Blake2b<U32>>::create(&values).to_commitment();
+            assert_eq!(tree_commitment.root, decoded.root);
+        }
+
         #[test]
         fn test_bytes_tree((t, values) in arb_tree(5)) {
             let bytes = t.to_bytes();
@@ -377,12 +669,45 @@ mod tests {
         }
 
         #[test]
-        fn test_bytes_tree_commitment((t, values) in arb_tree(5)) {
-            let encoded = bincode::serialize(&t.to_commitment()).unwrap();
-            let decoded: MerkleTreeCommitment::<Blake2b<U32>> = bincode::deserialize(&encoded).unwrap();
-            let tree_commitment = MerkleTree::<Blake2b<U32>>::create(&values).to_commitment();
+        fn test_create_batch_proof((t, values) in arb_tree(30)) {
+            let mut mt_index_list :Vec<usize> = Vec::new();
+            for (i, _v) in values.iter().enumerate() {
+                mt_index_list.push(i);
+            }
+            mt_index_list.sort_unstable();
+            let batch_proof = t.get_batched_path(mt_index_list);
+            assert!(t.to_commitment_batch_compat().check(&values, &batch_proof).is_ok());
+        }
+
+        #[test]
+        fn test_bytes_batch_path((t, values) in arb_tree(30)) {
+            let mut mt_index_list :Vec<usize> = Vec::new();
+            for (i, _v) in values.iter().enumerate() {
+                mt_index_list.push(i);
+            }
+            mt_index_list.sort_unstable();
+
+            let bp = t.get_batched_path(mt_index_list);
+
+            let bytes = &bp.to_bytes();
+            let deserialized = BatchPath::from_bytes(bytes).unwrap();
+            assert!(t.to_commitment_batch_compat().check(&values, &deserialized).is_ok());
+
+            let encoded = bincode::serialize(&bp).unwrap();
+            let decoded: BatchPath<Blake2b<U32>> = bincode::deserialize(&encoded).unwrap();
+            assert!(t.to_commitment_batch_compat().check(&values, &decoded).is_ok());
+        }
+
+        #[test]
+        fn test_bytes_tree_commitment_batch_compat((t, values) in arb_tree(5)) {
+            let encoded = bincode::serialize(&t.to_commitment_batch_compat()).unwrap();
+            let decoded: MerkleTreeCommitmentBatchCompat::<Blake2b<U32>> = bincode::deserialize(&encoded).unwrap();
+            let tree_commitment = MerkleTree::<Blake2b<U32>>::create(&values).to_commitment_batch_compat();
             assert_eq!(tree_commitment.root, decoded.root);
+            assert_eq!(tree_commitment.nr_leaves, decoded.nr_leaves);
+
         }
+
     }
 
     fn pow2_plus1(h: usize) -> usize {
@@ -418,5 +743,24 @@ mod tests {
                 };
             assert!(t.to_commitment().check(&values[0], &path).is_err());
         }
+
+
+        #[test]
+        fn test_create_invalid_batch_proof(
+            i in any::<usize>(),
+            (values, proof) in values_with_invalid_proof(10)
+        ) {
+            let t = MerkleTree::<Blake2b<U32>>::create(&values[1..]);
+            let indices = vec![i % (values.len() - 1); values.len() / 2];
+            let batch_values = vec![values[i % (values.len() - 1)]; values.len() / 2];
+            let path = BatchPath{values: proof
+                            .iter()
+                            .map(|x|  Blake2b::<U32>::digest(x).to_vec())
+                            .collect(),
+                indices,
+                hasher: PhantomData::<Blake2b<U32>>::default()
+                };
+            assert!(t.to_commitment_batch_compat().check(&batch_values, &path).is_err());
+        }
     }
 }
diff --git a/mithril-core/src/stm.rs b/mithril-core/src/stm.rs
index 278c7d35e..766248f26 100644
--- a/mithril-core/src/stm.rs
+++ b/mithril-core/src/stm.rs
@@ -82,7 +82,7 @@
 //!     .filter_map(|p| {
 //!         return p.sign(&msg);
 //!     })
-//!     .collect::<Vec<StmSig<D>>>();
+//!     .collect::<Vec<StmSig>>();
 //!
 //! // StmClerk can aggregate and verify signatures.
 //! let clerk = StmClerk::from_signer(&ps[0]);
@@ -107,13 +107,16 @@
 //! ```
 
 use crate::dense_mapping::ev_lt_phi;
-use crate::error::{AggregationError, RegisterError, StmSignatureError};
+use crate::error::{
+    AggregationError, RegisterError, StmAggregateSignatureError, StmSignatureError,
+};
 use crate::key_reg::ClosedKeyReg;
-use crate::merkle_tree::{MTLeaf, MerkleTreeCommitment, Path};
+use crate::merkle_tree::{BatchPath, MTLeaf, MerkleTreeCommitmentBatchCompat};
 use crate::multi_sig::{Signature, SigningKey, VerificationKey, VerificationKeyPoP};
-use blake2::digest::Digest;
+use blake2::digest::{Digest, FixedOutput};
 use rand_core::{CryptoRng, RngCore};
 use serde::{Deserialize, Serialize};
+use std::cmp::Ordering;
 use std::collections::{BTreeMap, HashMap, HashSet};
 use std::convert::{From, TryFrom, TryInto};
 use std::hash::{Hash, Hasher};
@@ -187,11 +190,7 @@ pub struct StmClerk<D: Clone + Digest> {
 
 /// Signature created by a single party who has won the lottery.
 #[derive(Debug, Clone, Serialize, Deserialize)]
-#[serde(bound(
-    serialize = "Path<D>: Serialize",
-    deserialize = "Path<D>: Deserialize<'de>"
-))]
-pub struct StmSig<D: Clone + Digest> {
+pub struct StmSig {
     /// The signature from the underlying MSP scheme.
     pub sigma: Signature,
     /// The Stm verification Key.
@@ -200,30 +199,34 @@ pub struct StmSig<D: Clone + Digest> {
     pub stake: Stake,
     /// The index(es) for which the signature is valid
     pub indexes: Vec<Index>,
-    /// The path through the MerkleTree for this party.
-    pub path: Path<D>,
+    /// Merkle tree index of the signer.
+    pub signer_index: Index,
 }
 
-/// Stm aggregate key, which contains the merkle tree root and the total stake of the system.
+/// Stm aggregate key (batch compatible), which contains the merkle tree commitment and the total stake of the system.
+/// Batch Compat Merkle tree commitment includes the number of leaves in the tree in order to obtain batch path.
 #[derive(Debug, Clone, Serialize, Deserialize)]
 #[serde(bound(
-    serialize = "Path<D>: Serialize",
-    deserialize = "Path<D>: Deserialize<'de>"
+    serialize = "BatchPath<D>: Serialize",
+    deserialize = "BatchPath<D>: Deserialize<'de>"
 ))]
-pub struct StmAggrVerificationKey<D: Clone + Digest> {
-    mt_commitment: MerkleTreeCommitment<D>,
+pub struct StmAggrVerificationKey<D: Clone + Digest + FixedOutput> {
+    mt_commitment: MerkleTreeCommitmentBatchCompat<D>,
     total_stake: Stake,
 }
 
 /// `StmMultiSig` uses the "concatenation" proving system (as described in Section 4.3 of the original paper.)
 /// This means that the aggregated signature contains a vector with all individual signatures.
+/// BatchPath is also a part of the aggregate signature which covers path for all signatures.
 #[derive(Debug, Clone, Serialize, Deserialize)]
 #[serde(bound(
-    serialize = "Path<D>: Serialize",
-    deserialize = "Path<D>: Deserialize<'de>"
+    serialize = "BatchPath<D>: Serialize",
+    deserialize = "BatchPath<D>: Deserialize<'de>"
 ))]
-pub struct StmAggrSig<D: Clone + Digest> {
-    pub(crate) signatures: Vec<StmSig<D>>,
+pub struct StmAggrSig<D: Clone + Digest + FixedOutput> {
+    pub(crate) signatures: Vec<StmSig>,
+    /// The list of unique merkle tree nodes that covers path for all signatures.
+    pub batch_proof: BatchPath<D>,
 }
 
 impl StmParameters {
@@ -351,17 +354,18 @@ impl StmInitializer {
     }
 }
 
-impl<D: Clone + Digest> StmSigner<D> {
+impl<D: Clone + Digest + FixedOutput> StmSigner<D> {
     /// This function produces a signature following the description of Section 2.4.
     /// Once the signature is produced, this function checks whether any index in `[0,..,self.params.m]`
     /// wins the lottery by evaluating the dense mapping.
     /// It records all the winning indexes in `Self.indexes`.
-    /// If it wins at least one lottery, it produces the merkle path for its corresponding `(VerificationKey, Stake)`.
-    pub fn sign(&self, msg: &[u8]) -> Option<StmSig<D>> {
+    /// If it wins at least one lottery, it stores the signer's merkle tree index. The proof of membership
+    /// will be handled by the aggregator.
+    pub fn sign(&self, msg: &[u8]) -> Option<StmSig> {
         let msgp = self
             .closed_reg
             .merkle_tree
-            .to_commitment()
+            .to_commitment_batch_compat()
             .concat_with_msg(msg);
         let sigma = self.sk.sign(&msgp);
 
@@ -378,16 +382,12 @@ impl<D: Clone + Digest> StmSigner<D> {
             }
         }
         if !indexes.is_empty() {
-            let path = self
-                .closed_reg
-                .merkle_tree
-                .get_path(self.mt_index.try_into().ok()?);
             Some(StmSig {
                 sigma,
                 pk: self.vk,
                 stake: self.stake,
                 indexes,
-                path,
+                signer_index: self.mt_index,
             })
         } else {
             None
@@ -406,7 +406,7 @@ impl<D: Clone + Digest> StmSigner<D> {
     }
 }
 
-impl<D: Digest + Clone> StmClerk<D> {
+impl<D: Digest + Clone + FixedOutput> StmClerk<D> {
     /// Create a new `Clerk` from a closed registration instance.
     pub fn from_registration(params: &StmParameters, closed_reg: &ClosedKeyReg<D>) -> Self {
         Self {
@@ -425,36 +425,47 @@ impl<D: Digest + Clone> StmClerk<D> {
 
     /// Aggregate a set of signatures for their corresponding indices.
     ///
-    /// This function first deduplicates the repeated signatures and, if there are enough
-    /// signatures, returns an instance of `StmAggrSig`.
+    /// This function first deduplicates the repeated signatures, and if there are enough signatures, it collects the merkle tree indexes of unique signatures.
+    /// The list of merkle tree indexes is used to create a batch proof, to prove that all signatures are from eligible signers.
+    ///
+    /// It returns an instance of `StmAggrSig`.
     pub fn aggregate(
         &self,
-        sigs: &[StmSig<D>],
+        sigs: &[StmSig],
         msg: &[u8],
     ) -> Result<StmAggrSig<D>, AggregationError> {
-        let unique_sigs = self.dedup_sigs_for_indices(msg, sigs)?;
+        let mut unique_sigs = self.dedup_sigs_for_indices(msg, sigs)?;
+        unique_sigs.sort_unstable();
+
+        let mt_index_list = unique_sigs
+            .iter()
+            .map(|sig| sig.signer_index as usize)
+            .collect::<Vec<usize>>();
+
+        let batch_proof = self.closed_reg.merkle_tree.get_batched_path(mt_index_list);
 
         Ok(StmAggrSig {
             signatures: unique_sigs,
+            batch_proof,
         })
     }
 
-    /// Given a slice of `sigs`, this function returns a new list of signatures with only  valid indices.
+    /// Given a slice of `sigs`, this function returns a new list of signatures with only valid indices.
     /// In case of conflict (having several signatures for the same index)
     /// it selects the smallest signature (i.e. takes the signature with the smallest scalar).
     /// The function selects at least `self.k` indexes.
     ///  # Error
-    /// If there is no sufficient signatures, then the function fails.s
+    /// If there is no sufficient signatures, then the function fails.
     // todo: We need to agree on a criteria to dedup (by defaut we use a BTreeMap that guarantees keys order)
     // todo: not good, because it only removes index if there is a conflict (see benches)
     pub fn dedup_sigs_for_indices(
         &self,
         msg: &[u8],
-        sigs: &[StmSig<D>],
-    ) -> Result<Vec<StmSig<D>>, AggregationError> {
+        sigs: &[StmSig],
+    ) -> Result<Vec<StmSig>, AggregationError> {
         let avk = StmAggrVerificationKey::from(&self.closed_reg);
-        let mut sig_by_index: BTreeMap<Index, &StmSig<D>> = BTreeMap::new();
-        let mut removal_idx_by_vk: HashMap<&StmSig<D>, Vec<Index>> = HashMap::new();
+        let mut sig_by_index: BTreeMap<Index, &StmSig> = BTreeMap::new();
+        let mut removal_idx_by_vk: HashMap<&StmSig, Vec<Index>> = HashMap::new();
 
         for sig in sigs.iter() {
             if sig.verify(&self.params, &avk, msg).is_err() {
@@ -486,7 +497,7 @@ impl<D: Digest + Clone> StmClerk<D> {
             }
         }
 
-        let mut dedup_sigs: HashSet<StmSig<D>> = HashSet::new();
+        let mut dedup_sigs: HashSet<StmSig> = HashSet::new();
         let mut count: u64 = 0;
 
         for (_, &sig) in sig_by_index.iter() {
@@ -526,31 +537,29 @@ impl<D: Digest + Clone> StmClerk<D> {
     }
 }
 
-impl<D: Clone + Digest> StmSig<D> {
-    /// Verify an stm signature by checking that the lottery was won, the merkle path is correct,
+impl StmSig {
+    /// Verify an stm signature by checking that the lottery was won,
     /// the indexes are in the desired range and the underlying multi signature validates.
-    pub fn verify(
+    pub fn verify<D: Clone + Digest + FixedOutput>(
         &self,
         params: &StmParameters,
         avk: &StmAggrVerificationKey<D>,
         msg: &[u8],
-    ) -> Result<(), StmSignatureError<D>> {
+    ) -> Result<(), StmSignatureError> {
         let msgp = avk.mt_commitment.concat_with_msg(msg);
-
         self.sigma.verify(&msgp, &self.pk)?;
         self.check_indices(params, &msgp, avk)?;
-        avk.mt_commitment
-            .check(&MTLeaf(self.pk, self.stake), &self.path)?;
+
         Ok(())
     }
 
     /// Verify that all indices of a signature are valid.
-    pub(crate) fn check_indices(
+    pub(crate) fn check_indices<D: Clone + Digest + FixedOutput>(
         &self,
         params: &StmParameters,
         msgp: &[u8],
         avk: &StmAggrVerificationKey<D>,
-    ) -> Result<(), StmSignatureError<D>> {
+    ) -> Result<(), StmSignatureError> {
         for &index in &self.indexes {
             if index > params.m {
                 return Err(StmSignatureError::IndexBoundFailed(index, params.m));
@@ -569,80 +578,108 @@ impl<D: Clone + Digest> StmSig<D> {
     /// Convert an `StmSig` into bytes
     ///
     /// # Layout
-    /// * Party id
     /// * Stake
     /// * Number of valid indexes (as u64)
     /// * Indexes of the signature
     /// * Public Key
     /// * Signature
-    /// * Merkle Tree path
+    /// * Merkle index of the signer.
     pub fn to_bytes(&self) -> Vec<u8> {
         let mut output = Vec::new();
         output.extend_from_slice(&self.stake.to_be_bytes());
         output.extend_from_slice(&(self.indexes.len() as u64).to_be_bytes());
+
         for index in &self.indexes {
             output.extend_from_slice(&index.to_be_bytes());
         }
+
         output.extend_from_slice(&self.pk.to_bytes());
         output.extend_from_slice(&self.sigma.to_bytes());
-        output.extend_from_slice(&self.path.to_bytes());
+
+        output.extend_from_slice(&self.signer_index.to_be_bytes());
         output
     }
 
-    /// Extract an `StmSig` from a byte slice.
-    pub fn from_bytes(bytes: &[u8]) -> Result<StmSig<D>, StmSignatureError<D>> {
+    /// Extract a batch compatible `StmSig` from a byte slice.
+    pub fn from_bytes<D: Clone + Digest + FixedOutput>(
+        bytes: &[u8],
+    ) -> Result<StmSig, StmSignatureError> {
         let mut u64_bytes = [0u8; 8];
+
         u64_bytes.copy_from_slice(&bytes[..8]);
         let stake = u64::from_be_bytes(u64_bytes);
+
         u64_bytes.copy_from_slice(&bytes[8..16]);
         let nr_indexes = u64::from_be_bytes(u64_bytes) as usize;
-        let mut index = Vec::new();
+
+        let mut indexes = Vec::new();
         for i in 0..nr_indexes {
             u64_bytes.copy_from_slice(&bytes[16 + i * 8..24 + i * 8]);
-            index.push(u64::from_be_bytes(u64_bytes));
+            indexes.push(u64::from_be_bytes(u64_bytes));
         }
-        let pk = StmVerificationKey::from_bytes(&bytes[16 + nr_indexes * 8..])?;
-        let sigma = Signature::from_bytes(&bytes[112 + nr_indexes * 8..])?;
-        let path = Path::from_bytes(&bytes[160 + nr_indexes * 8..])?;
+
+        let offset = 16 + nr_indexes * 8;
+        let pk = StmVerificationKey::from_bytes(&bytes[offset..offset + 96])?;
+        let sigma = Signature::from_bytes(&bytes[offset + 96..offset + 144])?;
+
+        u64_bytes.copy_from_slice(&bytes[offset + 144..offset + 152]);
+        let signer_index = u64::from_be_bytes(u64_bytes);
 
         Ok(StmSig {
             sigma,
             pk,
             stake,
-            indexes: index,
-            path,
+            indexes,
+            signer_index,
         })
     }
+
+    /// Compare two `StmSig` by their signers' merkle tree indexes.
+    pub fn cmp_stm_sig(&self, other: &Self) -> Ordering {
+        self.signer_index.cmp(&other.signer_index)
+    }
 }
 
-impl<D: Clone + Digest> Hash for StmSig<D> {
+impl Hash for StmSig {
     fn hash<H: Hasher>(&self, state: &mut H) {
         Hash::hash_slice(&self.sigma.to_bytes(), state)
     }
 }
 
-impl<D: Clone + Digest> PartialEq for StmSig<D> {
+impl PartialEq for StmSig {
     fn eq(&self, other: &Self) -> bool {
         self.sigma == other.sigma
     }
 }
 
-impl<D: Clone + Digest> Eq for StmSig<D> {}
+impl Eq for StmSig {}
+
+impl PartialOrd for StmSig {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp_stm_sig(other))
+    }
+}
+
+impl Ord for StmSig {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.cmp_stm_sig(other)
+    }
+}
 
-impl<D: Clone + Digest> From<&ClosedKeyReg<D>> for StmAggrVerificationKey<D> {
+impl<D: Clone + Digest + FixedOutput> From<&ClosedKeyReg<D>> for StmAggrVerificationKey<D> {
     fn from(reg: &ClosedKeyReg<D>) -> Self {
         Self {
-            mt_commitment: reg.merkle_tree.to_commitment(),
+            mt_commitment: reg.merkle_tree.to_commitment_batch_compat(),
             total_stake: reg.total_stake,
         }
     }
 }
 
-impl<D: Clone + Digest> StmAggrSig<D> {
+impl<D: Clone + Digest + FixedOutput> StmAggrSig<D> {
     /// Verify aggregate signature, by checking that
     /// * each signature contains only valid indices,
     /// * the lottery is indeed won by each one of them,
-    /// * the merkle tree path is valid,
+    /// * the batched path is valid,
     /// * the aggregate signature validates with respect to the aggregate verification key
     /// (aggregation is computed using functions `MSP.BKey` and `MSP.BSig` as described in Section 2.4 of the paper).
     pub fn verify(
@@ -650,43 +687,34 @@ impl<D: Clone + Digest> StmAggrSig<D> {
         msg: &[u8],
         avk: &StmAggrVerificationKey<D>,
         parameters: &StmParameters,
-    ) -> Result<(), StmSignatureError<D>> {
-        // Check that indices are all smaller than `m` and they are unique
+    ) -> Result<(), StmAggregateSignatureError<D>> {
         let mut nr_indices = 0;
         let mut unique_indices = HashSet::new();
+        let mut leaves = Vec::new();
+
         for sig in &self.signatures {
+            let msgp = avk.mt_commitment.concat_with_msg(msg);
+            sig.check_indices(parameters, &msgp, avk)?;
+
             for &index in &sig.indexes {
-                if index > parameters.m {
-                    return Err(StmSignatureError::IndexBoundFailed(index, parameters.m));
-                }
                 unique_indices.insert(index);
                 nr_indices += 1;
             }
+
+            let mt_leaf = MTLeaf(sig.pk, sig.stake);
+            leaves.push(mt_leaf);
         }
 
         if nr_indices != unique_indices.len() {
-            return Err(StmSignatureError::IndexNotUnique);
+            return Err(StmAggregateSignatureError::IndexNotUnique);
         }
 
-        // Check that there are sufficient signatures
         if (nr_indices as u64) < parameters.k {
-            return Err(StmSignatureError::NoQuorum);
+            return Err(StmAggregateSignatureError::NoQuorum);
         }
 
-        // Check that all signatures did win the lottery
-        for sig in self.signatures.iter() {
-            let msgp = avk.mt_commitment.concat_with_msg(msg);
-            sig.check_indices(parameters, &msgp, avk)?;
-
-            // Check that merkle paths are valid
-            if avk
-                .mt_commitment
-                .check(&MTLeaf(sig.pk, sig.stake), &sig.path)
-                .is_err()
-            {
-                return Err(StmSignatureError::PathInvalid(sig.path.clone()));
-            }
-        }
+        let proof = &self.batch_proof;
+        avk.mt_commitment.check(&leaves, &proof.clone())?;
 
         let msg = avk.mt_commitment.concat_with_msg(msg);
         let signatures = self
@@ -709,6 +737,7 @@ impl<D: Clone + Digest> StmAggrSig<D> {
     /// * Number of signatures (as u64)
     /// * Size of a signature
     /// * Signatures
+    /// * Batch proof
     pub fn to_bytes(&self) -> Vec<u8> {
         let mut out = Vec::new();
         out.extend_from_slice(&u64::try_from(self.signatures.len()).unwrap().to_be_bytes());
@@ -720,26 +749,38 @@ impl<D: Clone + Digest> StmAggrSig<D> {
         for sig in &self.signatures {
             out.extend_from_slice(&sig.to_bytes())
         }
+        let proof = &self.batch_proof;
+        out.extend_from_slice(&proof.to_bytes());
+
         out
     }
 
-    /// Extract a `StmMultiSig` from a byte slice.
-    pub fn from_bytes(bytes: &[u8]) -> Result<StmAggrSig<D>, StmSignatureError<D>> {
+    ///Extract a `StmAggrSig` from a byte slice.
+    pub fn from_bytes(bytes: &[u8]) -> Result<StmAggrSig<D>, StmAggregateSignatureError<D>> {
         let mut u64_bytes = [0u8; 8];
+
         u64_bytes.copy_from_slice(&bytes[..8]);
         let size = usize::try_from(u64::from_be_bytes(u64_bytes))
-            .map_err(|_| StmSignatureError::SerializationError)?;
+            .map_err(|_| StmAggregateSignatureError::SerializationError)?;
+
         u64_bytes.copy_from_slice(&bytes[8..16]);
         let sig_size = usize::try_from(u64::from_be_bytes(u64_bytes))
-            .map_err(|_| StmSignatureError::SerializationError)?;
+            .map_err(|_| StmAggregateSignatureError::SerializationError)?;
+
         let mut signatures = Vec::with_capacity(size);
         for i in 0..size {
-            signatures.push(StmSig::from_bytes(
+            signatures.push(StmSig::from_bytes::<D>(
                 &bytes[16 + i * sig_size..16 + (i + 1) * sig_size],
             )?);
         }
 
-        Ok(StmAggrSig { signatures })
+        let offset = 16 + sig_size * size;
+        let batch_proof = BatchPath::from_bytes(&bytes[offset..])?;
+
+        Ok(StmAggrSig {
+            signatures,
+            batch_proof,
+        })
     }
 }
 
@@ -747,6 +788,7 @@ impl<D: Clone + Digest> StmAggrSig<D> {
 mod tests {
     use super::*;
     use crate::key_reg::*;
+    use crate::merkle_tree::BatchPath;
     use bincode;
     use blake2::{digest::consts::U32, Blake2b};
     use proptest::collection::{hash_map, vec};
@@ -845,7 +887,7 @@ mod tests {
         )
     }
 
-    fn find_signatures(msg: &[u8], ps: &[StmSigner<D>], is: &[usize]) -> Vec<StmSig<D>> {
+    fn find_signatures(msg: &[u8], ps: &[StmSigner<D>], is: &[usize]) -> Vec<StmSig> {
         let mut sigs = Vec::new();
         for i in is {
             if let Some(sig) = ps[*i].sign(msg) {
@@ -926,7 +968,7 @@ mod tests {
             match msig {
                 Ok(aggr) => {
                     let verify_result = aggr.verify(&msg, &clerk.compute_avk(), &params);
-                    assert!(verify_result.is_ok(), "{:?}", verify_result);
+                    assert!(verify_result.is_ok(), "Verification failed: {:?}", verify_result);
                 }
                 Err(AggregationError::NotEnoughSignatures(n, k)) =>
                     assert!(n < params.k || k == params.k),
@@ -972,11 +1014,11 @@ mod tests {
 
             if let Some(sig) = p.sign(&msg) {
                 let bytes = sig.to_bytes();
-                let sig_deser = StmSig::<D>::from_bytes(&bytes).unwrap();
+                let sig_deser = StmSig::from_bytes::<D>(&bytes).unwrap();
                 assert!(sig_deser.verify(&params, &avk, &msg).is_ok());
 
                 let encoded = bincode::serialize(&sig).unwrap();
-                let decoded: StmSig::<D> = bincode::deserialize(&encoded).unwrap();
+                let decoded: StmSig = bincode::deserialize(&encoded).unwrap();
                 assert!(decoded.verify(&params, &avk, &msg).is_ok());
             }
         }
@@ -984,7 +1026,7 @@ mod tests {
         #[test]
         fn test_multisig_serialize_deserialize(nparties in 2_usize..10,
                                           msg in any::<[u8;16]>()) {
-            let params = StmParameters { m: 10, k: 1, phi_f: 1.0 };
+            let params = StmParameters { m: 10, k: 5, phi_f: 1.0 };
             let ps = setup_equal_parties(params, nparties);
             let clerk = StmClerk::from_signer(&ps[0]);
 
@@ -1061,12 +1103,10 @@ mod tests {
 
     #[derive(Debug)]
     struct ProofTest {
-        n: usize,
         msig: Result<Sig, AggregationError>,
         clerk: StmClerk<D>,
         msg: [u8; 16],
     }
-
     /// Run the protocol up to aggregation. This will produce a valid aggregation of signatures.
     /// The following tests mutate this aggregation so that the proof is no longer valid.
     fn arb_proof_setup(max_parties: usize) -> impl Strategy<Value = ProofTest> {
@@ -1084,12 +1124,7 @@ mod tests {
                 let sigs = find_signatures(&msg, &ps, &all_ps);
 
                 let msig = clerk.aggregate(&sigs, &msg);
-                ProofTest {
-                    n,
-                    msig,
-                    clerk,
-                    msg,
-                }
+                ProofTest { msig, clerk, msg }
             })
         })
     }
@@ -1136,11 +1171,20 @@ mod tests {
             })
         }
         #[test]
-        fn test_invalid_proof_path(tc in arb_proof_setup(10), i in any::<usize>()) {
-            let n = tc.n;
+        fn test_invalid_proof_path(tc in arb_proof_setup(10)) {
             with_proof_mod(tc, |aggr, _, _msg| {
-                let pi = i % aggr.signatures.len();
-                aggr.signatures[pi].path.index = (aggr.signatures[pi].path.index + 1) % n;
+                let p = aggr.batch_proof.clone();
+                let mut index_list = p.indices.clone();
+                let values = p.values;
+                let batch_proof = {
+                    index_list[0] += 1;
+                    BatchPath {
+                        values,
+                        indices: index_list,
+                        hasher: Default::default()
+                    }
+                };
+                aggr.batch_proof = batch_proof;
             })
         }
     }


Test patch:
diff --git a/mithril-aggregator/tests/certificate_chain.rs b/mithril-aggregator/tests/certificate_chain.rs
index 0fe47e472..91e94aa14 100644
--- a/mithril-aggregator/tests/certificate_chain.rs
+++ b/mithril-aggregator/tests/certificate_chain.rs
@@ -13,7 +13,7 @@ async fn certificate_chain() {
     let protocol_parameters = ProtocolParameters {
         k: 5,
         m: 100,
-        phi_f: 0.65,
+        phi_f: 0.95,
     };
     let mut tester = RuntimeTester::build(protocol_parameters.clone()).await;
 
diff --git a/mithril-aggregator/tests/create_certificate.rs b/mithril-aggregator/tests/create_certificate.rs
index df04e3323..de0d7c01f 100644
--- a/mithril-aggregator/tests/create_certificate.rs
+++ b/mithril-aggregator/tests/create_certificate.rs
@@ -10,7 +10,7 @@ async fn create_certificate() {
     let protocol_parameters = ProtocolParameters {
         k: 5,
         m: 100,
-        phi_f: 0.65,
+        phi_f: 0.95,
     };
     let mut tester = RuntimeTester::build(protocol_parameters.clone()).await;
 
diff --git a/mithril-aggregator/tests/test_extensions/runtime_tester.rs b/mithril-aggregator/tests/test_extensions/runtime_tester.rs
index 19fb95a4a..1552f274d 100644
--- a/mithril-aggregator/tests/test_extensions/runtime_tester.rs
+++ b/mithril-aggregator/tests/test_extensions/runtime_tester.rs
@@ -221,6 +221,13 @@ impl RuntimeTester {
                             e
                         )
                     })?;
+            } else {
+                panic!(
+                    "Signer '{}' could not sign. \
+                    This test is based on the assumption that every signer signs everytime. \
+                    Possible fix: relax the protocol parameters or give more stakes to this signer.",
+                    signer_with_stake.party_id
+                );
             }
         }
 
diff --git a/mithril-core/proptest-regressions/stm.txt b/mithril-core/proptest-regressions/stm.txt
index 9fbc0b8fe..145bf068d 100644
--- a/mithril-core/proptest-regressions/stm.txt
+++ b/mithril-core/proptest-regressions/stm.txt
@@ -13,3 +13,5 @@ cc bfe6fbad028ad86d75df7c75d29ee8f3279a81acbf50ef971b3dae92d529eeeb # shrinks to
 cc 9ef4bbf885dd054e2e54c85d0a54ef324d5ef7af232157c50bd55986640c6cab # shrinks to nparties = 7, m = 11, k = 1, msg = [16, 197, 45, 60, 228, 119, 173, 69, 2, 156, 57, 238, 34, 178, 228, 198]
 cc 533659c456e216b566b35d413e0b505c6e4d8d04ab402d79343e46a5a32c7c9d # shrinks to nparties = 18, m = 11, k = 1, msg = [78, 114, 142, 29, 122, 86, 154, 181, 170, 165, 114, 115, 234, 82, 143, 36]
 cc f2c14c2a2d3f02a4d98028f41effa69c153529df611e2206e9cbf540e7a99079 # shrinks to nparties = 2, m = 14, k = 1, msg = [69, 0, 87, 0, 53, 5, 58, 203, 42, 90, 66, 244, 89, 95, 198, 22]
+cc 55d304e2dd7bed15dace28eaf8d75174ff9b43e12b98257eb0c5f9296dae66d8 # shrinks to nparties = 21, m = 13, k = 3, msg = [21, 101, 128, 247, 30, 236, 71, 44, 165, 161, 251, 81, 117, 162, 221, 120]
+cc 174b0d31fe87e15ff2e295149062b3adc65b722d8cff4c08257d4b93d72b086b # shrinks to nparties = 15, m = 10, k = 3, msg = [217, 131, 84, 187, 173, 212, 75, 52, 100, 187, 38, 147, 226, 0, 218, 88]
diff --git a/mithril-core/tests/integration.rs b/mithril-core/tests/integration.rs
index b41b481a5..fd86f1e75 100644
--- a/mithril-core/tests/integration.rs
+++ b/mithril-core/tests/integration.rs
@@ -56,7 +56,7 @@ fn test_full_protocol() {
     let sigs = ps
         .par_iter()
         .filter_map(|p| p.sign(&msg))
-        .collect::<Vec<StmSig<H>>>();
+        .collect::<Vec<StmSig>>();
 
     let clerk = StmClerk::from_signer(&ps[0]);
     let avk = clerk.compute_avk();