logos-co/nomos-pocs
1
0
Fork 0
mirror of https://github.com/logos-co/nomos-pocs.git synced 2025-02-23 14:38:32 +00:00
Code Issues Packages Projects Releases Wiki Activity
nomos-pocs/cryptarchia/weighted-cryptarchia.ipynb

639 lines
190 KiB
Plaintext
Raw Permalink Normal View History

cryptarchia fork choice experiments
2024-11-25 19:28:53 +04:00
{
"cells": [
{
"cell_type": "code",
"execution_count": 27,
"id": "ad657d5a-bd36-4329-b134-6745daff7ae9",
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"from dataclasses import dataclass\n",
"from pyvis.network import Network\n",
"from pyvis.options import Layout"
]
},
{
"cell_type": "code",
"execution_count": 28,
"id": "a9e0b910-c633-4dbe-827c-4ddb804f7a9a",
"metadata": {},
"outputs": [],
"source": [
"def phi(f, alpha):\n",
" return 1 - (1-f)**alpha"
]
},
{
"cell_type": "code",
"execution_count": 246,
"id": "aa0aadce-a0be-4873-ba23-293be74db313",
"metadata": {},
"outputs": [],
"source": [
"@dataclass\n",
"class Block:\n",
" id: int\n",
" slot: int\n",
" height: int\n",
" weight: int\n",
" parent: int\n",
" refs: list[int]\n",
" leader: int"
]
},
{
"cell_type": "code",
"execution_count": 247,
"id": "a538cf45-d551-4603-b484-dbbc3f3d0a73",
"metadata": {},
"outputs": [],
"source": [
"@dataclass\n",
"class NetworkParams:\n",
" mixnet_delay_mean: int # seconds\n",
" mixnet_delay_var: int\n",
" broadcast_delay_mean: int # second\n",
" pol_proof_time: int # seconds\n",
" no_network_delay: bool = False\n",
"\n",
" def sample_mixnet_delay(self):\n",
" scale = self.mixnet_delay_var / self.mixnet_delay_mean\n",
" shape = self.mixnet_delay_mean / scale\n",
" return np.random.gamma(shape=shape, scale=scale)\n",
" \n",
" def sample_broadcast_delay(self, blocks):\n",
" return np.random.exponential(self.broadcast_delay_mean, size=blocks.shape)\n",
"\n",
" def block_arrival_slot(self, block_slot):\n",
" if self.no_network_delay:\n",
" return block_slot\n",
" return self.pol_proof_time + self.sample_mixnet_delay() + self.sample_broadcast_delay(block_slot) + block_slot"
]
},
{
"cell_type": "code",
"execution_count": 248,
"id": "24779de7-284f-4200-9e4a-d2aa6e1b823b",
"metadata": {},
"outputs": [],
"source": [
"@dataclass\n",
"class Params:\n",
" SLOTS: int\n",
" f: float\n",
" honest_stake: np.array\n",
" adversary_control: float\n",
"\n",
" @property\n",
" def N(self):\n",
" return len(self.honest_stake) + 1\n",
"\n",
" @property\n",
" def stake(self):\n",
" return np.append(self.honest_stake, self.honest_stake.sum() / (1/self.adversary_control - 1))\n",
" \n",
" @property\n",
" def relative_stake(self):\n",
" return self.stake / self.stake.sum()\n",
"\n",
" def slot_prob(self):\n",
" return phi(self.f, self.relative_stake)"
]
},
{
"cell_type": "code",
"execution_count": 269,
"id": "a90495a8-fcda-4e47-92b4-cc5ceaa9ff9c",
"metadata": {},
"outputs": [],
"source": [
"class Sim:\n",
" def __init__(self, params: Params, network: NetworkParams):\n",
" self.params = params\n",
" self.network = network\n",
" self.leaders = np.zeros((params.N, params.SLOTS), dtype=np.int64)\n",
" self.blocks = []\n",
" self.block_slots = np.array([], dtype=np.int64)\n",
" self.block_weights = np.array([], dtype=np.int64)\n",
" self.block_heights = np.array([], dtype=np.int64)\n",
" self.block_arrivals = np.zeros(shape=(params.N, 0), dtype=np.int64) # arrival time to each leader for each block\n",
"\n",
" # emit the genesis block\n",
" self.emit_block(\n",
" leader=0,\n",
" slot=0,\n",
" height=1,\n",
" weight=1,\n",
" parent=-1,\n",
" refs=[]\n",
" )\n",
" self.block_arrivals[:,:] = 0 # all nodes see the genesis block\n",
"\n",
" def emit_block(self, leader, slot, weight, height, parent, refs):\n",
" assert type(leader) in [int, np.int64]\n",
" assert type(slot) in [int, np.int64]\n",
" assert type(weight) in [int, np.int64]\n",
" assert type(height) in [int, np.int64]\n",
" assert type(parent) in [int, np.int64]\n",
" assert all(type(r) in [int, np.int64] for r in refs)\n",
"\n",
" block = Block(\n",
" id=len(self.blocks),\n",
" slot=slot,\n",
" weight=weight,\n",
" height=height,\n",
" parent=parent,\n",
" refs=refs,\n",
" leader=leader,\n",
" )\n",
" self.blocks.append(block)\n",
" self.block_slots = np.append(self.block_slots, block.slot)\n",
" self.block_weights = np.append(self.block_weights, block.weight)\n",
" self.block_heights = np.append(self.block_heights, block.height)\n",
" \n",
" # decide when this block will arrive at each node\n",
" new_block_arrival_by_node = self.network.block_arrival_slot(np.repeat(block.slot, self.params.N))\n",
"\n",
" if parent != -1:\n",
" # the new block cannot arrive before it's parent\n",
" parent_arrival_by_node = self.block_arrivals[:,parent]\n",
" new_block_arrival_by_node = np.maximum(new_block_arrival_by_node, parent_arrival_by_node)\n",
" \n",
" self.block_arrivals = np.append(self.block_arrivals, new_block_arrival_by_node.reshape((self.params.N, 1)), axis=1)\n",
" return block.id\n",
"\n",
" def emit_leader_block(self, leader, slot):\n",
" assert type(leader) in [int, np.int64], type(leader)\n",
" assert isinstance(slot, int)\n",
"\n",
" parent = self.fork_choice(leader, slot)\n",
" \n",
" refs = self.select_refs(leader, parent, slot)\n",
" return self.emit_block(\n",
" leader,\n",
" slot,\n",
" weight=self.blocks[parent].weight + len(refs) + 1,\n",
" height=self.blocks[parent].height + 1,\n",
" parent=parent,\n",
" refs=refs\n",
" )\n",
"\n",
" def fork_choice(self, node, slot) -> id:\n",
" assert type(node) in [int, np.int64], type(node)\n",
" assert isinstance(slot, int)\n",
"\n",
" arrived_blocks = self.block_arrivals[node] <= slot\n",
" return (self.block_weights*arrived_blocks).argmax()\n",
"\n",
" def select_refs(self, node: int, parent: int, slot: int) -> list[id]:\n",
" assert type(node) in [int, np.int64], node\n",
" assert type(parent) in [int, np.int64], parent\n",
" assert type(slot) in [int, np.int64], slot\n",
" assert parent != -1\n",
"\n",
" parents_siblings = [s for s in self.block_siblings(node, parent, slot) if s != parent]\n",
" # we are uniformly sampling from power_set(forks)\n",
" return list(np.array(parents_siblings)[np.random.uniform(size=len(parents_siblings)) < 0.5])\n",
"\n",
" \n",
" def block_siblings(self, node, block, slot):\n",
" blocks_seen_by_node = self.block_arrivals[node,:] <= slot\n",
" parent = self.blocks[block].parent\n",
" if parent == -1:\n",
" return [block]\n",
" successor_blocks = self.block_slots > self.blocks[parent].slot\n",
" candidate_siblings = np.nonzero(blocks_seen_by_node & successor_blocks)[0]\n",
" return [b for b in candidate_siblings if self.blocks[b].parent == parent]\n",
"\n",
" def plot_spacetime_diagram(self, MAX_SLOT=1000):\n",
" alpha_index = sorted(range(self.params.N), key=lambda n: self.params.relative_stake[n])\n",
" nodes = [f\"$N_{{{n}}}$($\\\\alpha$={self.params.relative_stake[n]:.2f})\" for n in alpha_index]\n",
" messages = [(nodes[alpha_index.index(self.blocks[b].leader)], nodes[alpha_index.index(node)], self.blocks[b].slot, arrival_slot, f\"$B_{{{b}}}$\") for b, arrival_slots in enumerate(self.block_arrivals[:-1,:].T) for node, arrival_slot in enumerate(arrival_slots) if arrival_slot < MAX_SLOT]\n",
" \n",
" fig, ax = plt.subplots(figsize=(8,4))\n",
" \n",
" # Plot vertical lines for each node\n",
" max_slot = max(s for _,_,start_t, end_t,_ in messages for s in [start_t, end_t])\n",
" for i, node in enumerate(nodes):\n",
" ax.plot([i, i], [0, max_slot], 'k-', linewidth=0.1)\n",
" ax.text(i, max_slot + 30 * (0 if i % 2 == 0 else 1), node, ha='center', va='bottom')\n",
" \n",
" # Plot messages\n",
" colors = plt.cm.rainbow(np.linspace(0, 1, len(messages)))\n",
" for (start, end, start_time, end_time, label), color in zip(messages, colors):\n",
" start_idx = nodes.index(start)\n",
" end_idx = nodes.index(end)\n",
" ax.annotate('', xy=(end_idx, end_time), xytext=(start_idx, start_time),\n",
" arrowprops=dict(arrowstyle='->', color=\"black\", lw=0.5))\n",
" placement = 0\n",
" mid_x = start_idx * (1 - placement) + end_idx * placement\n",
" mid_y = start_time * (1 - placement) + end_time * placement\n",
" ax.text(mid_x, mid_y, label, ha='center', va='center', \n",
" bbox=dict(facecolor='white', edgecolor='none', alpha=0.7))\n",
" \n",
" ax.set_xlim(-1, len(nodes))\n",
" ax.set_ylim(0, max_slot + 70)\n",
" ax.set_xticks(range(len(nodes)))\n",
" ax.set_xticklabels([])\n",
" # ax.set_yticks([])\n",
" ax.set_title('Space-Time Diagram')\n",
" ax.set_ylabel('Slot')\n",
" \n",
" plt.tight_layout()\n",
" plt.show()\n",
"\n",
"\n",
" def honest_chain(self):\n",
" chain_head = max(self.blocks, key=lambda b: b.weight)\n",
" honest_chain = {chain_head.id}\n",
" \n",
" curr_block = chain_head\n",
" while curr_block.parent >= 0:\n",
" honest_chain.add(curr_block.parent)\n",
" curr_block = self.blocks[curr_block.parent]\n",
" return sorted(honest_chain, key=lambda b: self.blocks[b].weight)\n",
"\n",
" def visualize_chain(self):\n",
" honest_chain = self.honest_chain()\n",
" print(\"Honest chain length\", len(honest_chain))\n",
" honest_chain_set = set(honest_chain)\n",
" \n",
" layout = Layout()\n",
" layout.hierachical = True\n",
" \n",
" G = Network(width=1600, height=800, notebook=True, directed=True, layout=layout, cdn_resources='in_line')\n",
"\n",
" for block in self.blocks:\n",
" # level = slot\n",
" level = block.weight\n",
" color = \"lightgrey\"\n",
" if block.id in honest_chain_set:\n",
" color = \"orange\"\n",
"\n",
" G.add_node(int(block.id), level=level, color=color, label=f\"{block.id}:s={block.slot},w={block.weight},refs={block.refs}\")\n",
" if block.parent >= 0:\n",
" G.add_edge(int(block.id), int(block.parent), width=2, color=color)\n",
" for ref in block.refs:\n",
" G.add_edge(int(block.id), int(ref), width=1, color=\"blue\")\n",
" \n",
" \n",
" return G.show(\"chain.html\")\n",
"\n",
" def run(self, seed=None):\n",
" if seed is not None:\n",
" np.random.seed(seed)\n",
" \n",
" for s in range(1, self.params.SLOTS):\n",
" if s > 0 and s % 100000 == 0:\n",
" print(f\"SIM={s}/{self.params.SLOTS}, blocks={len(self.blocks)}\")\n",
" \n",
" # the adversary will not participate in the simulation\n",
" # (implemented by never delivering blocks to the adversary)\n",
" self.block_arrivals[-1,:] = self.params.SLOTS\n",
"\n",
" self.leaders[:,s] = np.random.random(size=self.params.N) < self.params.slot_prob()\n",
" for leader in np.nonzero(self.leaders[:,s])[0]:\n",
" if self.params.adversary_control is not None and leader == self.params.N - 1:\n",
" continue\n",
" self.emit_leader_block(\n",
" leader,\n",
" s,\n",
" )\n",
"\n",
" def adverserial_analysis(self, should_plot=True, seed=0):\n",
" np.random.seed(seed)\n",
"\n",
" adversary = self.params.N-1 # adversary is always the last node in our simulations\n",
"\n",
" self.block_arrivals[adversary,:] = self.block_slots # we will say the adversary receives the blocks immidiately\n",
"\n",
"\n",
" \n",
" honest_weight_by_slot = np.zeros(self.params.SLOTS, dtype=np.int64)\n",
" honest_height_by_slot = np.zeros(self.params.SLOTS, dtype=np.int64)\n",
" for block in self.blocks:\n",
" block_weight = np.zeros(self.params.SLOTS, dtype=np.int64) + block.weight\n",
" block_weight[:block.slot] = 0\n",
" honest_weight_by_slot = np.maximum(block_weight, honest_weight_by_slot)\n",
" \n",
" block_height = np.zeros(self.params.SLOTS, dtype=np.int64) + block.height\n",
" block_height[:block.slot] = 0\n",
" honest_height_by_slot = np.maximum(block_height, honest_height_by_slot)\n",
" \n",
" for slot in range(1, self.params.SLOTS):\n",
" if honest_weight_by_slot[slot] == 0:\n",
" honest_weight_by_slot[slot] = honest_weight_by_slot[slot-1]\n",
" if honest_height_by_slot[slot] == 0:\n",
" honest_height_by_slot[slot] = honest_height_by_slot[slot-1]\n",
"\n",
" \n",
" honest_chain = self.honest_chain()\n",
" \n",
" reorg_hist = np.zeros(self.params.SLOTS, dtype=np.int64)\n",
" reorg_depths = np.array([], dtype=np.int64)\n",
"\n",
" if should_plot:\n",
" plt.figure(figsize=(20, 6))\n",
" ax = plt.subplot(121)\n",
" \n",
" adversary_active_slots = np.random.random(size=self.params.SLOTS) < phi(self.params.f, self.params.relative_stake[adversary])\n",
" all_active_slots = (self.leaders.sum(axis=0) + adversary_active_slots) > 0\n",
"\n",
" for block in self.blocks:\n",
" if block.id > 0 and block.id % 1000 == 0:\n",
" print(\"Processing block\", block)\n",
"\n",
" nearest_honest_block = block\n",
" while nearest_honest_block.height >= len(honest_chain) or honest_chain[nearest_honest_block.height-1] != nearest_honest_block.id:\n",
" nearest_honest_block = self.blocks[nearest_honest_block.parent]\n",
"\n",
" cumulative_rel_height = adversary_active_slots[block.slot+1:].cumsum()\n",
" refs = self.select_refs(adversary, block.id, slot=self.params.SLOTS)\n",
"\n",
" assert len(refs) == 0\n",
"\n",
" adverserial_weight_by_slot = block.weight + len(refs) + cumulative_rel_height\n",
" \n",
" adverserial_wins = adverserial_weight_by_slot > honest_weight_by_slot[block.slot + 1:]\n",
" \n",
" reorg_events = adverserial_wins & all_active_slots[block.slot+1:]\n",
" reorg_depths = np.append(reorg_depths, honest_height_by_slot[block.slot + 1:][reorg_events] - nearest_honest_block.height)\n",
" reorg_hist += np.append(np.zeros(block.slot, dtype=np.int64), adverserial_wins).sum(axis=0)\n",
"\n",
" if should_plot:\n",
" if reorg_events.sum() > 0:\n",
" first_slot = block.slot+1\n",
" last_slot = first_slot + np.nonzero(reorg_events)[0].max() + 1\n",
"\n",
" ax.plot(np.arange(first_slot, last_slot), adverserial_weight_by_slot[:last_slot-first_slot]-honest_weight_by_slot[first_slot:last_slot], lw=\"1\")\n",
" for event in np.nonzero(reorg_events)[0]:\n",
" plt.axvline(x = event + block.slot + 1, ymin = 0, ymax = 1, color ='red', lw=0.01)\n",
" \n",
"\n",
" if should_plot:\n",
" ax.plot(np.zeros(self.params.SLOTS), color=\"k\", label=f\"honest chain\")\n",
" _ = ax.set_title(f\"max chain weight with adversery controlling {self.params.relative_stake[adversary] * 100:.0f}% of stake\")\n",
" _ = ax.set_ylabel(\"weight advantage\")\n",
" _ = ax.set_xlabel(\"slot\")\n",
" _ = ax.legend()\n",
" \n",
" ax = plt.subplot(122)\n",
" _ = ax.grid(True)\n",
" _ = ax.hist(reorg_depths, density=False, bins=100)\n",
" _ = ax.set_title(f\"re-org depth with {self.params.relative_stake[adversary] * 100:.0f}% adversary\")\n",
" _ = ax.set_xlabel(\"re-org depth\")\n",
" _ = ax.set_ylabel(\"frequency\")\n",
"\n",
" return reorg_depths"
]
},
{
"cell_type": "code",
"execution_count": 270,
"id": "d7eef71a-aa3c-49df-a711-9c9f7f5cb4a8",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"avg blocks per slot 0.03625\n",
"Number of blocks 3625\n",
"longest chain 3625\n",
"CPU times: user 4.24 s, sys: 3.48 s, total: 7.72 s\n",
"Wall time: 7.95 s\n"
]
}
],
"source": [
"%%time\n",
"np.random.seed(0)\n",
"sim = Sim(\n",
" params=Params(\n",
" SLOTS=100000,\n",
" f=0.05,\n",
" adversary_control = 0.3,\n",
" honest_stake = np.random.pareto(10, 1000)\n",
" ),\n",
" network=NetworkParams(\n",
" mixnet_delay_mean=10, # seconds\n",
" mixnet_delay_var=4,\n",
" broadcast_delay_mean=2, # second\n",
" pol_proof_time=2, # seconds\n",
" no_network_delay=True\n",
" )\n",
")\n",
"sim.run(seed=5)\n",
"\n",
"n_blocks_per_slot = len(sim.blocks) / sim.params.SLOTS\n",
"print(\"avg blocks per slot\", n_blocks_per_slot)\n",
"print(\"Number of blocks\", len(sim.blocks))\n",
"print(\"longest chain\", max(b.height for b in sim.blocks))"
]
},
{
"cell_type": "code",
"execution_count": 271,
"id": "6680bc4d-39b9-4c9c-909f-da52f78295eb",
"metadata": {},
"outputs": [],
"source": [
"# sim.plot_spacetime_diagram()"
]
},
{
"cell_type": "code",
"execution_count": 272,
"id": "aabccc4e-8f47-403e-b7f9-7508e93ec18b",
"metadata": {},
"outputs": [],
"source": [
"# sim.visualize_chain()"
]
},
{
"cell_type": "code",
"execution_count": 274,
"id": "c5e14de5-7ff2-44e8-b825-8e6aa97f6e99",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Processing block Block(id=1000, slot=27702, height=1001, weight=1001, parent=999, refs=[], leader=453)\n",
"Processing block Block(id=2000, slot=55437, height=2001, weight=2001, parent=1999, refs=[], leader=316)\n",
"Processing block Block(id=3000, slot=82902, height=3001, weight=3001, parent=2999, refs=[], leader=595)\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAABlwAAAIhCAYAAAAreRctAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8fJSN1AAAACXBIWXMAAA9hAAAPYQGoP6dpAAEAAElEQVR4nOzdd3wUxd8H8M9ekrv0kAAhoRdpSjH0JkW6IAqCCqhgw/KzAo+KDRAR7CiIIoJUFbEgggKhSJEuAtJ7TyCE9Hplnj+W3bvL3SXXklySz/v1CtxtnZ2d3dub782MJIQQICIiIiIiIiIiIiIiIrdpSjsBREREREREREREREREZR0DLkRERERERERERERERB5iwIWIiIiIiIiIiIiIiMhDDLgQERERERERERERERF5iAEXIiIiIiIiIiIiIiIiDzHgQkRERERERERERERE5CEGXIiIiIiIiIiIiIiIiDzEgAsREREREREREREREZGHGHAhIiIiIiIiIiIiIiLyEAMuRD6oe/fuaNasmVe3WbduXYwePdqr2yxOkyZNgiRJbq27YMECSJKEvXv3Frns7NmzsWDBArf246y//voLkiThr7/+Uqf98ccfmDRpkt3lJUnCc889V6xpKowkSQ7TRqXnu+++w4wZM4pl28o1c+7cOXXa6NGjUbduXavlSvM+8sYbbyAuLg5RUVEIDAxE/fr1MWbMGJw/f95mWb1ej8mTJ6Nu3brQ6XRo0qQJZs6cabPcli1bEBcXh7CwMHTt2hVHjhyxWeZ///sfunXrBiGE149p5syZuOWWW6DVaiFJElJTU93eljfKR926dTFw4ECPtkFERETkjpJ4zty+fTsmTZpk95mrNJ6D7D2DO3qmO3fuHCRJwkcffeTWvi5evIjBgwejfv36CAkJQUREBOLi4jBr1iwYDAab5c+cOYMhQ4agUqVKCA0NRe/evbFv3z6rZYQQmDhxImrUqIHo6Gi88MILyMvLs1omLS0N1atXx/z5891KtzvKWt0HEZU/DLgQVRC//vor3nrrrdJOhtOeeOIJ7Nixo9j3UxIBl1atWmHHjh1o1aqVOu2PP/7A5MmTi3W/VL4UZ8DFWaV5H0lNTcXw4cOxcOFCrFmzBuPHj8eqVavQvn17JCcnWy377LPPYtq0afjf//6HtWvXYvDgwXjxxRfx3nvvWW1v8ODBaNu2LX755RdERERgyJAhMBqN6jI7d+7E/PnzMWfOHLcDwI7s378fL7zwAnr06IGNGzdix44dCAsLc3t7vlA+iIiIiHzZ9u3bMXnyZI9+5OJNAwYMwI4dOxAbG6tOK65nuqysLISHh+Ott97CypUr8cMPP6BLly54/vnn8fTTT1stm5SUhDvuuAMnTpzA/Pnz8eOPPyI3Nxfdu3fH8ePH1eUWL16Mjz/+GFOnTsUXX3yBZcuW4cMPP7Ta1oQJE9CoUSM8+uijXj8mIiJf5V/aCSCikhEXF1faSXBJzZo1UbNmzdJOhleEh4ejQ4cOpZ0Mn5aTk4PAwECvV2oXlJ2djeDg4GLdhy8wGo0wGAzQ6XRe3W5p3ke++OILq/fdu3dHvXr1cNddd+G3337DY489BgA4fPgw5s2bh6lTp+L//u//1GWTk5Px7rvv4umnn0ZUVBR27NiBvLw8fPHFFwgICMBtt92GGjVq4OTJk2jSpAn0ej3GjBmDV199FU2aNPH68Rw+fBgA8OSTT6Jdu3Ze3z4RERGVH77wDKvX6yFJEvz9WY3kLVWrVkXVqlVLZF9NmjTBwoULrab1798f165dw8KFC/HFF1+o3x0+/PBDJCUlYfv27ahTpw4AoEuXLmjQoAHefvttLFu2DACwevVqjBw5Um1NcvLkSaxcuRJvvvkmAGDHjh1YsGAB/v3332L/nlfaSur6KKnvzUTkGbZwoXJD6YLq4MGDGDZsGCIiIhAVFYWxY8fCYDDg+PHj6NevH8LCwlC3bl188MEHVuvn5uZi3LhxuP3229V1O3bsiN9++81quR9++AGSJGHWrFlW0ydOnAg/Pz/Ex8cXmdbvvvsOHTt2RGhoKEJDQ3H77bdj3rx5Nsvt2bMHd9xxB4KDg1G/fn1Mnz4dJpPJ5TQDts1qlW6uvv/+e7zxxhuoXr06wsPD0atXL6tfrdhz+PBhSJKE5cuXq9P++ecfSJKE2267zWrZQYMGoXXr1lbTli1bho4dOyIkJAShoaHo27cv/v33X6tl7HUplpeXh3HjxiEmJgbBwcHo2rUr/vnnH4dNhjMyMvDMM8+gSpUqqFy5MoYMGYIrV65Y5cnhw4exefNmSJIESZJsulCyNGzYMJvju/vuu23yYt++fZAkCb///jsA2y7FRo8erVYeK/st2JQckH8x1LRpUwQHB6Nly5ZYtWqVw7QpXCkT6enpePLJJ1G5cmWEhoaiX79+OHHihNUyK1asgCRJ2LBhg836X375pXrNKfbu3YtBgwap3T7FxcXhxx9/tFpPaTq/bt06PPbYY6hatSqCg4ORl5eHpKQkjBkzBrVq1YJOp0PVqlXRuXNnrF+/3mob69evR8+ePREeHo7g4GB07tzZJo1KGdq3bx+GDh2KyMhINGjQAIsXL4YkSXZbUL3zzjsICAiwKif2HDt2DMOHD0e1atWg0+lQu3ZtPPLII1ZN6A8dOoR77rkHkZGRCAwMxO23327zJcfZ67B79+5YvXo1zp8/b1VmAHP3Ah988AHeffdd1KtXDzqdDps2bQIArFy5Eh07dkRwcDDCwsLQu3dvt1uPeXIfEULgvffeQ506dRAYGIg2bdogPj4e3bt3R/fu3d1Kj/IF1fKLzYoVKyCEsPkV3aOPPoqcnBysWbMGgHyt6HQ6BAQEAABCQ0PV6QDw0UcfIT8/HxMmTHA5XfPnz0fLli0RGBiIqKgoDB48GEePHlXnd+/eHQ899BAAoH379pAkqdBuD4q6LgorHwAwefJktG/fHlFRUQgPD0erVq0wb948p7pJmz17Nvz9/TFx4kR1mjPXHxEREbnH0TMsID9PzZ49G7fffjuCgoIQGRmJoUOH4syZM05v35Vn1MWLF2PcuHGoUaMGdDodTp06BQCYO3cuGjVqBJ1Oh1tvvRXfffed3e5o7dHr9XjllVfU73RdunTB7t277S6bmJiIp556CjVr1oRWq0W9evUwefJkqy6wLJ+Fp06ditq1a6vPmpbPJ5MmTVJ/jFOvXj31ecmy22cAWLNmDVq1aoWgoCA0adLEqa6w2rZtiwEDBlhNa968OSRJwp49e9Rpv/zyCyRJwn///QfAtkuxop7pFJ988gnq1auH0NBQdOzYETt37iwyjY5UrVoVGo0Gfn5+6rRff/0Vd955pxpsAeQfEQ4ZMgS///67mv+5ubkICQlRlwkNDVWfpZUfL7322mto3LixS2ly9tnVmbJ04MABSJJkt77lzz//hCRJWLlypTrt5MmTGDFiBKKjo6HT6dC0aVObH34Vdn1kZ2dj/PjxqFevnvpdoE2bNvj+++/V9ffu3YsHH3wQdevWRVBQEOrWrYvhw4fbdJXs6Hvztm3b1O9gBS1atMim3BFRKRBE5cTEiRMFANG4cWMxZcoUER8fL1555RUBQDz33HOiSZMm4vPPPxfx8fHi0UcfFQDEzz//rK6fmpoqRo8eLRYvXiw2btwo1qxZI8aPHy80Go1YuHCh1b6efvppodVqxZ49e4QQQmzYsEFoNBrx5ptvFpnOt956SwAQQ4YMEcuXLxfr1q0Tn3zyiXjrrbfUZbp16yYqV64sGjZsKL766isRHx8vnn32WQHAKi2upLlOnTpi1KhR6vtNmzYJAKJu3bpi5MiRYvXq1eL7778XtWvXFg0bNhQGg6HQ44iNjRVjxoxR30+fPl0EBQUJAOLy5ctCCCH0er0IDw8Xr7zyirrc1KlThSRJ4rHHHhOrVq0Sv/zyi+jYsaMICQkRhw8fVpdTzqel4cOHC41GI1577TWxbt06MWPGDFGrVi0RERFhdWzffvutACDq168vnn/+ebF27VrxzTffiMjISNGjRw91uX379on69euLuLg4sWPHDrFjxw6xb98
"text/plain": [
"<Figure size 2000x600 with 2 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"reorgs = sim.adverserial_analysis()"
]
},
{
"cell_type": "code",
"execution_count": 277,
"id": "0bdf3ada-059a-4145-bb12-8a15d022bb9f",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.01013\n"
]
}
],
"source": [
"print(len(reorgs[reorgs > 10]) / sim.params.SLOTS)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "467972af-de30-4a5d-9e62-f8e17a7f9813",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"simulating 1/10\n",
"simulating 2/10\n",
"simulating 3/10\n",
"simulating 4/10\n",
"simulating 5/10\n",
"simulating 6/10\n",
"simulating 7/10\n",
"simulating 8/10\n",
"simulating 9/10\n",
"simulating 10/10\n",
"finished simulation, starting analysis\n"
]
}
],
"source": [
"np.random.seed(0)\n",
"stake = np.random.pareto(10, 100)\n",
"\n",
"sims = [Sim(\n",
" params=Params(\n",
" SLOTS=100000,\n",
" f=0.05,\n",
" adversary_control = i,\n",
" honest_stake = stake\n",
" ),\n",
" network=NetworkParams(\n",
" mixnet_delay_mean=10, # seconds\n",
" mixnet_delay_var=4,\n",
" broadcast_delay_mean=2, # second\n",
" pol_proof_time=10, # seconds\n",
" no_network_delay=False\n",
" )\n",
") for i in np.linspace(1e-3, 0.3, 10)]\n",
"\n",
"for i, sim in enumerate(sims):\n",
" print(f\"simulating {i+1}/{len(sims)}\")\n",
" sim.run(seed=0)\n",
"\n",
"print(\"finished simulation, starting analysis\")\n",
"advs = [sim.adverserial_analysis(should_plot=False) for sim in sims]"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "a8a2f501-aa97-4a80-8206-1a5862006ebc",
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAB38AAAKjCAYAAAAd5cXtAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8fJSN1AAAACXBIWXMAAA9hAAAPYQGoP6dpAAB+uklEQVR4nOzde5yWZZ0/8M8zw1k5KAozrIiYJxAPCOl6xlQ8ZZ5SK0UzK01NBXVXtF+ZqaxmaOVKsplKrofKLGptkzJNV0tF8VAblqnoHCIPMYg6HOb5/UEz6zSDzoPAgw/vt6/rtcx13891f5+NLtMP3+suFIvFYgAAAAAAAAB4X6sqdwEAAAAAAAAAvHfCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADdyl3A2qilpSX19fXp27dvCoVCucsBAAAAAGAVKhaLWbhwYYYMGZKqKj1SAFQO4W8n6uvrM3To0HKXAQAAAADAavTiiy9mk002KXcZALDKCH870bdv3yTJHjk43dK9zNUAAAAAALAqLc2SPJC72v5dMABUCuFvJ1qPeu6W7ulWEP4CAAAAAFSU4vL/47V/AFQaLzMAAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADCXwAAAAAAAIAKIPwFAAAAAAAAqADdyl3A2qC5uTnNzc1tPzc1NZWxGgAAAAAAAIDS6fxNMmXKlPTv379tDB06tNwlAQAAAAAAAJSkUCwWi+Uuotw66/wdOnRoxuWwdCt0L2NlAAAAAACsakuLS3JvfpwFCxakX79+5S4HAFYZxz4n6dmzZ3r27FnuMgAAAAAAAABWmmOfAQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACqA8BcAAAAAAACgAgh/AQAAAAAAACpAt3IXsDZr2XW7tHTrVe4y1pgeL71a7hLKYum8unKXsOa1LCt3BQAAAAAAAKxiOn8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKACCH8BAAAAAAAAKoDwFwAAAAAAAKAClD38vfbaazN8+PD06tUrY8aMyf333/+O9993330ZM2ZMevXqlc033zzf+ta32l3/4Q9/mLFjx2bAgAFZb731suOOO+a73/3u6vwKAAAAAAAAAGVX1vD39ttvz9lnn50LL7wwjz/+ePbcc88cdNBBmTdvXqf3P/fcczn44IOz55575vHHH88FF1yQM888M3fccUfbPRtuuGEuvPDCPPTQQ3nyySdz0kkn5aSTTsrPf/7zNfW1AAAAAAAAANa4QrFYLJbr4bvsskt22mmnTJs2rW1uxIgROfzwwzNlypQO9//rv/5rZs6cmf/93/9tmzv11FPzxBNP5KGHHlrhc3baaacccsgh+cpXvtKlupqamtK/f//stesX0q1brxK+0ftbj5deLXcJZbF0Xl25S1jzWpaVuwIAAAAAKJulxSW5Nz/OggUL0q9fv3KXAwCrTNk6fxcvXpzZs2dn/Pjx7ebHjx+fBx98sNPPPPTQQx3uP+CAA/Loo49myZIlHe4vFov55S9/mblz52avvfZaYS3Nzc1pampqNwAAAAAAAADeT8oW/r788stZtmxZBg8e3G5+8ODBaWxs7PQzjY2Nnd6/dOnSvPzyy21zCxYsyPrrr58ePXrkkEMOyTe/+c3sv//+K6xlypQp6d+/f9sYOnToe/hmAAAAAAAAAGteWd/5mySFQqHdz8ViscPcu93/j/N9+/bNnDlz8sgjj+TSSy/NpEmTcu+9965wzcmTJ2fBggVt48UXX1yJbwIAAAAAAABQPt3K9eCNNtoo1dXVHbp858+f36G7t1VNTU2n93fr1i0DBw5sm6uqqsoWW2yRJNlxxx3zv//7v5kyZUrGjRvX6bo9e/ZMz54938O3AQAAAAAAACivsnX+9ujRI2PGjMmsWbPazc+aNSu77bZbp5/ZddddO9x/9913Z+zYsenevfsKn1UsFtPc3PzeiwYAAAAAAABYS5Wt8zdJJk2alAkTJmTs2LHZddddM3369MybNy+nnnpqkuXHMdfV1WXGjBlJklNPPTXXXHNNJk2alM985jN56KGHcv311+fWW29tW3PKlCkZO3ZsPvCBD2Tx4sW56667MmPGjEybNq0s3xEAAAAAAABgTShr+HvsscfmlVdeycUXX5yGhoaMGjUqd911V4YNG5YkaWhoyLx589ruHz58eO66665MnDgx//7v/54hQ4bkG9/4Ro466qi2exYtWpTTTjstL730Unr37p1tttkmN998c4499tg1/v0AAAAAAAAA1pRCsVgslruItU1TU1P69++fvXb9Qrp161XuctaYHi+9Wu4SymLpvLpyl7DmtSwrdwUAAAAAUDZLi0tyb36cBQsWpF+/fuUuBwBWmbK98xcAAAAAAACAVUf4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFUD4CwAAAAAAAFABhL8AAAAAAAAAFaBbuQtYm702oneqe/QqdxlrzHoDa8pdQlmsv+jNcpewxrX8bUG5S1jjikuXlLuE8igWy10BAAAAAACwhuj8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAAAAKgAwl8AAAAAAACACiD8BQAAAAA
"text/plain": [
"<Figure size 4000x4000 with 2 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"max_reorg_depth = max(a.max() if len(a) > 0 else 0 for a in advs)\n",
"\n",
"\n",
"heatmap = np.zeros((len(advs), max_reorg_depth), dtype=np.int64)\n",
"\n",
"for i, adv in enumerate(advs):\n",
" for depth in range(max_reorg_depth):\n",
" heatmap[i][depth] = (adv == depth).sum()\n",
"\n",
"plt.figure(figsize=(40,40))\n",
"ax = plt.subplot(121)\n",
"im = ax.imshow(heatmap)\n",
"\n",
"_ = ax.set_yticks(np.arange(len(sims)), labels=[f\"{s.params.adversary_control:.2f}\" if i % 2 == (len(sims) - 1) % 2 else None for i, s in enumerate(sims)])\n",
"_ = ax.set_xticks(np.arange(max_reorg_depth), labels=[r if r % (max_reorg_depth // 10) == 0 else None for r in range(max_reorg_depth)])\n",
"_ = ax.set_xlabel(\"reorg depth\")\n",
"_ = ax.set_ylabel(\"adversary stake\")\n",
"\n",
"ax = plt.subplot(1,10,6)\n",
"scale = heatmap.max()\n",
"ax.imshow(np.arange(scale+1).reshape((1, scale+1)).T, extent=(1,0,1,0))\n",
"_ = ax.set_yticks(np.arange(scale+1) / scale, labels = [r if r % (scale // 10) == 0 else None for r in range(scale+1)])\n",
"_ = ax.set_xticks([], minor=False)\n",
"_ = ax.set_ylabel(\"frequency\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c9b9cf70-3849-4b3d-9110-a6779df8c83f",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "36dd222a-cdf6-4fc9-8ca5-6d7acffa153f",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.9"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Reference in New Issue Copy Permalink