Skip to content

Instantly share code, notes, and snippets.

View gavinandresen's full-sized avatar

Gavin Andresen gavinandresen

View GitHub Profile

Minimal Viable Privacy Dapp

How much code would I have to write to make MetaMask use Tornado so I can get easy-to-use, private ETH transactions?

  1. command-line tool: connect to MetaMask-in-browser and print account balances, addresses to console
  2. Add --deposit option: figure out how many of what denonimation tornado deposits to make to zero-out account.
  3. ... use account's private key as HD MPK, use paths 86'/0'/... and 86'/1'/... to derive tornado notes (??how to get private key? Ask for 12-word backup??)
  4. ... deposit into those notes (use Thresher for any leftover balance after paying deposit transaction gas)
  5. Add option to display total balance stored in Tornado (via some magic). Q: Privacy problem if contract state queried from a single service/node?
  6. Add --send amount to_address option: derive temporary withdraw keypair
gavinandresen /
Last active February 13, 2020 18:51
Smart contract design for handling "change" privately

Brain dump on "Thresher", inspired by playing with on ethereum (see ). "Thresher" because it accumulates deposits until some minimum threshold is reached, then pays out.

The problem: deposits and withdrawals are fixed-size, with a minimum size (0.1 ETH in the case of ether). Anybody that uses tornado properly will accumulate less-than-minimum amounts of ETH in different addresses and be unable to spend them without compromising privacy.

Note: I'll be talking only about ETH for the rest of this gist, but the idea obviously applies to any of the tokens supported by

gavinandresen /
Last active April 20, 2023 13:38
Updating old paths (witnesses) for a balanced merkle forest accumulator


It would be spiffy to use the balanced merkle forest idea for ethereum tokens or to store unspent transaction outputs.

Tadge Dryja has been working on 'utreexo' (presentation) for storing unspent transaction outputs in log(n) space; this gist is inspired by, and is very similar to, that work.

So my previous gist describes really simple algorithms for adding and removing items from a balanced merkle forest. This gist extends those operations to create

gavinandresen /
Last active February 20, 2021 09:26
Balanced Merkle Forest design

I want a cryptographic accumulator[^accumulator] that has the following properties:

  • It can be build incrementally using a small amount of persistent memory
  • Witness proofs are reasonably small.
  • Witness proofs are computationally easy to verify.
  • Must have at least 100-bit security.

The idea is to minimize on-chain storage; the accumulator will live on-chain, maintained by a smart contract. Transactions submitted to the smart contract can add to the accumulator. And then later transactions can be created that include proofs that a value is part of the accumulator.

gavinandresen /
Last active December 14, 2023 23:28
Storing the UTXO as a bit-vector

Half-baked thoughts exploring a different way of implementing a fully-validating BCH node.

The idea is to shift the storage of full transaction data to wallets, and explore how little data a fully validating node could store. This isn't a problem today (the UTXO set easily fits in the RAM of an inexpensive server-class machine), but might eventually be at very large transaction volumes.

Initial block download is a problem today (it is annoying to have to wait several hours or days to sync up a new node), and this scheme could make it orders of magnitude faster by shifting the time when full transaction data is broadcast from initial block download to new transaction announcement.

gavinandresen /
Last active February 20, 2021 09:28
Backwards Initial Block Download Scheme

This is a scheme for discovering the current "unspent transaction output set"; it could be used to bootstrap a node that stores the UTXO set using a Cuckoo Filter.

It has the following nice properties:

  1. It starts with an empty UTXO set, but quickly discovers a large enough subset to validate a majority of new transactions (TODO: empirically measure how many blocks to be able to validate 50+% of new tx), and incrementally gets better over time.
  2. It uses a simple data structure to keep track of progress (TODO: empirically calculate maximum size of the spent set processing tip to genesis).
  3. It doesn't require any consensus-level change or require miners to maintain any extra data structures or indexes.

However, it does require downloading every single block.

gavinandresen /
Last active June 7, 2021 17:45
Using a cuckoo filter for fast 'unspent?' lookups

A "Cuckoo Filter" is a nifty data structure invented a few years ago; read the paper for details.

Like a Bloom filter, you insert items and then can later ask "does this item exist in the filter?" You'll get either a definite "no" or "yes, probably" with some false-positive error rate. Cuckoo filters have two advantages over Bloom filters:

  1. They are more space efficient at false positive rates less than about 0.03.
  2. You can delete items from them without affecting the false positive rate at all.

It seems to me that an in-memory cuckoo filter could work really well to keep track of Bitcoin's "unspent transaction output set" (UTXO set), to make transaction (or block) validation as fast as possible using minimal memory or disk.

Recall that Bitcoin transactions (other than coinbase transactions that create new coins) have inputs that refer to unspent outputs. An input refers to a previous output by giving the transaction id (a 32-byte hash) co

gavinandresen / ReplayProtection.patch
Created June 15, 2017 15:15
OP_RETURN replay protection patch
diff --git a/src/policy/policy.cpp b/src/policy/policy.cpp
index ec398f662..6724399c0 100644
--- a/src/policy/policy.cpp
+++ b/src/policy/policy.cpp
@@ -117,6 +117,10 @@ bool IsStandardTx(const CTransaction& tx, std::string& reason, const bool witnes
return false;
+ if (tx.ReplayProtected()) {
+ return false;
gavinandresen /
Created April 22, 2017 15:16
Random Sanity for specific languages

The standard library of every programming language has at least one pseudo-random number generator. C has rand(), Javascript has math.Random()... and if you're writing code that needs good randomness you shouldn't use those.

There could be a series of github projects that generate bad random datastreams using those old, deprecated generators and "typical" starting seeds (e.g. 0, current Unix time, small integers that might be process ids) and feeds the results in to the database.

That only does some good if programmers start inserting checks to into their C or Javascript applications... and if they don't know enough to use RAND_bytes() or crypto.RandomBytes()

gavinandresen /
Last active May 10, 2017 12:13
Invalid Block Proofs

For head-first relaying of blocks, I implemented an 'invalidblock' message that, like a 'block' message, broadcasts the full block data when the header of the block was valid but the full block turned out to be invalid.

This should be a very rare occurrence-- miners are incentivized to fix bugs that cause them to produce invalid blocks. So transmitting the full block data once or twice a year shouldn't be an issue... but perhaps it will be an issue if partial validation ever becomes necessary to scale.

First, I assume the 80-byte block header is valid: its hash satisifes proof-of-work.

Proving that the block reward in the coinbase transaction is <= sum(fees)+subsidy requires the full block data (although once segwit is deployed, signatures in the witness data aren't needed).

Proving the block is over size or sigop or sighash limits requires all of the transaction data up to the first transaction that puts the block over the limit (and proof that those transactions are in the block, so a partial merkle tre