スケーリングビットコイン・ワークショップ: Hong Kong 2015

Fungibility and scalability

adam3us (Adam Back)

slides: https://scalingbitcoin.org/hongkong2015/presentations/DAY1/1_overviews_2_back.pdf

video: https://youtube.com/watch?v=aQ1--w4uEMM&t=2443

I think everyone knows what fungibility is, it's when coins are equal and interchangeable. It's an important property for an electronic cash system. All bitcoin users would have a problem if fungability goes away.

Bitcoin has fungibility without privacy. Previous electronic cash systems had fungibility and cryptographic blinding. In Bitcoin, there's decentralized mining that somebody will process your transaction even if a given miner may not. But there is some privacy, because it's based on pseudonyms. And there's some ambiguity about change addresses and the other outputs, and there are other things we will talk about.

The types of privacy that people might be interested are things like linkability, who's paying who. Another one is the balance privacy, how many BTC you have in your wallet. Another one is the transaction privacy, how much was the payment value of the given transaction.

One of the main kind of point I wanted to make in this presentation was about the positive as well as negative aspects of introducing fungibility mechanisms. Typically we have seen fungibility mechanisms that they increase the number of transactions or they increase the size of transactions, zerocoin transactions for instance are 30 kilobytes or thereabout, and some of the mechanisms increase the UTXO as a side effect, which is undesirable for node size or scalability and stuff.

The observation to make is that some of the more advanced fungibility mechanisms can actually reduce the number of transactions and potentially reduce the UTXO size. The obvious thing to do is that for a simple fungibility is a reusable address. It slightly obscures who's paying who, at least compared to a single fully used address. Partly it.....

Often when you are using a smartphone wallet, bloom filters are not privacy-preserving. That defense is weak at the moment. It creates more addresses, increases the number of transactions, increases the size of transactions. You combine fragmented values from the wallet. Will also increase UTXO size because users will have more unseptns as result of fragmentation. It's moderately effective at best. Academics have analyzed the network and shown the effectiveness of this approach is a little weak.

One thing that could be done to reduce the linkability coming from multiple inputs into a single transactions is to use multiple independent transactions from multiple addresses to multiple receiver addresses. This could be done at a payment-protocol level.

Using the existing protocols, in a p2p format is coinjoin ((coinjoin status; see also coinswap and coinshuffle)). You have shared input addresses from different users, there's nothing preventing a transaction having inputs from different users. Combines inputs from different users, and corresponds outputs to the payments that the users would have made, combined in a single transaction that pays each of the change addresses and so on. There are restrictions. You need to provide values that gain ambiguity, you gain no privacy if it's unambiguous if the input amount is the same as a certain output amount. A disadvantage of this is that you need to coordinate with other spenders. Also, this is vulnerable to sybil attacks because some users might be attacking the system by offering to mix the coins, but really they are just trying to fill up the transaction set so that you are the only person who isn't the attacker. These protocols are trying to be trustless, such that the person operating hte server for the p2p mechanism cannot steal the coins.

Confidential transactions I mentioned at the beginning a number of different types of, some are more directly ... for the amounts of the transactions from the obsrevers. Using some relatively conservative cryptographic primitives, used in ECDSA signatures, that one can hide the values of the transactions to the network. The value of the transaction is only visible to the recipient of the transaction. The values add up and the network can verify this without seeing the actual values. This mechanism provides some indirect privacy improvement. Change is more ambiguous because you wont see $20 going in and then $13.99 going out, and the rest being change, given specific amounts and the exchange rate- well, it's somewhat ambiguous. You could also pre-emptively send zero-value transactions to other users, which adds more ambiguity. Coinjoin is more effective with confidential transactions, you can combine two sets of coins with coinjoin and it's fully ambiguous who's paying who without any extra restrictions on the implement.

Another example of the tradeoff here is that the transaction size with confidential transactions is maybe 6x larger. Would we deploy something like confidential transactions within Bitcoin given that they are 5x bigger? This presents a tough choice because of constraints on block size in Bitcoin. These transactions are providing more functionality per transaction, they are in some sense, there is an opportunity to compress it in some way. A single coinjoin confidential transaction can actually replace multiple standard transactions, to the extent that these mechanisms are used, it reduces overhead of things like merge avoidance, you get balance privacy, which others have tried to achieve by splitting up their BTC into multiple HD wallet addresses, and some have done merge avoidance or multiple payments to get value privacy. You end up with a smaller UTXO set because you have less output fragmentation. It's hard to evaluate the average reclaim space, but we might get closer to an acceptable overhead or neutral overhead. So we would have to do some anonymized data collection with users to wokr out the actual use of merge avoidance and so on, to see whether merging confidential transactions into Bitcoin would make sense.

Another method is linkable ring signatures used in some altcoins. It's slightly better than coinjoin. The sender can choose the mixer, you don't need to coordinate with all the users. The values being mixed, each coin going into the ringsig, must have the same value. This is quite restrictive on usability. Linkability is what prevents double spending. Side-effect of this is that it is not UTXO compatible. The overhead is that the ring signature is ... you can choose 5 possible other inputs, and your signature would be about 5x larger. There might be a small saver here, which is that you are less reliant on reusable addresses for linkability.

The other more powerful fungibility or privacy mechanisms is zerocoin and zerocash protocols. They are not UTXO-compatible, you have an ever-growing UTXO set or double-spend database. Zerocash hides the value, zerocoin doesn't. Each set has a denomination, you only have privacy in zerocoin within the denomination. There are some zerocoin extensions that can hide the value. The transactions are quite large. Zerocash is more practical on size basis, but CPU expensive and uses some cutting-edge cryptography that we have less confidence on. Both of these systems have a key trusted setup trap door. But otherwise, zerocash is quite ideal for fungability and privacy.

Another type of fungibility mechanism that I proposed some time ago was encrypted transactions or committed transactions. It follows the Bitcoin model of having fungability without privacy. It provides no privacy at all. It improves fungability. The way it works is that you have two-phase validation. In the first phase, the miner is able to tell that the transaction hasn't been spent. In the second phase, they learn who is being paid. The idea is that in the first phase, the miner has to mine th etransaction, and the other one happens a day later maybe. In the second phase, all the miners learn an encryption key that allows them to encrypt the first phase transaction, tell that it is valid, and do final-stage approval. There is a deterrent to censoring the second stage transaction because the first one was already mined, and you would have to have a consensus rule to approve all valid second-stage transaction, or else you might orphan the entire's day work which is quite expensive.

A related topic with fungability is the sort of tradeoff with privacy and identity. Bitcoin is intentionally an identity-less system. It's permissionless, you can operate and use it without an account. I think that what we want to achieve for internet protocols in general is to avoid it being trivial to do ... by default... investigations are always going to be possible, but there must be an incremental cost to conducting an investigating and retain societal norms. Some people have tried to argue against privacy features on electronic cash, on the basis that it would become too anonymous. I think this is not a concern. There is a video in the past where I talk about this.

There's a tradeoff with scale. Some of the advanced fungability systems might be more deployable than I previously thought, because you reclaim some space overhead. To evaluate this, we need to consider more than just the raw size of the transactions. We also have to consider the fungability and the savings in UTXO size and the number of transactions that would have otherwise been used, because we're introducing a more powerful transaction type that would have replaced other transaction patterns. To actually do this, we need to collect data about how common merge avoidance and coinjoin are.

Overall we want to improve flexibility and allow users to make choices. Fungability is very important and a very core part of Bitcoin, so I think we do have to do some work on fungability in bitcoin. These solutions are somewhat more practical than we previously thought, if we take into account the reclaimed block space from other transaction usage that would be foregone with these alternatives.

That's the end of the presentation part.

Q: Would you agree that chaining several coinjoin transactions, in privacy behind that, and confidential transactions would one coinjoin transaction be enough to completely break the link?

A: Chaining coinjoin can help, to the extent that you are not sybil attacked. A confidential transaction coinjoin is more powerful because you can choose any set of transactions, you don't have to wait for qualifying ones with an ambiguous range of values.

Q: You have talked about zerocash as a nearly-ideal solution with a few caveats, like risk around new crypto. Both of those issues seem like htey solve themselves over time. How much time? How much extra CPU do they consume? How risky is the crypto before people would begin to feel comfortable?

A: The next speaker might have some things to say about this. I think the thing, the CPU cost, CPUs become more efficient, that will improve itself. Perhaps ew can sort of combine a hybrid between desktops and smart phone wallets to improve performance. But the crypto protocol is more difficult because it depends on how conservative you want to be. The bitcoin existing crypto assumptions are really old, like 20 or 30 years old, so we have high confidence. SNARK crypto, well maybe at most 20 years and not actively used. We don't know as much about this, there hasn't been as much applied research on attacking them. And then there's a bunch of new assumptions and it's a rapidly evolving space there. The other challenge is the sort of setup trap door, there's a private key that they have to delete, so there's some variants that don't have that problem.

Q: Which proposals here would be more likely to have BIPs written in the near future?

A: Interesting question. Perhaps confidential transactions is closest, since it's implemented in sidechains elements open-source release so people could look at that. Potentially if the protocol can have its space overhead lowered, if we can get a breakthrough on that, that might bring viability forward for integration.

Q: Sidechains can help with scalability. Does this limit the scalability of sidechains for bitcoin, if sidechains have confidential transactions?

A: Confidential transactions are the default on sidechains. They can be disabled. You can have sidechains without confidential transactions. During the presentation I was trying to articulate that even though the average transaction goes to 2.5 kilobytes, or maybe 2 kilobytes with recent CT improvements, it is providing more value and more functionality. Perhaps the overhead is not as high as it sounds. A range of users have seemed interested in a range of uses for share-related uses, seeing some commercial confidentiality, so it seems to be something in demand across the full set of Bitcoin users.

Q: In encrypted transactions, there are two steps. The second step- can miners censor that? Whta happens if I never publish the second step?

A: I skipped over the details there. It's timelock-encrypted. It has to be provably decryptable at the time you publish the first phase. If you publish it, and then you fail to publish it in the future, then everyone can decrypt it, it just takes sequential execution on a CPU core.

Q: How can we ensure everyone with the valid transaction is going to use the Bitcoin Core wallet under the anonymized blockchain?

A: It is a trade-off, mainly I was arguing that the overhead is less than it seems. Maybe 5x is too much, but if we do the analysis and find that in the best case most CT transactions would replace 5 regular transactions, then maybe it will be the same overhead. The fragmentation in wallets, and the amount of transactions that arise purely from attempts to get value privacy, could give us an indication. And also there is hope that we could improve the space overhead of CT transactions, from 2.5 kilobytes to slightly under 2 kilobytes.