This is a very interesting topic. If a solution was found, a much better, easier, more convenient implementation of Bitcoin would be possible.
Originally, a coin can be just a chain of signatures. With a timestamp service, the old ones could be dropped eventually before there's too much backtrace fan-out, or coins could be kept individually or in denominations. It's the need to check for the absence of double-spends that requires global knowledge of all transactions.
The challenge is, how do you prove that no other spends exist? It seems a node must know about all transactions to be able to verify that. If it only knows the hash of the in/outpoints, it can't check the signatures to see if an outpoint has been spent before. Do you have any ideas on this?
It's hard to think of how to apply zero-knowledge-proofs in this case.
We're trying to prove the absence of something, which seems to require knowing about all and checking that the something isn't included.
Re: Not a suggestion
Still thinking this idea through...
The only job the network needs to do is to tell whether a spend of an outpoint is the first or not.
If we're willing to have clients keep the history for their own money, then some of the information may not need to be stored by the network, such as:
- the value
- the association of inpoints and outpoints in one transaction
The network would track a bunch of independent outpoints. It doesn't know what transactions or amounts they belong to. A client can find out if an outpoint has been spent, and it can submit a satisfying inpoint to mark it spent. The network keeps the outpoint and the first valid inpoint that proves it spent. The inpoint signs a hash of its associated next outpoint and a salt, so it can privately be shown that the signature signs a particular next outpoint if you know the salt, but publicly the network doesn't know what the next outpoint is.
I believe the clients would have to keep the entire history back to the original generated coins. Someone sending a payment would have to send data to the recipient, as well as still communicating with the network to mark outpoints spent and check that the spend is the first spend. Maybe the data transfer could be done as an e-mail attachment.
The fact that clients have to keep the entire history reduces the privacy benefit. Someone handling a lot of money still gets to see a lot of transaction history. The way it retrospectively fans out, they might end up seeing a majority of the history. Denominations could be made granular to limit fan-out, but a business handling a lot of money might still end up seeing a lot of the history.
The only job the network needs to do is to tell whether a spend of an outpoint is the first or not.
If we're willing to have clients keep the history for their own money, then some of the information may not need to be stored by the network, such as:
- the value
- the association of inpoints and outpoints in one transaction
The network would track a bunch of independent outpoints. It doesn't know what transactions or amounts they belong to. A client can find out if an outpoint has been spent, and it can submit a satisfying inpoint to mark it spent. The network keeps the outpoint and the first valid inpoint that proves it spent. The inpoint signs a hash of its associated next outpoint and a salt, so it can privately be shown that the signature signs a particular next outpoint if you know the salt, but publicly the network doesn't know what the next outpoint is.
I believe the clients would have to keep the entire history back to the original generated coins. Someone sending a payment would have to send data to the recipient, as well as still communicating with the network to mark outpoints spent and check that the spend is the first spend. Maybe the data transfer could be done as an e-mail attachment.
The fact that clients have to keep the entire history reduces the privacy benefit. Someone handling a lot of money still gets to see a lot of transaction history. The way it retrospectively fans out, they might end up seeing a majority of the history. Denominations could be made granular to limit fan-out, but a business handling a lot of money might still end up seeing a lot of the history.
Re: Not a suggestion
I believe the clients would have to keep the entire history back to the original generated coins. The fact that clients have to keep the entire history reduces the privacy benefit.
I thought this too at first. But then I convinced myself otherwise.
I was talking about in the hypothetical system I was describing, if the network doesn't know the values and lineage of the transactions, then it can't verify them and vouch for them, so the clients would have to keep the history all the way back.
If a client wasn't present until recently, the two ways to convince it that a transaction has a valid past is:
1) Show it the entire history back to the original generated coin.
2) Show it a history back to a thoroughly deep block, then trust that if so many nodes all said the history up to then was correct then it must be true.
But if the network didn't know all the values and lineage of the transactions, it couldn't do 2), I don't think.
Re: Not a suggestion
I'm not grasping your idea yet. Does it hide any information from the public network? What is the advantage?
If at least 50% of nodes validated transactions enough that old transactions can be discarded, then everyone saw everything and could keep a record of it.
Can public nodes see the values of transactions? Can they see which previous transaction the value came from? If they can, then they know everything. If they can't, then they couldn't verify that the value came from a valid source, so you couldn't take their generated chain as verification of it.
Does it hide the bitcoin addresses? Is that it? OK, maybe now I see, if that's it.
Crypto may offer a way to do "key blinding". I did some research and it was obscure, but there may be something there. "group signatures" may be related.
There's something here in the general area:
http://www.users.zetnet.co.uk/hopwood/crypto/rh/
What we need is a way to generate additional blinded variations of a public key. The blinded variations would have the same properties as the root public key, such that the private key could generate a signature for any one of them. Others could not tell if a blinded key is related to the root key, or other blinded keys from the same root key. These are the properties of blinding. Blinding, in a nutshell, is x = (x * large_random_int) mod m.
When paying to a bitcoin address, you would generate a new blinded key for each use.
Then you need to be able to sign a signature such that you can't tell that two signatures came from the same private key. I'm not sure if always signing a different blinded public key would already give you this property. If not, I think that's where group signatures comes in. With group signatures, it is possible for something to be signed but not know who signed it.
As an example, say some unpopular military attack has to be ordered, but nobody wants to go down in history as the one who ordered it. If 10 leaders have private keys, one of them could sign the order and you wouldn't know who did it.
If at least 50% of nodes validated transactions enough that old transactions can be discarded, then everyone saw everything and could keep a record of it.
Can public nodes see the values of transactions? Can they see which previous transaction the value came from? If they can, then they know everything. If they can't, then they couldn't verify that the value came from a valid source, so you couldn't take their generated chain as verification of it.
Does it hide the bitcoin addresses? Is that it? OK, maybe now I see, if that's it.
Crypto may offer a way to do "key blinding". I did some research and it was obscure, but there may be something there. "group signatures" may be related.
There's something here in the general area:
http://www.users.zetnet.co.uk/hopwood/crypto/rh/
What we need is a way to generate additional blinded variations of a public key. The blinded variations would have the same properties as the root public key, such that the private key could generate a signature for any one of them. Others could not tell if a blinded key is related to the root key, or other blinded keys from the same root key. These are the properties of blinding. Blinding, in a nutshell, is x = (x * large_random_int) mod m.
When paying to a bitcoin address, you would generate a new blinded key for each use.
Then you need to be able to sign a signature such that you can't tell that two signatures came from the same private key. I'm not sure if always signing a different blinded public key would already give you this property. If not, I think that's where group signatures comes in. With group signatures, it is possible for something to be signed but not know who signed it.
As an example, say some unpopular military attack has to be ordered, but nobody wants to go down in history as the one who ordered it. If 10 leaders have private keys, one of them could sign the order and you wouldn't know who did it.