Quote from: imhoneer on June 27, 2017, 02:29:33 PM

Смысл дерева меркля - это получения одного хеша из нескольких хешей. Т.е. имеем изначально 4 транзакции, группами по 2 хешируем и получаем 2 хеша, потом эти 2 хеша хешируем и получаем один конечный хеш. Если транзакций нечетное количество, то одна из них клонируется в недостающую группу.

Мне тоже кажется это не совсем рационально, слишком много операций, уверен, что можно как-то сразу сложить хеши всех транзакций и найти конечный хеш.

Да, структурирование данных в дерево Меркля затрачивает много ресурсов, но поскольку в биткойне был заложен алгоритм PoW - то там это было как бы к месту. Есть и другие, боле быстрые способы контроля целостности данных. Но в дереве Меркля важно то, что контролируется не только сами данные, но и структура самого дерева, которая может быть полезной при восстановлении данных. Например, берется контрольная сумма от объёмного каталога файлов. Нам нужно проверить его целостность. Если мы видим, что контрольная сумма не совпадает - то можно спуститься по дереву на один уровень ниже и проверить два хэша - в случае повреждения одного файла в нашем каталоге один из хэшей нижележащего уровня будет совпадать, а другой нет. Далее мы опять спускаемся на один уровень, но только там, где хэш не совпадает. Таким образом мы очень быстро доберёмся до повреждённого файла. Поскольку там получается степенная функция, то проход по дереву Меркля для поиска повреждённых данных занимает всегда очень мало времени. Буквально за несколько проверок хешей мы можем найти повреждённый файл, даже если этих файлов триллионы. Таким образом, алгоритм Меркля "долго" хеширует, но быстро находит повреждённые данные. И конечно, таким образом можно искать не только повреждённые, но и просто изменённые файлы.