CoinJoin: Bitcoin privacy for the real world

[Crowex]

For my own part, I would question that there is a non-ephemeral identification of participants, namely by requiring the inputs first. The inputs would serve as an identification and if any problems were subsequently to arise, they could be blacklisted.

But if the inputs are really not connectable to the outputs could I jam the transaction by using outputs that add up to greater than my inputs?
In this case could anyone work out that it was me that put in the outputs that made the transaction not balance?

[1714093899]

1714093899

[gmaxwell]

But if the inputs are really not connectable to the outputs could I jam the transaction by using outputs that add up to greater than my inputs?
In this case could anyone work out that it was me that put in the outputs that made the transaction not balance?

No, instead they prevent you from doing that in the first place.

E.g. in the blinded example: When you provide your inputs everyone sees your values, and you specify "this is a blinded X btc output" and they all sign that output with a key which corresponds to X btc, and obviously refuse to do so if your input isn't at least X.  Later you reveal your output, and they know its value by which keys signed it.

This isn't to say that implementing any of this is interesting. The state machine to achieve success in all cases ends up very complicated. (This is also why I think that blinded but quasi-centeralized e.g. where a semi trusted party coordinates are probably more interesting for initial deployment).

[itsunderstood]

Anonymint is one of these who thinks bitcoin is broken and will pursue that to the end.  He is interesting to talk to, but still ignored by the world.  If bitcoin is broken, then go away, thanks.

Now whats all this about bitcoin using the Naval asset called "Tor"?  Seems legit.

[AnonyMint]

And my post to which you are replying is in fact explaining the DOS (denial-of-service) is insoluble if you can't identify the participants in order to rate-limit them.

And again in that post you admit there is a DOS problem. You didn't solve it. And you can't solve it in a decentralized setting unless you have non-ephemeral identification of the participants. Which is precisely the point of my prior post to which you are replying

You are asserting it, (over and over again) but it doesn't make it true. It was explained in adequate detail previously enough for other people to understand it and implement tools that address it.

Incorrect. What I wrote is functionally equivalent to what you described. The point is the transaction can be jammed in the final round.

It's actually not, since it's not actually possible in the Bitcoin protocol to do what (it sounds like) you're describing, but more importantly performing the operation in that order defeats the anti-dos. If you lead with the inputs they provide a trivial anti-dos mechanism.

And precisely how do you identify which input is the adversary when the correlation of the inputs and the outputs is necessarily cryptographically blinded?

As far as I can see, you can't.

I am confident that now you see the functionally w.r.t. to anti-DOS of what I described and what you described are equivalent, i.e. any one who is the least bit mathematical can see that the salient mathematical foundation of CoinJoin is that the correlation between the inputs and outputs must be cryptographically blinded, thus it makes no difference mathematically for anti-DOS whether the inputs or outputs are specified in the first round of the protocol.

As for whether my proposed protocol of putting the outputs in the first round is implementable on the Bitcoin blockchain, it is irrelevant since we are talking about a general protocol here and an altcoin could be designed to allow a transaction where outputs and inputs can be signed to point to the transaction nonce (a hash of any number) plus the addresses of the inputs OR outputs. I didn't bother to check how Bitcoin signs the transactions, because it is conceptually irrelevant to our discussion. Perhaps in Bitcoin the signature of the transaction must include all the inputs AND outputs. The reason I presented my formulation (in fact I mentioned the ring signatures idea from Adam Back in the Zerocoin thread months ago in this thread) is because it is more powerful conceptually than one gmaxell described. I thought gmaxell would appreciate that since I think he is a math guy.

And exactly how do you propose to identify that adversary in a decentralized setting?   My point is you can't, at least not without breaking anonymity, and anonymity was the entire point of mixing.

Because they fail to sign. There is no need to identify them beyond identifying their input coins to achieve rate limiting, and no need to identify the input/output correspondence.

I'll repeat it, since maybe other people are having problems following the link:

I will quote from your more detailed description upthread.

This is an extremely interesting idea.  Could you elaborate on how the Zerocoin transaction stages map to the stages of CoinJoin transaction creation?

For non-decenteralized coincoin, you simply pass around a transaction and sign it. It's a single sequence and an atomic transaction, you'd make two loops through the users, one to discover the inputs and outputs, and another to sign them. There really aren't stages to it.

Making a decenteralized CoinJoin secure, private, and resistant to DOS attack (people refusing to sign in order to make it fail) is trickier... for the privacy and dos attack resistance you can use ZC:

Presume the participants for a transaction are sharing some multicast medium and can all communicate.  They need to accomplish the task of offering up inputs (txid:vout) for inclusion in the transaction and then, in an unlinkable way, providing outputs to receive their coins.

Each participant connects and names bitcoin input(s), an address for change (if needed), and the result of performing a ZC mint transaction to add to the ZC accumulator. They sign all this with the keys for the corresponding inputs proving its theirs to spend.

Then all the parties connect again anonymously and provide ZC redeem transactions which specify where the resulting bitcoins should go.

Zerocoin (ZC) requires a trusted party to generate the parameters, thus it is the antithesis of decentralized, so you have a logical error above.

https://github.com/Zerocoin/libzerocoin/wiki/Generating-Zerocoin-parameters

This isn't the only way to do this in a decentralized manner, the way to do it with blind signatures is fairly similar:

Each participant connects, names Bitcoin input(s), an address for change (if needed), a key for blind signing, and a blinded hash of the address they want paid. They sign all this with the keys for the corresponding inputs proving its theirs to spend.

Each participant then blind signs the blinded hashes of all participants (including themselves).

And so how can you correlate which input is the one who didn't blind sign all?

As far as I can see, you can't.

I've dug very deep (into cryptography research papers) lately into trying to find a way to delink inputs from outputs without a trusted party, and I have realized that mathematically it can't be done. It is a fundamental conceptualization.

The only way to delink without anti-DOS is to use an accumulator commitment scheme with common NP-hard parameters that can be presented in an NIZKP (non-interactive zero knowledge proof) which will always require a trusted party to generate the common parameters for the trapdoor math.

This is just one example of a way to address this. There are several other ones possible— and discussed early on in this thread.  Other ones include publishing commitments and then if the process fails having everyone reveal their intended outputs (which they then discard and never use) in order to avoid being banned, or using an anonymous accumulator instead of blind signing to control access.

That isn't anti-DOS.

Each spender commits a hash of his intended output. Then everyone does the blinded protocol. If the blinded protocol fails, everyone including the adversary reveals the link between inputs and outputs, because by definition the output key must be an abundant resource so that it is not costly to reveal it and generate a new one to try again.

, or using an anonymous accumulator instead of blind signing to control access.

A ZKP + accumulator isn't decentralized as I explained above.

[gmaxwell]

And precisely how do you identify which input is the adversary when the correlation of the inputs and the outputs is necessarily cryptographically blinded?
As far as I can see, you can't.

The input is identified by the fact that it fails to sign a provably valid transaction.

And exactly how do you propose to identify that adversary in a decentralized setting?   My point is you can't, at least not without breaking anonymity, and anonymity was the entire point of mixing.

Because they fail to sign. There is no need to identify them beyond identifying their input coins to achieve rate limiting, and no need to identify the input/output correspondence.

...by the fact that they fail to sign.

I will quote from your more detailed description upthread.

You're now quoting from a different approach. I listed several. The one which I specifically identified in our discussion here used plain chaum blinded signature. (The others should work fine too— but if you mix things up its hard to have a coherent discussion)

Zerocoin (ZC) requires a trusted party to generate the parameters, thus it is the antithesis of decentralized, so you have a logical error above.

ZC initialized with an RSA UFO has no trusted initialization, in fact— they make the updates much larger but thats harmless for data not going in the blockchain. Additionally if you do use the efficient trusted initialization the ZC accumulator approach still has perfect zero knoweldge. Compromise of the state allows someone to make false proofs (dos attacks in this context).   Though these points are not terribly relevant because I wasn't talking about the ZC approach.

And so how can you correlate which input is the one who didn't blind sign all?

Because they refuse to sign the transaction. Everyone knows that all the outputs provided in the transaction were the unique outputs provided by the inputting parties (because they have been signed by all participants). So they all know the transaction is valid.

(of course, if it fails before you finish the unblinding, — you explain below how thats handled)

I've dug very deep (into cryptography research papers) lately into trying to find a way to delink inputs from outputs without a trusted party, and I have realized that mathematically it can't be done. It is a fundamental conceptualization.
The only way to delink without anti-DOS is to use an accumulator commitment scheme with common NP-hard parameters that can be presented in an NIZKP (non-interactive zero knowledge proof) which will always require a trusted party to generate the common parameters for the trapdoor math.

You've apparently not done much research at all, as you are not aware of RSA UFOs (which are described in some of the very first papers about those sorts of accumulators), you are not aware of non-trapdoor NIZK (e.g. fiat-shamir/random oracle only), and ... apparently you're not aware of anything as simple as a blind signature.

Each spender commits a hash of his intended output. Then everyone does the blinded protocol. If the blinded protocol fails, everyone including the adversary reveals the link between inputs and outputs, because by definition the output key must be an abundant resource so that it is not costly to reveal it and generate a new one to try again.

I'm glad you agree that the case where the protocol fails before all the blind signatures are collected is easily resolved. If it fails after transaction signing has begun, then—because the blind signatures assure everyone that the transaction was correct— you know the non-signer is the adversary.

[AnonyMint]

Something doesn't add up...

First I want to make sure that gmaxell's protocol is first we sign inputs, then we blind sign outputs, then we unblind.

But if the inputs are really not connectable to the outputs could I jam the transaction by using outputs that add up to greater than my inputs?
In this case could anyone work out that it was me that put in the outputs that made the transaction not balance?

No, instead they prevent you from doing that in the first place.

E.g. in the blinded example: When you provide your inputs everyone sees your values, and you specify "this is a blinded X btc output" and they all sign that output with a key which corresponds to X btc, and obviously refuse to do so if your input isn't at least X.  Later you reveal your output, and they know its value by which keys signed it.

Don't the inputs need to be signed to a specific block chain transaction?

Each participant connects, names Bitcoin input(s), an address for change (if needed), a key for blind signing, and a blinded hash of the address they want paid. They sign all this with the keys for the corresponding inputs proving its theirs to spend.

Each participant then blind signs the blinded hashes of all participants (including themselves).

Each participant then reconnects anonymously and discloses their unblinded values and all the signatures. Because all the participants can see all the signatures, they know all are authentic. They sign, and if they refuse to sign everyone is convinced that the refusing signer is attempting to jam and bans them.

Check.

And precisely how do you identify which input is the adversary when the correlation of the inputs and the outputs is necessarily cryptographically blinded?
As far as I can see, you can't.

The input is identified by the fact that it fails to sign a provably valid transaction.

Could you please explain to me how an input can sign a "provably valid" block chain transaction without knowing the outputs?

And exactly how do you propose to identify that adversary in a decentralized setting?   My point is you can't, at least not without breaking anonymity, and anonymity was the entire point of mixing.

Because they fail to sign. There is no need to identify them beyond identifying their input coins to achieve rate limiting, and no need to identify the input/output correspondence.

...by the fact that they fail to sign.

I will quote from your more detailed description upthread.

You're now quoting from a different approach. I listed several. The one which I specifically identified in our discussion here used plain chaum blinded signature. (The others should work fine too— but if you mix things up its hard to have a coherent discussion)

I will not respond to this part of your reply at this time, so as to not further confuse the line of discussion above and below.

Zerocoin (ZC) requires a trusted party to generate the parameters, thus it is the antithesis of decentralized, so you have a logical error above.

ZC initialized with an RSA UFO has no trusted initialization, in fact— they make the updates much larger but thats harmless for data not going in the blockchain. Additionally if you do use the efficient trusted initialization the ZC accumulator approach still has perfect zero knoweldge. Compromise of the state allows someone to make false proofs (dos attacks in this context).   Though these points are not terribly relevant because I wasn't talking about the ZC approach.

I was aware of the RSA UFO claim from the ZC research paper, but Adam Back's comments seem to imply (?) it isn't a realistic option (so to save time I trusted what I interpreted to be his expert opinion). I just now skimmed this research paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.4015&rep=rep1&type=pdf

Efficient Accumulators Without Trapdoor Extended Abstract
Tomas Sander

There are some assumptions made when I would need to think more deeply about.

Apparently there is some reason ZC did not adopt the UFO approach by default. I suppose those assumptions have not be been sufficiently attacked by cryptanalysis yet.

Compromise of the trusted PQ in ZC allows the trusted party to double-spend coins. Thus I assume for the CoinJoin case, it would cause the number of outputs to not match inputs, so thus a form of DOS.

I'm glad you've admitted that your proposal for CoinJoin employing ZC doesn't work decentralized, unless UFOs are a valid solution (are they and why?).

And so how can you correlate which input is the one who didn't blind sign all?

Because they refuse to sign the transaction. Everyone knows that all the outputs provided in the transaction were the unique outputs provided by the inputting parties (because they have been signed by all participants). So they all know the transaction is valid.

But the DOS can occur during the blinding signing of the outputs.

(of course, if it fails before you finish the unblinding, — you explain below how thats handled)

So how isn't that a DOS vulnerability? I repeat this question below.

I've dug very deep (into cryptography research papers) lately into trying to find a way to delink inputs from outputs without a trusted party, and I have realized that mathematically it can't be done. It is a fundamental conceptualization.
The only way to delink without anti-DOS is to use an accumulator commitment scheme with common NP-hard parameters that can be presented in an NIZKP (non-interactive zero knowledge proof) which will always require a trusted party to generate the common parameters for the trapdoor math.

You've apparently not done much research at all, as you are not aware of RSA UFOs (which are described in some of the very first papers about those sorts of accumulators), you are not aware of non-trapdoor NIZK (e.g. fiat-shamir/random oracle only), and ... apparently you're not aware of anything as simple as a blind signature.

I was aware of RSA UFOs as stated above. I was also aware of the Fiat-Shamir research paper below where the square roots (on mod n curve) stored on a smart card can't be factored (mod n) by the verifier (in polynomial time) and thus these roots are hidden by multiple interactive challenge rounds that employ a mathematical product that hides the actual values but requires the sum to be equal, and this can be converted to non-interactive (NI) via the Fiat-Shamir transformation by employing a one-way cryptographic hash function to issue the random challenges.

http://www.cs.rit.edu/~jjk8346/FiatShamir.pdf

Each spender commits a hash of his intended output. Then everyone does the blinded protocol. If the blinded protocol fails, everyone including the adversary reveals the link between inputs and outputs, because by definition the output key must be an abundant resource so that it is not costly to reveal it and generate a new one to try again.

I'm glad you agree that the case where the protocol fails before all the blind signatures are collected is easily resolved.

How is that not a DOS attack on the input signatures that were already made?

Everyone must start again, and the adversary is not identified.

If it fails after transaction signing has begun, then—because the blind signatures assure everyone that the transaction was correct— you know the non-signer is the adversary.

Yes but if I understand correctly, the DOS attack can occur while the blind signatures of outputs are being made as I explained above.

[AnonyMint]

Zerocoin (ZC) requires a trusted party to generate the parameters, thus it is the antithesis of decentralized, so you have a logical error above.

ZC initialized with an RSA UFO has no trusted initialization, in fact— they make the updates much larger but thats harmless for data not going in the blockchain. Additionally if you do use the efficient trusted initialization the ZC accumulator approach still has perfect zero knoweldge. Compromise of the state allows someone to make false proofs (dos attacks in this context).   Though these points are not terribly relevant because I wasn't talking about the ZC approach.

I was aware of the RFC UFO claim from the ZC research paper, but Adam Back's comments seem to imply (?) it isn't a realistic option (so to save time I trusted what I interpreted to be his expert opinion). I just now skimmed this research paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.4015&rep=rep1&type=pdf

Efficient Accumulators Without Trapdoor Extended Abstract
Tomas Sander

There are some assumptions made when I would need to think more deeply about.

Apparently there is some reason ZC did not adopt the UFO approach by default. I suppose those assumptions have not be been sufficiently attacked by cryptanalysis yet.

Compromise of the trusted PQ in ZC allows the trusted party to double-spend coins. Thus I assume for the CoinJoin case, it would cause the number of outputs to not match inputs, so thus a form of DOS.

I'm glad you've admitted that your proposal for CoinJoin employing ZC doesn't work decentralized, unless UFOs are a valid solution (are they and why?).

On further reading, apparently UFOs are impractical because there isn't an entropy source that can be trusted to be random over such large domains. Please feel free to correct me if I am mistaken about the requirement.

We shift our unreliability of trust from unknowing if someone intercepted the computation of N = PQ to the unreliability of unknowing whether our input entropy could be attacked at any time in the future.

The research paper suggests in "2.1 On the generation of public random strings" to use stock market data, but there is hidden periodicity in the stock market data:

http://armstrongeconomics.com/2014/03/09/research-shocking-there-is-order-in-the-chaos/

Just in case you believe that guy's model is nonsense, then you can try to explain how his cyclic model has predicted (in advance, this isn't just model that fits what happened) everything accurately:

https://bitcointalk.org/index.php?topic=495527.msg5464897#msg5464897

https://bitcointalk.org/index.php?topic=365141.msg5642957#msg5642957

[gmaxwell]

E.g. in the blinded example: When you provide your inputs everyone sees your values, and you specify "this is a blinded X btc output" and they all sign that output with a key which corresponds to X btc, and obviously refuse to do so if your input isn't at least X.  Later you reveal your output, and they know its value by which keys signed it.

Don't the inputs need to be signed to a specific block chain transaction?

Eventually, after the transaction is formed according to the blind signatures.

Could you please explain to me how an input can sign a "provably valid" block chain transaction without knowing the outputs?

At the point they sign the transaction they know the outputs (or else the transaction wouldn't yet exist).

I was aware of the RSA UFO claim from the ZC research paper, but Adam Back's comments seem to imply (?) it isn't a realistic option (so to save time I trusted what I interpreted to be his expert opinion). I just now skimmed this research paper

Zerocoin itself was already not realistic inside Bitcoin due (among other reasons) to the large transaction that you have to put into the blockchain. UFOs make them larger by a small multiple. Sending a few extra tens of KB outside of Bitcoin probably isn't an issue.

On further reading, apparently UFOs are impractical because there isn't an entropy source that can be trusted to be random over such large domains. Please feel free to correct me if I am mistaken about the requirement.

WTF?! Like in everything else you use a cryptographically strong PRNG which holds as long as some underlying hash function holds, and if the hash function is distinguishable with unknown inputs from a random oracle you're already hosed in every other protocol (including your DSA signatures).

Compromise of the trusted PQ in ZC allows the trusted party to double-spend coins. Thus I assume for the CoinJoin case, it would cause the number of outputs to not match inputs, so thus a form of DOS.

Yes? and so what? First— I note that you're continuing to waste time discussing the more complicated ZC thing when that wasn't what I was speaking about and do not recommend people implement (I noted it as a possibility for those were excited about ZC to find a potential application for the technology). Secondly— who cares if maybe someone kept a trapdoor and could just DOS attack? If you were really worried about that case you can just keep around a couple parameter sets, track how often you fail in each case and prefer ones where you've never been dos attacked (with the users taking a majority decision or something like that).

I'm glad you've admitted that your proposal for CoinJoin employing ZC doesn't work decentralized

I did no such thing. Your frequent misrepresentation in discussion makes it very difficult to justify continuing to respond to you.

And so how can you correlate which input is the one who didn't blind sign all?

Because they refuse to sign the transaction. Everyone knows that all the outputs provided in the transaction were the unique outputs provided by the inputting parties (because they have been signed by all participants). So they all know the transaction is valid.

But the DOS can occur during the blinding signing of the outputs.

Great. If the DOS attack occurs during the blind signing of the output tokens then everything is totally trivial then. Since every inputting user is required to blind sign everyone else output token, if they don't— you know who's jamming the process and you ban them.

Here is an overview of all the places a user could refuse to participate further:

(0) If a user refuses to sign an initial introduction message that specifies their input and their blinded output (and other parameters like blind signing keys to be used), then they're just not participating as producing that message is how they join in.

(1) If a user refuses to sign the blinded outputs of all the other users their inputs are blacklisted as the blind signing of everyone's output tokens is not anonymous (relative to inputs).

(2) If a user (now reconnected anonymously relative to inputs) refuses to reveal their unblinded outputs, this attempt is aborted, all honest users reveal their blinding factors and withholder is deanonymized and their inputs banned.

If we've made it this far we have a set of outputs which were provably created by the people who created the inputs, though we don't know the correspondence. We can form a transaction and know that the transaction matches their wishes. So we do.

(3) If any input does not sign for the resulting transaction we blacklist them because we know the transaction is accurate at this point.

I really cannot understand why you find this difficult to understand.

[AnonyMint]

I'm glad you've admitted that your proposal for CoinJoin employing ZC doesn't work decentralized

I did no such thing. Your frequent misrepresentation in discussion makes it very difficult to justify continuing to respond to you.

You removed part of the logic of the sentence. Here is what I wrote:

I'm glad you've admitted that your proposal for CoinJoin employing ZC doesn't work decentralized, unless UFOs are a valid solution (are they and why?).

Surely you understand that the word "unless" means that if UFOs are not a solution, then I'm asserting you've admitted and if UFOs are a solution then I'm not asserting you have admitted.

So I did not (intentionally) misrepresent your stance. You are still claiming that UFOs are a solution, thus you haven't admitted and I have never claimed you have.

Note the logic of "unless" also (unintentionally) meant that you admitted couldn't think of a way to use a trusted PQ instead of a UFO. But you have apparently presented a workable idea below. Kudos!

I was aware of the RSA UFO claim from the ZC research paper, but Adam Back's comments seem to imply (?) it isn't a realistic option (so to save time I trusted what I interpreted to be his expert opinion). I just now skimmed this research paper

Zerocoin itself was already not realistic inside Bitcoin due (among other reasons) to the large transaction that you have to put into the blockchain. UFOs make them larger by a small multiple. Sending a few extra tens of KB outside of Bitcoin probably isn't an issue.

I agree the extra size is not likely a factor for use offchain such as a decentralized CoinJoin.

Zerocoin is also not realistic inside Bitcoin because if a trusted party could create unlimited Bitcoins, that would violate basic principle of Bitcoin. That same trust issue may or may not apply if used in CoinJoin.

I elaborate below why am not convinced UFOs would solve that trust issue if used in Bitcoin.

On further reading, apparently UFOs are impractical because there isn't an entropy source that can be trusted to be random over such large domains. Please feel free to correct me if I am mistaken about the requirement.

WTF?! Like in everything else you use a cryptographically strong PRNG which holds as long as some underlying hash function holds, and if the hash function is distinguishable with unknown inputs from a random oracle you're already hosed in every other protocol (including your DSA signatures).

I would need to look and think more deeply about the math he showed there, but seemed like he was saying that we can predict the occurrence of primes in a product probabilistically thus I am having the conjectured thought (to explore more when I have more time) that the requirements on the period (in the applicable domain space) over which the assumption that the (approximation to the) Random Oracle model must hold true may be implicitly much more vast than when we apply hash functions in Z. I am curious to think more about what he actually proved and didn't prove.

I think there is much more depth to this than we can go into now. And I haven't had the time yet to wrap my mind completely around the math in that paper on UFOs.

Why don't we ask Adam Back? He is a neutral party and I think he may know more about the deeper implications of the mathematical assumptions in that RSA-UFO paper.

Or we can simply agree to stop discussing about Zerocoin or RSA-UFOs, which would be fine by me.

Compromise of the trusted PQ in ZC allows the trusted party to double-spend coins. Thus I assume for the CoinJoin case, it would cause the number of outputs to not match inputs, so thus a form of DOS.

Yes? and so what? First— I note that you're continuing to waste time discussing the more complicated ZC thing when that wasn't what I was speaking about and do not recommend people implement (I noted it as a possibility for those were excited about ZC to find a potential application for the technology).

I am replying to your comments. If you stop talking about Zerocoin, then I can stop responding about Zerocoin.

I am curious about Zerocoin as a solution for CoinJoin since I am fairly certain that your proposed protocol for CoinJoin can be DOS-attacked (see my reason below).

Secondly— who cares if maybe someone kept a trapdoor and could just DOS attack? If you were really worried about that case you can just keep around a couple parameter sets, track how often you fail in each case and prefer ones where you've never been dos attacked (with the users taking a majority decision or something like that).

That is a very interesting idea! Since knowing PQ doesn't allow you to snoop on the other participants' anonymity, that might be workable.

And then we don't need RSA-UFOs.

I don't see why you need to track how often there is failure. You simply discard a PQ where there was a DOS attack, because that is 100% evidence that PQ is compromised.

E.g. in the blinded example: When you provide your inputs everyone sees your values, and you specify "this is a blinded X btc output" and they all sign that output with a key which corresponds to X btc, and obviously refuse to do so if your input isn't at least X.  Later you reveal your output, and they know its value by which keys signed it.

Don't the inputs need to be signed to a specific block chain transaction?

Eventually, after the transaction is formed according to the blind signatures.

Could you please explain to me how an input can sign a "provably valid" block chain transaction without knowing the outputs?

At the point they sign the transaction they know the outputs (or else the transaction wouldn't yet exist).

And so how can you correlate which input is the one who didn't blind sign all?

Because they refuse to sign the transaction. Everyone knows that all the outputs provided in the transaction were the unique outputs provided by the inputting parties (because they have been signed by all participants). So they all know the transaction is valid.

But the DOS can occur during the blinding signing of the outputs.

Great. If the DOS attack occurs during the blind signing of the output tokens then everything is totally trivial then. Since every inputting user is required to blind sign everyone else output token, if they don't— you know who's jamming the process and you ban them.

Here is an overview of all the places a user could refuse to participate further:

(0) If a user refuses to sign an initial introduction message that specifies their input and their blinded output (and other parameters like blind signing keys to be used), then they're just not participating as producing that message is how they join in.

(1) If a user refuses to sign the blinded outputs of all the other users their inputs are blacklisted as the blind signing of everyone's output tokens is not anonymous (relative to inputs).

(2) If a user (now reconnected anonymously relative to inputs) refuses to reveal their unblinded outputs, this attempt is aborted, all honest users reveal their blinding factors and withholder is deanonymized and their inputs banned.

If we've made it this far we have a set of outputs which were provably created by the people who created the inputs, though we don't know the correspondence. We can form a transaction and know that the transaction matches their wishes. So we do.

(3) If any input does not sign for the resulting transaction we blacklist them because we know the transaction is accurate at this point.

I really cannot understand why you find this difficult to understand.

Two orthogonal issues.

First, an adversary could make a 1 Satoshi input and DOS on the (3) step. You ban that address but adversary has billions more at neglible cost.

I suppose you could set a minimum input amount to avoid this. But still no problem for the adversary, he passes his BTC through a mixer can comes to hit you again and again.

I am sorry to bring you bad news Gregory but with a non-atomic operation in the decentralized case you can always be DOS-attacked.  Zerocoin may be the solution?


Second and orthogonal to my point above, I don't understand this:

But if the inputs are really not connectable to the outputs could I jam the transaction by using outputs that add up to greater than my inputs?
In this case could anyone work out that it was me that put in the outputs that made the transaction not balance?

No, instead they prevent you from doing that in the first place.

E.g. in the blinded example: When you provide your inputs everyone sees your values, and you specify "this is a blinded X btc output" and they all sign that output with a key which corresponds to X btc, and obviously refuse to do so if your input isn't at least X.  Later you reveal your output, and they know its value by which keys signed it.

Appears you are saying that as a participant when I provide my input, I also specify the amount of my output?

So how is there unlinking of output amounts from input amounts?

[malevolent]

Two orthogonal issues.
First, an adversary could make a 1 Satoshi input and DOS on the (3) step. You ban that address but adversary has billions more at neglible cost.
I suppose you could set a minimum input amount to avoid this. But still no problem for the adversary, he passes his BTC through a mixer can comes to hit you again and again.
I am sorry to bring you bad news Gregory but with a non-atomic operation you can always be DOS-attacked.  Zerocoin may be the solution?

Transaction fees and confirmation times should slow down the attacker.

[AnonyMint]

Two orthogonal issues.
First, an adversary could make a 1 Satoshi input and DOS on the (3) step. You ban that address but adversary has billions more at neglible cost.
I suppose you could set a minimum input amount to avoid this. But still no problem for the adversary, he passes his BTC through a mixer can comes to hit you again and again.
I am sorry to bring you bad news Gregory but with a non-atomic operation you can always be DOS-attacked.  Zerocoin may be the solution?

Transaction fees and confirmation times should slow down the attacker.

As for slowing down, the adversary can have many parallel addresses in play so I don't think so.

Transaction fees might work if they are significant enough. I haven't studied how much the tx fees are in Bitcoin much. I think I read that certain txs can be 0 for some cases?

If the adversary is mixing through CoinJoin transactions (hehe, uses what he also DOS-attacks against itself), then the blockchain tx fee is going to be shared between all parties of the CoinJoin transaction, so could it be insignificant?

Edit: I've just realized the adversary can eliminate the transaction fees too, by spending those banned amounts as he normally would (e.g. day trading), thus he doesn't incur any extra cost.

Edit#2: unless all decentralized CoinJoins share their ban lists (which is quite impractical to achieve as it is the antithesis of decentralization), adversary can just round-robin through them.

So I've won the argument. Checkmate.

[gmaxwell]

Surely you understand that the word "unless" means that if UFOs are not a solution,

Actually I think they're fine for this without the UFOs, I only brought them up because you were insisting things that were add odds with their e
Appears you are saying that as a participant when I provide my input, I also specify the amount of my output?

So how is there unlinking of output amounts from input amounts?

Derp. Your output is equal to your input. Privacy comes from equalizing amounts.

[AnonyMint]

Derp.

You just can't resist the ad hominem even after I've shown you were wrong all along about DOS attacks on your protocol.

Sigh.

[piotr_n]

I'm sometimes reading this topic, occasionally, and it seems always the same. Actually, its getting worse.
Like with almost everything: plenty of ideas, but no solution whatsoever.

As for this specific topic, it basically seems like the level of the misery is just increasing.
My advise: talk less, do more - it will solve all your problems, I promise!

Why do people even care to waste their time on pointless discussions?
I could have saved so much of my own time, if I had only known an answer to such a stupid question
I guess it must be some kind of entertainment, like watching TV, because I cannot believe someone would be wasting his time on this kind of pointless forum arguments, though still thinking that he actually somehow helps the mankind.
We are talking about tens of pages of a "technical" topic (and not only this one!), lasting for years, with practically no actual applications - it must be just an entertainment, what else?
Unless it's a new kind of science: a theoretical engineering... Though I would still rather count it as a stupid kind of philosophy 

[AnonyMint]

So how is there unlinking of output amounts from input amounts?

Derp. Your output is equal to your input. Privacy comes from equalizing amounts.

And thus my original statement was correct:

Comments please on my technical statement herein?

A decentralized CoinJoin will have difficulty forming transactions ... that look like this if anyone can join:

https://blockchain.info/tx/e4abb15310348edc606e597effc81697bfce4b6de7598347f17c2befd4febf3b?show_adv=true

Also my statement that the CoinJoin protocol can be DOS-attacked was correct.

It was a bit difficult to explain these facts w.r.t. to gmaxell's semi-coherent, incomplete explanations of his protocol. But I think I was able to help him to specify the essential requirements of his protocol.

As for this specific topic, it basically seems like the level of the misery is just increasing.
My advise: talk less, do more - it will solve all your problems, I promise!

The solution was provided by gmaxell. Use Zerocoin which is an atomic operation from inputs -> available outputs. But it won't work for Bitcoin's current block chain design, because even if we could (which we currently can't) we don't want to put the Zerocoin accumulator on the block chain because we don't want to trust the PQ thus we want to the accumulator to have a preset short-term lifespan and all inputs and outputs must specify themselves with that time limit. However this can't work in Bitcoin because inputs have to sign the output addresses. Thus in Bitcoin the specification of the output addresses would make it a non-atomic operation thus it can be DOS-attacked.

The solution for an altcoin (or Bitcoin if we can make such a radical change) is to make the transaction id a nonce and have the inputs and outputs sign that nonce. If the outputs are greater than inputs, then the transaction is invalid. In the rare event the outputs are greater than inputs, then we know to throw away and don't reuse the Zerocoin accumulator's PQ (because its trust is compromised) and try again.

[nanobit]

Could someone kindly give a status update on when will we have a real-world, usable CoinJoin (besides the implementation on Blockchain.info)? This thread is huge, and I'm sure many casual readers would like to see a tl;dr to learn will this result in a usable client soon, or what's the plan?

I found the thread when reading this article from 7 months ago. What has happened since?
http://bitcoinmagazine.com/6630/trustless-bitcoin-anonymity-here-at-last/

[Suzuki]

I find it a good idea to create a site where you enter a P2SH address, it gives back a traditional address, and when it receives money at the traditional address, it immediately forwards the unconfirmed BTC to the P2SH address. Hope someone will manage it!

[maaku]

Could someone kindly give a status update on when will we have a real-world, usable CoinJoin (besides the implementation on Blockchain.info)? This thread is huge, and I'm sure many casual readers would like to see a tl;dr to learn will this result in a usable client soon, or what's the plan?

I found the thread when reading this article from 7 months ago. What has happened since?
http://bitcoinmagazine.com/6630/trustless-bitcoin-anonymity-here-at-last/

can someone kindly give a status update when we will havemoney distributed to developers to work on a free and fair and decentralized coin join?

[themgp]

Could someone kindly give a status update on when will we have a real-world, usable CoinJoin (besides the implementation on Blockchain.info)? This thread is huge, and I'm sure many casual readers would like to see a tl;dr to learn will this result in a usable client soon, or what's the plan?

I found the thread when reading this article from 7 months ago. What has happened since?
http://bitcoinmagazine.com/6630/trustless-bitcoin-anonymity-here-at-last/

I'm still actively working on the implementation I have started Coinmux.  I have taken a break for the last month after spending 3+ months working on it nights and weekends. Hopefully there is a Bitcoin God that wants to offer me a job to work on it full time.

[solex]

There is now 42 BTC donated: https://blockchain.info/address/3M8XGFBKwkf7miBzpkU3x2DoWwAVrD1mhk

Was the plan to pay 100% to the author of the first complete implementation, or for piece-work in progress?