Today I am at the 2nd Workshop on Bitcoin Research, which is co-located with Financial Crypto. My PhD student, Marie Vasek, will be live-blogging the workshop in the comments.
Today I am at the 2nd Workshop on Bitcoin Research, which is co-located with Financial Crypto. My PhD student, Marie Vasek, will be live-blogging the workshop in the comments.
The first presentation is by Daniel Malinowski and On the Malleability of Bitcoin Transactions. Given a transaction and a bitcoin user, a bitcoin miner can “maul” or change the transaction such that it has the same sender, recipient and value, but a different binary representation and hash. Malleability attack is when an attacker gets a mauled transaction accepted into the consensus blockchain. BTC users accept the first transaction that they see which makes this attack effective. This poses some problems: transactions are normally tracked by hashes. When you change the hash, the client might think the transaction was rejected, even if the mauled version was accepted into the blockchain. If you try to make a transaction using coins from the change of a mauled transaction, than you can’t because, again, that is tied to the hash of the previous transaction. Transaction malleability happens for a number of reasons. There is malleability in ECDSA signatures. Attackers can also use nonstandard binary encoding or add dummy operations in the scriptSig of the transaction. The authors mauled transactions in their lab and found that the efficacy of the attack is around 40-50% under the scenarios when the client was not connected to the attacker and around 90% when there was a direct connection. Mt. Gox claimed that people were attacking them using transaction malleability, though the author debates whether this was actually the case. They found that all the wallets but Bitcoin Core and Xapo had errors. Most had an incorrect balance and blocked bitcoins. Restricting the syntax of Bitcoin transactions could help. Also, identifying transactions by the hash of the simplified transaction without the scriptSig. The bitcoin core developers mentioned BIP 62 in the question section, though this is not implemented yet and it cannot solve all of the transaction malleability issues.
Next up is Malte Möser on Trends, Tips, Tolls: A Longitudinal Study of Bitcoin Transaction Fees. The security of the Bitcoin blockchain is a kind of a public good: it is non-rivalrous as it is an information good and non-excludable by nature of the p2p network. BTC miners get a reward when mining a new block. Currently miners earn 25 bitcoin per block they mine, but this halves every so often (around 4 years). This is hoped to eventually be supplemented by transaction fees. If we assume we have perfectly competitive miners, and production costs are fixed per block, then a miner wil include transactions based on marginal costs. Then they will only make money if transactors are competing for space. This would cause both rivalry and excludability, which would turn the Bitcoin blockchain into a private good. The individual transaction fee stayed below 0.1% over time, which makes it more efficient than other payment systems. They found a large effect from changes in default fees in Bitcoin Core and Electrum wallet; a large volume transactor Satoshi Dice also changes the distribution. Transactions with fees are picked up quicker than those without (it seems miners respond to incentives). Though, only one mining pool has more than half of their blocks mined with no zero fee transactions. The authors suggest that monetary inflation (such as given in the large mining reward) might be better to approximate the true costs of transactions rather than individual transaction fees since many of the costs related to the mining and propagation of transactions are not known up front.
The final talk in the section is by Patrick McCorry on ZombieCoin: Powering Next-Generation Botnets with Bitcoin. Current botnets use centralized channels for command and control (such as a website or IRC channel) or decentralized channels (such as customized p2p networks) — and actually, also hybrids of the two strategies. The authors envision a botmaster sending commands through a custom crafted Bitcoin transaction. Their c&c protocol includes special commands for things such as a criminal to lease the botnet from the botmaster. They don’t rely on the blockchain, but rather the underlying p2p network. This method costs 3 cents per command and requires no maintenance. The botmaster can partition their botnet using bloom filters — another “feature” of using the Bitcoin network for a c&c channel. However, there are only about 80,000 connections available on the network. This botnet also requires the bots to be listening on the Bitcoin network, which might further incentivize antivirus companies to blacklist such Bitcoin-related software.
John Tromp introduced an alternative proof-of-work scheme Cuckoo Cycle: a memory bound graph-theoretic proof-of-work. A proof-of-work system allows a verifier to check, with negligible effort, that a prover has expended a large amount of computational effort. Hashcash is a proof-of-work system used in many cryptocurrencies such as Bitcoin. However, memory-bound proof-of-work systems (which Hashcash is not) can make mining more egalitarian. Memory-bound systems make DRAM like that ASIC for memory bound applications; SRAM is twice as expensive but not twice as effective, so it is not cost effective for memory bound proof-of-work. His scheme is based on finding a subgraph, H, in a random graph, G. In particular, H is a cycle of length L and G is a bipartite graph with half the number of edges as nodes. He picks the constants to have adequate odds of finding the cycle, but not more than one. This means that to solve the proof-of-work, a miner will have to store the entire graph in RAM. The cycle cannot be too small, motivated here by the time/memory tradeoff. The graph needs to be large enough to not all be able to fit on one chip. Like the Bitcoin difficulty can change, the difficulty for his proof-of-work can also change with the size of the graph.
The last talk before lunch is Ben Johnson on mining pools, particularly When Bitcoin Mining Pools Run Dry: A Game-Theoretic Analysis of the Long-Term Impact of Attacks Between Mining Pools. Most of the mining power in the Bitcoin network is concentrated in organized groups of miners called pools. Attacks between mining pools happen the more frequently in the Bitcoin ecosystem compared to other types of Bitcoin services. There is a potential for competition in more than just mining power, but also an adversarial competition. Last year the author group (full disclosure: along with Tyler Moore and me) looked at this in a one-off manner with a simplified model with only two pools. This year, the model is expanded to look at repeated games. They look pool strategies based on both the size of the mining pool and the relative attractiveness (such as the fee structure or the ease-of-use). In a peaceful situation, when no mining pools are attacked, the size of the pools converge to their attractiveness levels. When that convergence happens, the authors denote this the steady state. When the cost of an attack is low or migration rate is high, then the odds of attacking are great. When the pools aren’t particularly attractive, the odds of attack are lower. A peaceful equilibrium exists when the migration rate is high and the costs of attack are high. There is greater incentive to attack more attractive mining pools regardless of current size; relatedly, less attractive pools have a greater incentive to attack. Mining pool attacks can be prevented by raising the costs of attacks, increasing pool competition, and increasing the ease of migrating across pools.
The first talk after lunch is from David Vandervort and is on Issues in Designing a Bitcoin-like Community Currency. A community currency is money issues by a non-government entities which are usually restrained to a small geographic area such as the Brixton Pound good in Brixton, UK and BerkShares good in Massachusetts, US. These can be created for some common value which are evident in their distribution mechanism i.e. volunteerism (given out when volunteering). We can also see community cryptocurrencies such as Marscoin which the creator intends to be used by colonists on Mars and distributed some of the currency to the Mars Society. Community loan funds are large parts of community currencies; the blockchain can help make the loan fund transparent and enable community voting. There are many issues in community currencies; the cryptocurrency-based issues such as identity and trust largely mirror the traditional issues.
Next up is Garrick Hileman on The Bitcoin Market Potential Index. This index is motivation by the existential question: why Bitcoin? (and the corollary: when will it become adopted?) This aims a better understanding of factors that drive bitcoin adoption and highlight where it will become adopted. There are three functions of money: unit of account, medium of exchange, and store of value. According to the author, Bitcoin, to this point, has largely been only treated as a store of value (though the Bank of England issued a report listing the other two functions as depending on the money storing value). The author ranks countries based on a combined index, ranking Argentina, Venezuela, and Zimbabwe as the top in Bitcoin market potential. More generally, he finds Sub-Saharan Africa as a promising place for Bitcoin. For more information, this information is visualized at bitcoiniq.info. The variables he considers include technology penetration (technological penetration must precede Bitcoin penetration) and black market penetration (Bitcoin can circumvent government-enforced regulations) as well as current Bitcoin penetration. The big missing variable is Bitcoin-related regulation, but it is recent and, relatedly, is unclear.
Emily McReynolds is presenting on Bitcoin regulation, or more generally, Cryptographic Currencies from a Tech-Policy Perspective: Key Policy Issues and Technical Directions. In particular, this is motivated by border crossings with Bitcoin. Bitcoin is virtual, convertible money (as contrasted with Monopoly money which is physical and non-convertible). It is unclear where the money is with Bitcoin (and therefore who has jurisdiction over any particular Bitcoin). Furthermore, things like multisig make it possible for a particular Bitcoin to “live” in multiple places simultaneously. Also, just because Bitcoin makes something feasible to do, that doesn’t make it legal (such as buying drugs on the Internet or earning money without recording that to the tax office). Since Bitcoin is effectively pseudonymous, it is not as dangerous with regards to money laundering; a popular currency with stronger anonymity is more worrying to the author (and regulators). Vulnerabilities in the Bitcoin protocol and who is responsible for related havoc wrecked was also considered. There was a discussion about in which cases a US court can force you to turn over your public or private keys based on previous rulings that the US court cannot force a person to turn over a password that might incriminate her.
The last session is on privacy in Bitcoin, specifically on Bitcoin mixers. Luke Valenta starts off the final section with a talk on Blindcoin: Blinded, Accountable Mixes for Bitcoin. Bitcoin mixing services are Bitcoin laundering services which make a particular Bitcoin hard to track, obfuscating identity of the holder. This paper does an analysis of the Mixcoin protocol, presented last year at FC, which adds a warranty to the standard mixing protocol. However, the Mixcoin mixing service learns the input to the output mapping (bad for anonymity). The Blindcoin protocol builds on the Mixcoin, adding blind signatures and an append-only public log. Users send their offer (mix me 3BTC and I’ll give you 0.1BTC) to the mix, and if the mix accepts, it sends back a signed warranty and posts their commitment to return with the coin later in a public log. The user then sends in her Bitcoin to the mix and, according to the contract, the mix sends the user a blind agreement. When this blind agreement is unmasked by the user later, the mix trades sends the coin to the user’s new address. Blindcoin’s public log increases opportunities to side channel attacks and increases fees and delays. However, it also adds more privacy to mixing services. In the question section, Ian Goldberg and others raised the issue that this protocol identifies the mix in the log; speaker and others imagine a way in which the mix’s commitment is logged in a way that preserves anonymity.
The final talk of the day is from Sarah Meiklejohn on Privacy-Enhancing Overlays in Bitcoin. This paper analyses how much anonymity Bitcoin actually provides. While in theory addresses are not linked to identity, in practice, we can cluster which addresses belong to a particular user. Bitcoin mixers, such as Mixcoin, help users anonymize themselves. The author considers Coinjoin which renders clustering ineffective. These transactions do not require users to share private keys with each other and “look like” normal transactions. Here, multiple users coordinate together to make a larger transaction where all the BTC is taken from all the users in, and all the BTC is sent to the proper outputs, but precisely who sent what where is unknown. They measure how effective is deconstructing these transactions or guessing the input address(es) for each output. They looked at how many possible mappings there could be. When the adversary knows one entry of the Coinjoin transaction, she does fairly okay mapping inputs to outputs. However, when our adversary knows the transaction is a Coinjoin transaction or when the adversary is not confident that it is a Coinjoin transaction, the adversary notes many possible mappings and is less confident in her analysis.