Author: Starknet
Source: https://blog.cashu.space/bringing-zero-knowledge-proofs-to-cashu/
In this article, we will explore how “zero-knowledge evidence” can allow eash tokens with arbitrary spending conditions (specified by a Turing-complete programming language) to be exchanged without sacrificing privacy.
Cashu Protocol Overview
The following is a general overview of the "Cashu" protocol. For more details, please refer to the protocol documentation: Cashu NUTs (Notation, Usage, and Terminology).
Cashu is a free and open-source Chaumian ecash protocol ( Chaum, 1982 ) that allows for nearly free and privacy-preserving Bitcoin transactions via electronic tokens; these electronic tokens are similar to banknotes and coins and are held by the user.
The Cashu protocol defines the interaction between the three parties:
Sender (Alice): Transmits the token to...
Receiver (Carla): Receives the token.
The Mint (Bob): A third party that allows Alice and Carla to perform the following operations:
Minting : Users send Bitcoin via the Lightning Network to mint Cashu tokens.
- Alice signals to Bob that she wants to mint a certain amount of Cashu tokens.
- Bob then generates a Lightning Invoice for that amount and gives it to Alice.
- After receiving the payment, Bob " blindly signs " some secret values defined by Alice.
- Alice can then obtain Bob's signature by unblinding, thereby generating the cashu token.
- Then Alice can send these tokens—essentially the revealed secrets, and Bob's (unblinding) signatures on them—to Carla.
(Translator's note: In the Cashu protocol, tokens have standardized denominations that are powers of 2. Therefore, a user does not receive one token at a time, but rather multiple tokens that can be combined to obtain the desired amount.)
Interchange: Create a cashu token using another cashu token
- Carla signals to Bob that she wants to exchange tokens (she needs to send the token to Bob).
- After verifying the token, Bob blind-signs some new secret values defined by Carla and invalidates the token Carla used for the exchange.
- In addition, just like giving change in cash, Carla can also request that tokens be split into other denominations, for example, splitting a token worth 32 "satoshis" into two tokens worth 16 satoshis each.
Meltdown : Exchange Cashu tokens for Bitcoin
- Alice signaled to Bob that she wanted to melt some tokens.
- She sent the Cashu token and an equivalent amount of Lightning Invoices to Bob.
- After Bob verified the tokens, he paid the Lightning Invoice and voided the melted tokens.
Example: Alice sends 100 smarts to Carla
(The following example is shown in the cashu.me web wallet.)
Let's use a more concrete example. Suppose Alice has sufficient funds in her Cashu wallet and wants to send 100 satoshis of ecash to Carla.
- On the "Send" page, Alice's wallet software will guarantee that she holds at least 100 satoshis worth of tokens. If her balance exceeds this amount, but her tokens cannot exactly make up 100 satoshis, the wallet will perform a swap operation with the mint.
- Then, Alice serializes the token to be sent.
- Then, Alice can send the serialized token to Carla (through the communication channel).
- In the "receiving payment" phase, Carla immediately performs a swap using the received tokens. As mentioned earlier, the swap will cause Bob to invalidate the tokens used for the swap and create a new token using a secret value defined by Carla, thereby completing the transfer of ownership of the token's value.
Cost conditions
Alice might want to send a token that cannot be spent arbitrarily and can only be spent by the owner of a specific public key. This gives rise to the concept of " spending conditions ".
The spending conditions on a token mean that a token is only swapped or melted if a "witness" that meets the conditions can be provided.
In order to set spending conditions on some cashu tokens, the secret value must follow a pre-defined secret value format during the minting or swapping process.
For example, if the condition is that Carla is the holder of a certain public key, then Alice's secret value must follow the " Pay to Public Key (P2PK) Secret Value Format ".
Using our previous example again, in the penultimate step, if the serialized token is worth 100 satoshis and contains a secret value like this:
Therefore, if Calir wants to receive funds (i.e., exchange tokens), she must provide a valid signature of this public key as proof. If all the signatures provided by Carl are verified by the public key in secret.data , then Bob will execute the exchange.
Currently, the Cashu protocol only supports two spending conditions ( P2PK and HTLC ). Implementing new spending conditions requires modifications to many active parts and can be very cumbersome. To address these issues, we introduce a new privacy-preserving, arbitrary spending condition, which we call the "Cairo spending condition".
Calculation of STARK proof
Cairo cost conditions allow the valid execution of any Cairo program to be set as a cost condition. The witness provided by the coster is zero-knowledge evidence of the execution of the specified Cairo program, whose output matches the condition.
A very brief introduction to Cario and STARK
"STARK evidence" is used to verify the correctness of a computation very efficiently (far faster than the computation itself takes) without revealing the input data of the computation (this property is called "zero knowledge").
" Cairo " is a programming language specifically designed to be used with STARK proofs. It compiles human-readable code into a set of polynomial evaluation constraints (the proof system deals with polynomials in a large finite field Fp , and the bytecode of a Cairo program is an array of numbers in Fp ).
For example, the following Cairo program fibonacci: Fp → Fp calculates the result of taking the nth Fibonacci number modulo p :
It takes approximately 500 milliseconds to calculate the following results:
Then, we can use stwo-cairo to generate a STARK evidence to assert the correctness of this calculation.
Given the bytecode of fibonacci , the output c , and this STARK proof, a dedicated validator can assert the validity of the statement: ∃n : fibonacci(n) = c , without needing to know n or run fibonacci calculations, and in just 50 milliseconds!
You can try this example on the stwo-cairo.vercel.app webpage.
Now, if we replace fibonacci with an implementation of the verification function of a digital signature scheme that we like, we get a customized P2PK condition! Let's see how it actually works.
Cairo spending conditions
(Sender) sets conditions:
When sending a token, users can add a Cairo spending condition by specifying the hash value of a compiled program and the hash value of the output condition.
This program (and its output conditions) may need to be shared with the recipient via a separate communication channel.
(The recipient) spends the locked token:
Any user who wants to spend this token must run this program, match the output condition desired by the sender, and then generate STARK evidence for this calculation—which is finally verified by the mint.
Key points regarding privacy
In this setup, the mint will know the program's bytecode when a user spends a token (which is a prerequisite for verifying evidence).
In situations where privacy is of paramount importance, we can use a bootloader on top of the original program.
This bootloader is a Cairo program, like a virtual machine, which executes the original program and then outputs (program_hash, program_output) .
We can modify the spending conditions as follows:
程序哈希值→bootloader_program_hash输出条件→(program_hash, output_condition)
From then on, the mint will only know the bytecode of this bootloader, while the original program will remain secret from the mint from beginning to end!
Our work
To learn more, please see our NUT proposal and the codebase we created in TypeScript for client-side validation of Cairo programs in a browser!
Sample video
(over)
