Как я могу преобразовать древовидную структуру JSON в дерево Меркла

Question

Я запускаю веб-сервер, на котором получаю данные в формате JSON и планирую хранить их в базе данных NoSQL. Вот пример:

      data_example = {
    "key1": "val1",
    "key2": [1, 2, 3],
    "key3": {
        "subkey1": "subval1",
        .
        .
        }
      }

У меня были мысли об использовании дерева Меркла для представления моих данных, поскольку JSON также представляет собой древовидную структуру.

По сути, я хочу хранить свои данные в (или как) более безопасной децентрализованной древовидной структуре. Многие объекты будут иметь доступ для создания, чтения, обновления или удаления (CRUD) записи из него. Эти операции CRUD в идеале должны быть проверены другими объектами в сети, которые также будут содержать копию базы данных. Прямо как в блокчейне.

У меня проблема с дизайном / концепцией, и я пытаюсь понять, как превратить свой JSON в древовидную структуру Меркла. Это мой класс Node:

      class Node:
    """ class that represents a node in a merkle tree"""
    def __init__(data):
          self.data = data
          self.hash = self.calculate_some_hash()  # based on the data or based on its child nodes

Меня интересует концепция / дизайн этого, поскольку я не мог понять, как это может работать. Есть идеи, как сохранить / сохранить мой объект data_example в дереве Меркла? (Является ли это возможным?)

Answer 1

Вы можете создать дерево Меркла, сначала преобразовав свой словарь в форму объекта класса, а затем рекурсивно пройдя по дереву, хешируя сумму хэшей дочерних узлов. Поскольку дерево Меркла требует единственного корневого узла, любые входные словари, которые имеют более одного ключа на самом верхнем уровне, должны стать дочерним словарем пустого корневого узла (с ключом по умолчанию None):

      data_example = {
  "key1": "val1",
  "key2": [1, 2, 3],
  "key3": {
     "subkey1": "subval1",
     "subkey2": "subval2",
     "subkey3": "subval3",
    }
}
class MTree:
   def __init__(self, key, value):
      self.key, self.hash = key, None
      self.children = value if not isinstance(value, dict) else self.__class__.build(value, False) 
   def compute_hashes(self):
       #build hashes up from the bottom
       if not isinstance(self.children, list):
          self.hash = hash(self.children)
       else:
          self.hash = hash(sum([i.compute_hashes() for i in self.children]))
       return self.hash
   @classmethod
   def build(cls, dval, root=True):
       #convert non-hashible values to strings
       vals = [(a, str(b) if isinstance(b, list) else b) for a, b in dval.items()]
       if root:
          if len(vals) > 1:
             return cls(None, dval)
          return cls(vals[0][0], vals[0][-1])
       return [cls(a, b) for a, b in vals]  
   def __repr__(self):
      return f'{self.__class__.__name__}({self.hash}, {repr(self.children)})'        

---

      tree = MTree.build(data_example) #create the basic tree with the input dictionary
_ = tree.compute_hashes() #get the hashes for each node (predicated on its children)
print(tree)

Выход:

      MTree(-1014944431667870016, [MTree(-7962592415126961561, 'val1'), MTree(6194701856889846614, '[1, 2, 3]'), MTree(-1552896882644449020, [MTree(-6078179965770983042, 'subval1'), MTree(-1511576603232499350, 'subval2'), MTree(6036859686359033372, 'subval3')])])