Концепция MAST в Биткоине

    В рамках данной статьи мы поговорим о концепции MAST и ее применении в протоколе Биткоин. Мы рассмотрим свойства, которых позволяет добиться MAST, а также пользу от его применения. Статья будет интересна читателям, которые увлекаются протоколом Биткоина и другими инновационными платежными системами. Этой теме также посвящена отдельная лекция в рамках онлайн-курса по Blockchain “MAST в Биткоине”.

    Концепция MAST подразумевает использование деревьев Меркла и абстрактных синтаксических деревьев, чтобы задавать условия траты монет на выходах транзакций. Рассмотрим по порядку, как это устроено.

    Merkle Tree


    Так можно схематично изобразить Merkle Tree.

    image

    Есть кусочки данных, для которых нужно получить контрольную сумму, т. е. вычислить хеш-значение от всех кусочков. Но вместо того, чтобы все их конкатенировать и подать на вход хеш-функции одним значением, Merkle Tree предлагает другой подход. Каждый кусочек данных хешируется по отдельности. Потом получившиеся хеш-значения попарно конкатенируются и снова хешируются. И так до тех пор, пока не получится одно хеш-значение, которое покрывает все порции данных. Это значение называется Merkle Root.

    Merkle Tree позволяет проверить вхождение отдельного кусочка данных в Merkle Root, не имея при этом всех остальных кусочков данных. Это ценное свойство.

    Допустим, пользователь имеет Merkle Root и данные одной транзакции (на схеме выше она обозначена красным цветом). Тогда пользователь может взять цепочку недостающих хеш-значений (на схеме они обозначены синим цветом) для того чтобы проверить что данная транзакция входит в Merkle Root. Недостающие хеш-значения называются Merkle Branch. Для конкретной транзакции их можно запросить у того узла сети, который хранит полный блок.

    Такой способ хеширования множества кусочков данных применяется во многих протоколах. Самые известные примеры — это хеширование транзакций, которые входят в блок, и хеширование частей файлов, которые передаются в сети BitTorrent для формирования торрент-файла.

    Abstract Syntax Tree


    Теперь давайте познакомимся с абстрактными синтаксическими деревьями (Abstract Syntax Tree). На схеме ниже изображено синтаксическое дерево, которое описывает очень простой цикл. Здесь синим цветом обозначены узлы дерева, которые означают операции, зеленым обозначены переменные, а красным — константы. Ребра дерева обозначают переходы между операциями.

    image

    Таким образом, описан цикл, который выполняется в определенной последовательности. Сначала проверяется равенство переменной А и константы 32. Если оно не выполняется, то переходим к телу цикла, где выполняется присвоение переменной А суммы двух значений: самой переменной А и константы 2. Так устроено абстрактное синтаксическое дерево в общих чертах.

    Что же такое MAST?


    Теоретическую почву мы подготовили, теперь определим, что такое MAST и какова его польза. MAST — это Merkelized Abstract Syntax Tree, где применяются идеи дерева Меркла и абстрактного синтаксического дерева для задания взаимоисключающих условий траты монет. При этом в качестве языка описания условий выступает, как обычно, Bitcoin Script. Концепция MAST позволяет повысить конфиденциальность и уменьшить размер транзакций.

    Развитие концепции и текущее положение


    Развивать и продвигать идею MAST в сообществе Биткоина начали такие люди, как Russell O’Connor, Pieter Wuille, Peter Todd и Johnson Lau. В начале 2016-го года было опубликовано предложение по улучшению протокола Биткоин под номером 114 (BIP114), где была описана спецификация одного из вариантов реализации данного подхода с использованием witness programs, которые в свою очередь были введены с обновлением SegWit. BIP114 также предлагает программную реализацию, которая добавляет новые правила достижения консенсуса в протокол Биткоина.

    Позже, в 2017-ом году, предложили альтернативный вариант реализации концепции MAST, который описан в BIP117. Он основан на BIP114 и вносит некоторые модификации. На момент 2018-го года оба предложения остаются на стадии рассмотрения.

    Отметим, что MAST может быть интегрирован в Биткоин с помощью softfork обновления протокола. И это, пожалуй, самая важная особенность данной концепции.

    MAST на схеме


    Схематично Merkelized Abstract Syntax Tree будет выглядеть так.

    image

    Здесь MAST Root — это корневое хеш-значение, которое будет помещаться в выход транзакции. Синим цветом обозначены хеш-значения веток дерева, которые ведут к условиям траты монет. Таким образом, эти ветки содержат взаимоисключающие условия, по которым монеты могут быть потрачены. Следовательно, тот, кто тратит монеты, будет использовать либо одну ветку, либо другую.

    Желтым цветом обозначены условия, которые задаются с помощью Bitcoin Script. Причем те условия, по которым монеты будут потрачены вероятнее всего, рекомендуется помещать как можно ближе к корню дерева — это сделает доказательство владения монетами меньшим по размеру.

    Проблемы с транзакциями в Биткоине


    Давайте обозначим проблемы, которые возникают при обычном задании условий траты монет с помощью Bitcoin Script. Первая, и самая важная из них, состоит в том, что получателю нужно описать или передать условия, на которых он хочет получить платеж, чтобы отправитель указал их в выходе своей транзакции. MAST и P2SH решают эту проблему.

    Вторая проблема: сложные условия занимают большой объем памяти в выходе транзакции. Как результат, отправитель должен оплачивать комиссию за установление таких сложных условий получения монет, хотя их диктует получатель. P2SH и MAST также справляются с этим, перекладывая необходимость включения больших объемов данных в транзакцию, которая будет тратить, а соответственно повышенную комиссию будет платить уже получатель, а не отправитель.

    Третья проблема состоит в том, что ScriptPubKey, который помещается в выходе транзакции, ограничен по размеру и количеству операций, т. е. OP_CODEs. Концепция MAST позволяет практически полностью уйти от этих ограничений без ущерба для надежности за счет взаимоисключающих условий.

    Четвертая проблема: при отправке монет все сразу видят условия их траты. MAST позволяет скрывать условия траты до момента самой траты. Причем раскрыты будут только те условия, которые фактически используются, а не все возможные варианты.

    Свойства, которые дает использование MAST в Биткоине


    Одно из них — повышение уровня конфиденциальности пользователей за счет скрытия условий траты, которые в итоге не использовались. Данное свойство достигается путем доказательства того, что только определенные условия входят в MAST Root и удовлетворения этим условиям.

    Другим положительным свойством является возможность задать более объемные и сложные условия траты монет. Например, с помощью MAST можно задать сотни тысяч разных вариантов мультиподписи для одного выхода транзакции. При этом условия траты монет и соответствующее доказательство владения монетами, будут весьма компактными.

    Кроме того, появляется возможность фиксировать в блокчейне данные произвольного объема без увеличения размера транзакции.

    image

    На этой схеме приведен вариант структуры MAST в соответствии с BIP114. Синим цветом обозначены хеш-значения, желтым — Bitcoin Script, а красным — произвольные данные в качестве дополнительного сообщения. В верхней части дерева включено значение версии.

    Упрощенная схема MAST



    image

    Здесь задано два взаимоисключающих условия траты монет. В первом случае монеты можно потратить, предоставив одну подпись и дождавшись наступления определенного времени, а во втором — нужно предоставить несколько подписей. Пользователи могут прибегнуть к одному из вариантов, при этом условия второго не будут разглашены.

    Применение MAST на практике


    В первом случае MAST можно применить для более оптимизированной реализации HTLC (Hashed Time-Lock Contracts), которые применяются в протоколе Lightning Network. В другом — для более оптимизированной реализации Escrow.

    MAST дает возможность реализовать очень большие конструкции с использованием multisignature. Это поможет решить такие насущные проблемы, как кража или потеря биткоинов, а в некоторых случаях позволит даже отказаться от cold storage.

    Благодаря MAST во многих случаях можно отказаться от операции OP_RETURN для добавления данных в блокчейн Биткоина. Вместо этого можно включать эти данные в дерево и при необходимости доказывать, что конкретные данные были зафиксированы в блокчейне Биткоина. При этом не понадобится увеличивать размер самого блокчейна.

    Оптимизация объема данных


    Обратим внимание на оптимизацию объема данных, которые в итоге попадают в блокчейн. Внимательно посмотрите на график ниже. На вертикальной оси обозначен объем данных в байтах, при этом сама шкала логарифмическая. На горизонтальной оси отмечается количество альтернативных условий траты монет.

    image

    Синей линией обозначена зависимость объема данных от количества условий без использования MAST. Красной линией обозначена зависимость объема данных от количества условий с использованием MAST. Голубая линия — это лимит размера Bitcoin Script для P2SH. Зеленая линия — это лимит размера Bitcoin Script в структуре witness.

    Вывод простой. Концепция MAST позволяет хранить значительно меньший объем данных при той же надежности проверки и намного большей функциональности.

    А теперь перейдем к часто задаваемым вопросам по этой теме.

    Часто задаваемые вопросы


    — Будет ли MAST Root задаваться в структуре witness или где он будет указан?

    MAST Root вместе данными, которые его определяют, будет указываться в ScriptPubKey на выходе транзакции. Эти данные будут занимать 25-35 байт и, скорее всего, они будут легко кодироваться в привычный Биткоин адрес. А в структуре witness, где доказывается владение монетами, будет указан Merkle Branch и данные, которые удовлетворяют условиям траты, например электронные подписи.

    — Будет ли расширено множество доступных OP_CODEs в языке Bitcoin Script?

    На данный момент еще не ясно, потому что предложение на стадии рассмотрения и еще могут быть внесены дополнительные правки и улучшения. Вероятно, будет добавлен такой OP_CODE, как OP_MERKLEBRANCHVERIFY, для гибкости использования MAST. Возможно, предложат еще что-то полезное, но это пока неточно.

    — Есть ли вероятность интеграции MAST в ближайшее время?

    Вероятность конечно же есть, но она мала. Ведь это обновление важное, но не срочное, поэтому оно может подождать, пока разработчики думают над другими улучшениями протокола. Позже они могут интегрировать сразу несколько улучшений в одном обновлении, как это было в случае SegWit.

    Distributed Lab

    25,00

    Blockchain Experts

    Поделиться публикацией
    Комментарии 1
      0
      У вас интересные технические статьи. Насколько я понял MAST предполагает улучшения когда скрипт используем много разных условий, но насколько часто это используется? Обычно транзакции это просто операции перевода или нет?

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое