Лёгкие HTTPS-сертификаты на деревьях Меркла

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

Разработчики Chrome с коллегами из других компаний и экспертами группы PLANTS внедряют первое изменение HTTPS, которое поможет решить постквантовые проблемы производительности. Это компактные TLS-сертификаты на деревьях Меркла (Merkle Tree Certificates, MTC). Они заменяют часть тяжелой цепочки подписей компактными доказательствами в бинарном дереве.

Суть в том, что в новой модели удостоверяющий центр подписывает единый корень дерева, а «сертификат» MTC, отправляемый в браузер, является лишь лёгким доказательством включения в это дерево.

Больше трафика и вычислений

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

В феврале 2026 года компания Google предложила новый формат хранения HTTPS-сертификатов. Примерно в то же время IETF создала рабочую группу PKI, Logs, ANd Tree Signatures (PLANTS) для решения вопросов производительности интернета, которые возникнут при переходе на более сложную криптографию.

Сертификаты MTC позволят внедрить надёжные постквантовые алгоритмы без оверхеда на трафик, как в классических цепочках сертификатов X.509.

Сокращая данные аутентификации в рукопожатии, MTC сохранит постквантовый веб таким же быстрым, как и сегодняшний интернет. И есть ещё одно важное преимущество — в MTC основным свойством выдачи является прозрачность, то есть Certificate Transparency. Тут невозможно выдать публичный сертификат, не включив его в публичное дерево. Это означает, что свойства безопасности сегодняшней экосистемы Certificate Transparency включены «по умолчанию».

Дерево Меркла

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

На любой узел дерева можно сослаться по его координатам: хэш уровня номер , сокращённо h(L,K). На уровне входом каждого хэша является одна запись. На более высоких уровнях входом является пара хэшей с уровня ниже.

h(0,K) = H(запись K)
h(L+1,K) = H(h(L,2K), h(L,2K+1))

Чтобы доказать, что определённая запись содержится в дереве, представленном данным верхним хэшем (то есть чтобы позволить клиенту аутентифицировать запись), достаточно предоставить хэши, необходимые для пересчёта общего верхнего хэша. Например, мы хотим доказать, что определённая битовая строка на самом деле является записью 9 в дереве из 16 записей с верхним хэшем . Мы можем предоставить эти биты вместе с другими входными данными для хэширования, необходимыми для восстановления общего хэша дерева с использованием этих битов. Для проверки клиент может вывести:

T = h(4, 0)
  = H(h(3,0), h(3,1))
  = H(h(3,0), H(h(2,2), h(2,3)))
  = H(h(3,0), H(H(h(1,4), h(1,5)), h(2,3)))
  = H(h(3,0), H(H(H(h(0,8), h(0,9)), h(1,5)), h(2,3)))
  = H(h(3,0), H(H(H(h(0,8), H(record 9)), h(1,5)), h(2,3)))
  = H(h(3,0), H(H(H(h(0,8), H(B)), h(1,5)), h(2,3)))

Если дать клиенту значения , он сможет вычислить , а затем объединить все эти хэши и проверить, совпадает ли результат с .

Графически, доказательство состоит из хэшей соседних узлов (жёлтые) вдоль пути (синий) от проверяемой записи до корня дерева:

Благодаря дереву хэшей можно написать эффективное (длиной ) доказательство того, что конкретная запись находится в логе.

Но есть две связанные задачи, которые нужно решить:

1. лог должен быть определён для любой длины N, а не только для степеней двойки;

2. нужно иметь возможность написать эффективное доказательство того, что один лог является префиксом другого.

Лог в дереве Меркла

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

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

Стратегия доказательства для полных деревьев Меркла хорошо переносится и на неполные. Например, доказательство того, что запись 9 находится в дереве размером 13, выглядит так: .

Чтобы доказать, что лог с деревом хэшей включён в лог с деревом хэшей , можно следовать той же идее: предоставить проверяемые вычисления и , в которых все входные данные для вычисления также являются входными данными для вычисления . Например, деревья размером 7 и 13:

На диаграмме узлы x дополняют дерево размером 13 с хэшем , а узлы дополняют дерево размером 7 с хэшем . Чтобы доказать, что листья включены в , сначала представим вычисление в терминах полных поддеревьев (обведённые синим на диаграмме вверху):

T_7 = H(h(2,0), H(h(1,2), h(0,6)))

Затем приводим вычисление , расширяя хэши по мере необходимости, чтобы показать одни и те же поддеревья. Таким образом, становятся видимыми соседние поддеревья (обведённые красным):

T_13 = H(h(3,0), H(h(2,2), h(0,12)))
  = H(H(h(2,0), h(2,1)), H(h(2,2), h(0,12)))
  = H(H(h(2,0), H(h(1,2), h(1,3))), H(h(2,2), h(0,12)))
  = H(H(h(2,0), H(h(1,2), H(h(0,6), h(0,7)))), H(h(2,2), h(0,12)))

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

План включения MTC в Chrome

Сейчас в сотрудничестве с Cloudflare оценивается производительность TLS-соединений на сертификатах MTC.

После валидации основной технологии в начале 2027 года планируется пригласить операторов CT-лог, у которых есть хотя бы один лог в Chrome, для участия в начальной настройке публичных MTC. Поскольку MTC архитектурно похожа на CT, эти операторы обладают уникальной квалификацией, чтобы обеспечить запуск MTC.

К III кв. 2027 года планируется завершить требования для подключения дополнительных УЦ к новому постквантовому хранилищу Chrome Root Store и соответствующей корневой программе, которая поддерживает только МТС. Постквантовое хранилище будет работать параллельно с обычным Chrome Root Store.

Эта область быстро развивается, так что планы по внедрению МТС могут быть скорректированы. Будем следить за обновлениями браузеров.