В этой статье речь пойдёт о ключевом компоненте готовящегося релиза Dash Platform - следующего этапа развития криптовалюты Dash.

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

В попытке добиться ещё большей децентрализации разработчики из Dash Core Group решили, что эта функция должна присутствовать в Dash Platform. Поэтому они создали собственное решение в форме многослойной, специализированной, доказуемой базы данных: GroveDB.  

В этой статье мы рассмотрим применение доказательств запроса по вторичным индексам и почему с ними Dash Platform станет ещё привлекательнее для разработчиков блокчейн-приложений, а потом перейдём к истории, архитектуре и отдельным аспектам внедрения вторичных индексов на основе GroveDB.

Благодарим разработчиков Ивана Шумкова, Сэмьюэла Уэстриха, ThePhez и Virgile Bartolo за помощь в написании этой статьи.

Применение

Доказательства запросов по вторичным индексам могут стать неоценимым инструментом для систем, которые работают с конфиденциальными данными. Это единственный метод, который даёт пользователям стопроцентную уверенность, что полученные из сети данные подлинны, и в то же время позволяет эффективно делать сложные запросы. Их применение актуально во многих индустриях, но особенно нужны они в сфере блокчейн-разработки, где основной упор делается на отсутствие необходимости доверять участникам сети. 

dApps

Многие популярные блокчейн-приложения, в том числе Metamask, Uniswap и Opensea, на данный момент работают с внешними сервисами индексации, например с The Graph. Но эти сервисы не предоставляют доказательств запроса и не гарантируют подлинность ответа на запрос. Вместо этого пользователям приходится полагаться на экономическую заинтересованность и репутационную систему, которые пытаются обеспечить заинтересованность в предоставлении нодами сети подлинных данных. Но, в конечном счёте, никаких гарантий или способов верификации они не дают. При этом доказательства запроса вторичного индекса Dash Platform могут предоставить такие способы и гарантии, и по этой причине высока вероятность того, что многие приложения захотят воспользоваться именно GroveDB.

Dash Platform

Хотя GroveDB создавалась как отдельный продукт, который можно интегрировать в любую систему, использующую RocksDB, Dash Platform будет первой системой, которая его применит. Таким образом разработчики, разместившие свои децентрализованные приложения на Dash Platform, будут иметь преимущество перед теми, кто пользуется другими платформами, поскольку у них будут такие гарантии безопасности и возможности создания запросов от GroveDB, каких никто другой предоставить не может.

Разработчикам DCG не терпится увидеть, какой эффект криптографические доказательства сложных запросов в GroveDB окажут на сферу баз данных на блокчейне. Все заинтересованные читатели, разработчики и владельцы продукта, не стесняйтесь обращаться к нам с вопросами. Чтобы узнать больше, загляните в репозиторий GitHub и следите за новостями о релизах на официальном сайте. 

Предыстория

Документы GroveDB

GroveDB хранит данные в формате “ключи-значения”, что является стандартным методом хранения в базах данных на блокчейне. Кроме того, там присутствует логика, благодаря которой “ключи-значения” можно комбинировать в другой формат гибридных данных, что-то среднее между таблицей реляционной базы данных и NoSQL-документом. В Dash Platform они называются документами и обрабатываются как JSON-объекты, поэтому в контексте разговора о GroveDB мы тоже будем называть их документами.

{
  “id”: “EgHsMrtzbMrJSaxixRWSNqIbXShASteoJxUBkAwMFcSveMPfLKLTyyMbwuMDXkl”,
  “name”: “Alice”,
  “city”: “New York”,
  “cuisine”: “Italian”,
  “acceptsDash”: True
}
NoSQL-документ с пятью полями ключ-значение

Вторичные индексы

Документам в документоориентированных базах данных и записям в реляционных базах данных необходимы уникальные идентификаторы для разделения от других похожих документов/записей. Как правило для этого используется массив случайных байтов в поле ID. ID выступает в роли основного индекса, чтобы можно было получить определённые документы/записи по запросу ID. Но выполнять запросы по ID не очень эффективно. Большинству приложений нужны запросы по определённым полям данных, например, по названию заведения, городу, предлагаемой кухне, возможности оплаты в Dash и так далее, то есть по вторичным индексам.

Таким образом клиенты могут выполнять сложные запросы, например, получить названия всех ресторанов в заданном городе, если для этого города создан вторичный индекс. База данных просто перейдёт к индексу этого города и просмотрит все документы/записи по нему. Если клиент хочет выполнить тот же запрос без вторичных индексов, то она будет искать по всем документам/записям подряд, чтобы проверить, находится ли ресторан в заданном городе, а затем выдаст название. Таким образом становится очевидно, что использование вторичных индексов в большинстве случаев делает запросы к базе данных намного эффективнее.

Криптографические доказательства

Криптографические доказательства - это жизненная сила бездоверительных баз данных. Если вам предоставляют криптографические доказательства результатов запроса, можно с уверенностью доказать, что эти результаты на самом деле хранятся в базе данных. Эта функция очень важна при работе, например, с финансовыми приложениями, расположенными на большом количестве анонимных серверов. Без криптографических доказательств хосты могут легко подменить данные, а у клиентов не будет никаких доказательств подлинности возвращаемых данных. Каждый раз, когда пользователь делает запрос в базу данных без доказательств, ему приходится только надеяться и верить, что хосты передадут ему точную информацию. Чтобы понять, как именно работают доказательства в GroveDB, посмотрите наши документы по внедрению деревьев Меркла.

Предшествующий опыт

До текущего момента, ни одно решение не использовало доказательства запроса вторичного индекса (по крайней мере, в решениях с открытым кодом), но мы можем изучить, как применялись вторичные индексы в других базах данных в формате “ключ-значение”, чтобы получить представление о том, как архитектура вторичных индексов GroveDB вписывается в общепринятую практику. Существуют две основные категории структур вторичных индексов для баз данных с “ключом-значением”: инвертированные индексы и b-деревья:

• Инвертированные индексы: каждое значение вторичного индекса сопоставляется с основными ключами документов, которые содержат это значение, обычно в форме списка.

• b-деревья: b-деревья создаются для каждого вторичного индекса и хранятся как объекты в хэш-таблице. Этим методом пользуется The Graph, популярный сервис индексации, с которым сегодня работают многие популярные блокчейн-приложения.

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

Архитектура

GroveDB - первая производительная реализация иерархически заверенной структуры данных, во многом вдохновлённая статьёй Database Outsourcing with Hierarchical Authenticated Data Structures. Это граф, или grove, деревьев Меркл, где корневые хэши деревьев нижнего уровня хранятся в нодах деревьев более высокого уровня. Благодаря инновационной структуре GroveDB - это первая в своём роде база данных, которая поддерживает криптографические доказательства для запросов по вторичным индексам.

Чтобы лучше понять, что представляет из себя архитектура вторичных индексов в GroveDB, мы рассмотрим пример, как вторичные индексы GroveDB применяются в Dash Platform. Нижеприведённый пример - это высокоуровневая демонстрация для понимания общей архитектуры, поэтому некоторые несущественные для обычных читателей детали были здесь опущены, но они раскрываются дальше в Деталях реализации. Там же приведен и пример контракта данных Dash Platform.

Пример

Все документы с контрактами данных на Dash Platform хранятся в соответствующих деревьях для документов*, которых может быть несколько. Ключи в этих деревьях - это ID документа (основные ключи), а значения - полностью сериализованные документы (плюс некая мета-информация). Корневой хэш каждого дерева с документами хранится в ноде соответствующего дерева с контрактами**, а корневой хэш каждого дерева с контрактом хранится в Дереве Контрактов.

Поскольку дальше диаграммы будут только усложняться по сравнению с Диаграммой 1, мы переключимся на более компактную схему. Диаграмма 2 показывает ту же информацию, что на Диаграмме 1, но в новом виде. Здесь стрелки не обозначают взаимосвязь “предок-потомок” внутри одного дерева. Скорее, выходящие из одной ноды стрелки указывают на ноды, из которых состоит дерево, чей корневой хэш хранится в высокоуровневой ноде, что было показано пунктирными линиями на Диаграмме 1.

Помимо хранения документов, GroveDB также создаёт деревья под каждым деревом с типом документа для каждого вторичного индекса этого типа документа. Например, под деревом “Тип документа 1” может быть дерево для индекса “Город”. Дерево “Город” будет состоять из поддеревьев для каждого уникального значения поля “Город”, например, Нью-Йорк и Феникс, и в каждом из этих деревьев будут содержаться ссылки на документы, в которых присутствует это значение***.

Поддеревья вторичного индекса хранят не документы полностью, а лишь ссылки на ноды, где находятся оригиналы.

Так выглядит базовая архитектура вторичных индексов в GroveDB. Далее мы рассмотрим два отдельных, но довольно распространённых случая: уникальные индексы и составные индексы.

Уникальные индексы

В GroveDB создатель контракта данных можно назначить любой из вторичных индексов своего контракта уникальным, и в этом случае ни один другой документ не может обладать таким же значением индекса. Таким образом, в поддереве значений уникального индекса всегда находится лишь один документ (например, как у поддерева Феникса с диаграммы выше), где ключ равен нулю, а значение - это ссылка.

Составные индексы

В GroveDB есть возможность создания составных индексов, которые по сути являются собранными воедино отдельными индексами. Например, можно назначить индекс город-кухня, который выберет все рестораны с одинаковой кухней в обозначенном городе в собственные поддеревья. Составные индексы тоже могут быть уникальными. Если составной индекс город-кухня назначить уникальным, то внутри одного города может быть только один ресторан с такой кухней.

Детали реализации

*В дереве с типом документа документы хранятся в том дереве, чей хэш хранится под ключом “0”.

**В дереве контракта сериализованный контракт хранится под ключом 0, а деревья с типом документа хранятся в дереве, чей хэш находится под ключом 1.

***В случае не-уникальных вторичных индексов, как в примере, ссылки на документ, как и сами документы, хранятся в поддеревьях с ключом “0”. У уникальных индексов нет поддерева с ключом “0”, а сами ссылки на документ хранятся под ключом “0” прямо в поддереве значения индекса.

Пример контракта данных, использованный в разделе Архитектура. Документ в разделе Предыстория тоже можно отнести к этому контракту данных, потому что он проходит все проверки схем.

  “documentType2”: {
    “type”: “object”,
    “indices”: [
      {
        “name”: “city”,
        “properties”: [
          {
            “city”: “asc”
          }
        ]
      },
      {
        “name”: “cityAndCuisine”,
        “properties”: [
          {
            “city”: “asc”
          },
          {
            “cuisine”: “asc”
          }
        ],
        “unique”: true
      }
    ],
    “properties”: {
      “name”: {
        “type”: “string”,
        “maxLength”: 128,
        “description”: “Name of the restaurant.”
      },
      “city”: {
        “type”: “string”,
        “maxLength”: 64
      },
      “cuisine”: {
        “type”: “string”,
        “maxLength”: 256
      },
      “acceptsDash”: {
        “type”: “boolean”,
        “description”: “True if the restaurant accepts Dash as a form of payment.”
      }
    },
    “required”: [
      “name”,
      “city”,
      “acceptsDash”
    ],
    “additionalProperties”: false
  }
}

*Пример контракта данных  Dash Platform в JSON-формате*