Тайное голосование с применением однотипных бюллетеней впервые появилось в Австралии в 1856 году. Насколько хорошо эта система была спроектирована? Если бы вы замыслили в наши дни создать систему выборов, защищённую от мошенничества и фальсификаций, получилось бы у вас то же самое? На мой взгляд, такая система не соответствует разумным требованиям безопасности и изначально основана на принципах, которые неизбежно приводят к узурпации власти той или иной влиятельной группировкой.
В последние десятилетия появились системы сквозного проверяемого голосования, такие как Prêt à Voter, Scantegrity или DRE-ip, в той или иной мере использующие криптографические методы для защиты от фальсификаций. В этой статье я немного расскажу об одной из этих систем, после чего опишу систему случайного голосования с использованием non-malleable time lock puzzles, которая вообще отказывается от того, чтобы предоставлять гражданам осознанно выбирать руководящих лиц государства.
ПРЕДУПРЕЖДЕНИЕ
На Хабре запрещено обсуждение политики. В этой статье не упоминаются конкретные персоналии, государства и события. Материал посвящён исключительно технологиям организации демократических процессов. Просьба в комментариях придерживаться той же линии.
1. DRE-ip
Считается, что в демократических странах, основной инструмент защиты от коррупции — это сменяемость власти, за которую отвечает процедура выборов. Эта процедура начинается на местных избирательных участках, где происходит подсчёт голосов населения одного района. Результаты голосования заносятся в бумажный протокол и отправляются в территориальную избирательную комиссию, где происходит суммирование протоколов разных избирательных участков, составляется новый протокол, который отправляется дальше вверх по инстанциям, до тех пор пока итоговые протоколы не попадают в центральную избирательную комиссию, где подсчитываются результаты всего голосования. Общественный контроль обеспечивается наблюдателями, что придаёт всему действию некоторую защиту от фальсификаций. Проблема в том, что на каждом следующем этапе задействовано меньше людей и, соответственно, меньше наблюдателей. За работой центральной избирательной комиссии могут следить единицы, максимум десятки, наблюдателей. Это слишком мало для страны с населением больше миллиона человек. Людям, планирующим узурпировать власть, невозможно договориться с миллионами наблюдателей, которые действуют на всех избирательных участках, но они вполне могут договориться с 10 наблюдателями, которые следят за центральной избирательной комиссией. В ход могут идти подкуп, шантаж и угрозы насилия. Самое грустное, что у центральной избирательной комиссии есть возможность «нарисовать» любые результаты выборов, независимо от того, насколько добросовестно работали наблюдатели в местных избирательных комиссиях.
Эта проблема решается довольно просто, даже не прибегая ни к каким экзотическим криптографическим системам. Оставьте только самый нижний уровень избирательных комиссий и отправляйте протоколы подсчёта голосов прямо в общедоступную центральную базу данных. Пускай каждый протокол будет подписан электронной подписью каждого из наблюдателей, работавших на участке, а также электронной подписью избирательного ведомства, ответственного за работу базы данных протоколов. Любой гражданин сможет скачать эту базу данных и убедиться, что голоса подсчитаны верно. Любой наблюдатель сможет проверить, что в базе данных хранится подлинный протокол его избирательного участка, а если нет, то у него на руках будут подписанные электронные документы, являющиеся железным доказательством в суде. При этом из протокола по-прежнему не будет понятно, как проголосовал каждый избиратель, т. е. голосование останется тайным.
То, что эта система нигде не используется, само по себе достаточно странно. Но иногда на местных выборах применяются более продвинутые системы голосования, такие как система DRE-ip, разработанная в 2016 году. В этой статье я сосредоточился именно на ней, поскольку это единственная система, не требующая наличия Tallying Authorities (доверенных избирательных органов, подсчитывающих голоса). В других системах обычно присутствуют несколько TA, принадлежащих к разным партиям, и их взаимная враждебность якобы должна предотвращать фальсификации — очевидно, за исключением случаев, когда эти партии вступают в сговор.
Процедура голосования в системе DRE-ip выглядит так.
Гражданин приходит на избирательный участок, на котором действует обычная процедура регистрации избирателя, соблюдающая правило «один человек — один голос». После этой процедуры избиратель получает уникальный токен, не привязанный к его личности. Затем он использует этот токен для авторизации в машине DRE. Он сообщает машине свой голос, машина генерирует случайный секрет, и на основании голоса и секрета генерирует последовательность данных, из которых невозможно восстановить ни секрет, ни голос. Она выдаёт избирателю подписанный документ с этими данными и уникальным индексом бюллетеня. Из этого документа нельзя извлечь информацию, за кого проголосовал избиратель, так что голосование остаётся тайным (в частности, у заинтересованных сторон нет возможности покупать голоса), но при этом он даёт возможность доказать в суде факт манипуляции результатами голосования. В этот момент избиратель должен выбрать между тем, чтобы подтвердить свой голос, и тем, чтобы проверить машину на честность. Во втором случае машина предоставляет ему ещё один подписанный документ, содержащий сгенерированный секрет и голос избирателя, и помеченный как audited. Избиратель проверяет, что данные на первом подписанном документе действительно соответствуют этому секрету. В этом случае он может снова проголосовать. Если этого соответствия нет, то избиратель заявляет протест (по всей видимости — обращается в суд). Если он выбрал подтвердить свой голос, то машина добавляет голос к сумме голосов, а секрет — к сумме секретов (из которых, конечно же, нельзя восстановить ни отдельный голос, ни отдельный секрет), затем надёжным образом стирает из памяти голос и секрет, а данные из первого документа отправляет в bulletin board (BB) — публичное хранилище, в которое машина DRE имеет право добавлять записи (append-only write access). Если опубликованные данные не соответствуют данным из первого документа, для избирателя это ещё одно основание обратиться в суд. В bulletin board попадает не только конечный документ о голосовании, но и все проверочные документы, помеченные как audited, чтобы представители общественности могли самостоятельно проверить каждый из них. В конце голосования туда попадает финальная сумма голосов и сумма секретов. Используя все эти опубликованные данные, можно проверить правильность суммы голосов с помощью определённой математической формулы.
Если голосование представляет собой выбор из 2 кандидатов, то голос за первого кандидата записывается как 1, а голос за второго — как 0. Тогда сумма голосов будет равна количеству голосов, поданных за первого кандидата, и результаты выборов однозначно определяются по сумме голосов. Если кандидатов больше 2, то параллельно запускается система DRE-ip для каждого кандидата. Это усложняет процедуру работы с бюллетенями и требует ещё одного «доказательства корректности» (proof of well-formedness), для проверки, что сумма голосов одного избирателя равна 1.
Навскидку, я нахожу в этой системе одну стандартную проблему — она по-прежнему зависит от честности и ответственности наблюдателей. Поэтому я не вижу, чем она лучше варианта, когда происходит обычный подсчёт протоколов и отправка их в общую базу данных. При отсутствии добросовестных наблюдателей, влиятельные группировки могут нарушить принцип «один человек — один голос» и проголосовать за людей, не пришедших на выборы. С помощью доступа на чтение к машине DRE и внешнего наблюдения за избирательным участком они могут получить информацию о том, как голосовал каждый избиратель, и нарушить тайну голосования.
Система не требует неправдоподобно высокой квалификации от миллионов наблюдателей. Наблюдатели всего лишь должны удостовериться, что за процессом голосования нет никакого внешнего слежения, и вести мониторинг трафика, чтобы убедиться, что машина DRE не отправляет в сеть никакой лишней информации. От них не требуется умения разобрать машину по винтику и подтвердить, что она соответствует какой-то технической спецификации. Добросовестная регистрация голосов и корректность их подсчёта проверяется математически, а факт фальсификации легко доказывается с помощью подписанных электронных документов.
Интерлюдия
Давайте поговорим о самой демократии, как о власти политиков, выбранных большинством избирателей. Так ли хороша эта идея, как принято считать?
Для начала, пускай вас не вводит в заблуждение приставка «демо», указывающая на власть народа. Избирательные кампании стоят астрономических денег, поэтому поставить своего человека на определённую должность могут только богатые и влиятельные группировки. Демократия — это власть элит. Влиятельная группировка может потратить астрономическую сумму денег на избирательную кампанию тогда и только тогда, когда она рассчитывает вернуть эти деньги с процентами, поэтому демократия неотделима от коррупции. Группировка должна полностью контролировать продвигаемых ею политиков, поэтому она заинтересована приводить к власти преступников, обложенных компроматом. Компромат — это очень эффективный и технологичный способ обеспечения лояльности. Чем хуже компромат, тем больше он даёт контроля над политиком. Честные люди, на которых в принципе не может существовать никакого компромата, не нужны ни одной из влиятельных группировок, и не имеют никаких шансов занять руководящие посты.
Голоса подавляющего большинства избирателей не являются следствием взвешенного и продуманного решения. Решения принимаются под влиянием рекламного медиаконтента, подготовленного людьми, разбирающимися в психологических аспектах пропаганды. Этот контент апеллирует не к логике, а к эмоциям и глубинным инстинктам.
Но если я так не люблю демократию, то что я предлагаю взамен? Какой политический строй может быть лучше?
2. Лоттократия
Представьте, что президент страны выбирается случайно из нескольких миллионов человек — скажем, из 10% людей с самыми высокими доходами. Что президента буквально выбирает генератор случайных чисел, и никому заранее не известно, кто именно будет выбран. Это делает невозможным для любой влиятельной группы протолкнуть на эту должность нужного ей кандидата. Никакая организация не сможет тайно завербовать разом несколько миллионов человек. Поскольку кандидаты выбираются случайно, их усреднённые личностные качества — интеллект, ответственность и склонность к деструктивным действиям — будут средними по той группе, из которой их выбирают. И это одно из преимуществ предложенной системы. Если президент выбирается НЕ случайно, то на это место с наибольшей вероятностью попадают худшие из худших. Если же он выбирается случайно, то в среднем должность будут занимать люди со средней степенью испорченности. Среднее — это лучше, чем наихудшее. Поэтому качество государственных деятелей при такой системе сильно вырастет.
Такой способ выборов по-английски называется «sortition», а по-русски — «выборы по жребию». Сам политический строй при этом называют «демархией» (demarchy) или лоттократией (lottocracy).
Выборная демократия скорее обозначает власть влиятельных групп, чем народную власть. Лоттократия имеет гораздо больше оснований называться демократией, чем то, что мы имеем сейчас.
Лоттократия существовала в древних Афинах, где выборы в городской совет, законодательное собрание и на большинство государственных должностей проводились с помощью клеротериона — специального устройства для жеребьёвки. Большинство афинян верило, что настоящая демократия — это именно жеребьёвка, а не голосование. А голосование для них являлось атрибутом олигархической системы.
В Ломбардии и Венеции смешанная система из обычных выборов и выборов по жребию существовала с 12 по 18 век, а во Флоренции — с 14 по 15 век.
В одном из государственных институтов подобная система существует до сих пор. Она называется «суд присяжных».
У лоттократии есть множество активных сторонников. Можете почитать вот эту статью в Nature об алгоритмах случайных выборов, которые позволяют не просто набрать уполномоченную группу людей, а соблюсти различные квоты — профессиональные, возрастные, по уровню образования и пр. В терминах статьи такая группа называется «panel», но я буду называть её «советом» для избежания ненужных аналогий.
Если вы хотите передать всю власть советам опробовать один из этих алгоритмов, то в статье есть ссылка на сайт, который позволяет это сделать. Туда можно загрузить два CSV файла — с описанием социальных групп, списком кандидатов и указанием, сколько представителей каждой группы должны попасть в совет. После нескольких (десятков) минут тяжёлых вычислений сайт вернёт вам CSV файл с описанием всех вариантов состава совета и вероятностью, вычисленной для каждого варианта. Я экспериментировал с сообществом, в котором есть люди, относящиеся одновременно к нескольким социальным группам. Судя по результатам вычислений, такие люди не получают преимущества перед людьми, относящимися только к одной группе, и имеют примерно такую же вероятность попасть в совет. Очевидно, именно это и задумывали авторы алгоритма.
Ключевая проблема лоттократии — это выбор источника случайных чисел, который не поддавался бы влиянию людей, заинтересованных в определённых результатах выборов. Если представителей власти выбирает генератор случайных чисел, то задача узурпации власти сведётся к задаче влияния на результат этого генератора, либо к задаче точного предсказания этого результата.
Одна реалистичная (но узкоприменимая) идея на этот счёт изложена в документе RFC 3797, описывающем внутреннюю процедуру IETF для случайного выбора голосующих членов NomCom из пула подходящих кандидатов. Случайное зерно (random seed) формируется из таких источников случайной информации, как результаты правительственных лотерей, баланс казначейства или объём торгов на Нью-Йоркской бирже. Предполагается, что людям, которые могут повлиять на Нью-Йоркскую биржу, нет никакого интереса вмешиваться в деятельность NomCom, поэтому результаты жеребьёвки можно считать честными.
Может быть, это и годится для комитета, номинирующего кандидатов для Совета по Архитектуре Интернета и других подразделений IETF, но не для выбора высших должностных лиц государства. Для того, чтобы поместить на ключевую должность своего человека, поверьте, политические группировки найдут средства изменить результаты правительственных лотерей, скорректировать баланс казначейства и как-нибудь научатся манипулировать торгами на Нью-Йоркской бирже. Случайное зерно нужно брать из такого источника, чтобы каждый гражданин мог лично убедиться в его случайности. Эта проверка не должна требовать неординарных усилий, и должна быть доступна любому дееспособному человеку. Само зерно должно иметь равномерное распределение, чтобы у всех кандидатов были одинаковые шансы на победу, и множество возможных значений, достаточно большое, чтобы обеспечить выбор из нескольких миллионов кандидатов.
Есть простой способ коллективной генерации случайного числа, который отвечает всем этим требованиям. Группа людей собирается в одном месте, и каждый приносит на встречу закрытый конверт, внутри которого записано случайное число от 0 до N - 1. Затем они одновременно вскрывают конверты, суммируют записанные в них числа и берут остаток от деления полученной суммы на N. В результате получается искомое случайное число.
В системе лоттократического голосования, N — это количество кандидатов на выборах, а полученное случайное число — это номер победившего кандидата.
Недобросовестным участникам такого мероприятия нет смысла вступать в сговор и пытаться обеспечить определённый (неслучайный) результат процедуры, потому что в итоговой сумме достаточно одного случайного числа, чтобы результат был полностью случайным и имел равномерную плотность распределения от 0 до N - 1. Достаточно одному участнику принести по-настоящему случайное число, и результат будет таким же случайным и непредсказуемым, как если бы все участники действовали так же добросовестно.
Эта схема хорошо работает, к примеру, для группы из 5 человек, но при попытке провести такую процедуру для 100 млн участников возникнут определённые организационные трудности. Как собрать 100 млн человек в одном помещении и не сорвать меры противодействия ковиду? Как организовать суммирование чисел, чтобы каждый из 100 млн человек мог лично убедиться в его математической точности?
Естественным желанием будет перенести это мероприятие в Интернет, но как в таком случае обеспечить одновременность раскрытия всех случайных чисел? Во-первых, достаточно трудно заставить такое большое количество избирателей синхронизироваться и опубликовать свои числа в короткое временно́е окно. Во-вторых, если какая-то влиятельная группировка контролирует сервера избирательной системы, то она может узнать все случайные голоса на момент окончания этого временно́го окна, примерно за 1 наносекунду рассчитать нужное число, проголосовать от имени одного из членов группировки, внеся это число в реестр, и получить нужный результат генерации, который обеспечит победу определённого кандидата.
3. Non-Malleable Time Lock Puzzles
На сайте equalitybylot есть статья Мэттью Грея, в которой предлагается использовать Non-Malleable Time Lock Puzzles для коллективной генерации случайного числа по описанному выше принципу. Такие паззлы имеют свойство быстро вычисляться в одну сторону и медленно — в другую. В этом они похожи на хэш-функции. Однако, вычисление time lock паззла невозможно распараллелить, поэтому, даже потратив бесконечное количество денег на вычислительное оборудование, вы не сможете ускорить решение этого паззла больше определённого предела. При этом предел может быть выбран такой, чтобы это было удобно для организации жеребьёвки — например, 24 часа. Предполагается, что ни одна политическая группировка не может владеть компьютером, способным вычислить ключ паззла за тот период времени, который отведён для выборов.
Каждый участник жеребьёвки должен придумать секретный ключ (целое число от 0 до N - 1, где N — количество кандидатов на выборах), с помощью которого генерируется паззл. Все сгенерированные паззлы в течение заранее согласованного периода времени публикуются в открытом общедоступном хранилище. По истечении этого периода в открытое хранилище отправляются секретные ключи. Публикация секретных ключей не обязательна, но она сэкономит электроэнергию, необходимую для решения паззлов. Все паззлы должны быть либо решены, либо проверены с помощью опубликованных ключей. Остаток от деления суммы секретных ключей на количество кандидатов используется как номер победившего кандидата.
Даже если какая-то группировка контролирует n-е количество избирателей и может в любой момент выборов добавить к сумме ключей любое число, она не узнает, какое именно число необходимо добавить, чтобы получить нужный номер кандидата, пока не взломает все паззлы, и она не сможет взломать все паззлы до окончания выборов, потому что в мире не существует способных на это компьютеров.
Если влиятельная группировка получит контроль над сервером избирательной системы и попробует сфальсифицировать жеребьёвку, то ей придётся подделать ВСЕ опубликованные паззлы, т. е. этот обман станет очевиден абсолютно всем гражданам страны. Если среди этих паззлов будет хотя бы один по-настоящему случайный (с ключом, неизвестным этой группировке), то результат жеребьёвки будет таким же непредсказуемым, как если бы таких паззлов было пять, десять или миллион.
Конкретная процедура выявления фальсификации, на мой взгляд, в этом случае должна опираться на документ, подписанный электронными подписями хотя бы 60% граждан, и утверждающий, что система голосования неявным образом отбрасывает присланные гражданами паззлы, не возвращая подтверждение отказа и не сохраняя соответствующих записей в публичных логах.
Ещё один признак фальсификации может быть обнаружен после окончания голосования и публикации реестра паззлов, подписанного электронной подписью избирательного ведомства. Появление двух версий реестра, подписанных этой электронной подписью, но имеющих разное содержание, является доказательством, что закрытый ключ электронной подписи был скомпрометирован.
Сам Мэттью Грей считает, что Non-Malleable Time Lock Puzzles должны использоваться только как запасной вариант. В качестве основного варианта он предлагает многоуровневое голосование с очной явкой избирателей, когда 1000 человек собираются вместе и складывают в кучу бумажные конверты с несгораемыми табличками внутри. На табличках должны быть написаны случайные номера кандидатов. В назначенный срок все конверты разом сжигаются, а данные из табличек публично подсчитываются и используются для выбора представителя из этих 1000 человек, который будет участвовать в следующем этапе выборов. Затем 1000 таких представителей опять собираются вместе, устраивают ещё одно сожжение конвертов, и всё повторяется до тех пор, пока не будет выбран один человек.
Можно сказать, что 1000 человек на последнем этапе выборов — это слишком малое количество, и при желании спецслужбы смогут всех их запугать или подкупить. К тому же, я плохо представляю, как 1000 человек будет коллективно суммировать числа, записанные на тысяче табличек. Но в аргументах Мэттью Грея против Non-Malleable Time Lock Puzzles тоже есть рациональное зерно. Понять математику, стоящую за этими паззлами, можно только после многих лет обучения. Она затрагивает такие области, как Circuit complexity, теория чисел и современная криптография, и только небольшая часть населения сможет понять доказательство того, что эта схема является честным способом случайного выбора. Всем остальным придётся просто довериться этой небольшой группе людей, что создаёт очевидную угрозу узурпации власти и в целом указывает на то, что демократией здесь и не пахнет. Кстати, тот же аргумент применим и против системы DRE-ip.
В заключение скажу, что в приведённых схемах решается проблема случайного выбора одного диктатора. Это делается для простоты изложения концепции, но на самом деле ничто не мешает немного доработать механизм выборов, и вместо одного человека, выбирать собрание голосующих членов. Это позволит сформировать орган, склонный принимать взвешенные и согласованные решения, а также смягчить риски, связанные с попаданием психопата на ответственную должность.
Автор: taydvax
