waxwing on Nostr: I've been thinking this through and I've encountered two closely related problems. My ...

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 ...).

quoting
nevent1q…0tl7

I believe we currently have the technology to make compact proofs of ownership of a certain amount of btc without revealing which utxos we own. Computationally intensive, sure, but compact and quick to verify, even though thwre are 160M+ utxos.

There's a bit of engineering work, but with this, we could embarrass Coinbase Custody into proving they actually hold the coin they claim to.

nevent1q…2rpk