casper_types/block/
rewarded_signatures.rs

1use alloc::{collections::BTreeSet, vec::Vec};
2
3use crate::{
4    bytesrepr::{self, Bytes, FromBytes, ToBytes},
5    PublicKey,
6};
7
8#[cfg(feature = "datasize")]
9use datasize::DataSize;
10#[cfg(feature = "json-schema")]
11use schemars::JsonSchema;
12
13use serde::{Deserialize, Serialize};
14use tracing::error;
15
16/// Describes finality signatures that will be rewarded in a block. Consists of a vector of
17/// `SingleBlockRewardedSignatures`, each of which describes signatures for a single ancestor
18/// block. The first entry represents the signatures for the parent block, the second for the
19/// parent of the parent, and so on.
20#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default, Serialize, Deserialize)]
21#[cfg_attr(feature = "datasize", derive(DataSize))]
22#[cfg_attr(feature = "json-schema", derive(JsonSchema))]
23pub struct RewardedSignatures(Vec<SingleBlockRewardedSignatures>);
24
25/// List of identifiers for finality signatures for a particular past block.
26///
27/// That past block height is current_height - signature_rewards_max_delay, the latter being defined
28/// in the chainspec.
29///
30/// We need to wait for a few blocks to pass (`signature_rewards_max_delay`) to store the finality
31/// signers because we need a bit of time to get the block finality.
32#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default, Serialize, Deserialize)]
33#[cfg_attr(feature = "datasize", derive(DataSize))]
34#[cfg_attr(feature = "json-schema", derive(JsonSchema))]
35pub struct SingleBlockRewardedSignatures(Vec<u8>);
36
37impl SingleBlockRewardedSignatures {
38    /// Creates a new set of recorded finality signaures from the era's validators +
39    /// the list of validators which signed.
40    pub fn from_validator_set<'a>(
41        public_keys: &BTreeSet<PublicKey>,
42        all_validators: impl IntoIterator<Item = &'a PublicKey>,
43    ) -> Self {
44        // Take the validators list
45        // Replace the ones who signed with 1 and the ones who didn't with 0
46        // Pack everything into bytes
47        let result = Self::pack(
48            all_validators
49                .into_iter()
50                .map(|key| u8::from(public_keys.contains(key))),
51        );
52
53        let included_count: u32 = result.0.iter().map(|c| c.count_ones()).sum();
54        if included_count as usize != public_keys.len() {
55            error!(
56                included_count,
57                expected_count = public_keys.len(),
58                "error creating past finality signatures from validator set"
59            );
60        }
61
62        result
63    }
64
65    /// Gets the list of validators which signed from a set of recorded finality signaures (`self`)
66    /// + the era's validators.
67    pub fn to_validator_set(
68        &self,
69        all_validators: impl IntoIterator<Item = PublicKey>,
70    ) -> BTreeSet<PublicKey> {
71        self.unpack()
72            .zip(all_validators)
73            .filter_map(|(active, validator)| (active != 0).then_some(validator))
74            .collect()
75    }
76
77    /// Packs the bits to bytes, to create a `PastFinalitySignature`
78    /// from an iterator of bits.
79    ///
80    /// If a value is neither 1 nor 0, it is interpreted as a 1.
81    #[doc(hidden)]
82    pub fn pack(bits: impl Iterator<Item = u8>) -> Self {
83        //use itertools::Itertools;
84
85        fn set_bit_at(value: u8, position: usize) -> u8 {
86            // Sanitize the value (must be 0 or 1):
87            let value = u8::from(value != 0);
88
89            value << (7 - position)
90        }
91
92        let inner = chunks_8(bits)
93            .map(|bits_chunk| {
94                bits_chunk
95                    .enumerate()
96                    .fold(0, |acc, (pos, value)| acc | set_bit_at(value, pos))
97            })
98            .collect();
99
100        SingleBlockRewardedSignatures(inner)
101    }
102
103    /// Unpacks the bytes to bits,
104    /// to get a human readable representation of `PastFinalitySignature`.
105    #[doc(hidden)]
106    pub fn unpack(&self) -> impl Iterator<Item = u8> + '_ {
107        // Returns the bit at the given position (0 or 1):
108        fn bit_at(byte: u8, position: u8) -> u8 {
109            (byte & (0b1000_0000 >> position)) >> (7 - position)
110        }
111
112        self.0
113            .iter()
114            .flat_map(|&byte| (0..8).map(move |i| bit_at(byte, i)))
115    }
116
117    /// Calculates the set difference of two instances of `SingleBlockRewardedSignatures`.
118    #[doc(hidden)]
119    pub fn difference(mut self, other: &SingleBlockRewardedSignatures) -> Self {
120        for (self_byte, other_byte) in self.0.iter_mut().zip(other.0.iter()) {
121            *self_byte &= !other_byte;
122        }
123        self
124    }
125
126    /// Calculates the set intersection of two instances of `SingleBlockRewardedSignatures`.
127    pub fn intersection(mut self, other: &SingleBlockRewardedSignatures) -> Self {
128        self.0 = self
129            .0
130            .iter()
131            .zip(other.0.iter())
132            .map(|(a, b)| *a & *b)
133            .collect();
134        self
135    }
136
137    /// Returns `true` if the set contains at least one signature.
138    pub fn has_some(&self) -> bool {
139        self.0.iter().any(|byte| *byte != 0)
140    }
141}
142
143impl ToBytes for SingleBlockRewardedSignatures {
144    fn to_bytes(&self) -> Result<Vec<u8>, bytesrepr::Error> {
145        let mut buffer = bytesrepr::allocate_buffer(self)?;
146        buffer.extend(Bytes::from(self.0.as_ref()).to_bytes()?);
147        Ok(buffer)
148    }
149
150    fn serialized_length(&self) -> usize {
151        self.0.serialized_length()
152    }
153}
154
155impl FromBytes for SingleBlockRewardedSignatures {
156    fn from_bytes(bytes: &[u8]) -> Result<(Self, &[u8]), bytesrepr::Error> {
157        let (inner, rest) = Bytes::from_bytes(bytes)?;
158        Ok((SingleBlockRewardedSignatures(inner.into()), rest))
159    }
160}
161
162impl RewardedSignatures {
163    /// Creates a new instance of `RewardedSignatures`.
164    pub fn new<I: IntoIterator<Item = SingleBlockRewardedSignatures>>(
165        single_block_signatures: I,
166    ) -> Self {
167        Self(single_block_signatures.into_iter().collect())
168    }
169
170    /// Creates an instance of `RewardedSignatures` based on its unpacked (one byte per validator)
171    /// representation.
172    pub fn pack(unpacked: Vec<Vec<u8>>) -> Self {
173        Self(
174            unpacked
175                .into_iter()
176                .map(|single_block_signatures| {
177                    SingleBlockRewardedSignatures::pack(single_block_signatures.into_iter())
178                })
179                .collect(),
180        )
181    }
182
183    /// Creates an unpacked (one byte per validator) representation of the finality signatures to
184    /// be rewarded in this block.
185    pub fn unpack(&self) -> Vec<Vec<u8>> {
186        self.0
187            .iter()
188            .map(|single_block_signatures| single_block_signatures.unpack().collect())
189            .collect()
190    }
191
192    /// Returns this instance of `RewardedSignatures` with `num_blocks` of empty signatures
193    /// prepended.
194    pub fn left_padded(self, num_blocks: usize) -> Self {
195        Self(
196            core::iter::repeat_with(SingleBlockRewardedSignatures::default)
197                .take(num_blocks)
198                .chain(self.0)
199                .collect(),
200        )
201    }
202
203    /// Calculates the set difference between two instances of `RewardedSignatures`.
204    pub fn difference(self, other: &RewardedSignatures) -> Self {
205        Self(
206            self.0
207                .into_iter()
208                .zip(other.0.iter())
209                .map(|(single_block_signatures, other_block_signatures)| {
210                    single_block_signatures.difference(other_block_signatures)
211                })
212                .collect(),
213        )
214    }
215
216    /// Calculates the set intersection between two instances of `RewardedSignatures`.
217    pub fn intersection(&self, other: &RewardedSignatures) -> Self {
218        Self(
219            self.0
220                .iter()
221                .zip(other.0.iter())
222                .map(|(single_block_signatures, other_block_signatures)| {
223                    single_block_signatures
224                        .clone()
225                        .intersection(other_block_signatures)
226                })
227                .collect(),
228        )
229    }
230
231    /// Iterates over the `SingleBlockRewardedSignatures` for each rewarded block.
232    pub fn iter(&self) -> impl Iterator<Item = &SingleBlockRewardedSignatures> {
233        self.0.iter()
234    }
235
236    /// Iterates over the `SingleBlockRewardedSignatures`, yielding the signatures together with
237    /// the block height for each entry. `block_height` is the height of the block that contains
238    /// this instance of `RewardedSignatures`.
239    pub fn iter_with_height(
240        &self,
241        block_height: u64,
242    ) -> impl Iterator<Item = (u64, &SingleBlockRewardedSignatures)> {
243        self.0.iter().enumerate().map(move |(rel_height, sbrs)| {
244            (
245                block_height
246                    .saturating_sub(rel_height as u64)
247                    .saturating_sub(1),
248                sbrs,
249            )
250        })
251    }
252
253    /// Returns `true` if there is at least one cited signature.
254    pub fn has_some(&self) -> bool {
255        self.0.iter().any(|signatures| signatures.has_some())
256    }
257}
258
259pub(crate) static EMPTY: RewardedSignatures = RewardedSignatures(Vec::new());
260
261impl ToBytes for RewardedSignatures {
262    fn to_bytes(&self) -> Result<Vec<u8>, bytesrepr::Error> {
263        self.0.to_bytes()
264    }
265
266    fn serialized_length(&self) -> usize {
267        self.0.serialized_length()
268    }
269}
270
271impl FromBytes for RewardedSignatures {
272    fn from_bytes(bytes: &[u8]) -> Result<(Self, &[u8]), bytesrepr::Error> {
273        Vec::<SingleBlockRewardedSignatures>::from_bytes(bytes)
274            .map(|(inner, rest)| (RewardedSignatures(inner), rest))
275    }
276}
277
278/// Chunks an iterator over `u8`s into pieces of maximum size of 8.
279fn chunks_8(bits: impl Iterator<Item = u8>) -> impl Iterator<Item = impl Iterator<Item = u8>> {
280    struct Chunks<B>(B);
281
282    struct Chunk {
283        values: [u8; 8],
284        index: usize,
285        max: usize,
286    }
287
288    impl<B> Iterator for Chunks<B>
289    where
290        B: Iterator<Item = u8>,
291    {
292        type Item = Chunk;
293
294        fn next(&mut self) -> Option<Self::Item> {
295            let mut values = [0; 8];
296            let max = core::iter::zip(&mut values, &mut self.0)
297                .map(|(array_slot, value)| *array_slot = value)
298                .count();
299
300            (max != 0).then_some(Chunk {
301                values,
302                max,
303                index: 0,
304            })
305        }
306    }
307
308    impl Iterator for Chunk {
309        type Item = u8;
310
311        fn next(&mut self) -> Option<Self::Item> {
312            if self.index < self.max {
313                let n = self.values.get(self.index).cloned();
314                self.index += 1;
315                n
316            } else {
317                None
318            }
319        }
320    }
321
322    Chunks(bits)
323}
324
325#[cfg(any(feature = "testing", test))]
326impl SingleBlockRewardedSignatures {
327    /// Returns random data.
328    pub fn random(rng: &mut crate::testing::TestRng, n_validators: usize) -> Self {
329        let mut bytes = vec![0; (n_validators + 7) / 8];
330
331        rand::RngCore::fill_bytes(rng, bytes.as_mut());
332
333        SingleBlockRewardedSignatures(bytes)
334    }
335}
336
337#[cfg(test)]
338mod tests {
339    use super::{chunks_8, SingleBlockRewardedSignatures};
340    use crate::{
341        bytesrepr::{FromBytes, ToBytes},
342        testing::TestRng,
343        PublicKey,
344    };
345    use rand::{seq::IteratorRandom, Rng};
346    use std::collections::BTreeSet;
347
348    #[test]
349    fn empty_signatures() {
350        let rng = &mut TestRng::new();
351        let validators: Vec<_> = std::iter::repeat_with(|| PublicKey::random(rng))
352            .take(7)
353            .collect();
354        let original_signed = BTreeSet::new();
355
356        let past_finality_signatures =
357            SingleBlockRewardedSignatures::from_validator_set(&original_signed, validators.iter());
358
359        assert_eq!(past_finality_signatures.0, &[0]);
360
361        let signed = past_finality_signatures.to_validator_set(validators);
362
363        assert_eq!(original_signed, signed);
364    }
365
366    #[test]
367    fn from_and_to_methods_match_in_a_simple_case() {
368        let rng = &mut TestRng::new();
369        let validators: Vec<_> = std::iter::repeat_with(|| PublicKey::random(rng))
370            .take(11)
371            .collect();
372        let signed = {
373            let mut signed = BTreeSet::new();
374            signed.insert(validators[2].clone());
375            signed.insert(validators[5].clone());
376            signed.insert(validators[6].clone());
377            signed.insert(validators[8].clone());
378            signed.insert(validators[10].clone());
379            signed
380        };
381
382        let past_finality_signatures =
383            SingleBlockRewardedSignatures::from_validator_set(&signed, validators.iter());
384
385        assert_eq!(past_finality_signatures.0, &[0b0010_0110, 0b1010_0000]);
386
387        let signed_ = past_finality_signatures.to_validator_set(validators);
388
389        assert_eq!(signed, signed_);
390    }
391
392    #[test]
393    fn simple_serialization_roundtrip() {
394        let data = SingleBlockRewardedSignatures(vec![1, 2, 3, 4, 5]);
395
396        let serialized = data.to_bytes().unwrap();
397        assert_eq!(serialized.len(), data.0.len() + 4);
398        assert_eq!(data.serialized_length(), data.0.len() + 4);
399
400        let (deserialized, rest) = SingleBlockRewardedSignatures::from_bytes(&serialized).unwrap();
401
402        assert_eq!(data, deserialized);
403        assert_eq!(rest, &[0u8; 0]);
404    }
405
406    #[test]
407    fn serialization_roundtrip_of_empty_data() {
408        let data = SingleBlockRewardedSignatures::default();
409
410        let serialized = data.to_bytes().unwrap();
411        assert_eq!(serialized, &[0; 4]);
412        assert_eq!(data.serialized_length(), 4);
413
414        let (deserialized, rest) = SingleBlockRewardedSignatures::from_bytes(&serialized).unwrap();
415
416        assert_eq!(data, deserialized);
417        assert_eq!(rest, &[0u8; 0]);
418    }
419
420    #[test]
421    fn serialization_roundtrip_of_random_data() {
422        let rng = &mut TestRng::new();
423        let n_validators = rng.gen_range(50..200);
424        let all_validators: BTreeSet<_> = std::iter::repeat_with(|| PublicKey::random(rng))
425            .take(n_validators)
426            .collect();
427        let n_to_sign = rng.gen_range(0..all_validators.len());
428        let public_keys = all_validators
429            .iter()
430            .cloned()
431            .choose_multiple(rng, n_to_sign)
432            .into_iter()
433            .collect();
434
435        let past_finality_signatures =
436            SingleBlockRewardedSignatures::from_validator_set(&public_keys, all_validators.iter());
437
438        let serialized = past_finality_signatures.to_bytes().unwrap();
439        let (deserialized, rest) = SingleBlockRewardedSignatures::from_bytes(&serialized).unwrap();
440
441        assert_eq!(public_keys, deserialized.to_validator_set(all_validators));
442        assert_eq!(rest, &[0u8; 0]);
443    }
444
445    #[test]
446    fn chunk_iterator() {
447        fn v(maybe_chunk: Option<impl Iterator<Item = u8>>) -> Option<Vec<u8>> {
448            maybe_chunk.map(itertools::Itertools::collect_vec)
449        }
450
451        // Empty chunks:
452
453        let mut chunks = chunks_8(IntoIterator::into_iter([]));
454
455        assert_eq!(v(chunks.next()), None);
456
457        // Exact size chunk:
458
459        let mut chunks = chunks_8(IntoIterator::into_iter([10, 11, 12, 13, 14, 15, 16, 17]));
460
461        assert_eq!(v(chunks.next()), Some(vec![10, 11, 12, 13, 14, 15, 16, 17]));
462        assert_eq!(v(chunks.next()), None);
463
464        // Chunks with a remainder:
465
466        let mut chunks = chunks_8(IntoIterator::into_iter([
467            10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
468        ]));
469
470        assert_eq!(v(chunks.next()), Some(vec![10, 11, 12, 13, 14, 15, 16, 17]));
471        assert_eq!(v(chunks.next()), Some(vec![18, 19, 20, 21, 22, 23, 24, 25]));
472        assert_eq!(v(chunks.next()), Some(vec![26]));
473    }
474}
casper_types/block/rewarded_signatures.rs

casper_types/block/
rewarded_signatures.rs
