/**
 * byzantine.ts — Byzantine Generals Problem (Signed Message Protocol)
 *
 * Run with: npx ts-node byzantine.ts
 *
 * Simulates the Byzantine Generals Problem using signed messages.
 * Loyal generals follow the protocol; traitors send arbitrary lies.
 */

// --- Types ---

type Order = 'attack' | 'retreat'
type GeneralType = 'loyal' | 'traitor'
type GeneralRole = 'commander' | 'lieutenant'

interface Message {
  from: number
  order: Order
  signatures: Set<number>
  path: number[]
}

class General {
  id: number
  role: GeneralRole
  type: GeneralType
  orders: Map<string, Order> = new Map() // keyed by message signature chain
  receivedMessages: Message[] = []

  constructor(id: number, role: GeneralRole, type: GeneralType) {
    this.id = id
    this.role = role
    this.type = type
  }

  sign(msg: Message): Message {
    msg.signatures.add(this.id)
    msg.path.push(this.id)
    return msg
  }

  // --- Step 1: Commander sends initial order ---

  sendOrder(order: Order): Message[] {
    if (this.role !== 'commander') throw new Error('Only the commander sends orders')

    if (this.type === 'traitor') {
      // Traitor commander: send different orders to different lieutenants
      console.log(`\n💀 Traitor Commander ${this.id} sends conflicting orders!`)
      return [
        this.sign({ from: this.id, order: 'attack', signatures: new Set(), path: [] }),
        this.sign({ from: this.id, order: 'retreat', signatures: new Set(), path: [] }),
      ]
    }

    // Loyal commander: send the same order to all
    console.log(`\n📯 Loyal Commander ${this.id} orders: ${order}`)
    return [
      this.sign({ from: this.id, order, signatures: new Set(), path: [] }),
      this.sign({ from: this.id, order, signatures: new Set(), path: [] }),
    ]
  }
}

// --- The Protocol ---

function simulateByzantineGenerals(
  commanderType: GeneralType,
  traitorId: number | null,
) {
  const numGenerals = 4 // 1 commander + 3 lieutenants (satisfies 3f+1 for f=1)

  console.log(`\n${'='.repeat(60)}`)
  console.log(`BYZANTINE GENERALS — Signed Messages Protocol`)
  console.log(`Commander: ${commanderType} | Traitor General: ${traitorId ?? 'none'}`)
  console.log(`${'='.repeat(60)}\n`)

  // Create generals
  const commander = new General(0, 'commander', commanderType)
  const lieutenants: General[] = []
  for (let i = 1; i < numGenerals; i++) {
    lieutenants.push(new General(i, 'lieutenant', i === traitorId ? 'traitor' : 'loyal'))
  }

  const allGenerals = [commander, ...lieutenants]

  // --- PHASE 1: Commander broadcasts orders ---
  console.log('📤 PHASE 1: Commander broadcasts orders')
  const initialMessages = commander.sendOrder('attack')

  // Distribute messages to lieutenants (commander sends one to each sequentially)
  const round1Messages: Message[] = []
  for (let i = 0; i < lieutenants.length; i++) {
    const msg = initialMessages.length > 1 ? initialMessages[i] : initialMessages[0]
    if (msg) {
      round1Messages.push(msg)
      console.log(`   Commander ${commander.id} → General ${lieutenants[i].id}: "${msg.order}" (signed: [${[...msg.signatures]}])`)
    }
  }

  // --- PHASE 2: Lieutenants receive and forward ---
  console.log('\n📥 PHASE 2: Lieutenants process messages')

  for (const lt of lieutenants) {
    const incoming = round1Messages.find(m => m.path[m.path.length - 2] === 0 && m.path[m.path.length - 1] === lt.id)

    if (incoming) {
      lt.receivedMessages.push(incoming)
      console.log(`   General ${lt.id} received: "${incoming.order}" from Commander`)

      if (lt.type === 'traitor') {
        // Traitor lieutenant: lies about what they received
        const fakeOrder: Order = incoming.order === 'attack' ? 'retreat' : 'attack'
        const fakeMsg: Message = {
          from: lt.id,
          order: fakeOrder,
          signatures: new Set([...incoming.signatures]),
          path: [...incoming.path],
        }
        lt.sign(fakeMsg)

        // Send to all other lieutenants
        for (const other of lieutenants) {
          if (other.id === lt.id) continue
          other.receivedMessages.push(structuredClone(fakeMsg))
          console.log(`   💀 Traitor General ${lt.id} → General ${other.id}: "${fakeOrder}" (claiming Commander said "${fakeOrder}")`)
        }
      } else {
        // Loyal lieutenant: honestly forward the signed message
        const forwarded = lt.sign(structuredClone(incoming))
        for (const other of lieutenants) {
          if (other.id === lt.id) continue
          other.receivedMessages.push(structuredClone(forwarded))
          console.log(`   ✅ Loyal General ${lt.id} → General ${other.id}: "${incoming.order}" (signed: [${[...forwarded.signatures]}])`)
        }
      }
    }
  }

  // --- PHASE 3: Each lieutenant decides ---
  console.log('\n⚖️ PHASE 3: Lieutenants decide')

  for (const lt of lieutenants) {
    // Each lieutenant looks at ALL messages they received and applies a deterministic decision rule
    // For signed messages, they take the majority of the orders they saw directly from the commander
    // (identified by messages where the first signature is the commander, id=0)
    const commanderOrders = lt.receivedMessages
      .filter(m => m.signatures.has(0))
      .map(m => m.order)

    const attacks = commanderOrders.filter(o => o === 'attack').length
    const retreats = commanderOrders.filter(o => o === 'retreat').length
    const decision: Order = attacks >= retreats ? 'attack' : 'retreat'

    console.log(`   General ${lt.id} (${lt.type}): saw [${commanderOrders.join(', ')}] → decides: ${decision}`)
  }

  // --- Verify IC1 (All loyal lieutenants agree) ---
  console.log('\n📋 VERIFICATION:')
  const loyalDecisions = lieutenants
    .filter(lt => lt.type === 'loyal')
    .map(lt => {
      const commanderOrders = lt.receivedMessages
        .filter(m => m.signatures.has(0))
        .map(m => m.order)
      const attacks = commanderOrders.filter(o => o === 'attack').length
      const retreats = commanderOrders.filter(o => o === 'retreat').length
      return { id: lt.id, decision: attacks >= retreats ? 'attack' : 'retreat' as Order }
    })

  const allAgree = loyalDecisions.every(d => d.decision === loyalDecisions[0]?.decision)
  const firstDecision = loyalDecisions[0]?.decision

  if (commanderType === 'loyal') {
    // IC2: If commander is loyal, all loyal generals follow the commander's order
    const followsCommander = loyalDecisions.every(d => d.decision === 'attack')
    console.log(`   IC2 (follow commander): ${followsCommander ? '✅ PASS' : '❌ FAIL'} — all loyal lieutenants decided: ${firstDecision}`)
  } else {
    // IC1: All loyal lieutenants must agree on the same plan
    console.log(`   IC1 (loyal agree): ${allAgree ? '✅ PASS' : '❌ FAIL'} — all loyal lieutenants agreed on: ${firstDecision}`)
  }
}

// --- Run simulations ---

// Case 1: Loyal commander, all loyal lieutenants
simulateByzantineGenerals('loyal', null)

// Case 2: Loyal commander, one traitor lieutenant
simulateByzantineGenerals('loyal', 1)

// Case 3: Traitor commander, one traitor lieutenant
simulateByzantineGenerals('traitor', 1)

console.log('\n✅ All simulations complete.')

⬇ Download byzantine.ts