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.
quotingI'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.
nevent1q…c8jd
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 ...).
nevent1q…0tl7