Contest Proposal: Zero-Knowledge Voting Protocol Implementation

Contest: Zero-Knowledge Voting Protocol Implementation

Contest dates: July 1, 2021 00:01 UTC - September 15, 2021 at 23:59 UTC

Voting period: 20 days

Background and Description

In January, 2021, a contest called Challenge MIT/Harvard paper on Blockchain Faults in Election Systems was held, which crowdsourced arguments to defend the position that secure blockchain based elections are possible. As a result, community arguments were summarized in a joint Free TON community paper, which was used by the GBA to foster a discussion with US election officials.

=nil; Foundation, as an initial member of the Free TON community developed an upgraded version of the TON Virtual Machine, which includes cryptographic primitives required for usage of zero-knowledge proof verification within virtualized applications. =nil; Foundation also prepared C++ (GitHub - NilFoundation/cpp-ton: Cryptography-enhanced Telegram Open Network Protocol C++ Implementation) and Rust-y (GitHub - NilFoundation/rust-ton: Cryptography-enhanced Telegram Open Network Protocol Rust Implementation) ZK proof verification instruction-enhanced TON protocol implementations.

Now Free TON has all of the required technologies to run a blockchain mass voting implementation contest.

Voting protocols inherently imply voter anonymity, but they should also support voter registration by authorities, so they usually get designed as Zero-Knowledge protocols (e.g. https://eprint.iacr.org/2017/585.pdf or https://eprint.iacr.org/2019/1406.pdf)

This document proposes the Zero-Knowledge voting protocol implementation contest on top of the newly introduced TVM Groth16 verification instruction.

Instructions for participants

Contestants are expected to create a voting protocol using the newly introduced VERGRTH16 instruction and make it usable with the FreeTON protocol.

General requirements

  • Must be a correctly functioning FreeTON virtualized application deployed either to https://main.ton.dev (https://ton.live) or to https://net.freeton.nil.foundation (https://nil.ton.live or to https://live.freeton.nil.foundation).

  • Must Involve VERGRTH16 TVM instruction usage.

  • Must have an integral public bulletin board for the non-malleable ballot box, because the voting system requires technical support.

  • Must ensure that the ballot guarantees privacy of the voting message while also guaranteeing that the voter cannot reproduce their vote.

  • Must allow the voter to verify the inclusion of their vote, and also ensure that others cannot coerce the voter to create a false ballot.

  • The ballot must only be generated for eligible voters.

  • Must ensure that voting results uniquely correspond to the ballots in the public board.

  • Must ensure that ballots do not reveal voter identity to any entities, even authorities.

  • Must ensure that ballots are unique to only the individual voting and there is no possibility for proxy votes.

  • Must contain the following actor roles:

    • Voter.
    • Verifier.
    • Ballot Issuer.
  • Must contain definitions for the following items:

    • Ballot. Required not to disclose the Voter’s decision until the Ballot Issuer decides to.
    • Voter Registry. Proves a particular Voter is eligible to vote.
  • Must contain a Ballot Issuer Voter registration procedure:

    • Voter generates some public identifier.
    • Voter submits the public identifier to the Ballot Issuer.
    • Ballot Issuer introduces the Voter’s identifier to the Voter Registry.

Evaluation criteria and winning conditions

  • Apart from uploading a submission, a code should be submitted in accordance with GitHub - freeton-org/readme and deployed either to https://main.ton.dev (https://ton.live) or to https://net.freeton.nil.foundation (https://nil.ton.live or https://live.freeton.nil.foundation).
  • Each contestant should present their solution at a convenient time agreed upon in advance with DevEx Sub-governance members. A solution should include tests with clear instructions.
  • If a test does not cover some scenarios, then jurors can develop their own tests; however, if the burden falls on the jurors, the contest submissions scores should lose some points.
  • The solution should have an open source license.
  • The solution should contain at least a draft of the architecture description which is implied to contain following parts:
    • In-TVM part. Proof verification part. This part is supposed to be done with VERGRTH16 instruction usage and executed within the TVM.
    • Native part. Circuit definition. Proof generator.

Instructions for jurors

Jurors must verify the correctness of the protocol submitted by each contestant to the test cluster as follows:

  • To reproduce every use case scenario (voter registration, voting, vote count)
  • To confirm the solution complies to the architecture description.
  • To confirm the solution complies to protocol requirements.

Voting

  • Jurors whose team(s) intend to participate in this contest by providing submissions lose their right to vote in this contest.
  • A jury from other sub-governance groups could be added to this contest to provide additional technical expertise.
  • Each juror will vote by rating each submission on a scale of 1 to 10.
  • Jurors should provide feedback on each submission.
  • The jury will reject duplicate, subpar, incomplete, or inappropriate submissions.

Reward

Only submissions with an average score equal to or more than 7.00 can get a reward.

  • 1st prize………………………………………… 600,000 TONs
  • 2nd prize………………………………………… 300,000 TONs
  • 3rd prize………………………………………… 100,000 TONs

Total prizes: 1,000,000 TONs

Note: If the number of winning submissions is less than the number of rewards available, any remaining rewards are not subject to distribution and are considered void.

Jury rewards

An amount equal to 15% of all total tokens actually awarded will be distributed equally between all jurors who vote and provide feedback. Both voting and feedback are mandatory in order to collect the reward.

Governance rewards

An amount equal to 2% of the prize fund will be allocated to members who participated in organizing the contest, to be distributed equally among them:

  • @nemothenoone
  • @prigolovko

Procedural remarks

  • Participants must upload their work correctly so it can be viewed and accessible in the formats described. If work is inaccessible or does not fit the criteria described, the submission may be rejected by jurors.
  • Participants must submit their work before the closing of the filing of applications. If not submitted on time, the submission will not count.
1 Like

Everyone, please join DevEx meet up 15th July 14 CET. Hope we will finalise this contest.

It is not very clear what this sentence is about. You can reveal its meaning (1), used causation (2) and terms (3):

  • integral public bulletin board;
  • non-malleable ballot box;
  • the voting system requires technical support - why?

What does this mean? It is “The voter can’t duplicate his vote”?

How are you going to control offline events?

Procedural remarks to all contestants
● Submission document format. Submission should be in form of PDF
document. The reason of this is to avoid possibility to change the submission
after the final contest date.
● Accessibility. All submissions must be accessible for the Jury to open and view,
so please double-check your submission. If the submission is inaccessible or
does not fit the criteria described, jurors may reject the submission.
● Timing. Contestants must submit their work before the closing of the filing of
applications. If not submitted on time, the submission will not count.
● Contact information. All submissions must contain the contestant’s contact
information, preferably a Telegram username by which jurors can verify that the
submission belongs to the individual who submitted it. If not, jurors may reject
your submission.
● Content. The content published in the forum and the provided PDF file should
not differ, except for formatting. Otherwise, jurors may reject the submission.
● Well-formed links. If your submission has links to the work performed, the
content of those links must have the contestant’s contact details, preferably a
Telegram username, so jurors can match it and verify whom the work belongs. If
not, jurors may reject your submission.

Thanks! This should be definitely included.

@Andmans The issue that we were talking about on Telegram is quite relatable with the solution expected by this DEV-related contest :wink: Maybe, we might also think about the solution to protect the users’ submissions (especially the bio data-related submissions for the different contests like jury selection) instead of revealing them on the blockchain forever for everyone including the malicious hackers.

Also I have couple of question:

  1. Do we want to make announcements for this contest like we did for auction and Subscriptions system?
  2. Probably you need my help in organizing the contest, do you? (AMA, calculation of results, issuance of rewards);

btw, also good proposal regarding contest announcements, but should be addresed to responsible team:

I guess, changes have to be something like this:

General requirements:

  • Bulletin board must maintain its integrity.
  • Ballot box must be a non-malleable one.

Security requirements:

  • Fradulent ballot generation complexity should be no less than EdDSA over Ed25519 bruteforce complexity (since the public voter identifier could be, for example, a EdDSA public key).
  • Voting results disclosure should be not possible until the voting is ended.
1 Like

To avoid missunderstanding please put a new version of this proposal below. Also please change contest period as we discussed on the meet up. It would be nice if you provide a translation into Russian as well as some participants asked.

@p.prigolovko Agreed. Here is an updated version. The translated version is coming in the reply following.

Contest: Zero-Knowledge Voting Protocol Implementation

Contest dates: July 20, 2021 00:01 UTC - October 1, 2021 at 23:59 UTC

Voting period: 15 days

Background and Description

In January, 2021, a contest called Challenge MIT/Harvard paper on Blockchain Faults in Election Systems was held, which crowdsourced arguments to defend the position that secure blockchain based elections are possible. As a result, community arguments were summarized in a joint Free TON community paper , which was used by the GBA to foster a discussion with US election officials.

=nil; Foundation, as an initial member of the Free TON community developed an upgraded version of the TON Virtual Machine, which includes cryptographic primitives required for usage of zero-knowledge proof verification within virtualized applications. =nil; Foundation also prepared C++ (GitHub - NilFoundation/cpp-ton: Cryptography-enhanced Telegram Open Network Protocol C++ Implementation ) and Rust-y (GitHub - NilFoundation/rust-ton: Cryptography-enhanced Telegram Open Network Protocol Rust Implementation) ZK proof verification instruction-enhanced TON protocol implementations.

Now Free TON has all of the required technologies to run a blockchain mass voting implementation contest.

Voting protocols inherently imply voter anonymity, but they should also support voter registration by authorities, so they usually get designed as Zero-Knowledge protocols (e.g. https://eprint.iacr.org/2017/585.pdf or https://eprint.iacr.org/2019/1406.pdf )

This document proposes the Zero-Knowledge voting protocol implementation contest on top of the newly introduced TVM Groth16 verification instruction.

Instructions for participants

Contestants are expected to create a voting protocol using the newly introduced VERGRTH16 instruction and make it usable with the FreeTON protocol.

General requirements

  • Must be a correctly functioning FreeTON virtualized application deployed either to https://main.ton.dev (https://ton.live) or to https://net.freeton.nil.foundation (https://nil.ton.liveor to https://live.freeton.nil.foundation).
  • Must Involve VERGRTH16 TVM instruction usage.
  • Must ensure the bulletin maintains its integrity.
  • Must ensure the ballot box is a non-malleable one.
  • Must ensure that the ballot guarantees privacy of the voting message while also guaranteeing that the voter cannot reproduce their vote.
  • Must allow the voter to verify the inclusion of their vote, and also ensure that others cannot coerce the voter to create a false ballot.
  • The ballot must only be generated for eligible voters.
  • Must ensure that voting results uniquely correspond to the ballots in the public board.
  • Must ensure that ballots do not reveal voter identity to any entities, even authorities.
  • Must ensure that ballots are unique to only the individual voting and there is no possibility for proxy votes.
  • Must contain the following actor roles:
    • Voter.
    • Verifier.
    • Ballot Issuer.
  • Must contain definitions for the following items:
    • Ballot. Required not to disclose the Voter’s decision until the Ballot Issuer decides to.
    • Voter Registry. Proves a particular Voter is eligible to vote.
  • Must contain a Ballot Issuer Voter registration procedure:
    • Voter generates some public identifier.
    • Voter submits the public identifier to the Ballot Issuer.
    • Ballot Issuer introduces the Voter’s identifier to the Voter Registry.

Security requirements

  • Fradulent ballot generation complexity should be no less than EdDSA over Ed25519 bruteforce complexity (not an extremely formal requirement, but it is okay since the public voter identifier could be, for example, a EdDSA public key).
  • Voting results disclosure should be not possible until the voting is ended.

Evaluation criteria and winning conditions

  • Apart from uploading a submission, a code should be submitted in accordance with GitHub - freeton-org/readme and deployed either to https://main.ton.dev (https://ton.live) or to https://net.freeton.nil.foundation (https://nil.ton.live or https://live.freeton.nil.foundation).
  • Each contestant should present their solution at a convenient time agreed upon in advance with DevEx Sub-governance members. A solution should include tests with clear instructions.
  • If a test does not cover some scenarios, then jurors can develop their own tests; however, if the burden falls on the jurors, the contest submissions scores should lose some points.
  • The solution should have an open source license.
  • The solution should contain at least a draft of the architecture description which is implied to contain following parts:
    • In-TVM part. Proof verification part. This part is supposed to be done with VERGRTH16 instruction usage and executed within the TVM.
    • Native part. Circuit definition. Proof generator.

Instructions for jurors

Jurors must verify the correctness of the protocol submitted by each contestant to the test cluster as follows:

  • To reproduce every use case scenario (voter registration, voting, vote count)
  • To confirm the solution complies to the architecture description.
  • To confirm the solution complies to protocol requirements.

Voting

  • Jurors whose team(s) intend to participate in this contest by providing submissions lose their right to vote in this contest.
  • A jury from other sub-governance groups could be added to this contest to provide additional technical expertise.
  • Each juror will vote by rating each submission on a scale of 1 to 10.
  • Jurors should provide feedback on each submission.
  • The jury will reject duplicate, subpar, incomplete, or inappropriate submissions.

Reward

Only submissions with an average score equal to or more than 7.00 can get a reward.

  • 1st prize………………………………………… 600,000 TONs
  • 2nd prize………………………………………… 300,000 TONs
  • 3rd prize………………………………………… 100,000 TONs

Total prizes: 1,000,000 TONs

Note: If the number of winning submissions is less than the number of rewards available, any remaining rewards are not subject to distribution and are considered void.

Jury rewards

An amount equal to 15% of all total tokens actually awarded will be distributed equally between all jurors who vote and provide feedback. Both voting and feedback are mandatory in order to collect the reward.

Governance rewards

An amount equal to 2% of the prize fund will be allocated to members who participated in organizing the contest, to be distributed equally among them:

  • @nemothenoone
  • @prigolovko

Procedural remarks

  • Participants must upload their work correctly so it can be viewed and accessible in the formats described. If work is inaccessible or does not fit the criteria described, the submission may be rejected by jurors.
  • Participants must submit their work before the closing of the filing of applications. If not submitted on time, the submission will not count.
  • Submission description document format. Submission description should be formatted as PDF document to avoid post-deadline submission changes.
  • Accessibility. All the submissions must be accessible for the Jury, so please double-check your submission. If the submission is inaccessible or does not fit the criteria described, jurors may reject the submission.
  • Timing. Contestants must submit their work before the closing of the filing of applications. If not submitted on time, the submission will not count.
  • Contact information. All submissions must contain the contestant’s contact
    information, preferably a Telegram username by which jurors can verify that the submission belongs to the individual who submitted it. If not, jurors may reject your submission.
  • Content. The content published in the forum and the provided PDF file should not differ, except for formatting. Otherwise, jurors may reject the submission.
  • Well-formed links. If your submission has links to the work performed, the
    content of those links must have the contestant’s contact details, preferably a
    Telegram username, so jurors can match it and verify whom the work belongs. If not, jurors may reject your submission.
1 Like

Контест: Имплементация протокола голосования с использованием доказательств с нулевым разглашением.

Даты проведения: 20 Июля 2021 00:00 UTC - Октябрь 1, 2021 23:59 UTC.

Период голосования: 15 дней.

Описание

В январе 2021 года был проведен конкурс под названием “Challenge MIT/Harvard paper on Blockchain Faults in Election Systems”, в котором собраны аргументы в защиту позиции, согласно которой безопасные выборы на основе блокчейна возможны. В результате аргументы сообщества были собраны в совместном документе сообщества Free TON, который был использован GBA для обсуждения с представителями избирательных комиссий США.

=nil; Foundation, будучи первоначальным членом сообщества Free TON, разработал обновленную версию виртуальной машины TON, которая включает криптографические примитивы, необходимые для использования проверки доказательства с нулевым разглашением в виртуализированных приложениях. =nil; Foundation также подготовил расширенную имплементацию протокола TON на C++ (https://github.com/nilfoundation/cpp-ton) и на Rust (https://github.com/nilfoundation/rust-ton).

Теперь Free TON имеет все необходимые технологии для проведения конкурса по внедрению массового голосования на блокчейне.

Протоколы голосования по своей сути подразумевают анонимность избирателя, но они также должны поддерживать регистрацию избирателей властями, поэтому они обычно разрабатываются как протоколы с нулевым разглашением (например, https://eprint.iacr.org/2017/585.pdf или https: // eprint.iacr.org/2019/1406.pdf).

В этом документе предлагается конкурс реализации протокола голосования с нулевым разглашением информации поверх недавно представленной инструкции проверки TVM Groth16.

Инструкции для участников

Ожидается, что участники конкурса создадут протокол голосования с использованием недавно представленной инструкции VERGRTH16 и сделают ее пригодной для использования с протоколом FreeTON.

Основные требования

Решение должно:

  • Быть корректно функционирующим виртуализированным приложением FreeTON, развернутым либо на https://main.ton.dev (https://ton.live), либо на https://net.freeton.nil.foundation (https://nil.ton.live или https://live.freeton.nil.foundation).
  • Включать использование инструкции VERGRTH16 TVM.
  • Обеспечивать валидность бюллетеня.
  • Обеспечивать целостность урны для голосования.
  • Гарантировать конфиденциальность голоса в бюллетене, а также гарантировать, что избиратель не сможет дублировать свой голос.
  • Позволить избирателю проверить включение своего голоса, а также гарантировать, что другие не могут заставить избирателя создать фальшивый бюллетень.
  • Бюллетень должен быть создан только для избирателей, имеющих право голоса.
  • Гарантировать, что результаты голосования взаимно-однозначно соответствуют бюллетеням на общественной доске.
  • Обеспечить, чтобы бюллетени не раскрывали личность избирателя никаким организациям, даже властям.
  • Гарантировать, что бюллетени являются подходящими только для индивидуального голосования и нет возможности для голосования по доверенности.
  • Содержать следующие роли:
    • Избиратель.
    • Верификатор.
    • Эмитент бюллетеней.
  • Содержать определения для следующих элементов:
    • Бюллетень. Требуется не разглашать решение избирателя до тех пор, пока об этом не примет эмитент бюллетеней.
    • Реестр избирателей. Доказывает, что конкретный избиратель имеет право голоса.
  • Содержать порядок регистрации избирателя, выдавшего бюллетень:
    • Избиратель генерирует некий публичный идентификатор.
    • Избиратель отправляет публичный идентификатор эмитенту бюллетеней.
    • Эмитент бюллетеней вносит идентификатор избирателя в Реестр избирателей.

Требования безопасности

  • Сложность создания поддельного бюллетеня должна быть не меньше, чем сложность перебора подписи EdDSA на Ed25519 (не очень формальное требование, но это нормально, поскольку публичный идентификатор избирателя может быть, например, открытым ключом EdDSA).
  • Раскрытие результатов голосования не должно быть возможным до окончания голосования.

Критерии оценки и условия выигрыша

  • Помимо загрузки заявки, код должен быть отправлен в соответствии с GitHub - freeton-org/readme и развернут либо на https://main.ton.dev (https://ton.live), либо на https://net.freeton.nil.foundation (https://nil.ton.live или https://live.freeton.nil.foundation).
  • Каждый участник должен представить свое решение в время, заранее согласованное с членами Саб-Говернанса DevEx. Решение должно включать тесты с четкими инструкциями.
  • Если тест не охватывает некоторые сценарии, члены жюри могут разработать свои собственные тесты; однако, если бремя будет ложиться на жюри, результаты конкурсных работ должны потерять несколько баллов.
  • Решение должно иметь лицензию с открытым исходным кодом.
  • Решение должно содержать как минимум черновик описания архитектуры, которое, как предполагается, должно содержать следующие части:
    • Часть In-TVM. Часть проверки доказательства. Эта часть должна выполняться с использованием инструкции VERGRTH16 и выполняться внутри TVM.
    • Нативная часть. Определение схемы. Генератор доказательств.

Инструкции для судей

Члены жюри должны проверить правильность протокола, представленного каждым участником тестового кластера, следующим образом:

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

Голосование

  • Судьи, чьи команды намереваются участвовать в этом конкурсе, предоставляя материалы, теряют право голоса в этом конкурсе.

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

  • Каждый член жюри будет голосовать, оценивая каждую заявку по шкале от 1 до 10.

  • Члены жюри должны давать отзывы по каждому представлению.

  • Жюри отклонит дублирующиеся, некачественные, неполные или несоответствующие материалы.

Вознаграждение

Только заявки со средним баллом, большим или равным 7,00, могут получить награду.

1 место ………………………………………… 600 000 TON
2 место ………………………………………… 300 000 TON
3 место ………………………………………… 100 000 TON
Всего призов: 1000000 TON

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

Награды жюри

Сумма, равная 15% от всех фактически присужденных токенов, будет равномерно распределена между всеми членами жюри, которые голосуют и предоставляют отзывы. Как голосование, так и обратная связь являются обязательными для получения награды.

Награды за подготовку контеста

Сумма, равная 2% от призового фонда, будет выделена участникам, участвовавшим в организации конкурса, и равно распределена между ними:

@nemothenoone
@prigolovko

Процедурные замечания

  • Участники должны правильно загружать свои работы, чтобы их можно было просматривать и использовать в описанных форматах. Если работа недоступна или не соответствует описанным критериям, работа может быть отклонена членами жюри.
  • Участники должны представить свои работы до закрытия приема заявок. Если решение не подано вовремя, отправка не засчитывается.
  • Формат документа с описанием решения. Описание решения должно быть отформатировано как документ PDF, чтобы избежать изменений после крайнего срока подачи.
  • Доступность. Все работы должны быть доступны жюри, поэтому, пожалуйста, проверьте их еще раз. Если представление недоступно или не соответствует описанным критериям, члены жюри могут отклонить его.
  • Время. Конкурсанты должны представить свои работы до окончания приема заявок. Если не подано вовремя, отправка не засчитывается.
  • Контакты. Все материалы должны содержать контактную информацию участника.
  • Содержание. Контент, опубликованный на форуме, и предоставленный PDF-файл не должны отличаться, за исключением форматирования. В противном случае члены жюри могут отклонить заявку.
  • Корректные ссылки. Если в заявке есть ссылки на выполненную работу, содержание этих ссылок должно иметь контактные данные участника, желательно имя пользователя Telegram, чтобы члены жюри могли сопоставить его и проверить, кому принадлежит работа. В противном случае члены жюри могут отклонить вашу заявку.

Contest Prolongation Proposal: #33 Zero-Knowledge Voting Protocol Implementation

It is proposed to amend the following parameters to the following contest:
0:519ded40788204e6fd35b3933e29e3c44e9ca91ff98423774649ce3fa21625d2

Submission period: August 9, 2021 00:01 UTC - December 6, 2021, 23:59 UTC
Voting period: 20 days

@nemothenoone [1 Dec 2021 11:35:37 (1 Dec 2021 11:36:09)]:
Folks. I think we would like to get two more weeks on voting protocol contest to get the debugging done.
Objections?
@fabrice_dune [1 Dec 2021 11:55:26]:
Are there any other known contestants ? Given I asked the same thing 2 days ago in the Formet subgov, I wouldn’t complain :wink:
@prigolovko [1 Dec 2021 11:55:50]:
No problem

Contest Amendment Proposal: Zero-Knowledge Voting Protocol Implementation

It is proposed to amend the following parameters to the following contest: 0:519ded40788204e6fd35b3933e29e3c44e9ca91ff98423774649ce3fa21625d2

Submission period: August 9, 2021 00:01 UTC - December 20, 2021, 23:59 UTC Voting period: 20 days

Hello there. Its my submission. zkpcontest · GitHub any questions to tg @Blackjack_and_code

Contest Prolongation Proposal: #33 Zero-Knowledge Voting Protocol Implementation

It is proposed to amend the following parameters to the following contest:
0:519ded40788204e6fd35b3933e29e3c44e9ca91ff98423774649ce3fa21625d2

Submission period: August 9, 2021 00:01 UTC - December 30, 2021, 23:59 UTC
Voting period: 20 days

1 Like

As discussed at DexEx Subgov Weekly meeting 12/23/2021

Contest MIgration Proposal: Zero-Knowledge Voting Protocol Implementation

It is proposed to continue the execution of the following contest 0:519ded40788204e6fd35b3933e29e3c44e9ca91ff98423774649ce3fa21625d2, Free TON Community within the Cryptography SG (same terms, same jurors) (https://crypto.gov.freeton.org) along with the annulment of the results of the currently existing contest within the DevEx SG.

Corresponding links from Crypto Subgov are bellow.
Approved contest proposal: Free TON Community
Forum thread: Contest Proposal: Zero-Knowledge Voting Protocol Implementation (Migrated from DevEx)