How would you prove that you own >= X BTC without disclosing addresses ? (ZKP)

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: gmaxwell on August 15, 2015, 06:06:13 AM

Using an AOS ring signature only works when you know the pubkeys, which you don't for most coins in the Bitcoin UTXO set.

In any case, the ring signature used to construct the CT range proof is just the AOS scheme when not used with any AND, so thats implement in secp256k1-zkp.

To avoid the proof size-- you're off in snark land-- e.g. the statement you prove "I know a private key for an adequate coin belonging to a utxo set with this hashroot". I previously suggested a scheme that lets you avoid doing 99% of the EC math inside a snark, so this could get a small under 400 byte proof and be implementable. I think it was in a forum post... I'll have to look. But the basic process have the snark instead prove "Pubkey P is a blinding of a pubkey that is member of this tree", and then you also prove you know P's discrete log externally to the snark. The verification of the blinding can be done with a single point addition in the prover.

A CDS ring signature works just as well, but obviously it would only be functional for currencies like Monero where the pubkeys are published instead of the pubkey hashes.

hexafraction

sr. member

Activity: 392

Merit: 268

Tips welcomed: 1CF4GhXX1RhCaGzWztgE1YZZUcSpoqTbsJ

Quote from: Dabs on August 15, 2015, 11:15:05 AM

Quote from: gmaxwell on August 15, 2015, 06:06:13 AM

Using an AOS ring signature only works when you know the pubkeys, which you don't for most coins in the Bitcoin UTXO set.

In any case, the ring signature used to construct the CT range proof is just the AOS scheme when not used with any AND, so thats implement in secp256k1-zkp.

To avoid the proof size-- you're off in snark land-- e.g. the statement you prove "I know a private key for an adequate coin belonging to a utxo set with this hashroot". I previously suggested a scheme that lets you avoid doing 99% of the EC math inside a snark, so this could get a small under 400 byte proof and be implementable. I think it was in a forum post... I'll have to look. But the basic process have the snark instead prove "Pubkey P is a blinding of a pubkey that is member of this tree", and then you also prove you know P's discrete log externally to the snark. The verification of the blinding can be done with a single point addition in the prover.

Uh... Mr gmaxwell, could you say that again in "plain language" ? I mean, in "normal English" ? I'm seriously trying to understand what you're trying to say.

The way I said it, although a solution, is centralized. This can probably even be implemented by a large block explorer or block chain site, automatically. But I know everyone is looking for a better way, or something that can be done in the bitcoin core client.

Some alt-coins have this thing called Proof of Stake, I'm wondering if that's an angle bitcoin can use (for proving the original question of the OP, not for mining.)

Proof of stake isn't anonymous as ZKP proofs are. The AOS signature lets you mathematically prove a statement "I have access to a private key for at least one of the addresses in this set" without revealing which. If you're trying to prove you own 1 BTC you'd sign it so that set would be a set of a bunch of keys that all contain 1 BTC.

I'm not sure about the 'snark' concept. It would be nice if someone could provide an explanation or a link to one.

Dabs

legendary

Activity: 3416

Merit: 1912

The Concierge of Crypto

Quote from: gmaxwell on August 15, 2015, 06:06:13 AM

Using an AOS ring signature only works when you know the pubkeys, which you don't for most coins in the Bitcoin UTXO set.

In any case, the ring signature used to construct the CT range proof is just the AOS scheme when not used with any AND, so thats implement in secp256k1-zkp.

To avoid the proof size-- you're off in snark land-- e.g. the statement you prove "I know a private key for an adequate coin belonging to a utxo set with this hashroot". I previously suggested a scheme that lets you avoid doing 99% of the EC math inside a snark, so this could get a small under 400 byte proof and be implementable. I think it was in a forum post... I'll have to look. But the basic process have the snark instead prove "Pubkey P is a blinding of a pubkey that is member of this tree", and then you also prove you know P's discrete log externally to the snark. The verification of the blinding can be done with a single point addition in the prover.

Uh... Mr gmaxwell, could you say that again in "plain language" ? I mean, in "normal English" ? I'm seriously trying to understand what you're trying to say.

The way I said it, although a solution, is centralized. This can probably even be implemented by a large block explorer or block chain site, automatically. But I know everyone is looking for a better way, or something that can be done in the bitcoin core client.

Some alt-coins have this thing called Proof of Stake, I'm wondering if that's an angle bitcoin can use (for proving the original question of the OP, not for mining.)

gmaxwell

staff

Activity: 4284

Merit: 8808

Using an AOS ring signature only works when you know the pubkeys, which you don't for most coins in the Bitcoin UTXO set.

In any case, the ring signature used to construct the CT range proof is just the AOS scheme when not used with any AND, so thats implement in secp256k1-zkp.

To avoid the proof size-- you're off in snark land-- e.g. the statement you prove "I know a private key for an adequate coin belonging to a utxo set with this hashroot". I previously suggested a scheme that lets you avoid doing 99% of the EC math inside a snark, so this could get a small under 400 byte proof and be implementable. I think it was in a forum post... I'll have to look. But the basic process have the snark instead prove "Pubkey P is a blinding of a pubkey that is member of this tree", and then you also prove you know P's discrete log externally to the snark. The verification of the blinding can be done with a single point addition in the prover.

Dabs

legendary

Activity: 3416

Merit: 1912

The Concierge of Crypto

There is a semi-centralized way. You show this proof to a third party who vouches for what you said. This third party will simply confirm that you control a certain amount of coins at a certain point in time (or until present) without revealing the address to the other person.

This will essentially be a service provided by that third party.

Disclaimer: I do escrows, and they can do this without the owner handing over control of the bitcoins. That boils down to whether the other person can trust the escrow service or not.

What I've been asked to do before was to actually hold the coins, tell the other guy that I hold the coins, then return the coins back to the owner minus my fee. If it were for some loan or exchange to an alt or as collateral, then I hold the coins for the duration of the contract.

johoe

full member

Activity: 217

Merit: 259

Quote from: znort987 on August 14, 2015, 10:33:00 AM

Currently, you can prove ownership of coins by signing with
the private key of an address where coins are stored.

Is there a ZKP (Zero Knowledge Proof) way of demonstrating
that you own at least X BTC ?

Here is a simple idea that is not completely ZK: find a bunch of coins that contain roughly the same amount as the coin you want to prove ownership of. Then use an Abe-Ohkubo-Suzuki ring signature[1] to prove that you own one of the private keys. The more coins you pick the less information you leak but the larger your signature get.

I guess that there is a ZKP, but checking it requires to process the full UTXO set and probably the size of the signature would be similar in size as the UTXO set.

[1] Masayuki Abe, Miyako Ohkubo, and Koutarou Suzuki, 1-out-of-n signatures from a variety of keys, In Advances in Cryptology - ASIACRYPT 2002, LNCS, Springer-Verlag, 2002, pp. 415–432.

RustyNomad

sr. member

Activity: 336

Merit: 251

Thought about this a bit last night and it seems like there is no real way but to move all the funds, or the quantity required, to a single address and to sign a message with the address. On most block explorers one will also be able to look up the address and see whether the funds has been spent or not. A good way to maybe do this would be to create a paper wallet to which you can move the funds. If privacy is an issue you can use a mixer and move the funds from your wallet to the mixer and on to your paper wallet.

Once you have provided the proof you can just sweep that paper wallet back into your standard wallet. Far easier than having to create a new HD wallet etc..

You can also share the xpub key of the wallet/account if you do not wish to move all the funds to a single address. But doing this will mean that you give up any privacy you had as the other party will be able to view all transactions for every single address in that wallet/account.

If I however required somebody to provide proof like this for a transaction I would prefer that the person move the funds into escrow with somebody. Just proving that they have the funds on an addresses is no guarantee that it will actually be transferred to you once the transaction has been done.

tspacepilot

legendary

Activity: 1456

Merit: 1081

I may write code in exchange for bitcoins.

Quote from: Kazimir on August 14, 2015, 04:00:46 PM

Quote from: achow101 on August 14, 2015, 02:38:34 PM

That would only price that you had x btc at one point in time. It didn't guarantee that the bottom sent to other addresses are still in your possession.

You can wait and move the coins after you've proven you own them.

But that doesn't really address OPs question, because in principle, if he wants to prove he owns and address, he can just do that with a signed message and then move the coins to new addresses. The question was if it's possible to prove you own BTC without showing the addresses. I'd also like to know if it's possible.

The closest thing I could come up with would be that there might be some way to prove that you own at least one of a set of addresses, all of which have the required amount funded. I don't know if that's possible either, but if so it might be pretty close to what the OP wants.

I'm here to learn!

Kazimir

legendary

Activity: 1176

Merit: 1011

Quote from: achow101 on August 14, 2015, 02:38:34 PM

That would only price that you had x btc at one point in time. It didn't guarantee that the bottom sent to other addresses are still in your possession.

You can wait and move the coins after you've proven you own them.

achow101

staff

Activity: 3458

Merit: 6793

Just writing some code

I don't think that our is possible without telling people what addresses are yours.

Quote from: Kazimir on August 14, 2015, 11:59:35 AM

You could sign a message with the private key of an address that holds ≥ x BTC, and then distribute the bitcoins over a tree of other addresses or mix them.

That would only price that you had x btc at one point in time. It didn't guarantee that the bottom sent to other addresses are still in your possession.

RustyNomad

sr. member

Activity: 336

Merit: 251

I agree with the OP that this would be a great feature to have in a wallet.

Just don't know how one will be able to it though. Only way in which it can be done at this stage is to move everything to a single address and to sign a message with that address.

Would be nice if one could sort of sign a whole wallet but guess that would have to involve the xpub key of that wallet in some way or another and that would expose all your transactions for the world to see or to whom ever have the xpub key, that is unless the wallet can just produce a signature similar to what you currently get when signing with a single address.

Kazimir

legendary

Activity: 1176

Merit: 1011

You could sign a message with the private key of an address that holds ≥ x BTC, and then distribute the bitcoins over a tree of other addresses or mix them.

thejaytiesto

legendary

Activity: 1358

Merit: 1014

Quote from: znort987 on August 14, 2015, 10:33:00 AM

Currently, you can prove ownership of coins by signing with
the private key of an address where coins are stored.

Is there a ZKP (Zero Knowledge Proof) way of demonstrating
that you own at least X BTC ?

That'd be a killer feature for credit-worthiness type applications
of bitcoin.

I don't think this is possible at all. To prove it you would always need to show something that ultimately links whatever that is to you address. And if you present something that cannot be linked to the address it's pointless. I don't know, I think it doesn't make much sense.

hexafraction

sr. member

Activity: 392

Merit: 268

Tips welcomed: 1CF4GhXX1RhCaGzWztgE1YZZUcSpoqTbsJ

It would require a rework of the way outputs are stored and represented in Bitcoin. The unspent outputs themselves aren't represented in a way that a zero-knowledge proof can be constructed for one or a set of them, if I'm not mistaken. However, I'm not even close to certain. If this were possible in a way that I didn't imagine, I'd be quite interested to hear of it.

znort987

vip

Activity: 72

Merit: 12

Currently, you can prove ownership of coins by signing with
the private key of an address where coins are stored.

Is there a ZKP (Zero Knowledge Proof) way of demonstrating
that you own at least X BTC ?

That'd be a killer feature for credit-worthiness type applications
of bitcoin.

Topic: How would you prove that you own >= X BTC without disclosing addresses ? (ZKP) (Read 1745 times)