13 октября 2016, 19:56 — Аарон ван Вирдум
Предлагаемый софтфорк SegWit, который должен состояться в ближайшее время, расширит потенциал Биткойна разными способами. Одной из потенциально перспективных инноваций, которую SegWit делает возможной, является MAST (Merkelized Abstract Syntax Trees — меркелизованные абстрактные синтаксические деревья). Хотя предназначен прежде всего для повышения гибкости смарт-контрактов, MAST в то же время повысит масштабируемость и конфиденциальность платформы.
Идея MAST родилась у Blockstream-разработчика Расселла О’Коннора (Russell O’Connor), Blockstream- и Core-разработчика д-ра Питера Велле (Pieter Wuille), и Core-разработчика Питера Тодда (Peter Todd). Она была недавно описана в предварительном предложении по улучшению Биткойна (BIP) Core-разработчиком д-ром Джонсоном Лау (Johnson Lau).
Несмотря на свой потенциал, MAST на удивление прост.
P2SH: Введение для начинающих
Одна часть MAST основана на P2SH, который используется в определенных транзакциях Биткойна в течение уже нескольких лет.
Все операции Биткойна в сущности «запирают» биткойны в выходах, которые обычно содержат Биткойн-адреса. Биткойны запираются для того, чтобы их можно было затем «освободить» (и вновь «запереть») в другой транзакции. Таким образом биткойны переходят с одного адреса в другой.
Это «запирание» осуществляется на практике с помощью сценария — пары строк кода. Для стандартных транзакций, сценарий добавляется в выход транзакции и определяет необходимые условия для траты данных биткойнов в следующей транзакции.
Большинство нестандартных Биткойн-транзакций, таких как multisig или CheckLockTimeVerify, используют немного более сложную схему, именуемую «P2SH» (Pay to Script Hash). С P2SH биткойны по-прежнему запираются в сценарии, но сам сценарий не добавляется в выход транзакции. Вместо этого, сценарий хэшируется, то есть шифруется и сжимается в короткую и случайную на вид последовательность чисел. Эта последовательность чисел не может быть использована для восстановления исходного сценария. Однако имея исходный сценарий, можно легко воссоздать последовательность чисел путем повторного хэширования. Хэш сценария — это и есть то, что включается в выход транзакции. Для того, чтобы потратить P2SH-выход в следующей транзакции, недостаточно просто выполнить условия, определенные в сценарии, так как узлы сети Биткойна знают только о хэше сценария: о самом сценарии им ничего не известно. Следовательно, узлы не могут удостовериться в том, что условия, определенные в сценарии выполнены. То есть, они не могут подтвердить транзакцию.
Поэтому, чтобы раскрыть и тратить эти биткойны, транзакция должна включить в себя, вместе с условиями, определенными в сценарии, и сам сценарий — то есть замок (сценарий) вместе с ключом (условия).
Тогда узлы сети Биткойна, хэшировав включенный сценарий, могут удостовериться в том, что его хэш равен хэшу сценария, включенному в предыдущий выход. Если они совпадают, тогда узлы знают, что те биткойны действительно заперты в том конкретном сценарии. Затем узлам остается только проверить правильность выполнения условий, определенных в сценарии, и транзакция может быть подтверждена.
Деревья Меркла: Введение для начинающих
Вторая часть MAST — это криптографическая хитрость под названием дерево Меркла.
По сути, дерево Меркла является математической структурой, в которой различные наборы данных хэшируются в один компактный хэш: корень Меркла. Так же, как и любой другой хэш, корень Меркла не может быть использован для восстановления его составных данных в дереве Меркла.
Но дерево Меркла имеет одно уникальное свойство: если какие-либо из данных в дереве известны, то можно использовать корень Меркла, чтобы определить, содержатся ли на самом деле эти конкретные данные в дереве Меркла — даже если не все данные в дереве известны.
В качестве упрощенного примера, предположим, что Алиса создала дерево Меркла с сочитанием наборов данных «123» и «456» и получив на выходе корень дерева Меркла «789». Алиса тогда сообщает Бобу, что пакет данных «123» находится где-то в дереве Меркла. Теперь Боб, имея только корень Меркла («789»), может удостовериться в том, что «123» действительно содержится в дереве Меркла, даже если он ничего не знает о находящемся в нем также «456». И сколько еще пакетов данных данное дерево Меркла содержит ему тоже неизвестно — может быть тысячи, но Бобу необязательно что-либо знать о них.
MAST = P2SH + Деревья Меркла
MAST в сущности объединяет потенциал P2SH с возможностями деревьев Меркла.
C MAST, вместо того, чтобы запереть какие-то биткойны только в одном сценарии, те же биткойны можно запереть в серии различных сценариев. Другими словами, одни и те же биткойны могут быть заперты в соответствии с набором разных и взаимоисключающих условий (требующих, например, криптографическую подпись только от Алисы, или подписи от Боба и Кэрол вместе, или подпись только от Кэрол по истечению определенного количество времени, и так далее).
Какое из этих условий будет выполняться первым в (подтвержденной) транзакции определяет, каким образом биткойны будут потрачены. (Если Алиса первой подпишет транзакцию, потратившую выход, тогда её транзакция будет действительна. Если Боб и Кэрол сумели опередить Алису, то будет принята их транзакция. Или же, если прошло заданное количество времени, и Кэрол подписала первой, тогда выиграет её транзакция).
Так же, как и с P2SH, все эти различные сценарии хэшируются. Но теперь они объединяются в дерево Меркла. И корень этого дерева добавляется в выход транзакции в качестве некоего замка высшей инстанции.
Расходование средств происходит аналогичным P2SH образом. Чтобы создать транзакцию, тратящую средства из корня Меркла, нужно добавить в новую транзакцию весь сценарий вместе с необходимыми условиями для его выполнения (замок и ключ).
Но главное вот в чем: можно исключить все остальные сценарии (замки), включив только тот, который фактически используется. (Если Алиса потратит средства первой, ей не нужно будет включить сценарий, позволяющий Бобу и/или Кэрол тратить их. Более того, Алиса может даже не знать, что у Боба и/или Кэрол была такая возможность).
Узлы сети Биткойна могут проверить правильность включенного сценария с помощью вышеописанной хитрости с деревом Меркла. Они используют корень Меркла, включенный в выходе, чтобы определить, действительно ли данный сценарий присутствует в дереве Меркла. Если да, тогда узлы знают, что включенный сценарий является одним из допустимых вариантов расходования данных биткойнов и могут подтвердить новую транзакцию.
Преимущества
MAST улучшает Биткойн тремя основными способами: она расширяет гибкость смарт-контрактов, улучшает масштабируемость, и увеличивает приватность.
Тип гибких смарт-контрактов, предоставляемый MAST не является абсолютно новым: в P2SH уже существовали некоторые конструкции «или/или» (позволяющие требовать подпись только от Алисы, или от Боба и Кэрол, и т.д.). Но в настоящее время существует ограничение на размер различных опций, установленное протоколом для предотвращения DoS-атак.
Ввиду того, что MAST устраняет все подобные ограничения, он увеличивает гибкость смарт-контрактов. Сети все равно, существуют ли два возможных варианта траты средств, или 20, или 1000, так как в конечном итоге только один сценарий включается в транзакцию. Это делает возможными новые и сложные транзакции, такие как 1-из-1000-и multisig, являющие в настоящее время недопустимыми в силу их большого размера. Или длинные списки пользователей, имеющих право потратить определенные биткойны в разные моменты времени.
Кроме того, с P2SH все эти конструкции «или/или» можно было использовать, только опубликовав все сценарии, включая невыполненные. Это приводит к увеличению объема данных с соответсвующим удорожанием транзакций. Требуя от пользователя включения только того сценария, который фактически используется, MAST улучшает масштабируемость. Это уменьшает объем данных, передаваемых, проверяемых, и сохраняемых всеми узлами сети.
В качестве дополнительного бонуса, MAST улучшает конфиденциальность, опять-таки в силу того, что неиспользуемые сценарии остаются скрытыми навсегда. Арбитры депонированных транзакций, например, могут оставаться неизвестными, если не будут участвовать в сделке (из-за того, что обе стороны задействовали свой 2-из-2-х multisig-скрипт, оставив скрипт 2-из-3-х неиспользованным). Таким же образом, неиспользованные time-lock предохранители могут навсегда оставаться скрыты от публики.
Примечание автора: MAST находится в стадии разработки; детали реализации могут отличаться от описания в этой статье.
Источник: Bitcoin Magazine
