Double-Spend Protection

Double-Spend Protection via Nullifiers

This document describes the nullifier-based double-spend protection mechanism in the Roru Protocol.

Overview

Problem

Prevent the same note from being spent multiple times while maintaining privacy.

Solution

Nullifiers provide a privacy-preserving way to mark notes as spent without revealing which note was spent.

Nullifier System

Nullifier Definition

Nullifier Structure:

pub struct Nullifier {
    pub hash: Hash,  // 32-byte hash
}

Nullifier Generation

Generation Formula:

nullifier = Hash(commitment || nullifier_key || position)

Generation Code:

fn generate_nullifier(
    note_commitment: &Commitment,
    nullifier_key: &Scalar,
    position: u32,
) -> Nullifier {
    let input = [
        note_commitment.as_bytes(),
        nullifier_key.as_bytes(),
        position.to_le_bytes(),
    ].concat();
    
    Nullifier {
        hash: hash(input),
    }
}

Nullifier Properties

Uniqueness

Property: Each nullifier is unique

Guarantee:

• Different notes produce different nullifiers

• Same note always produces same nullifier

• No collisions (cryptographically)

Unlinkability

Property: Cannot link nullifier to note

Guarantee:

• Nullifier doesn't reveal commitment

• Cannot determine which note was spent

• Privacy-preserving

Determinism

Property: Same inputs always produce same nullifier

Guarantee:

• Reproducible generation

• Consistent verification

• No randomness in nullifier

Nullifier Set

Set Structure

Nullifier Set:

pub struct NullifierSet {
    pub nullifiers: HashSet<Nullifier>,
    pub tree: SparseMerkleTree,  // Optional: for efficient proofs
}

Set Operations

Insertion:

fn insert_nullifier(set: &mut NullifierSet, nullifier: Nullifier) {
    set.nullifiers.insert(nullifier);
    if let Some(tree) = &mut set.tree {
        tree.insert(nullifier.hash);
    }
}

Lookup:

fn contains_nullifier(set: &NullifierSet, nullifier: &Nullifier) -> bool {
    set.nullifiers.contains(nullifier)
}

Double-Spend Detection

Detection Process

Detection Steps:

1. Generate nullifier for note

2. Check if nullifier exists in set

3. If exists: reject transaction (double-spend)

4. If not: allow transaction

Detection Code:

fn check_double_spend(
    nullifier: &Nullifier,
    nullifier_set: &NullifierSet,
) -> Result<()> {
    if nullifier_set.contains_nullifier(nullifier) {
        return Err(Error::DoubleSpend);
    }
    Ok(())
}

Transaction Flow

Spending Process

Spending Steps:

1. Select note to spend

2. Generate nullifier

3. Check nullifier not in set

4. Create transaction with nullifier

5. After verification: add nullifier to set

Spending Code:

fn spend_note(
    note: &Note,
    nullifier_key: &Scalar,
    nullifier_set: &NullifierSet,
) -> Result<Nullifier> {
    let nullifier = generate_nullifier(
        &note.commitment,
        nullifier_key,
        note.position,
    );
    
    // Check for double-spend
    check_double_spend(&nullifier, nullifier_set)?;
    
    Ok(nullifier)
}

Nullifier Verification

Verification in Proof

Proof Circuit:

• Proves nullifier generated correctly

• Proves nullifier not in set

• Hides note information

• Validates generation

Circuit Constraints:

// Nullifier generation constraint
let computed_nullifier = hash(commitment || nullifier_key || position);
assert!(computed_nullifier == nullifier);

// Double-spend check (public input)
assert!(!nullifier_set.contains(nullifier));

Sparse Merkle Tree

Tree Structure

Tree for Nullifiers:

• Sparse Merkle tree

• Only non-empty nodes stored

• Efficient proofs

• Fast lookups

Tree Implementation:

pub struct NullifierTree {
    pub tree: SparseMerkleTree<Hash>,
    pub root: Hash,
}

Tree Operations

Insertion:

fn insert_nullifier(tree: &mut NullifierTree, nullifier: &Nullifier) {
    tree.tree.insert(nullifier.hash);
    tree.root = tree.tree.root();
}

Proof Generation:

fn prove_not_in_set(
    tree: &NullifierTree,
    nullifier: &Nullifier,
) -> MerkleProof {
    tree.tree.generate_proof(nullifier.hash)
}

Batch Operations

Batch Nullification

Batch Process:

1. Generate nullifiers for all inputs

2. Check all not in set

3. Batch insert after verification

Batch Code:

fn batch_check_nullifiers(
    nullifiers: &[Nullifier],
    nullifier_set: &NullifierSet,
) -> Result<()> {
    for nullifier in nullifiers {
        if nullifier_set.contains_nullifier(nullifier) {
            return Err(Error::DoubleSpend);
        }
    }
    Ok(())
}

Performance

Efficiency

Operations:

• Generation: O(1)

• Lookup: O(1) with hash set

• Insertion: O(1)

• Proof: O(log n) with tree

Storage:

• Nullifier: 32 bytes

• Set: O(n) where n is number of spent notes

• Tree: O(n log n) but sparse

Security

Security Properties

Cryptographic Security:

• Based on hash function security

• Collision resistance

• Preimage resistance

Privacy Security:

• Nullifiers don't reveal notes

• Unlinkable to commitments

• No information leakage

Threat Model

Protected Against:

• Double-spending

• Replay attacks

• Nullifier forgery

Security Assumptions:

• Secure hash function

• Secure nullifier keys

• Correct implementation

Edge Cases

Concurrent Transactions

Handling:

• Lock nullifier set during verification

• Sequential processing

• Conflict detection

Network Partitions

Handling:

• Eventual consistency

• Conflict resolution

• State reconciliation

Conclusion

Nullifier-based protection provides:

• Security: Prevents double-spending

• Privacy: Doesn't reveal spent notes

• Efficiency: Fast operations

• Scalability: Handles large sets

• Reliability: Cryptographically secure

Understanding nullifiers is essential for transaction security.