2024.12 Vol.1

It Could Be Anything, It Could Even Be A Boat

Generally a signature requires knowledge of the message being signed. The whole point is usually to prove, hey, the owner of this private key approves this message. But turns out there some use cases for a signer to not know the message. This generally involves some sort of semi-trusted central party which aggregates “blinded” data. The two common examples are voting and ecash. I am much more interested in the ecash.

The idea of ecash pre-dates bitcoin. It is another mixing of cryptographic patterns which creates a system similar to bitcoin, but with different trade-offs. And because it is striking a balance far from bitcoin’s, it might actually fit really well in the bitcoin ecosystem.

An ecash system involves a mint, a.k.a. a bank, and users of that mint. The mint creates (mints) a number of tokens, each having a certain value. For example, a mint could choose to create tokens with denominations 1 satoshi, 5 satoshis, and 10 satoshis. A user could come along and pay the mint in 100 satoshis in BTC (some how, maybe a lightning payment) in exchange for 100 satoshis of ecash tokens (maybe 5 10’s, 8 5’s, and 10 1’s). The obvious question here is: but why? Bitcoin has its distributed consensus property making it valuable, why would someone trade that for a mint’s ecash tokens which only have value at this mint?

While bitcoin’s distributed consensus makes its value ultra-robust, it also makes it expensive. Space on the blockchain is limited by design, so every UTXO-creating transaction is going to cost a lot. The lightning network addresses this by creating abstract channels between parties which aggregate a bunch of payments over time into just a handful of UTXOs amortizing the cost. But creating a lightning channel still requires at least one UTXO. This is cost prohibitive for some use cases. So we might start to see some tiers here. At one end is cold storage bitcoin for secure protection of wealth. In the middle you have lightning channels (and perhaps others like ARK?) which are less secure, but more cost effective. But these generally only make sense for large amounts of value. So we reach the other end of the spectrum, insecure, small one-off payments. Closer to the “cash in a wallet” analogy. Ecash.

Now what is cool about ecash mints is that a user doesn’t have to trust them with all their information. To be clear, the user does have to trust the mint to not “rug” them. The mint could accept a bunch of payments for ecash and then just walk away with the bitcoin. But what users are not giving to the mint, which is valuable in this day in age, is all the metadata of their transactions. The mint doesn’t know that Alice paid Bob 500 sats on Tuesday, it doesn’t know anything.

This is where the blind signatures come into play. It might be time to step through just how a mint mints a token, and luckily, this is more abstract algebra! Cashu is a modern ecash implementation and its protocol docs, called NUTS, are great at laying this out.

NUT00 describes the cryptographic protocol for minting.

1. The mint publishes a public key K = G^k.
2. Alice, a new user of the mint, picks a secret x and computes Y = hash_to_curve(x). If the magic function name doesn’t make it obvious, this outputs a point on the curve a.k.a. a public key.
3. Alice sends the mint B_ = Y + G^r. The underscore notations is for a “blind” variable, in this case a public key.
4. The mint sends back to Alice C_ = B_^k.
5. Alice performs a simple calculation to unblind C_ - K^r = Y^k + G^(k + r) - G(k + r) = Y^k = C.
6. The pair (x, C) is an ecash token and can be sent to other users of the mint.
7. Alice sends (x, C) to Carol and Carol verifies the token with the mint who checks that hash_to_curve(x)^k == C.

There is a whole ton of cryptography in the ecash space, look at all the other NUTs! But this seven step process in NUT00 is the crux of it. Working in reverse, one thing of note is how steps #6 and #7 show off how ecash is a “bearer token”. The token gets passed directly between users (in this case, Alice and Carol) and does not need to pass through the mint in a transaction. This is obviously different than the “public ledger” blockchain of bitcoin where the name of the game is getting the world to agree on a transaction being legit.

Step #7 shows the blockchain-y equivalent of the ecash system. A user can check-in with the mint, instead of the blockchain, if their ecash token is “real”. Because there is nothing stopping Alice from copy/pasting a bunch of (x, C)’s and sending them to different users. Effectively attempting a “double spend” attack. This is the tradeoff for the performance and privacy benefits of the ecash system, and is probably why no users should ever load up a ton of value in a mint. With that said, those privacy benefits are pretty cool and may be perfect for the average user buying some coffee.

Ok, so once a bearer token is minted, it is easy to see how it could bounce around leaving the mint none the wiser. But what is stopping a mint from still attempting to track transaction metadata? They at least know who first owns a token at minting time right? Hm, not so, time to look at steps 1 through 5.

A blind signature is used here so that a mint declares a token ID legit without ever seeing the ID itself. So it is not able to track the ID since it doesn’t know it! That blind term is the same as in a commitment scheme, but in this case there is no binding. Stepping through it to see why that isn’t necessary.

The basic pattern for a mint is to publish a public key per-denomination (e.g. 1 sat, 5 sats, 10 sats). For simplicity, let’s say this mint only has one public key and it only stamps tokens worth 1 satoshi. Step #1, the mint publishes that public key.

In step #2, Alice is literally choosing the ID for her new token. It could be anything! But there is an incentive for it to just be a big long random thing so it can’t be guessed, like a lot of things in bitcoin land. She takes this secret and “hashes it to the curve”. As it sounds, this maps arbitrary data to a point on the curve which is nice, because now we can perform some cryptographic operations on that data. One might think, how can all data be mapped to the curve? Won’t some hashes not exist on the curve by definition of the curve not being “everything”? And that is true. But it turns out due to the maths, it is not too big a deal, one just has to try a few guesses to find a legit point. A general strategy for this which is employed in Cashu is to concatenate a counter on the message before hashing. If the hash lands on a point, great! If not increment the counter and try again.

With a point found, the first operation Alice performs is blinding the data by adding G^r to it. This is the same tactic in a commitment scheme where the mint cannot find Y or G^r by just looking at the B_ output point. They are blind to the values since there are tons of combinations which could make up B_.

The mint takes the blind value and stamps it with its private key k and tosses that back to Alice. Alice does not learn anything from C_ without breaking the discrete log function to find k.

Now here is the cool algebra in step #5. Alice doesn’t know the mint’s secret k, but wants the mint’s stamp on her Y message. She needs to remove her added blinding factor without messing up the goal. After the mint stamps B_, the blinding factor part of the underlying equation is G^(r + k), add G r times and then k more times. So while Alice doesn’t know k, she does know G^k (the public key) and can add r more G’s to that! Then just subtract that from C_ to cancel out the blinding factor.

The mint has now “stamped” the ID x and can check itself in the future by mapping x to the curve and making sure the signature was made with its private key (kinda similar to the macaroons pattern).

No binding factor complexity is required in this scheme since Alice has no reason to change the ID (she will just lose money) and the mint has no ability. The goal of hiding the ID from the mint is achieved without it. The mint only needs to support a few operations: mint tokens, verify tokens, and melt (destroy) tokens. Minting and verifying has been covered. Melting is as simple as the mint writing down a token’s ID in its database. Tokens with IDs in the database will fail verification checks. This is a poor mans version to deny the double spend attack. Instead of a global blockchain it’s a single database! But dang, that is cheap. Users can perform a “swap” operation with the mint as soon as they receive ecash to protect themselves against a double spend. Swapping a token is essentially a combo of the three primitive operations: first verify, then melt, then mint a token of the same value.