Advertisement
grapheo12

Random Merkle Forest

Mar 21st, 2023
933
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.32 KB | None | 0 0
  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)[0]
  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)[0]
  26.  
  27.     forest[sample].append(item)
  28.  
  29.  
  30. if __name__ == "__main__":
  31.     try:
  32.         NUM_ITEMS = int(argv[1])
  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, "%")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement