PureLottery: Fair and Bias-Resistant Leader Election with a Novel Single-Elimination Tournament Algorithm
- URL: http://arxiv.org/abs/2402.17459v1
- Date: Tue, 27 Feb 2024 12:30:17 GMT
- Title: PureLottery: Fair and Bias-Resistant Leader Election with a Novel Single-Elimination Tournament Algorithm
- Authors: Jonas Ballweg,
- Abstract summary: Leader Election (LE) is crucial in distributed systems and blockchain technology, ensuring one participant acts as the leader.
Traditional LE methods often depend on distributed random number generation (RNG), facing issues like vulnerability to manipulation, lack of fairness, and the need for complex procedures such as verifiable delay functions (VDFs) and publicly-verifiable secret sharing (PVSS)
This Bachelor's thesis presents a novel approach to randomized LE, leveraging a game-theoretic assumption that participants, aiming to be chosen as leaders, will naturally avoid actions that diminish their chances.
This perspective simplifies LE by eliminating the need for decentralized
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Leader Election (LE) is crucial in distributed systems and blockchain technology, ensuring one participant acts as the leader. Traditional LE methods often depend on distributed random number generation (RNG), facing issues like vulnerability to manipulation, lack of fairness, and the need for complex procedures such as verifiable delay functions (VDFs) and publicly-verifiable secret sharing (PVSS). This Bachelor's thesis presents a novel approach to randomized LE, leveraging a game-theoretic assumption that participants, aiming to be chosen as leaders, will naturally avoid actions that diminish their chances. This perspective simplifies LE by eliminating the need for decentralized RNG. Introducing PureLottery, inspired by single-elimination sports tournaments, this method offers a fair, bias-resistant, and efficient LE solution for blockchain environments. It operates on the principle of two participants competing in each match, rendering collusion efforts useless. PureLottery stands out for its low computational and communication complexity, suitable for smart contract implementation. It provides strong game-theoretic incentives for honesty and is robust against adversaries, ensuring no increase in election chances through dishonesty. The protocol guarantees that each honest player has at least a 1/n chance of winning, irrespective of adversary manipulation among the other n-1 participants. PureLottery can also address related problems like participant ranking, electing multiple leaders, and leader aversion, showcasing its versatility across various applications, including lotteries and blockchain protocols. An open-source implementation is made available for public use.
Related papers
- Profitable Manipulations of Cryptographic Self-Selection are Statistically Detectable [4.704825771757308]
We study the detectability of profitable manipulations of the canonical cryptographic self-selection leader selection protocol introduced in [CM19].
We show that for any player with $alpha frac3-sqrt52 approx 0.38$ fraction of the total stake, every strictly profitable manipulation is statistically detectable.
arXiv Detail & Related papers (2024-07-24T02:34:01Z) - Fuzzychain: An Equitable Consensus Mechanism for Blockchain Networks [12.433289572707212]
Fuzzychain is a proposed solution to the drawbacks of Proof of Stake (PoS)
It introduces the use of fuzzy sets to define stake semantics, promoting decentralised and distributed processing control.
Our results indicate that Fuzzychain not only matches PoS in functionality but also ensures a fairer distribution of stakes among validators.
arXiv Detail & Related papers (2024-04-20T10:01:40Z) - Enhancing Trust and Privacy in Distributed Networks: A Comprehensive Survey on Blockchain-based Federated Learning [51.13534069758711]
Decentralized approaches like blockchain offer a compelling solution by implementing a consensus mechanism among multiple entities.
Federated Learning (FL) enables participants to collaboratively train models while safeguarding data privacy.
This paper investigates the synergy between blockchain's security features and FL's privacy-preserving model training capabilities.
arXiv Detail & Related papers (2024-03-28T07:08:26Z) - Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit [14.822625665220068]
We study a robust multi-agent multi-armed bandit problem where multiple clients or participants are distributed on a fully decentralized blockchain.
We are the first to incorporate advanced techniques from blockchains, as well as novel mechanisms, into the system to design optimal strategies for honest participants.
This is consistent with the multi-agent multi-armed bandit problem without malicious participants and the robust multi-agent multi-armed bandit problem with purely Byzantine attacks.
arXiv Detail & Related papers (2024-02-06T21:33:34Z) - Building Random, Fair, and Verifiable Games on Blockchain. Raffle smart
contract designs on Sui Network [10.410456199908587]
This paper aims to provide insights into designing a fair, verifiable, and efficient smart contract game on blockchain.
We explore efficient methods for implementing randomness on smart contracts, including DRAND committee-based decentralized random beacons and single private-key-based verifiable random functions (VRF)
Our findings provide valuable guidance for future researchers and developers in building random, fair, and verifiable games with smart contracts.
arXiv Detail & Related papers (2023-10-18T20:12:44Z) - A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks [0.6216023343793144]
We provide a protocol for distributed generation of randomness.
It is trustless and generates unbiased random numbers.
It is also tamper-proof and no party can change the output or affect its distribution.
arXiv Detail & Related papers (2023-09-20T12:21:39Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
Two-player zero-sum Markov games are arguably the most basic setting in multi-agent reinforcement learning.
We develop a learning algorithm that learns an $varepsilon$-approximate Markov NE policy using $$ widetildeObigg.
We derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities.
arXiv Detail & Related papers (2022-08-22T17:24:55Z) - Dual Lottery Ticket Hypothesis [71.95937879869334]
Lottery Ticket Hypothesis (LTH) provides a novel view to investigate sparse network training and maintain its capacity.
In this work, we regard the winning ticket from LTH as the subnetwork which is in trainable condition and its performance as our benchmark.
We propose a simple sparse network training strategy, Random Sparse Network Transformation (RST), to substantiate our DLTH.
arXiv Detail & Related papers (2022-03-08T18:06:26Z) - You are caught stealing my winning lottery ticket! Making a lottery
ticket claim its ownership [87.13642800792077]
Lottery ticket hypothesis (LTH) emerges as a promising framework to leverage a special sparse subnetwork.
Main resource bottleneck of LTH is however the extraordinary cost to find the sparse mask of the winning ticket.
Our setting adds a new dimension to the recently soaring interest in protecting against the intellectual property infringement of deep models.
arXiv Detail & Related papers (2021-10-30T03:38:38Z) - Secure Distributed Training at Scale [65.7538150168154]
Training in presence of peers requires specialized distributed training algorithms with Byzantine tolerance.
We propose a novel protocol for secure (Byzantine-tolerant) decentralized training that emphasizes communication efficiency.
arXiv Detail & Related papers (2021-06-21T17:00:42Z) - Multi-Stage Decentralized Matching Markets: Uncertain Preferences and
Strategic Behaviors [91.3755431537592]
This article develops a framework for learning optimal strategies in real-world matching markets.
We show that there exists a welfare-versus-fairness trade-off that is characterized by the uncertainty level of acceptance.
We prove that participants can be better off with multi-stage matching compared to single-stage matching.
arXiv Detail & Related papers (2021-02-13T19:25:52Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.