Game-Theoretically Secure Protocols Inspired by Blockchains
summary
Claims a constructive protocol that achieves game-theoretic leader election with corrupt majority and no trusted setup, improving from the usual log n tournament tree to log log n rounds under an ε-approximate fairness definition. Key tools are a downsampling-to-polylog committee, a seeded extractor/sampler (replacing a random oracle), and an honest‑majority MPC to choose a masked permutation of virtual IDs + masked permutation so small coalitions cannot bias their own chances. The protocol is built and proven under standard cryptographic assumptions; fairness degrades multiplicatively by ε and admits a stronger sequential fairness variant.
AI-written summary · about
chapters (15)
- 0:00Intro
- 1:10Motivation
- 2:01Coin Toss Protocol
- 3:26Coin Toss Requirements
- 5:28Multiparty Coin Toss
- 8:29Theoretic Coin Toss
- 10:59Tournament Tree Protocol
- 15:06Naive Ideas
- 16:00Results
- 27:41Strongman Scheme
- 33:58Random Article
- 36:28Majority NPC
- 38:36Highlevel idea
- 40:08Analysis
- 42:48Explanation
related talks
33mHow Fair is your Protocol? A Utility-Based Approach to Protocol Optimality
24mAutomated game-theoretic security analysis of blockchain protocols
34mProvably Secure Blockchain Protocols and Applications to Secure Computation
14mDivide and Conquer: A Compositional Approach to Game-Theoretic Security
34mQuantum and Classical Coin-flipping Protocols Based on Bit-commitment and their Point Games
34mConsensus with Adaptive Adversaries in the Synchronous and Partially Synchronous Models...
42mStochastic reasoning in decentralised systems
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing