Today I was making a slideshow about coinpools and a thought occurred to me.
I think it’s possible to have four or more people contribute funds to a coinpool and then make withdrawals “from” the coinpool without revealing to one another which user they are. I think this protocol would require interaction from every other participant whenever anyone wants to transact, but in case of a liveness failure, I think each user would be able to withdraw their balance. I am tentatively calling this idea a “zkp coinpool.” I initially also thought the people funding the coinpool could contribute different amounts to it, but I’m less confident of this now – you’ll see why later, but the paragraph after this one starts by assuming they can contribute different amounts.
I think a zkp coinpool is possible because of zero knowledge proofs, in particular, the Zokrates software. This software lets you prove that a number X is (1) positive and greater than a number M but (2) less than a number Y (3) without disclosing the number Y. So let us suppose a bunch of users each supply different amounts to an n-of-n multisig, such that the total balance of the multisig is (for example) 10 million sats. Then, as long as a user says they want to withdraw X, and they supply a proof that X is lower than their current balance Y (without disclosing what their current balance Y actually is), the other users should be perfectly fine with signing a “sighash_all” bitcoin transaction that puts the remainder (10 million - X) back in the multisig and X (minus a mining fee) in whatever address the user wants to withdraw to.
If a user withdraws their full balance, then their balance is zero, so they can no longer say they want to withdraw a number Y and supply a proof that Y is (1) positive and greater than 330 (the taproot dust limit) but (2) less than their current balance – because the proof is invalid unless Y is “greater” than 330, per part 1 of the proof. If their current balance is 0, Y cannot be all at once positive, greater than 330, and less than their current balance of 0, so no such proof can be created.
Once all keyholders in the n-of-n multisig validate the proof, but before they sign the “spend” transaction, they should create a new set of transactions that allows each user to withdraw their leftover balance from the “new” utxo that is about to be go back in the multisig.
Problems and solutions
A possibly-critical problem arises here: if each user deposited a different amount to the coinpool, then the user who withdrew X will now get a withdrawal transaction that lets him withdraw his original amount minus X, and that should be enough for everyone to identify which user he is – he is the one whose balance is no longer what it started out as.
I think I can fix the above problem by making each user contribute an identical amount. I can use use ring signatures to make each user prove they are one of the users without disclosing which one they are, and I can use zokrates to prove that the amount they are withdrawing is less than their balance. Since each user contributed the same amount, no user can tell which user is withdrawing.
But this has limits: if the same user withdraws again before anyone else does, everyone will be able to clearly see which user is withdrawing, because now we are in a new “round,” and in this round, one of the users started out with an amount less (by X) than his compatriots.
I think I can solve this problem by having all of the other users get two withdrawal transactions, one for an amount equal to the amount still owned by whoever withdrew Y, and another for each user’s “change.” The withdrawing user won’t have a “change” output but that’s okay, the users still know very little about who he is – they only know the one without a change address is the one who withdrew, they don’t know which user is the one without a change address, so they don’t know which user withdrew.
Since I don’t know much about zokrates, I posted this in the Zokrates gitter forum:
Hello, I have a problem and I think zokrates can help me solve it.
Suppose Alice, Bob, Carol, and Dave each pick a random number between 1 and 1000:
Alice picks 43
Bob picks 12
Carol picks 906
Dave picks 540
They all tell one other what numbers they picked in plaintext. Now they want to prove statements about their number without revealing which number is theirs, or which person they are.
For example, Alice wants to prove that the number 30 is less than her number, and this is the part where I think zokrates can help. Can Alice use Zokrates to prove that (1) she knows one of the numbers (2) the number 30 is less than her number? Such that no one can tell which person she is? (Except I suppose they all know she definitely isn't Bob.)
And further, given that the difference between Alice's number and 30 is 13, can we ensure that 13 counts as Alice's "new number" -- without disclosing the exact value of the new number to the others -- such that she can continue proving statements about the "new number" without revealing what it is? This should be done in such a way that if she tries to prove a statement about her "old number" (43) the others can detect that she has gone back to her "old number" and is not proving statements about her "new number."
If I learn how to do this in Zokrates then I think I have a really good idea here.
In the next part of this document I will try to limit the need for Zokrates.
I think the Zokrates demos (which I have already played with) make it easy to prove a number X is less than or greater than Y without revealing Y. That is the only thing required for #2 of the proof I need to create. For #1, I don’t think I really need zokrates for that; I can use ring signatures instead. Alice can prove she knows one of the numbers by proving she is one of the four people in the original group; after signing her transaction, a new “group” should be created, with the following “new” people:
Alice_prime_0
Bob_prime_0
Bob_prime_1
Carol_prime_0
Carol_prime_1
Dave_prime_0
Dave_prime_1
It’s perfectly fine for these “prime” people to disclose their new balances, just like they disclosed them when they contributed funds to the coinpool. They won’t have real names, just random pubkeys, and the balances for each random pubkey will be deterministic anyway: each “0” person will have an equal balance (their original balance minus X), and each “1” person will have an equal balance too (precisely X). They will be sorted randomly, too, so there’s no way to tell which person was Alice originally.
Whenever someone wants to spend an amount X and proves they are allowed to, everyone has to (1) create a btc transaction letting the user withdraw that amount and putting the remainder back in the multisig, but don’t sign it yet (2) create a new “list” of keyholders with the new pubkeys (3) sign a transaction distributing the funds to the new pubkeys – note that the only “input” to this transaction should be the multisig itself (1) sign the btc transaction mentioned in #1.
Voila! Alice could withdraw her money without revealing who she is. Anyone in the pool could do this in “round 1” and since round 2 is identical to round 1, except with more pubkeys, anyone can do it in round 2 too.
Wait, what happens if a user in round 2 wants to withdraw an amount greater than any of the individual amounts tied to that user's individual pubkeys? I suppose they will need to prove they own two or more of their money-holding pubkeys and that those pubkeys hold amounts which sum to an amount greater than or equal to the amount they want to withdraw. And I suppose that reduces that user’s anonymity set – if, in round 2, you withdraw using 2 pubkeys, then you are definitely not the person who withdrew in round 1, since he only has 1 pubkey. But I suppose that diminution of privacy isn’t too bad.
Another problem: suppose Alice withdraws all her money in round 1. Can she turn off her computer now and stop interacting? I don’t think that would be very good for the others, because they can only sign new transactions if Alice’s pubkey signs them too. They would all be able to “withdraw” their money but if on those grounds I say it’s “fine” for Alice to turn off her computer, that basically means this protocol only works until someone withdraws all their money. If I modify the protocol to have the money go to a “new” multisig that “excludes” Alice’s key, then doesn’t that reveal that Alice was the one who spent her money in the last round? I’m not sure but I suspect this problem is resolvable like this:
It sounds easy to make a way for Alice to say “I withdrew my full balance” which user she is. If she does that, then have everyone else send a message to everyone where the message contains a new pubkey, and a proof that, after the current round, their new balance is still greater than 0. If Alice withdrew her full balance, she cannot supply this proof, so she cannot contribute a new pubkey to the multisig, which she shouldn’t want to do anyway. Once all the “remaining” users have sent in their new pubkeys, have the “change” output of the “withdrawal” btc transaction put all the money in the new multisig, then sign a tx spending from the new multisig to give everyone except Alice their current balances.
2025-05-20 Update
After some experimentation, I think it is reasonable for every user to contribute a different amount, if they are all multiples of some number, e.g. multiples of 10000 sats. The initial withdrawal tx, or txs, should send the money out of the multisig and into a bunch of 10k satoshi outputs.
So suppose there are 4 users, Alice, Bob, Carol and Dave, and these are their contributions:
Alice: 40,000 sats
Bob: 60,000 sats
Carol: 100,000 sats
Dave: 200,000 sats
The total is 400,000 sats, so the initial withdrawal transaction ought to create 40 outputs of 10,000 sats apiece.
Now let us suppose one of the users spends 4,256 sats plus a 200 sat fee. A transaction should be created and signed that uses the 400,000 sats in the multisig as an input, and as an output, it should put 400,000 - 4,456 = 395,544 sats back in the multisig, 4,256 sats in whatever address the user is sending money to, and a new transaction should be created and signed that spends from the 395,544 sat multisig and splits up the money into 39 outputs of 10,000 sats apiece and 1 output worth 5,544 sats.
The last output belongs to the spender, but no one knows who that is, and even if our spender wants to spend his money in the future, he can even include a proof that his balance includes that amount, because it will not reveal that that output belongs to him.
Another consideration: after experimenting, I don't think ring signatures help me with this project. I thought I could use those to prove that a user knows one of the numbers without disclosing which one he knows, and I can, but when proving that his balance is greater than or equal to the amount he wants to spend, the proof generation function actually has to know which balance is his, and ring signatures don't seem to help point that out. Note that the proof won't say which balance is the spender's, but the function he uses to generate that proof has to take some sort of identifier as input, but keep that identifier a secret.
To solve that problem, what I'm thinking of doing is tying each balance to a hash in a kind of array: [hash1, balance1], [hash2, balance2]. Then the function by which the spender generates the proof must take multiple parameters, including the preimages associated with the balances that he claims are his. The function will validate that he knows those preimages, and thus that those balances are his, and sum them so that he can prove the amount he wants to spend is less than or equal to the sum of his balances. But the proof itself won't disclose which preimages belong to the spender. So when the spender supplies the other coinpool members with the proof, they can validate that he is allowed to spend the amount he wants to spend without learning how much money he has.
Update 2025-05-21
I think I suddenly lost a lot of enthusiasm for this project today. I was experimenting with zokrates and discovered a problem when I compiled the proving function separately in the proof generator and the proof verifier, which seems important to do since the prover in my system is one of the coinpool users and all of the other users are supposed to act as verifiers. The prover and the verifier are always different people in my model, so it is important that they be able to generate the proving function independently and still run it and get the same results. But I found that the prover has to give the verifier a key called a "verifiation key," and this verification key has to be generated in a "trusted setup," which produces "toxic waste" which must be destroyed, otherwise fake proofs can be generated. So I think I need to figure out a way to have every member of the coinpool cooperate in the trusted setup every time a new coinpool is created or someone spends something, and I'm not sure that's feasible.