Оригинальное название: 《Создание Цикады: Частное голосование на блокчейне с использованием временных замков》

Автор: Майкл Чжу, a16z

Составитель: Линн, MarsBit

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

Вот почему мы представляем Цикаду: новую, открытую библиотеку Solidity, использующую временные замковые головоломки и нулевые знания для реализации частного голосования на блокчейне. В отличие от существующих систем, Цикада обладает новыми свойствами конфиденциальности, минимизирует предположения о доверии и достаточно эффективна для использования в основной сети Ethereum.

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

Краткий обзор частного голосования

В любой голосовательной системе (на блокчейне или другой) существует множество различных уровней конфиденциальности, которые необходимо учитывать. Раскрытие отдельных бюллетеней, текущая подсчет голосов и идентичность избирателей будут по-разному влиять на мотивацию избирателей. Какие свойства конфиденциальности необходимы, зависит от контекста голосования. Несколько из них часто встречаются в литературе по криптографии и социальным наукам:

• Конфиденциальность бюллетеней: секретные бюллетени, также известные как "австралийские бюллетени", были разработаны для голосовательных систем реального мира как способ сохранить предпочтения отдельных избирателей и уменьшить взятки и принуждение (в контексте блокчейна нам может понадобиться свойство, более мощное, чем конфиденциальность бюллетеней — см. "безрецептурность" ниже). Конфиденциальность бюллетеней также может уменьшить социальное давление — меньшая вероятность того, что кто-то проголосует, основываясь на мнении других о его выборе.
• Конфиденциальность текущего подсчета голосов: многие голосовательные системы скрывают текущий подсчет голосов, пока избиратели все еще голосуют, или количество голосов, отданных за каждый вариант, чтобы избежать влияния на явку и мотивацию избирателей. Мы уже видели это в реальном мире; например, американские сенаторы, голосующие позже, более склонны поддерживать свою партию, чем те, кто голосует раньше. А в блокчейне: в голосовании с учетом токенов киты могут обмануть своих оппонентов, создавая ложное чувство безопасности (некоторые могут не захотеть голосовать, предполагая, что они все равно победят), а затем в последний момент отдать свой голос, чтобы изменить результат.
• Анонимность избирателей: во многих голосовательных системах реального мира ваш голос не является публичным, но факт, что вы проголосовали, часто является публичным. Это важно для предотвращения мошенничества со стороны избирателей, поскольку публикация записей о голосовании позволяет людям проверять, голосовал ли кто-то другим именем. Однако в блокчейне мы можем предотвратить мошенничество со стороны избирателей, сохраняя анонимность с помощью криптографических примитивов — например, с помощью Semaphore, вы можете доказать в нулевых знаниях, что вы являетесь квалифицированным избирателем, который еще не голосовал.
• Безрецептурность: отдельные избиратели предоставляют "рецепт" своего бюллетеня, чтобы доказать, как они голосовали третьей стороне, иначе это может привести к продаже голосов. Тесно связанное, но более мощное свойство — устойчивость к принуждению, которое может предотвратить принуждение избирателей голосовать определенным образом. Эти свойства особенно привлекательны в децентрализованной среде, поскольку право голоса может быть реализовано через ликвидность на рынке смарт-контрактов. К сожалению, их также трудно реализовать — на самом деле, Юэлс и др. отметили, что без надежного оборудования это невозможно в безразрешительной среде .

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

Представляем Цикаду: Конфиденциальность подсчета голосов на основе гомоморфных временных замков

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

Во-первых, временные замковые головоломки (Rivest, Shamir, Wagner, 1996) — это криптографическая головоломка, которая скрывает секрет, который может быть раскрыт только после истечения определенного времени — более конкретно, эта головоломка может быть расшифрована путем многократного выполнения некоторых непараллельных вычислений. Временные замковые головоломки полезны в контексте голосования для достижения конфиденциальности текущей статистики: пользователи могут подавать свои бюллетени в виде временных замковых головоломок, так что они остаются конфиденциальными в процессе голосования, но могут быть раскрыты после голосования. В отличие от большинства других структур частного голосования, это позволяет конфиденциальности текущей статистики не полагаться на статистические органы (например, выборные работники, подсчитывающие бумажные или цифровые бюллетени), пороговое шифрование (несколько доверенных сторон должны сотрудничать для расшифровки сообщения) или любые другие доверенные стороны: любой может решить временную замковую головоломку, чтобы гарантировать, что результаты будут раскрыты после голосования.

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

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

Новая структура: эффективность и компромиссы

Чтобы сделать голосовательную схему практичной на блокчейне, необходимо учитывать несколько вопросов. Во-первых, злоумышленник может попытаться манипулировать голосованием, подав неправильный закодированный бюллетень. Например, мы можем захотеть, чтобы временные замковые головоломки для каждого бюллетеня кодировались как булевы значения: "1" означает поддержку предложенной меры, "0" означает противодействие. Страстный сторонник предложения может попытаться закодировать, например, "100", чтобы увеличить свои эффективные голоса.

Мы можем предотвратить такую атаку, заставив избирателей одновременно подавать доказательство нулевых знаний о действительности бюллетеня вместе с самим бюллетенем. Однако вычислительная стоимость доказательства нулевых знаний очень высока — чтобы минимизировать затраты на участие избирателей, доказательство должно быть (1) эффективно вычисляемым на клиенте и (2) эффективно проверяемым на блокчейне.

Чтобы сделать доказательство максимально эффективным, мы использовали настраиваемый протокол sigma — доказательство нулевых знаний, разработанное для конкретных алгебраических соотношений, а не универсальной системы доказательства. Это делает время доказательства очень быстрым: генерация доказательства действительности бюллетеня на Python на стандартном ноутбуке занимает 14 мс.

Хотя проверка этого протокола sigma концептуально проста, она требует значительной части больших модульных степеней. Линейная гомоморфная схема Малавольты и Тьягараджана использует шифрование Пайлье, поэтому эти возведения в степень будут выполняться по некоторым RSA мод N с модулем N\^2. Для разумного размера N возведение в степень на большинстве EVM цепей очень дорого (миллионы газа). Чтобы снизить затраты, Цикада использует экспоненциальный ЭльГамаль — экспоненциальный ЭльГамаль по-прежнему предоставляет аддитивную гомоморфность, но работает на меньших модулях (N вместо N\^2).

Недостатком использования ЭльГамаля является то, что последний шаг расшифровки подсчета требует грубой силы для решения дискретного логарифма (обратите внимание, что это выполняется оффлайн и эффективно проверяется на блокчейне). Поэтому он подходит только для случаев, когда ожидаемое окончательное количество голосов относительно невелико (например, менее 2\^32, или около 4,3 миллиона голосов). В первоначальной схеме на основе Пайлье подсчет можно было эффективно расшифровать независимо от его размера.

Выбор RSA модуля N также включает компромиссы. Наша реализация использует 1024-битный модуль для повышения эффективности газа. Хотя это значительно выше максимального RSA модуля, который когда-либо был публично разложен (829 бит), он ниже обычно рекомендуемого размера в 2048 бит для RSA шифрования или подписей. Однако нашим приложениям не требуется долгосрочная безопасность: как только выборы завершены, нет риска, связанного с будущими значениями N. Предполагается, что подсчет голосов и бюллетени будут опубликованы после истечения срока временного замка, поэтому использование относительно небольшого модуля является разумным. (Если алгоритмы разложения улучшатся, это также можно легко обновить в будущем.)

Анонимность и квалификация избирателей

Как уже упоминалось, Цикада обеспечивает конфиденциальность текущего подсчета голосов — свойства временных замковых головоломок сохраняют подсчет голосов в тайне во время голосования. Однако каждый отдельный бюллетень также является временной замковой головоломкой, зашифрованной при тех же публичных параметрах. Это означает, что так же, как можно расшифровать подсчет (выполнив необходимые вычисления), можно расшифровать и каждый бюллетень. Другими словами, Цикада гарантирует конфиденциальность бюллетеней только во время голосования — если любопытный наблюдатель захочет расшифровать бюллетень конкретного избирателя, он может это сделать. Расшифровка любого отдельного бюллетеня так же дорога, как и расшифровка окончательного подсчета голосов, поэтому наивно потребуется O(n) работы для полного расшифрования бюллетеней с n избирателями. Однако все эти бюллетени могут быть расшифрованы параллельно (при условии, что достаточно много машин), и затраченное время будет таким же, как время, необходимое для расшифровки окончательного подсчета голосов.

Для некоторых бюллетеней это может быть нежелательно. Хотя мы удовлетворены временной конфиденциальностью подсчета голосов, мы можем захотеть обеспечить конфиденциальность бюллетеней на неопределенный срок. Для достижения этого мы можем объединить Цикаду с протоколом анонимной квалификации избирателей, инстанцируя его через доказательства членов группы в нулевых знаниях. Таким образом, даже если бюллетени будут расшифрованы, они лишь раскроют, что кто-то проголосовал таким образом — мы уже знаем это из подсчета голосов.

В нашем репозитории мы включили пример контракта для анонимности избирателей с использованием Semaphore. Однако обратите внимание, что сам контракт Цикада не делает никаких предположений о том, как определять или реализовывать квалификацию избирателей. В частности, вы можете заменить Semaphore, например, на Semacaulk или ZK состояние доказательства (как предложено здесь и здесь).

Статистические органы

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

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

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

Цикада исследует одно из многих направлений в области конфиденциальности голосования на блокчейне и дополняет большую часть исследований, проводимых другими командами. Как уже упоминалось, Цикада тесно связана с такими технологиями, как Semaphore, ZK состояние доказательства и ограничители недействительности для анонимных членов группы. Цикада также может интегрироваться с оптимистичными проверками доказательств, предложенными командой Nouns Vortex, чтобы снизить нагрузку газа для избирателей.

Существует также возможность настроить Цикаду для поддержки различных схем голосования (например, голосование с учетом токенов, вторичное голосование) — более сложные схемы могут быть слишком затратными для основной сети Ethereum, но они могут быть практичными на L2. Учитывая это, мы приветствуем ваши вклады, форки и предложения о том, куда двигаться дальше с Цикадой.