Криптографы десятилетиями пытаются построить «финального босса» своей науки — обфускацию. Это штука, которая превращает программу (P) в зашифрованную версию (Obf(P)): ты можешь её запускать на обычных данных и получать обычные результаты, но внутренности (P) остаются скрытыми. Самый популярный формализм — indistinguishability obfuscation (iO): если тебе дали две обфусцированных программы с одинаковой функциональностью, ты не сможешь сказать, какая из них какая. Обфускация прячет код, а не данные.
С помощью iO можно заменить «доверенную третью сторону» практически для любого протокола. Исключение одно: обфусцированная программа не защищена от копирования, поэтому не может делать «штуки с состоянием» вроде денег. Тут-то и пригождаются блокчейны. Вместе они могут дать, например, систему голосования без единой доверенной ноды — безопасную, приватную и устойчивую к сговору.
Проблема в том, что сделать iO чертовски сложно. В 2001 году доказали, что идеальная обфускация невозможна в принципе. Двадцать лет исследователи бились над «вторым местом». Было много провалов, но последние годы принесли хорошие новости: iO таки можно построить на разумных криптографических допущениях. Но есть и плохие: время исполнения таких схем — буквально «галактическое». Формально, оно полиномиальное, но это полином (λ^{10}), где λ — параметр безопасности (обычно 100–120). Каждый бит приходится прогонять через многоуровневую матрёшку из гомоморфного шифрования, и на выходе получаются многомегабайтные промежуточные значения.
Есть два луча надежды. Первый: это похоже на то, что происходило со SNARK'ами в 2010 году. Сейчас, когда доказана принципиальная возможность, умные люди (и боты) начнут по одному откусывать порядки от runtime, и в итоге мы, возможно, получим реализацию, которая «всего лишь» день считает на тяжёлом GPU. Второй путь — не ждать чудес оптимизации, а лучше разобраться с новыми криптографическими допущениями и научиться отличать безопасные от опасных.
Самый rigourous (и самый медленный) подход базируется на конструкции из работ AJ15/BV15/LPST15/LPST16. В двух словах: берётся succinct FE (functional encryption) и XiO (обфускация, дающая выигрыш в размере по сравнению с таблицей истинности). Они комбинируются в «сублинейное компактное randomized encoding», которое затем рекурсивно применяется к каждому биту входных данных. На нижнем уровне лежат garbled circuits и fully homomorphic encryption (FHE) на решётках (LWE). Схема работает, но пока остаётся теоретическим достижением — слишком медленно для реального мира.