On Chaumain Mints and their Applicability to Bitcoin

[casey]

Chaumian mints have some very interesting properties, namely privacy, scaling, and usability, which are complementary to bitcoin.

I think there are lots of interesting problems there, such as how to federate a mint, how to interoperate with bitcoin, and how to make a good, usable, bitcoin-based Chaumian mint wallet.

I just finished a post on the topic. @elsirion has some information at fedimint.org, in addition to actually being at work on an implementation.

This is very broad topic, unlike the other, more specific, problems in this repository. However, there's lots of interesting sub-problems, and it seems valuable enough for Bitcoin that I wanted to create an issue.

[LLFourn]

This is a great research topic to me. It amounts to asking what is the ideal Bitcoin custodian (if all legal considerations were ignored). I think the federation of the ownership of the coins is not too interesting a subject (the answer is threshold signatures) but is certainly part of it. The main question is what is the state of the art WRT to chaumian banks and how can it be applied to Bitcoin.

I see the main problem description as describing what we want from an ideal system:

• deposit/withdraw via on-chain or lightning
• anonymously merge/split coins (can we do it non-interactively?).
• recover coins from seed words -- blockchain chaumian cash systems like ZCash this can't be done for shielded addresses You have to backup state somewhere. Since you have a trusted federation they naturally can be used to store anonymous encrypted backups of your cash.
• Use cash for services provided by the custodian (maybe they are an exchange or lending platform).
• Can naturally be used a a coin mixing service.

@casey, @elsirion are you happy with this framing of the topic? If so I think thing to do is to collect resources to flesh it out a bit.

[elsirion]

That all sounds interesting, although my focus is a bit different. For me some big remaining questions are:

Lightning integration

Building a federated LN node is hard and the the resulting node would most likely be slow due to the BFT consensus needed.

So another option is to have most collateral as plain old multisig on-chain and some service provider that is centralized, but can prove to the federation that it paid an invoice for them which leads to a payout afterwards. A similar scheme can be built for receiving via LN invoices, here the service provider needs a bond as security and users would claim the received money using a ricardian contract (requires preimage/some other secret for PTLCs from sender).

There are many subtleties when it comes to this protocol, so that will be a major focus for me.

Blinded amount tokens

Currently I use plain old blind signatures on nonces. The key determines the denomination and there are amount tiers to make transactions smaller. This obviously decreases the anonymity set. One interesting idea is to instead use blind signatures on a nonce and a blinded amount (+ range proof). This would allow one big anonymity set of coins and potentially smaller transactions. But it's unclear if this would all in all actually be more efficient as I'm not aware of any cryptographic protocol that would allow the necessary proofs over blind amounts/amount sums of items inside the blinded message. Super interesting if anyone wants to go that way, but to far out there for me right now, I want to have a working implementation relatively soon.

Backups

Unlike blockchain based systems there is no easy stateless recovery mechanism like BIP32. You point out some interesting ways to solve the problem. I think the "pay the mint to store some encrypted data" approach is the easiest that I'll go with, but there are some considerations re privacy to keep in mind (does the backup leak anything etc.).

BFT consensus

How low can we get the consensus round length (in seconds) while using an anonymous communication network like Tor or Nym. There are some interesting hybrid consensus algorithms like the bolt-dumbo transformer (synchronous by default, async if timeout is hit).

The latency is important for UX. For the payer the latency is 1 consensus round plus the time lightning takes for routing. This should ideally be only a few seconds.

Payment interactivity and change

I think "anonymously merge/split coins (can we do it non-interactively?)." is out of scope a bit, at least I can't even imagine how to go about that. Returning change seems simpler tbh since avoiding double spends naively requires interactivity anyway and the alternative approach of leaking the payees identity and using e.g. bonds as insurance is messy.

Use cases

As you noted federated mints could be used for mixing. But not only that, as you might not trust them with large amounts. Instead they could be integrated into mixing protocols to recycle toxic change. Instead of one toxic change output per input multiple are combined and sent to the mint in a pay to contract way that states which pub key may redeem how much of the deposited funds as tokens. Users can then accumulate their toxic change there till paying out a round amount makes sense again.

I'm currently working on a prototype and did some research on threshold blind signatures (a key building block) the last few months. With that nearing its end I'll go on to writing a complete system overview of such a federated mint. I'll try to share some of my insights along the way. Probably mostly on fedimint.org.

[elsirion]

Thinking about how all this fits into bitcoin-problems I guess the most straight forward research question is "how to build blinded amount tokens". All the other aspects seem more engineering problems. Federated lightning might also profit from a thorough examination (is it really just building everything with threshold sigs? What needs to be changed on the protocol level to make it work best?).

[LLFourn]

Thanks @elsirion that information is really useful. I agree with you that the only clear cut research topic is the blinded amounts problem. I also agree that it would be very hard to do splitting and merging coins non-interactively. The blinded amounts is also relevant to the tumbler problem.

So perhaps we'll start with the blinded amounts problem as its own problem page first. It sounds like the problems related to the federation are mostly about choosing a BFT consensus alogirthm at this point.

[nothingmuch]

Blinded amount tokens

Currently I use plain old blind signatures on nonces. The key determines the denomination and there are amount tiers to make transactions smaller. This obviously decreases the anonymity set. One interesting idea is to instead use blind signatures on a nonce and a blinded amount (+ range proof). This would allow one big anonymity set of coins and potentially smaller transactions. But it's unclear if this would all in all actually be more efficient as I'm not aware of any cryptographic protocol that would allow the necessary proofs over blind amounts/amount sums of items inside the blinded message. Super interesting if anyone wants to go that way, but to far out there for me right now, I want to have a working implementation relatively soon.

FWIW this is more or less solved, depending on the specific instantiation.

In general an anonymous credential scheme can be used to instantiate a token with homomorphic amount commitments, by proving properties of the homomorphic amount commitments in zero knowledge at issuance time.

Anonymous credentials are analogous to blind signatures, in that they can be issued without revealing the message to the issuer/signer. However, the analogue of the message is structured, usually a vector of so called "attributes", which can be field or group elements (depending on the scheme). As part of this blinded issuance, properties of the attributes may be proven in zero knowledge.

With some variations, instead of simply sending the credential verbatim possession of the credential is proven in zero knowledge, along with a selective disclosure of some/all of the attributes. If this can be done repeatedly without individual presentations being linkable by the verifier, this is called "unlinkable multi show". If that is the case, disclosure of a nullifier/serial number is required on presentation to prevent double spending.

In a token scheme verifying a credential presentation where the serial number is unused is like confirming a transaction is unspent. With a homomorphic amount commitment (which can, or in some cases must be re-randomized) authenticated as part of a given show protocol, properties about the balance of multiple such commitments can be proven much like with Confidential Transactions, independently of the specific credential scheme.

More generally rebalancing/conversion operations with multiple credentials of possibly mixed types/credential schemes can be supported. In such a protocol multiple credentials are presented, and multiple new ones requested as replacements, such that the commitments all cancel out. To ensure that the amounts actually are balanced, range proofs must be provided for the amount attribute as part of the credential request. Pedersen commitments with incompatible generators can also be accommodated using generalized DLEP proofs for ones that can be summed together in a balance proof.

Any cleartext amounts, perhaps corresponding to fees, payments, or exchanges against blind signatures or something like privacy pass tokens representing a fixed denomination can also be taken account by tweaking the sum value, and proving that this tweaked sum is a commitment to 0 as part of the combined operation. I think it should be possible to include otVES/adapter signatures in the presentation to do interesting things relating to UTXOs/channel commitments, but I haven't worked out anything in detail.

Depending on how the credential is issued, different trust models or verification models are permitted, KVACs (as in Danake & WabiSabi) are more efficient, but can only be verified by the issuer since verification requires a secret key.

Some more details about concrete schemes from my mailing list response, reformatted with links for convenience here.

Alternative credential schemes can be applied in a similar way, with
fairly minor differences in how attribute commitments are handled
(e.g. in the balance proofs)

• The ACL scheme is publicly verifiable, but still relies on a
  single issuer. see this paper for a wallet based on thereof, as well as the
  cited works for some variations which rely on more general zero
  knowledge proofs.
• The Coconut scheme provides threshold issuance. I have not
  studied this scheme in detail, but IIRC it only supports scalar
  attributes (as opposed the KVACs used in WabiSabi, which also support
  group elements. See also Danake which relies on scalar attributes
  only and uses epoch schemes.

Note that not all schemes have security proofs using standard assumptions, for instance both KVAC schemes I'm aware of build on algebraic MACs which have a satisfying proof of security but only in the generic group model, or alternatively a proof of security under more standard assumptions (DDH) but only for a weaker notion of unforegeability, against a non-adaptive adversary. Both these and ACL can be instantiated using an Abelian group of prime order, like secp256k1, and only require sigma protocols for the zero knowledge proofs.

In addition to these schemes I mentioned above, there is some interesting work utilizing pairing based cryptography. If i'm not mistaken, Brands credentials, the first realization of the anonymous credential concept, can also be used.

Thanks @elsirion that information is really useful. I agree with you that the only clear cut research topic is the blinded amounts problem. I also agree that it would be very hard to do splitting and merging coins non-interactively.

More broadly there are also schemes for delegatable anonymous credentials, and unrelated to anonymous credentials, offline/divisible e-cash (also pairing based). Continuing the analogy to signatures, these are like linkable ring signatures. In this setting the issuer must be able to address double spending after the fact, based on the revealed identify of the double spender. If this trust model is acceptable, payments can be verified p2p in an offline setting, so there are interesting tradeoffs to consider.

Edit to update: Since posting that I learned that the ACL scheme is also affected by the ROS attacks on blind Schnorr signatures

[LLFourn]

@nothingmuch thanks very much for this write up. It made me confident that this is possible. The way I see it a problem page could be set up to find a combination of schemes that achieve a chaumian mint with this functionality:

1. Deposit - exchange real coins for credential by transferring to bank. The received coins must be unlikable to the deposit.
2. Transaction - destroy a set of input coins and create a set of output coins with the same total value. The output coins must be unlinkable to the input coins and each other.
3. Withdraw - destroy a coin and get real coins in exchange. The destroyed coin must be unlinkable (ignoring value) to any transaction or deposit.

I think there are a few places you could start designing this functionality but I think the full design is an open question? Or would you consider this is "solved"?

How to make it a federation is also interesting.

If i'm not mistaken, Brands credentials, the first realization of the anonymous credential concept, can also be used.

IIRC "brands" credential scheme is broken [1].

[1] https://eprint.iacr.org/2012/298.pdf

[nothingmuch]

I think there are a few places you could start designing this functionality but I think the full design is an open question? Or would you consider this is "solved"?

To me this all reduces to a single generic exchange operation. Depending on what is being exchanged, this might need phasing/backout/refunds or it could be atomic, but abstractly it is the same. This can represent the interests of one party or many.

For example, consolidating two anon credential tokens would be a 1:1 conversion of a single unit and can be fully atomic, present and request credentials in one go. A deposit or withdrawal links the issuance or spend of such tokens to BTC.

If multiple units with conversions more complex than 1:1 conversion are needed, conceptually it can still be thought of as 1:1 where the "before" and "after" are like normal vectors, and the exchange rate between different units is a basis vector, and the magnitude is an invariant.

So basically I think various centralized providers, consensus systems etc could support different kinds of units (on chain BTC, virtual UTXOs/outputs of state commitments, non-BTC units which are pegged to BTC like L-BTC or chaumian e-bank tokens, and of course shitcoins, utility coins, access tokens, anything at all really) in a pluggable way by declaring what kinds of units they support (e.g. a chaumian e-bank that supports lightning deposits by exchanging a payment with a token issuance). Depending on the nature of the finality system, and the underlying units, either an atomic exchange, or a prepare-commit exchange, or both may be supported.

Two or more parties (in the simplest case a client and server) who can all agree on a threat model for atomicity/backout guraantees, and compatibility between the different unit types they are interested should in principle be compatible, but initially it seems to me that a few specialized such protocols would be much easier to start with.

So, I would say very far from solved in practice, but solved in theory, and in a way that gives confidence that the practical side could be approached incrementally.

IIRC "brands" credential scheme is broken [1].

[1] https://eprint.iacr.org/2012/298.pdf

Not broken per se afaik, but not only is there no security proof, there are impossibility results for a security proof, and it doesn't support unlinkable multi-show which makes it more cumbersome for most of the things anonymous credentials are useful for (not so much of a problem for e-cash; unlinkable multi-show actually requires the introduction of a double spend mechanism, but this is straightforward).

(edited because i trailed off mid sentence, and point out that unlinkable multi-show is actually

[LLFourn]

Ok so I think the the situation is that there's an open question about how this can be instantiated and what are the local optimums of design. A problem page would be helpful for anyone looking to try and build such a thing and a useful place to keep resources as the state of the art develops.

[LLFourn]

Another interesting idea from @RubenSomsen is if the mint can publish coin related data publicly so a user could trawl through all the existing coins and see if they own them. i.e. just from seed words restore coins. If the mint could reveal these coin "commitments" without revealing anything useful to any attacker that would be awesome!

[elsirion]

That's a cool idea! I had a similar idea in a discussions about backupability some time ago but was thinking about querying the mint for specific coins to see if they are spent or not (trading losing coins against losing privacy), but indeed if you "broadcast" the entire log you don't have to give up either (feasibility depends on mint size I guess).

I believe that it doesn't make a difference if only the mint knows the issued list and spent list or everyone. Privacy has to hold even against the mint itself, so a passive mint observer is a strictly weaker adversary.

If you can derive both nonces and blinding keys from a seed and all (blind_nonce, blind_sig) pairs and the list of spent nonces is public you should be able to fully recover your funds just from the seed. First derive all nonces and blind_nonces up to the point where you can't find them in the issued list anymore. Then you can check which of these are already spent and reconstruct the coins using the blind_signatures for the remaining ones.

[callebtc]

Another interesting idea from @RubenSomsen is if the mint can publish coin related data publicly so a user could trawl through all the existing coins and see if they own them. i.e. just from seed words restore coins. If the mint could reveal these coin "commitments" without revealing anything useful to any attacker that would be awesome!

Nice, we're doing just that in Cashu!