Oddbean new post about login | logout I've been thinking this through and I've encountered two closely related problems. My outline of the naive approach is: see the "Vcash" section of the Curve Trees paper. The "pour" algorithm already does most of what you want. You build a tree of utxo pubkeys, more exactly tags of the form G__nll =hash(pubkey)G_t to use the notation of the paper. Then for each of yours, you build the commitment as C_i = v_iG_v + G_nll_i + r_i H where v is the value of the coin and r_i is a random chosen by the prover to blind the commitment. So far so normal. Then you use CurveTrees' "Selectandrerandomise" algo to get C_rr,i (rr means 're-randomized' commitment) along with a proof of its validity (i.e. a proof that it's in the tree. After doing this for every one of your utxos, you then need to attach a second zero knowledge proof, a minor adaptation of "pour" in Fig 6 of the paper: instead of proving zero balance from summing ins and outs in a transaction, you prove "commitment to my claimed balance minus the sum of commitments to the list I've given has value 0". You also need to attach a range proof for each one of the outputs, but this is also handled by spend/pour in the paper. But in that lies the problem: if I claim an exact amount, say 100 BTC, and I have to provide a list of N utxos, I've provided already too much information, in the general case: with a very specific amount and a number it's almost trivial (usually) to crunch the public utxo set and figure out the subset that gives the exactly correct total sum. I only see two directions to correct this problem. Use a proof of range instead of exact balance (prove x > y instead of x == y), but this can be surprisingly much more difficult than proving exact values in zero knowledge. Or, some form of aggregation to avoid leaking the number of items (so instead of one c_rr per one of your keys, somehow aggregating the selectandrerandomize? not sure if that actually even makes sense ...). nostr:nevent1qqs90g0yjyl3a4k28tqed65fpuynn06gu6566n2x4ndftwz33ft7w4cpz4mhxue69uhhyetvv9ujuerpd46hxtnfduhsygr8twz0ua0zz64eglr58rh9r898wafhdh0stkklhf3830gp9cwh9qpsgqqqqqqsrz0tl7
After several weeks of work, I think I have a working implementation (very basic so far, and lots of caveats..) of something that solves this problem. To recap: you want to prove that you own a total of T BTC, but privately. But revealing exact amount may make it too easy to deanon. So I have a proof of this statement: "I own N utxos, whose total value is between k and k + 2^n, for some k and n that I announce, but I am not revealing which N utxos they are, or what their individual values is, out of a given list of 300k utxos". The code at https://github.com/AdamISZ/aut-ct/tree/auditing now does this. See the latest commit note. In brief you need 3 or 4 components to the proof: 1/ a proof that each blinded commitment is part of that 300k set, 2/a proof that each committed value, when summed together, lies in the given range (using bulletproofs), and 3/ key images per utxo to ensure you dont' cheat by just claiming the same utxo multiple times. nostr:nevent1qqsqc8wgf8w74sh2sjfpjgw4lpp7sp08vfvgpc7dvljewn3cq4grscgpz4mhxue69uhhyetvv9ujuerpd46hxtnfduhsygr8twz0ua0zz64eglr58rh9r898wafhdh0stkklhf3830gp9cwh9qpsgqqqqqqsxpc8jd
Practical considerations: 1/ only taproot utxos 2/ address reuse is not supported (though it could be with a trivial algo change 3/ notice the anon set is not "all utxos in the keyset provided" (say it was "all taproot utxos above 0.1 btc" for example). if you specify 5 utxos and you prove "total is between 10 and 12 btc", then obviously not all combinations of 4 utxos add up to something in that range. So if you started with e.g. 300k, your actual anon set might be more like 5000 (guess!). (but even more confusing - 5k utxos might be *part* of a set of 4 that adds up to that range, but the number of actual combinations of 4 could be astronomically larger). Due to nonlinear distribution of utxos, it will therefore be better, if you have a large treasury, to split your coins into a lot more small values, and then build proofs of sums with larger utxo numbers. 4/ proofs in the current code are not aggregated, which makes proving for say 50 utxos, not 4, impractically slow. But this is an implementation detail: aggregation of these bulletproofs is a well established algorithm, and removes this problem. The verification here is very fast, as with aut-ct. By the way if you're wondering where any documentation of this algorithm is, yet, don't, I haven't written it yet, it's on the way.
This is beautiful Adam, thanks!
Here's the paper: https://github.com/AdamISZ/aut-ct/blob/auditing/auditor-docs/privacy-preserving-proof-of-assets.pdf First half is quite discursive with no mathematics ... it's important to give the context of why (at least according to me) this is an interesting alternative way to do proof of assets compared to other approaches. Feel free to share anywhere you think people might be interested. I will add a bit more to the doc later, but the actual algo is there. nostr:nevent1qqsx2rz74lcr2hklujx85ntu0a0gmuzx5r7nw6v84s5892rkktln7wcpr4mhxue69uhkummnw3ezucnfw33k76twv4ezuum0vd5kzmp0qgsxwkuyle67y94tj378gw8w2xw2wa6nwmwlqhddlwnz0z7sztsaw2qrqsqqqqqpv55779