Материал подготовлен получателем гранта BitMEX Келвином Кимом
Аннотация. Бейли и Санкигири в своей статье «Деревья Меркла, оптимизированные для неизменяемых клиентов в биткоине» (Merkle Trees Optimized for Stateless Clients in Bitcoin) представили новую конструкцию аккумулятора для хранения данных состояния биткоина, заявив о значительном улучшении по сравнению с предыдущими решениями Utreexo. Однако мы обнаружили недостатки в коде, который использовался для обеспечения этих улучшений. В этой статье мы покажем ошибку в коде, которая опровергает выводы, представленные в их статье. Авторам сообщили об ошибке 23 апреля 2022 года.
Основной тезис статьи Бейли и Санкигири заключается в том, что «новый алгоритм сокращает размер доказательства в 4,6 раза по сравнению с UTREEXO». В статье приводится следующий график, сравнивающий размеры доказательств блок за блоком.
Рисунок. График данных в статье Бейли и Санкигири
Обнаруженная нами ошибка присутствует в RetrieveListProofs() до коммита `6f1b3c0a08eaf8b84715aa3eecf236e61e3b7c98`. Эта функция принимает фрагмент (срез) элементов, которые необходимо доказать в аккумуляторе, и возвращает доказательство для каждого из этих элементов. Но используемая ими горутина доказывает только последний элемент в фрагменте (срезе). В этом можно убедиться по этой ссылке: https://go.dev/play/p/BoMuRWEnAf1. Таким образом, эта функция доказывает только последний элемент среза: он доказывается n раз (где n — длина среза), а дублирующие хэши доказательств удаляются в вызывающей функции, `RetrieveBatchProof()`.
Эта ошибка была исправлена в коммите `8e85f455a7fdf087e0cb3098ccf12dabf10764ad`. Мы построили график ниже, используя код, приведенный в статье, и код из текущего мастера в коммите `d9a12423cd4c5903dcba3498d17e01d76dea34d4`:
Рисунок. График данных до блока 591,000 с устраненной ошибкой
Новый код обеспечивает гораздо меньшее сокращение размера доказательства — на 22,17%. Но это не график, опубликованный в их статье, — график, который включен в их статью, создан на основе кода с ошибкой.
Следует отметить, что код, на основе которого были получены данные для этого графика, также имел ошибки и падал при попытке воспроизвести результаты в статье. Мы связались с авторами, и они внесли исправления в репозиторий, на который приведена ссылка в статье. Но и после внесения этих исправлений в коде все еще остаются ошибки; чтобы получить этот график, нужны патч и приведенный здесь скрипт.
Файл в этом гисте можно добавить в пакет “patriciaaccumulator”, чтобы проверить, если в коде указанная выше ошибка. Тестовый код генерирует аккумулятор с 8 листьями и доказывает листья 2 и 7.
В коде без ошибки 4 доказанных хэша в позициях: 3, 6, 8, 10. Код с ошибкой доказывает только последний лист 7. Таким образом, возвращается только 3 хэша: 6, 10, 12.
Идея, представленная в статье Болтона и Санкагири, действительно обеспечивает уменьшение размера доказательств по сравнению с размером, первоначально предложенным в статье Драйи в Utreexo. Однако результаты, заявленные в аннотации к статье, неверны и получены на основе ошибочного кода. Правильные данные, представленные здесь, обеспечивают уменьшение размера на 22,17%, а правильный график значительно отличается от представленного в статье.