Instant Runoff Voting (IRV) is one example of ranked-choice voting. It provides many known benefits when used in elections, such as minimising vote splitting, ensuring few votes are wasted, and providing resistance to strategic voting. However, the voting and tallying procedures for IRV are much more complicated than those of plurality and are both error-prone and tedious. Many automated systems have been proposed to simplify these procedures in IRV. Some of these also employ cryptographic techniques to protect the secrecy of ballots and enable verification of the tally. Nearly all of these cryptographic systems require a set of trustworthy tallying authorities (TAs) to perform the decryption of votes and/or running of mix servers, which adds significant complexity to the implementation and election management. We address this issue by proposing Camel: an E2E verifiable solution for IRV that requires no TAs. Camel employs a novel representation and a universally verifiable shifting procedure for ballots that facilitate the elimination of candidates as required in an IRV election. We combine these with a homomorphic encryption scheme and zero-knowledge proofs to protect the secrecy of the ballots and enable any party to verify the well-formedness of the ballots and the correctness of the tally in an IRV election. We examine the security of Camel and prove it maintains ballot secrecy by limiting the learned information (namely the tally) against a set of colluding voters.
Georgios Birmpas, Philip Lazos, Evangelos Markakis, Paolo Penna
In this paper, we investigate the impact of reward schemes and committee sizes motivated by governance systems over blockchain communities. We introduce a model for elections with a binary outcome space where there is a ground truth (i.e., a "correct" outcome), and where stakeholders can only choose to delegate their voting power to a set of delegation representatives (DReps). Moreover, the effort (cost) invested by each DRep positively influences both (i) her ability to vote correctly and (ii) the total delegation that she attracts, thereby increasing her voting power. This model constitutes the natural counterpart of delegated proof-of-stake (PoS) protocols, where delegated stakes are used to elect the block builders. As a way to motivate the representatives to exert effort, a reward scheme can be used based on the delegation attracted by each DRep. We analyze both the game-theoretic aspects and the optimization counterpart of this model. Our primary focus is on selecting a committee that maximizes the probability of reaching the correct outcome, given a fixed monetary budget allocated for rewarding the delegates. Our findings provide insights into the design of effective reward mechanisms and optimal committee structures (i.e., how many DReps are enough) in these PoS-like governance systems.
Niclas Boehmer, Markus Brill, Alfonso Cevallos, Jonas Gehrlein · 6 authors
We provide the first large-scale data collection of real-world approval-based committee elections. These elections have been conducted on the Polkadot blockchain as part of their Nominated Proof-of-Stake mechanism and contain around one thousand candidates and tens of thousands of (weighted) voters each. We conduct an in-depth study of application-relevant questions, including a quantitative and qualitative analysis of the outcomes returned by different voting rules. Besides considering proportionality measures that are standard in the multiwinner voting literature, we pay particular attention to less-studied measures of overrepresentation, as these are closely related to the security of the Polkadot network. We also analyze how different design decisions such as the committee size affect the examined measures.
Given n participants, leader election (LE) is the process of designating one of them as the leader or coordinator. LE is ubiquitous in distributed computing and blockchain and has a wide variety of applications ranging from lotteries to proof-of-stake (PoS) protocols and decentralized autonomous organizations (DAOs). In a blockchain setting, we normally require our LE protocol to be decentralized, lead to a consensus about the elected leader, and be fair, i.e. elect each participant with the same probability $1 /n.$ Traditional blockchain LE solutions reduce the problem to decentralized uniform sampling from the set $\{1,2, \ldots, n\}.$ This reduction leads to approaches which are either vulnerable to manipulation, or fail to guarantee fairness, or require inefficient procedures such as verifiable delay functions (VDFs) and publicly-verifiable secret sharing (PVSS), thus making them gas-inefficient and costly when implemented as smart contracts.In this work, we observe that fair leader election can be achieved without explicit decentralized random number generation (RNG). In other words, the intuition behind our work is that RNG is a strictly harder problem than LE. This is because every LE participant is assumed to prefer to be chosen as the leader, e.g. the participant prefers to win the lottery or be the miner for the next PoS block. Thus, they will refrain from actions that would reduce their chance of being selected. This game-theoretic incentive can be exploited to design much simpler protocols for LE in comparison to RNG, by ensuring that dishonest behavior can only reduce the winning chances of the participant.Specifically, we propose PureLottery, a protocol inspired by single-elimination knockout tournaments in sports such as football. We show that PureLottery selects the winner uniformly at random and provides strong game-theoretic guarantees to incentivize honest behavior. PureLottery is also strongly bias-resistant in the sense that every honest participant is guaranteed to win the lottery with probability at least $1 /n$, even if an adversary controls all of the other $n -1$ players. In other words, dishonest behavior will never increase an adversary’s chances of being elected, even if the adversary controls all but one of the participants. Finally, PureLottery is a simple protocol that can be efficiently implemented as a smart contract and uses a small amount of gas in practice. We provide an open-source implementation of the protocol, dedicated to the public domain with no copyright.
Samuel H. Christie, Lalana Kagal, Alessandro Ricci, Munindar P. Singh
The articles in this special section focuses on decentralized systems. Our world is filled with decentralized systems, human society and organizations being the most familiar examples. In such systems, we see multiple loci of ownership or control, representing different parties or administrative domains. That is, the members of a decentralized system are, belong to, or represent different people or organizations. We use the term decentralized system to mean any system formed of autonomous entities, with a special interest in cases where the entities are heterogeneous. Autonomy here refers to the decision-making capacity of an entity, meaning that it decides for itself. In other words, autonomy reflects the freedom to act. Heterogeneity here refers to the design, construction, and configuration of an entity, meaning that it is potentially built on distinct grounds from any other entity. In other words, heterogeneity reflects the freedom of a designer to apply any reasoning method on any available information.
Liangde Tao, Lin Chen, Lei Xu, Weidong Shi · 6 authors
Many research works in computational social choice assume a fixed set of voters in an election and study the resistance of different voting rules against electoral manipulation. In recent years, however, a new technique known as random sample voting has been adopted in many multi-agent systems. One of the most prominent examples is blockchain. Many proof-of-stake based blockchain systems like Algorand will randomly select a subset of participants of the system to form a committee, and only the committee members will be involved in the decision of some important system parameters. This can be viewed as running an election where the voter committee (i.e., the voters whose votes will be counted) is randomly selected. It is generally expected that the introduction of such randomness should make the election more resistant to electoral manipulation, despite the lack of theoretical analysis. In this paper, we present a systematic study on the resistance of an election with a randomly selected voter committee against bribery. Since the committee is randomly generated, by bribing any fixed subset of voters, the designated candidate may or may not win. Consequently, we consider the problem of finding a feasible solution that maximizes the winning probability of the designated candidate. We show that for most voting rules, this problem becomes extremely difficult for the briber as even finding any non-trivial solution with non-zero objective value becomes NP-hard. However, for plurality and veto, there exists a polynomial time approximation scheme that computes a near-optimal solution efficiently. The algorithm builds upon a novel integer programming formulation together with techniques from n-fold integer programming, which may be of a separate interest.
We study a scenario where an adjudication task (e.g., the resolution of a binary dispute) is outsourced to a set of agents who are appointed as jurors. This scenario is particularly relevant in a Web3 environment, where no verification of the adjudication outcome is possible, and the appointed agents are, in principle, indifferent to the final verdict. We consider simple adjudication mechanisms that use (1) majority voting to decide the final verdict and (2) a payment function to reward the agents with the majority vote and possibly punish the ones in the minority. Agents interact with such a mechanism strategically: they exert some effort to understand how to properly judge the dispute and cast a yes/no vote that depends on this understanding and on information they have about the rest of the votes. Eventually, they vote so that their utility (i.e., their payment from the mechanism minus the cost due to their effort) is maximized. Under reasonable assumptions about how an agent's effort is related to her understanding of the dispute, we show that appropriate payment functions can be used to recover the correct adjudication outcome with high probability. Our findings follow from a detailed analysis of the induced strategic game and make use of both theoretical arguments and simulation experiments.
Xiaotong Sun, Xi Chen, Charalampos Stasinakis, Georgios Sermpinis
Decentralized Autonomous Organization (DAO) provides a decentralized governance solution through blockchain, where decision-making process relies on on-chain voting and follows majority rule. This paper focuses on MakerDAO, and we find three voter coalitions after applying clustering algorithm to voting history. The emergence of a dominant voter coalition is a signal of governance centralization in DAO, and voter coalitions have complicated influence on Maker protocol, which is governed by MakerDAO. This paper presents empirical evidence of multicoalition democracy in DAO and further contributes to the contemporary debate on whether decentralized governance is possible.
Jan 1, 2022·Proceedings of the ... Annual Hawaii International Conference on System Sciences/Proceedings of the Annual Hawaii International Conference on System Sciences
Tom Barbereau, Reilly Smethurst, Orestis Papageorgiou, Alexander Rieger · 5 authors
Bitcoin and Ethereum are frequently promoted as decentralized, but developers and academics question their actual decentralization. This motivates further experiments with public permissionless blockchains to achieve decentralization along technical, economic, and political lines. The distribution of tokenized voting rights aims for political decentralization. Tokenized voting rights achieved notoriety within the nascent field of decentralized finance (DeFi) in 2020. As an alternative to centralized crypto-asset exchanges and lending platforms (owned by companies like Coinbase and Celsius), DeFi developers typically create non-custodial projects that are not majority-owned or managed by legal entities. Holders of tokenized voting rights can instead govern DeFi projects. To scrutinize DeFi’s distributed governance strategies, we conducted a multiple-case study of non-custodial, Ethereum-based DeFi projects: Uniswap, Maker, SushiSwap, Yearn Finance, and UMA. Our findings are novel and surprising: quantitative evaluations of DeFi’s distributed governance strategies reveal a failure to achieve political decentralization.
In river systems, costly upstream pollution abatement creates downstream welfare gains. Absent adequate agreement on how to share the gains, upstream regions lack incentives to reduce pollution levels. We develop a model that makes explicit the impact of water quality on production benefits and suggest a solution for sharing the gains of optimal pollution abatement, namely the Shapley value of an underlying convex cooperative game. We provide a decentralized implementation through a smart contract to automate negotiations and payments. In effect, it ensures a socially optimal agreement supported by fair compensations to regions that turn to cleaner production from those that pollute.
Proof-of-vote is a third generation of the Nakamoto consensus. With proof-of-vote, validators compete for people-votes, using proof-of-suffrage given by proof-of-person, and authorize transactions based on authority delegated by the consensus mechanism, just like proof-of-work or proof-of-stake. This logical conclusion of the Nakamoto consensus allows a “nation” of people to secure their own ledger, the equivalent of representative democracy for distributed ledger technology.
More details: https://shivarthu.reaudito.com/ Democracy is about fair and equal treatment of everyone in a country. But itbecomes unrealistic to achieve when political parties have their conflict of interest,and leaders don’t have the expertise to make evidence-based policies and neitherhave the skill and manpower for solving problems that surround our society andecosystem. The new fair democracy provides an elegant way of governance thatseparates the representative responsibility according to their specialization and cangrow into any complexity. The governance is divided into various departments, andeach department is supervised by representatives with expertise in the field. Votersneed to have enough knowledge about the departments and their problems, in orderto vote for the selecting representatives of a department. The selection process ofrepresentatives is difficult in and easy out, which allows only serious and utilitarianactors to hold the responsibility, weeding out frivolous ones.
We study the liquid democracy problem, where each voter can either directly vote to a candidate or delegate his voting power to a proxy. We consider the implementation of liquid democracy on the blockchain through Ethereum smart contract and to be compatible with the realtime self-tallying property, where the contract itself can record ballots and update voting status upon receiving each voting massage. A challenge comes due to the gas fee limitation of Ethereum mainnet, that the number of instruction for processing a voting massage can not exceed a certain amount, which restrict the application scenario with respect to algorithms whose time complexity is linear to the number of voters. We propose a fast algorithm to overcome the challenge, such that i) shifts the on-chain initialization to off-chain and ii) the on-chain complexity for processing each voting massage is O(\log n), where n is the number of voters.
ABSTRACT: Proof-of-vote is a third generation of the Nakamoto consensus. With proof-of-vote, validators compete for people-votes, using proof-of-suffrage given by proof-of-person, and authorize transactions based on authority delegated by the consensus mechanism, just like proof-of-work or proof-of-stake. This logical conclusion of the Nakamoto consensus allows a “nation” of people to secure their own ledger, the equivalent of representative democracy for distributed ledger technology.
The purpose of this paper is to show how the mechanism of the reward structure for cryptocurrency mining (known as “Proof of Work†) is applicable to alleviation of the free rider problem for voluntary public goods provision. This paper presents the following results. First, if each individual reports preferences honestly, then the Samuelson condition can hold. It is possible to set an appropriate level of mining. Second, if the scheme (mechanism) offered by our manuscript is introduced, public goods can theoretically be provided at a Pareto optimal level under certain conditions because each rational individual reports true preferences to the government.
We propose a design for philanthropic or publicly-funded seeding to allow (near) optimal provision of a decentralized, self-organizing ecosystem of public goods. The concept extends ideas from Quadratic Voting to a funding mechanism for endogenous community formation. Individuals make public goods contributions to projects of value to them. The amount received by the project is (proportional to) the square of the sum of the square roots of contributions received. Under the standard model this yields first best public goods provision. Variations can limit the cost, help protect against collusion and aid coordination. We discuss applications to campaign finance, open source software ecosystems, news media finance and urban public projects. More broadly, we offer a resolution to the classic liberal-communitarian debate in political philosophy by providing neutral and non-authoritarian rules that nonetheless support collective organization.
Countries like Estonia, Norway or Australia developed electronic voting systems, which could be used to realize parliamentary elections with the help of personal computers and the Internet. These systems are completely different in their design and their way to solve the same problem. In this thesis, we analyze some of the largest real-world systems, describe their building blocks and their general design to focus on possible problems in these electronic voting systems. Furthermore, we present a template for an e-voting system, which we designed to try to fulfill the preliminaries and requirements of a secure electronic voting system. We use the experiences and the building blocks of existing systems to combine them to another more secure system. Afterwards, we compare our concept with real-world systems to evaluate the fulfillments of the requirements. Conclusively, we discuss the occurring problems when designing a secure system. Peer-to-peer networks provide many advantages, like decentralization, which might be applicable to electronic voting systems. Therefore, we take a look on the distributed database called blockchain and the usage in a peer-to-peer voting system. Our contribution to this topic is a modification of the proof-of-stake, which enables the usage of common devices, like smartphones or tablets, for the blockchain verification and inclusion of new ballots to the chain. This proof does not need much computing power and has a lower carbon footprint than the proof-of-work in the Bitcoin protocol.