Sybil attack success probability

sybil-attack-success-prob.py

#! /usr/bin/python3

##this file calculates the success probability of a sybil attack on the
# orderbook with fidelity bonds used in joinmarket
# see https://gist.github.com/chris-belcher/87ebbcbb639686057a389acb9ab3e25b

from scipy.optimize import brentq
from time import time
from datetime import timedelta

def descend_probability_tree(weights, remaining_descents, branch_probability):
    if remaining_descents == 0:
        return branch_probability
    else:
        total_weight = sum(weights)
        result = 0
        for i, w in enumerate(weights):
            #honest makers are at index 0
            if i == 0:
                #an honest maker being chosen means the sybil attack failed
                #so this branch contributes zero to the attack success prob
                continue
            if w == 0:
                continue
            descended_weights = weights.copy()
            descended_weights[i] = 0
            result += descend_probability_tree(descended_weights,
                remaining_descents-1, branch_probability*w/total_weight)
        return result

def calculate_sybil_attack_success_probability(honest_weight, sybil_count,
        sybil_weight, taker_peer_count):
    if taker_peer_count > sybil_count:
        #raise ValueError("attack success always zero if the peer count is " +
        #    "than the sybil count")
        return 0
    weights = [honest_weight] + sybil_count*[sybil_weight]
    return descend_probability_tree(weights, taker_peer_count, 1.0)

def calculate_top_makers_sybil_attack_success_probability(weights,
        taker_peer_count):
    honest_weight = sum(weights[taker_peer_count:])
    weights = [honest_weight] + weights[:taker_peer_count]
    return descend_probability_tree(weights, taker_peer_count, 1.0)

def calculate_required_sybil_weight(honest_weight, taker_peer_count,
    target_success_probability):
    
    def f(sybil_weight, honest_weight, taker_peer_count,
            target_success_probability):
        return (calculate_sybil_attack_success_probability(honest_weight,
            taker_peer_count, sybil_weight, taker_peer_count)
            - target_success_probability)
    return brentq(f, a=honest_weight, b=honest_weight*1e6, args=(honest_weight,
        taker_peer_count, target_success_probability))

def btcf(b):
    return "%0.8f" % (b,)

def weight_to_burned_coins(w):
    #calculates how many coins need to be burned to produce a certain bond
    return w**0.5

def weight_to_locked_coins(w, r, locktime_months):
    #calculates how many coins need to be locked to produce a certain bond
    return w**0.5 / r / locktime_months * 12

def coins_locked_to_weight(c, r, locktime_months):
    return (c*r*locktime_months/12.0)**2

def coins_burned_to_weight(c):
    return c*c

#0 = calculate required fidelity bond value for sybil attacking where value
#    of honest fidelity bonds is 1
#1 = calculate required fidelity bond value for sybil attacking with
#    honest fidelity bonds estimated using real life data
#2 = calculate probability of sybil attack success if the top k makers in the
#    real life data were actually sybils
task = 2
print_csv = True

#sybil attack succeeds if takers coinjoin only with the sybil attacker
# with this probability
target_success_probability = 0.95

#time value of money
r = 0.003
#time coins are locked for
locktime_months = 6

#which range of peer counts to calculate for
taker_peer_count_range = (2, 8)

print("task = " + str(task))
if task == 1 or task == 2:
    f_name = "joinmarket-orderbook-maxsizes-data.csv"
    fd = open(f_name)
    maxsizes = fd.read().strip().split("\n")
    fd.close()
    maxsizes = [float(m) for m in maxsizes]
    #locked all those coins
    timelocked_weights = [coins_locked_to_weight(m, r, locktime_months)
        for m in maxsizes]
    print("timelocked weights = " + str(timelocked_weights))
    print("equivalent burned coins = " + str([weight_to_burned_coins(w)
        for w in timelocked_weights]))

if task == 0 or task == 1:
    if task == 0:
        honest_weight = 1
    elif task == 1:
        honest_weight = sum(timelocked_weights)
        print("honest_weight coin equivalent = " +
            str(weight_to_burned_coins(honest_weight)) + "btc burned, or " +
            str(weight_to_locked_coins(honest_weight, r, locktime_months)) +
            " btc locked for 6m")

    print("calculating sybil attack required weight for honest weight="
        + str(honest_weight))
    data = []
    for taker_peer_count in range(*taker_peer_count_range):
        st = time()
        sybil_weight = calculate_required_sybil_weight(honest_weight,
            taker_peer_count, target_success_probability)
        et = time()
        btc_equiv = weight_to_burned_coins(sybil_weight)
        total_btc_burned = btc_equiv * taker_peer_count
        total_btc_locked_for_6m = weight_to_locked_coins(sybil_weight, r,
            locktime_months) * taker_peer_count
        print("required sybil_weight=" + str(sybil_weight) +
            " for peer count=" + str(taker_peer_count) + 
            " equivalent_burned_coin=" + btcf(btc_equiv) + " btc per" + 
            " sybil or " + btcf(total_btc_burned) +
            " btc in total or " + btcf(total_btc_locked_for_6m) +
            " btc locked for " + str(locktime_months) + " months, time_taken=" +
            str(timedelta(seconds=et-st)))
        data.append((taker_peer_count, sybil_weight, total_btc_burned,
            total_btc_locked_for_6m))
    if print_csv:
        print("peer-count,sybil-weight,total-btc-burned,total-btc-" +
            str(locktime_months) + "m-locked")
        for pc, sw, tbb, tbl in data:
            print(str(pc) + "," + str(sw) + "," + str(tbb) + "," + str(tbl))
elif task == 2:
    data = []
    for taker_peer_count in range(*taker_peer_count_range):
        st = time()
        success_prob = calculate_top_makers_sybil_attack_success_probability(
            timelocked_weights, taker_peer_count)
        et = time()
        print("success prob of self-sybil attack = "
            + str(round(success_prob*100, 2))
            + "% taker_peer_count=" + str(taker_peer_count) + ", time_taken="
            + str(timedelta(seconds=et-st)))
        data.append((taker_peer_count, success_prob))
    if print_csv:
        print("peer-count,success-probability")
        for pc, sp in data:
            print(str(pc) + "," + str(sp))