Компилятор с полностью гомоморфным шифрованием от Google

Ещё в мае 2022 года я переориентировал пару команд в Google на разработку полностью гомоморфного шифрования (вот объявление об этом в рассылке). С тех пор я участвовал в работе над многими проектами в этой области, в частности, руководил поддержкой на github.com/google/fully-homomorphic-encryption – это опенсорсный ПГШ-компилятор для C++. В этой статье даётся вводная информация о том, как при помощи этого инструмента компилировать программы с расчётом на ПГШ. Также пробежимся по тому, из чего этот компилятор состоит.

Если вы хотели бы поучаствовать в этом проекте, пожалуйста, напишите мне на mathintersectprogramming@gmail.com или j2kun@mathstodon.xyz. Мне придётся решить несколько бюрократических вопросов, чтобы можно было принимать вклад от сторонних разработчиков (должным образом ссылаясь на разработчиков в git-коммитах), но, при наличии достаточного интереса с вашей стороны я постараюсь управиться с этим, не откладывая.

Обзор

Ключевая идея в основе полностью гомоморфного шифрования (далее — ПГШ) заключается в том, что можно зашифровать данные, а затем гонять на них программы, даже не расшифровывая самих данных. Если довести такую ситуацию до крайности, то можно сказать, что обладай кто-либо физическим доступом к машине и, следовательно, возможностью проверить значения у неё в отдельных ячейках памяти в ходе выполнения программы, он всё равно не увидел бы ни малейшей информации об обрабатываемых данных (если бы не взломал криптосистему).

Наш ПГШ-компилятор преобразует программы C++, работающие с обычным текстом, в программы, работающие с соответствующими ПГШ-шифротекстами (поскольку выдаёт высокоуровневый код, затем подлежащий дальнейшей компиляции. Следовательно, этот инструмент можно охарактеризовать как транспилятор). Если конкретнее, транспилятор преобразует конкретное подмножество правильных программ на C++ — подробнее о том, как определяется это подмножество, мы поговорим ниже — в программы, решающие те же задачи на зашифрованных данных посредством одной из поддерживаемых реализаций ПГШ-криптосистем. В данном смысле они близки к традиционному компилятору: разбирают ввод, прогоняют несколько этапов оптимизации, генерируют некоторый вывод. Правда, как будет показано в этой статье, благодаря уникальным свойствам ПГШ этот компилятор сближается по свойствам с инструментариями для операций над аппаратными схемами.

Разнообразные варианты ПГШ, ныне поддерживаемые компилятором, называются «предзагрузкой вентилей» (gate bootstrapping). Мне не хватило бы времени детально разобрать здесь математику, лежащую в основе этого процесса — достаточно сказать, что такая технология позволяет пожертвовать производительностью, зато решает более простую задачу: выполняет оптимизацию и выдаёт работающую программу. А далее я скажу, что такая смесь ПГШ позволяет зашифровать каждый бит входной информации, превращая ввод в отдельный шифротекст. Затем программа представляется в виде логических (комбинационных) схем, состоящих из таких вентилей как AND (И), OR (ИЛИ), XNOR (исключающее ИЛИ), т.д.  Одно из достоинств компилятора заключается в том, что он управляет отображением типов высшего порядка (например, целых чисел, массивов и структур) на списки зашифрованных булевых значений и обратно.

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

С другой стороны, оптимизация комбинационных схем – это хорошо изученная задача, для решения которой есть готовые продукты, поддающиеся интеграции (от автора: они что-то интегрировали) в ПГШ-компилятор. Так можно ускорить работу программ.

Зависимости

Если коротко: почитайте файлы docker.

В Google применяется внутренняя система сборки, именуемая blaze, а её опенсорсный аналог (полностью эквивалентный оригиналу за исключением названия) именуется bazel. Одна из первых любопытных вещей, которую можно отметить по поводу компилятора: bazel используется как для сборки, так и для использования проекта (второй аспект хотелось бы изменить). Так что вам потребуется установить bazel, а легче всего это сделать, установив bazelisk, который аналогичен nvm для Node или pyenv для Python. Сразу много версий bazel вам не понадобится, но так легче всего установить новейшую версию. Я буду пользоваться Bazel 4.0.0, но есть и более свежие версии, которые также должны нормально работать.

Вам понадобится компилятор C (я пользуюсь gcc12), поскольку большинство зависимостей в проекте построены на основе исходников (см. в следующем абзаце) и небольшого количества внешних библиотек и программ, обеспечивающих поддержку некоторых плагинов для оптимизации схем. Ниже приведён полный список для систем, основанных на debian.

apt-get update && apt-get install -y \
  gcc \
  git \
  libtinfo5 \
  python \
  python3 \
  python3-pip \
  autoconf \
  libreadline-dev \
  flex \
  bison \
  wget

Как упоминалось выше, все остальные зависимости собираются из исходного кода, и при первой сборке проекта на эту работу требуется существенное время. Поэтому вы вполне можете клонировать и запустить эту сборку, прямо пока читаете статью. Приведённая ниже команда соберёт проект и все приводимые в качестве примера двоичные файлы, а затем кэширует промежуточные артефакты, чтобы можно было пользоваться ими в будущих сборках, просто перекомпилируя те элементы, которые могли измениться со времени последней сборки. В разделе о Bazel/Starlark подробнее рассказано о том, что делает эта команда. Замечание: особо странный случай – с LLVM. Если вы пользуетесь экзотической операционной системой (или контейнером docker, только позвольте мне не углубляться в объяснения, почему с этим есть проблема), то bazel может предпочесть собрать LLVM с нуля – в случае с первой сборкой на это может потребоваться час-два. Также он может отказать из-за того, что в вашей системе не хватает какой-то зависимости. Это особо тяжёлый случай (и жалоба №1 в случае со всеми проблемами, заводимыми у нас на GitHub). Но, если вы работаете на стандартной комбинации ОС/архитектура процессора (из тех, что перечислены здесь), компилятор просто выберет нужную зависимость LLVM и установит её в вашей системе.

git clone https://github.com/google/fully-homomorphic-encryption.git
cd fully-homomorphic-encryption
bazel build ...:all

Чистая сборка на моём домашнем компьютере делается примерно за 16 минут.

Подробный разбор двух примеров: add и string_cap

В этом разделе я покажу два сквозных примера, в которых буду работать с компилятором как конечный пользователь. В первом примере рассмотрим донельзя простую программу, складывающую два 32-разрядных целых числа. Во втором примере будет программа, которая делает заглавным первый символ в каждом слове в строке, записанной в кодировке ASCII. Примеры уже лежат в репозитории в разделе transpiler/examples, они называются simple_sum и string_cap.

Обе эти программы представлены в виде компиляции единственной функции, которая является входной точкой для ПГШ-компонента программы. Также предоставляются API и библиотека для интеграции этой программы с более крупной.

Начнём с simple_sum. Добавим заголовок и файл с исходным кодом как в любой стандартной программе на C++, но с одной дополнительной строкой, сообщающей компилятору, какую именно функцию нужно скомпилировать (а также какие функции внутри неё вызываются).

// add.h
int add(int a, int b);
 
// add.cc
#include "add.h"
 
#pragma hls_top
int add(int a, int b) {
  return a + b;
}

Строка #pragma hls_top сообщает компилятору, какая функция является входной точкой. Кстати, hls здесь означает “high level synthesis” (высокоуровневый синтез), а сама инструкция компилятора взята из проекта XLS, используемого у нас в качестве парсера и первичного сборщика схем. Здесь ‘top’ означает просто «функция верхнего уровня».

Затем в файле из того же каталога, именуемом BUILD (см. далее раздел о Bazel/Starlark, где даётся обзор системы сборки) создаётся цель для сборки, вызывающая ПГШ-компилятор. В данном случае в качестве бекенда воспользуемся OpenFHE.

# BUILD
# загружает ПГШ-компилятор в качестве расширения Bazel.
load("//transpiler:fhe.bzl", "fhe_cc_library")
 
fhe_cc_library(
  name = "add_fhe_lib",
  src = "add.cc",
  hdrs = ["add.h"],
  encryption = "openfhe",  # библиотека для криптосистемы бекенда
  interpreter = True,      # используем динамическое планирование потоков
  optimizer = "yosys",     # оптимизатор логических схем
)

Полный набор опций для данного правила сборки (т.e., документация по главной входной точке компилятора) находится в docstring по макросу bazel. Я выбрал те параметры, которые, на мой взгляд, позволяют добиться золотой середины между стабильностью и производительностью.

Если выполните bazel build add_fhe_lib, то увидите, что сборка идёт – и на этом всё (подробнее см. в разделе «промежуточные файлы» о том, что здесь происходит за кулисами). Но, если вы что-либо неправильно введёте в файле сборки, то на этом месте компилятор споткнётся. Он генерирует заголовок и файл cc, содержащий тот же API, что и add, но с другими типами в качестве аргументов, а также дополнительные аргументы, требуемые на бекенде библиотеки ПГШ.

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

#include <stdio.h>
#include <iostream>
#include <ostream>
 
#include "absl/strings/numbers.h"
#include "transpiler/codelab/add/add_fhe_lib.h"
#include "transpiler/data/openfhe_data.h"
 
constexpr auto kSecurityLevel = lbcrypto::MEDIUM;
 
int main(int argc, char** argv) {
  if (argc < 3) {
    fprintf(stderr, "Usage: add_main [int] [int]\n\n");
    return 1;
  }
 
  int x, y;
  if(!absl::SimpleAtoi(argv[1], &x)) {
    std::cout << "Bad int " << argv[1] << std::endl;
    return 1;
  }
  if(!absl::SimpleAtoi(argv[2], &y)) {
    std::cout << "Bad int " << argv[2] << std::endl;
    return 1;
  }
  std::cout << "Computing " << x << " + " << y << std::endl;
 
  // Настраиваем контекст бекенда и ключи шифрования.
  auto context = lbcrypto::BinFHEContext();
  context.GenerateBinFHEContext(kSecurityLevel);
  auto sk = context.KeyGen();
  context.BTKeyGen(sk);
 
  OpenFhe<int> ciphertext_x = OpenFhe<int>::Encrypt(x, context, sk);
  OpenFhe<int> ciphertext_y = OpenFhe<int>::Encrypt(y, context, sk);
  OpenFhe<int> result(context);
  auto status = add(result, ciphertext_x, ciphertext_y, context);
  if(!status.ok()) {
    std::cout << "FHE computation failed: " << status << std::endl;
    return 1;
  }
 
  std::cout << "Result: " << result.Decrypt(sk) << "\n";
  return 0;
}

Вот что происходит в тех частях, которые не являются явно шаблонным кодом:

Конфигурирование уровня безопасности библиотеки OpenFHE (он называется BinFHE, подсказывая, что выполняет полное гомоморфное шифрование двоичных схем).

constexpr auto kSecurityLevel = lbcrypto::MEDIUM;

Настройка первичного секретного ключа OpenFHE

auto context = lbcrypto::BinFHEContext();
context.GenerateBinFHEContext(kSecurityLevel);
auto sk = context.KeyGen();
context.BTKeyGen(sk);

Шифрование входных значений. Здесь используется API, предоставляемый компилятором (хотя, поскольку весь проект представляет собой исследовательский прототип, мне кажется, что его авторы так и не принялись за унификацию части, отвечающей за «настройку первичного секретного ключа» за API) и включаемый сюда из include "transpiler/data/openfhe_data.h"

OpenFhe<int> ciphertext_x = OpenFhe<int>::Encrypt(x, context, sk);
OpenFhe<int> ciphertext_y = OpenFhe<int>::Encrypt(y, context, sk)

Затем вызываем функцию add с активированным ПГШ и дешифруем результаты.

Далее создаём ещё одно правило BUILD для двоичного файла:

cc_binary(
    name = "add_openfhe_fhe_demo",
    srcs = [
        "add_openfhe_fhe_demo.cc",
    ],
    deps = [
        ":add_fhe_lib",
        "//transpiler/data:openfhe_data",
        "@com_google_absl//absl/strings",
        "@openfhe//:binfhe",
    ],
)

Запускаем код при помощи bazel:

$ bazel run add_openfhe_fhe_demo -- 5 7
Computing 5 + 7
Result: 12

На моей системе на это потребовалось менее 7 секунд.

Рассмотрим более сложный пример string_cap, где во всей красе предстают циклы и массивы. Это слегка упрощённая версия примера, выложенного на GitHub. Начнём с заголовка и файла с исходным кодом:

// string_cap.h
#define MAX_LENGTH 32
void CapitalizeString(char my_string[MAX_LENGTH]);
 
// string_cap.cc
#include "string_cap.h"
 
#pragma hls_top
void CapitalizeString(char my_string[MAX_LENGTH]) {
  bool last_was_space = true;
#pragma hls_unroll yes
  for (int i = 0; i < MAX_LENGTH; i++) {
    char c = my_string[i];
    if (last_was_space && c >= 'a' && c <= 'z') {
      my_string[i] = c - ('a' - 'A');
    }
    last_was_space = (c == ' ');
  }
}

Вот теперь есть что обсудить. Начнём с того, что у этой строки статическая длина, известная во время компиляции. Это необходимо, поскольку программа ПГШ является логической схемой. Она определяет подключения для каждого из входных значений и должна знать, сколько таких подключений определять. В данном случае у нас будет схема с 32 * 8 подключениями, по одному на каждый разряд каждого из символов в массиве.

Вторая новинка здесь – это #pragma hsl_unroll yes, которая, как и hls_top, приказывает компилятору XLS полностью размотать этот цикл. Поскольку программа ПГШ – это статическая схема, никаких циклов в ней быть не может. XLS разматывает наши циклы за нас – и, кстати, я недавно узнал, что она использует решатель Z3, чтобы сначала доказать, что циклы могут быть размотаны (в сложных программах это может приводить к увеличению времени компиляции). Я не знаю никаких других компиляторах, в которых предусматривался бы такой этап доказательства. Складывается впечатление, что размотчик циклом LLVM просто транжирит свои циклы ЦП, если поручить ему полностью размотать бесконечный цикл.

Основная процедура похожа на ту, что мы рассмотрели ранее:

#include <array>
#include <iostream>
#include <string>
 
#include "openfhe/binfhe/binfhecontext.h"
#include "transpiler/data/openfhe_data.h"
#include "transpiler/examples/string_cap/string_cap.h"
#include "transpiler/examples/string_cap/string_cap_openfhe_yosys_interpreted.h"
 
int main(int argc, char** argv) {
  if (argc < 2) {
    fprintf(stderr, "Usage: string_cap_openfhe_testbench string_input\n\n");
    return 1;
  }
 
  std::string input = argv[1];
  input.resize(MAX_LENGTH, '\0');
  std::string plaintext(input);
 
  auto cc = lbcrypto::BinFHEContext();
  cc.GenerateBinFHEContext(lbcrypto::MEDIUM);
  auto sk = cc.KeyGen();
  cc.BTKeyGen(sk);
 
  auto ciphertext = OpenFheArray<char>::Encrypt(plaintext, cc, sk);
  auto status = CapitalizeString(ciphertext, cc);
  if (!status.ok()) {
    std::cout << "FHE computation failed " << status << std::endl;
    return 1;
  };
  std::cout << "Decrypted result: " << ciphertext.Decrypt(sk) << std::endl;
}

Вот ключевые отличия:

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

• Мы используем OpenFheArray, а не OpenFhe, чтобы закодировать массив символов.

А теперь, пропустив правило сборки двоичного файла и запустив его, получим:

$ bazel run string_cap_openfhe_yosys_interpreted_testbench -- 'hello there'
Decrypted result: Hello There

Интересно, что на моей машине на это также уходит около 6 секунд (столько же, сколько и в случае с программой, складывающей 32-разрядные числа). Для более длинной строки (до 32 символов) получим такое же время выполнения, поскольку, естественно, программа обрабатывает все символы из MAX_LENGTH, не зная, являются ли они нулевыми байтами.

Обзор Bazel и Starlark

ПГШ-компилятор зародился в Google любопытным образом. Он был создан десятками участников-добровольцев (в те самые 20% рабочего времени, которые уделяются на сторонние проекты), и многие из них работали над инструментарием XLS для аппаратного синтеза, который является центральным компонентом этого компилятора. В силу таких ограничений, а также потому, что вся работа полностью велась в Google, не было особого поля для манёвра, которое позволило бы обеспечить независимость компилятора от внутреннего сборочного инструментария, используемого в Google.

Здесь мы подходим к Bazel и Starlark, сегодня служащие фасадом этого компилятора, обращённым к пользователю. Bazel – это опенсорсный аналог внутрикорпоративной сборочной системы Google (внутренний инструмент называется “Blaze”), а Starlark – это язык сценариев, созданный по образцу Python. Есть множество мнений о Bazel, которые я не буду здесь повторять. Лучше сделаю минимальный обзор того, как он работает в контексте ПГШ-компилятора.

Сначала немного терминологии. Чтобы приступить к работе с Bazel, нужно сделать следующее.

• Определить файл WORKSPACE, в котором описаны все внешние зависимости вашего проекта, рассказано, как вытягивать их исходный код, и какие команды bazel должны использоваться для их сборки. Можно сравнить эту информацию с высокоуровневыми списками CMakeList, за тем исключением, что в этом файле не содержится никаких инструкций о сборке проекта – просто объявляется корень дерева каталогов этого проекта и указывается имя проекта.

• Определить набор файлов BUILD в каждом подкаталоге, указав здесь целевые сборки, которые могут быть сделаны из содержащихся в этом каталоге файлов с исходным кодом (но не из его подкаталогов). Всё точно, как с файлами CMakeLists в подкаталогах. Каждая цель для сборки может объявлять зависимости, связывающие её с другими целями для сборки, а bazel build гарантирует, что первым делом будут собираться именно зависимости, а также кэширует результаты сборки в пределах всего сеанса. В корне многих проектов лежит файл BUILD, это нужно для предоставления публичных библиотек и API данного проекта.

• Использовать встроенные правила bazel, например, cc_library, cc_binary и cc_test, чтобы сгруппировать файлы в библиотеки, поддающиеся сборке при помощи bazel build, исполняемые двоичные файлы, которые также можно выполнять при помощи  bazel run, а также тесты, которые можно выполнять при помощи bazel test. Большинство правил bazel сводятся к вызову какой-либо исполняемой программы, например, gcc или javac с конкретными аргументами. Одновременно с этим отслеживается накапливающееся множество зависимостей, касающихся артефактов сборки, это делается в «герметичном» месте файловой системы.

• Написать любые дополнительные макросы bazel, сцепляющие встроенные команды bazel, например, чтобы определять локальные группирования сборочных команд, которые должны происходить в определённой последовательности. Эти макросы выглядят как функции на Python, вызывающие отдельные правила bazel и, возможно, передающие данные между ними. Они записываются в файлах .bzl, которые интерпретируются непосредственно самим bazel.

Вообще сборка целей в bazel проходит в две фазы. Сначала идёт фаза анализа. На ней загружаются все файлы BUILD и импортированные файлы .bzl, а также просматриваются все правила, которые при этом вызывались. В частности, компилятор выполняет макросы, так как должен знать, какие правила через них вызываются (а выполнение правил можно подстраховывать на уровне потока управления, либо можно динамически генерировать их аргументы, т.д.). Но правила сборки как таковые он не выполняет. За этой работой компилятору удаётся построить полный граф зависимостей, сообщить об опечатках, недостающих зависимостях, циклах, т.д. По завершении фазы анализа компилятор выполняет базовые правила в том порядке, в котором идут зависимости, и кэширует результаты. Bazel вновь выполнит какое-либо правило только в случае, если что-либо изменится в базовых зависимостях или в тех файлах, от которых он зависит.

Компилятор ПГШ написан на Starlark – в том смысле, что главной входной точкой компилятора является макрос Bazel fhe_cc_library. Этот макрос сцепляет ряд правил, которые вызывают парсер, оптимизатор схем и этапы генерации кода – для каждого из этих элементов предусмотрено своё правило Bazel. Каждое из этих правил по очереди объявляет или записывает файлы, которые мы можем проверить – об этом в следующем разделе.

Вот как выглядит fhecclibrary (если коротко, это подмножество потока управления):

def fhe_cc_library(name, src, hdrs, copts = [], num_opt_passes = 1,
        encryption = "openfhe", optimizer = "xls", interpreter = False, library_name = None,
        **kwargs):
    """Правило для сборки библиотек cc_libraries на основе ПГШ. [docstring пропущен]"""
    transpiled_xlscc_files = "{}.cc_to_xls_ir".format(name)
    library_name = library_name or name
    cc_to_xls_ir(
        name = transpiled_xlscc_files,
        library_name = library_name,
        src = src,
        hdrs = hdrs,
        defines = kwargs.get("defines", None),
    )
 
    # ниже мы добавляем ведущее двоеточие к аргументу `src`, тем самым указывая, 
    # где находятся файлы, сгенерированные по предыдущему правилу. При этом имя файла 
    # служит уникальным идентификатором.
    transpiled_structs_headers = "{}.xls_cc_transpiled_structs".format(name)
    xls_cc_transpiled_structs(
        name = transpiled_structs_headers,
        src = ":" + transpiled_xlscc_files,
        encryption = encryption,
    )
 
    if optimizer == "yosys":  # other branch omitted for brevity
        verilog = "{}.verilog".format(name)
        xls_ir_to_verilog(name = verilog, src = ":" + transpiled_xlscc_files)
        netlist = "{}.netlist".format(name)
        verilog_to_netlist(name = netlist, src = ":" + verilog, encryption = encryption)
        cc_fhe_netlist_library(
            name = name,
            src = ":" + netlist,
            encryption = encryption,
            interpreter = interpreter,
            transpiled_structs = ":" + transpiled_structs_headers,
            copts = copts,
            **kwargs
        )

Среди правил, вызываемых макросом, есть следующие:

• cc_to_xls_ir, вызывающее парсер xlscc и выдающее внутреннее представление программы в виде высокоуровневой схемы. На этом шаге выполняется размотка циклов и другие умные вещи, связанные с преобразованием кода C++ в схему.

• xlscc_transpiled_structs, вызывающее двоичный файл, который обрабатывает структуры (эта часть сложная, её рассмотрение выходит за рамки данной статьи).

• xls_ir_to_verilog, преобразующее внутреннее представление XLS IR в verilog, так, чтобы его можно было оптимизировать при помощи Yosys/ABC – популярной программы для проектирования и оптимизации схем.

• verilog_to_netlist, вызывающее Yosys как для оптимизации схемы, так и для преобразования её в максимально низкоуровневое внутреннее представление, называемое netlist.

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

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

Промежуточные файлы, сгенерированные компилятором

Выше я упоминал, что промежуточные файлы, сгенерированные каждым правилом сборки, bazel кладёт в «герметичное» место в файловой системе. На это место ставится символьная ссылка из корня рабочего пространства, это делается при помощи bazel-bin.

$ ls -al . | grep bazel-bin
/home/j2kun/.cache/bazel/_bazel_j2kun/42987a3d4769c6105b2fa57d2291edc3/execroot/com_google_fully_homomorphic_encryption/bazel-out/k8-opt/bin

В bazel-bin содержится зеркало дерева исходников проекта, а в каталоге для правила сборки находятся все сгенерированные файлы. Вот как эта информация выглядит для нашего сумматора 32-разрядных чисел:

$ ls
_objs                                   add_test
add_fhe_lib.cc                          add_test-2.params
add_fhe_lib.entry                       add_test.runfiles
add_fhe_lib.generic.types.h             add_test.runfiles_manifest
add_fhe_lib.h                           libadd.a
add_fhe_lib.ir                          libadd.a-2.params
add_fhe_lib.netlist.v                   libadd.pic.a
add_fhe_lib.netlist.v.dot               libadd.pic.a-2.params
add_fhe_lib.opt.ir                      libadd.so
add_fhe_lib.types.h                     libadd.so-2.params
add_fhe_lib.v                           libadd_fhe_lib.a
add_fhe_lib.ys                          libadd_fhe_lib.a-2.params
add_fhe_lib_meta.proto                  libadd_fhe_lib.pic.a
add_openfhe_fhe_demo                    libadd_fhe_lib.pic.a-2.params
add_openfhe_fhe_demo-2.params           libadd_fhe_lib.so
add_openfhe_fhe_demo.runfiles           libadd_fhe_lib.so-2.params
add_openfhe_fhe_demo.runfiles_manifest

Виден вывод, это файлы .h и .cc, а также скомпилированные на их основе файлы .so (артефакты сборки вывода), но для нас важнее внутренние сгенерированные файлы. Именно здесь можно посмотреть, какими получились сгенерированные схемы.

Первый файл, который лучше рассмотреть подробнее – это add_fhe_lib.opt.ir, представляющий собой вывод компилятора xlscc с включением XLS-внутреннего шага оптимизации. Именно здесь в основном изложено, как компилятор использует проект XLS: преобразует входную программу в схему. Файл выглядит так:

package my_package
 
file_number 1 "./transpiler/codelab/add/add.cc"
 
top fn add(x: bits[32], y: bits[32]) -> bits[32] {
  ret add.3: bits[32] = add(x, y, id=3, pos=[(1,18,25)])
}

Как видите, это определённое в XLS внутреннее представление (IR) главной процедуры, снабжённое некоторыми дополнительными метаданными к исходному коду. Поскольку XLS-IR нативно поддерживает операции сложения, результат тривиален. Здесь интересно отметить, что числа представлены в виде битовых массивов. Если коротко, система значимых типов XLS-IR поддерживает только биты, массивы и кортежи, причём, кортежи здесь – это механизм для поддержки структур.

Далее XLS-IR преобразуется в Verilog в addfhelib.v, и в результате даёт (тоже тривиальный) код:

module add(
  input wire [31:0] x,
  input wire [31:0] y,
  output wire [31:0] out
);
  wire [31:0] add_6;
  assign add_6 = x + y;
  assign out = add_6;
endmodule

На следующем этапе нужно прогнать этот verilog через Yosys, это зрелый комплект для синтеза схем. В контексте нашего проекта Yosys решает две задачи:

• Преобразует высокоуровневые операции в заданный набор логических вентилей (оперирующих отдельными битами)

• Оптимизирует полученную в результате схему, так, чтобы её размер получился минимальным

XLS также на это способен, и, если хотите в этом убедиться, можете заменить у сборочного правила optimizer атрибут yosys на xls. Но мы обнаружили, что у Yosys схемы, как правило, получаются в 2-3 раза меньше. Скрипт, который мы даём yosys, находится в файле fhe_yosys.bzl. В этом файле заключены макросы bazel и правила, касающиеся вызова Yosys. Вывод программы-сумматора получается таким:

module add(x, y, out);
  wire _000_;
  wire _001_;
  wire _002_;
  [...]
  wire _131_;
  wire _132_;
  output [31:0] out;
  wire [31:0] out;
  input [31:0] x;
  wire [31:0] x;
  input [31:0] y;
  wire [31:0] y;
  nand2 _133_ (.A(x[12]), .B(y[12]), .Y(_130_));
  xor2 _134_ ( .A(x[12]), .B(y[12]), .Y(_131_));
  nand2 _135_ ( .A(x[11]), .B(y[11]), .Y(_132_));
  or2 _136_ ( .A(x[11]), .B(y[11]), .Y(_000_));
  nand2 _137_ ( .A(x[10]), .B(y[10]), .Y(_001_));
  xor2 _138_ ( .A(x[10]), .B(y[10]), .Y(_002_));
  nand2 _139_ ( .A(x[9]), .B(y[9]), .Y(_003_));
  or2 _140_ ( .A(x[9]), .B(y[9]), .Y(_004_));
  nand2 _141_ ( .A(x[8]), .B(y[8]), .Y(_005_));
  xor2 _142_ ( .A(x[8]), .B(y[8]), .Y(_006_));
  nand2 _143_ ( .A(x[7]), .B(y[7]), .Y(_007_));
  or2 _144_ ( .A(x[7]), .B(y[7]), .Y(_008_));
  [...]
  xor2 _291_ ( .A(_006_), .B(_035_), .Y(out[8]));
  xnor2 _292_ ( .A(x[9]), .B(y[9]), .Y(_128_));
  xnor2 _293_ ( .A(_037_), .B(_128_), .Y(out[9]));
  xor2 _294_ ( .A(_002_), .B(_039_), .Y(out[10]));
  xnor2 _295_ ( .A(x[11]), .B(y[11]), .Y(_129_));
  xnor2 _296_ ( .A(_041_), .B(_129_), .Y(out[11]));
  xor2 _297_ ( .A(_131_), .B(_043_), .Y(out[12]));
endmodule

Получается схема, в которой всего 165 вентилей.

Затем на этапе генерации кода производится файл add_fhe_lib.cc, загружающий схему в интерпретатор, а интерпретатор умеет отобразить операцию and2 на выбранный библиотечный вызов бекендовой криптосистемы (см. исходный код бекенда OpenFHE) и использует планирование пула потоков на ЦП, чтобы ускорить вычисление всей схемы.

Что касается схемы string_cap, файл opt.ir демонстрирует более разнообразное внутреннее представление XLS, в том числе, операции по расширению знака, индексированию и срезу массивов, а также мультиплексированию веток (sel). В результате оптимизации получается 684-вентильная схема (хотя, многие из этих вентилей являются «инвертирующими» или «буферные», а значит, обходятся для ПГШ фактически даром).

Компилятор также выдаёт файл .dot, который можно отобразить в формате SVG (внимание, размер SVG ~2,3 МибиБ). Осмотрев схему, вы убедитесь, что она достаточно неглубокая и широкая, что позволяет планировщику потоков развернуться в этой схеме с параллелизмом, и в результате она станет быстро работать. Тем временем сумматор 32-разрядных чисел, пусть на него и приходится всего около 25% вентилей – схема гораздо более глубокая и, следовательно, параллелизма в нём меньше.

Поддерживаемые программы для ввода C++ и издержки на шифрование

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

Во-первых, поддерживаемое этим компилятором подмножество C++ довольно невелико. Как упоминалось выше, все данные должны иметь статические размеры. Таким образом, нельзя написать программу, которая обрабатывала бы произвольные изображения. Вместо этого придётся взять верхнюю границу размера изображения, в соответствии с этим заполнить изображение нулями и только потом шифровать, а затем написать программу, которая бы оперировала изображением именно такого размера. В том же ключе выбранные вами целочисленные типы нетривиальным образом повлияют на производительность. Чтобы в этом убедиться, замените тип int в 32-разрядном сумматоре на char и посмотрите, какая схема у вас получится.

Аналогично, в циклах нужно предусмотреть статические ограничения на количество итераций. Точнее, xlscc должен быть в состоянии полностью размотать каждый цикл. Таким образом, допускаются некоторые формы циклов while и такая рекурсия, которая доказуемо завершается. Здесь возможны некоторые проблемы, если во вводимом коде содержатся циклы со сложными критериями выхода (например, break контролируется при помощи if/else). Также в таком случае нужно тщательно продумывать, как именно писать циклы, хотя, работа над компилятором продолжается, и возможно, что в будущем он возьмёт это продумывание на себя.

Наконец, если шифровать каждый бит обычного текста, это серьёзно сказывается на использовании доступного пространства. Каждая операция по шифрованию отдельного бита соответствует списку примерно из 700 32-разрядных целых чисел. Если вы хотите зашифровать монохромное изображение размером 100×100 пикселей, каждый пиксель которого выражается 8-разрядным целым числом (0-255), вам понадобится 218 МибиБ, чтобы сохранить все эти пиксели в памяти. Это примерно 20 000-кратные издержки. Для сравнения, видеоклип на песню Рика Эстли “Never Gonna Give You Up” при качестве 360p занимает около 9 МибиБ (что довольно мало для трёхминутного видео!). Если же этот видеоклип будет зашифрован по ПГШ, то его размер составит 188 ГибиБ, что (осторожная оценка) соответствует 20 полнометражным фильмам в качестве 1080p. В некоторых других схемах ПГШ предусмотрены меньшие размеры шифротекста, но это достигается за счёт ещё более высоких требований к оперативной памяти, в которой будут производиться вычисления. Поэтому, если вы собираетесь эксплуатировать программы для обработки видео – это осуществимо, но работу потребуется должным образом распределить, а также продумать, как максимально ужать данные перед шифрованием. Например, можно работать при низком разрешении, в тонах серого, с пониженной кадровой частотой. Все эти меры также в целом ускорят работу программ.

До новых встреч!