This repository contains complementary code for the OpenRank Litepaper, demonstrating a proof-of-concept implementation for decentralized reputation computation with fraud-proof mechanisms.

• Overview
• Architecture
• Project Structure
• Ranking Algorithms
  • EigenTrust
  • Hubs and Authorities (HITS)
• Verification Modes
  • Pessimistic Mode
  • Optimistic Mode
• Cryptographic Primitives
  • Poseidon Hash Function
  • Sparse Merkle Trees
  • Compute Trees
• Mathematical Foundations
  • Finite Field Arithmetic
  • Arbitrary Precision Rationals
  • Approximate Equality Verification
• Fraud Proof Mathematics
• Usage
• Dependencies
• License

OpenRank is a system for computing trust and reputation scores in a decentralized network. The key challenge is ensuring that off-chain computations can be verified on-chain efficiently without re-executing the entire algorithm.

This PoC demonstrates:

• Two ranking algorithms: EigenTrust and Hubs & Authorities
• Two verification paradigms: Pessimistic and Optimistic
• Cryptographic commitments using Poseidon hashes and Sparse Merkle Trees

┌──────────────────────────────────────────────────────────────────────────┐
│                           OpenRank System                                │
├──────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  ┌──────────────┐    ┌──────────────┐    ┌───────────────────────────┐   │
│  │  Algorithms  │    │ Compute Node │    │    Settlement Layer       │   │
│  ├──────────────┤    ├──────────────┤    ├───────────────────────────┤   │
│  │ • EigenTrust │───▶│ • Compute    │───▶│ • Smart Contract          │   │
│  │ • Hubs &     │    │   Trees      │    │ • Challenge/Response      │   │
│  │   Authorities│    │ • Proofs     │    │ • Fraud Proof Verification│   │
│  └──────────────┘    └──────────────┘    └───────────────────────────┘   │
│                              │                                           │
│                              ▼                                           │
│                    ┌──────────────────┐                                  │
│                    │  Cryptographic   │                                  │
│                    │   Primitives     │                                  │
│                    ├──────────────────┤                                  │
│                    │ • Poseidon Hash  │                                  │
│                    │ • Sparse Merkle  │                                  │
│                    │   Trees          │                                  │
│                    └──────────────────┘                                  │
│                                                                          │
└──────────────────────────────────────────────────────────────────────────┘

src/
├── main.rs                 # Entry point with example scenarios
├── algo/                   # Ranking algorithm implementations
│   ├── et_field.rs         # EigenTrust over finite fields
│   ├── et_rational.rs      # EigenTrust with arbitrary precision rationals
│   ├── h_and_a_field.rs    # HITS over finite fields
│   ├── h_and_a_float.rs    # HITS with floating point
│   └── h_and_a_rational.rs # HITS with arbitrary precision rationals
├── compute_node/           # Compute node implementation
│   ├── am_tree.rs          # Adjacency matrix tree
│   ├── compute_tree.rs     # Compute tree for score verification
│   └── mod.rs              # Compute node with proof generation
├── merkle_tree.rs          # Sparse Merkle Tree implementation
├── poseidon.rs             # Poseidon hash function
├── params/                 # Cryptographic parameters
│   └── poseidon_bn254_5x5.rs # Poseidon parameters for BN254
├── settlement.rs           # Smart contract simulation
└── systems/                # System modes
    ├── optimistic.rs       # Optimistic fraud-proof protocol
    └── pessimistic.rs      # Pessimistic full verification

EigenTrust is a reputation system designed for peer-to-peer networks where trust is propagated transitively. The core idea is that if Alice trusts Bob, and Bob trusts Carol, then Alice should have some indirect trust in Carol.

1. Local Trust Matrix: Each peer i assigns a local trust value lt[i][j] to peer j, representing how much i trusts j based on direct interactions.

2. Normalization: Local trust values are normalized so each row sums to 1:

   c[i][j] = lt[i][j] / Σₖ lt[i][k]
   

3. Iterative Computation: Global trust scores are computed iteratively:

   t⁽ᵏ⁺¹⁾[i] = Σⱼ c[j][i] · t⁽ᵏ⁾[j]
   

   In matrix form: t⁽ᵏ⁺¹⁾ = Cᵀ · t⁽ᵏ⁾

4. Convergence: The algorithm runs until scores converge (typically 20-30 iterations).

5. Pre-trust: Initial scores can be seeded with pre-trusted peers to bootstrap the system.

• Convergence: Under mild conditions, the iteration converges to the principal eigenvector of Cᵀ
• Normalization: Final scores sum to 1, representing a probability distribution over peers
• Sybil Resistance: Malicious peers cannot inflate their scores without receiving trust from honest peers

The system provides two implementations:

• et_field.rs: Computation over finite fields (BN254 scalar field) for cryptographic compatibility
• et_rational.rs: Exact computation using arbitrary-precision rationals for verification

HITS (Hyperlink-Induced Topic Search), also known as Hubs and Authorities, is a link analysis algorithm that computes two scores for each node:

• Hub Score: How good a node is at pointing to authoritative nodes
• Authority Score: How authoritative a node is (pointed to by good hubs)

1. Adjacency Matrix: Define A[i][j] = 1 if there's a link from i to j, otherwise 0.

2. Mutual Reinforcement: The key insight is that good hubs point to good authorities, and good authorities are pointed to by good hubs:

   auth⁽ᵏ⁺¹⁾[i] = Σⱼ A[j][i] · hub⁽ᵏ⁾[j]    (authorities are pointed to by hubs)
   hub⁽ᵏ⁺¹⁾[i]  = Σⱼ A[i][j] · auth⁽ᵏ⁾[j]   (hubs point to authorities)
   

   In matrix form:

   auth⁽ᵏ⁺¹⁾ = Aᵀ · hub⁽ᵏ⁾
   hub⁽ᵏ⁺¹⁾  = A · auth⁽ᵏ⁾
   

3. L2 Normalization: After each iteration, scores are normalized using the L2 norm:

   hub[i] = hub[i] / √(Σⱼ hub[j]²)
   auth[i] = auth[i] / √(Σⱼ auth[j]²)
   

4. Convergence: The algorithm converges to the principal eigenvectors of AᵀA (for authorities) and AAᵀ (for hubs).

• Eigenvector Relationship:
  • Authority scores converge to the principal eigenvector of AᵀA
  • Hub scores converge to the principal eigenvector of AAᵀ
• Mutual Reinforcement: The two-score system creates a feedback loop that identifies important nodes
• Symmetry: Transposing the adjacency matrix swaps hub and authority scores

Three implementations are provided:

• h_and_a_field.rs: Finite field arithmetic for cryptographic proofs
• h_and_a_rational.rs: Exact arbitrary-precision computation
• h_and_a_float.rs: Floating-point for quick prototyping

In pessimistic mode, every computation is fully verified. This is the straightforward approach where the verifier re-executes the algorithm and checks the results.

1. Input Commitment: The compute node commits to inputs (local trust matrix, pre-trust values)
2. Computation: Run the ranking algorithm for N iterations
3. Output Commitment: Commit to the final scores
4. Verification: The verifier:
   • Takes the committed inputs
   • Re-runs one iteration of the algorithm
   • Verifies the result matches (within precision tolerance)

For EigenTrust, the verifier checks:

t'[target] ≈ Σⱼ c[j][target] · t[j]

Where t' is the claimed new score and t is the previous iteration's scores.

Approximate Equality Check: Since we use rational arithmetic, exact equality is checked by:

1. Compute LCM of denominators: L = lcm(denom(t'), denom(computed))
2. Scale numerators:
   • n₁ = numer(t') × (L / denom(t'))
   • n₂ = numer(computed) × (L / denom(computed))
3. Truncate to precision: n₁' = floor(n₁ / 10^k), n₂' = floor(n₂ / 10^k)
4. Assert: n₁' = n₂'

// From pessimistic.rs - EigenTrust verification
let target_peer_id = 1;
let mut new_s = Br::zero();
for j in 0..5 {
    new_s += normalised_lt[j][target_peer_id].clone() * res_br[j].clone();
}

let prev_s = res_br[target_peer_id].clone();

// Scale to common denominator and compare
let lcm = prev_s.denom().lcm(&new_s.denom());
let c_numer = prev_s.numer() * (lcm.clone() / prev_s.denom());
let c_prime_numer = new_s.numer() * (lcm.clone() / new_s.denom());

let scale = BigUint::from(10usize).pow(46);
assert_eq!(c_numer.div_floor(&scale), c_prime_numer.div_floor(&scale));

In optimistic mode, computations are assumed correct unless challenged. This dramatically reduces on-chain verification costs by only performing verification when disputes arise.

┌────────────┐         ┌────────────┐         ┌────────────┐
│   Compute  │         │   Smart    │         │ Challenger │
│    Node    │         │  Contract  │         │            │
└─────┬──────┘         └─────┬──────┘         └─────┬──────┘
      │                      │                      │
      │  1. Submit Data      │                      │
      │  (Merkle Roots)      │                      │
      │─────────────────────▶│                      │
      │                      │                      │
      │                      │  2. Challenge        │
      │                      │  (peer_from, peer_to)│
      │                      │◀─────────────────────│
      │                      │                      │
      │  3. Response         │                      │
      │  (Merkle Proofs)     │                      │
      │─────────────────────▶│                      │
      │                      │                      │
      │                      │  4. Verify           │
      │                      │  (on-chain)          │
      │                      │──────┐               │
      │                      │      │               │
      │                      │◀─────┘               │
      │                      │                      │

A challenge specifies a location in the computation to verify:

pub struct Challenge {
    pub from: Fr,  // Source peer (incoming edge)
    pub to: Fr,    // Target peer (whose score to verify)
}

For consistency challenges, two locations are compared:

pub struct ConsistencyChallenge {
    pub target1: Challenge,  // First location
    pub target2: Challenge,  // Second location (same 'from', different 'to')
}

1. Validity Proof (EtComputeTreeValidityProof)

Proves that a score was computed correctly:

pub struct EtComputeTreeValidityProof {
    peer_path: ComputeTreeMembershipProof,      // Path to target peer's score
    neighbour_path: Path<Hasher>,               // Path in neighbor's subtree
    lt_tree_path: AmTreeMembershipProof,        // Local trust value proof
    c: BrDecomposed,                            // Claimed score (decomposed)
    c_prime: BrDecomposed,                      // Computed score (decomposed)
}

2. Consistency Proof

Proves that the same intermediate value appears at multiple tree locations:

pub struct ConsistencyProof {
    target1_path: ComputeTreeMembershipProof,
    target2_path: ComputeTreeMembershipProof,
}

The smart contract performs three checks:

1. Data Verification: Merkle paths lead to the committed roots

   let (target_root, _) = self.peer_path.master_tree_path.root();
   assert!(target_root == data[1]);  // Matches committed compute tree root

2. Challenge Verification: Proofs correspond to the challenged locations

   assert!(self.peer_path.master_tree_path.index == challenge.to);
   assert!(self.lt_tree_path.sub_tree_path.index == challenge.from);

3. Correctness Verification: The mathematical relationship holds

   // c ≈ c' within precision tolerance
   let c_reduced = c.num_limbs.div_floor(&power_of_ten);
   let c_prime_reduced = c_prime.num_limbs.div_floor(&power_of_ten);
   assert!(c_reduced == c_prime_reduced);

Poseidon is a hash function designed specifically for zero-knowledge proof systems. It operates natively over prime fields, making it much more efficient in ZK circuits than traditional hash functions like SHA-256.

Poseidon uses the Hades design strategy with three types of rounds:

1. Full Rounds (First Half): All state elements pass through S-boxes
2. Partial Rounds: Only the first state element passes through S-box
3. Full Rounds (Second Half): All state elements pass through S-boxes

Each round consists of:

1. AddRoundConstants: state[i] += round_constant[i]
2. SubWords (S-box): state[i] = state[i]^α (where α=5 for BN254)
3. MixLayer (MDS): state = MDS_matrix × state

For BN254 with width 5:

• Full rounds: 8 (4 + 4)
• Partial rounds: 56
• S-box exponent: 5

pub fn permute(&self) -> [Fr; WIDTH] {
    let mut state = self.inputs;
    
    // First half of full rounds
    for round in 0..half_full_rounds {
        state = P::apply_round_constants(&state, &round_consts);
        for s in state.iter_mut() {
            *s = P::sbox_f(*s);  // x^5
        }
        state = P::apply_mds(&state);
    }
    
    // Partial rounds
    for round in 0..partial_rounds {
        state = P::apply_round_constants(&state, &round_consts);
        state[0] = P::sbox_f(state[0]);  // Only first element
        state = P::apply_mds(&state);
    }
    
    // Second half of full rounds
    for round in 0..half_full_rounds {
        state = P::apply_round_constants(&state, &round_consts);
        for s in state.iter_mut() {
            *s = P::sbox_f(*s);
        }
        state = P::apply_mds(&state);
    }
    
    state
}

A Sparse Merkle Tree (SMT) is a Merkle tree where most leaves are empty (default values). This allows for efficient proofs of non-membership and works well with large, sparse key spaces.

Each node stores a tuple (hash, accumulated_value):

pub struct SparseMerkleTree<H> {
    nodes: HashMap<(u32, Fr), (Fr, Fr)>,  // (level, index) -> (hash, acc_value)
    default: Vec<(Fr, Fr)>,                // Default nodes at each level
}

1. Additive Mode (insert_leaf)

Values are summed as they propagate up the tree:

parent.hash = Poseidon(left.hash, left.value, right.hash, right.value, 0)
parent.value = left.value + right.value

2. Multiplicative Mode (insert_leaf_mul)

At the leaf level, values are multiplied before summing:

// At leaf level (level 0):
parent.value = left.hash × left.value + right.hash × right.value

// At higher levels:
parent.value = left.value + right.value

This is crucial for EigenTrust verification where we compute Σ lt[j][i] × score[j].

A membership proof contains the sibling nodes along the path from leaf to root:

pub struct Path<H> {
    index: Fr,                                    // Leaf index
    root: (Fr, Fr),                               // Expected root
    path_arr: [[Fr; 4]; Fr::NUM_BITS as usize],  // [(left_hash, left_val, right_hash, right_val); ...]
}

pub fn verify(&self) -> bool {
    let bits = field_to_bits_vec(self.index);
    
    for i in 0..Fr::NUM_BITS - 1 {
        let node = Poseidon::hash(path_arr[i]);
        let sum = path_arr[i][1] + path_arr[i][3];
        
        // Check parent contains this node
        let (parent_hash, parent_sum) = if bits[i + 1] {
            (path_arr[i + 1][2], path_arr[i + 1][3])  // We're on the right
        } else {
            (path_arr[i + 1][0], path_arr[i + 1][1])  // We're on the left
        };
        
        assert!(parent_hash == node && parent_sum == sum);
    }
    
    // Check final level matches root
    let final_hash = Poseidon::hash(path_arr[last]);
    let final_sum = path_arr[last][1] + path_arr[last][3];
    assert!(self.root == (final_hash, final_sum));
}

Compute Trees provide a hierarchical structure optimized for verifying iterative computations like EigenTrust.

                    Master Tree
                    ┌─────────┐
                    │  Root   │
                    │(hash,Σs)│
                    └────┬────┘
                   ┌─────┴─────┐
              ┌────┴────┐ ┌────┴────┐
              │ Peer 0  │ │ Peer 1  │  ...
              │(h₀, s₀) │ │(h₁, s₁) │
              └────┬────┘ └────┬────┘
                   │           │
              Sub-Tree 0   Sub-Tree 1
              ┌────┴────┐  ┌────┴────┐
              │  Root   │  │  Root   │
              └────┬────┘  └────┬────┘
             ┌────┬┴───┬────┐   ...
             │    │    │    │
           (lt₀₀×s₀) (lt₁₀×s₁) ...

Master Tree:

• Leaves contain (sub_tree_root_hash, final_score) for each peer
• The root commits to all final scores

Sub Trees (one per peer):

• Each peer has a sub-tree storing contributions from all neighbors
• Leaf j in peer i's sub-tree contains (lt[j][i], score[j])
• Uses multiplicative mode: accumulated = Σⱼ lt[j][i] × score[j]

pub struct ComputeTreeMembershipProof {
    master_tree_path: Path<Hasher>,  // Path in master tree
    sub_tree_path: Path<Hasher>,     // Path in sub-tree
}

Verification ensures:

1. Sub-tree path is valid (multiplicative)
2. Master tree path is valid (additive)
3. Master tree leaf contains the sub-tree root

All cryptographic operations use the BN254 scalar field:

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

Properties:

• Prime field of ~254 bits
• Supports efficient elliptic curve operations
• Used in Ethereum's precompiles (ecAdd, ecMul, ecPairing)

Operations:

• Addition: (a + b) mod p
• Multiplication: (a × b) mod p
• Inversion: a⁻¹ such that a × a⁻¹ ≡ 1 (mod p)
• Exponentiation: a^n mod p (using square-and-multiply)

For exact computation, scores are represented as ratios of arbitrary-precision integers:

type Br = Ratio<BigUint>;  // numerator / denominator

Operations preserve exactness:

• a/b + c/d = (ad + bc) / bd
• a/b × c/d = ac / bd
• Automatic GCD reduction after operations

Since iterative algorithms produce converging (not exact) values, we need approximate equality:

fn approx_equal(a: &Br, b: &Br, precision: u32) -> bool {
    // 1. Find common denominator
    let lcm = a.denom().lcm(b.denom());
    
    // 2. Scale numerators
    let a_scaled = a.numer() * (lcm.clone() / a.denom());
    let b_scaled = b.numer() * (lcm.clone() / b.denom());
    
    // 3. Truncate to precision
    let scale = BigUint::from(10u32).pow(precision);
    let a_truncated = a_scaled.div_floor(&scale);
    let b_truncated = b_scaled.div_floor(&scale);
    
    // 4. Compare
    a_truncated == b_truncated
}

Claim: Score t[i] at iteration k+1 equals Σⱼ c[j][i] × t[j] at iteration k.

Proof Structure:

1. Reveal t[i] from compute tree (with Merkle proof)
2. Reveal t[j] for challenged neighbor j (with Merkle proof)
3. Reveal c[j][i] from local trust tree (with Merkle proof)
4. Show that the accumulated sum in the sub-tree equals the claimed score

Verification Math:

Given:
- c[j][i] = local_trust[j][i] / Σₖ local_trust[j][k]  (from LT tree)
- t[j] = neighbor's score (from compute tree)
- t[i] = claimed score (from compute tree)

Verify:
- Sub-tree accumulator = Σⱼ c[j][i] × t[j]
- Sub-tree accumulator ≈ t[i] (within precision)

Claim: Hub score h[i] equals (Σⱼ A[j][i] × auth[j]) / ||hub||₂

Proof Structure:

1. Reveal h[i] (claimed hub score)
2. Reveal auth[j] for challenged neighbor
3. Reveal A[j][i] from adjacency matrix tree
4. Reveal the sum Σⱼ A[j][i] × auth[j]
5. Reveal ||hub||₂ (L2 norm)
6. Verify the normalization

Verification Math:

Given:
- A[j][i] ∈ {0, 1} (from AM tree)
- auth[j] = authority score (from compute tree)
- sum = Σⱼ A[j][i] × auth[j] (from sub-tree accumulator)
- sum_sqrt ≈ √(Σⱼ sum[j]²) (provided, verified approximately)

Verify:
- h[i] × sum_sqrt ≈ sum[i] (within precision)

Claim: The same intermediate score t[j] appears everywhere it's referenced.

Proof Structure:

1. Reveal t[j] at location 1 (peer i's sub-tree)
2. Reveal t[j] at location 2 (peer k's sub-tree)
3. Verify both values match

This prevents a malicious compute node from using different values for the same score in different parts of the computation.

# Run the default example (Hubs & Authorities optimistic)
cargo run

# Run tests
cargo test

In main.rs, uncomment the desired scenario:

fn main() {
    // EigenTrust Pessimistic
    // et_pessimistic();
    // et_pessimistic_invalid();

    // EigenTrust Optimistic
    // et_optimisitic_interactive();
    // et_optimisitic_interactive_invalid();

    // Hubs And Authorities pessimistic
    // ha_pessimistic();
    // ha_pessimistic_invalid();

    // Hubs And Authorities optimistic
    ha_optimisitic_interactive();
}

The _invalid variants demonstrate fraud detection when a compute node submits incorrect data.

See LICENSE for details.