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 digest::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        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        Self::check(qc_vp, message, qc)?;
182
183        let signer_pks: Vec<_> = qc_vp
184            .stake_entries
185            .iter()
186            .zip(signers.iter())
187            .filter(|(_, b)| **b)
188            .map(|(pk, _)| pk.stake_key.clone())
189            .collect();
190        Ok(signer_pks)
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use jf_signature::{
197        bls_over_bn254::{BLSOverBN254CurveSignatureScheme, KeyPair},
198        SignatureScheme,
199    };
200    use vbs::{version::StaticVersion, BinarySerializer, Serializer};
201
202    use super::*;
203    type Version = StaticVersion<0, 1>;
204
205    macro_rules! test_quorum_certificate {
206        ($aggsig:tt) => {
207            let mut rng = jf_utils::test_rng();
208            let agg_sig_pp = $aggsig::param_gen(Some(&mut rng)).unwrap();
209            let key_pair1 = KeyPair::generate(&mut rng);
210            let key_pair2 = KeyPair::generate(&mut rng);
211            let key_pair3 = KeyPair::generate(&mut rng);
212            let entry1 = StakeTableEntry {
213                stake_key: key_pair1.ver_key(),
214                stake_amount: U256::from(3u8),
215            };
216            let entry2 = StakeTableEntry {
217                stake_key: key_pair2.ver_key(),
218                stake_amount: U256::from(5u8),
219            };
220            let entry3 = StakeTableEntry {
221                stake_key: key_pair3.ver_key(),
222                stake_amount: U256::from(7u8),
223            };
224            let qc_pp = QcParams {
225                stake_entries: &[entry1, entry2, entry3],
226                threshold: U256::from(10u8),
227                agg_sig_pp,
228            };
229            let msg = [72u8; 32];
230            let sig1 =
231                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair1.sign_key_ref(), &msg, &mut rng)
232                    .unwrap();
233            let sig2 =
234                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair2.sign_key_ref(), &msg, &mut rng)
235                    .unwrap();
236            let sig3 =
237                BitVectorQc::<$aggsig>::sign(&agg_sig_pp, key_pair3.sign_key_ref(), &msg, &mut rng)
238                    .unwrap();
239
240            // happy path
241            let signers = bitvec![0, 1, 1];
242            let qc = BitVectorQc::<$aggsig>::assemble(
243                &qc_pp,
244                signers.as_bitslice(),
245                &[sig2.clone(), sig3.clone()],
246            )
247            .unwrap();
248            assert!(BitVectorQc::<$aggsig>::check(&qc_pp, &msg.into(), &qc).is_ok());
249            assert_eq!(
250                BitVectorQc::<$aggsig>::trace(&qc_pp, &msg.into(), &qc).unwrap(),
251                vec![key_pair2.ver_key(), key_pair3.ver_key()],
252            );
253
254            // Check the QC and the QcParams can be serialized / deserialized
255            assert_eq!(
256                qc,
257                Serializer::<Version>::deserialize(&Serializer::<Version>::serialize(&qc).unwrap())
258                    .unwrap()
259            );
260
261            // bad paths
262            // number of signatures unmatch
263            assert!(BitVectorQc::<$aggsig>::assemble(
264                &qc_pp,
265                signers.as_bitslice(),
266                &[sig2.clone()]
267            )
268            .is_err());
269            // total weight under threshold
270            let active_bad = bitvec![1, 1, 0];
271            assert!(BitVectorQc::<$aggsig>::assemble(
272                &qc_pp,
273                active_bad.as_bitslice(),
274                &[sig1.clone(), sig2.clone()]
275            )
276            .is_err());
277            // wrong bool vector length
278            let active_bad_2 = bitvec![0, 1, 1, 0];
279            assert!(BitVectorQc::<$aggsig>::assemble(
280                &qc_pp,
281                active_bad_2.as_bitslice(),
282                &[sig2, sig3],
283            )
284            .is_err());
285
286            assert!(BitVectorQc::<$aggsig>::check(
287                &qc_pp,
288                &msg.into(),
289                &(qc.0.clone(), active_bad)
290            )
291            .is_err());
292            assert!(BitVectorQc::<$aggsig>::check(
293                &qc_pp,
294                &msg.into(),
295                &(qc.0.clone(), active_bad_2)
296            )
297            .is_err());
298            let bad_msg = [70u8; 32];
299            assert!(BitVectorQc::<$aggsig>::check(&qc_pp, &bad_msg.into(), &qc).is_err());
300
301            let bad_sig = &sig1;
302            assert!(
303                BitVectorQc::<$aggsig>::check(&qc_pp, &msg.into(), &(bad_sig.clone(), qc.1))
304                    .is_err()
305            );
306        };
307    }
308    #[test]
309    fn test_quorum_certificate() {
310        test_quorum_certificate!(BLSOverBN254CurveSignatureScheme);
311    }
312}
hotshot_types/qc.rs

hotshot_types/
qc.rs
