Alternative Catalyst voting schemes with new crypto protocols by IOG Research, Photrek, and the Catalyst Team

[GENERAL] Name and surname of main applicant

Kriss Baird

[GENERAL] Are you delivering this project as an individual or as an entity (whether formally incorporated or not)

Entity (Incorporated)

[GENERAL] Co proposers and Additional applicants

Prof. Roman Oliynykov

Dr. Philip Lazos 

Prof. Bingsheng Zhang 

Dr. Dmytro Kaidalov 

Prof. Lyudmila Kovalchuk 

Dr. Andrii Nastenko 

Dr. Mariia Rodinko 

Dr. Oleksii Shevtsov

Zeyuan Yin

Dr. Kenric Nelson

Megan Hess

Juana Attieh

Dr. André L. M. Vilela

[GENERAL] Please specify how many months you expect your project to last (from 2-12 months)

12

[GENERAL] Please indicate if your proposal has been auto-translated into English from another language.

No

[GENERAL] Summarize your solution to the problem (200-character limit including spaces)

A set of selected voting schemes for Catalyst, a research paper on their properties, comparison and recommendations for selection, a research paper on supporting cryptographic protocols for voting

[GENERAL] Does your project have any dependencies on other organizations, technical or otherwise?

No

[GENERAL] If YES, please describe what the dependency is and why you believe it is essential for your project’s delivery. If NO, please write “No dependencies.”

No dependencies

[GENERAL] Will your project’s output/s be fully open source?

Yes

[GENERAL] Please provide here more information on the open source status of your project outputs

Yes, the academic papers will be published openly with free access for everyone.

The implementation specifications and prototype implementations will be fully open source subject to the conditions of the Apache 2.0, or MIT License we will use.

[SOLUTION] Please describe your proposed solution.

Solution:

There are many promising avenues to improve the Catalyst voting mechanism, including:

• Exploring variations in the voting power distribution (candidates include but are not limited to time-staked weighting, square-root, and other power weighting). As baselines, the properties of one-coin-one-vote and one-person-one-vote will be included in the analysis
• Investigating different tallying rules ( e.g., methods like preferential voting, ranked choice and spend voting, the Borda count, etc.);
• Reevaluating and developing new cryptographic protocols to address privacy requirements for the selected voting schemes; besides that it is needed to consider providing confidentiality not only for voters' choices on specific projects but also to the very fact of voting for some project.

This project will deliver:

1. The project team (Photrek + IOG Research) will engage with a broader Cardano community to understand better the problems of the existing voting mechanism and make decisions about what is best suitable for Catalyst
2. The prospective voting mechanisms will be identified by exploring existing literature
3. The academic paper written describes with analyses the selected voting mechanism
4. The academic paper will be written on privacy preserving cryptographic voting protocols for the selected voting schemes
5. Prototype implementations and Catalyst architecture requirements for the selected voting mechanisms will be provided in preparation for future development and production deployment

From the ₳500,000 requested, ₳110,000 allocated toward co-proposer compensation in support of design research and testing. The remainder of the budget is allocated to cryptographic research, prototyping and preparing Catalyst architecture for new solutions.

Background:

Catalyst is considered the primary driver for innovation development in the Cardano ecosystem. It enables the harnessing of collective wisdom within the community to allocate funds from the Cardano treasury to diverse projects contributing to Cardano's growth and prosperity.

One of the main technical benefits of Catalyst is the voting mechanism. Initially designed to offer a straightforward and reliable way for stakeholders to express their opinions on various funding proposals, it ensures the privacy of individual voter choices while remaining fully verifiable for internal or external observers. The mechanism utilises a fuzzy threshold voting method allowing stakeholders to vote Yes/No/Abstain (Yes/Abstain) for every submitted proposal.

However significant these benefits are, Catalyst voting today is quite simplistic. Users can select from one of several options and apply their entire voting power toward that option. Typically, this is either Yes / No, or Yes / Abstain.

With its many roles, user-interactions, and the variety of proposals, organising a high-quality decision-making process with a single universal voting mechanism is demonstrably and increasingly challenging. 

As Catalyst grew significantly with an increased number of projects, voters, and distributed funds, various participants joining during this process bring new behaviour strategies that may be far from original assumptions, creating risks for fairness, meritocracy and egalitarian decision making.

While we can appreciate that Catalyst voting today is serving the purpose well enough to identify proposals that are approved by the community of participants, in general, in order to advance the state of the art of Catalyst and offer greater dynamics the voting mechanisms needs reconsideration to enhance flexibility for the diverse Catalyst innovation platform.

The goal of this proposal is to explore the alternative voting mechanisms within the context of Catalyst, conduct a systematic analysis of their properties, and establish a framework to discern which voting mechanisms suit better for what types of collaborative decision processes in Catalyst towards achieving fairness and meritocracy.

[IMPACT] Please define the positive impact your project will have on the wider Cardano community.

The outcome of this project directly addresses the problem of enhancing the voting mechanism in Catalyst. It will provide alternative voting options and clear guidance on how to select among these options and how to implement them.

We expect the enhanced voting mechanisms lead to improved properties of decisions, fostering community sentiment and advocacy, growing adoption, engagement, and reputation over time.

The research outcome will help not only Catalyst to develop clear data-driven analysis and technical requirements for voting, which is arguably the most important feature of Catalyst, but it will also advance state of the art decentralised decision-making process for the benefit of a broader community.

The deep research and peer-reviewed publication will once again cement the reputation of Cardano as a leading innovation platform driven by rigorous scientific and technical processes.

Catalyst Research dissemination events

These will be held at a minimum as presentations in After-Town Hall events. Additionally, the project team will seek to present findings of this research at academic or industry conferences.   

Monthly newsletters:

Reach: 60,000 mailing list members

Monthly email updates sent to all mailing list members to provide a run down on progress and highlight key achievements amounting to approximately 12 monthly newsletters over a 12 month period.

Fortnightly technical development updates:

Reach: Averaging per a month: 3,000 report readers; 60,000 Twitter views; 100 retweets

The Catalyst Team and IOG Research will provide technical development updates every month as part of the overall Cardano technical development update communications. 

Weekly Town Halls:

Reach: At least 1,000 viewers, up to 10,000 periodically

The Catalyst Team hosts the weekly ‘global’ Catalyst Town Hall on Wednesdays at 5PM UTC, and publishes on YouTube for on-demand availability. 

Catalyst Blogs:

Reach: Averaging 5,000 readers per blog based on the last 12 months

Regular blogs published via ProjectCatalyst.io help to amplify progress and updates to outputs that have been achieved. The Catalyst Team expects to produce at least six blogs over the 12 month period

[CAPABILITY & FEASIBILITY] What is your capability to deliver your project with high levels of trust and accountability? How do you intend to validate if your approach is feasible?

The project will engage a group of researchers from the IOG and Cardano community including cryptography experts, game-theory experts, research engineers and others. 

IOG has proven many times its capabilities to perform high quality research, having already published almost two hundred peer-reviewed papers including those at top conferences and journals. IOG designed and implemented most of the elements of the Cardano network, accumulating a lot of knowledge and experience.

Moreover, the involved researchers participated in the development of Catalyst since its early days, including designing of the privacy-preserving cryptographic protocol, community review mechanism and many other developments. They possess significant expertise in this domain.

Also, the group will involve prominent Cardano community members who have made significant contributions to the ecosystem in the past

[Project Milestones] What are the key milestones you need to achieve in order to complete your project successfully?

M1: Literature review of shortlisted voting schema  

Output: A list of recommended voting schemes (including mentioned above) for Catalyst-specific use cases of blockchain decision making and literature surveys for them

Deliverables: 

1.  Project Initiation Kick-off meeting and Minutes
2. A summary of Catalyst-specific decision making use cases 
3. Community-led proposed shortlist of potential voting schemes
4. Final shortlist of voting schemes
5. Literature review of selected voting schemes

Acceptance Criteria: 

1. Minutes are provided with summarized project plan including a timeline of tasks and RACI (responsible, accountable, consulted, informed) 
2. The use-cases match the existing understanding of role-based interactions used in Catalyst
3. Community-proposed shortlist of potential voting is aligned with the Catalyst use-cases and with clear definition of the schema and measurable efficiency criteria for participants

M2: Early Voting schema analysis and proofs 

Output: A draft: a list of selected voting schemes (3-5) for analysis, sketch of analysis and proofs for the selected voting schemes

Deliverables: 

1. A document (to be a part of the future research paper) that describes the model and sketch proofs for at least one voting scheme among selected ones

Acceptance Criteria: 

1. A document (to be a part of the future research paper) that describes the model and sketch proofs
2. Minutes (a seminar recording) that explain the model and sketch proofs for at least one voting scheme among selected ones

M3: Cryptographic research for new voting protocols

Output: A draft: the construction of privacy preserving cryptographic voting protocols for selected voting schemes

Deliverables: 

1. A document that describes the achievability and potential complexity of privacy preserving cryptographic voting protocol(s) for the selected voting schemes, the model and the construction of privacy preserving cryptographic voting protocol(s) for at least one among the selected voting schemes

Acceptance Criteria: 

1. A document (to be a part of the future research paper) that describes the model and the construction of privacy preserving cryptographic voting protocol(s)
2. Minutes (a seminar recording) that explain the model and the construction of privacy preserving cryptographic voting protocol(s)

M4: Architecture design and basic prototyping

Outputs: draft of the main parts of the research papers and partial implementation of the developed voting protocol(s)

Deliverables:

1. A draft: main proofs of properties of the selected voting schemes
2. A draft: main proofs of properties of the privacy preserving cryptographic voting protocols for selected voting schemes with achievable efficient cryptographic support
3. A repo: partial implementation of the privacy preserving cryptographic voting protocols 

Acceptance criteria: 

1. Drafts of the research papers: main proofs of properties of the selected voting schemes; the privacy preserving cryptographic voting protocols that are developed for selected voting schemes: the construction and security proofs
2. Architecture reasonably satisfies the high level requirements of Hermes/Athena and Catalyst Voices technical specifications (project Catalyst will produce a statement on the potential applicability, practical usage, and integration of the research into Hermes/Athena and Catalyst Voices).
3. Repo contains: partial implementation of the privacy preserving cryptographic voting protocols, a guide on launching tests on the already implemented parts
4. Minutes (a seminar recordings) that explain results above

M5: Research ready for peer-review and publication: 

Outputs: preprints of the research papers and prototype implementation 

Deliverables:

1. A draft report: properties of the selected set of the voting schemes for Catalyst, comparison and recommendations for selection depending on input requirements
2. A public preprint of the research paper on analysis of the voting schemes
3. A public preprint of the research paper on the developed privacy preserving cryptographic voting protocols
4. The repo: prototypes of implemented privacy preserving cryptographic voting protocols and their benchmarks
5. Minutes (a seminar recordings) that explain results above

Acceptance Criteria: 

1. Publicly available preprints and a list of conferences or journal for submission, if it is aligned with the submission privacy of the conference or a journal
2. The repo: prototypes of the implemented privacy preserving cryptographic voting protocols and their benchmarks
3. Minutes (a seminar recordings) that explain results above

1. The report on the selected set of the voting schemes for Catalyst, comparison and recommendations for selection depending on input requirements.
2. The research paper on analysis of the voting schemes submitted to the conference or journal (the preprint is publicly available).
3. The research paper on privacy preserving cryptographic voting protocols for selected voting schemes submitted to the conference or journal (the preptint is publicly available).
4. The prototype implementation of the implemented privacy preserving cryptographic voting protocols for selected voting schemes and their benchmarks (the repo with the source code is publicly available).
5. Video review of the voting scheme comparison, cryptographic protocols for them and prototype operation demo.

[RESOURCES] Who is in the project team and what are their roles?

IOG Research

Prof. Roman Oliynykov

Roman is a research fellow at IOG and a professor at leading Ukrainian V.N. Karazin National University, having deep expertise in blockchain systems, cryptography and cybersecurity. His prior professional experience includes leading the team that developed Ukrainian cryptographic standards: the Kalyna block cipher (DSTU 7624:2014) and the Kupyna hash function (DSTU 7564:2014), training of cyber police officers, giving lectures on decentralised ledger technologies, cryptography, software and network security in Ukraine, South Korea and Norway. He published over 100 academic papers; the most important results, including ones related to Catalyst, were presented at top-tier conferences and journals. Roman joined IOG in 2016 and contributed to Ouroboros Classic, and since 2017 has been working on scientific research for Catalyst, covering voting protocols, incentive analysis and other directions.

Dr. Philip Lazos

Philip is a research fellow at IOG, working on all things related to the economics and incentives of blockchains (such as transaction processing, governance, tokenomics and stablecoins). Before that, he was a postdoc at the Sapienza University of Rome and the University of Oxford. He has many publications in top tier venues in Computational Economics, Artificial Intelligence, Operations Research and Algorithms and Complexity. Philip has a master’s degree in Electrical Engineering and Computer Science from the National Technical University of Athens and PhD in Computer Science from the University of Oxford.

Prof. Bingsheng Zhang 

Bingsheng Zhang is currently a ZJU100 Professor at the College of Computer Science and Technology, Zhejiang University, Hangzhou, China. He is the PI of National Key R&D Programmes of China. Before that, he was program director of Lancaster University’s master’s degree in cybersecurity and leader of the university’s security research group. He specializes in cryptography, multi-party computation, verifiable electronic voting (e-voting), and zero-knowledge proofs. He has published over 60 papers at top-tier conferences and journals in cryptography and security, such as Eurocrypt, Asiacrypt, PKC, CCS, NDSS, PODC, Infocom, IEEE TIFS, IEEE TDSC, and IEEE TSC, etc. He is the editor of ISO/IEC 27565 "Guidelines on privacy preservation based on zero knowledge proofs" and the secretary of IEEE P2842 workgroup on "Recommended Practice for Secure Multi-party Computation".

Dr. Dmytro Kaidalov 

Dmytro is a blockchain researcher, cryptographer, and software engineer. He studied information security and obtained a PhD in the field of symmetric cryptography. With over 15 years of experience in the tech industry, Dmytro has spent more than seven years specifically in the blockchain space. Currently serving as a research engineer at Input Output, he focuses on designing and prototyping new protocols and systems, including consensus schemes, stablecoins, voting schemes, cross-chain protocols, and more. Dmytro has been actively contributing to Catalyst since its inception. He played a major role in developing the privacy-preserving voting scheme that is one of the key elements in Catalyst. He also contributed to the design of the review system. Overall, Dmytro has amassed extensive knowledge and expertise in blockchain voting systems.

Prof. Lyudmila Kovalchuk 

Lyudmila is a mathematician, cryptographer and blockchain researcher. She studied mathematics and obtained a PhD in the field of Probability theory and Mathematical statistics, and Dr. Habil. in Cryptology. She has been working in blockchain research for more than 7 years, started in 2016 as a research fellow at IOG. Lyudmila has a great teaching experience for over 20 years, working at the National Technical University of Ukraine “Kyiv Polytechnical Institute named after Ihor Sykorskii” and other universities as a professor. She is the author of National and harmonised Standards of Ukraine in Cryptology. Lyudmila has over 40 academic papers in leading academic conferences and journals, and more than 20 papers among those are published with IOG research - blockchain security and privacy, ZKP, analysis and proofs of voting systems properties in Catalyst.

Dr. Andrii Nastenko 

Andrii is a research engineer at IOG. He graduated from Kharkiv National University of Radioelectronics, Ukraine as a Master of Science, then a postgraduate as PhD in Information security with a thesis on symmetric cryptography. He participated in numerous projects on cryptography-space research and information security-related software development resulting in a 15-year expertise with 7 years specifically in blockchain technologies. Since 2016 when Andrii started as a Research Fellow in IOG (IOHK) he became a co-creator of the Cardano Catalyst treasury system including the underlying voting protocol and participated in the initial research for Midnight. He also acted as a co-developer in the initial phase of Zen cryptocurrency project. Having accumulated a significant amount of knowledge in distributed information technologies now he is focused on the research of the DAOs-related voting schemes together with the development of prospective distributed voting crypto-protocols providing optimal performance, quantum resistance, coercion resistance, adaptive security and other top-edge properties desired for modern distributed voting systems.

Dr. Mariia Rodinko 

Mariia Rodinko received a Ph.D. degree in computer science at V. N. Karazin Kharkiv National University, Ukraine. She has been working for IOG since 2016. Currently, Mariia is IOG Junior Research Fellow and an associate professor at Systems and Technologies Modeling Department at V. N. Karazin Kharkiv National University, Ukraine. In IOG she mainly concentrates on projects dedicated to blockchain governance, decentralized auctions and analysis of distributed consensus protocols. She also has a solid background in cryptography and cryptanalysis. Mariia has 24 research publications in leading academic conferences and journals.

Dr. Oleksii Shevtsov

Olexiy has been involved in IOG research since 2016. His research merges new industry problems with known frameworks of social choice, analysis and measure. His academic background is in information security, where he obtained a Ph.D. degree in the field of public key cryptography. He is particularly involved in the voting mechanisms and consensus among participants, especially in reaching fairness and verifiability.

Zeyuan Yin 

Zeyuan Yin received his B.E. degree in Computer Science from Shandong University in 2021. Currently, he is pursuing his Ph.D. degree at Zhejiang University. His research interests mainly focus on electronic voting (e-voting), blockchain, and zero-knowledge proofs. So far, he has published a paper on IEEE TIFS, and he won the third prize in the WPPCC 2022 Privacy-Preserving Computing Competition and the "Outstanding Team Award" in the Xinghe Cup 2023 Privacy-Preserving Computing Competition.

Photrek: 

Dr. Kenric Nelson is the Founder and President of Photrek, LLC which is developing novel approaches to Complex Decision Systems, including risk-aware machine intelligence, particularly for environmental risks, and governance policies for decentralized communities. He served on the Cardano Catalyst Circle governance council and is leading a revitalization of Sociocracy for All’s @work circle. Prior to launching Photrek, Nelson was a Research Professor with Boston University Electrical & Computer Engineering (2014-2019) and Sr. Principal Systems Engineer with Raytheon Company (2007-2019). He has pioneered novel information metrics that are improving the training of machine learning algorithms. His education in electrical engineering includes a B.S. degree Summa Cum Laude from Tulane University, a M.S. degree from Rensselaer Polytechnic Institute, and a Ph.D. degree from Boston University. His management education includes an Executive Certificate from MIT Sloan and participation in NSF’s I-Corp program.

Megan Hess, Communications Lead at Photrek, serves as the facilitator in Photrek’s Cardano Circle, coordinating initiatives supporting governance and risk intelligence. Megan collaborated with Photrek on their first Catalyst project, Diversifying Voting Influence. She was selected by her Photrek colleagues to represent the contracting team on Photrek’s Advisory Circle. Megan is acting as the Sub-Regional coordination lead with Wada for Central Africa, Francophone liaison, and Cameroon Team Lead. She has a Bachelor’s degree in Physics from the University of Denver and has taught Middle/High School Math and Physics.

Juana Attieh, product lead at Photrek, leading the Cardano circle and facilitating the SNET circle. Co-founder of Cardano MENA and LALKUL Stake Pool. Interim chair at the Membership and Community Committee at Intersect. Advisor at AMLOK.tech. Juana is committed to fostering decentralized governance and contributing towards optimal solutions for self-organizing systems. With her work, Juana seeks to reimagine societies, unlock untapped potential, and provide inclusive opportunities to those who need them most.

Dr. André L. M. Vilela has investigated the dynamics of interacting agent-based models in statistical mechanics, combining phase transitions, critical phenomena, and finite-size scaling analysis with sociophysics, econophysics, and complex network theory. His research focuses on unveiling the underlying mathematical mechanisms that drive the behavior of agents in groups within social networks and financial markets, and how their decisions promote active collective phenomena. He is a Distinguished Visiting Scientist at Boston University, an Associate Professor at the University of Pernambuco, and Former Coordinator of the Materials Physics undergraduate program. His education in Physics includes completing a B.S. degree With High Honors Award, an MSc. degree with Distinction Award, and a Ph.D. degree from the Federal University of Pernambuco

Catalyst Team

Steven Johnson: Catalyst Lead Architect

Steven will lead the evaluation and analysis of new cryptographic protocol and their effect on the Catalyst Hermes and voting architecture

Kriss Baird, GM and Head of Product

Kriss will be principally accountable for project management, ensuring all deliverables are produced to a high quality. He will provide product analysis of use-cases for alternative voting mechanisms and will lead on the dissemination activities in collaboration with IOG Research and Photrek. Kriss will be responsible for managing internal resources required to deliver the project within budget and on-time.

[BUDGET & COSTS] Please provide a cost breakdown of the proposed work and resources.

The budget requested will be used primarily to cover the costs of people resources required to deliver the project scope. This includes community members and members of IOG Research and Catalyst teams. 

M1: Literature review of shortlisted voting schemes: ₳120,000

M2: Early Voting schema analysis and proofs: ₳95,000

M3: Cryptographic research for new voting protocols: ₳95,000

M4: Architecture design and basic prototyping: ₳95,000

M5: Research ready for peer-review and publication: ₳95,000

The primary phases of the project are outlined below, along with the percent allocation of the budget toward each phase of research:

• 43% Literature review and selection analysis
• 38% Cryptography and prototyping
• 19% Research Outcomes

Community co-proposers listed on the proposal, will play a significant role in both the research and evaluation required for this project:

Selection of and initial analysis of viable voting methods

• Photrek will lead the selection of voting methods in collaboration with IOG & the community.

Collaboration with IOG research on scientific evaluation

• Photrek will support IOG Research with scientific expertise in voting simulation and analysis.

Community dissemination and feedback

• Photrek will support IOG Catalyst in publications, workshops, and recommendations for the Catalyst development roadmap.

[VALUE FOR MONEY] How does the cost of the project represent value for money for the Cardano ecosystem?

Alternative Voting Mechanisms research brings to Catalyst and Cardano:

• Open access to the cutting edge decision making technologies research for implementation by third parties developing decentralised systems, brought forward by world leading expertise.  
• Novel cryptographic protocols supporting the selected solutions that guarantee fairness, verifiability and other properties of the decision making
• Independent and objective scientific results instead of by preference of an individual founder or the development team
• Open source prototype implementation of the cryptographic voting protocols and benchmarks for them,also available as the reference implementation for other projects / ecosystems interested in decentralised decision making
• Integral system results for Catalyst where research outputs can be discussed among connecting different solutions from several research and development teams. We expect to deliver this for others to then build from. 

The value case for Catalyst implementation is unlocked by this research

• Advancing decision-making properties in Catalyst
• Improve sentiment agreement rates of fairness of community-made decisions in Catalyst, leading to further demonstration of trust in distributed decision making at scale
• Practical data on decision outcomes is collected to supplement the research findings
• Reference implementation for other projects or ecosystems interested in distributed decision making

[IMPORTANT NOTE] The Applicant agrees to Fund Rules and also that data in the submission form and other data provided by the project team during the course of the project will be publicly available.

I Accept