Merkle Tree
Дерево Меркель (Merkle Tree) – структура данных, основанная на хеше(Hash). Хэш-структура данных присваивает данные ключу. Простая форма этого — быстрый набор телефоне. Назначение номера телефона для каждой клавиши является структурой, основанной на хэше.
Для проверки данных используются Merkle Tree. Он очень эффективен, потому что он используется вместо полного файла информации.
Merkle Tree обычно имеют коэффициент двух ветвей, что означает, что у каждого узла может быть два дочерних узла. Опять же, обычно Merkle Tree реализуются как двоичные деревья (вкл. / Выкл. Или 1/0), но опять же они могут быть созданы как дерево с n дочерними элементами на узел.
Методы
Было бы слишком сложно копировать длинные сложные файлы по всем системам. Merkle Tree используется для отправки сообщения в сеть путем отправки только хеша для сравнения. Каждый хэш может хэшировать, тогда хеши хэшей могут хешировать. Единственный раз, когда вам нужно разбить большой хеш, — когда обнаруживается разница. Когда различие обнаруживается в хеше, оно рассматривает ветви этого хэша. Поскольку компьютеры могут выполнять сразу несколько действий, он может запускать несколько хеш-сравнений и делать это сравнение довольно быстро. Для распределенных систем просто неэффективно проверять весь файл на наличие проблем. Для одноранговых систем это помогает проверять информацию даже из ненадежного источника. Возможно сделать это, используя самый надежный источник, и хеш начинается сверху и сравнивает элементы друг с другом.
Протокол отправки хэша
Протокол отправки хэша следующий:
- Компьютер 1 отправляет файл на компьютер 2
- Компьютер 2 проверяет хэш на корне дерева Merkle
Если нет никакой разницы, процесс завершен. в противном случае, поскольку существует разница, компьютер 2 запрашивает корни двух поддеревьев этого хэша. Компьютер 1 создает необходимые хэши и отправляет их на компьютер 2. Повторите шаги 4 и 5 до тех пор, пока не будут найдены блоки данных. Возможно найти более одного блока данных, в котором есть различия / ошибки.