Equihash Block Witholding Simulation

simulation.rb

#!/usr/bin/env ruby

# This is a simulation of the advantage an attacker can get by following
# a particular selfish mining strategy that works when the sequential PoW
# running time is of the same order as the block target time. The simulation
# assumes instant block propagation, so the advantage this simulation computes
# is *on top of* the advantage gained by doing regular selfish mining.

# The network is made up of Equihash Machines. Equihash Machines are either
# Attacker Machines or Normal Machines. Normal Machines and Attacker Machines
# spit out the same number of equihash solutions, but Attacker Machines run
# `attacker_speedup` times faster than Normal Machines. The fraction of the
# network which is Attacker Machines vs. Normal Machines is set so that when all
# of the Equihash Machines (Attacker and Normal) mine with the default strategy,
# the Attacker Machines win `attacker_network_fraction` of the blocks.

# Time is measured in units of the target block interval, and Normal Machines
# can run `regular_equihash_per_block` times within a block interval.

# You can adjust these parameters here:
regular_equihash_per_block = 4
attacker_speedup = 2.0
attacker_network_fraction = 0.25
blocks = 100000

# Running this program simulates two things:
#
# 1. The regular case, where all Equihash Machines use the default mining
#    strategy.
#
# 2. The attack case, where the Normal Machines use the default mining strategy,
#    but the Attacker Machines follow a different strategy. When they win a
#    block, they withold it from the network but mine on top of it until just
#    before the currently-running Normal Machines would finish running. They
#    only disclose blocks when it is to their advantage to do so.
#
# The following simplifications have been made:
# 
# - If there is *any* time left before the Normal Machines finish, we give the
#   attacker an *entire* run of their Attacker Machines. This makes the
#   simulation overestimate the attacker's advantage.

def assert(b)
  unless b
    raise "Assertion failure!"
  end
end

def simulate_blocks_default_strategy(tf, ts, pa, po, blocks)
  # The attacker's implementation is faster or the same speed.
  assert(tf <= ts)
  assert(tf > 0)
  assert(ts > 0)

  # The Attacker Machine portion of the network's chance of winning per run is
  # a valid probability.
  assert(0 <= pa)
  assert(pa <= 1)

  # The Normal Machine portion of the network's chance of winning per run is
  # a valid probability.
  assert(0 <= po)
  assert(po <= 1)

  attacker_wins = 0
  other_wins = 0
  block_times = []

  # We're assuming block propagation is instant, and all communication between
  # all Equihash Machines is instant, so following the default strategy, all
  # machines of each type are always in the same state, i.e. they always have
  # the same amount of time remaining before they finish running.

  blocks.times do |block_num|
    time = 0
    next_other_run = ts
    loop do
      new_time = time + tf

      if time < next_other_run && next_other_run <= new_time
        if rand() < po
          # The Normal Machine portion of the network wins this block.
          other_wins += 1
          block_times << next_other_run
          break
        end
        next_other_run += ts
      end

      if rand() < pa
        # The Attacker Machine portion of the network wins this block.
        attacker_wins += 1
        block_times << new_time
        break
      end

      time = new_time
    end
  end

  return attacker_wins, other_wins, (block_times.inject(:+).to_f/blocks)
end

def simulate_blocks_attacker_strategy(tf, ts, pa, po, blocks)
  # The attacker's implementation is faster or the same speed.
  assert(tf <= ts)
  assert(tf > 0)
  assert(ts > 0)

  # The Attacker Machine portion of the network's chance of winning per run is
  # a valid probability.
  assert(0 <= pa)
  assert(pa <= 1)

  # The Normal Machine portion of the network's chance of winning per run is
  # a valid probability.
  assert(0 <= po)
  assert(po <= 1)

  attacker_wins = 0
  other_wins = 0
  block_times = []

  # The attacker knows there's this much time before the Normal Machines finish
  # running.
  time_remaining_before_other_runs_complete = 0

  # The attacker has this many blocks which they haven't broadcast to the
  # network yet.
  attacker_blocks_ahead = 0

  normal_machines_finish = false

  blocks.times do |block_num|

    # Attack Strategy
    # ---------------

    if normal_machines_finish
      normal_machines_finish = false

      # This branch should only be taken when the Normal Machines finish the
      # round the attacker can predict it's safe to wait for.
      assert(time_remaining_before_other_runs_complete == 0)

      # If the attacker is ahead by a block, they can broadcast it to get all of
      # the Normal Machines to restart just before they finish. So in this case
      # they never actually finished, the attacker got them to restart on the
      # new block.
      if attacker_blocks_ahead > 0
        attacker_blocks_ahead -= 1
        time_remaining_before_other_runs_complete = ts
        # Attack continues, fall through...
      else
        # The Normal Machines have a chance at winning now that they've
        # finished.
        if rand() < po
          # They win.
          other_wins += 1
          # FIXME: This is wrong
          block_times << ts
          next
        end
      end
    end

    # If the Normal Machines have running time left (any at all), let's give the
    # attacker a whole opportunity to mine the block. This gives them an extra
    # advantage, so the simulation upper bounds their advantage.
    if time_remaining_before_other_runs_complete > 0

      # The Normal Machines make progress towards finishing their run.
      time_remaining_before_other_runs_complete = [0, time_remaining_before_other_runs_complete - tf].max
      if time_remaining_before_other_runs_complete == 0
        normal_machines_finish = true
      end

      if rand() < pa
        # Attacker's strategy advantage has them win this block.
        attacker_wins += 1
        attacker_blocks_ahead += 1
        # FIXME: This isn't right.
        block_times << tf
        next
      end

      # Attacker didn't win, but they might still be able to get another full
      # run in before the Normal Machines finish. Restart the loop.
      redo
    end

    # Default Strategy
    # ---------------

    # We get here when the attacker doesn't know there's time before the Normal
    # Machines finish running, and can't release a block to make that the case.

    assert(time_remaining_before_other_runs_complete == 0)
    assert(attacker_blocks_ahead == 0)

    # This is the same as normal mining, except for we set
    # `time_remaining_before_other_runs_complete` appropriately when the
    # attacker wins the block.

    time = 0
    next_other_run = ts
    loop do
      new_time = time + tf

      if time < next_other_run && next_other_run <= new_time
        if rand() < po
          # The Normal Machine portion of the network wins this block.
          other_wins += 1
          block_times << next_other_run
          break
        end
        next_other_run += ts
      end

      if rand() < pa
        # The Attacker Machine portion of the network wins this block.
        attacker_wins += 1
        attacker_blocks_ahead += 1
        time_remaining_before_other_runs_complete = next_other_run - new_time
        block_times << new_time
        break
      end

      time = new_time
    end
  end

  return attacker_wins, other_wins, (block_times.inject(:+).to_f/blocks)
end

def calculate_po_default_strategy(tb, tf, ts, pa)
  ts/tb * (1.0 - pa * tb/tf)
end

def calculate_po_attacker_strategy(tb, tf, ts, pa)
  # Experimentally, we get good results (block target time near 1) using the
  # same `po` as for the regular case, so we don't need to bother implementing
  # newton's method or whatever to find the correct `po` for the attack case.
  po = calculate_po_default_strategy(tb, tf, ts, pa)
  return po
end

# The target block interval
tb = 1.0
# The running time of a Normal Machine
ts = tb / regular_equihash_per_block.to_f
# The running time of an Attacker Machine
tf = ts / attacker_speedup
# The probability one of the solutions produced by one run of all the Attacker
# Machines will pass the difficulty check.
pa = attacker_network_fraction * tf/tb
# The probability one of the solutions produced by one run of all the Normal
# Machines will pass the difficulty check.
po = calculate_po_default_strategy(tb, tf, ts, pa)

# No-attack case
attacker_wins, other_wins, avg_block_time = simulate_blocks_default_strategy(
  tf,
  ts,
  pa,
  po,
  blocks
)

# Attack case
attacker_wins_a, other_wins_a, avg_block_time_a = simulate_blocks_attacker_strategy(
  tf,
  ts,
  pa,
  po,
  blocks
)

puts "Inputs"
puts "-------"
puts "Regulars can do #{regular_equihash_per_block} equihash runs per block interval."
puts "The attacker's implementation is #{attacker_speedup}x faster."
puts "The attacker should control #{(attacker_network_fraction*100).round(2)}% of the network in the regular case."
puts ""

puts "Results"
puts "--------"
puts "The attacker's probability of passing the difficulty check in one round is #{pa.round(6)}."
puts "The simulated attacker won #{(attacker_wins.to_f/blocks * 100).round(2)}% of the blocks normally (should match the percentage above)."
puts "The simulated attacker won #{(attacker_wins_a.to_f/blocks * 100).round(2)}% of the blocks using the attack strategy."
puts "The attacker gains a #{(attacker_wins_a.to_f/attacker_wins).round(4)} advantage factor (+#{((attacker_wins_a.to_f/attacker_wins - 1)*100).round(2)}%) by using the attack strategy."
puts ""

puts "Sanity Checks"
puts "--------------"
puts "The observed block interval in the regular case (should be ~1): #{avg_block_time.round(6)}"
puts "The observed block interval in the attack case (should be ~1): #{avg_block_time_a.round(6)}"