sp_consensus_sassafras/
ticket.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Primitives related to tickets.
19
20use crate::vrf::RingVrfSignature;
21use codec::{Decode, DecodeWithMemTracking, Encode, MaxEncodedLen};
22use scale_info::TypeInfo;
23
24pub use sp_core::ed25519::{Public as EphemeralPublic, Signature as EphemeralSignature};
25
26/// Ticket identifier.
27///
28/// Its value is the output of a VRF whose inputs cannot be controlled by the
29/// ticket's creator (refer to [`crate::vrf::ticket_id_input`] parameters).
30/// Because of this, it is also used as the ticket score to compare against
31/// the epoch ticket's threshold to decide if the ticket is worth being considered
32/// for slot assignment (refer to [`ticket_id_threshold`]).
33pub type TicketId = u128;
34
35/// Ticket data persisted on-chain.
36#[derive(
37	Debug, Clone, PartialEq, Eq, Encode, Decode, DecodeWithMemTracking, MaxEncodedLen, TypeInfo,
38)]
39pub struct TicketBody {
40	/// Attempt index.
41	pub attempt_idx: u32,
42	/// Ephemeral public key which gets erased when the ticket is claimed.
43	pub erased_public: EphemeralPublic,
44	/// Ephemeral public key which gets exposed when the ticket is claimed.
45	pub revealed_public: EphemeralPublic,
46}
47
48/// Ticket ring vrf signature.
49pub type TicketSignature = RingVrfSignature;
50
51/// Ticket envelope used on during submission.
52#[derive(
53	Debug, Clone, PartialEq, Eq, Encode, Decode, DecodeWithMemTracking, MaxEncodedLen, TypeInfo,
54)]
55pub struct TicketEnvelope {
56	/// Ticket body.
57	pub body: TicketBody,
58	/// Ring signature.
59	pub signature: TicketSignature,
60}
61
62/// Ticket claim information filled by the block author.
63#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode, MaxEncodedLen, TypeInfo)]
64pub struct TicketClaim {
65	/// Signature verified via `TicketBody::erased_public`.
66	pub erased_signature: EphemeralSignature,
67}
68
69/// Computes a boundary for [`TicketId`] maximum allowed value for a given epoch.
70///
71/// Only ticket identifiers below this threshold should be considered as candidates
72/// for slot assignment.
73///
74/// The value is computed as `TicketId::MAX*(redundancy*slots)/(attempts*validators)`
75///
76/// Where:
77/// - `redundancy`: redundancy factor;
78/// - `slots`: number of slots in epoch;
79/// - `attempts`: max number of tickets attempts per validator;
80/// - `validators`: number of validators in epoch.
81///
82/// If `attempts * validators = 0` then we return 0.
83///
84/// For details about the formula and implications refer to
85/// [*probabilities an parameters*](https://research.web3.foundation/Polkadot/protocols/block-production/SASSAFRAS#probabilities-and-parameters)
86/// paragraph of the w3f introduction to the protocol.
87// TODO: replace with [RFC-26](https://github.com/polkadot-fellows/RFCs/pull/26)
88// "Tickets Threshold" paragraph once is merged
89pub fn ticket_id_threshold(
90	redundancy: u32,
91	slots: u32,
92	attempts: u32,
93	validators: u32,
94) -> TicketId {
95	let num = redundancy as u64 * slots as u64;
96	let den = attempts as u64 * validators as u64;
97	TicketId::max_value()
98		.checked_div(den.into())
99		.unwrap_or_default()
100		.saturating_mul(num.into())
101}
102
103#[cfg(test)]
104mod tests {
105	use super::*;
106
107	// This is a trivial example/check which just better explain explains the rationale
108	// behind the threshold.
109	//
110	// After this reading the formula should become obvious.
111	#[test]
112	fn ticket_id_threshold_trivial_check() {
113		// For an epoch with `s` slots we want to accept a number of tickets equal to ~s·r
114		let redundancy = 2;
115		let slots = 1000;
116		let attempts = 100;
117		let validators = 500;
118
119		let threshold = ticket_id_threshold(redundancy, slots, attempts, validators);
120		let threshold = threshold as f64 / TicketId::MAX as f64;
121
122		// We expect that the total number of tickets allowed to be submitted
123		// is slots*redundancy
124		let avt = ((attempts * validators) as f64 * threshold) as u32;
125		assert_eq!(avt, slots * redundancy);
126
127		println!("threshold: {}", threshold);
128		println!("avt = {}", avt);
129	}
130}
sp_consensus_sassafras/ticket.rs

sp_consensus_sassafras/
ticket.rs
