Деревья и доказательства Меркла
Нашли на просторах твиттера интересный тред на тему “Деревья и доказательства Меркла” и перевели его, чтобы вы тоже могли с ней ознакомиться.
Разобравшись с понятием Дерево Меркла, станет понятно, как работает технология Блокчейн. Вот что предстоит узнать:
- Что такое Деревья Меркла, и как они сжимают большое количество информации?
- Доказательство Меркла что это такое, и как оно работает?
- Почему Дерево Меркла эффективно?
Что такое деревья Меркла и как они сжимают большое количество информации
Разбираться в теме мы начнём с понятия хеширования.
Хеширование — это преобразование вводных данных произвольного содержания и размера в одну строку.
Вводные данные получают уникальную строку на выходе, даже если эти данные почти идентичны.
Дерево Меркла использует хеширование для преобразования больших объемов информации в одну строку. Это позволяет доказать, что транзакция была включена в больший набор данных.
Технология названа в честь Ральфа Меркла, который предложил её в 1987 году. Еще её называют хэш-деревом.
Двоичное дерево Меркла — структура данных, которая создана путем объединения хэшей.
Данные объединяются в хэш, два полученных результата объединяются и снова хэшируются. Этот цикл повторяется, пока не останется одна строчка.
Верхний хэш (Top Hash) — это значение, которое содержит в себе всю информацию вводных данных. Он же корневой хэш или корневой узел.
Если данные будут изменены, создаваемый ими хэш будет другим, включая корневой узел.
Как результат, вместо данных, вы получаете одну строчку. Это удобно при сравнении информации, потому что вам не нужно сравнивать её всю, достаточно будет сравнить один корень с другим (Top Hash). Если корни совпадают, наборы данных одинаковы.
Доказательство Меркла что это такое, и как оно работает
Деревья Меркла преобразовывают данные в хэш, поэтому они работают только в одном направлении: Легко построить дерево из необработанных данных, но восстановить данные из него невозможно. Корень Меркла можно публиковать публично, не опасаясь раскрытия данных.
Возникает вопрос: может ли дерево Меркла делать что-либо, кроме как проверять ВЕСЬ набор данных?
Да! Можно проверить, есть ли в дереве определённые данные, или нет.
Есть такое понятие как Доказательство Меркла. Устанавливается оно путем предоставления конкретных данных и промежуточных хэшей верификатору, которые позволяют воссоздать дерево.
Если вычисленный корневой узел совпадает с существующим узлом, верификатор убедиться в том, что информация находится в наборе данных.
Почему Дерево Меркла эффективно
В примерах есть только 4 набора информации, но на практике, деревья могут быть развернуты для миллионов, миллиардов и триллионов данных.
По мере увеличения набора данных, деревья Меркла становятся все более и более эффективными. Как по согласованию, так и по проверке.
Деревья Меркла обеспечивают единый уникальный вывод, файл размером в несколько ГБ можно сжать до размера одной строки.
Хорошо спроектированная сеть может поддерживать множество ресурсов локально и координировать их, передавая чрезвычайно легкий корневой хэш.
Итоги
В начале говорилось: “Разобравшись с понятием дерево Меркла вы так же сможете понять как работает технология блокчейн.”
Блокчейн работает по этому же принципу и в его случае данные — это транзакции. Множество транзакций хэшируются в одну строчку и записываются в блок, этот блок соединяется со следующими транзакциями, и полученный хэш вноситься в следующий блок. Получается каждый новый блок содержит в себе информацию предыдущего, а тот предыдущего и так аж до самой первой транзакции в сети.
Деревья Меркла это способ умещения информации в одну строку. Они уменьшают объем информации и позволяют мобильно и быстро сравнивать информацию при надобности. Но достать исходную информацию из корневого хэша не получиться.