Skip to content

Instantly share code, notes, and snippets.

@callebtc
Last active August 7, 2023 01:12
  • Star 12 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?

A Proof of Liabilities Scheme for Ecash Mints

Abstract: In this document, I will outline a proof-of-liabilities (PoL) scheme for ecash systems and Cashu specifically, which is a Chaumian ecash system for Bitcoin. The PoL scheme consists of three parts. First, a publicly auditable list of all issued ecash tokens in the form of mint proofs, and second, a publicly auditable list of all redeemed ecash tokens in the form of burn proofs, which are both regularly published by the mint operator. Third, a mint publicly commits to rotate its keys regularly once each epoch and allows all ecash in circulation to recycle from old epochs to the newest one. If clients remain vigilant and mints agree on a certain set of rules of operation which are publicly verifiable, users of a mint can detect whether a cheating mint has printed unbacked ecash during a past epoch, and, in many cases, provide public proofs of the mint engaging in this adversary behavior. Users achieve this by regularly checking the published list for inclusion of the ecash they minted or redeemed during that particular key epoch.

Introduction

While many custodial entities like exchanges have introduced proof-of-reserve (PoR) schemes in the last years to respond to criticism about the solvency of these entities, a major issue that remains unsolved is the lack of a credible PoL scheme which would be necessary in order to also ensure that the custodial entity has not promised more money to its users than they attested to in their PoR report. Ecash mints face the same issue as these traditional non ecash-based custodians. In particular, ecash mints have to solve two major problems in order to ensure that their user's funds are secure:

Protection against a fast rug

Custodial entities are the only ones that have the private keys for the Bitcoin funds that are either secured on-chain or in Lightning channels which means that a rogue custodian can take everyone's Bitcoin at any time. Every custodial system faces this problem (as the saying goes: not your keys, not your coins). Federated ecash systems like Fedimint and federated sidechains like Liquid improve on this dramatically by custodying all funds in a multisig address with a reasonable t-of-n quorum made of the guardians of a federation. These key holders also validate and advance the state of the additional ledger system like an ecash system or a sidechain with the same quorum. This approach leaves room for a subset of key holders being malicious but not being able to steal users funds. In its current form, Cashu uses Lightning for which no federated approaches exist yet and therefore relies on a single-sig custody model which makes it particularly vulnerable against these scenarios. While the majority of the funds could still be held in an on-chain multisig address to achieve similar security as a fully-federated approach in principle, in practice, this means no real improvement if we can't solve the second problem.

Protection against a slow rug

Instead of stealing everyone's funds at once, the entity (or entities) that control the mint could slowly inflate the supply by issuing unbacked ecash and thus run a fractional reserve system. This could go on for a long time without being detected as the mint could practically debase their entire balance up to a small percentage which would be needed in order to prevent users taking any notice of it. In this document, I outline a solution for this problem using a PoL scheme for ecash mints and show how it also - as a side effect - vastly improves the risk against a fast rug as well in the case of Cashu when it is combined with an auditable on-chain multisig address in which the vast majority of user's funds are held.

I will only focus on the PoL part of this problem and assume that the PoR part is already solved using conventional on-chain attestation methods.

How ecash is minted

To use Cashu, a user Alice first needs to acquire ecash tokens. For that, Alice's wallet has to do two things: First, Alice asks the mint for a Lightning invoice and pays it using any other Bitcoin Lightning wallet. Second, when the invoice is paid, Alice generates a secret x and blinds it (i.e. encrypts it) and sends it to the mint. The mint then signs this blinded secret which we call a blind signature C'. The mint then sends the blind signature back to Alice and her wallet unblinds (i.e. decrypts) it to obtain a signature C on the secret x which the mint has both never seen. The tuple (x, C) is an ecash token and can be sent around to other users as a form of untraceable money.

How ecash is burned

Whenever Alice sends a token (x, C) to another user Carol, to finalize the transaction, Carol needs to burn the token and redeem it for a token of equal value in order to prevent Alice from double-spending it. For that, Carol sends (x, C) to the mint and the mint verifies that C is indeed its signature and if it has never seen x before, adds it to a list of seen secrets, i.e., the mint burns the ecash. That way, the mint can prevent anyone from double-spending (x, C). If x was never seen before, the mint generates new ecash with the same value and sends it to Carol very similar to the way it was initially minted. The transaction is now complete.

Similarly, if Carol wants to withdraw their funds onto their Lightning wallet or make a Lightning payment to someone else, she sends the ecash to the mint and asks the mint to pay a Lightning invoice of the same value. The mint then burns the ecash as described above and pays the invoice.

It's worth noting that since ecash is burned at every transaction and at any payout onto Lightning, the lifetime of an ecash token is relatively short. That also means that both, the list of issued signatures and the list of burned tokens can grow quickly and will grow indefinitely if we don't come up with something. Luckily, there is a simple solution to this problem which is key rotation.

Keyset rotation and epochs

To solve the issue of the indefinitely growing list of spent secrets that the mint has to carry along forever, Cashu mints can rotate their keys using an incrementing derivation path for their private keys. We call the set of private keys that the mint uses to sign tokens a keyset and we call the period in which a specific keyset is used an epoch. When the mint rotates to a new keyset, an epoch ends and a new epoch begins. A Cashu mint will still accept tokens from an older epoch for a given amount of time so they can be recycled to the new epoch. One could imagine rotating epochs every month while always keeping the last 24 epochs alive until they time out.

Crucially, whenever a mint receives a token from an old epoch, it always redeems it for a token of a new epoch. That way, all tokens that ever move will always be recycled to the newest epoch and, eventually, no tokens from old epochs will be in circulation anymore. If all tokens from an epoch are fully redeemed the epoch is "cleared". If an epoch has been cleared, or, as in this example, 24 months have passed and the epoch times out, a mint can prune all seen secrets of this keyset from its database and deactivate its private keys, preventing the mint's database from growing indefinitely.

As it turns out, we can use this key rotation mechanism to construct our PoL scheme.

Mint and burn reports

image Figure. (a) Publicly released PoL reports of the mint include all mint proofs (issued blind signatures) and all burn proofs (redeemed secrets). A cheating mint would try to artificially shorten the list of mint proofs and inflate the list of burn proofs. (b) A mint's proof-of-liabilities (outstanding ecash balance) is compared to its proof-of-reserves (on-chain assets). A cheating mint would try to artificially reduce the open balance but it can't inflate its on-chain assets.

As mentioned, for an ecash mint to function, it needs to keep a list of spent secrets, which are burnt ecash tokens. For its basic functioning, it does not need to keep the list of blind signatures, which attest for minted tokens, but it will be useful for this PoL scheme. We assume that the mint periodically and publicly releases the list of blind signatures, that we call mint proofs and the list of spent secrets called burn proofs. Therefore, these lists attest to the ecash outputs and inputs of the mint respectively. We will see how these two lists must remain balanced and how users can detect, and in some cases prove, whether the mint either refused adding legitimate entries or added fake ones.

The mint regularly provides these reports for all keyset epochs, whether they are cleared or not. In our example, a mint would publish 24 reports for each keyset epoch each month. The mint signs these reports with the private keys of the keyset to ensure its authenticity. The mint also timestamps these reports on a public ledger using tools like OpenTimestamps or Mainstay to ensure that they aren't changed retroactively. The way these reports are stored, distributed, encoded, or the interval in which they should be released is not subject of this document. I can imagine that, as usual, Merkle trees will be useful for further improving on this.

When these lists are made publicly available, the entries of these two lists can be summed up and audited by anyone. In the case of an honest mint, the total amount attested for in the mint proofs will be equal to the value of all issued ecash tokens and the total amount of the burn proofs will be equal to the redeemed tokens. The difference between the two is the aggregate outstanding balance in all user wallets. The outstanding balances are the mint's liabilities to its users in the form of ecash and must be less or equal to a proof of reserves report the mint provides separately. A cheating mint has two ways of artificially reducing the outstanding balance and we will show that both attempts can be detected by its users.

Catching a cheating mint

image Figure. Users verify whether an old mint proof list was manipulated after key rotation and whether all their blind signatures are included in the report. Users also verify whether their ecash from an old epoch is worth more than the outstanding balance of that epoch.

First, a cheating mint will want to publish as few blind signatures (mint proofs) as possible in order to disinflate its liabilities. If Cashu wallets keep all blind signatures they received from the mint during that keyset epoch in their database, they can publicly prove that they obtained a blind signature from the mint that was not listed in the mint proof list. That way, a single user can call out a mint if they don't find their blind signature in the PoL reports.

If this happens, a user needs to prove that they have a valid signature from the mint: The user who contests the report provides a discrete-log equality (DLEQ) proof, which allows others to verify the signature is indeed from the mint.

It is important to note that publicly revealing the DLEQ proof removes the unlinkability of the minting and the burning of the specific ecash token and therefore the privacy of the contesting user. However, a single ecash token that was not accounted for by the mint is enough to trigger suspicion for all other users tilting the cost-benefit balance of this approach towards its favor.

However, sacrificing privacy in the context of the ecash mint is still more preferable than for an account-based system. In the worst case, the mint would be able to know which Lightning payment (peg-in) was linked to the mint and burn proof pair. Luckily, due to the sender privacy of source-based routing, a mint can not easily determine the origin of a Lightning payment. In the more common case, the mint and burn proof pair the user reveals for contesting a cheating mint are already recycled ecash tokens that are not linkable to the initial peg-in payment.

Fake burn proofs

The second way a mint could lie about its PoL report is to include fake burn proofs in its list of spent secrets. Essentially, a mint could spin up a wallet and spend unbacked ecash which it then reports in its burn proof list. That way, a mint can artificially increase the amount of allegedly redeemed ecash and shrink the outstanding balance that it reports.

In order for a user to catch the mint at artificially inflating its list of burn proofs, users can also check whether their spent secrets are included in this list. If the outstanding balance reported for a past keyset is less than the secrets a user or multiple users reveal, the mint must have added fake entries to the list. Essentially, a mint can only artificially inflate the burn proofs and remain undetected up to its best guess for ecash that was lost or forgotten by its owners. Any attempt to further inflate the list can be contested against by users who can prove that they either held or still hold ecash from this epoch that is unaccounted for. Importantly, a user can only prove that the mint is cheating, if they can provide a set of tokens whose sum is worth more than the outstanding balance that is reported. This is due to the fact that a user might simply claim that the mint didn't include their ecash although they never attempted to actually burn it.

In the most optimal case, past epochs will always fully clear and the sum of minted tokens will equal the sum of burned tokens such that the outstanding balance of that key epoch reaches zero shortly after it is rotated out of. Only in this case, a user with a token that was not accounted for in the burn proof report can immediately prove that the mint is adding fake proofs to the report, independent of the amount of the ecash used to contest the report.

In practice, however, there will always be users who only rarely use their wallet or users who lose their wallets, it is likely that epochs don't fully clear. Therefore the mint's burn proof reports of past epochs need to be carried on and updated regularly (for example every month) to account for old ecash from that epoch is redeemed for up to 24 months. In the case of an outstanding balance, either one or multiple mint users must show that their aggregate ecash is worth more than the outstanding balance of an epoch to prove that the mint is cheating. However, in practice, users who notice that the mint does not include their spend attempts in its report and may be inflating the list with fake entries will sound the alarm to other users who would then rotate to a new epoch as quickly as they can, making it even harder to cheat for the mint as the outstanding balance of an old epoch further shrinks.

Time is your friend

By rotating the keys in an agreed-upon schedule, the mint publicly commits to not add any additional fake mint proofs to their past PoL reports. Users can validate the mint proof lists once they are released and easily detect whether new entries are added or legitimate ones are removed further on. At the same time, user wallets adopt a simple policy to refuse tokens from epochs other than the most recent one. With these rules in place, rotating the keys has two main effects:

First, it introduces an "arrow of time" onto the token dynamics which is ultimately enforced by the users themselves. User wallets refuse to accept tokens from an older keyset, either from a mint or from other users. That way, we force all tokens from old epochs that ever move into the newest keyset.

Second, it forces the mint to publicly commit that it won't add any more mint proofs to its report (which can be publicly checked). At first glance, the mint would not be incentivized to do so, since mint proofs increase its liabilities and thus the open balance it reports. However, a cheating mint could still choose to add fake mint proofs to the list when the open balance shrinks too much and it risks being caught by its users. Limiting the issuance of mint proofs makes sure that the open balance of an old epoch can only shrink and never grow, which means that the risk of a cheating mint getting caught monotonically increases over time.

Therefore, rotating epochs simulates a periodic "bank run" which allows users to observe past epochs and determine whether the mint has manipulated the reports.

PoL reduces the rugpull risk in Cashu

At first glance, the two major issues of ecash, the fast-rug risk by stealing everyone's money in one big swoop, and the slow-rug risk by inflating the ecash supply, do not seem to be directly related. If the keys for the custody of on-chain Bitcoin and carrying out ecash operations are held by the same party or parties, the risk for both threats are equal. Fedimint simultaneously reduces both of these risks by relying on a federated approach in which both, the on-chain reserves in a multisig and the distributed ecash operations are handled by a federation.

The Cashu protocol in its current state is not federated and relies on a single operating mint which makes the ecash operations extremely fast, efficient to operate, and very easy to build apps on top of it. That means that it can be implemented into very lightweight applications like a simple website or potentially very large deployments that need to process a vast number of transactions per second. Additionally, the fact that Cashu solely operates on the Lightning network makes it impossible to federate the mint because funds on a Lightning channel can currently only be held by a single party.

However, one could imagine that a mint would only be able to access a small part of the reserves while the vast majority of the funds can be swapped out from Lightning onto an on-chain address. The mint would only have to keep a small percentage of its reserves as a float on Lightning to enable frictionless payments and keep the majority that moves only slowly on-chain. The percentage of the float needs to be determined according to the liquidity requirements of the mint to allow for day-to-day user withdrawals.

This would enable two things. First, it would allow an easy proof-of-reserve report using conventional on-chain attestation methods. As a note, the float kept in Lightning channel balances can not be accounted for. Second, all on-chain funds could be held in a multisig address consisting of multiple independent parties. However, without a convincing PoL scheme, the parties of the multisig who do not control the mint can not be sure that the mint is not artificially inflating the ecash supply and stealing from the reserves. Only with a PoL scheme, participants of a multisig could hold the operator of a Cashu mint accountable for inflating its ecash reserves.

It follows from the separation of custody of the on-chain reserves and the float of the mint that funds flowing from the reserves to the float should only happen at intervals similar to the key rotation epoch length at which the PoL reports are released. Only then can the guardians of the reserve be confident that the mint is not inflating the supply and is indeed asking for funds held by legitimate users. If the goal is to keep the float at a fixed percentage, the reserve guardians should either deposit to or withdraw funds from the mint once a month, depending on how the open balance relative to the target float percentage has decreased or increased during that period.

Most importantly, in this PoL scheme, a cheating mint can only artificially inflate its liabilities but not reduce them without taking the risk at being caught doing so. If the mint inflates its liabilities, guardians of the reserves will ask for a withdrawal to keep the float at a constant percentage. If it shrinks its liabilities, the mint risks being caught by its users.

A PoL scheme is the key for a trust model in which the vast majority of a mint's funds are held in a multisig address controlled by multiple independent parties while at the same time the ecash mint is operated by a single-sig entity that optimizes its operation on enabling efficient payments.

Issues and limitations of this approach

The presented scheme offers several reasons to consider it as a significant improvement for the auditability of ecash systems. However, a few problems remain that the proposal in this document does not address.

Unaccountability of Lightning funds

Since the balance held in Lightning channels can not be publicly accounted for, the float the mint keeps on Lightning must be treated as a margin of error in the balance between the PoR and PoL reports. If the float is kept small, say at 1% of the overall reserves, this should be a manageable risk the guardians of the reserves can deal with. Importantly, a mint operator can always run away with the entire balance on Lightning. An ecash mint operation of significant size should therefore have mechanisms in place to ensure that the guardians of the reserves have some form of oversight over the financial activities of the mint operator. Related to this, guardians of the reserves must make sure that the mint operator regularly swaps out to their on-chain address and that the float's percentage remains constant over time.

Unprovable theft or censorship

While the scheme presented here protects users from an undetectable inflation of the ecash supply by the mint, it does not protect users against other kinds of theft or censorship a mint might engage in. In particular, a mint could include burn proofs of their users in their report but never honor them, for example, by refusing to pay out their funds on Lightning. Users have no way to publicly prove that the mint refused to honor its promise since regular Lightning payments can't be enforced or be publicly proven. This is comparable to a case when a regular bank or exchange would refuse to pay out the funds of one of their customers when they request a withdrawal but still deduct the funds from their balance. One possibility to account for this in an ecash system might be via the use of fraud proofs. Here, the mint signs a commitment to a transaction they will carry out for the user once their ecash is redeemed. Users can then publicly release a challenge to which the mint has to respond to proving they carried out the intended transaction.

To the extend that a mint steals from its users or censors their transactions, it also increases its ability to silently print unbacked ecash since the censored payments are entries that are potentially missing from its reports. However, I do not think that a mint can go on like this forever without remaining undetected. The mint has at least two ways of censoring ecash transactions: it could refuse to honor a note with a specific secret, similar to when a bank would refuse to accept a cash note with a specific serial number. In this case, a censored user could publicly demonstrate that the mint does not honor their claim. Another possibility is that the mint refuses to honor notes randomly such that it becomes harder to publicly demonstrate censorship. In either case, although it is not always possible to publicly prove that the mint is trying to cheat, it is detectable up to a certain degree by individual users who can then either choose to withdraw all their funds from the mint and raise public awareness about the incident.

Resource limitations and scaling

The presented PoL scheme relies on users being able to download the PoL report to check whether their mint proofs and their burn proofs were included. Depending on the volume of the ecash mint and the frequency with which it releases the reports, this might become a burden in terms of internet traffic and other technical resources for some end users. A pair of mint proof and burn proof has roughly a footprint on the order of 100 bytes. That means that a report of 1 MB can account for 10,000 ecash transactions. As mentioned in the beginning of this document, the frequency which which these reports should be published and in which form they should be encoded is not further elaborated here. However, since the particular ordering of entries does not matter for the PoL scheme, one could potentially merkelize the reports and use variants of Merkle proofs to allow wallets to conduct a more efficient audit of the mint's liabilities.

This scheme does not provide perfect accountability

It is critical to stress that the presented PoL scheme does not free users from all trust they have to place onto the mint operators and the guardians of the reserves. As we have seen, user funds are still in control of external parties and can be stolen by the mint (the float on Lightning) or a set of colluding guardians (the entire reserves). Furthermore, there are several issues such as theft or censorship that can only be detected by an individual user but can't easily be proven publicly to the rest of the world. It is important to keep in mind that these problems exist and not pretend that the presented scheme solves all these issues at once. However, the presented PoL scheme protects users specifically from an otherwise uncontrollable and undetectable inflation of the mint's ecash reserves within a certain margin as I outlined in this document as transparently as I could.

Summary

To summarize, for a proof-of-liabilities scheme for ecash to work, users and operators of a mint must agree on the following.

Mints must:

  • Rotate into a new keyset epoch at an publicly announced and agreed-upon time (for example every month or every n Bitcoin blocks).
  • Accept ecash from old keyset epochs for an extended period of time (for example 24 months).
  • Recycle all tokens it encounters from old epochs for tokens from the newest one.
  • Release signed reports on the mint proofs and burn proofs for each keyset and timestamp them on a public ledger such as the Bitcoin blockchain.
  • Regularly provide a proof-of-reserve report that is equal or greater than the outstanding balance in the proof-of-liabilities reports.

Wallets must:

  • Accept only ecash from the most recent keyset epoch from other users or the mint.
  • When a new epoch begins, recycle ecash from old epochs to the newest one using self-payments.
  • Check whether its minted tokens (blind signatures) are accounted for in past mint proof reports of the mint.
  • Regularly verify that past mint proof reports are not further manipulated.
  • Regularly check whether its burned tokens (spent secrets) are accounted for in the past burn proof reports of the mint.
  • If a blind signature is not accounted for in the mint proof report of the mint, the user can immediately prove that the mint is cheating. The user of the wallet is warned that something fishy is going on and that they should remove their funds from the mint immediately and ring the alarm bell.
  • If an old keyset report is cleared, i.e. there are reportedly no outstanding balances anymore, but the mint did not include a spent secret of the wallet, the user can prove that the mint added fake entries to its report and immediately ring the alarm bell.
  • If an old keyset report is not cleared, i.e. there is still an outstanding balance, and a spent secret of a wallet is not accounted for in the burn proof report of the mint, the user knows that something fishy is going on and can withdraw their funds immediately. If the user has a balance larger than the outstanding balance, they can prove immediately that the mint added fake entries and ring the alarm bell. If the balance is smaller, only when multiple users come together and prove that the aggregate of their balances is larger than the outstanding balance of the report, they can prove that the mint has added fake entries to this list.

Acknowledgements

Thank you to Shinobi for providing valuable input along the path of spelling out this idea. Thank you Moonsettler for thinking deeply about this problem and pointing out that the finitude of keyset epochs is the missing piece for making this scheme work. Thank you to Ruben Somsen for pointing out issues in this design that relate to unprovable theft by the mint. Thank you to all reviewers for suggesting improvements of some of the ideas presented here. Thank you to Phyro for sharing your work freely with the world and accompanying the Cashu development efforts along its path.

If you, dear reader, have found an issue with this scheme or can think of improvements, please get in touch with us.

@pippellia-btc
Copy link

Hi all.

First things first, I think the Proof of Reserve on the first picture refers to epoch 2462, not 2642.

As I said on Twitter, I think the proposal is very good and solid imo, but I would change the wording a bit here and there:

a) I would not use the terms " Mint Proof" and "Burn Proof" because they are confusing, but rather "Mint List" and "Burn List". They are not proofs and can be faked by the Mint, BUT the Mint can be caught in doing so.

For example, the Mint can massively inflate the supply of ecash, but cannot do so WITHOUT getting caught.

b) I have another wording suggestion, but first I need to check if my understanding is correct or not.
Let it be:

Mn = E-cash minted at epoch n
Bn = E-cash burned at epoch n

N = the number of epochs
PoR = Proof of Reserve at epoch n

The mint must maintain

$$\sum_{n=1}^N Mn-Bn \leq PoR$$

The Mint can try to inflate Bn, but it must be careful. If a set of users can collectively show that they held more than $$Mn-Bn$$ from epoch n, then they can prove that the Mint added fake burns to the burn list.
This gives another constraint on the Mint

$$ Cn \leq Mn - Bn \ \ \ \forall n \leq N$$

where Cn = "maximum amount of ecash (from epoch n) that a set of users can prove to have held".

Cn is probably never known in practice, but obviously exists.

This implies that

$$ \sum_{n=1}^N Cn \leq \sum_{n=1}^N Mn-Bn \leq PoR$$

This explains why I initially suggested Range Proof of Liability as the name of the scheme (rPol)
Perhaps another option is Bounded Liability Scheme.

I would not use the word "proof" alone since it gives a false sense of security, because the exact value of the outstanding balance cannot be verified. What can be verified is that this amount is within a range.

Did I get something wrong?

@callebtc
Copy link
Author

First things first, I think the Proof of Reserve on the first picture refers to epoch 2462, not 2642.

Thank you for this, I fixed the image!

As I said on Twitter, I think the proposal is very good and solid imo, but I would change the wording a bit here and there:

a) I would not use the terms " Mint Proof" and "Burn Proof" because they are confusing, but rather "Mint List" and "Burn List". They are not proofs and can be faked by the Mint, BUT the Mint can be caught in doing so.

That's true, the entries in these lists do not proof anything about the list itself but these objects are called proofs in the context of ecash transactions. They are a proof that the mint has given a blind signature on a blinded message.

This explains why I initially suggested Range Proof of Liability as the name of the scheme (rPol) Perhaps another option is Bounded Liability Scheme.

IMO, calling it a range proof would cause even more confusion because the term "range proof" is reserved for a set of cryptographic proofs which the one presented here is not one of.

I would not use the word "proof" alone since it gives a false sense of security, because the exact value of the outstanding balance cannot be verified. What can be verified is that this amount is within a range.

I'm not sure if the name really matters that much. "Proof of Liabililties" is an established term. Even if this scheme can only convince you that the liabilities are in a range, the name still fits because it achieves what a PoL should achieve. PoL is not a mathematical term. Range proof is though.

Did I get something wrong?

I think you've got everything right! Thank you for taking a look and carefully reading the document. Happy to hear you think it's useful.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment