validator_rotation.py

tot_val = 10000
tot_per_shard = 200
bad_ratio = .20
rounds = 5000
compromised_ratio = 1. / 3

assert tot_val % tot_per_shard == 0

bad = int(bad_ratio * tot_val)
good = tot_val - bad

val = [1] * bad + [0] * good

from random import sample

def rotate():
    cur_val = sample(val, tot_val)
    shards = [cur_val[i:i+tot_per_shard] for i in range(0, tot_val, tot_per_shard)]
    return shards

def badness(shards):
    return max(sum(x) for x in shards)

def badness_ratio_experiment():
    return badness(rotate()) / tot_per_shard

max_ratio = 0.
dist = []

compromised_rounds = 0

for _ in range(rounds):
    rat = badness_ratio_experiment()
    dist.append(rat)

    if rat >= compromised_ratio:
        compromised_rounds += 1

    if rat > max_ratio:
        max_ratio = rat
        print("Max adversarial percent: {}%".format(round(100 * max_ratio, 2)))

print("Number of compromised rounds:", compromised_rounds)

try:
    import matplotlib.pyplot as plt
    plt.hist(dist)
    plt.show()
except:
    print("Install matplotlib to see final distribution.")