# Bringing Zero Knowledge Proofs to Cashu: Arbitrary Spending Conditions

In this blog post, we explore how zero-knowledge proofs enable the exchange of ecash tokens with arbitrary spending conditions (specified by a Turing-complete programming language), *without* sacrificing privacy.

## A Brief Overview of Cashu

*The following is a high-level introduction of the protocol, for all the nuts and bolts of the cashu protocol, check out the official [Cashu NUTs (Notation, Usage, and Terminology)](https://github.com/cashubtc/nuts)*.

[Cashu](https://https://cashu.space/) is a free and open source Chaumian ecash ([Chaum, 1982](https://chaum.com/wp-content/uploads/2022/01/Chaum-blind-signatures.pdf)) protocol allowing for nearly free, privacy-preserving Bitcoin transactions through digital tokens, which analogously to physical cash, are stored by users.

The Cashu protocol defines the interaction between three parties:
- The sender (Alice): transmitting their token to..
- The recepient (Carla): receiving it.
- The Mint (Bob): a third party with whom Alice and Carla can perform the following operations:
- [minting](https://github.com/cashubtc/nuts/blob/main/04.md): creating cashu tokens from bitcoins sent over the lightning network
:::spoiler
- Alice signals to Bob that she wants to mint cashu tokens worth some amount.
- Bob then creates a lightning invoice of that amount, which he transmits to Alice.
- On reception of the payment, Bob [blindly signs](https://github.com/cashubtc/nuts/blob/main/00.md#protocol) some secrets defined by Alice.
- Alice can then create a cashu tokens by unblinding the signatures.
- Alice can send those tokens, which are essentially the revealed secrets and their unblinded signatures to Carla.

- [swapping](swahubtc/nuts/blob/main/03.md): creating cashu tokens from other cashu tokens
:::spoiler
- Carla signals to Bob that she wants to swap a tokens.
- On verification of the token, Bob blindly signs some new secrets defined by Carla and invalidate the swapped tokens.
- Additionally, like change for physical cash, Carla can request to split the swapped tokens to different amounts, i.e. get two blind signatures worth `16 sats` each from a tokens worth `32 sats`.

- [melting](https://github.com/cashubtc/nuts/blob/main/05.md): getting bitcoins from cashu tokens
:::spoiler
- Alice signals to Bob that she would like to melt tokens.
- She sends to Bob a lightning invoice and cashu tokens worth the requested amount.
- On verification of the tokens, Bob pays the lightning invoice and invalidates the melted tokens.

### Example: Alice sending `100 sats` to Carla.

*(The following example is illustrated on the [cashu.me](https://cashu.me) wallet.)*

For a more concrete example, say Alice has a sufficiently funded cashu wallet and wants to send `100 sats` worth of ecash to Carla.


1. On `SEND`, Alice's wallet will ensure that she posses at least`100 sats` worth of tokens in her local storage. If she doesn't have change that amounts up to the target amount, then the wallet will perform a swap operation with the mint.
2. Alice then [serializes](https://https://github.com/cashubtc/nuts/blob/d3e2a510dcfc20ecb19cce59d5a4f5cc58c51e25/00.md#v4-tokens) the tokens.
3. Which she can send to Carla over their communication channel.
4. On `RECEIVE`, Carla swaps the received tokens. As stated above, the swap will have Bob invalidate the swapped tokens, and allow for the creation of new tokens with secrets defined by Carla, thus transfering the ownership of the tokens' value.

## Spending Conditions

Alice may not want to send tokens that can be spent by anyone, but only to some owner of a public key. This introduces the concept of [Spending Conditions](https://github.com/cashubtc/nuts/blob/main/10.md).

A Spending Condition on a token allows for the swapping or the melting of that token only if a `Witness` satisfying the condition is provided. Meaning that if Bob provides a blind signature, then a `Witness` satisfying the pre-defined condition was provided.

To set a spending condition on cashu tokens, in the minting or swapping process, the secrets have to follow the [Well-Known Secret format](https://github.com/cashubtc/nuts/blob/main/10.md#well-known-secret).

For example, if the condition is that Carla is the owner of some public key, then Alice's secret must follow the [Pay-to-Public-Key (P2PK) Secret format](https://github.com/cashubtc/nuts/blob/main/11.md#pay-to-pubkey).

Following our previous example, in the last step, if the deserialized token worth `100 sat` contains a secrets that look like this:

[
  "P2PK",
  {
    "nonce": "859d4935c4907062a6297cf4e663e2835d90d97ecdd510745d32f6816323a41f",
    "data": "0249098aa8b9d2fbec49ff8598feb17b592b986e62319a4fa488a3dc36387157a7", 
    // ↑ the public key of the spender (defined by Alice)
 ...
]

then for Carla to `RECEIVE`, meaning swapping the tokens, she has to provide valid signatures of the secrets as a `Witness`. If Bob performs the swap, then all the signatures provided by Carla correctly verified with the public key specified in `secret.data`.

Currently only two kinds of Spending Conditions are supported in the Cashu specification ([P2PK](https://github.com/cashubtc/nuts/blob/main/11.md), [HTLC](https://github.com/cashubtc/nuts/blob/main/14.md)). The implementation of new kinds of spending conditions requires the modification of a lot of moving parts, and can be quite cumbersome. To solve these issues, we introduce here a new kind of privacy-preserving, arbitrary Spending Conditions which we named *Cairo Spending Conditions*.

## STARK-proven Computations
Cairo Spending Conditions allow for the valid execution of arbitrary [Cairo](https://https://www.cairo-lang.org/) programs to be set as Spending Conditions. The `Witness` provided by the spender is the zero-knowledge proof-of-execution of the set Cairo program with output matching the condition.

### (Very) Short Introduction to Cairo, STARKs

STARK proofs are used to verify efficiently (much faster than the computation time) the correctness of a computation without revealing the input data (this property is called zero-knowledge).

[Cairo](https://https://www.cairo-lang.org/) is a programming language specifically designed to be used with STARK proofs, compiling human readable code to a set of polynomial evaluation constraints (the proof system works with polynomials over a large finite field $\mathbb{F}_p$, the bytecode of a Cairo program is an array of values in $\mathbb{F}_p$).

<!-- In this section, a Cairo program will be a function $f: \mathbb{F}^n \to \mathbb{F}^m$ -->

Let's take for example the following Cairo program $\operatorname{fibonacci}: \mathbb{F}_p \to \mathbb{F}_p$ computing the $n$-th Fibonacci number modulo $p$:

#[executable]
fn main(n: felt252) -> felt252 {
    fib(0, 1, n)
}

fn fib(a: felt252, b: felt252, n: felt252) -> felt252 {
    match n {
        0 => a,
        _ => fib(b, a + b, n - 1),
    }
}

Computing the following takes approximately **500ms**:

$$\begin{align*}
\operatorname{fibonacci}(1000000) &= 695000552232784364605822574033841251045467108014039321325831286927771212966\\&= c \in \mathbb{F}_p. \end{align*}$$

We can then generate a STARK proof asserting the correctness of this computation using [stwo-cairo](https://github.com/starkware-libs/stwo-cairo).

Given $\operatorname{fibonacci}$ as bytecode, the output $c$, and the STARK proof, a separate verifier can assert the validity of the claim $\exists n : \operatorname{fibonacci}(n) = c$ without learning $n$ nor having to run the computation, in only **50ms**!

*You can try the above example live at [stwo-cairo.vercel.app](https://stwo-cairo.vercel.app/).*

Now if we replace $\operatorname{fibonacci}$ by an implementation of the verification function for our favorite signature scheme, we get a custom P2PK condition! Let's see this it works in practice.

### Cairo Spending Conditions

- Setting the condition (sender):
When sending a token, a user can add a Cairo spending condition by specifying the hash of a compiled program and the hash of the output condition.
The program (and potentially the output condition) has to be shared with the receiver via a separate channel.
- Spending the locked token (receiver):
Any user who wants to spend this token will have to execute the program, match the a output condition and generate STARK proof of this computation which will be verified by the mint.

### Note on Privacy

In the above setup, the mint learns about the program bytecode when a user spends a token (this is necessary for verifying the proof claim).

In situations where privacy is critical, we can make use of a [bootloader](https://zksecurity.github.io/stark-book/cairo/bootloader.html) together with the original program.

The bootloader is a Cairo program acting like a VM that will execute the original program and will output `(program_hash, program_output)`.

We can now modify the spending condition as such:

- `program_hash` → `bootloader_program_hash`
- `output_condition` → `(program_hash, output_condition)`

Now the mint only needs to know the bytecode of the bootloader, and the original program is kept private from the mint at all times!

<!-- ### Our Contributions
- The Cairo Spending Condition Specification
- Integration of the proof verification in the Rust Mint
- Integration of stwo-cairo prover in the Rust Wallet
- Stwo-Cairo-ts: A typscript library to Proving in the browser
- Integration of the new spending condition in the cashu-ts library
- Integration of the browser prover in the cashu.me wallet -->

## Our work

For more details, check out our [NUT proposal](https://github.com/cashubtc/nuts/pull/288) and the [typescript library](https://github.com/clealabs/stwo-cairo-ts) we created for client-side proving of Cairo programs in the browser!

### Demo Video
{%youtube nO3eZG8Nf9M %}