# X-only Pubkeys and Insecure MuSig Shortcuts

There are two posts I recently contributed to Blockstream’s engineering blog expanding on the talk I gave at The Lightning Conference 2019. Cross-posting them here because they fit the theme of this blog:

• Reducing Bitcoin Transaction Sizes with x-only Pubkeys

This article is about the recent introduction of so-called x-only pubkeys to the Bitcoin Improvement Proposal BIP-schnorr […] significantly reducing the weight of every transaction output without any loss in security. By removing the Y-coordinate byte from compressed public keys currently used in Bitcoin, public keys end up with a 32-byte representation. We are going to look at how it works, why that’s useful, and sketch a security proof.

• Insecure Shortcuts in MuSig

Using BIP-Schnorr-based multisignatures, no matter how many signers are involved, the result is a single public key and a single signature indistinguishable from a regular, single-signer BIP-Schnorr signature. This article is about optimizing implementations of multisignature protocols and why seemingly harmless changes can totally break the security.

# Secure Protocols on BIP-taproot

At Breaking Bitcoin 2019 in Amsterdam I gave a talk about how to build secure protocols on BIP-taproot or more specifically how to avoid the dangers we learned about so far. There was not enough time to cover everything. The talk also gives an introduction to how to use our MuSig implementation in libsecp256k1-zkp. The video recording is on youtube (slides). Thanks to kanzure there’s also a transcript of the talk.

Erratum: MuSig nonces can not be pre-shared. Only nonce commitments. See https://github.com/ElementsProject/secp256k1-zkp/pull/73 for details.

# Nix-bitcoin

nix-bitcoin (github.com/fort-nix/nix-bitcoin) is a project I contribute to in my spare time that provides nix packages and nixos modules for easily installing Bitcoin nodes and higher layer protocols. The initial idea was to build myself a lightning node in a reproducible way. I talked more about the motivation and how to use it at the LightningHackdayMUC (video, slides).

# Schnorr and Taproot in Lightning

Last weekend a bunch of hackers assembled for the 3rd Lightning Netword Hackday in Berlin. The event was packed with interesting sessions, neat hacks and exciting discussions which were concluded with the traditional dinner & drinks at ROOM77. I gave a talk about “Schnorr and Taproot in Lightning” (slides, video) focusing on privacy and security implications.

# Blind Signatures in Scriptless Scripts

At the recent Building on Bitcoin conference in Lisbon I gave a talk about a few new ideas in the scriptless scripts framework. The first part was mainly about blind coinswaps, which is a way to swap bitcoins with a tumbler without revealing which coin are swapped. The second part about how to exchange ecash tokens peer-to-peer using scriptless scripts and Brands credentials. You can find the talk on youtube and the slides here. Thanks to kanzure there’s also a transcript of the talk.

EDIT: I’ve added a note about the security of Blind Schnorr signatures against forgery to the slides. In short, a naive implementation of the scheme is vulnerable to Wagner’s attack. An attacker can forge a signature using 65536 parallel signing sessions and O(2^32) work.

# Exploiting Low Order Generators in One-Time Ring Signatures

Last week the Monero team disclosed a major bug in CryptoNote based cryptocurrencies (reddit thread) which could be used to create “create an infinite amount of coins”. Monero itself was quietly fixed in February (release, pull request) and the since then every user syncing the blockchain from scratch validates that it was never exploited in Monero. However, it was used in CryptoNote based shitcoin ByteCoin to create about 700 million coins out of thin air.

There are already a few good explanations of the bug, for example at the Monero StackExchange and the modern crypto mailing list. This article gives additional background about the signature scheme and the properties of the curve that allowed this bug to slip in.

Apart from the value at stake, this bug is interesting because it shows the risks of breaking a specialized cryptosystems such as Ed25519 apart and apply the parts in other contexts. Ed25519 is designed for plain cryptographic signatures and the curve it is based on is used in CryptoNote to implement one-time ring signatures. In contrast to a regular signature scheme, one-time ring signatures using the curve require that part of the signature does not generate a small subgroup. Ensuring this is necessary when using curves with a cofactor. CryptoNote did not do that.

# A Problem With Monero’s RingCT

The crypto-currency Monero is about to introduce a new milestone in Blockchain technology: RingCT. This is a scheme that allows using Confidential Transactions (CT) while keeping the non-interactive coin mixing typical for Monero. CT enables hiding the transaction amounts from anyone but sender and receiver while full nodes are still able to verify that input amounts are equal to output amounts. RingCT is currently not active in Monero; it is designed to be introduced as a hard fork early January.

I am a complete outsider to Monero and especially the Monero development community, but having reviewed the CT design and implementation (in libsecp256k1) extensively during my day job, I was very interested in the design decisions underlying RingCT. Very quickly I found a red flag in the ring signature scheme called ASNL used in the range proofs. This scheme is a new contribution by the paper and indeed turned out to be exploitable such that an attacker would be able to create coins from nothing. You can find the exploit code on GitHub and a detailed explanation in this post.

While writing the exploit code and preparing this blog post I learned that an anonymous person called RandomRun reported a flaw in the security proof of ASNL, which convinced the Monero devs to publish a bugfix release that switches to Borromean signatures (good call!). As a result the upcoming hard fork will not be vulnerable to this exploit. Interestingly, the error in the security proof is exactly the flip-side of the vulnerability discussed in this post.

EDIT: The Monero community reacted to this article (see reddit) but they didn’t like its style. Also, they got the timeline of the discovery of the bug wrong.

# The 2016 Backdoored Cryptocurrency Contest Winner

Thanks to a quite a bit of luck I won this years version of the Underhanded Crypto Contest focused on crypto currencies. The submission consists of a writeup and – of course – backdoored code.

# Data-Driven De-Anonymization in Bitcoin

Slides

Abstract

We analyse the performance of several clustering algorithms in the digital peer- to-peer currency Bitcoin. Clustering in Bitcoin refers to the task of finding addresses that belongs to the same wallet as a given address. In order to assess the effectiveness of clustering strategies we exploit a vulner- ability in the implementation of Connection Bloom Filtering to capture ground truth data about 37,585 Bitcoin wallets and the addresses they own. In addition to well-known clustering techniques, we introduce two new strategies, apply them on addresses of the collected wallets and evaluate precision and recall using the ground truth. Due to the nature of the Connection Bloom Filtering vulnerability the data we collect is not without errors. We present a method to correct the performance metrics in the presence of such inaccuracies. Our results demonstrate that even modern wallet software can not protect its users properly. Even with the most basic clustering technique known as multi- input heuristic, an adversary can guess on average 68.59% addresses of a victim. We show that this metric can be further improved by combining several more sophisticated heuristics.