Taproot And FROST Improve Bitcoin Privacy – Bitcoin Magazine
This is an opinion editorial by Dan Gould and Nick Farrow. Gould is a developer who worked on TumbleBit, PayJoin and Chaincase App and has been sponsored by the Human Rights Foundation and Geyser Grants. Farrow is an Australian Bitcoin engineer best known for his open source payment processor SatSale.
“Hey, I just got an invite to this hackathon in Malaysia,” Evan Lin said, interrupting my flow over the laptop in the Taipei Hackerspace. “That sounds magical,” I said back. “Can I come?”
I had been banging my head on the desk for weeks. Lin had torn apart my idea of what bitcoin privacy was. “It’s a private event, not your typical hackathon. I can ask.”
One flight, two weeks and six minutes of voicemail logistics later, we walked down the streets of Kuala Lumpur, Malaysia with Lloyd Fournier, pondering a shared passion to make bitcoin’s privacy stick. Now we were a team. We set out to upgrade Fedimint using semi-polished cryptography, some jotted down notes, and then demo it at the first ever Malaysian BitDevs Meetup five days later.
Fournier had joined Nick Farrow to develop FROST, a new threshold cryptography exploiting Taproot, in the months before. As a source of human resources for Bitcoin, Fournier had also worked closely with Lin who is a Bitcoin Dev Kit (BDK) contributor. He and I had spent the past few weeks upgrading PayJoin privacy under fluorescent lights in the wee hours of Taipei, Taiwan, so we had established the confidence to jump into the deep end of a project together. Fournier’s invitation was a step to the edge. To demonstrate cutting-edge cryptography to the world, we had to put FROST in an app. Fedimint had everyone’s eyes on its new threshold escrow model. It was suitable for the search.
Self-storage is a new, scary concept for most people. So many people store bitcoin in third-party custody on exchanges, leaving them vulnerable to censorship and indecent surveillance. Federated mints offer a third way: A federation of known custodians keeps the community’s funds safe. So how does it work?
Anyone can send bitcoin to a Fedimint in exchange for electronic cash. Guardians share custody of the community’s bitcoin in a multi-signature wallet. E-cash tokens are just some data: blind signatures that can be redeemed for a certain amount of bitcoin later. They are super powerful notes. Submit a Lightning invoice and your e-cash to “unplug”. You can get e-cash in a text and have the federation reissue signatures so no one else can take it. The signatures are blinded, so that they can be redeemed in total anonymity. Anyone can send e-cash to a Fedimint to get bitcoin.
To share custody between guardians, Fedimint uses legacy Bitcoin Script-based multi-signature addresses. A threshold number of guardians sign to transfer funds. These funds are easy to spot on the blockchain since Script multisig writes the number of signatories and the total number of guardians to the blockchain for all to see. Although E-cash is anonymous, monitoring companies can identify connections, connections and pooling of community funds. Leveraging Bitcoin’s latest upgrade, Taproot, our team solved this privacy issue by switching Script multisig to FROST.
Enter FROST
FROST (Flexible Round Optimized Schnorr Threshold) is a powerful new type of multisig that aggregates key shares of federation members into a common FROST key. To use under this key, a threshold number of members must each produce a signature share. The shares are then combined to form a single signature valid under the common FROST key. Members coordinate outside the chain. FROST transactions are indistinguishable from regular single-party taproot spending, thus stopping the sinister monitoring. In addition, FROST allows flexible federations, allowing new guardians to join without coordinating each member of the federation to generate new keys again.
Our first step was to understand how the union reached a consensus each signing round. Fedimint’s consensus algorithm can tolerate bad behavior for up to a third of the federation and still reach consensus. It took one day on the whiteboard to decode the consensus algorithm and another to configure the initial FROST key generation.
Arriving at Fedimint consensus (image provided by authors)
We cheated key generation by doing everything in a single trusted device’s memory. In best practice, a two-round ceremony retains a person’s secret shares of the common FROST key that exists only on that person’s device. The ultimate secret is never reconstructed.
Coming to consensus (signatures)
We tested a link transaction before changing Fedimint wallet code and got confused. Due to a limitation of blind signatures, Fedimint E-cash tokens (similar to CoinJoin outputs), are limited to preset denominations, so each E-cash token transfer has an anonymity set. Waited and waited and waited, Lin laughed that we must have messed something up.
It turned out that the standard banknote denominations we set required the coin to generate around 300,000 signatures to issue enough e-cash to cover the connected amount. There are suggestions to fix this by using anonymous credentials instead. We reset the coin to use much higher default denominations since we just tested. Hackathons are, after all, for hackers.
In a stroke of luck, Bitcoiner Malaysia had just formed and was ready for their first event. Between the four of us hackers, a number of the largest Chinese bitcoin podcast and scholars on their way to earning the first Bitcoin Ph.D. in Malaysia we planned to show our proof of work at BitDevs at the end of the week.
Our most difficult task lay ahead: federated signatures. To produce a FROST stake, signers must agree to shared randomness, called nonces. In the case of Fedimint, signers use consensus to agree on a unique nonce for each federation member that joins a signing session. Then, signing participants pool shares into a full signature.
While preparing our live demo for the meet, we managed to get some nonce sharing semi-working and fixed some fee bugs as well. Despite our hard work, dinner rolled around before our code worked. We crossed the threshold into deepest hackathon territory huddled around the triple-pair programming TV in Farrow’s hotel room.
An unreal experience
With our tap water ready and the Unreal Tournament soundbar cranked up, Fournier sat at the keyboard, while we tossed out bug fixes, variable names, and commands from the back seat. 1:30am rolled around and our eyelids were heavy. A few taps later, just like magic, the disconnection worked. Each signer will receive signature shares from the others and redeem anon’s e-cash in exchange for bitcoin. “Flawless Victory” rang out from the soundboard. We cheered in disbelief.
Except it didn’t work. The next day we ran the code and saw problems right away. We were just lucky the night before. It only worked once out of three or four tries. We combed through hackathon-quality code for hours. Well after lunch we were still worried about cramming in another late night. To our benefit, we found the problem: a classic indexing error. At 17:00 FROSTimint was ready to present.
When we circled up for BitDevs, the locals took a self-described “support group” format for introductions. Fournier brought us back to reality with the technical. The first meeting discussed the future and weaknesses of guardians with joy. How would we choose guardians? Can they hold partial reserves? Most importantly, how can my laksa noodle soup shop outperform fiat using Fedimint?
This is a guest post by Dan Gould and Nick Farrow. Opinions expressed are entirely their own and do not necessarily reflect the opinions of BTC Inc. or Bitcoin Magazine.
