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 { acc + entry.stake_amount } else { acc }
92                    },
93                );
94        if total_weight < qc_pp.threshold {
95            return Err(SignatureError::ParameterError(format!(
96                "total_weight {} less than threshold {}",
97                total_weight, qc_pp.threshold,
98            )));
99        }
100        let mut ver_keys = vec![];
101        for (entry, b) in qc_pp.stake_entries.iter().zip(signers.iter()) {
102            if *b {
103                ver_keys.push(entry.stake_key.clone());
104            }
105        }
106        if ver_keys.len() != sigs.len() {
107            return Err(SignatureError::ParameterError(format!(
108                "the number of ver_keys {} != the number of partial signatures {}",
109                ver_keys.len(),
110                sigs.len(),
111            )));
112        }
113        let sig = A::aggregate(&qc_pp.agg_sig_pp, &ver_keys[..], sigs)?;
114
115        Ok((sig, signers.into()))
116    }
117
118    fn check(
119        qc_vp: &Self::QcVerifierParams<'_>,
120        message: &GenericArray<A::MessageUnit, Self::MessageLength>,
121        qc: &Self::Qc,
122    ) -> Result<Self::QuorumSize, SignatureError> {
123        let (sig, signers) = qc;
124        if signers.len() != qc_vp.stake_entries.len() {
125            return Err(SignatureError::ParameterError(format!(
126                "signers bit vector len {} != the number of stake entries {}",
127                signers.len(),
128                qc_vp.stake_entries.len(),
129            )));
130        }
131        let total_weight: U256 =
132            qc_vp
133                .stake_entries
134                .iter()
135                .zip(signers.iter())
136                .fold(
137                    U256::ZERO,
138                    |acc, (entry, b)| {
139                        if *b { acc + entry.stake_amount } else { acc }
140                    },
141                );
142        if total_weight < qc_vp.threshold {
143            return Err(SignatureError::ParameterError(format!(
144                "total_weight {} less than threshold {}",
145                total_weight, qc_vp.threshold,
146            )));
147        }
148        let mut ver_keys = vec![];
149        for (entry, b) in qc_vp.stake_entries.iter().zip(signers.iter()) {
150            if *b {
151                ver_keys.push(entry.stake_key.clone());
152            }
153        }
154        A::multi_sig_verify(&qc_vp.agg_sig_pp, &ver_keys[..], message, sig)?;
155
156        Ok(total_weight)
157    }
158
159    fn trace(
160        qc_vp: &Self::QcVerifierParams<'_>,
161        message: &GenericArray<<A>::MessageUnit, Self::MessageLength>,
162        qc: &Self::Qc,
163    ) -> Result<Vec<<A>::VerificationKey>, SignatureError> {
164        Self::check(qc_vp, message, qc)?;
165        Self::signers(qc_vp, qc)
166    }
167
168    fn signers(
169        qc_vp: &Self::QcVerifierParams<'_>,
170        qc: &Self::Qc,
171    ) -> Result<Vec<<A>::VerificationKey>, SignatureError> {
172        let (_sig, signers) = qc;
173        if signers.len() != qc_vp.stake_entries.len() {
174            return Err(SignatureError::ParameterError(format!(
175                "signers bit vector len {} != the number of stake entries {}",
176                signers.len(),
177                qc_vp.stake_entries.len(),
178            )));
179        }
180
181        let signer_pks: Vec<_> = qc_vp
182            .stake_entries
183            .iter()
184            .zip(signers.iter())
185            .filter(|(_, b)| **b)
186            .map(|(pk, _)| pk.stake_key.clone())
187            .collect();
188        Ok(signer_pks)
189    }
190}
191
192#[cfg(test)]
193mod tests {
194    use jf_signature::{
195        SignatureScheme,
196        bls_over_bn254::{BLSOverBN254CurveSignatureScheme, KeyPair},
197    };
198    use vbs::{BinarySerializer, Serializer, version::StaticVersion};
199
200    use super::*;
201    type Version = StaticVersion<0, 1>;
202
203    macro_rules! test_quorum_certificate {
204        ($aggsig:tt) => {
205            let mut rng = jf_utils::test_rng();
206            let agg_sig_pp = $aggsig::param_gen(Some(&mut rng)).unwrap();
207            let key_pair1 = KeyPair::generate(&mut rng);
208            let key_pair2 = KeyPair::generate(&mut rng);
209            let key_pair3 = KeyPair::generate(&mut rng);
210            let entry1 = StakeTableEntry {
211                stake_key: key_pair1.ver_key(),
212                stake_amount: U256::from(3u8),
213            };
214            let entry2 = StakeTableEntry {
215                stake_key: key_pair2.ver_key(),
216                stake_amount: U256::from(5u8),
217            };
218            let entry3 = StakeTableEntry {
219                stake_key: key_pair3.ver_key(),
220                stake_amount: U256::from(7u8),
221            };
222            let qc_pp = QcParams {
223                stake_entries: &[entry1, entry2, entry3],
224                threshold: U256::from(10u8),
225                agg_sig_pp,
226            };
227            let msg = [72u8; 32];
228            let sig1 =
229                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair1.sign_key_ref(), &msg, &mut rng)
230                    .unwrap();
231            let sig2 =
232                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair2.sign_key_ref(), &msg, &mut rng)
233                    .unwrap();
234            let sig3 =
235                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair3.sign_key_ref(), &msg, &mut rng)
236                    .unwrap();
237
238            // happy path
239            let signers = bitvec![0, 1, 1];
240            let qc = BitVectorQc::<$aggsig>::assemble(
241                &qc_pp,
242                signers.as_bitslice(),
243                &[sig2.clone(), sig3.clone()],
244            )
245            .unwrap();
246            assert!(BitVectorQc::<$aggsig>::check(&qc_pp, &msg.into(), &qc).is_ok());
247            assert_eq!(
248                BitVectorQc::<$aggsig>::trace(&qc_pp, &msg.into(), &qc).unwrap(),
249                vec![key_pair2.ver_key(), key_pair3.ver_key()],
250            );
251
252            // Check the QC and the QcParams can be serialized / deserialized
253            assert_eq!(
254                qc,
255                Serializer::<Version>::deserialize(&Serializer::<Version>::serialize(&qc).unwrap())
256                    .unwrap()
257            );
258
259            // bad paths
260            // number of signatures unmatch
261            assert!(BitVectorQc::<$aggsig>::assemble(
262                &qc_pp,
263                signers.as_bitslice(),
264                std::slice::from_ref(&sig2)
265            )
266            .is_err());
267            // total weight under threshold
268            let active_bad = bitvec![1, 1, 0];
269            assert!(BitVectorQc::<$aggsig>::assemble(
270                &qc_pp,
271                active_bad.as_bitslice(),
272                &[sig1.clone(), sig2.clone()]
273            )
274            .is_err());
275            // wrong bool vector length
276            let active_bad_2 = bitvec![0, 1, 1, 0];
277            assert!(BitVectorQc::<$aggsig>::assemble(
278                &qc_pp,
279                active_bad_2.as_bitslice(),
280                &[sig2, sig3],
281            )
282            .is_err());
283
284            assert!(BitVectorQc::<$aggsig>::check(
285                &qc_pp,
286                &msg.into(),
287                &(qc.0.clone(), active_bad)
288            )
289            .is_err());
290            assert!(BitVectorQc::<$aggsig>::check(
291                &qc_pp,
292                &msg.into(),
293                &(qc.0.clone(), active_bad_2)
294            )
295            .is_err());
296            let bad_msg = [70u8; 32];
297            assert!(BitVectorQc::<$aggsig>::check(&qc_pp, &bad_msg.into(), &qc).is_err());
298
299            let bad_sig = &sig1;
300            assert!(
301                BitVectorQc::<$aggsig>::check(&qc_pp, &msg.into(), &(bad_sig.clone(), qc.1))
302                    .is_err()
303            );
304        };
305    }
306    #[test]
307    fn test_quorum_certificate() {
308        test_quorum_certificate!(BLSOverBN254CurveSignatureScheme);
309    }
310
311    /// State returned by the [`three_node_setup`] helper.
312    struct ThreeNodeSetup {
313        key_pair1: KeyPair,
314        key_pair2: KeyPair,
315        key_pair3: KeyPair,
316        entries: Vec<
317            StakeTableEntry<<BLSOverBN254CurveSignatureScheme as SignatureScheme>::VerificationKey>,
318        >,
319        sig1: <BLSOverBN254CurveSignatureScheme as SignatureScheme>::Signature,
320        sig2: <BLSOverBN254CurveSignatureScheme as SignatureScheme>::Signature,
321        sig3: <BLSOverBN254CurveSignatureScheme as SignatureScheme>::Signature,
322    }
323
324    /// Helper that assembles a 3-node QC setup reused across signers tests.
325    ///
326    /// Callers build `QcParams { stake_entries: &setup.entries, threshold, agg_sig_pp: () }`
327    /// locally so that the borrow of `entries` stays within the caller's stack frame.
328    fn three_node_setup() -> ThreeNodeSetup {
329        let mut rng = jf_utils::test_rng();
330        let key_pair1 = KeyPair::generate(&mut rng);
331        let key_pair2 = KeyPair::generate(&mut rng);
332        let key_pair3 = KeyPair::generate(&mut rng);
333        let entries = vec![
334            StakeTableEntry {
335                stake_key: key_pair1.ver_key(),
336                stake_amount: U256::from(1u8),
337            },
338            StakeTableEntry {
339                stake_key: key_pair2.ver_key(),
340                stake_amount: U256::from(1u8),
341            },
342            StakeTableEntry {
343                stake_key: key_pair3.ver_key(),
344                stake_amount: U256::from(1u8),
345            },
346        ];
347        let msg = [42u8; 32];
348        let sig1 = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::sign(
349            &(),
350            key_pair1.sign_key_ref(),
351            msg,
352            &mut rng,
353        )
354        .unwrap();
355        let sig2 = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::sign(
356            &(),
357            key_pair2.sign_key_ref(),
358            msg,
359            &mut rng,
360        )
361        .unwrap();
362        let sig3 = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::sign(
363            &(),
364            key_pair3.sign_key_ref(),
365            msg,
366            &mut rng,
367        )
368        .unwrap();
369        ThreeNodeSetup {
370            key_pair1,
371            key_pair2,
372            key_pair3,
373            entries,
374            sig1,
375            sig2,
376            sig3,
377        }
378    }
379
380    #[test]
381    fn test_signers_extracts_correct_keys() {
382        let setup = three_node_setup();
383        let qc_pp = QcParams {
384            stake_entries: &setup.entries,
385            threshold: U256::from(2u8),
386            agg_sig_pp: (),
387        };
388        // Nodes 2 and 3 sign (bitvec [0, 1, 1])
389        let signers_bv = bitvec![0, 1, 1];
390        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
391            &qc_pp,
392            signers_bv.as_bitslice(),
393            &[setup.sig2, setup.sig3],
394        )
395        .unwrap();
396        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
397        assert_eq!(
398            result,
399            vec![setup.key_pair2.ver_key(), setup.key_pair3.ver_key()]
400        );
401    }
402
403    #[test]
404    fn test_signers_different_subset() {
405        let setup = three_node_setup();
406        let qc_pp = QcParams {
407            stake_entries: &setup.entries,
408            threshold: U256::from(2u8),
409            agg_sig_pp: (),
410        };
411        // Nodes 1 and 3 sign (bitvec [1, 0, 1])
412        let signers_bv = bitvec![1, 0, 1];
413        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
414            &qc_pp,
415            signers_bv.as_bitslice(),
416            &[setup.sig1, setup.sig3],
417        )
418        .unwrap();
419        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
420        assert_eq!(
421            result,
422            vec![setup.key_pair1.ver_key(), setup.key_pair3.ver_key()]
423        );
424    }
425
426    #[test]
427    fn test_signers_all_participants() {
428        let setup = three_node_setup();
429        let qc_pp = QcParams {
430            stake_entries: &setup.entries,
431            threshold: U256::from(2u8),
432            agg_sig_pp: (),
433        };
434        let signers_bv = bitvec![1, 1, 1];
435        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
436            &qc_pp,
437            signers_bv.as_bitslice(),
438            &[setup.sig1, setup.sig2, setup.sig3],
439        )
440        .unwrap();
441        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
442        assert_eq!(
443            result,
444            vec![
445                setup.key_pair1.ver_key(),
446                setup.key_pair2.ver_key(),
447                setup.key_pair3.ver_key()
448            ]
449        );
450    }
451
452    #[test]
453    fn test_signers_no_participants() {
454        // signers() does NOT check the threshold - it just reads the bitvec.
455        // We build the (sig, bitvec) tuple directly to avoid the threshold check in assemble().
456        let setup = three_node_setup();
457        let qc_pp = QcParams {
458            stake_entries: &setup.entries,
459            threshold: U256::from(2u8),
460            agg_sig_pp: (),
461        };
462        // Use sig1 as the dummy aggregated signature; signers() only reads the bitvec.
463        let empty_bv = bitvec![0, 0, 0];
464        let qc = (setup.sig1, empty_bv);
465        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
466        assert!(result.is_empty());
467    }
468
469    #[test]
470    fn test_signers_does_not_check_message() {
471        // signers() only reads the bitvec, it does NOT verify the message.
472        // So calling it with a QC assembled over message A but passing a different message is fine.
473        let setup = three_node_setup();
474        let qc_pp = QcParams {
475            stake_entries: &setup.entries,
476            threshold: U256::from(2u8),
477            agg_sig_pp: (),
478        };
479        let signers_bv = bitvec![0, 1, 1];
480        // Assemble QC over the "real" message (msg = [42u8; 32] from three_node_setup)
481        let qc = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::assemble(
482            &qc_pp,
483            signers_bv.as_bitslice(),
484            &[setup.sig2, setup.sig3],
485        )
486        .unwrap();
487        // signers() succeeds regardless of any message - it only reads the bitvec.
488        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc).unwrap();
489        assert_eq!(
490            result,
491            vec![setup.key_pair2.ver_key(), setup.key_pair3.ver_key()]
492        );
493    }
494
495    #[test]
496    fn test_signers_bitvec_length_mismatch() {
497        let setup = three_node_setup();
498        let qc_pp = QcParams {
499            stake_entries: &setup.entries,
500            threshold: U256::from(2u8),
501            agg_sig_pp: (),
502        };
503        // qc_pp has 3 stake entries but we create a QC with a bitvec of length 4.
504        let wrong_bv = bitvec![0, 1, 1, 0];
505        // Use sig1 as a plausible Signature value; signers() won't verify it.
506        let qc_bad = (setup.sig1, wrong_bv);
507        let result = BitVectorQc::<BLSOverBN254CurveSignatureScheme>::signers(&qc_pp, &qc_bad);
508        assert!(result.is_err());
509    }
510}
hotshot_types/qc.rs

hotshot_types/
qc.rs
