Code shared from the Rust Playground

playground.rs

//! Generalizing Cryptographic Reductions and the Forking Lemma in Pure Rust.
//! This implementation relies strictly on the standard library.

use std::collections::HashMap;
use std::cell::RefCell;

// =========================================================================
// 1. Core Mathematical Abstractions (Prime Field & Mock Curve)
// =========================================================================

/// A primitive Mock Field element / Scalar under modulo N.
/// For simplicity of this proof simulation, we use a small prime N.
const GROUP_ORDER: u64 = 1000003;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Scalar(pub u64);

impl Scalar {
    pub fn add(self, other: Scalar) -> Scalar {
        Scalar((self.0 + other.0) % GROUP_ORDER)
    }

    pub fn sub(self, other: Scalar) -> Scalar {
        Scalar((GROUP_ORDER + self.0 - other.0) % GROUP_ORDER)
    }

    pub fn mul(self, other: Scalar) -> Scalar {
        Scalar((self.0 * other.0) % GROUP_ORDER)
    }

    /// Extended Euclidean Algorithm for modular inverse
    pub fn invert(self) -> Option<Scalar> {
        if self.0 == 0 { return None; }
        let (mut a, mut m, mut x0, mut x1) = (self.0 as i64, GROUP_ORDER as i64, 0i64, 1i64);
        while a > 1 {
            let q = a / m;
            let mut t = m;
            m = a % m;
            a = t;
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }
        if x1 < 0 { x1 += GROUP_ORDER as i64; }
        Some(Scalar(x1 as u64))
    }
}

/// Represents a Group Element (e.g., a Public Key P = xG).
/// In our generalized model, we simulate a cyclic group where Generator G = 1.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct GroupElement(pub u64);

impl GroupElement {
    pub fn generator() -> Self {
        GroupElement(1)
    }

    pub fn scale(scalar: Scalar) -> Self {
        GroupElement((GroupElement::generator().0 * scalar.0) % GROUP_ORDER)
    }

    pub fn add(self, other: GroupElement) -> Self {
        GroupElement((self.0 + other.0) % GROUP_ORDER)
    }
}

// =========================================================================
// 2. Defining the Hard Problem & The Adversary Traits
// =========================================================================

/// The Discrete Logarithm Problem (DLP) Challenge.
/// Given a `GroupElement` (Q), find the `Scalar` (q) such that Q = qG.
pub struct DlpChallenge {
    pub target: GroupElement,
}

/// Traits defining an Adversary capable of forging a Taproot-like signature.
/// A valid signature components in this generalized framework are a commitment scalar `R`
/// and a response scalar `s`.
#[derive(Debug, Clone, Copy)]
pub struct ForgerySignature {
    pub r_out: Scalar,
    pub s_out: Scalar,
}

/// The Adversary interface. The adversary interacts with a Random Oracle (the hash function)
/// to produce a forgery against a given public key challenge.
pub trait TaprootAdversary {
    fn execute<F>(&self, public_key: GroupElement, random_oracle: F) -> ForgerySignature
    where
        F: FnMut(Scalar) -> Scalar;
}

// =========================================================================
// 3. The Random Oracle Engine (Intermediary for Forking)
// =========================================================================

/// A programmable Random Oracle that lets a Simulator intercept, record,
/// and dynamically alter hash responses during execution.
pub struct RandomOracleSimulator {
    pub history: RefCell<Vec<Scalar>>,
    pub assigned_responses: RefCell<HashMap<Scalar, Scalar>>,
    pub fixed_responses: Vec<Scalar>,
}

impl RandomOracleSimulator {
    pub fn new(fixed_responses: Vec<Scalar>) -> Self {
        Self {
            history: RefCell::new(Vec::new()),
            assigned_responses: RefCell::new(HashMap::new()),
            fixed_responses,
        }
    }

    /// The mocking routing passed to the adversary
    pub fn query(&self, message: Scalar) -> Scalar {
        self.history.borrow_mut().push(message);
        
        let mut assigned = self.assigned_responses.borrow_mut();
        if let Some(&cached) = assigned.get(&message) {
            return cached;
        }

        // Pull from our pre-programmed list of responses if available
        let idx = assigned.len();
        let response = if idx < self.fixed_responses.len() {
            self.fixed_responses[idx]
        } else {
            Scalar(42) // Fallback static value
        };

        assigned.insert(message, response);
        response
    }
}

// =========================================================================
// 4. The Generalized Forking Lemma & Reduction Engine
// =========================================================================

/// The reduction engine. It implements the "Trap" that takes an adversary
/// and forces them to solve the hard DLP challenge.
pub struct ReductionEngine;

impl ReductionEngine {
    /// Reduces the Discrete Logarithm Problem to a Taproot Forgery Attack.
    /// This function acts as the Simulator described in cryptographic proofs.
    pub fn solve_dlp<A: TaprootAdversary>(challenge: DlpChallenge, adversary: A) -> Result<Scalar, &'static str> {
        // --- RUN 1 ---
        // Setup a random oracle sequence for the first run
        let oracle_run_1 = RandomOracleSimulator::new(vec![Scalar(5005), Scalar(9009)]);
        
        // Treat the target DLP challenge key Q directly as our Tweaked Public Key P'
        let tweaked_pubkey = challenge.target;

        // Execute the adversary up to their forgery state
        let forgery_1 = adversary.execute(tweaked_pubkey, |msg| oracle_run_1.query(msg));

        // Locate the point where the adversary committed to the hash challenge
        let histories_1 = oracle_run_1.history.borrow().clone();
        if histories_1.is_empty() {
            return Err("Adversary did not query the Random Oracle; cannot fork.");
        }
        
        // Find the specific critical query message that bound the signature to the hash
        let critical_query = histories_1[0]; 
        let hash_challenge_1 = *oracle_run_1.assigned_responses.borrow().get(&critical_query).unwrap();

        // --- RUN 2 (The Fork) ---
        // We rewind time. We change the response to the critical query to a *new* challenge value.
        let hash_challenge_2 = Scalar(7777); // Divergent hash response
        let oracle_run_2 = RandomOracleSimulator::new(vec![hash_challenge_2, Scalar(9009)]);
        
        // Force the adversary to execute again under identical setup but a modified hash response
        let forgery_2 = adversary.execute(tweaked_pubkey, |msg| oracle_run_2.query(msg));

        // --- ALGEBRAIC CANCELLATION ---
        // From Run 1: s1 = r + e1 * q
        // From Run 2: s2 = r + e2 * q
        // Implies:    (s1 - s2) = q * (e1 - e2)
        // Implies:    q = (s1 - s2) / (e1 - e2)
        
        let s_diff = forgery_1.s_out.sub(forgery_2.s_out);
        let e_diff = hash_challenge_1.sub(hash_challenge_2);

        let e_diff_inv = e_diff.invert().ok_or("Modular inverse failed; division by zero.")?;
        let private_key = s_diff.mul(e_diff_inv);

        // Verify the extraction is mathematically correct against the original hard challenge
        if GroupElement::scale(private_key) == challenge.target {
            Ok(private_key)
        } else {
            Err("Reduction extracted an invalid scalar.")
        }
    }
}

// =========================================================================
// 5. Instantiating a Mock Adversary to Validate the System
// =========================================================================

/// A mock adversary that successfully cheats if given an oracle, 
/// unknowingly exposing itself to the Forking Lemma reduction trap.
pub struct MockAdversary {
    pub secret_nonce_r: Scalar,
}

// Fixed line 209: Removed 'fallthrough' keyword mistake
impl TaprootAdversary for MockAdversary {
    fn execute<F>(&self, public_key: GroupElement, mut random_oracle: F) -> ForgerySignature
    where
        F: FnMut(Scalar) -> Scalar,
    {
        // 1. Commit to a temporary cryptographic point
        let r_out = self.secret_nonce_r;
        
        // 2. Query the oracle using the public key and data configuration
        let e_challenge = random_oracle(Scalar(public_key.0));

        // 3. Craft a forgery assuming knowledge of a hidden secret relation
        // Real-world adversaries use mathematical cleverness; here we model the output relations
        // Forgery verification identity: sG = R + eQ. 
        // Assuming hidden private relation q = 555 for the mock.
        let hidden_q = Scalar(555); 
        let s_out = r_out.add(e_challenge.mul(hidden_q));

        ForgerySignature { r_out, s_out }
    }
}

// =========================================================================
// 6. Execution Driver
// =========================================================================

fn main() {
    println!("--- Initializing Generalized Reduction Setup ---");

    // Define a hard Discrete Logarithm Problem challenge: 
    // Given Q = GroupElement(555), extract the hidden scalar '555' via the Generator.
    let hidden_solution = Scalar(555);
    let challenge = DlpChallenge {
        target: GroupElement::scale(hidden_solution),
    };
    
    println!("DLP Challenge Target Public Key Point: {:?}", challenge.target);

    // Instantiate our target attacker engine
    let adversary = MockAdversary {
        secret_nonce_r: Scalar(12345), // Static internal state for the deterministic adversary
    };

    println!("\nExecuting Forking Lemma simulation inside the Reduction Engine...");
    
    match ReductionEngine::solve_dlp(challenge, adversary) {
        Ok(extracted_secret) => {
            println!("-------------------------------------------------------");
            println!("SUCCESS: Forking Lemma Reduction Extracted Secret Successfully!");
            println!("Extracted Secret Scalar: Solution = {}", extracted_secret.0);
            println!("Matches Original Target: {}", extracted_secret.0 == hidden_solution.0);
            println!("-------------------------------------------------------");
        }
        Err(e) => {
            println!("Reduction failed: {}", e);
        }
    }
}