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.

Dear Gavin,

Interesting read! I wrote a simple ‘solidity’ pseudo contract that would allow depositors to ‘randomly’ win a tornado cash tokens out of a small eth pool managed by the contract. The functionality is a little simpler than you describe, and does not allow for 2 transactions in neighboring blocks. But it gives the user more certainty about the chance of winning the token, especially when the balance of the contract is sufficient (over 1 eth).

Contract SimpleThresher
  bytes lastCommitment = 0x0;
  uint lastAmount = 0;
  uint lastBlockNumber = 0;

  function deposit(bytes commitment) payable public
    roll()
    lastCommitment = commitment;
    lastAmount = value;
    lastBlockNumber = block.number + 1;
  

  function roll() public
    if (lastAmount > 0)
      // Check if last commitment won a tornado token. Based on N + 1 blockhash and commitment. Also gives some less good odds for a pool size lower than 1
      If (lastBlockNumber > block.number - 1)
        throw
      if (self.balance < 1 eth)
         lastAmount = lastAmount * self.balance / 1 eth;
      if ((blockhash(lastBlockNumber) ^ lastCommitment) % 0.1 eth < lastAmount)
        Tornado.deposit(lastCommitment, 0.1 eth);
      lastAmount = 0;
  

The blockhash function in solidity only outputs the has of the last 256 blocks. Which is about an hours worth of blocks. So there needs to be a second way of validating a roll where the contract would receive and validate the content of a full block header.

I got itchy and have a working version:
https://github.com/gavinandresen/thresher
... but I think I'm going to rewrite it. Instead of:
Account with less than 0.1 ETH --> Thresher --maybe--> 0.1 Tornado deposit

I think it might be better to do:
Account with less than 0.1 ETH --> Thresher --maybe--> 0.1+ into Account --> Tornado deposit
... where Thresher awards 0.1 ETH plus enough extra ETH to cover gas costs for a tornado deposit.

Using Thresher is then just a regular "send all ETH from a dust account to the Thresher address".
If you're lucky, a few blocks later the account then has enough ETH for a Tornado deposit.

I just checked your repo, Really like the continues processing of transactions.

I also like your idea to send the 0.1+ eth to the account, the UX would be sleek! It should create less dust. Maybe an option to specify the expected profit amount?

Just saw your update. Sweet.

I would suggest to calculate the withdraw amount at the moment of deposit. Instead when you win or loose. This would result in a lower storage footprint. And would give the depositor full control over their gas cost. lastly your data structure would be ready to take on bigger fish than tornado alone.

You also need to fix line 157 that uses the currentBlock-1 which varies a lot over time especially as long as the contract is not used every other block. It should be blockNumber + 1 i think.

Note that the blockhash only gives access to the last 256 blocks. After this period the blockhash will return 0. Which gives the depositor another chance to win.

I would suggest to calculate the withdraw amount at the moment of deposit. Instead when you win or loose. This would result in a lower storage footprint.

I don't think I can save any storage. I need to store four pieces of information for every entry: current block height when the entry was received, address to receive winnings, how many ETH they contributed, and how much to pay out if they win. Currently 'how much to pay out' is their gasPrice*million+entryvalue, but I think it would be clearer to store it as how much to pay out. That won't save any storage, though.

I have to store both how much they contributed and how much to pay out to make the random draw fair.

And would give the depositor full control over their gas cost. lastly your data structure would be ready to take on bigger fish than tornado alone.

Do you mean letting the depositor specify how much they'd like to get paid if they win? That's an interesting idea, I might do that. As long as it is less than 4 ETH it should work, and it would make it much more general.

You also need to fix line 157 that uses the currentBlock-1 which varies a lot over time especially as long as the contract is not used every other block. It should be blockNumber + 1 i think.

currentBlock-1 is what I intended. If the contract is unused for several (or even thousands of) blocks then entries are kind of like schrodinger's cat-- they have neither won nor lost. Somebody with a pending entry could try to watch block hashes and submit another entry to trigger a "win" payout; but if more than one person tries to do that, the results will be random and fair over the long run.

Note that the blockhash only gives access to the last 256 blocks. After this period the blockhash will return 0. Which gives the depositor another chance to win.

That's why I don't want to use entry.blocknumber+1.

hi

Do you mean letting the depositor specify how much they'd like to get paid if they win? => Yes, maybe you can add an extra function that accepts a winningAmount under 4 eth.

I am starting to better understand how it functions, but when creating a deposit. It looks like i can can always calculate what the randomhash will be at the time of withdraw. The randomHash is calculated based on the previous blockhash (at time of deposit) and my used gasprice. Now an attacker can adjust its gasprice or wait for the right blockhash, to generate a randomHash that let’s him win when no other depositor uses the contract.

Maybe i still do not understand the concept completely. Keep up the good work ;)

@kaibakker : thanks for the great comments, I think you're right-- it would be better to use entry.blocknumber+1 (or currentBlock-255 if the contract is unused or underfunded for 255 blocks) for the randomness.

And I could do two things to make sure the contract never hits the "unused/unfunded for 255 blocks" case:

1. Prefund the contract with an ETH or two, so every new entry can be paid out right away (after just two blocks, assuming a new entry comes in) if it wins.
2. Set up a process that watches the contract and sends an 'always wins' entry (e.g. sends 0.1 ETH to win 0.1 ETH deposit) if there have been no other deposits in 100 blocks. That will cost about a penny in transaction fees at current gas prices, or worst-case 62 cents per day.

I really like the progress on the contract.

The downside of your approach is that you always need to watch the contract or otherwise it will be drained, because you will give people 2 chances of winning (before and after 256 blocks).

An alternative method of handeling this problem would be to skip deposits older than 256 blocks. You could create a second function that accepts a full blockheader and the index of a winning deposit. I think you could accept any blockheader with atleast 50% of the current difficulty and the correct blocknumber. Now anyone can claim an old winning deposit, and you don't have to watch/protect the contract holdings.

https://github.com/amiller/ethereum-blockhashes/blob/master/README.md here is an old repo that calculates blockhashes of old blocks, their gas calculations will be out dated.

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.