use core::fmt::{Display, Formatter};
use core::str::FromStr;
use num_enum::{IntoPrimitive, TryFromPrimitive};
use crate::encoding::{EncodingProfile, ErasureCode, ProfileError};
use crate::erasure::MAX_GROUP_SIZE;
#[repr(u64)]
#[derive(Clone, Copy, Debug, Eq, IntoPrimitive, PartialEq, TryFromPrimitive)]
pub enum TrustModel {
Permissionless = 1,
Trusted = 2,
}
impl Display for TrustModel {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
match self {
Self::Permissionless => write!(f, "permissionless"),
Self::Trusted => write!(f, "trusted"),
}
}
}
impl FromStr for TrustModel {
type Err = ThresholdError;
fn from_str(text: &str) -> Result<Self, ThresholdError> {
match text.trim() {
"permissionless" => Ok(Self::Permissionless),
"trusted" => Ok(Self::Trusted),
_ => Err(ThresholdError::TrustModel),
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum ThresholdError {
Width(u64),
Recovery { n: u64, k: u64 },
Profile(ProfileError),
PermissionlessRecovery { n: u64, k: u64, limit: u64 },
TrustModel,
}
impl Display for ThresholdError {
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
match self {
Self::Width(n) => write!(f, "group size {n} is outside 1..={MAX_GROUP_SIZE}"),
Self::Recovery { n, k } => write!(f, "recovery count {k} is outside 1..={n}"),
Self::Profile(error) => write!(f, "{error}"),
Self::PermissionlessRecovery { n, k, limit } => write!(
f,
"a permissionless network of {n} recovers from at most {limit}, got {k}"
),
Self::TrustModel => write!(f, "expected permissionless or trusted"),
}
}
}
impl std::error::Error for ThresholdError {}
impl From<ProfileError> for ThresholdError {
fn from(error: ProfileError) -> Self {
Self::Profile(error)
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Thresholds {
pub certify: u64,
pub invalidate: u64,
pub evict: u64,
pub snapshot: u64,
pub assignment: u64,
pub synced: u64,
}
impl Thresholds {
pub fn try_new(trust: TrustModel, n: u64, k: u64) -> Result<Self, ThresholdError> {
if n == 0 || n > MAX_GROUP_SIZE as u64 {
return Err(ThresholdError::Width(n));
}
if k == 0 || k > n {
return Err(ThresholdError::Recovery { n, k });
}
match trust {
TrustModel::Permissionless => Ok(Self::permissionless(n, k)),
TrustModel::Trusted => Ok(Self::trusted(k)),
}
}
fn permissionless(n: u64, k: u64) -> Self {
let quorum = supermajority(n);
let honest = max_faulty(n) + 1;
Self {
certify: quorum,
invalidate: quorum,
evict: quorum,
snapshot: honest,
assignment: honest,
synced: k.max(honest),
}
}
fn trusted(k: u64) -> Self {
Self {
certify: k,
invalidate: k,
evict: k,
snapshot: k,
assignment: k,
synced: k,
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct NetworkParams {
pub profile: ErasureCode,
pub trust: TrustModel,
pub thresholds: Thresholds,
}
impl NetworkParams {
pub fn try_new(profile: ErasureCode, trust: TrustModel) -> Result<Self, ThresholdError> {
let thresholds =
Thresholds::try_new(trust, u64::from(profile.n()), u64::from(profile.k()))?;
Ok(Self { profile, trust, thresholds })
}
pub fn n(&self) -> usize {
usize::from(self.profile.n())
}
pub fn k(&self) -> usize {
usize::from(self.profile.k())
}
}
pub fn validate_profile(
trust: TrustModel,
profile: EncodingProfile,
) -> Result<ErasureCode, ThresholdError> {
let code = ErasureCode::try_from(profile)?;
let n = u64::from(code.n());
let k = u64::from(code.k());
let limit = max_faulty(n) + 1;
if trust == TrustModel::Permissionless && k > limit {
return Err(ThresholdError::PermissionlessRecovery { n, k, limit });
}
Ok(code)
}
const fn max_faulty(n: u64) -> u64 {
(n - 1) / 3
}
const fn supermajority(n: u64) -> u64 {
(2 * n + 3) / 3
}
#[cfg(test)]
mod tests {
use super::*;
use crate::encoding::{ClayParams, RSParams, RepParams, TAPENET_PROFILE};
const WIDTHS: std::ops::RangeInclusive<u64> = 1..=MAX_GROUP_SIZE as u64;
#[test]
fn tapenet() {
let thresholds = Thresholds::try_new(TrustModel::Permissionless, 20, 7).expect("tapenet");
assert_eq!(
thresholds,
Thresholds {
certify: 14,
invalidate: 14,
evict: 14,
snapshot: 7,
assignment: 7,
synced: 7,
},
);
}
#[test]
fn permissionless_counts() {
for n in WIDTHS {
for k in 1..=n {
let thresholds = Thresholds::try_new(TrustModel::Permissionless, n, k).expect("valid");
let quorum = thresholds.certify;
let faulty = n - quorum;
assert!(3 * quorum > 2 * n);
assert!(3 * (quorum - 1) <= 2 * n);
assert_eq!(faulty, max_faulty(n));
assert_eq!(
thresholds,
Thresholds {
certify: quorum,
invalidate: quorum,
evict: quorum,
snapshot: faulty + 1,
assignment: faulty + 1,
synced: k.max(faulty + 1),
},
);
}
}
}
#[test]
fn trusted_counts() {
for n in WIDTHS {
for k in 1..=n {
let thresholds = Thresholds::try_new(TrustModel::Trusted, n, k).expect("valid");
assert_eq!(
thresholds,
Thresholds {
certify: k,
invalidate: k,
evict: k,
snapshot: k,
assignment: k,
synced: k,
},
);
}
}
}
#[test]
fn bad_width() {
let wide = MAX_GROUP_SIZE as u64 + 1;
for trust in [TrustModel::Permissionless, TrustModel::Trusted] {
assert_eq!(Thresholds::try_new(trust, 0, 1), Err(ThresholdError::Width(0)));
assert_eq!(Thresholds::try_new(trust, wide, 7), Err(ThresholdError::Width(wide)));
}
}
#[test]
fn bad_recovery() {
for trust in [TrustModel::Permissionless, TrustModel::Trusted] {
assert_eq!(
Thresholds::try_new(trust, 4, 0),
Err(ThresholdError::Recovery { n: 4, k: 0 }),
);
assert_eq!(
Thresholds::try_new(trust, 4, 5),
Err(ThresholdError::Recovery { n: 4, k: 5 }),
);
}
}
#[test]
fn zero_model() {
assert!(TrustModel::try_from(0u64).is_err());
assert_eq!(TrustModel::try_from(1u64), Ok(TrustModel::Permissionless));
assert_eq!(TrustModel::try_from(2u64), Ok(TrustModel::Trusted));
assert!(TrustModel::try_from(3u64).is_err());
}
#[test]
fn model_text() {
for trust in [TrustModel::Permissionless, TrustModel::Trusted] {
assert_eq!(trust.to_string().parse(), Ok(trust));
}
assert_eq!("open".parse::<TrustModel>(), Err(ThresholdError::TrustModel));
}
#[test]
fn tapenet_profile() {
let above = EncodingProfile::clay(ClayParams::new(20, 8, 16));
assert_eq!(
validate_profile(TrustModel::Permissionless, TAPENET_PROFILE.into()),
Ok(TAPENET_PROFILE),
);
assert_eq!(
validate_profile(TrustModel::Permissionless, above),
Err(ThresholdError::PermissionlessRecovery { n: 20, k: 8, limit: 7 }),
);
}
#[test]
fn recovery_rule() {
for n in 2..=MAX_GROUP_SIZE as u8 {
let certify = Thresholds::try_new(TrustModel::Permissionless, u64::from(n), 1)
.expect("valid")
.certify;
let limit = u64::from(n) + 1 - certify;
for k in 1..n {
let profile = EncodingProfile::reed_solomon(RSParams::new(k, n - k));
let is_accepted = validate_profile(TrustModel::Permissionless, profile).is_ok();
assert_eq!(is_accepted, u64::from(k) <= limit, "n {n} k {k}");
}
}
}
#[test]
fn trusted_profiles() {
let profiles = [
EncodingProfile::reed_solomon(RSParams::new(3, 1)),
EncodingProfile::reed_solomon(RSParams::new(4, 2)),
EncodingProfile::clay(ClayParams::new(10, 7, 9)),
EncodingProfile::replication(RepParams::new(1)),
EncodingProfile::replication(RepParams::new(2)),
];
for profile in profiles {
assert!(validate_profile(TrustModel::Trusted, profile).is_ok());
}
assert!(validate_profile(TrustModel::Permissionless, profiles[0]).is_err());
}
#[test]
fn bad_profile() {
let cases = [
(EncodingProfile::unknown(), ProfileError::UnknownEncoding),
(EncodingProfile::reed_solomon(RSParams::new(4, 0)), ProfileError::Recovery),
(EncodingProfile::clay(ClayParams::new(20, 7, 7)), ProfileError::Helpers),
(EncodingProfile::replication(RepParams::new(21)), ProfileError::Width),
];
for trust in [TrustModel::Permissionless, TrustModel::Trusted] {
for (profile, error) in cases {
assert_eq!(validate_profile(trust, profile), Err(ThresholdError::Profile(error)));
}
}
}
}