Zcash скрывает, кому предназначена транзакция. Эта приватность создает неудобный вопрос: если сеть не видит, какие транзакции принадлежат вам, как ваш собственный кошелек их находит?
Сегодня ответ довольно грубый. Кошелек не может спросить у сервера, какие транзакции мои, потому что такой вопрос раскрыл бы именно то, что Zcash пытается скрыть. Поэтому вместо этого кошелек загружает большой объем данных и локально проверяет каждый элемент, чтобы понять, что принадлежит ему. Это работает и сохраняет приватность, но это медленно и тяжеловесно. Такое сканирование является одной из главных причин, почему синхронизация кошелька может казаться вялой.
Идеальным решением был бы способ, при котором кошелек мог бы запросить у сервера точно свои данные и получить их, а сервер при этом так и не узнал бы, что именно было запрошено. Именно это и обеспечивает частное извлечение информации.
Частное извлечение информации — это криптографический метод, который позволяет клиенту прочитать одну запись из базы данных сервера, не раскрывая серверу, какую именно запись он прочитал.
Представьте библиотеку, где вы можете получить именно ту книгу, которая вам нужна, но библиотекарь так и не узнает, какую книгу он вам выдал. Вы получаете свой экземпляр, а ваш интерес остается приватным. PIR — это математическая версия этой идеи, примененная к любой базе данных.
Эта концепция изучается в криптографии уже десятилетиями. Впервые она была представлена в 1995 году Chor, Goldreich, Kushilevitz и Sudan, которые описали подход с несколькими серверами, а первая версия для одного сервера появилась в 1997 году у Kushilevitz и Ostrovsky. Это не изобретение Zcash, а уже сложившаяся область, которую Zcash теперь применяет к реальной и устойчивой проблеме.
Существует два широких подхода к построению PIR, и это различие важно.
Первый использует несколько серверов. Клиент отправляет каждому из нескольких серверов часть запроса, а затем локально объединяет их ответы. Ни один отдельный сервер не видит достаточно, чтобы понять, что именно было запрошено. Это эффективно, но зависит от того, что серверы не вступают в сговор друг с другом, а это трудно гарантировать в реальном мире.
Второй использует один сервер и продуманную криптографию вместо нескольких участников. Здесь клиент опирается на специальный инструмент под названием гомоморфное шифрование, и именно это направление наиболее полезно для реального развертывания, потому что ему не нужны несколько не вступающих в сговор серверов.
Гомоморфное шифрование — это вид шифрования, который позволяет серверу выполнять вычисления над данными, пока они остаются зашифрованными. Сервер получает корректный зашифрованный ответ, так и не увидев исходные значения.
Вот идея PIR с одним сервером, построенного таким образом. Клиенту нужен элемент номер три из списка. Он формирует запрос, который по сути представляет собой зашифрованное «да» для позиции три и зашифрованное «нет» для всех остальных позиций. Для сервера этот запрос — просто бессмысленный шум, он не может определить, в какой позиции находится «да».
Затем сервер объединяет свою базу данных с этим зашифрованным запросом, используя особые свойства гомоморфного шифрования: он умножает каждый сохраненный элемент на соответствующее зашифрованное «да» или «нет» и складывает результаты. На выходе получается один зашифрованный пакет, содержащий ровно тот элемент, который хотел клиент, и ничто не раскрывает, какой именно это был элемент. Клиент расшифровывает этот пакет и читает свой элемент. Сервер ответил на вопрос, так и не узнав сам вопрос.
Более сильная версия, называемая symmetric PIR, добавляет вторую гарантию: клиент узнает только тот элемент, который он запросил, и ничего не узнает о других записях в базе данных. Это защищает не только клиента, но и саму базу данных.
Современные схемы для одного сервера строятся на решеточной криптографии, чаще всего на предположении learning with errors. Запрос клиента представляет собой вектор шифротекстов, то есть шифрование единицы в целевом индексе и нуля во всех остальных, а само шифрование аддитивно гомоморфно, поэтому сервер может складывать шифротексты и умножать их на открытые записи базы данных без расшифровки.
Сервер рассматривает базу данных как матрицу, применяет к ней зашифрованный вектор выбора и возвращает один шифротекст, который расшифровывается в нужную строку. Поскольку запрос неотличим от случайного шума, сервер не получает никакой информации об индексе.
Исторически главным препятствием всегда была стоимость. В наивной реализации сервер должен обращаться к каждой записи в базе данных для каждого запроса, что дорого вычислительно, а шифротексты имеют большой размер, что дорого по пропускной способности. Недавние исследования борются с этим с помощью предварительной обработки: схемы вроде SimplePIR и FrodoPIR позволяют серверу заранее подготовить базу данных и выдать каждому клиенту небольшую подсказку, перенося значительную часть работы в офлайн-фазу, чтобы живые запросы стали быстрыми. Полезный побочный эффект состоит в том, что конструкции на основе решеток также считаются устойчивыми к квантовым атакам, что соответствует более широкому движению Zcash в сторону постквантовой приватности.
PIR — часть усилий по тому, чтобы сделать Zcash одновременно приватным и быстрым в масштабе.
Целью является описанное выше узкое место со сканированием кошельком. Работа в Valar Group развивает методы частного извлечения информации, чтобы кошелек мог получать собственные данные с сервера, а сервер при этом не узнавал, какие записи были запрошены. Одно из конкретных применений — приватная проверка nullifier. Nullifier — это уникальная метка, публикуемая при трате note, которая не позволяет потратить одни и те же средства дважды. Кошельку часто нужно проверить, появился ли уже данный nullifier, иными словами, не потрачена ли еще note, а выполнение такой проверки через сервер сегодня может раскрыть, о какой note идет речь. Частное извлечение информации позволяет кошельку задать этот вопрос, не раскрывая, какой nullifier его интересует. Это идет параллельно с другой работой по масштабированию, включая Project Tachyon и новое ПО для узлов, направленной на устранение ограничений производительности, которые сегодня сдерживают приватные кошельки.
Важно честно говорить о текущем этапе. Это активные исследования и инженерная работа, а не завершенная и уже выпущенная функция. Концепция хорошо устоялась, направление определено, но сделать PIR достаточно эффективным для повседневных кошельков на обычных устройствах — это как раз та сложная часть, над которой сейчас и работают.