Bitcoin Forum
October 22, 2017, 12:30:20 PM *
News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [23] 24 25 26 27 28 29 30 31 32 33 34 35 »
  Print  
Author Topic: CoinJoin: Bitcoin privacy for the real world  (Read 262866 times)
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 03, 2014, 02:16:13 AM
 #441

The dc-net solution requires you to trust only that there exists at least one other node (ANY participating node) that is not compromised; that's a strictly stronger guarantee than Tor

My understanding of dc-nets is it is impractical to stop denial-of-service. Generally speaking the stronger the anonymity of the mixing, the more difficult to deal with denial-of-service.

I have more comments about what actually works for anonymity at another thread.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
1508675420
Hero Member
*
Offline Offline

Posts: 1508675420

View Profile Personal Message (Offline)

Ignore
1508675420
Reply with quote  #2

1508675420
Report to moderator
1508675420
Hero Member
*
Offline Offline

Posts: 1508675420

View Profile Personal Message (Offline)

Ignore
1508675420
Reply with quote  #2

1508675420
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1508675420
Hero Member
*
Offline Offline

Posts: 1508675420

View Profile Personal Message (Offline)

Ignore
1508675420
Reply with quote  #2

1508675420
Report to moderator
therealbigcoin
Full Member
***
Offline Offline

Activity: 188



View Profile
March 03, 2014, 07:42:22 AM
 #442

The extant solution for anonymous networks (Tor) requires extra steps that many users won't do,
Tor is actually quite easy to bundle, and some other programs (like torchat) already do. I'd assume that someday there would be bitcoin clients offered with bundled tor.

I was looking at Orchid (a Tor library) today and saw Mike Hearn's name on a github pull request: https://github.com/subgraph/Orchid/pull/9 with the comment: "I need this fix for bitcoinj."

how about security? I think most exit nodes are under nsa controll, how could that improved?

gweedo
Legendary
*
Offline Offline

Activity: 1246


Java, PHP, HTML/CSS Programmer for Hire!


View Profile WWW
March 03, 2014, 07:54:00 AM
 #443

The extant solution for anonymous networks (Tor) requires extra steps that many users won't do,
Tor is actually quite easy to bundle, and some other programs (like torchat) already do. I'd assume that someday there would be bitcoin clients offered with bundled tor.

I was looking at Orchid (a Tor library) today and saw Mike Hearn's name on a github pull request: https://github.com/subgraph/Orchid/pull/9 with the comment: "I need this fix for bitcoinj."

how about security? I think most exit nodes are under nsa controll, how could that improved?

I am pretty sure since bitcoind nodes support only tor interactions and many people run them in that state, their would be no reason to hit an exit node if you don't want to, since you would be routed to the bitcoind nodes on tor.

Even if you do hit an NSA controlled exit node, the worst they can do is act like a cancer node to you, and give you false data, and you send rejected transactions on the network.

Want to earn 2500 SATOSHIS per hour? Come Chat and Chill in https://goseemybits.com/lobby
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 11, 2014, 08:55:57 AM
 #444

Comments please on my technical statement herein?

Yes, I think CoinJoin should be a very good start.  But do any really decentralised and fully working implementations of CoinJoin exist already?  I don't think so and would be interested to know if they are.

I'm not aware of any either but don't let that deter you from using one of the already existing solutions even if they aren't perfect.

A decentralized CoinJoin will have difficulty forming transactions (including unequal or equal transaction amounts) that look like this if anyone can join:

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

A sharedcoin transaction will look something like this: https://blockchain.info/tx/e4abb15310348edc606e597effc81697bfce4b6de7598347f17c2befd4febf3b (picked at random). As you can see multiple inputs and outputs make the determining the actual sender and receiver more difficult.

The server does not need to keep any logs and transactions are only kept in memory for a short time. However If the server was compromised or under subpoena it could be force...

Because the way it must work is the users sign the transaction first with their requested outputs, then in the second round they sign their payments as inputs to the transaction. If the payment inputs are less than the total, then the transaction is invalid. There is no way to determine who cheated and rate limit them. Thus the saboteur can stomp on every attempt to create a CoinJoin transaction and destroy the decentralized system.

DarkCoin says they can solve this by charging a fee, but you will see I originally proposed that idea in the CoinJoin thread and the requirement is all the participants must be permanently identified and then must use divide-and-conquer to whittle down to who was the saboteur. But identification defeats the mixing!

Thus I have not yet seen a workable decentralized CoinJoin that can scale. And I don't expect one.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
March 11, 2014, 02:13:16 PM
 #445

AnonMint, Every post you've made here has been error and confusion.

The very first post in the thread points out that decentralized versions take more work because of the anti-DOS proofing. A couple posts down I give some examples of how it can be done.

You're presuming a broken model that I don't believe anyone here has ever suggested. You'd always being the protocol by specifying the inputs in which you intend to sign. Signature authority over inputs is the principle scarcity that allows you to may the system dos-attack resistant. After the inputs are signed, outputs can be specified in a cheat proof way, and then the only avenue for disruption is refusing to sign which can be addressed by blacklisting your inputs (and other rate limiting tokens) and restarting.

Bitcoin will not be compromised
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 11, 2014, 03:41:59 PM
 #446

AnonMint, Every post you've made here has been error and confusion.

Keep your ad hominem attacks out of it please. I asked kindly for technical comments.

The very first post in the thread points out that decentralized versions take more work because of the anti-DOS proofing.

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.

[A couple posts down](https://bitcointalk.org/index.php?topic=279249.msg2984051#msg2984051) I give some examples of how it can be done.

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're presuming a broken model that I don't believe anyone here has ever suggested.

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

Since you didn't see the equivalence let me explain it. I thought you were smart enough to deduce such things. I chose to let the signatures of inputs go in the second and final round and point to a transaction because I envisioned using ring signatures. And the transaction won't be valid (blockchain will reject it) if the inputs are less than the outputs, so my version is just as safe as yours. And the DOS problem is equivalent. Come on you are a math guy, you can surely see that without me needing to explain it you.

And if you think about it a while you will realize, by inverting the operations and using a ring signature, mine has advantages suchas that not all have to sign in the first round before proceeding to the second round (they get excluded from second round too). Yet the DOS issue remains in the final.

You'd always being the protocol by specifying the inputs in which you intend to sign. Signature authority over inputs is the principle scarcity that allows you to may the system dos-attack resistant. After the inputs are signed, outputs can be specified in a cheat proof way, and then the only avenue for disruption is refusing to sign which can be addressed by blacklisting your inputs (and other rate limiting tokens) and restarting.

Well now you see your error. You can reread my post again, and admit I was correct.

From your upthread post:

If a party fails to sign, everyone else is convinced that its because they are jamming the process (intentionally or maliciously) and then can all ban (ignore in the future) whatever costly identity they used to enter the mix, or — if there is no other mechanism— that particular txin which they used.

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

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
March 11, 2014, 05:40:08 PM
 #447

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.

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

Quote
And exactly how do you propose to identify that adversary in a decentralized setting?  Wink 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:

An example (using the blind signature approach, simplified for equal values) is that each participant cryptographically blinds their desired output, and then signs their blinded output using the keys from their intended inputs.  They then present to the group their inputs (and assuming those inputs are not black-listed) everyone in the group blind-signs each of the outputs. Then everyone connects again with new connections (e.g. a new circuit in tor) and presents their unblinded outputs and their signatures. Now everyone knows that all of the provided outputs were from authorized parties— but not the correspondence. The transaction is composed and— back on their original connections— they all sign. If someone doesn't sign, it means they're jamming the process, everyone blacklists theirs inputs and automatically restarts.  The network naturally rate limits them via the finite supply of available outputs.  (of course, if you want you can attack other valuable identities to the first step, like coin burning or what have you, if the natural network rate limit isn't enough).

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.

Bitcoin will not be compromised
wheatstone
Member
**
Offline Offline

Activity: 82


View Profile
March 11, 2014, 07:28:29 PM
 #448

Keep your ad hominem attacks out of it please. I asked kindly for technical comments.

I think you misunderstand what an ad hominem attack is. If gmaxwell had called you are blithering fool, that would qualify. As it were, he pointed out that your posts have been incorrect and confused, and then backed it up with specifics. That's not attacking the man, that's attacking the content (which was full of errors and confused).

You might try answering gmaxwell's assertion that ratelimiting is, in fact, not an issue instead of merely stipulating that it is insoluble.

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.
solex
Legendary
*
Offline Offline

Activity: 1078


100 satoshis -> ISO code


View Profile
March 11, 2014, 07:54:50 PM
 #449

I have had the AnonyMint on ignore for months now and my experience of this forum is much improved. Shame that quotes still occur, however.

Crowex
Member
**
Offline Offline

Activity: 111


View Profile
March 11, 2014, 08:24:02 PM
 #450

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?
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
March 11, 2014, 09:33:59 PM
 #451

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

Bitcoin will not be compromised
itsunderstood
Sr. Member
****
Offline Offline

Activity: 364


American1973


View Profile
March 11, 2014, 11:34:46 PM
 #452

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.

Check out my prescient ATS thread from 2008: "Windows XP: End the Cyberwar, Open the Code Now!" http://www.abovetopsecret.com/forum/thread411978/pg1
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 12, 2014, 04:12:26 AM
 #453

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.

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

Quote
And exactly how do you propose to identify that adversary in a decentralized setting?  Wink 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.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
March 12, 2014, 06:57:34 AM
 #454

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.

Quote
And exactly how do you propose to identify that adversary in a decentralized setting?  Wink 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.
...by the fact that they fail to sign.

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)

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.

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.

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

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

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

Bitcoin will not be compromised
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 12, 2014, 08:40:14 AM
 #455

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?


Quote
And exactly how do you propose to identify that adversary in a decentralized setting?  Wink 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.
...by the fact that they fail to sign.

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.

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

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 12, 2014, 10:13:14 AM
 #456

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

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2324



View Profile
March 12, 2014, 03:38:01 PM
 #457

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

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

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

Bitcoin will not be compromised
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 12, 2014, 05:44:40 PM
 #458

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.

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
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?

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
malevolent
can into space
Staff
Legendary
*
Offline Offline

Activity: 1834



View Profile
March 12, 2014, 06:14:47 PM
 #459

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
Hero Member
*****
Offline Offline

Activity: 518


View Profile
March 12, 2014, 06:34:15 PM
 #460

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.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [23] 24 25 26 27 28 29 30 31 32 33 34 35 »
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!