# STARKs: Paving the way to more trustlessness for Cashu?

## Introduction

The Cashu protocol, a Chaumian ecash system for Bitcoin, aims to provide privacy guarantees akin to physical cash. However, its current implementation heavily relies on trust in the mint (custodian), raising significant security concerns. In this analysis, we explore the potential integration of STARK (Scalable Transparent ARguments of Knowledge) proofs and a Proof of Liabilities (PoL) scheme to mitigate these issues and bolster the overall security model of the Cashu protocol.

The proposed PoL scheme is heavily based on the work of [Calle](https://x.com/callebtc), as detailed in his document [A Proof of Liabilities Scheme for Ecash Mints](https://gist.github.com/callebtc/ed5228d1d8cbaade0104db5d1cf63939). My goal is to synthesize these ideas with STARK proofs to enhance the protocol's security and transparency.

Before delving into the proposed improvements, let's review briefly the current Cashu protocol and its limitations.

## Shout-outs

Huge thanks to [Calle](https://x.com/callebtc) and Maya Dotan for their invaluable input and thought-provoking discussions on this topic. You folks rock!

## Cashu Protocol: The TL;DR Version

### Key players

- Users: Senders (e.g., Alice) and receivers (e.g., Carol)
- Mint (server): Bob
- Elliptic curve cryptography with generator point G
- Blind Diffie-Hellman key exchange (BDHKE)

### Protocol Flow

1. Minting tokens:
- User requests a Lightning invoice from the mint and pays it
- User generates a secret 'x', blinds it, and sends it to the mint
- Mint signs the blinded secret and returns the blind signature
- User unblinds the signature to obtain the ecash token (x, C)

2. Swapping tokens:
- Used to split tokens or replace received tokens with new ones

3. Spending tokens (melting):
- Receiver sends the token (x, C) to the mint for verification
- Mint verifies the signature and checks if 'x' has been seen before
- If valid, mint burns the token and executes the payment over Lightning

### The not-so-great parts

Now, don't get me wrong – Cashu is extremely cool, but it's not without its challenges:

1. **High trust requirements**: The mint, as a custodial service, could potentially censor transactions or even steal all assets.
2. **Lack of transparency**: There's no visibility into the mint's reserves or its ability to honor all liabilities.
3. **Limited offline protection**: The protocol offers minimal safeguards against double-spending for offline users.

But fear not! We're about to explore how STARKs and a Proof of Liabilities scheme might just save the day.

## STARK Proofs: A Primer

Before we dive into the good stuff, let's break down what STARK proofs are and why they're perfect for our Cashu makeover.

[STARKs (Scalable Transparent ARguments of Knowledge)](https://eprint.iacr.org/2018/046.pdf) are a class of zero-knowledge proofs with several desirable properties:

1. **Scalability**: Proving time is quasi-linear and verification time is poly-logarithmic with respect to the computation size.
2. **Transparency**: No trusted setup is required, eliminating a potential point of failure.
3. **Post-quantum security**: STARKs are resistant to attacks by quantum computers.
4. **Succinctness**: Proofs are relatively small and quick to verify.

They allow a prover (in our case, the mint) to convince a verifier (users or the Bitcoin network) of the correctness of a computation without revealing the inputs or intermediate steps.

## Proof of Liabilities Scheme for Cashu

One way to mitigate the risks of Mint acting maliciously would be to implement the [Proof of Liabilities Scheme proposed](https://gist.github.com/callebtc/ed5228d1d8cbaade0104db5d1cf63939) by Calle.
This scheme addresses the critical issue of preventing mints from inflating the ecash supply undetectably and would improve visibility on whether or not the Mint is capable of paying off all valid withdrawals.

### Key Components of the PoL Scheme

1. Mint and Burn Reports: The mint regularly publishes two types of reports:
- Mint proofs: A list of all issued ecash tokens (blind signatures)
- Burn proofs: A list of all redeemed ecash tokens (spent secrets)

2. Keyset Rotation and Epochs: The mint rotates its keys periodically, creating distinct epochs. This allows for:
- Pruning of old data to prevent indefinite growth of the spent secrets list
- Creation of an "arrow of time" in token dynamics
- Forcing public commitment from the mint regarding past epochs

3. User Verification: Users actively participate in verifying the integrity of the mint by:
- Checking for inclusion of their minted and burned tokens in the reports
- Verifying that past reports are not manipulated

### Detecting Cheating Mints

1. `Mint trying to sweep things under the rug?`: Users can prove the mint's dishonesty by providing a valid signature not included in the report.
2. `Mint inflating the burn list?`: Users can contest if their unspent tokens exceed the reported outstanding balance for an epoch.

### Benefits of the PoL Scheme

1. Prevents undetectable inflation of ecash supply
2. Introduces periodic "simulated bank runs" through epoch rotations
3. Allows for effective multisig custody of reserves while maintaining efficient single-sig mint operations
4. Enhances overall transparency and accountability of the mint

## STARKs and PoL: A match made in math heaven

We could combine the STARK proofs with the PoL scheme to provide additional security guarantees and efficiency improvements:

### STARK-powered mint and burn reports

1. **Generate STARK proofs:** The mint generates STARK proofs attesting to the correctness of mint and burn reports.

2. **Publish proofs:** These proofs are included in the published reports.

3. **Efficient verification:** Users can efficiently verify the integrity of the reports without needing to download all the data.

### Efficient User Verification

1. **Succinct data inclusion:** STARK proofs enable succinct representations of data inclusion.

2. **Privacy-preserving checks:** Users can verify their token's inclusion without revealing which specific tokens they own.

### Enhanced Epoch Transition Verification

1. **Verify epoch transitions:** Generate STARK proofs to confirm the correct transition between epochs.

2. **Account for valid tokens:** Ensure that all valid tokens from prevous epochs are correctly carried over to the new epoch.

## The Bitcoin STARK Saga: When pigs (or cats) fly?

Okay, now we're entering the realm of wild speculation. What if we could verify these STARK proofs right on Bitcoin itself? Mind. Blown.

This crazy scenario would need something like a soft fork to bring back the `OP_CAT` opcode from the dead.

### OP_CAT and STARK Verification

The `OP_CAT` opcode concatenates two elements on the stack. When combined with other Bitcoin script opcodes, it enables the construction of a STARK verifier directly in Bitcoin script. We have successfully [implemented](https://github.com/Bitcoin-Wildlife-Sanctuary/bitcoin-circle-stark) and [demonstrated a STARK proof verification on a Bitcoin signet](https://x.com/StarkWareLtd/status/1813929304209723700) with `OP_CAT` enabled, showing the feasibility of verifying STARK proofs directly on Bitcoin.

### Building a STARK Verifier on Bitcoin

To make this STARK verifier on Bitcoin, we need a few key ingredients:

1. Field arithmetic operations
2. Polynomial evaluation
3. Merkle tree verification
4. FRI (Fast Reed-Solomon IOP of Proximity) protocol

Surprisingly enough, with `OP_CAT` enabled, these components can be efficiently implemented in Bitcoin script, allowing for on-chain verification of STARK proofs.

However, having a STARK verifier is not sufficient, you also need the Bitcoin onchain logic to have the following properties:
- Persistent logic and state.
- Ability to control how logic/state is changed.

For this, covenants are mandatory. Luckily, in our hypothetical scenario, we have `OP_CAT` to help us! Thanks to the [Schnorr trick described by Andrew Poelstra](https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298), `OP_CHECKSIG` combined with `OP_CAT` can emulate `OP_TXHASH`, effectively giving us covenants.

The onchain design would look like this:
- `P2TR (Pay-to-Taproot)` to hold the logic and funds
- `P2WSH (Pay-to-Witness-Script-Hash)` to hold the state root.


### Going Nuts: Cashu x STARKs on Bitcoin

Now let's see how the Cashu protocol could leverage such a STARK verifier on Bitcoin. The integration process would involve the following steps:

1. **Mint generates STARK Proofs:** The mint generates STARK proofs for its off-chain operations.

2. **Proofs submitted onchain:** These proofs are submitted to the Bitcoin network.

3. **Onchain verification:** The Bitcoin script verifies the proof's validity.

4. **Fraud proofs:** Users can submit fraud proofs if they detect a cheating mint. The verifier script could then slash or penalize the cheating mint upon valid fraud proof submission.

To implement this integration effectively, we need to generate STARK proofs for the logic of the Cashu protocol and the mint's operations. There are several approaches to achieve this, each with its own trade-offs:

1. **Custom circuits / AIRs for the Cashu protocol**: This approach involves writing specialized arithmetic circuits or Algebraic Intermediate Representations (AIRs) for the Cashu protocol. While it offers the potential for highly optimized proofs, it is extremely complex, labor-intensive, and prone to errors. The associated security risks also make this option less attractive.

2. **Leveraging existing Mint implementations with ZK-VMs**: This method involves using an existing Cashu implementation (e.g., in Rust) and proving its operations using a zero-knowledge virtual machine such as RISC Zero, SP1, or Jolt. This approach is arguably the simplest, as it can leverage existing implementations. However, it may incur significant performance overhead due to the generality of the ZK-VM. Moreover, none of those systems have been battle-tested yet.

3. **Implementing Cashu in a specialized ZK DSL**: This approach involves rewriting the Cashu protocol in a domain-specific language (DSL) designed for zero-knowledge proofs, such as Cairo. This method offers a compelling balance between implementation simplicity and proof efficiency. Furthermore, Cairo has been audited by several security experts and has a proven track record of correctness and robustness. It is used in production and has been battle-tested (settled over $1.2 trillion dollars over the past four years, with over 500M transactions, which represents nearly half of the total number of Bitcoin transactions since genesis).

We believe the third approach—using a specialized ZK DSL like Cairo—offers the best trade-offs between simplicity, efficiency, and security. To this end, we have begun experimenting with implementing Cashu in Cairo.

As a proof of concept, we've implemented the first step of the Blind Diffie-Hellman Key Exchange (BDHKE) scheme, the backbone of the Cashu protocol. You can find the code for this implementation in the [Cashu ZK Engine repository](https://github.com/AbdelStark/cashu-zk-engine).


By implementing the Cashu logic in Cairo, we can generate STARK proofs that provide computational integrity guarantees for the mint's operations. Moreover, this approach allows us to implement the logic for generating mint and burn proofs for the Proof of Liabilities scheme in a verifiable manner, both on-chain and off-chain.

The potential benefits of this approach are:

1. **Forced ecash melting**: Users could compel the melting of ecash even if the mint becomes unresponsive or attempts to censor transactions, given certain predefined conditions.

2. **Mint accountability**: The system could implement slashing mechanisms or penalties for dishonest mints if there is cryptographic proof of rule violations or malicious behavior.

3. **Integrity by design**: All mint operations would be provably correct.

## Wrapping up

The integration of STARK proofs and the Proof of Liabilities scheme into the Cashu protocol presents a promising approach to reduce trust assumptions and enhance overall security.

The proposed enhancements address key limitations of the current Cashu protocol, providing users with strong cryptographic guarantees while maintaining the privacy features that make Cashu valuable.

Key benefits of this approach include:

1. Enhanced transparency and accountability of mint operations
2. Reduced risk of undetectable ecash supply inflation
3. Improved protection against fractional reserve practices
4. Potential for non-custodial ecash solutions on Bitcoin

---

Keep stacking sats and stay sovereign! ✌️

Catch me on Nostr: `npub1hr6v96g0phtxwys4x0tm3khawuuykz6s28uzwtj5j0zc7lunu99snw2e29`



## Dive deeper

- [Cashu Specifications (NUTs)](https://cashubtc.github.io/nuts/): Dive deep into the technical details of the Cashu protocol.
- [Cashu Documentation](https://docs.cashu.space/): Comprehensive guide to understanding and implementing Cashu.
- [Cashu Visual Explainer](https://lconf.gandlaf.com/): An interactive visual guide to help you grasp Cashu concepts.
- [Cashu ZK Engine proof of concept](https://github.com/AbdelStark/cashu-zk-engine): BDHKE implementation in Cairo
- [The path to general computation on Bitcoin](https://starkware.co/blog/general-computation-on-bitcoin/)
- [Circle STARK verifier in Bitcoin script source code](https://github.com/Bitcoin-Wildlife-Sanctuary/bitcoin-circle-stark)
- [Circle STARKs paper](https://eprint.iacr.org/2024/278.pdf)
- [Bitcoin Signet STARK verification demo transactions](https://github.com/Bitcoin-Wildlife-Sanctuary/bitcoin-circle-stark/pull/91)