ULBT: как искать и сортировать зашифрованные строки без полного сканирования

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

В этом тексте предлагается практический подход к решению этой проблемы на базе ULBT (Unbalanced Lexicographic Bucket Tree). Предложенный подход предполагает решение следующих задач

• поиск по подстроке;

• префиксный поиск;

• пейджинг с сортировкой;

Базовым ограничением будет статичность индекса. Это означает что назначенный индекс фиксирован для уникальной строки.

Зачем вообще это нужно

В системах с разделением зон (доверенная/недоверенная) обычно всё хорошо, пока нужен доступ по первичному ключу. Проблемы начинаются, когда требуются реальные продуктовые операции:

• contains (поиск подстроки),

• startsWith (префикс),

• order by + paging по защищённому полю.

Наивный путь — гонять большие массивы кандидатов в закрытую зону и обрабатывать (фильтровать или сортировать) там. На десятках и сотнях миллионов записей производительность быстро упирается в сеть.

Нужен индекс в открытой зоне. Но индекс всегда что-то раскрывает. Поэтому задача формулируется как инженерный компромисс:

• Не терять полноту поиска (без false negatives).

• Прогнозируемо резать кандидатов до приемлемого значения до отправки в закрытую зону.

• Не требовать переиндексации всего массива при каждой вставке.

• Ограничить утечки через структуру индекса.

Модель угроз (что считаем атакой)

Целевая модель в этой реализации:

• утечка таблиц и индексов из открытой зоны;

• частичная расшифровка отдельных записей через доступные каналы;

• активный сценарий: получение ключевого материала для специально подобранных записей.

Цель дизайна — даже в этих условиях не дать дёшево восстановить остальной массив и его точный смысл.

Идея ULBT в одном абзаце

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

Ключевое свойство: структура поддерживает селективную фильтрацию и диапазонные операции, не требуя каждый раз переписывать внешний индекс «с нуля».

Как выглядит ULBT (упрощённо)

Представьте дерево, в котором каждый узел может содержать не более N ключей (например, N=5).
При добавлении 6-го ключа узел расщепляется: создаются 6 дочерних узлов, а родитель превращается во внутренний узел с разделителями. При превышении предела дочернего узла он в свою очередь становится внутренним узлом и создает дочерние узлы

Важнейшая деталь: идентификатор узла (bucket_id) никогда не меняется после создания. При расщеплении узел АА остаётся на месте, но превращается из листа во внутренний узел. Все внешние ссылки на него продолжают работать, а закрытая зона знает, как прозрачно перенаправить запрос в нужный дочерний узел.

Что где хранится

Закрытая зона

• Словарь для сопоставления уникальных ключей с исходными значениями строк;

• структуры ULBT для формирования индексов открытой зоны;

• база хранения структур с данными для восстановления после рестарта сервиса.

Открытая зона

• индексы для фильтрации и сортировки из ULBT дерева закрытой зоны;

• Уникальный ключ записи закрытой зоны;

• Важно: во внешней зоне нет исходных строк в открытом виде.

Поиск по подстроке: как это делается

Для поиска в открытой зоне используется ULBT дерево для хранения триграмм. Построение триграммного индекса в закрытой зоне состоит из следующих шагов:

1. Входящая строка раскладывается на триграммы.

2. Каждая триграмма получает индекс бакета в дереве ULBT в виде последовательности символов.

3. Формируем внешний индекс, путем «склеивания» полученных последовательностей в единую строку.

4. При поиске в открытой зоне поисковая последовательность посылается в закрытую зону и полученный ключ используется для поиска.

Пример: для входящего «азбука» выделяем триграммы и ищем/добавляем их в ULBT. В результате получаем набор индексов » аз»(an) ,»азб»(c), «збу»(cf), «бук»(cd), «ука»(fee). Разная длина индекса определена глубиной в дереве бакета с найденной триграммой. Финальный индекс в открытом контуре будет anccfcdfee. Поисковый запрос по подстроке «збук» в этом случае преобразуется в cfcd, что позволит легко найти нужную строку по индексу.

Обратите внимание: коды склеиваются без разделителей, что делает невозможным однозначное восстановление исходных триграмм по индексу даже в случае его компрометации.

Очевидно, что подобная фильтрация даст некоторое количество ложноположительных значений, так как cfcd может сформироваться и из других индексов (c fcd или cfc d или даже c f c d), но это с точки зрения безопасности скорее преимущество, так как дополнительно усложняет анализ.

Идея простая: мы не доказываем совпадение окончательно, мы быстро получаем узкий список кандидатов для финальной проверки в доверенной зоне.

Префиксный поиск

Префиксный поиск по началу строки/токена очевиден. К поисковой подстроке добавляем лидирующий пробел и ищем совпадения либо по началу индекса для начала строки, либо как подстроку для поиска по началу токена. .

Пейджинг и сортировка по защищённому полю

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

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

• По данным skip-take делается отсечение поддеревьев в частотном дереве слева и справа.

• Выполняется дофильтрация в глубину дерева пессмимистичным алгоритмом, чтобы избежать ложно-отрицательного отсечения.

Практический эффект: в закрытую зону уходит «страница + небольшой хвост», а не весь массив.

Правила эксплуатации (важнее всего в проде)

Конкурентность

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

• модель блокировок: lock per leaf;

• независимые вставки в разные листья идут параллельно.

Удаление

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

• Произвольное удаление запрещено;

• разрешён только последовательный откат последних записей (LIFO-rollback).

LIFO-rollback означает, что можно безопасно удалить только последнюю добавленную транзакцию, если она ещё не была зафиксирована во внешней зоне.

Обновление

• UPDATE реализуется как новая версия значения;

• старые индексы не переписываются.

Консистентность публикации

• данные и индекс публикуются наружу только после успешного COMMIT в закрытой зоне;

• если сбой до COMMIT — наружу не выходит ни ключ, ни индекс.

Инварианты реализации

💡 Почему не Bloom Filter и не OPE?

Что получилось в экспериментах

Описанный алгоритм был реализован и обкатан на стенде

Стенд:

• Файл с 1,8 млн строк, эмулирующих закрытые данные;

• закрытая зона в виде WebAPI-сервиса.

• открытая зона в виде консольного клиента на C# (.NET 9);

• таблица 200 000 записей (подмассив ключей и индексов данных с дублирующимися ключами из закрытой зоны). Для проверки в таблице храним отдельный столбец с закрытыми данными, который используем для проверки правильности работы индексов.

Наблюдения:

• построение строчного ULBT 1,8 млн строк (N=26) — около 9 секунд;

• глубина дерева при построениях для 100 прогонов с перемешиванием порядка ввода близка к теоретическому минимуму (не более 6 уровней при оптимальных 5);

• При тестировании пейджинга на 100 рандомных страницах рандомного размера в закрытую зону уходило размер страницы + 5…30 записей (например, для страницы 50 — от 55 до 80 кандидатов) Ложно-отрицательных результатов не наблюдалось. После обработки в закрытой зоне результат страницы в точности соответствовал контрольному набору открытых данных;

• поиск по открытому индексу: 300–900 мкс для пейджинга, 1–5 мс для подстрочного поиска.

Где границы применимости

ULBT хорошо подходит, когда:

• записи не удаляются;

• нужны практичные contains / prefix / sort + page;

• критично не перерасчитывать весь индекс при вставках;

• есть строгое разделение доверенной и недоверенной зон.

ULBT не серебряная пуля, если:

• нужна свободная модель удаления/перестроения;

• требуется формально доказанная защита leakage-профиля уровня академических SSE-схем;

• недопустимы даже структурные утечки порядка.

Вывод

ULBT — компромисс с чёткими ограничениями. В практических сценариях с разделением зон он даёт то, чего обычно не хватает:

• приемлемую безопасность,

• высокую селективность,

• предсказуемую эксплуатацию,

• и скорость, достаточную для реальной продуктовой нагрузки.

А какие подходы к поиску по зашифрованным данным используете вы? Сталкивались ли с ограничениями OPE или SSE-схем в продакшене? Делитесь опытом в комментариях.