Decryptionof results — Расшифровкарезультата
Votescalculation — Подсчетголосов
Votingresults — Итогиголосования

Подсчет зашифрованных бюллетеней

 Теперь голосование окончено, и у нас есть зашифрованный блокчейн. Задача – подсчитать бюллетени и выдать результаты голосования.

Краткое отступление. Каждому варианту выбора в ходе голосования присваивается простое число, начиная с 2:

По сути, отправляя бюллетени, избиратели отправляют в систему голосования эти простые числа, зашифрованные открытым ключом.

Также важно отметить, что система Эль-Гамаля является мультипликативно гомоморфной:

Это значит, что зашифрованное сообщение m1, умноженное на зашифрованное сообщение m2, равно результату шифрования произведения m1 и m2.

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

а n – количество отправленных бюллетеней.

Умножая зашифрованные данные, мы получаем произведение всех поданных голосов также в зашифрованной форме.

Дешифровка результатов

Как вы помните, мы используем пороговое шифрование (схему разделения секрета Шамира). Любые k участников, которые знают координаты k различных точек многочлена, могут восстановить многочлен и все его константы, включая свободный член, который является разделенным секретом. По сути задача состоит в решении системы уравнений для восстановления исходного многочлена и его свободного члена. Этот тип задачи обычно решается с помощью интерполяционного многочлена Лагранжа, и мы тоже используем этот подход. Основная идея проста: это многочлен минимальной степени, принимающий данные значения в данном наборе точек, то есть интерполирующий функцию по известным точкам. Ниже это описано подробнее.

Чтобы дешифровать данные, начнем с идентификации набора доверенных представителей, Pl, которые хранят части ключей и будут участвовать в восстановлении исходного текста.

Далее вводим набор π ͼ {1,..n}, |π|=k.

Чтобы восстановить исходный текст, мы рассчитываем измененный ключ ai.

Так как

где ai – измененный ключ представителя Pi, li – множитель в функции Лагранжа, который зависит от номера узла и общего числа узлов в π ͼ {1,..n}.

Чтобы дешифровать результаты голосования, нужно последовательно применить ключи ai представителя Pi.

Подсчет голосов

В результате может получиться уравнение, например, такого вида:

где k1, k2, k3 – число людей, проголосовавших за каждого из кандидатов, а N – дешифрованное нами число. Теперь, когда мы знаем использованные простые числа (3, 5, 7) и N, нам нужно разложить уравнение на множители и получить k1, k2 и k3.

Рассмотрим простой случай со следующим уравнением:

Как найти x, если известны α, β и M? Простейший способ – умножать α на само себя, пока не получим β, так как здесь речь идет о группе вычетов по модулю M, порядок 

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

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

Сначала для некого k рассчитываются αk, α2k, α3k и так далее. Это так называемые большие шаги:

На втором этапе алгоритма рассчитываются произведения β⋅α, β⋅α2 β⋅α3и так далее. Это так называемые малые шаги:

На представленной выше схеме видно, что в какой-то момент значение β⋅αt становится равным некому значению ym, рассчитанному на предыдущем этапе. Таким образом, 


из чего следует, что 

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

А малый шаг в алгоритме Шенкса реализован так: для всех jh=1..m,h=1..k, проверить, есть ли число β*α1j1*α2j2*αkjk в таблице. Если число есть в таблице, результатом будет вектор (i1m- j1, i2m-j2,..ikm-jk). Принцип в целом тот же, что описан выше, но мы с самого начала работаем с произведением вариантов, выбранных избирателями.

Скорость подсчета голосов

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

Количество избирателей   Количество вариантов   Время вычисления 

10 000                                     4                                          0,220 с 

1 000 000                               4                                           1692 с (Python) 681 с (Cython) 


Можно предположить, что при хорошей оптимизации и использовании всех ядер процессора обработка 1 000 000 голосов при 5 вариантах выбора или 100 000 при 6 вариантах выбора на одном компьютере займет разумное количество времени.

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

Did this answer your question?