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.
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?
Check.
Could you please explain to me how an input can sign a "provably valid" block chain transaction without knowing the outputs?
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.
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?).
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.
So how isn't that a DOS vulnerability? I repeat this question below.
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
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.
Yes but if I understand correctly, the DOS attack can occur while the blind signatures of outputs are being made as I explained above.
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.In this case could anyone work out that it was me that put in the outputs that made the transaction not balance?
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.
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.As far as I can see, you can't.
Could you please explain to me how an input can sign a "provably valid" block chain transaction without knowing the outputs?
Quote
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.
...by the fact that they fail to sign. My point is you can't, at least not without breaking anonymity, and anonymity was the entire point of mixing.Quote
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.
Quote
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.
Quote
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?).
Quote
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.
Quote
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.
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
Quote
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, thenbecause 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.