CoinJoin: Bitcoin privacy for the real world

[Peter Todd]

2-party-mix proposal, as discussed on IRC:

First of all it has to be recognized that in a truly decentralized environment that are almost no protections against sybil attackers; the best you can do is make a sybil attack expensive. Because of this a n-party-mix with fancy cryptography is equivalent to an iterated 2-party mix. (even in an n-party-mix n-1 of the parties might be a sybil attacker) This is not true for the non-decentralized case, such as a mix where access is controlled by possession of a bitcointalk account, or a good OTR reputation.

Secondly in a 2 party mix the other party automatically knows what txins and txouts you are contributing to the mix by process of elimination. There's nothing you can do about that. However you can ensure that only that party knows, provided your counter-party doesn't reveal the info.

Thirdly the anti-dos limited resource should be denominated in Bitcoins, not proof of work or some other similar scheme; you want a large-scale attacker to have costs as similar as possible to a small-scale attacker and PoW functions are very susceptible to large improvements due to optimization. For Bitcoin's that optimization has already happened.

So, building on my previous thoughts earlier in this thread, I'm proposing the following basic mix protocol, here between Alice and Bob:

• 1) Announce: Alice states that she wishes to create a transaction.
• 2) Reply: Bob replies with the txins and txout he wishes to add to the transaction.
• 3) Sign: Alice signs her txins and sends the signatures to Bob.
• 4) Broadcast: Bob signs his txins, and broadcasts the transaction.

Step 1 happens in the clear; steps 2 and 3 can be encrypted to the pubkeys of the respective receivers.

For anti-DoS the act of broadcasting these messages can be made expensive by requiring the senders to include a nLockTime'd transaction spending a txin to a scriptPubKey the sender controls. Usually this txin would be used in the mix, although technically it doesn't have to be. The key idea here is that by broadcasting such a tx the sender is guaranteed to spend some tx fees somehow, either in the nLockTime'd tx, or in a different tx with the same txin. The actual amount of fees required per KB of data broadcast can be adjusted automatically by supply and demand.

Note how since tx fees are what is being used you automatically have sybil resistance: an attacker trying to be the counter-party to a large % of total traffic will need to either spend, or have access to the privkeys of, a large % of all the transactions being done on Bitcoin itself. While any individual transaction may get unlucky and fall victim to an eavesdropper, overall there is a significant privacy benefit.

As for the broadcast medium, like I suggested above, putting this data on the Bitcoin P2P network itself makes the most sense to ensure the widest possible usage. Similarly re: usage, note how the only cryptographic primitive used in the above protocol that is not currently used by Bitcoin wallets is asymmetric encryption. Being only two parties transactions can go through quickly when counter-parties are available, and they can timeout and fallback to standard transactions otherwise. Bandwidth usage is a small multiple of the transactions themselves; potentially less if return-path routing of the replies can be made to work properly.

FWIW I'm planning on implementing this, either directly in the satoshi client, or as a prototype in python-bitcoinlib. It's a good complement to more complex schemes utilizing multi-party cryptography primitives for mixes among semi-centralized groups.

[AnonyMint]

What about DOS attacks? Can't someone refuse to sign even if the transaction is valid?

Yes, this can be DOS attacked in two different ways: someone can refuse to sign a valid joint transaction, or someone can spend their input out from under the joint transaction before it completes.

However, if all the signatures don't come in within some time limit, or a conflicting transaction is created, you can simply leave the bad parties and try again. With an automated process any retries would be invisible to the user. So the only real risk is a persistent DOS attacker.

In the non-decentralized (or decentralized but non-private to participants) case, gaining some immunity to DOS attackers is easy: if someone fails to sign for an input, you blacklist that input from further rounds. They are then naturally rate-limited by their ability to create more confirmed Bitcoin transactions.

I don't see any way for the DoS adversary to spend the input before the joint transaction completes, if the joint transaction is atomic in the current block. If the joint transaction has been populated to all mining pools, then the input is disallowed by those pools to be double-spent in another transaction in the same block. If there is a competing PoW fork which didn't grab the joint transaction, then which ever fork wins will unwind the transactions of the losing fork(s). Am I missing something or was your point specific to limitations of Bitcoin (and not any altcoin in general)?

If those who want to participate in the joint transaction must sign with their private key to prove they have the funds available, before the set of payers (participant signers) is selected, then they can be fined for not signing the joint transaction. Am I missing something?

I do not know what Bitcoin miners do when they see double-spend attempts in the same atomic block. I am thinking they should submit these to the blockchain under some special transaction which fines the payer.

I guess one issue is that for example with ring (group) signatures, the identity of the signers of the outputs is not known, so if the sum of the outputs doesn't match the sum of the inputs, then it is not known whom to penalize for oversubscribing (DoS) the outputs. We don't want a bijective mapping between inputs and outputs.

This is not decentralized in the sense that the blockchain is a central ledger, but it is meta-decentralized in the sense that PoW input entropy is.

[genjix]

lol just received this email about our coinjoin server. we are running nothing except tor and our own software (checked processes).

-----Original Message-----

From: abuse@hetzner.de
Sent: 30 August 2013 07:54
To: XXX
Subject: Abuse Message [AbuseID:0D0482:15]: AbuseNormal: 22-102567054 Notice of
Unauthorized Use of Paramount Pictures Corporation Property

Dear Mr XXX,

We received information about spam or abuse from paramount@copyright-compliance.com.
Please take all necessary measures to avoid this in the future.

Furthermore we request that you send a short response within 24 hours to us and to
the complainant. This response should contain information about how this could
happen and what you intend to do about it.

How to proceed:
-       Solve the problem
-       Send a response to us: Use the following link:
http://abuse.hetzner.de/statements/?token=gdfsdfggdghhdddghhdg
-       Send a response by email to the complainant

A technician will check the data and coordinate further proceeding. If we received
multiple complaints, the situation can lead to a server blocking.

Important note:
When you reply to us, please leave the abuse ID [AbuseID:djkdfkdgfsf] unchanged in the
subject line.


Best regards,

Sandra Betz

Hetzner Online AG
Stuttgarter Str. 1
91710 Gunzenhausen
Tel: +49

• 9831 610061

Fax: +49

• 9831 610062

abuse@hetzner.de
www.hetzner.de

Register Court: Registergericht Ansbach, HRB 3204
Management Board: Dipl. Ing. (FH) Martin Hetzner
Chairwoman of the Supervisory Board: Diana Rothhan

----- attachment -----

Return-path: <paramount@copyright-compliance.com>
Envelope-to: abuse@hetzner.de
Delivery-date: Thu, 29 Aug 2013 17:52:21 +0200
Received: from [67.128.96.38] (helo=newpop2.baytsp.com)
        by lms.your-server.de with esmtp (Exim 4.74)
        (envelope-from <paramount@copyright-compliance.com>)
        id 1VF4WC-0005Im-FE
        for abuse@hetzner.de; Thu, 29 Aug 2013 17:52:21 +0200
Received: from portalmail2.baytsp.com ([10.243.1.48])
        by newpop2.baytsp.com (8.14.4/8.14.4) with ESMTP id r7TFq9cU019137
        for <abuse@hetzner.de>; Thu, 29 Aug 2013 15:52:10 GMT
Date: Thu, 29 Aug 2013 15:52:09 GMT
From: "paramount@copyright-compliance.com" <paramount@copyright-compliance.com>
To: abuse@hetzner.de
Message-ID: <12570450.32906.1377791529817.JavaMail.dc@portalmail2>
Subject: 22-102567054 Notice of Unauthorized Use of Paramount Pictures
 Corporation Property
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: Clear (ClamAV 0.97.6/17768/Thu Aug 29 16:10:58 2013)
X-Spam-Score: 1.5 (+)
Delivered-To: he1-abuse@hetzner.de

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Notice ID: 22-102567054
Notice Date: 29 Aug 2013 15:52:08 GMT

Hetzner Online AG

Dear Sir or Madam:

Irdeto USA, Inc. (hereinafter referred to as "Irdeto") swears under penalty of
perjury that Paramount Pictures Corporation ("Paramount") has authorized Irdeto to
act as its non-exclusive agent for copyright infringement notification.  Irdeto's
search of the protocol listed below has detected infringements of Paramount's
copyright interests on your IP addresses as detailed in the below report.

Irdeto has reasonable good faith belief that use of the material in the manner
complained of in the below report is not authorized by Paramount, its agents, or the
law.  The information provided herein is accurate to the best of our knowledge.
Therefore, this letter is an official notification to effect removal of the detected
infringement listed in the below report.  The Berne Convention for the Protection of
Literary and Artistic Works, the Universal Copyright Convention, as well as
bilateral treaties with other countries allow for protection of client's copyrighted
work even beyond U.S. borders.  The below documentation specifies the exact location
of the infringement.

We hereby request that you immediately remove or block access to the infringing
material, as specified in the copyright laws, and insure the user refrains from
using or sharing with others unauthorized Paramount's materials in the future.

Further, we believe that the entire Internet community benefits when these matters
are resolved cooperatively.  We urge you to take immediate action to stop this
infringing activity and inform us of the results of your actions.  We appreciate
your efforts toward this common goal.

Please send us a prompt response indicating the actions you have taken to resolve
this matter, making sure to reference the Notice ID number above in your response.

If you do not wish to reply by email, please use our Web Interface by clicking on
the following link:
http://webreply.copyright-compliance.com/WebReply?webreplyhash=a1fd4ac345b02bfd8ccde04dafbefbb2

Nothing in this letter shall serve as a waiver of any rights or remedies of
Paramount with respect to the alleged infringement, all of which are expressly
reserved.  Should you need to contact me, I may be reached at the below address.

Regards,

Andrew Beck
Irdeto USA, Inc.
3255-3 Scott Blvd. Suite 101 Santa Clara, CA 95054
Phone: 408-492-8500  fax: 408-727-6743
paramount@copyright-compliance.com

*pgp public key is available on the key server at http://pgp.mit.edu

Note: The information transmitted in this Notice is intended only for the person or
entity to which it is addressed and may contain confidential and/or privileged
material.  Any review, reproduction, retransmission, dissemination or other use of,
or taking of any action in reliance upon, this information by persons or entities
other than the intended recipient is prohibited.  If you received this in error,
please contact the sender and delete the material from all computers.

This infringement notice contains an XML tag that can be used to automate the
processing of this data.  If you would like more information on how to use this tag
please contact Irdeto.

Evidentiary Information:

Notice ID: 22-102567054
Initial Infringement Timestamp: 29 Aug 2013 15:39:19 GMT
Recent Infringement Timestamp: 29 Aug 2013 15:39:19 GMT
Infringers IP Address: 46.4.92.107
Protocol: BitTorrent
Infringed Work: Jack Reacher
Infringing File Name: Jack.Reacher.2012.FRENCH.BDRip.XviD-AYMO.avi
Infringing File Size: 1464350720
Bay ID: 5166dd04b34ac587893959274914e9a782d8c375|1464350720
Port ID: 40670
Infringer's User Name:

- - ---Start ACNS XML
<?xml version="1.0" encoding="UTF-8"?>
<Infringement xmlns="http://www.acns.net/ACNS"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.acns.net/ACNS
http://www.acns.net/v1.2/ACNS2v1_2.xsd">
    <Case>
        <ID>22-102567054</ID>
        <Status>Open</Status>
    </Case>
    <Complainant>
        <Entity>Irdeto USA, Inc</Entity>
        <Contact>Andrew Beck</Contact>
        <Address>3255-3 Scott Blvd. Suite 101, Santa Clara, California 95054 United
States of America</Address>
        <Phone>408-492-8500,408-727-6743</Phone>
        <Email>paramount@copyright-compliance.com</Email>
    </Complainant>
    <Service_Provider>
        <Entity>Hetzner Online AG</Entity>
        <Email>abuse@hetzner.de</Email>
    </Service_Provider>
    <Source>
        <TimeStamp>2013-08-29T15:39:19.000Z</TimeStamp>
        <IP_Address>46.4.92.107</IP_Address>
        <Port>40670</Port>
        <Type>BitTorrent</Type>
        <UserName></UserName>
        <Number_Files>1</Number_Files>
        <Deja_Vu>No</Deja_Vu>
    </Source>
    <Content>
        <Item>
            <TimeStamp>2013-08-29T15:39:19.000Z</TimeStamp>
            <Title>Jack Reacher</Title>
            <FileName>Jack.Reacher.2012.FRENCH.BDRip.XviD-AYMO.avi</FileName>
            <FileSize>1464350720</FileSize>
            <URL></URL>
        </Item>
    </Content>
</Infringement>
- - ---End ACNS XML
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.17 (MingW32)

iQEcBAEBAgAGBQJSH24pAAoJEPbLkHDojX/o54sH/3xKVr2nWY17u26+ulU16T6i
gsrEizaKOnWqC+FSALnQUuDE+eUUyCtRJb/Ce21kPmn5xiaHv96EzwzbvRPCsnBg
ecKo/MKEUJfzTgwwgoMCKHRePhNwJikToH1Daj5xOJEWw3KXHCUN4IkfBMlfttkW
yH5hH0+AE5weD86TjApW35bzxgcjXoC3YNKzNXw6lgFaHv+SrK4A24Jh4UEJxo8+
qa4Ca7eN7gXvu10fy6TH6rW9eunsYkdA5Za6pEUUkPhKACPJHY6ORvIPGRhuSma7
RNwv+uJ9srgV/W54SniuUyU3jfgyW2OHH6Nej5ONC9oJg1GMo+mG3Jm5kCw7Sss=
=sF8x
-----END PGP SIGNATURE-----

[AnonyMint]

I guess one issue is that for example with ring (group) signatures, the identity of the signers of the outputs is not known, so if the sum of the outputs doesn't match the sum of the inputs, then it is not known whom to penalize for oversubscribing (DoS) the outputs. We don't want a bijective mapping between inputs and outputs.

The only solution to this I see is to use divide-and-conquer to find the adversary (identity tied to the public key committed to the input). By dividing the set size in half and repeat, eventually the adversaries are discovered or they relent and complete the transaction. This is why a mandatory tx fee is important, so as to deplete their capital if they send to themselves.

The output signatures come at step 2, before step 3 where all sign their inputs, thus recursively repeating this operation is less time costly than being able to DoS step 3.

[Hawkix]

Just an idea - what if we moved the mixing service to miners as a part of the job they do?

- users would broadcast special half-baked transaction (just inputs)
- miners would somehow form the queue of unsigned inputs into mixing "batches" and provide a way how to query current batches
- users would broadcast their signatures of the batch
- when the batch is signed by all parties, its moved by miner into the current block, if after some timeout it is not signed (few blocks?), its dumped

This would reuse existing Bitcoin p2p network and add new message type(s). The transaction will remain the same, no need for fork. It will allow easy integration into existing clients.

[AnonyMint]

Just an idea - what if we moved the mixing service to miners as a part of the job they do?

- users would broadcast special half-baked transaction (just inputs)
- miners would somehow form the queue of unsigned inputs into mixing "batches" and provide a way how to query current batches
- users would broadcast their signatures of the batch
- when the batch is signed by all parties, its moved by miner into the current block, if after some timeout it is not signed (few blocks?), its dumped

This would reuse existing Bitcoin p2p network and add new message type(s). The transaction will remain the same, no need for fork. It will allow easy integration into existing clients.

Thanks for copying my idea upthread, and you added an idea of how to integrate without a fork. I can't comment if that will work or not.

[Hawkix]

Thanks for copying my idea upthread, and you added an idea of how to integrate without a fork. I can't comment if that will work or not.

Not copied, my own ramblings. Which thread?

[AnonyMint]

Thanks for copying my idea upthread, and you added an idea of how to integrate without a fork. I can't comment if that will work or not.

Not copied, my own ramblings. Which thread?

My prior 4 posts in this thread today before you wrote yours. Ignoring the one about high-latency mix-nets.

[AnonyMint]

The advanced crypto part isn't necessarily that advanced and doesn't require ZK proof systems. Such protocols were already designed:

http://blog.ezyang.com/2012/07/secure-multiparty-bitcoin-anonymization/

It just requires secure multi-party sorts, which is a more well studied subset of general MPC.

A couple minutes ago Phantomcircuit directed me to this writeup...

That has two weaknesses:

1. All transactions must be the same amount.

2. The participants have to be trusted to produce uniformly distributed keys. I think this means it isn't secure?

[AnonyMint]

Ok, so coin age would be your DoS countermeasure?

Note that attackers don't actually have to spend that input if they disrupt the protocol. They can use the same one over and over, even many times simultaneously.

PoW could be an option where participants can set a minimum PoW accepted and a maximum PoW they're themselves willing to perform. So for example if 10 people all have 2^15 work within their range of acceptable PoW (one has 2^15 as their lowest, another as their highest, they'll all generate a common input for PoW and start working on it. Then they start this scheme with the SMPC. That would indeed make the attack costly for somebody trying to break the scheme for as many as possible (DoS) and would make Sybil very costly.

Upthread earlier today I proposed a fee for not completing the transaction. I guess you are not proposing that because of timeouts when the participant can't complete but not due to malice?

Thus you propose PoW an a resource cost, hoping this will rate limit.

Hmm. But the rate limiting has to be severe enough that the adversary can't basically shut down transactions (if all are going to be mixed by default which is what I want) entirely, so I am thinking there needs to be a much more severe cost on the adversary.

All costs that fall on the adversary will also fall on the honest participants, but asymmetrically because the adversary will always incur the cost and the participant will only incur it on network timeout.

It isn't certain that you'd be able to tell WHICH input that the attacker used, at least not with my scheme where you hide who's using what input. Revealing who's using what input might not be optimal if a user want to use inputs already tied to himself AND some inputs that aren't already, and doesn't want the unlinked ones to become linked to him.

Send all inputs to one key first.

[AnonyMint]

So if my understanding is correct, a ring signature is comprised of the N public keys and N + 1 large random values (N + 3 for ECDSA), for each signer so (N + 1)^2 plus the N public keys total if each participant is only sending to one output. In practice, they will send to more than one output to hide correlation of input and output amounts.

Yet if my thinking is correct, these large signatures don't need to be stored in the blockchain permanently. This signature only needs to be shown as evidence to all near-term PoW peers for what goes permanently into the blockchain, which are spends for each input to a special public key (which can't spend any other way) which has "spends" corresponding to each output in the signature. So it appears this would require a soft-fork of Bitcoin, because the participants can't send to a normal public key.

Can anyone comment on whether my understanding is correct or not?

[gmaxwell]

Can anyone comment on whether my understanding is correct or not?

No, thats incorrect. Putting ring signatures in transactions would require a hard fork, and under our current security model would require storing the large signature.

Moreover, ring signatures would not be useful in the blockchain. Adam suggested (uh thanks for pointing to that, I missed that post!) using a ring signature for exactly the same purpose that I suggested blind signing: it would be a mechanism external to the blockchain that participants would communicate the set of outputs to each other without identifying the source.  If someone were to try to do what you're suggesting it would enable any of the participants in the transaction to steal the coins. This is exactly the opposite of what we want.

As an aside would you mind adding a link particular ECC ring signature scheme that you're looking at? A reasonably efficient ECC ring signature scheme would be useful to have, and might result in a faster and more compact implementation than the blinded signature approach (esp with many participants). Though I'm not sure how to prevent DOS attacks in such a scheme, since if you get too many outputs you can't tell which party was the cheater, though perhaps some ring signature system would in the event of failure have a way to deanonymize the users so they could determine who produced the extra output.

[AnonyMint]

Can anyone comment on whether my understanding is correct or not?

No, thats incorrect. Putting ring signatures in transactions would require a hard fork, and under our current security model would require storing the large signature.

If there exists a secure proof (the group signature, plus the spend transactions signed by all participants) that total of inputs match the total of outputs and all peers have agreed on this by accepting the block, then we don't need to keep that proof around in the blockchain. We can just keep the spend transactions to a key and spends from that key to the outputs. This would be a special key that the miner can not spend any other way than to providing the matching secure proof. If you disagree, please kindly explain why and not just assert I am wrong without any explanation. I assume you are correct, but I need to see why? Thank you in advance for helping me to understand.

Moreover, ring signatures would not be useful in the blockchain. Adam suggested (uh thanks for pointing to that, I missed that post!) using a ring signature for exactly the same purpose that I suggested blind signing: it would be a mechanism external to the blockchain that participants would communicate the set of outputs to each other without identifying the source.

Yes, but I am explaining how I am thinking we can use the miner to help out in a special way as I have described upthread.

If someone were to try to do what you're suggesting it would enable any of the participants in the transaction to steal the coins. This is exactly the opposite of what we want.

How so? The participants sign to a special key that can't be spent any other way (blockchain will forbid it).

As an aside would you mind adding a link particular ECC ring signature scheme that you're looking at? A reasonably efficient ECC ring signature scheme would be useful to have, and might result in a faster and more compact implementation than the blinded signature approach (esp with many participants). Though I'm not sure how to prevent DOS attacks in such a scheme, since if you get too many outputs you can't tell which party was the cheater, though perhaps some ring signature system would in the event of failure have a way to deanonymize the users so they could determine who produced the extra output.

Upthread, I described a divide-n-conquer strategy for identifying the adversarial DoS participant.

I just pulled up the first thing on Google, not sure if it is applicable, Anonymous signcryption in ring signature scheme
over elliptic curve cryptosystem

Thanks for the reply.

[gmaxwell]

If there exists a secure proof (the group signature, plus the spend transactions signed by all participants) that inputs match the outputs and all peers have
agreed on this by accepting the block, then we don't need to keep that proof around in the blockchain. We can just keep the spend transactions to a key and spends from that key to the outputs. This would be a special key that the miner can not spend any other way than to providing the matching secure proof. If you disagree, please kindly explain why and not just assert I am wrong without any explanation. I assume you are correct, but I need to see why? Thank you in advance for helping me to understand.

This is oftopic, I was trying to avoid the Bitcoin 101 in this thread.

The security model of Bitcoin is that nodes do not trust the network. The network is anonymous parties and could be chalk full of sybils, so we consider it malicious at all times.  We verify _everything_ for ourselves that can be— the one thing that cannot be is transaction ordering.  Because everything is verified the potential for gain in sybil attacking or lying about the ordering is small.  Under what you're suggesting miners could steal arbitrary coins from third parties at the expense of mining a few blocks (whatever depth you require to permit hiding the proof). This isn't the security model we've adopted, and it's one that might unhinge the economic alignment of miners.

As to why it would be a forking change— you want the Bitcoin network to allow the spending of coin based not on the current signature types allowed but on a new ring type.  These transactions would look like theft to the existing network and so they can't be supported without a hardfork to relax the rules.

How so? The participants sign to a special key that can't be spent any other way (blockchain will forbid it).

A ring signature specifies N keys and then provides a signature which could have been provided by any of the N. I may have been misunderstanding what you were suggesting but it sounded like you were saying that a transaction would be signed by a ring signature over its inputs.  This means that without your consent I could take a coin of mine, and a coin of yours, and write a transaction paying to two addresses of mine, and provide a ring signature ... and steal your coin.

If instead you mean that it would also require the individual scalar signatures. Then there is never any reason to have the ring signature in the blockchain, the participants could just perform it externally and sign conditionally on it passing.

[maaku]

I pushed the beginnings of a framework for a CoinJoin implementation using RSA blinded signature operations. It's written in Python and under the MIT license:

https://github.com/maaku/coinjoin

So far it's a storage layer for the various objects and message involved in the protocol, some simple primitives for the blinding operations, and a few utilities for pulling outputs from JSON-RPC. I'm working on more primitives that I will probably add next week, including tools for creating messages at various stages, and eventually getting this running over BitMessage.

Patches welcome.

[AnonyMint]

If there exists a secure proof (the group signature, plus the spend transactions signed by all participants) that inputs match the outputs and all peers have
agreed on this by accepting the block, then we don't need to keep that proof around in the blockchain. We can just keep the spend transactions to a key and spends from that key to the outputs. This would be a special key that the miner can not spend any other way than to providing the matching secure proof. If you disagree, please kindly explain why and not just assert I am wrong without any explanation. I assume you are correct, but I need to see why? Thank you in advance for helping me to understand.

This is oftopic, I was trying to avoid the Bitcoin 101 in this thread.

I think maybe I am the one teaching you Bitcoin 101 here... (yes I know you are a Bitcoin core dev and all due respect is accorded to you)

The security model of Bitcoin is that nodes do not trust the network. The network is anonymous parties and could be chalk full of sybils, so we consider it malicious at all times.  We verify _everything_ for ourselves that can be— the one thing that cannot be is transaction ordering.  Because everything is verified the potential for gain in sybil attacking or lying about the ordering is small.

I don't know why you mention Sybil attacks, since miner reputation is irrelevant.

The attacker must have 51% of the difficulty to be dishonest in order to cheat against the others who respect the protocol. Miners have an incentive to ignore what does not match the group signature proof, because other miners will ignore them, and they would waste effort doing PoW on a fork that the majority rejects.

That is basic Bitcoin 101 stuff. I think you are conflating the need to verify the transaction chain with my point. The transaction chain must be verified, because it is the way to make sure a more recent spend did not occur.

Under what you're suggesting miners could steal arbitrary coins from third parties at the expense of mining a few blocks (whatever depth you require to permit hiding the proof). This isn't the security model we've adopted, and it's one that might unhinge the economic alignment of miners.

The miner(s) can not steal anything unless they have 51% of the difficulty as explained above.

Admittedly this is worse than now, where a 51% attack can't spend other people's coins. But if you have a 51% attack, then you've got big problems any way. And as soon as a few coins are misspent, everyone will realize the network is compromised. Just keep the group signature proof in the blockchain long enough for the participants to file a public claim in the media. So lets say 1000 blocks?

As to why it would be a forking change— you want the Bitcoin network to allow the spending of coin based not on the current signature types allowed but on a new ring type.  These transactions would look like theft to the existing network and so they can't be supported without a hardfork to relax the rules.

Apology I did not make it clear that I wasn't disputing your point about hard fork.

How so? The participants sign to a special key that can't be spent any other way (blockchain will forbid it).

A ring signature specifies N keys and then provides a signature which could have been provided by any of the N. I may have been misunderstanding what you were suggesting but it sounded like you were saying that a transaction would be signed by a ring signature over its inputs.  This means that without your consent I could take a coin of mine, and a coin of yours, and write a transaction paying to two addresses of mine, and provide a ring signature ... and steal your coin.

If instead you mean that it would also require the individual scalar signatures. Then there is never any reason to have the ring signature in the blockchain, the participants could just perform it externally and sign conditionally on it passing.

I am saying that N participants (inputs) can make M signatures for outputs, where M >= N. If the total BTC of outputs != total BTC of inputs, then the N participants don't sign their inputs. Reset and try again.

When they don't match, that is a DoS, someone is trying to cheat. I explained upthread how to use divide-n-conquer to isolate the malicious participant(s).

Got it now?

[justusranvier]

I sold bitcoins today to a forex trader, and we had a long discussion about Bitcoin and the effects it could have on global finance.

At one point in the conversation I brought up CoinJoin and what it makes possible and his immediate reaction was, "That will have to be stopped."

I replied, "What is the US government going to do; tell Chinese, European, and Russian bitcoin miners what transactions they are and are not allowed to include in blocks?"

When I said that his eyes widened and his facial expressions had "Oh, shit" written all over it.

I rather enjoyed that part of the conversation.

[gmaxwell]

At one point in the conversation I brought up CoinJoin and what it makes possible and his immediate reaction was, "That will have to be stopped."

They can't even be distinguished. Short of a complete lockdown (and a total failure of the system) there is no way to block the activity or even reliably measure how much of it is going on.

I don't think this actually presents much concern to authorities— they manage to survive in a world where cash and other asset transfers leaves few records already.  When tax authorities question you to make sure you're paying your taxes, they'll ask to see your books same way it works with anything else... and nothing in this thread will protect someone there, at least in the US the responsibility is on the taxpayer to show they paid their taxes.  But in any case, the political debate is moot... just due to the technological inevitability of this: I've tried to think of a way to prevent it, and I cannot.

[AnonyMint]

The miner(s) can not steal anything unless they have 51% of the difficulty as explained above.

Admittedly this is worse than now, where a 51% attack can't spend other people's coins. But if you have a 51% attack, then you've got big problems any way. And as soon as a few coins are misspent, everyone will realize the network is compromised. Just keep the group signature proof in the blockchain long enough for the participants to file a public claim in the media. So lets say 1000 blocks?

And even there may be a solution to this 51% attack that enables the miners spending the coins. We keep a merkel hash of these signatures forever, so the spenders (or bitarchive.org ... does it exist?) can keep copies of the signatures and later prove if the miners have cheated. This would serve for rebuilding the blockchain manually, because with a 51% attack, the Bitcoin world is fubar anyway.

[gmaxwell]

Please keep posts on-topic. I'm going to start splitting non-coinjoin discussions out of this thread.