Читаю интернет и не до конца понимаю одну вещь. Есть Дерево Меркля (или Меркле). Допустим оно имеет N-количество отсортированных "листьев", представляющими блоки данных. Как проверяется, что конкретный "блок" не находится в дереве?
Ответ
Проверка принадлежности происходит очень просто - считается хеш блока, а потом просто проверка с хешом во всех листьях. Если есть совпадение, дальше проверяется валидность самого дерева, проходом от этого листа до корня дерева. Например, если это L2 на вашем рисунке, тогда проверяется Hash(Hash(0-0), Hash(0-1)), и дальше корневой хеш: Hash(Hash(0), Hash(1))
Свойства криптографических хеш-функций гарантируют, что произведя всего несколько простых вычислений хеша над небольшими объемами данных, мы гарантируем, что этот блок данных действительно входит в хеш в корне дерева.
Можете представить себе, если бы весь блок данных занимал несколько гигабайт, а вам нужно проверить принадлежность небольшой части, допустим 1 мб.
Еще хочу добавить, что операция проверки блока в дереве, это не то, ради чего используют дерево Меркля в blockchain-технологиях. Основное преимущество, это очень быстрый пересчет хеша при поступлении новых данных. А так же быстрый пересчет хеша, при удалении блока данных.
Пример с биткоин. Майнер непрерывно изменяет несколько байт в блоке, и считает хеш, что бы получить хеш начинающийся с множества нулей. В это время приходят новые транзакции, и нужно быстро пересчитать хеш в корне дерева (который является частью блока). Для этого понадобится всего O(log n) операций пересчета хеша. Если майнер решил выкинуть транзакцию с блока, и включить другую (с большей комиссией), все так же нужно O(log n) пересчетов.
Комментариев нет:
Отправить комментарий