hotshot_types/
qc.rs

1// Copyright (c) 2021-2024 Espresso Systems (espressosys.com)
2// This file is part of the HotShot repository.
3
4// You should have received a copy of the MIT License
5// along with the HotShot repository. If not, see <https://mit-license.org/>.
6
7//! Implementation for `BitVectorQc` that uses BLS signature + Bit vector.
8//! See more details in hotshot paper.
9
10use alloy::primitives::U256;
11use ark_std::{
12    fmt::Debug,
13    format,
14    marker::PhantomData,
15    rand::{CryptoRng, RngCore},
16    vec,
17    vec::Vec,
18};
19use bitvec::prelude::*;
20use generic_array::GenericArray;
21use jf_signature::{AggregateableSignatureSchemes, SignatureError};
22use serde::{Deserialize, Serialize};
23use typenum::U32;
24
25use crate::{
26    stake_table::StakeTableEntry,
27    traits::{qc::QuorumCertificateScheme, signature_key::SignatureKey},
28};
29
30/// An implementation of QC using BLS signature and a bit-vector.
31#[derive(Serialize, Deserialize)]
32pub struct BitVectorQc<A: AggregateableSignatureSchemes + Serialize + for<'a> Deserialize<'a>>(
33    PhantomData<A>,
34);
35
36/// Public parameters of [`BitVectorQc`]
37#[derive(PartialEq, Debug, Clone, Hash)]
38pub struct QcParams<'a, K: SignatureKey, P> {
39    /// the stake table (snapshot) this QC is verified against
40    pub stake_entries: &'a [StakeTableEntry<K>],
41    /// threshold for the accumulated "weight" of votes to form a QC
42    pub threshold: U256,
43    /// public parameter for the aggregated signature scheme
44    pub agg_sig_pp: P,
45}
46
47impl<A> QuorumCertificateScheme<A> for BitVectorQc<A>
48where
49    A: AggregateableSignatureSchemes,
50    A::VerificationKey: SignatureKey,
51{
52    type QcProverParams<'a> = QcParams<'a, A::VerificationKey, A::PublicParameter>;
53
54    // TODO: later with SNARKs we'll use a smaller verifier parameter
55    type QcVerifierParams<'a> = QcParams<'a, A::VerificationKey, A::PublicParameter>;
56
57    type Qc = (A::Signature, BitVec);
58    type MessageLength = U32;
59    type QuorumSize = U256;
60
61    /// Sign a message with the signing key
62    fn sign<R: CryptoRng + RngCore, M: AsRef<[A::MessageUnit]>>(
63        pp: &A::PublicParameter,
64        sk: &A::SigningKey,
65        msg: M,
66        prng: &mut R,
67    ) -> Result<A::Signature, SignatureError> {
68        A::sign(pp, sk, msg, prng)
69    }
70
71    fn assemble(
72        qc_pp: &Self::QcProverParams<'_>,
73        signers: &BitSlice,
74        sigs: &[A::Signature],
75    ) -> Result<Self::Qc, SignatureError> {
76        if signers.len() != qc_pp.stake_entries.len() {
77            return Err(SignatureError::ParameterError(format!(
78                "bit vector len {} != the number of stake entries {}",
79                signers.len(),
80                qc_pp.stake_entries.len(),
81            )));
82        }
83        let total_weight: U256 =
84            qc_pp
85                .stake_entries
86                .iter()
87                .zip(signers.iter())
88                .fold(
89                    U256::ZERO,
90                    |acc, (entry, b)| {
91                        if *b {
92                            acc + entry.stake_amount
93                        } else {
94                            acc
95                        }
96                    },
97                );
98        if total_weight < qc_pp.threshold {
99            return Err(SignatureError::ParameterError(format!(
100                "total_weight {} less than threshold {}",
101                total_weight, qc_pp.threshold,
102            )));
103        }
104        let mut ver_keys = vec![];
105        for (entry, b) in qc_pp.stake_entries.iter().zip(signers.iter()) {
106            if *b {
107                ver_keys.push(entry.stake_key.clone());
108            }
109        }
110        if ver_keys.len() != sigs.len() {
111            return Err(SignatureError::ParameterError(format!(
112                "the number of ver_keys {} != the number of partial signatures {}",
113                ver_keys.len(),
114                sigs.len(),
115            )));
116        }
117        let sig = A::aggregate(&qc_pp.agg_sig_pp, &ver_keys[..], sigs)?;
118
119        Ok((sig, signers.into()))
120    }
121
122    fn check(
123        qc_vp: &Self::QcVerifierParams<'_>,
124        message: &GenericArray<A::MessageUnit, Self::MessageLength>,
125        qc: &Self::Qc,
126    ) -> Result<Self::QuorumSize, SignatureError> {
127        let (sig, signers) = qc;
128        if signers.len() != qc_vp.stake_entries.len() {
129            return Err(SignatureError::ParameterError(format!(
130                "signers bit vector len {} != the number of stake entries {}",
131                signers.len(),
132                qc_vp.stake_entries.len(),
133            )));
134        }
135        let total_weight: U256 =
136            qc_vp
137                .stake_entries
138                .iter()
139                .zip(signers.iter())
140                .fold(
141                    U256::ZERO,
142                    |acc, (entry, b)| {
143                        if *b {
144                            acc + entry.stake_amount
145                        } else {
146                            acc
147                        }
148                    },
149                );
150        if total_weight < qc_vp.threshold {
151            return Err(SignatureError::ParameterError(format!(
152                "total_weight {} less than threshold {}",
153                total_weight, qc_vp.threshold,
154            )));
155        }
156        let mut ver_keys = vec![];
157        for (entry, b) in qc_vp.stake_entries.iter().zip(signers.iter()) {
158            if *b {
159                ver_keys.push(entry.stake_key.clone());
160            }
161        }
162        A::multi_sig_verify(&qc_vp.agg_sig_pp, &ver_keys[..], message, sig)?;
163
164        Ok(total_weight)
165    }
166
167    fn trace(
168        qc_vp: &Self::QcVerifierParams<'_>,
169        message: &GenericArray<<A>::MessageUnit, Self::MessageLength>,
170        qc: &Self::Qc,
171    ) -> Result<Vec<<A>::VerificationKey>, SignatureError> {
172        Self::check(qc_vp, message, qc)?;
173        Self::signers(qc_vp, qc)
174    }
175
176    fn signers(
177        qc_vp: &Self::QcVerifierParams<'_>,
178        qc: &Self::Qc,
179    ) -> Result<Vec<<A>::VerificationKey>, SignatureError> {
180        let (_sig, signers) = qc;
181        if signers.len() != qc_vp.stake_entries.len() {
182            return Err(SignatureError::ParameterError(format!(
183                "signers bit vector len {} != the number of stake entries {}",
184                signers.len(),
185                qc_vp.stake_entries.len(),
186            )));
187        }
188
189        let signer_pks: Vec<_> = qc_vp
190            .stake_entries
191            .iter()
192            .zip(signers.iter())
193            .filter(|(_, b)| **b)
194            .map(|(pk, _)| pk.stake_key.clone())
195            .collect();
196        Ok(signer_pks)
197    }
198}
199
200#[cfg(test)]
201mod tests {
202    use jf_signature::{
203        bls_over_bn254::{BLSOverBN254CurveSignatureScheme, KeyPair},
204        SignatureScheme,
205    };
206    use vbs::{version::StaticVersion, BinarySerializer, Serializer};
207
208    use super::*;
209    type Version = StaticVersion<0, 1>;
210
211    macro_rules! test_quorum_certificate {
212        ($aggsig:tt) => {
213            let mut rng = jf_utils::test_rng();
214            let agg_sig_pp = $aggsig::param_gen(Some(&mut rng)).unwrap();
215            let key_pair1 = KeyPair::generate(&mut rng);
216            let key_pair2 = KeyPair::generate(&mut rng);
217            let key_pair3 = KeyPair::generate(&mut rng);
218            let entry1 = StakeTableEntry {
219                stake_key: key_pair1.ver_key(),
220                stake_amount: U256::from(3u8),
221            };
222            let entry2 = StakeTableEntry {
223                stake_key: key_pair2.ver_key(),
224                stake_amount: U256::from(5u8),
225            };
226            let entry3 = StakeTableEntry {
227                stake_key: key_pair3.ver_key(),
228                stake_amount: U256::from(7u8),
229            };
230            let qc_pp = QcParams {
231                stake_entries: &[entry1, entry2, entry3],
232                threshold: U256::from(10u8),
233                agg_sig_pp,
234            };
235            let msg = [72u8; 32];
236            let sig1 =
237                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair1.sign_key_ref(), &msg, &mut rng)
238                    .unwrap();
239            let sig2 =
240                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair2.sign_key_ref(), &msg, &mut rng)
241                    .unwrap();
242            let sig3 =
243                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair3.sign_key_ref(), &msg, &mut rng)
244                    .unwrap();
245
246            // happy path
247            let signers = bitvec![0, 1, 1];
248            let qc = BitVectorQc::<$aggsig>::assemble(
249                &qc_pp,
250                signers.as_bitslice(),
251                &[sig2.clone(), sig3.clone()],
252            )
253            .unwrap();
254            assert!(BitVectorQc::<$aggsig>::check(&qc_pp, &msg.into(), &qc).is_ok());
255            assert_eq!(
256                BitVectorQc::<$aggsig>::trace(&qc_pp, &msg.into(), &qc).unwrap(),
257                vec![key_pair2.ver_key(), key_pair3.ver_key()],
258            );
259
260            // Check the QC and the QcParams can be serialized / deserialized
261            assert_eq!(
262                qc,
263                Serializer::<Version>::deserialize(&Serializer::<Version>::serialize(&qc).unwrap())
264                    .unwrap()
265            );
266
267            // bad paths
268            // number of signatures unmatch
269            assert!(BitVectorQc::<$aggsig>::assemble(
270                &qc_pp,
271                signers.as_bitslice(),
272                std::slice::from_ref(&sig2)
273            )
274            .is_err());
275            // total weight under threshold
276            let active_bad = bitvec![1, 1, 0];
277            assert!(BitVectorQc::<$aggsig>::assemble(
278                &qc_pp,
279                active_bad.as_bitslice(),
280                &[sig1.clone(), sig2.clone()]
281            )
282            .is_err());
283            // wrong bool vector length
284            let active_bad_2 = bitvec![0, 1, 1, 0];
285            assert!(BitVectorQc::<$aggsig>::assemble(
286                &qc_pp,
287                active_bad_2.as_bitslice(),
288                &[sig2, sig3],
289            )
290            .is_err());
291
292            assert!(BitVectorQc::<$aggsig>::check(
293                &qc_pp,
294                &msg.into(),
295                &(qc.0.clone(), active_bad)
296            )
297            .is_err());
298            assert!(BitVectorQc::<$aggsig>::check(
299                &qc_pp,
300                &msg.into(),
301                &(qc.0.clone(), active_bad_2)
302            )
303            .is_err());
304            let bad_msg = [70u8; 32];
305            assert!(BitVectorQc::<$aggsig>::check(&qc_pp, &bad_msg.into(), &qc).is_err());
306
307            let bad_sig = &sig1;
308            assert!(
309                BitVectorQc::<$aggsig>::check(&qc_pp, &msg.into(), &(bad_sig.clone(), qc.1))
310                    .is_err()
311            );
312        };
313    }
314    #[test]
315    fn test_quorum_certificate() {
316        test_quorum_certificate!(BLSOverBN254CurveSignatureScheme);
317    }
318
319    /// State returned by the [`three_node_setup`] helper.
320    struct ThreeNodeSetup {
321        key_pair1: KeyPair,
322        key_pair2: KeyPair,
323        key_pair3: KeyPair,
324        entries: Vec<
325            StakeTableEntry<<BLSOverBN254CurveSignatureScheme as SignatureScheme>::VerificationKey>,
326        >,
327        sig1: <BLSOverBN254CurveSignatureScheme as SignatureScheme>::Signature,
328        sig2: <BLSOverBN254CurveSignatureScheme as SignatureScheme>::Signature,
329        sig3: <BLSOverBN254CurveSignatureScheme as SignatureScheme>::Signature,
330    }
331
332    /// Helper that assembles a 3-node QC setup reused across signers tests.
333    ///
334    /// Callers build `QcParams { stake_entries: &setup.entries, threshold, agg_sig_pp: () }`
335    /// locally so that the borrow of `entries` stays within the caller's stack frame.
336    fn three_node_setup() -> ThreeNodeSetup {
337        let mut rng = jf_utils::test_rng();
338        let key_pair1 = KeyPair::generate(&mut rng);
339        let key_pair2 = KeyPair::generate(&mut rng);
340        let key_pair3 = KeyPair::generate(&mut rng);
341        let entries = vec![
342            StakeTableEntry {
343                stake_key: key_pair1.ver_key(),
344                stake_amount: U256::from(1u8),
345            },
346            StakeTableEntry {
347                stake_key: key_pair2.ver_key(),
348                stake_amount: U256::from(1u8),
349            },
350            StakeTableEntry {
351                stake_key: key_pair3.ver_key(),
352                stake_amount: U256::from(1u8),
353            },
354        ];
355        let msg = [42u8; 32];
356        let sig1 = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::sign(
357            &(),
358            key_pair1.sign_key_ref(),
359            msg,
360            &mut rng,
361        )
362        .unwrap();
363        let sig2 = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::sign(
364            &(),
365            key_pair2.sign_key_ref(),
366            msg,
367            &mut rng,
368        )
369        .unwrap();
370        let sig3 = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::sign(
371            &(),
372            key_pair3.sign_key_ref(),
373            msg,
374            &mut rng,
375        )
376        .unwrap();
377        ThreeNodeSetup {
378            key_pair1,
379            key_pair2,
380            key_pair3,
381            entries,
382            sig1,
383            sig2,
384            sig3,
385        }
386    }
387
388    #[test]
389    fn test_signers_extracts_correct_keys() {
390        let setup = three_node_setup();
391        let qc_pp = QcParams {
392            stake_entries: &setup.entries,
393            threshold: U256::from(2u8),
394            agg_sig_pp: (),
395        };
396        // Nodes 2 and 3 sign (bitvec [0, 1, 1])
397        let signers_bv = bitvec![0, 1, 1];
398        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
399            &qc_pp,
400            signers_bv.as_bitslice(),
401            &[setup.sig2, setup.sig3],
402        )
403        .unwrap();
404        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
405        assert_eq!(
406            result,
407            vec![setup.key_pair2.ver_key(), setup.key_pair3.ver_key()]
408        );
409    }
410
411    #[test]
412    fn test_signers_different_subset() {
413        let setup = three_node_setup();
414        let qc_pp = QcParams {
415            stake_entries: &setup.entries,
416            threshold: U256::from(2u8),
417            agg_sig_pp: (),
418        };
419        // Nodes 1 and 3 sign (bitvec [1, 0, 1])
420        let signers_bv = bitvec![1, 0, 1];
421        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
422            &qc_pp,
423            signers_bv.as_bitslice(),
424            &[setup.sig1, setup.sig3],
425        )
426        .unwrap();
427        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
428        assert_eq!(
429            result,
430            vec![setup.key_pair1.ver_key(), setup.key_pair3.ver_key()]
431        );
432    }
433
434    #[test]
435    fn test_signers_all_participants() {
436        let setup = three_node_setup();
437        let qc_pp = QcParams {
438            stake_entries: &setup.entries,
439            threshold: U256::from(2u8),
440            agg_sig_pp: (),
441        };
442        let signers_bv = bitvec![1, 1, 1];
443        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
444            &qc_pp,
445            signers_bv.as_bitslice(),
446            &[setup.sig1, setup.sig2, setup.sig3],
447        )
448        .unwrap();
449        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
450        assert_eq!(
451            result,
452            vec![
453                setup.key_pair1.ver_key(),
454                setup.key_pair2.ver_key(),
455                setup.key_pair3.ver_key()
456            ]
457        );
458    }
459
460    #[test]
461    fn test_signers_no_participants() {
462        // signers() does NOT check the threshold - it just reads the bitvec.
463        // We build the (sig, bitvec) tuple directly to avoid the threshold check in assemble().
464        let setup = three_node_setup();
465        let qc_pp = QcParams {
466            stake_entries: &setup.entries,
467            threshold: U256::from(2u8),
468            agg_sig_pp: (),
469        };
470        // Use sig1 as the dummy aggregated signature; signers() only reads the bitvec.
471        let empty_bv = bitvec![0, 0, 0];
472        let qc = (setup.sig1, empty_bv);
473        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
474        assert!(result.is_empty());
475    }
476
477    #[test]
478    fn test_signers_does_not_check_message() {
479        // signers() only reads the bitvec, it does NOT verify the message.
480        // So calling it with a QC assembled over message A but passing a different message is fine.
481        let setup = three_node_setup();
482        let qc_pp = QcParams {
483            stake_entries: &setup.entries,
484            threshold: U256::from(2u8),
485            agg_sig_pp: (),
486        };
487        let signers_bv = bitvec![0, 1, 1];
488        // Assemble QC over the "real" message (msg = [42u8; 32] from three_node_setup)
489        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
490            &qc_pp,
491            signers_bv.as_bitslice(),
492            &[setup.sig2, setup.sig3],
493        )
494        .unwrap();
495        // signers() succeeds regardless of any message - it only reads the bitvec.
496        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
497        assert_eq!(
498            result,
499            vec![setup.key_pair2.ver_key(), setup.key_pair3.ver_key()]
500        );
501    }
502
503    #[test]
504    fn test_signers_bitvec_length_mismatch() {
505        let setup = three_node_setup();
506        let qc_pp = QcParams {
507            stake_entries: &setup.entries,
508            threshold: U256::from(2u8),
509            agg_sig_pp: (),
510        };
511        // qc_pp has 3 stake entries but we create a QC with a bitvec of length 4.
512        let wrong_bv = bitvec![0, 1, 1, 0];
513        // Use sig1 as a plausible Signature value; signers() won't verify it.
514        let qc_bad = (setup.sig1, wrong_bv);
515        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc_bad);
516        assert!(result.is_err());
517    }
518}
hotshot_types/qc.rs

hotshot_types/
qc.rs
