collusion.sagews

class ProbNode:
    """Stores the probability of getting a specific number of colluding nodes within a group.
    Also contains the remaining nodes and colluding nodes in the network that are not in the group."""
    def __init__(self, nodes, colluding, group, quorum, upstream_prob):
        self.prob = upstream_prob * ((binomial(colluding, quorum) * binomial(nodes-colluding,group-quorum))/binomial(nodes, group))
        self.nodes = nodes - group
        self.colluding = colluding - quorum
    
def rcoin_control(pnodes, group, quorum, required_groups):
    if required_groups == 0:
        return sum(x.prob for x in pnodes)
    #Now we start branching.  Each configuration must be multiplied by the probabilities for each configuration of the other required nodes.
    pnodes = (group_control(x.nodes, x.colluding, group, quorum, x.prob) for x in pnodes)
    pnodes = [x for l in pnodes for x in l]  #flatten
    return rcoin_control(pnodes, group, quorum, required_groups - 1)    
    
#############################################
def group_control(nodes, colluding, group, quorum, upstream_prob=1):
    """returns an array of probability nodes that, when summed, is the probability of controlling the specified group in the specified network.
    It is the summ of all of the configurations that can achieve control
    nodes: the number of nodes in the network
    colluding: the number of nodes colluding in the attack
    group: the nodes in a group
    quorum: the colluding nodes required in a group to take control
    upstream_prob: the probabolity of previous calculations that must be multiplied into this calculation"""
    return [ProbNode(nodes, colluding, group, q, upstream_prob) for q in range(quorum, group + 1)]

def coin_control(nodes, colluding, group, quorum, required_groups):
    """the probability of controlling the nodes required to illegally modify a coin
    for a single colluding node"""
    #the target node is assumed to be colluding.  get the probabilities of controlling its group
    pnodes = group_control(nodes - 1, colluding - 1, group - 1, quorum - 1)
    return rcoin_control(pnodes, group, quorum, required_groups - 1)

def any_coin_control(nodes, colluding, group, quorum, required_groups):
    """The probability of controlling the nodes required to illegally modify a coin
    for ANY one of colluding nodes."""
    prob = coin_control(nodes, colluding, group, quorum, required_groups)
    return 1 - (1 - prob)**colluding

def even_chance_coin_control(nodes, group, quorum, required_groups):
    """The percent of colluding nodes required to get a 50 percent chance of success"""
    f = var('f')
    return find_root(coin_control(nodes, f, group, quorum, required_groups)==0.5,1,nodes)/nodes

x = var('x')

find_root(coin_control(100, x, 4, 3, 5)==0.5,1,100)/100

#control of a single group varying by group size.  x axis is percent of colluding nodes
#p1 = plot(sum(b.prob for b in group_control(100,x,3,2)),(x,1,99),rgbcolor=hue(0.2))
#p2 = plot(sum(b.prob for b in group_control(100,x,4,3)),(x,1,99),rgbcolor=hue(0.4))
#p3 = plot(sum(b.prob for b in group_control(100,x,5,4)),(x,1,99),rgbcolor=hue(0.6))
#p4 = plot(sum(b.prob for b in group_control(100,x,6,5)),(x,1,99),rgbcolor=hue(0.8))
#show(p1+p2+p3+p4)

#chance of corrupting any coin varying by group size(group - 1 == quorum). x axis is percent of colluding nodes
#p1 = plot(coin_control(100, x, 3, 2, 5),(x,1,99),rgbcolor=hue(0.2))
#p2 = plot(coin_control(100, x, 4, 3, 5),(x,1,99),rgbcolor=hue(0.4))
#p3 = plot(coin_control(100, x, 5, 4, 5),(x,1,99),rgbcolor=hue(0.6))
#p4 = plot(coin_control(100, x, 6, 5, 5),(x,1,99),rgbcolor=hue(0.8))
#p5 = plot(coin_control(100, x, 7, 6, 5),(x,1,99),rgbcolor=hue(1))
#show(p1+p2+p3+p4+p5)

#chance of corrupting any coin varying by group size (majority == quorum). x axis is percent of colluding nodes
#p1 = plot(coin_control(100, x, 3, 2, 5),(x,1,99),rgbcolor=hue(0.2))
#p2 = plot(coin_control(100, x, 4, 3, 5),(x,1,99),rgbcolor=hue(0.4))
#p3 = plot(coin_control(100, x, 5, 3, 5),(x,1,99),rgbcolor=hue(0.6))
#p4 = plot(coin_control(100, x, 6, 4, 5),(x,1,99),rgbcolor=hue(0.8))
#p5 = plot(coin_control(100, x, 7, 4, 5),(x,1,99),rgbcolor=hue(1))
#show(p1+p2+p3+p4+p5)

#chance of corrupting any coin varying by groups required. x axis is percent of colluding nodes
#p1 = plot(coin_control(100, x, 4, 3, 4),(x,1,99),rgbcolor=hue(0.2))
#p2 = plot(coin_control(100, x, 4, 3, 5),(x,1,99),rgbcolor=hue(0.4))
#p3 = plot(coin_control(100, x, 4, 3, 6),(x,1,99),rgbcolor=hue(0.6))
#p4 = plot(coin_control(100, x, 4, 3, 7),(x,1,99),rgbcolor=hue(0.8))
#p5 = plot(coin_control(100, x, 4, 3, 8),(x,1,99),rgbcolor=hue(1))
#show(p1+p2+p3+p4+p5)

#percent of colluding nodes required for even odds. x axis is network size
xs = range(1000,100000,1000)
ys = [even_chance_coin_control(x, 4, 3, 5) for x in xs]
list_plot(zip(xs,ys))