Эволюция airdrop: от обычного спама до Merkle tree

Airdrop — популярный способ раздать токены проекта сообществу. Настолько популярный, что порой приводит к заторам в сети Ethereum и огромным комиссиям в транзакциях. Совсем недавно подобная механика, которая использовалась для голосования на бирже FCoin, привела к печальным последствиям для всей сети Ethereum. О том, как можно модифицировать механизм airdrop, в специальном материале для ForkLog рассказал Head of Research Smartz Сергей Прилуцкий.

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

Для решения задачи необходимо в коде контракта определить, принадлежит ли данный адрес списку «белых» адресов. Если да, то разрешить произвести нужное действие. Предлагаемый вариант позволяет довольно просто решить эту проблему, держа в контракте всего одно число. Алгоритм блестящего криптографа Ральфа Меркла широко используется в практически любом децентрализованном софте для обеспечения целостности наборов данных.

Airdrop и ACL

Есть такая практика — выпустить свой токен и разослать его небольшие количества по десяткам тысяч адресов, у которых на балансе есть, для примера, хотя бы 1 ETH. Такой спам крайне популярен сейчас для продвижения собственных токенов. Мало кому нравится появление на своем балансе чьих-то неведомых токенов. Тем не менее, проектам это нужно, и заказы на airdrop очень популярны. Делается это обычно по старинке, вот так (на примере Ethereum, но подходят и другие блокчейны с контрактами, EOS, например):

• парсят блокчейн и находят много адресов по заданным критериям;
• создают адрес, на котором хранится достаточно токенов для рассылки всем из списка, либо предусматривают в контракте токена возможность создавать (минтить) нужное количество токенов заданному адресу (при отправке транзакции со специального привилегированного адреса);
• кладут на этот адрес достаточно Ethereum, чтобы хватило на оплату комиссии за каждую отправку токенов пользователю;
• запускают скрипт рассылки, который перебирает адреса и для каждого создает транзакцию, переводящую (или минтящую) токены заданному адресу.

То есть это просто проход по куче адресов и рассылка токенов каждому. В децентрализованных системах такая push-стратегия обычно довольно хромая, стоит дорого, порождает дыры в безопасности и вообще — это спам. В числе ее недостатков:

• на комиссии уходит много средств (чем больше адресов, тем больше комиссия). Кроме того, в момент рассылки комиссия может расти, т.к. растет нагрузка на сеть, стоимость транзакции растет тоже;
• рассылка требует написания скрипта, который будет слать транзакции, а в скрипте зашит секретный ключ, который дает доступ к куче токенов;
• рассылку необходимо запрограммировать и уметь продолжить с места, где все сломалось.

При этом есть решение гораздо проще, которое, как принято в децентрализованных сетях, большую часть работы отдает софту на стороне клиента. Это контроль доступа с использованием дерева Меркла — крайне удобной структуры данных, чтобы хранить в контракте лишь одно число фиксированного размера (merkleRoot), которое содержит в себе информацию обо всех включенных в дерево данных (об огромном списке адресов получателей, например).

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

Так, этот алгоритм годится для создания огромных ACL (Access Control List), которые позволяют предоставить доступ к некоторой функции контракта миллионам аккаунтов. Для этого нужно записать в контракт единственное число для проверки принадлежности аккаунта к списку.

Рассмотрим схему с airdrop, т.к. она сейчас крайне востребована на рынке и является простым и демонстративным примером смарт-контрактов с большими ACL.

Схема DApp-a

Для начала стоит напомнить, что смарт-контракт сначала деплоится в сеть Ethereum, после чего получает свой собственный адрес и баланс в сети, а далее принимает и процессит внутри себя входящие транзакции.

В схеме merkle-airdrop токены не рассылаются по адресам, а пользователи сами «требуют» свои токены, отправляя транзакции в контракт и оплачивая комиссию. Секрет в том, что в транзакцию пользователи добавляют данные, позволяющие контракту легко проверить, находятся ли они в «белом» списке адресов, причем сам список контракту помнить совершенно не обязательно. Сам контракт при этом является крайне экономным, ему необходимо всего лишь одно (!) число для списка адресов любого (!) размера — именно в этом суть этого отличного алгоритма. А еще такой контракт крайне прост в запуске, после которого не требует вообще никакой поддержки, и, за счет этой простоты, еще и крайне безопасен в использовании. Но об этих моментах чуть позже.

Смарт-контракт

Вот как приблизительно работает вся схема с контрактом merkle-airdrop:

1. В сеть выкладывается (или уже присутствует там) контракт токена.
2. Создается список адресов, которым позволено «потребовать» свои токены. Список генерируется на основе анализа блокчейна, собирается на сайте или иным способом.
3. Все адреса помещаются в один довольно массивный файл, который будет доступен публично по некоторому URL. Например, можно поместить его в протокол IPFS, но можно использовать любой способ залить файл и прочитать его потом из клиентского браузера.
4. На файл «натравливается» скрипт, который из всех содержащихся в нем адресов строит Merkle tree, и получает один единственный хеш — Merkle root. Этот root — главный параметр нашего контракта, который будет выдавать токены.
5. Контракт merkle-airdrop выкладывается в сеть. При выкладке он запоминает merkle root и адрес контракта-токена, чтобы он мог делать трансфер этого токена получателям.
6. На баланс airdrop-контракта кладется большое число токенов (обычным трансфером), достаточное чтобы выдать всем участникам списка.
7. Теперь у airdrop-контракта доступна снаружи функция claim-tokens-by-merkle-proof, которая принимает на вход от пользователя merkle-proof — доказательство того, что пользователь есть в том самом большом «белом» списке адресов. Если доказательство верное, то контракт выполняет transfer() со своего адреса и переводит пользователю токены.

Пользователь

А вот что происходит в браузере клиента (все операции проводятся клиентским JavaScript прямо на странице DApp-a):

1. Находит свой адрес в «белом» списке, который публично размещен где-то в Сети (например в IPFS) и убеждается, что имеет право на токены.
2. Строит из всех адресов в списке дерево Меркла, и из него получает тот самый merkle-proof, который представляет собой несколько чисел (хешей), их количество зависит от размера списка, но по сравнению с ним очень мало, например для ~100 000 адресов достаточно ~17 хешей (размер merkle-proof: log₂N, где N — число элементов).
3. Отправляет в контракт транзакцию, вызывающую функцию claim-tokens-by-merkle-proof и отправляющую туда полученный merkle-proof. Контракту остается проверить proof (при помощи сохраненного merkle-root) и сделать transfer() токенов, если proof верный.
4. Контракт запоминает, кому он выдал токены, чтобы предотвратить повторную выдачу.

Общими словами merkle-proof можно описать как «путь, которым можно пройти от адреса пользователя по дереву Меркла до самого merkle-root». Это довольно серьезная вычислительная работа и лишние данные, которые мы таким образом вынесли из контракта, сэкономив самое дорогое в блокчейне — хранилище.

Merkle-proof доказательство состоит из log₂N хешей (с округлением вверх до целого). Каждый хеш — такого же размера как и merkle-root, который мы записали в контракт-airdrop. То есть для списка из 1024 адресов, пользователь должен предоставить 10 хешей, а для ~4 млрд адресов — всего 32 хеша. Именно в протоколе построения и предъявления доказательства и прячется основная «фишка» контракта — хранение минимального количества информации для определения принадлежности некоторых данных к очень большому списку. Причем чем список больше, тем больше выигрыш.

В реальности контракт дополняется еще и возможностью забрать неиспользованные токены, обновить merkle root и ввести ограничения по времени, например запретить выдачу токенов после некоторого времени. Контракт несложно дорабатывается для раздачи произвольного количества токенов каждому адресу, в этом случае в файле хранятся не просто адреса получателей, но и необходимые суммы токенов, и слегка дорабатывается функция для проверки merkle-proof, но общий алгоритм от этого почти не меняется.

Преимущества и недостатки merkle-airdrop

Отдельно можно выделить преимущества и недостатки вышеуказанного метода по сравнению с традиционной рассылкой скриптом:

Плюсы:

• транзакция, требующая токены, стоит мало газа, причем это число — константа, зависящая от размера «белого» списка;
• после запуска контракта он не требует ни малейшей поддержки, вся активность обеспечивается пользователями;
• позволяет работать со списками практически произвольного размера с минимальным расходованием storage блокчейна.

Минусы:

• надо куда-то выкладывать публичный список адресов;
• клиентскому коду необходимо просмотреть все адреса в «белом» списке и выполнить довольно ресурсоемкий код.

В данном алгоритме нет никаких секретов, такой выигрыш по памяти контракта щедро «оплачен» работой кода на клиентской стороне по проверке принадлежности к списку. Такой подход крайне удачно демонстрирует различие моделей использования смарт-контрактов в сравнении с традиционными централизованными системами.

Традиционная рассылка токенов скриптом в ответ может противопоставить лишь простую и понятную схему работы. А усилия программиста для запуска обычного airdrop в разы превышают усилия для выкладки merkle-airdrop контракта, запущенный скрипт надо мониторить, чтобы не отвалился посередине списка, чтобы у него не закончились средства на комиссии за транзакции, следить, чтобы никто не украл ключ, которым скрипт подписывает транзакции. Плюс, если у вас есть файл с адресами, собственно программист вам и не нужен — деплой такого контракта крайне просто осуществить через публичные сервисы.

Особенности реализации

Помимо основного смарт-контракта, полный DApp для merkle-airdrop имеет некоторые особенности в реализации. В схеме merkle-airdrop большое количество работы возлагается на код в браузере пользователя, например построение merkle proof, для которого нужно пробежать по всему списку адресов. Сам список адресов надо где-то публично хранить, а для пользователя это должно быть не сложнее чем залить файл на сервер.

Поэтому в конструкторе merkle-airdrop на платформе Smartz разработчикам пришлось реализовать загрузку списка адресов в IPFS, отдачу этого списка клиенту и сделать для всего этого специальные JS-виджеты для работы с загруженным в IPFS файлом с адресами. В финальной версии DApp-а планируется сохранять информацию об IPFS напрямую в контракте, чтобы иметь 100% необходимых для airdrop данных в блокчейне. На данный момент выпущена рабочая alpha-версия, которая без проблем умеет раздавать токены по большому списку, но элементы управления пока не совсем удобны. Такой же конструктор airdrop для токенов EOS разрабатывается параллельно, поскольку имеет похожий интерфейс и внутреннюю логику.

В целом, тенденция к утяжелению клиентского кода имеет место во всех продвинутых решениях, и merkle tree — лишь первый из интересных алгоритмов. Другие схемы, такие как кольцевые подписи или zkSNARKs также требуют серьезных вычислений на стороне браузера, поэтому компания Smartz готовится к реализации больших и сложных JS компонентов в конструкторах интерфейсов на клиентской стороне.

Заключение

Главное «преимущество» традиционной рассылки токенов по списку в том, что эта схема позволяет закинуть токены даже тем, кто не желает этого. Есть и особые извращения, когда токенов можно разослать так мало, что биржа даже не позволяет делать с ними транзакции, и юзеры вынуждены наблюдать эти “ошметки” на своих адресах не имея возможности от них избавиться.

Проблема airdrop, когда компания раздает часть токенов системы в комьюнити, конечно крайне важна для развития проектов. Но такое решение, по мнению команды Smartz, недружелюбно к пользователям и неэффективно в целом. Да и вообще смарт-контракты крайне тяготеют к концепции «pull», а не «push», в которой именно пользователи сети являются инициаторами и контролерами бизнес-процессов, а истории, когда кто-то централизованно что-то навязывает десяткам тысяч пользователей, постепенно уходят в прошлое.

Подписывайтесь на новости ForkLog в Telegram: ForkLog Live — вся лента новостей, ForkLog — самые важные новости и опросы.