Ralph Merkle

Ви хочете надіслати зашифроване повідомлення. Одержувачеві потрібен таємний ключ, щоб його прочитати. Але як передати ключ, якщо хтось стежить за всім обміном? У статті 1978 року Ralph Merkle описав несподіваний спосіб: відправник готує багато зашифрованих загадок, одержувач навмання обирає та розв’язує одну й відкрито повертає прихований усередині ідентифікатор. Тепер обидва знають спільний ключ. Слухач також бачить ідентифікатор, але не знає, у якій загадці він містився. В описаній моделі його витрати зростають квадратично зі збільшенням завдання, а робота учасників — лінійно. Перевага квадратична, не експоненційна. Історичний прорив не є сучасною рекомендацією щодо шифрування повідомлень. [1]

Для розуміння статті 1978 року важливо знати можливості противника. Він може слухати, але зміни й підробки все ще вважаються виявними. Уявіть того, хто читає листи, а потім того, хто ще й переписує їх та підписує вашим ім’ям. Другий випадок потребує додаткового захисту: перевірки, з ким ви насправді спілкуєтеся. Різниця в обчислювальній роботі цього не вирішує. Тому загадки не роблять довільне спілкування через активного посередника безпечним. Їхній внесок — показати можливість домовитися без заздалегідь спільного таємного ключа за наведених припущень. [1]

Merkle Tree розв’язує іншу задачу. Це дерево автентифікації описано в дисертації Меркла 1979 року. Уявіть архів договорів: ви хочете перевірити конкретний договір, не завантажуючи весь архів. Для кожного елемента обчислюють хеш — короткий цифровий відбиток. Відбитки об’єднують попарно й знову хешують, поки не залишиться спільний корінь. Хешування не шифрує вміст, а дає змогу перевіряти відповідність. Для змістовної перевірки потрібен заздалегідь автентифікований корінь — підтверджений відбиток правильного архіву. Якщо шахрай може надати і власний документ, і довільний корінь, їхня відповідність нічого не доводить про початковий архів. [2]

Візьмімо збалансоване бінарне дерево з 8 елементами. Для перевірки обраного листка потрібні 3 сусідні хеші: на кожному рівні відбиток сусідньої гілки. Із власного листка та цих відбитків ви обчислюєте корінь і порівнюєте його з автентифікованим коренем. Сам листок і корінь не входять до кількості допоміжних хешів. Треба також знати структуру дерева й порядок поєднання: сусід розміщується ліворуч чи праворуч? Економія не ґрунтується на трюку з прихованими даними. Віддалені частини архіву представляють їхні відбитки, тож повні документи для цієї конкретної перевірки не потрібні. [2]

Merkle Tree підтверджує зв’язок між елементом і певним набором даних. Хибне твердження від цього не стає правдивим. У нашому архіві може бути договір із неправильним ім’ям; доказ правильно підтвердить його наявність, не виявивши помилки в імені. Так само відбиток не підтверджує повноважень автора документа. Варто розділяти запитання: чи відповідає елемент цьому кореню, звідки відомий корінь і за якими правилами приймається вміст? Це допомагає зрозуміти можливості тієї самої техніки в Bitcoin і завдання, які мають виконати інші складові системи. [2]

Bitcoin використовує Merkle Tree, щоб пов’язати транзакції із заголовком блока — його стислим записом. Корінь входить до заголовка; зміна включених транзакцій впливає на спільний відбиток. Satoshi Nakamoto описує цю конструкцію в розділі 7 whitepaper і посилається на роботу Меркла. Це свідчить про технічний вплив, а не авторство Bitcoin. Дерево не обирає чинну історію та не перевіряє підписи транзакцій замість вузлів. Bitcoin поєднує його з іншими правилами, зокрема перевіркою транзакцій і Proof of Work — доказом обчислювальної роботи. Корисніше розуміти окрему складову, ніж приписувати їй можливості всієї системи. [3]

Розділ 8 whitepaper описує SPV — спрощену перевірку платежів. Легкий клієнт працює із заголовками блоків і гілкою дерева, що пов’язує транзакцію з обраним блоком. Це заощаджує дані, але спирається на припущення щодо ланцюга з найбільшою накопиченою роботою та поведінки майнерів. Сам доказ включення не перевіряє всіх правил транзакцій так, як Full Node — вузол, що виконує повну перевірку. Він також не показує, чи був вихід витрачений пізніше: для цього потрібно знати подальші події. Початківцю важливо не плутати твердження «цей платіж є в цьому блоці» з повною перевіркою коштів, доступних зараз. [3]

Дисертація 1979 року використовує дерево автентифікації також для скінченного набору одноразових цифрових підписів. Цифровий підпис дає змогу перевірити, що власник певного таємного ключа схвалив повідомлення; це не зображення підпису на папері. Дерево може пов’язати багато перевірочних значень з одним відомим коренем. Проте в цій конструкції запас підписів обмежений і корінь згодом потрібно оновити. Це не дозволяє безмежно повторювати використання того самого одноразового ключа. Ця складніша частина роботи Меркла ілюструє спільну ідею: перевірити потрібну частину невеликим доказом і точно розуміти передумови перевірки. [2]