Довідка та теорія
Дерево Меркла (гешове дерево) підсумовує безліч блоків даних одним гешем — коренем Меркла. Кожен листок є гешем блоку даних; кожен внутрішній вузол — гешем конкатенації двох його нащадків.
Як воно будується
- Захешуйте кожен блок даних, утворивши рівень листків.
- Захешуйте кожну сусідню пару разом, утворивши батьківський рівень.
- Повторюйте, доки не залишиться єдиний вузол — корінь. Непарний вузол дублюється (пара із самим собою).
Виявлення підробки
Змініть один байт одного блоку — і його геш листка зміниться,
що змінить його батька, і так аж до кореня. Корінь — це
відбиток усього набору даних: будь-яку зміну можна
виявити лише за коренем.
Доказ Меркла (доказ включення)
Щоб довести, що блок належить до відомого кореня, не потрібні
всі дані — лише геш-сусід на кожному рівні шляху від
листка до кореня. Це лише O(log n) гешів.
Перевіряч перехешовує вгору й перевіряє, що результат дорівнює
довіреному кореню.
Де застосовується
Заголовки блоків Bitcoin та Ethereum зберігають корінь Меркла, щоб легкі клієнти могли перевірити транзакцію крихітним доказом. Git, IPFS, Certificate Transparency і багато баз даних використовують ту саму ідею для ефективних перевірок цілісності зі стійкістю до підробок.
Про цю симуляцію
Заради швидкості та наочності гешування тут використовує малу некриптографічну функцію змішування (у стилі FNV-1a), показану як короткий шістнадцятковий код. Реальні системи використовують SHA-256 чи Keccak, але структура дерева й логіка доказу ідентичні.
Поширені запитання
Що таке дерево Меркла?
Дерево Меркла — це двійкове дерево гешів. Листки є гешами блоків даних, а кожен батьківський вузол — гешем двох його нащадків, тож єдиний корінь підсумовує всі дані під ним.
Що таке корінь Меркла?
Корінь Меркла — це єдиний геш на вершині дерева. Він діє як компактний відбиток усього набору даних; якщо будь-який блок змінюється, змінюється й корінь.
Що таке доказ Меркла?
Доказ Меркла (доказ включення) — це набір сусідніх гешів уздовж шляху від листка до кореня. З його допомогою можна довести, що блок належить до відомого кореня, не розкриваючи інших блоків.
Чому зміна одного листка змінює корінь?
Оскільки кожен батьківський геш залежить від своїх нащадків, зміна одного листка каскадом поширюється вгору: змінюються його батько, дід і зрештою корінь. Саме це робить дерево стійким до підробок.
Наскільки великий доказ Меркла?
Доказ містить один сусідній геш на рівень дерева, тож його розмір зростає як O(log n) із кількістю листків n. Для мільйона листків це лише близько двадцяти гешів.
Де застосовуються дерева Меркла?
Вони використовуються в заголовках блоків Bitcoin та Ethereum, історії комітів Git, IPFS, журналах Certificate Transparency і багатьох розподілених базах даних для ефективної перевірки цілісності.
Що відбувається за непарної кількості листків?
Коли на рівні непарна кількість вузлів, останній вузол утворює пару з копією самого себе перед гешуванням. Це зберігає двійковість дерева на кожному рівні.
Чи є геш у цій симуляції криптографічно стійким?
Ні. Заради швидкості демо використовує малу функцію змішування у стилі FNV-1a, показану як короткий шістнадцятковий код. Реальні системи використовують SHA-256 чи Keccak, але структура дерева й логіка доказу абсолютно однакові.
Чи може доказ Меркла підтвердити відсутність блоку?
Стандартний доказ Меркла показує включення. Доведення відсутності потребує впорядкованого варіанта, як-от дерево Меркла-Патриції або розріджене дерево Меркла, що ця симуляція не охоплює.
Як легкий клієнт використовує корінь?
Легкий клієнт довіряє лише малому заголовку блоку, що містить корінь. Щоб перевірити транзакцію, він запитує лише O(log n) сусідніх гешів, перехешовує вгору й порівнює з довіреним коренем.