Crate mithril_stm

Source

Expand description

§Mithril-stm

This is a work in progress 🛠

mithril-stm is a Rust implementation of the scheme described in the paper Mithril: Stake-based Threshold Multisignatures by Pyrros Chaidos and Aggelos Kiayias.
The BLS12-381 signature library blst is used as the backend for the implementation of STM.
This implementation supports the trivial concatenation proof system (Section 4.3). Other proof systems such as Bulletproofs or Halo2 are not supported in this version.
We implemented the concatenation proof system as batch proofs:
- Individual signatures do not contain the Merkle path to prove membership of the avk. Instead, it is the role of the aggregator to generate such proofs. This allows for a more efficient implementation of batched membership proofs (or batched Merkle paths).
Protocol documentation is given in Mithril Protocol in depth.
The API also includes core verification. This functionality allows a full node verifier (CoreVerifier) that is able to verify the signatures that are generated without the registration information, i.e., avk. A CoreVerifier is assumed to know identities of the signers, so, it does not need to check the registration.
This library provides:
- The implementation of the Stake-based Threshold Multisignatures
- The implementation of CoreVerifier
- Key registration procedure for STM signatures
- The tests for the library functions, STM scheme, and CoreVerifier
- Benchmark tests

§Pre-requisites

Install Rust

Install a correctly configured Rust toolchain (latest stable version).
Install Build Tools build-essential and m4. For example, on Ubuntu/Debian/Mint, run sudo apt install build-essential m4.

§Download source code

# Download sources from github
git clone https://github.com/input-output-hk/mithril

# Go to sources directory
cd mithril-stm

§Compiling the library

cargo build --release

§Running the tests

For running rust tests, simply run (to run the tests faster, the use of --release flag is recommended):

cargo test --release

§Running the benches

cargo bench

§Example

The following is a simple example of the STM implementation:

use mithril_stm::{StmClerk, StmParameters, StmSig, KeyReg, StmInitializer, StmSigner, AggregationError};

use blake2::{digest::consts::U32, Blake2b};
use rayon::prelude::*;
use rand_chacha::ChaCha20Rng;
use rand_core::{RngCore, SeedableRng};

type H = Blake2b<U32>;

fn main() {
    let nparties = 32;
    let mut rng = ChaCha20Rng::from_seed([0u8; 32]);
    let mut msg = [0u8; 16];
    rng.fill_bytes(&mut msg);

    //////////////////////////
    // initialization phase //
    //////////////////////////

    let params = StmParameters {
        k: 357,
        m: 2642,
        phi_f: 0.2,
    };

    let parties = (0..nparties)
        .into_iter()
        .map(|_| 1 + (rng.next_u64() % 9999))
        .collect::<Vec<_>>();

    let mut key_reg = KeyReg::init();

    let mut ps: Vec<StmInitializer> = Vec::with_capacity(nparties as usize);
    for stake in parties {
        let p = StmInitializer::setup(params, stake, &mut rng);
        key_reg.register(stake, p.verification_key()).unwrap();
        ps.push(p);
    }

    let closed_reg = key_reg.close();

    let ps = ps
        .into_par_iter()
        .map(|p| p.new_signer(closed_reg.clone()).unwrap())
        .collect::<Vec<StmSigner<H>>>();

    /////////////////////
    // operation phase //
    /////////////////////

    let sigs = ps
        .par_iter()
        .filter_map(|p| p.sign(&msg))
        .collect::<Vec<StmSig>>();

    let clerk = StmClerk::from_signer(&ps[0]);
    let avk = clerk.compute_avk();

    // Check all parties can verify every sig
    for (s, p) in sigs.iter().zip(ps.iter()) {
        assert!(s.verify(&params, &p.verification_key(), &p.get_stake(), &avk, &msg).is_ok(), "Verification
        failed");
    }

    // Aggregate with random parties
    let msig = clerk.aggregate(&sigs, &msg);

    match msig {
        Ok(aggr) => {
            println!("Aggregate ok");
            assert!(aggr.verify(&msg, &clerk.compute_avk(), &params).is_ok());
        }
        Err(AggregationError::NotEnoughSignatures(n, k)) => {
            println!("Not enough signatures");
            assert!(n < params.k && k == params.k)
        }
        Err(AggregationError::UsizeConversionInvalid) => {
            println!("Invalid usize conversion");
        }
    }
}

§Benchmarks

Here we give the benchmark results of STM for size and time. We run the benchmarks on macOS 12.6 on an Apple M1 Pro machine with 16 GB of RAM.

Note that the size of an individual signature with one valid index is 72 bytes (48 bytes from sigma, 8 bytes from party_index, 8 bytes for the length of winning indices and at least 8 bytes for a single winning index) and increases linearly in the length of valid indices (where an index is 8 bytes).

+----------------------+
| Size of benchmarks   |
+----------------------+
| Results obtained by using the parameters suggested by the paper.
+----------------------+
+----------------------+
| Aggregate signatures |
+----------------------+
+----------------------+
| Hash: Blake2b 512    |
+----------------------+
k = 445 | m = 2728 | nr parties = 3000; 118760 bytes
+----------------------+
| Hash: Blake2b 256    |
+----------------------+
k = 445 | m = 2728 | nr parties = 3000; 99384 bytes
+----------------------+
+----------------------+
| Aggregate signatures |
+----------------------+
| Hash: Blake2b 512    |
+----------------------+
k = 554 | m = 3597 | nr parties = 3000; 133936 bytes
+----------------------+
| Hash: Blake2b 256    |
+----------------------+
k = 554 | m = 3597 | nr parties = 3000; 113728 bytes

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]

Implementation of Stake-based Threshold Multisignatures

Structs§

ClosedKeyReg: Structure generated out of a closed registration containing the registered parties, total stake, and the merkle tree. One can only get a global avk out of a closed key registration.
CoreVerifier: Full node verifier including the list of eligible signers and the total stake of the system.
KeyReg: Struct that collects public keys and stakes of parties. Each participant (both the signers and the clerks) need to run their own instance of the key registration.
ProofOfPossession: MultiSig proof of possession, which contains two elements from G1. However, the two elements have different types: k1 is represented as a BlstSig as it has the same structure, and this facilitates its verification. On the other hand, k2 is a G1 point, as it does not share structure with the BLS signature, and we need to have an ad-hoc verification mechanism.
Signature: MultiSig signature, which is a wrapper over the BlstSig type.
SigningKey: MultiSig secret key, which is a wrapper over the BlstSk type from the blst library.
StmAggrSig: 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.
StmAggrVerificationKey: 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.
StmClerk: StmClerk can verify and aggregate StmSigs and verify StmMultiSigs. Clerks can only be generated with the registration closed. This avoids that a Merkle Tree is computed before all parties have registered.
StmInitializer: Initializer for StmSigner. This is the data that is used during the key registration procedure. Once the latter is finished, this instance is consumed into an StmSigner.
StmParameters: Used to set protocol parameters.
StmSig: Signature created by a single party who has won the lottery.
StmSigRegParty: Signature with its registered party.
StmSigner: Participant in the protocol can sign messages.
VerificationKey: MultiSig verification key, which is a wrapper over the BlstVk (element in G2) from the blst library.
VerificationKeyPoP: MultiSig public key, contains the verification key and the proof of possession.

Enums§

AggregationError: Error types for aggregation.
CoreVerifierError: Errors which can be output by CoreVerifier.
RegisterError: Errors which can be outputted by key registration.
StmAggregateSignatureError: Errors which can be output by Mithril aggregate verification.
StmSignatureError: Errors which can be output by Mithril single signature verification.

Type Aliases§

Index: Quorum index for signatures. An aggregate signature (StmMultiSig) must have at least k unique indices.
Stake: The quantity of stake held by a party, represented as a u64.
StmVerificationKey: Wrapper of the MultiSignature Verification key
StmVerificationKeyPoP: Wrapper of the MultiSignature Verification key with proof of possession

Crate mithril_stmCopy item path