Share this page!

Enter URL or ID to Unroll

You can paste full URL like: https://x.com/threadreaderapp/status/1644127596119195649
or just the ID like: 1644127596119195649

How to get URL link on X (Twitter) App

  1. On the Twitter thread, click on or icon on the bottom
  2. Click again on or Share Via icon
  3. Click on Copy Link to Tweet
  4. Paste it above and click "Unroll Thread"!
  5. More info at Twitter Help
Tim Roughgarden Profile picture
Tim Roughgarden
@Tim_Roughgarden
Head of Research @a16z. Prof @Columbia. Theoretical computer scientist. Educator. Wrote Algorithms Illuminated, 20 Lectures on Algorithmic Game Theory, etc.
Maleph Profile picture Hakan Profile picture marouan.eth Profile picture 3 subscribed
Apr 2 • 19 tweets • 5 min read
• Which auction formats are robust to shill bidding?

• Why are Dutch auctions so popular in Web3?

• What happens if you change the credible auctions model to have public rather than private communication?

A new paper with Andrew Komo and @skominers answers all these questions 👇 (1/19)Image The paper lays out a theory of *shill-proof* auctions (2/19) Image
Feb 16 • 7 tweets • 2 min read
Happy to report that the main open theory question from my original work on EIP-1559 has been resolved (with two brilliant collaborators, Hao Chung and @ElaineRShi)---no transaction fee mechanism can be DSIC, MMIC, and OCA-proof!
(more context below) 1/7arxiv.org/pdf/2402.09321… DSIC: users have an "obvious optimal bid"
MMIC: miner/validator is instructed to maximize their fee revenue, has no incentive to insert fake transactions
OCA-proof: if miner + all users collude off-chain, they can't do better collectively than in canonical on-chain outcome 2/7
Jan 23 • 11 tweets • 3 min read
Meta-thread summarizing (most of) the results from my "Permissionless Consensus" paper with @AndrewLewisPye (1/11) Intro thread: (2/11)
Jan 19 • 11 tweets • 2 min read
Last thread (promise!) on results from my permissionless consensus paper with @AndrewLewisPye. The topic: are long-range attacks unavoidable for proof-of-stake blockchains? (1/11) We've known about long-range attacks for a long time (e.g. ). So what are they? (2/11)blog.ethereum.org/2014/05/15/lon…
Jan 10 • 10 tweets • 3 min read
Longest-chain protocols (or any protocol built for the dynamically available (DA) setting) must give up on a bunch of properties that you'd want (partition-resilience, accountability, optimistic responsiveness). Can PoS PBFT-style protocols do better? (1/10) [cc @AndrewLewisPye] Tl;dr: yes, on all counts, at least if you're willing to adopt the stronger assumptions of the quasi-permissionless (QP) setting! (2/10)
Dec 21, 2023 • 20 tweets • 4 min read
Should proof-of-stake blockchain protocols follow the longest-chain tradition of Bitcoin, the PBFT-style tradition of permissioned protocols, or something else entirely? The trade-offs are pretty fascinating, so let's dive in (cc @AndrewLewisPye) (1/20) The short answer is that PBFT-style PoS protocols make stronger assumptions about participation than longest-chain PoS protocols but, if these assumptions hold up, they can offer stronger guarantees like accountability, optimistic responsiveness, and partition-resilience (2/20)
Dec 14, 2023 • 9 tweets • 3 min read
if you assume nothing about who's running a blockchain protocol (as in e.g. Bitcoin) => you're stuck with probabilistic safety and liveness guarantees (as in Bitcoin)

but what about under (slightly) stronger participation assumptions? (w/@AndrewLewisPye) (1/9) our dynamically available (DA) setting assumes something that our fully permissionless (FP) setting does not:
if there are any honest players with non-zero stake at some time t, then there is at least one such player that actually bothers to run the protocol at that time (2/9) Image
Dec 13, 2023 • 20 tweets • 4 min read
The first main result in the "Permissionless Consensus" paper with @AndrewLewisPye is an FLP-type impossibility result for Bitcoin-style protocols (even in synchrony). What does that mean, exactly? (1/20) The Bitcoin protocol is remarkable in that it assumes literally nothing about who is running it at any given moment---in our terminology, the protocol works even in the fully permissionless (FP) setting (2/20)
Nov 17, 2023 • 9 tweets • 2 min read
A quick thread on what @AndrewLewisPye and I mean by "permissionless consensus" (1/9) The Bitcoin protocol solves a classical consensus problem known as "state machine replication (SMR)." In Bitcoin, the "state" is basically the current set of UTXOs. Researchers in distributed computing/systems have worked on SMR protocols since at least the 1980s (2/9)
Nov 16, 2023 • 6 tweets • 2 min read
.@AndrewLewisPye and I have, for years, been iterating on mathematical models for the design and analysis of permissionless consensus protocols 👇 Image We're finally happy with one, a "sweet spot" model that is both very general (accommodating most of the major approaches to sybil-resistance, consensus, long-range attack defense, etc.) and user-friendly enough to enable lots of different possibility and impossibility results
Jul 6, 2023 • 13 tweets • 3 min read
Lots of competing proposals out there for how to deal with MEV: OFAs and other competitive markets, encrypted mempools, MPC, TEEs, etc. But do we truly need any of these? Yes! And, with @bahrani_maryam and @PGarimidi, we have the math to prove it:👇
1/12 Image Background: a transaction fee mechanism (TFM) is the part of a blockchain protocol responsible for figuring out which transactions should be included and who should pay what. Example: EIP-1559.
2/12
Nov 19, 2022 • 9 tweets • 2 min read
(1/8) Slightly expanded version of my CESC talk, "On Some Results and Challenges in Cryptoeconomics":
tl;dr👇 (2/8) Many problems in cryptoeconomics can be viewed as mechanism design ("inverse game theory") with access to a native currency. But with power (e.g., ability to mint/burn) comes responsibility (macroeconomic consequences).
Oct 17, 2022 • 15 tweets • 2 min read
Lecture 9 (permissionless consensus and proof-of-work) of the Foundations of Blockchains lecture series is another two-part doozy. Here's part 1:
tl;dr thread (for part 1) below:
1/15 A permissionless protocol operates without knowledge of the set of nodes running the protocol.
2/15
Oct 1, 2022 • 11 tweets • 2 min read
Finally finished Lecture 8 of Foundations of Blockchains (on longest-chain consensus):
conclusion of tl;dr thread below
1/11 The common prefix property states that every pair of longest chains should agree on all but at most their last k blocks.
2/11
Aug 27, 2022 • 4 tweets • 1 min read
Coming soon to your favorite bookseller: 700pp, hardcover with offset printing, list price $60. Includes all of Algorithms Illuminated Parts 1-4 (The Basics; Graph Algorithms and Data Structures; Greedy Algorithms and Dynamic Programming; Algorithms for NP-Hard Problems) with the redundant bits removed.
Aug 26, 2022 • 4 tweets • 2 min read
Two great lectures by @FBaldimtsi from the @a16z summer research seminar series:

First lecture is about digital signatures --- their uses in web3, the three most popular schemes in web3 (ECDSA, Schnorr, BLS), and their efficiency & security properties.
Aug 11, 2022 • 13 tweets • 2 min read
A true gift from Justin Thaler (prof at Georgetown), making it 100x easier for all of us to understand what SNARKs are, the Pareto frontier of known constructions, and the labyrinthine considerations that govern the key bottleneck (proof generation time): a16zcrypto.com/measuring-snar… Some background and additional context about how SNARKs fit into the current vision for web3 infrastructure 👇
Jun 17, 2022 • 14 tweets • 2 min read
Lecture 8 of the Foundations of Blockchains lecture series (Longest-Chain Consensus) is a bit of a doozy, so I'm releasing it in two parts. Here's part 1:
tl;dr thread (for part 1) below:
1/14 Longest-chain consensus protocols as in Bitcoin and (the original version of) Ethereum are an important category of blockchain protocols (different from BFT-type protocols like Tendermint).
2/14
Apr 21, 2022 • 10 tweets • 3 min read
1/ I'm excited to announce that I've joined @a16z crypto as Head of Research! a16z.com/2022/04/21/ann… 2/ Last year I worked with a16z crypto as an advisor—the team is fantastic, their connections to the best projects and people in the space is unparalleled, and I had a ton of fun.
Apr 9, 2022 • 6 tweets • 1 min read
Blockchains are (virtual) computers, not databases.👇 The raison d'être of a database is to store data and support efficient queries over that data, not to perform general computations.
Feb 4, 2022 • 15 tweets • 2 min read
Lecture 2 of my Foundations of Blockchains lecture series (The Dolev-Strong Protocol) is now available:
tl;dr thread below:
1/15 Our current goal is to identify assumptions under which there are state machine replication (SMR) protocols that satisfy consistency and liveness.
2/15