byzantine_quorum.rs

byzantine_quorum.rs

use std::collections::HashMap;
use rand::{seq::SliceRandom, thread_rng};

// --- BQS Constants ---
// Maximum number of Byzantine faults (f or b) the system can tolerate.
const F: u32 = 4;

// The required supermajority count for a client to accept a value as correct.
// A value is only considered valid if F + 1 servers report it, allowing the
// client to mask 'F' colluding malicious responses. 
const SUPERMAJORITY_THRESHOLD: u32 = F + 1;

// Minimum theoretical servers for MQS existence: N >= 4f + 1 
const N_MIN: u32 = 4 * F + 1;

// --- Data Structures ---

/// Represents the replicated data item, consisting of a value and a version/timestamp.
/// Hash, Eq, PartialEq, and Clone are required for use as a key in the HashMap (clustering).
#[derive(Clone, Eq, Hash, PartialEq)]
struct ValueTimePair {
    value: String,
    timestamp: u64,
}

/// Represents the raw data received from a single server in the quorum.

struct ServerResponse {
    server_id: u32,
    data: ValueTimePair,
}

// --- Mock Quorum Access Simulation ---

/// Simulates reading from a quorum of servers, including malicious responses.
/// Servers are randomly assigned roles based on the fault tolerance F.
fn mock_quorum_access(
    quorum_size: u32,
    correct_state: ValueTimePair,
) -> Vec<ServerResponse> {
    let mut responses = Vec::new();

    // 1. Define malicious state (attempting to mislead with a higher timestamp)
    let malicious_state = ValueTimePair {
        value: "Fabricated_Y_Corrupted".to_string(),
        timestamp: 200, // Higher than correct_state.timestamp (100)
    };

    // 2. Assign Server Roles and Generate Responses
    let mut server_ids: Vec<u32> = (1..=quorum_size).collect();
    server_ids.shuffle(&mut thread_rng());

    for (i, id) in server_ids.into_iter().enumerate() {
        // We designate the first F servers in the shuffled list as Byzantine
        let is_byzantine = (i as u32) < F;

        let response_data = if is_byzantine {
            // F servers (up to 4) are Byzantine and collude
            malicious_state.clone()
        } else {
            // The remaining servers are correct (must be F+1 or more)
            correct_state.clone()
        };

        responses.push(ServerResponse {
            server_id: id,
            data: response_data,
        });
    }

    responses
}

// --- Core BQS Protocol Implementation ---

/// Implements the client's critical read operation, applying the Byzantine masking rule.
///
/// This function executes the F+1 supermajority validation to mask arbitrary failures. 
fn byzantine_read_protocol(responses: Vec<ServerResponse>) -> Option<ValueTimePair> {
    // 1. Clustering: Group responses by the identical ValueTimePair and count occurrences.
    let mut cluster_counts: HashMap<ValueTimePair, u32> = HashMap::new();

    for response in responses {
        // Use the value/timestamp pair as the key for clustering
        *cluster_counts.entry(response.data).or_insert(0) += 1;
    }

    // 2. Supermajority Validation and 3. Result Determination:
    // Filter for validated pairs and find the one with the highest timestamp.
    let mut definitive_result: Option<ValueTimePair> = None;

    for (pair, count) in cluster_counts.into_iter() {
        // Check against the F+1 supermajority threshold 
        if count >= SUPERMAJORITY_THRESHOLD {
            // This pair is reported by enough servers to mask 'F' Byzantine failures.
            // Select the validated pair with the highest timestamp as the definitive result.
            let is_latest = definitive_result.as_ref()
            .map_or(true, |current| pair.timestamp > current.timestamp);

            if is_latest {
                definitive_result = Some(pair);
            }
        }
    }

    definitive_result
}

// --- Demonstration ---

fn main() {
    // We simulate a quorum large enough to guarantee F+1 correct responses
    const QUORUM_SIZE: u32 = F + SUPERMAJORITY_THRESHOLD; // F=4, Thresh=5, Size=9
    let correct_state = ValueTimePair { value: "True_Data_A".to_string(), timestamp: 100 };

    println!("--- Byzantine Quorum System (MQS) Simulation ---");
    println!("Max Byzantine Faults (F): {}", F);
    println!("Supermajority Threshold (F + 1): {}", SUPERMAJORITY_THRESHOLD);
    println!("Simulated Quorum Size: {}", QUORUM_SIZE);
    println!("--------------------------------------------------");


    // 1. Simulate Quorum Access (Collect responses)
    let responses = mock_quorum_access(QUORUM_SIZE, correct_state.clone());

    let correct_count = responses.iter().filter(|r| r.data == correct_state).count() as u32;
    let malicious_count = responses.len() as u32 - correct_count;

    println!("Simulation Details:");
    println!("- Total Responses Collected: {}", responses.len());
    println!("- Malicious Reports (Servers <= F): {} (Timestamp 200)", malicious_count);
    println!("- Correct Reports (Servers > F): {} (Timestamp 100)", correct_count);


    // 2. Execute Byzantine Read Protocol (Masking and Validation)
    let result = byzantine_read_protocol(responses);

    // 3. Report Result
    match result {
        Some(pair) => {
            println!("\n✅ Byzantine Read Protocol Result:");
            println!("\tValue: {}", pair.value);
            println!("\tTimestamp: {}", pair.timestamp);

            if pair == correct_state {
                println!("\nConclusion: The correct state was successfully masked because {} servers reported it, meeting the F+1 threshold. The {} colluding Byzantine servers were ignored.", correct_count, malicious_count);
            } else {
                println!("\nConclusion: Failure! The client was misled by the malicious responses.");
            }
        }
        None => println!("\n❌ Byzantine Read Protocol Result: No value reached the F+1 supermajority threshold."),
    }
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=dd03989c46d5ae4982c9f8418c94dcb9