Byzantine Cycle Mode

Hi Everyone,

This week markets have been mostly stable, trading between $485/BTC and $585/BTC.  Trading volume this week has been low.  This calmness in the markets is generally a positive sign.  If we assume miners and merchants sell off their coins at a fairly constant rate, low trading volume and a steady price would suggest that retail bitcoiners are mostly buying.  Compare this to an environment where there is high trading volume and a steady price.  In that environment, it is more likely that retail bitcoiners are more balanced in their buying and selling since the merchant/miner selling pressure is a smaller proportion of the total trading volume.

News:
  • Bitshares X jumped 100% this week before crashing back down, net up about 20%: http://bit.ly/1vBMGmH.
    • Tim Swanson brought to my attention rumors of a potential collaboration between Bitshares and Ethereum a few weeks ago which may have triggered this price jump: http://bit.ly/1qTb9wV.
    • In the thread, Bitshares founder, Dan Larimer, seemed to suggest a formal partnership (including distribution of ETH to Bitshares PTS/AGS holders) with Ethereum was underway while the Vitalik and Ethereum team had other ideas (informal collaboration on technical challenges, no hard promises).
    • There's also some discussion in the thread about the merits of delegated proof-of-stake (DPoS) which is Bitshares' consensus algorithm. DPoS is one of the better versions of PoS (I prefer it to checkpointing and other schemes involving ) but there is still disagreement on whether PoS or PoW is superior.
    • My main issue with Bitshares X doesn't have to do with its consensus algorithm.  It has to do with its bitAssets concept and the idea of a market-pegged asset.  I'm unconvinced that it actually works.  I think redeemability is key for the pricing of a bitAsset to reflect its corresponding "real" asset.  There's also the problem of bitAsset's positions requiring 2x of the notional as collateral: http://bit.ly/1zZwlpS.  It's sort of a reverse 1 to 3 leverage which seems to defeat the point of having this sort of market.
  • OpenBazaar announces the use of reputation pledges, a reputation system based on proof-of-burn: http://bit.ly/1vBOyMs.
    • The idea is that customers will be more likely to trust vendors who have burned away some bitcoins since it makes the loss of that reputation costly (i.e. vendors are less likely to scam customers since it destroys their reputation for which they burned bitcoins.  Scammers would have to start a new account and burn an equivalent number of bitcoins as they did the first time for their first account to achieve the same reputation level.)
  • Dogeparty, the Counterparty analog for Dogecoin, started trading on Poloniex: http://bit.ly/1nOlJo6.  It's already dropped below the ongoing genesis burn/sale price: http://bit.ly/1pyS9bF.
Recently I've been looking into a variety of different anonymity mechanisms and meta-mechanisms and also atomic cross-chain trading (i.e.a P2P way of trading BTC for LTC without the use of a third-party and without requiring trust between the two first-party participants).
  • CoinSwap: http://bit.ly/1wZbSW7.
  • CoinShuffle: http://bit.ly/1tSe2CU.
  • Byzantine Cycle Mode: http://bit.ly/1pyWknN.
  • Atomic Cross-chain Trading: http://bit.ly/1ox4pTU.
The motivation behind the anonymity work is that there are a few shortcomings of CoinJoin (master nodes know inputs and outputs; inputs to be mixed cannot be arbitrary amounts (e.g. can be 10 BTC or 100 BTC but not 8.2246 BTC or 293.463 BTC)) and these mechanisms seek to address them.

Regarding the Byzantine Cycle Mode (BCM) paper, BCM is a meta-mechanism since it does not describe in any way how the actual mixing is done.  BCM assumes that a mixing algorithm requiring equal inputs exists (e.g. CoinJoin) and outputs a method for mixing unequal inputs.  Essentially, it breaks down multi-party arbitrary-input mixing into isolated, smaller mix-cycles of equal-input mixing.  This is an important innovation because it allows all equal-input mixing algorithms/mechanisms to remain competitive with inherent nonequal-input mixing algorithms.  In other words, it makes the equal-input mixing property a non-issue since all equal-input mixers can be generalized using BCM into nonequal-input mixers.

At a very high level, this is how it works:
  • A number of players broadcast to the rest of the network that they are interested in mixing.
  • For each mix, an ordering for the players is established using predetermined rules (e.g. an ordering based on the hash of last block).
  • Each player generates random numbers and broadcasts them to each of the other players.
  • With these random numbers through Byzantine agreement, each honest player in the mixing pool comes to the same Bitcoin Flow Matrix which is a matrix representation of who will mix how much with who else. The main innovation in this paper is in defining that agreement protocol such that no one player has disproportionate influence, each player has some tangible influence, each player's desire to mix their specified amount of bitcoins is correctly represented in the final Bitcoin Flow Matrix and the calculations used to arrive at the Bitcoin Flow Matrix are deterministic so all honest players come to the same result.
  • The result is a consensus between the players on a number of mixing cycles with equal inputs.  For each cycle a player is a member of, he then reaches out to each of the other players in that cycle uses CoinJoin or some other equal-input mixing algorithm to do the actual mix.
For example, Alice, Bob, Carol, and Dan each want to mix 1, 2, 3, 4 BTC respectively.  BCM returns these cycles: Alice mixes 1 with Bob, Bob mixes 1 with Alice and 1 with Dan, Carol mixes 3 with Dan.  So the total mixing operation with inputs 1, 2, 3, and 4 gets broken down into 3 cycles of equal inputs:
  • A<=>B for 1
  • B<=>D for 1
  • C<=>D for 3
So everyone is happy.  Of course BCM could have returned different cycles.  For example:
  • A<=>D for 1
  • B<=>C for 1
  • B<=>D for 1
  • C<=>D for 2
The innovation of BCM is that all parties are able to agree through a deterministic computation, whether to go with the first case (3 cycles) or the second case (4 cycles) without anyone being able to cheat (strongly influence which case is reached).

The only minor issue I see is in the way player order is determined.  If player order was determined by previous block hash, a bad actor could enter the mixing pool when he was guaranteed to be Player 1 and then have some influence on the first mix cycle computed by the BCM (See paper).  If he had dirty coins he would be able to choose to which player his coins would be dumped.  Of course since players' identities are hidden, he would still need to associate a player number with an identity so maybe this isn't a real problem.  If this is a problem, player order can be determined, instead, by some event in the future from when the BCM is initiated such as next block hash.  In any case, this is either a minor issue or not an issue at all.

Overall, I think the BCM mechanism is robust and provides a good extension to equal-input mixing algos.

It seems like solutions to the anonymity question like the ones above are bound to improve over time.  The volume and depth of work being done on this front confirms my belief that many intelligent people think anonymous transactions are important to a well-functioning cryptocurrency.

Cheers,
Kevin & Team Buttercoin
Bitcoin Trading Made Easy | Buttercoin.com 

Buttercoin currently in Private Beta, if you'd like access right now apply here: http://bit.ly/1kSgHZg.