Quote from: gmaxwell on March 12, 2014, 03:38:01 PM

Quote from: AnonyMint on March 12, 2014, 08:40:14 AM

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:

Quote from: AnonyMint on March 12, 2014, 08:40:14 AM

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!

Quote from: gmaxwell on March 12, 2014, 03:38:01 PM

Quote from: AnonyMint on March 12, 2014, 08:40:14 AM

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.

Quote from: gmaxwell on March 12, 2014, 03:38:01 PM

Quote from: AnonyMint on March 12, 2014, 08:40:14 AM

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.

Quote from: gmaxwell on March 12, 2014, 03:38:01 PM

Quote from: AnonyMint on March 12, 2014, 08:40:14 AM

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

Quote from: gmaxwell on March 12, 2014, 03:38:01 PM

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.

Quote from: gmaxwell on March 12, 2014, 03:38:01 PM

Quote from: AnonyMint on March 12, 2014, 08:40:14 AM

Quote

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.

Quote

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

Quote

Quote from: gmaxwell on March 12, 2014, 06:57:34 AM

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.

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:

Quote from: gmaxwell on March 11, 2014, 09:33:59 PM

Quote from: Crowex on March 11, 2014, 08:24:02 PM

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?