Smart contract design for handling "change" privately

Thresher.md

Brain dump on "Thresher", inspired by playing with tornado.cash on ethereum (see http://gavinandresen.ninja/a-more-private-eth-wallet ). "Thresher" because it accumulates deposits until some minimum threshold is reached, then pays out.

The problem: tornado.cash 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 tornado.cash.

Solution: a smart contract that accepts deposits that are less than 0.1 ETH with a tornado.cash 'note'. Once the contract has accumulated 0.1 ETH or more, it redeposits 0.1 ETH into tornado.cash with one of the deposit's notes, picked fairly at random (e.g. if you deposit 0.09 ETH your note has a 90% chance of being picked).

I'm going to make some people cringe and propose using a "good enough" way to pick the winners:

Winners are picked as a side effect of processing a new deposit at some current block height N.

The hash of block N-1 is used as the random seed to pick a winner. However, to make cheating by miners even more costly (they must pay transaction fees to another miner to get their entries on the list), only deposits received before block N-1 can win.

See "On Bitcoin as a public randomess source" by Bonneau, Clark, and Goldfeder for an analysis of miners trying to cheat by throwing away winning block hashes: https://pdfs.semanticscholar.org/ebae/9c7d91ea8b6a987642040a2142cc5ea67f7d.pdf Cheating only pays if miners can win more than twice what they earn mining a block; the reward is currently 2 ETH (plus fees), so we're OK using the block hash as our randomness source as long a cheating miner can't win more than 4 ETH.

Can depositors cheat? They cannot make it more likely that their entry is picked, because they cannot know what the block hash will be.

Gas costs

Tornado deposits are somewhat expensive-- on the order of a million gas. Each deposit to Thresher should include enough gas to cover a deposit, because each deposit could pick a winner and call tornado.deposit(). The contract could be written to pick multiple winners and make multiple tornado deposits at once (for once call to deposit()) if it accumulated 0.2 or more ether, but that would be bad because it would make the amount of gas required very unpredictable.

A Thresher user could try to cheat on gas costs by looking at the current state of the contract and seeing if their new deposit is likely to trigger a 'win' and a tornado deposit (e.g. most simply if their deposit will cause the Thresher balance to be >= 0.1 ETH). If it will (costing ~1million gas) they could wait and send their transaction later, after some other deposit has drained the contract.

Maybe the best design is to simply have deposits older than 256 blocks always lose. Leave it up to users of the contract to call processOldest() before 256 blocks have passed to make sure they don’t lose when they should have won. I think I’d still run a process to call processOldest every 200 blocks (if necessary); doing that would not be expensive, and writing that code is a lot easier than wrestling with lists of old block headers, I think.

That sounds good to me.

Looking at line 159. Am I right that it is possible to always win by adding a deposit and wait for over 256 blocks. Because winningThreshold is set to 0.

It also seems to be possible to get stuck behind a too big winning transaction in the same block. let's say there where 2 deposits in the same block, both of them should win. But the first winAmount is larger than the current balance, than the second transaction doesn't have a change to get their money. Maybe you want to check if the winAmount is smaller than the contracts balance at the time of the deposit (before or after the previous deposit is handled within that same transaction).

Line 159 sets threshold to bitwise-not-0, which is the maximum value for uint256. Easy to miss the ~ at the front, I’ll add a comment. As for getting stuck because the contract balance is low: that could also happen if random chance chooses lots of winners. If the contract starts with 9ETH, then eleven people contribute-0.1-to-win-1, there is a one-in-10^10 chance (hundred billion) the contract will be empty for the eleventh person. I was planning on donating 5 to 10ETH to the initial contract balance when it is deployed to main net, but I’ve been working on the ‘make sure processAll is called before 256 blocks go by’ code: https://github.com/gavinandresen/thresher/blob/master/triggerProcessing.js I could potentially save myself a little ether if that code automatically ‘tops up’ the contract if the contract balance goes low... Anyway, rejecting entries if the contract balance is less than the win amount is a good failsafe that is easy to code; I’ll do that. To be utterly safe would involve a loop through pending entries and adding up what they could potentially win (or keeping track of that in contract state to save gas). But doing that would open up a denial-of-service attack; I could send contribute-1-wei-to-win-1-ETH entries until the code decided there was a chance it wouldn’t be able to pay out.

Nice Gavin, I get it now.

I would be okay with having a small chance of not winning because the contract balance gets too low, but it would be nice to minimize this chance when there is like 1 other entry in the queue.

I imagine this to have some web interface in the future, where every deposit is represented like a raffle ticket with all information on it, turning red or green based on if they win or lose. Maybe I have some time in the future to play around with this.