Privacy-preserving proof of taproot assets

Proof of being a satoshi millionaire.

This file proves that I, as of block 861756, own 4 taproot utxos (that is, specifically unspent bitcoin) whose total value is between 1,000,000 and 1,262,144 sats. (Weirdly specific numbers? The proving system works for \(k\) to \(k + 2^n\) so I chose \(n=18\)).

At that time, there were 443472 taproot utxos of size more than 100,000 sats; each of the above mentioned 4 is part of that set. We choose a range of possible totals for obvious reasons: if I gave you the exact total value, then with some number crunching you might easily be able to fix exactly which 4 have that total, and I wouldn't have really got any privacy.

Using the software here anyone can verify that this statement is true, in 1/10 of a second, or less, once they have it installed and ready to go (which, OK, may take a bit longer ...). Also the proof is trivially small, at around 13kB.

I emphasize the time taken, because it's definitely possible to use other techniques to achieve this goal, but most of them would have very large proofs and very slow verification, given the limitation that this proof is about bitcoin, and that you don't have a way to get the owners of all the other utxos to cooperate with you to make custom cryptographic keys (if you could cooperate with them, that would open up other, even more efficient techniques!).

Here is a short video showing verification of the proof using a GUI that anyone can download and run:

To verify it independently:

You need to know the "user_string" (this is analogous to the message in a traditional digital signature; without it, the proof of funds is not so useful as anyone can claim it belongs to them!): here it is "waxwing-more-than-900K-sats!".

You need a keyset file (which here is really a commitment file; see PS below), which they can independently create using a Core node; but I provide it here should you want to download it and trust me. It contains only public data; basically, for every taproot utxo that exists.

You need to know the "--audit-range-min" and "--audit-range-exponent" for this proof; here they are 1000000 and 18.

Follow the instructions on verifying from the command line, at the end of the section here.

This is an approach to privacy-preserving proof of assets which I think could be very interesting for some practical applications, especially as the taproot anonymity set grows.

PS: The "commitment" here refers to the idea that we build a CurveTree where the leaves are EC points formed as \((xG + vH)\), where \(v\) is the value of the utxo in sats, and \(x\) is the private key (so \(xG\) is the public key revealed (for taproot) on chain). These commitments, and therefore this "tree", can be built by anyone - the process to do it is described here - and its root is reproducible. The particular one used for this, had a branching factor of 1024 and a depth of 2 (three including the root), so it has a capacity of about a million keys.

If you are interested to learn in detail what this algorithm is, please start here and then read the paper also.