 # Random Merkle Forest

Mar 21st, 2023
794
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import random
2. from sys import argv
3. from math import log2
4.
5. forest = []
6.
7. def insert_in_forest(item):
8.     if item % 1000 == 0:
9.         print("Processing item", item)
10.
11.     # print("Structure of forest:", [len(x) for x in forest])
12.     prob_gen_new_tree = 1 /(1 + 1.2 * log2(1 + 0.5 * len(forest)))
13.     sample = random.choices([0, 1], weights=[1 - prob_gen_new_tree, prob_gen_new_tree], k=1)
14.
15.     if sample == 1:
16.         # print("Creating new tree")
17.         forest.append([item])
18.         return
19.     # print("Adding to old trees")
20.     min_len = min([len(x) for x in forest])
21.     weights = [0.9**(len(x) - min_len) for x in forest]
22.     sample = random.choices(
23.         list(range(len(forest))),
24.         weights=weights,
25.         k=1)
26.
27.     forest[sample].append(item)
28.
29.
30. if __name__ == "__main__":
31.     try:
32.         NUM_ITEMS = int(argv)
33.     except:
34.         print("Usage: python3 rmf.py <number of items>")
35.         exit(0)
36.
37.     for i in range(NUM_ITEMS):
38.         insert_in_forest(i)
39.
40.     print("Number of trees:", len(forest))
41.     print("Average size:", sum([len(x) for x in forest]) / len(forest))
42.
43.     total_rmf = sum([len(x) - 1 for x in forest])
44.     total_mf = NUM_ITEMS - 1
45.     # rmf_sig = len(forest)
46.     # mf_sig = 1
47.     print("Total number of internal nodes in Merkle forest:", total_rmf)
48.     print("Total number of internal nodes in full merkle tree:", total_mf)
49.     print("Savings:", (total_mf - total_rmf) / (total_mf) * 100, "%")