The intent was that mixes have a one-to-one correspondence to simple cycles. So, examples 1a and 1b induce two mixes, while 1c three mixes.

After thinking over the threat model, I'm tending to agree more with laurentmt's point, and my answer to your question is this:

Combining node-distjoint cycles of the same amount is not only a viable variation, but also has the advantage of larger anonymity size for that mix. Supposing the mix amount is equal, if I were to weigh the pros of a large single trxn versus that of two with a significant time difference, I'd favor the larger trxn.

Threat model: the adversary
(1) has access to the blockchain,
(2) can differentiate, with non-negligible advantage, normal transactions from those that are apart of a mix,
(3) can know the identity of a person in control of an input address of the mix. 

Temporal distance doesn't increase anonymity, because the adversary can still tell which trxns are part of a mix. The larger anonymity set is meaningful, because the adversary can choose to examine only the mix that contains the input address of the person he's investigating. Since that trxn is larger in the combined case, the person is better protected. In the separated case, the adversary just ignores the trxn that doesn't have the address as an input.

laurentmt, this will help in the entropy analysis somewhat. Being that the # of cycles of the same flow amount is also a random variable, the size of the combined cycle is still too a RV.

LCG, I'm supportive of zerocoin/cash as well, of course. It's afterall the first and, for now, possibly the only demonstrably anonymous approach. Best regards on that exciting project.

I, like the other the devs who inspired this work, want to explore how to make bitcoin credibly anonymous using existing bitcoin capability.

Chained CoinJoins... now that's exciting! I hope this can open possibilities for chaining.

Sure I see where you're going with that, laurentmt. And agreed that entropy is less for BCM/Join than for native Joins, # of players being equal. That said, BCM is intended to make it easier to mix against larger, more diverse sets of players, and the number of mix participants is a random variable, so one could argue that the entropy comparison should be a probabilistic calculation where the expected # of players for a Join in BCM is equal to the # of players in the native join. Some txns in BCM will have fewer, some will have more.

Entropy analysis does cover the combinatorial dimension of semantic security, assuming the adversary knows all information known to any participant until the Join. Still, there are a few other dimension that I think should be taken into account.

Consider three types of adversaries for BCM:

(1) Passive - has access to the blockchain record of the mix(es), may identify whether a general BC txn is part of a mix, and may know the identity of the person controlling an input address that's part of the overall mix.

(2) Active - Participated in BCM but was not put of the Join of interest (thus knows everything in ! plus the # of coins being mixed, the mix matrix, and # of participants in the Join)
 
(3) Active - Participated in both BCM and the Join (thus knowing everything in 2 plus the input addresses of all participants, and the output addresses)

For native Join, these are one and the same type of adversary.

If we're willing to allow consideration for the common case (1) separately from the worst case (3), then with (1) BCM has something that native doesn't: the times in which the transactions occur can vary, so much so that other mix transactions can be interspersed in between transactions of this mix. There can be other non-mix transactions that look like mix transactions as well.

Greg, thanks! Yes, did find that recently and reference it in the paper. In fact I consider CoinShift an N-way extension of the same techniques.

My guess is that CoinSwap inspired the work on atomic cross-chain transactions (on which I based CoinShift)?

With CoinShift, I'm aiming for shifting ownership of bitcoins (atomic, trustless, decentralized) one step along the cycle found in BCM. (For 1<= i < N, player i transfers to player i+1. Player N transfers to player 1.)

I'll read the CoinSwap post again and explore how it lays out for N players.

Andy,

Excellent feedback, thank you for that!

You're on point in suggesting to make it explicit to prioritize non-self matches over self matches --- which can be done in the algorithm or by requiring that v_ij > 0 when i != j. The latter was my original intention.

Even with that, there is always the possibility of a self-match, which in my code I call a 'fault'. It turns out that, with the above change to ensure prioritization, there can be at most one fault. Otherwise, there would be two players who could have matched earlier (due to the above) but didn't, a contradiction.

A fault happens depending on the randomization and the conditioning of the instance, as you pointed out. Nothing to avoid, it's just a fact of life that one person may not be able to mix all of his coins in that instance.

Still, you reminded me of a topic I wanted to include in the paper on well- or ill-conditioned instances. Eg, if one player has input that is larger than the sum of all the others, then chances are that he will mix with a large number of the other players, and will certainly be the one with a self match for the remainder of his coins.

I want to avoid this or allow the players to avoid mixing in this circumstance, so another open question I will add is: can input conditions be defined that define an ill-conditioned instance? If so, then the approach will be that either each player checks for this condition during the process to decide whether to mix with a certain player or during peer discovery the condition is used to filter which players are grouped together.

On DoS:
That's exactly the line of thinking that's helpful, because I think the algorithm is such that DoS is an attacker's best option.

My thoughts are that particular attack can be mitigated by (1) adding a step where players confirm the inputs they received against each others, and (2) allowing the players to drop a peer if the result of that confirmation show that the peer sent different inputs to sufficiently high number of players. This seems similar to the blame idea from Tim's CoinShuffle paper.

What's clear is that honest players need a way to identify and boot bad players. That is a work in progress, and I been considering whether to use such a step for input confirmation for a while now. Need to be careful about opening more attack vectors by the inclusion of confirmation steps.

As part of a new open source implementation project, I've written a research paper presenting a new, complentary protocol to increase anonymity to Bitcoin.

The preliminary paper is the first of two papers describing the algorithmic underpinnings of the project, building on ideas from this forum (CoinJoin, CoinSwap, CoinShuffle, and atomic transfers)

The new algorithm, called Byzantine Cycle Mode, extends the application of Bitcoin mixing primitives (CoinJoin, etc) to large numbers of players mixing unequal inputs. I use an analogy to how encryption modes such as CTR and CBC extend the application of block ciphers (AES, 3DES) to large inputs of non whole block sizes.

Abstract:

Appreciate feedback.

The second paper, forthcoming, is on a new mixing primitive, CoinShift, based on TierNolan's atomic cross-chain solution.

Another related question to help me confirm my understanding of the contribution of CoinShuffle:

Is the following algorithm be semantically equivalent to the algorithm presented in your paper?

Communication is done peer-to-peer using public-key, authenticated encryption. 'Broadcast' in this context means a player sends a message to all the players over these links.

Each player i (1 < i < N) does the following:
1 Generate a random permutation P_i of (1, 2, ..., N)
2 Broadcast H(P_i), where H is a collision resistance hash.
3 For all j != i, receive H(P_j) from player j
4 Broadcast P_i
5 For all j != i, receive P_j from player j and confirm the hash value
6 Calculate output list = P_1 (P_2 ( ...P_N (1, 2, ..., N)...)), broadcast, and agree on that value

Player 1 creates the join transaction with the output list, and the transaction is signed by all players. The transaction is broadcasted to the blockchain.

BM, I have been exploring a strategy using N-way mixing, where by 'mixing' I mean the proper sense of creating separate transactions to exchange the coins. Whitepaper/ppt/git forthcoming.

The gist of the idea is:

(1) N players use a randomized Byzantine process to agree on a mixing specification, and then
(2) Execute multiple pairwise transactions atomically on the Bitcoin blockchain, ala TierNolan's atomic cross-chain transfer solution. This is an N-way, same-chain atomic transfer within Bitcoin (ie not cross chain).

Atomic Cross Chain Transfer discussion
https://bitcointalk.org/index.php?topic=193281.0
https://github.com/TierNolan/bips/blob/bip4x/bip-atom.mediawiki

Example:
Alice wants to mix 1 BTC
Bob wants to mix 2 BTC
Charlie wants to mix 3 BTC

In step 1, they decide on the following mix:
Alice --> Charlie 1BTC
Bob --> Charlie 2 BTC
Charlie --> Alice 1 BTC
Charlie --> Bob 2 BTC

In step 2, Alice executes her transfer to Charlie, Bob does his to Charlie, and Charlie does his to Alice and Bob. This is done in a way such that either all transfers succeed or they all fail.

I'm currently working on final steps of extending TierNolan's solution and a prototype.

Yes, this means the players pay for more transactions. One of the advantages is that the temporal locality of the transactions is loosened.

A very nice paper, guys, thanks. Will be in touch to exchange more ideas.

I have a similar paper with another approach that I will share with the community.

I agree colinistheman. Thanks for putting your thoughts out there.

Sent.

Thank you, Hal.

sundance

Thank you for that. Bitcoin is a way to support awakening consciousness and end our slavery.

Excellent talk, thanks

I see applications of this in many types of voting scenarios.

I recommend using the Paillier cryptosystem or other homomorphic cryptosystem to encrypt the contents of the vote. While people listening to the blockchain don't know who voted for who, they can see the subtotals of the vote during the vote (and potentially interfere with the outcome).

With homomorphic cryptosystems, the candidate choice is encrypted, and subtotals are done on the encrypted text so that subtotals are encrypted by definition and unknowable until the voting is done.

Great article!

"Bizarre shadowy paper-based payments system to be rolled out worldwide (or how cash would be described in the press if invented today)"

http://ledracapital.com/blog/2014/2/17/bitcoin-series-19-bizarre-shadowy-paper-based-payment-system-being-rolled-out-worldwide

Well done Mark, a nice synthesis of crypto and error correcting codes. And the code looks nice at that.

Rather, I should say, I understand what's written in the Stratum spec. Would appreciate enlightenment on what I'm missing if you're sure I don't understand what Stratum's addressing.

I understand it, and I'm talking about the network protocol aspect of it.

Guys,

Nice work on Stratum. A note that I hope you will take to heart --- this problem is already solved by open protocol standards (at least in TCP point to point cases). The rest of the financial world is already using it so for the purpose of easing future integration, it's best to leverage that instead of re-invent the wheel.

The FIX (Financial Information Exchange) protocol already covers all the requirements listed in Stratums spec and has been used for over 15 years in the financial world for relaying messages for trading, market data, request for quotes, and others. A recent open source implementation in C++ allows you to easily define new schema (xml, json) to extend the protocol.

http://fix8.org/

The protocol supports replay through sequence numbering, etc.
There are open source implementations in C++, Python, and Java, and possibly others. Oanda's FX trading system uses it:
http://fxtrade.oanda.com/images/FixSpecifications2.pdf

What you want is this to be adapted to the web server/client model.