a16z: как Cicada использует головоломки с блокировкой времени и доказательства с нулевым разглашением, чтобы включить голосование в сети

Cicada обладает новыми свойствами конфиденциальности, сводит к минимуму предположения о доверии и достаточно эффективна для использования в основной сети Ethereum.

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

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

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

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

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

Краткий обзор частных опросов

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

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

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

Представляем Cicada: конфиденциальность подсчета голосов из проблемы гомоморфной временной блокировки

Чтобы обеспечить конфиденциальность текущего подсчета голосов, Cicada использует криптографические примитивы, которые (насколько нам известно) никогда раньше не использовались в сети.

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

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

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

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

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

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

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

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

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

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

Анонимность и право голоса

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

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

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

Статистическое управление

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

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

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

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

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

*Благодарности: Cicada была разработана совместно с Жозефом Бонно. Спасибо Эндрю Холлу за справочную информацию об истории конфиденциальности голосования. Спасибо также Роберту Хакетту за его отзыв об этой статье. Особая благодарность Стефани Зинн за редактирование. *