Skip to content

Latest commit

 

History

History
561 lines (427 loc) · 28.2 KB

protocol_explanation.md

File metadata and controls

561 lines (427 loc) · 28.2 KB

Definitions

Scalar and GroupElement

Scalar

A Scalar is an element of group $\mathbb{Z}_q$, where $q$ is prime and is also called the order of the group. Scalar is also commonly referred to as PrivateKey and in cashu-kvac Scalar is a wrap-around secp256k1-py's PrivateKey with some added functionality.

GroupElement

A GroupElement is a point on the secp256k1 curve ($\mathbb{G}$). Also commonly referred to as PublicKey, in cashu-kvac it is indeed a wrap-around secp256k1-py's PublicKey similarly to Scalar.

Generators

Generators

Generators are points on the secp256k1 curve can be used as a basis from which it's possible to compute any other point on the curve through repetitive adding.

The term "generator" here is used loosely. While NUMS points might not necessarily generate the entire group of points on the curve, they can still be considered generators in the sense that they can be used to derive a large number of other points through repeated point addition.

In KVAC, different generators are used for specific purposes. Each generator is derived using NUMS (HashToCurve) to ensure the discrete logarithm relationship between any pair of them remains unknown:

  • $G_w, G_{w'}, G_{x_0}, G_{x_1}$: Used for computing the algebraic MAC (on the mint's side) and later for presenting credentials (on the client's side).
  • $G_\text{zmac}, G_\text{zamount}, G_\text{zscript}$: Used for randomizing the MAC alongside AmountAttribute and ScriptAttribute.
  • $G_\text{amount}, G_\text{script}$: Encode amounts into an AmountAttribute and scripts into a ScriptAttribute.
  • $G_\text{blind}$: Utilized for blinding terms in AmountAttribute and ScriptAttribute.

Mint Private Key

MintPrivateKey

In KVAC, a keyset is a single tuple of six secret values (for all amounts):

$$sk = (w, w', x_0, x_1, y_a, y_s)$$
  • $y_a$: Private key for signing AmountAttributes.
  • $y_s$: Private key for signing ScriptAttributes.
  • $w, w', x0, x1$: additional secret values needed for security hardening of the scheme.

Mint Public Parameters

MintPublicKey

The Mint's "public key" is a tuple $(I, C_w)$, calculated as:

  • $I = G_\text{zmac} - (x_0G_{x_0} + x_1G_{x_1} + y_aG_\text{zamount} + y_sG_\text{zscript})$
  • $C_w = wG_w + w'G_{w'}$

AmountAttribute

AmountAttribute

A point encoding an amount a with blindness r_a. Composition:

  • $r_a \leftarrow \text{BIP39}(\text{seed}, \text{"r-amount"}, \text{derivation})$
  • secret: $(a, r_a)$
  • public: $M_a = r_a\cdot G_\text{blind} + a\cdot G_\text{amount}$

Bootstrap AmountAttribute

Simply a AmountAttribute encoding $0$. Composition:

  • $r_a \leftarrow \text{BIP39}(\text{seed}, \text{"r-amount"}, \text{derivation})$
  • secret: $(r_a)$
  • public: $M_a = r_a\cdot G_\text{blind}$

ScriptAttribute

ScriptAttribute

A point encoding a script hash s with blindness r_s. Composition:

  • $r_s \leftarrow \text{BIP39}(\text{seed}, \text{"r-script"}, \text{derivation})$
  • secret: $(s, r_s)$
  • public: $M_s = r_s\cdot G_\text{blind} + s\cdot G_\text{script}$

MAC

MAC

Equivalent to Cashu's BlindedSignature.

The Mint generates this algebraic MAC using its secret parameters (sk) after verifying RandomizedCoins (see section Protocol). This MAC binds the AmountAttribute and ScriptAttribute together, ensuring neither can be presented alone.

Here $t$ can be picked by both the Mint or the wallet. If the wallet picks it, they will have to send it together with the AmountAttribute (and possibly ScriptAttribute).

The main advantage of letting the wallet derive $t$ from seed is that we can later leverage this for a recovery scheme that does not leak information to the Mint.

Composition:

  • $t \overset{\$}\leftarrow Z_q$ (Mint) or $t \leftarrow \text{BIP39}(\text{seed}, \text{"t"}, \text{derivation})$ (wallet)
  • $M_a$ from AmountAttribute
  • $M_s$ from ScriptAttribute or point at infinity if no script.
  • $U = \text{HashToCurve}(t)$
  • $V = w\cdot G_w + x_0\cdot U + x_1tU + y_a\cdot M_a + y_s\cdot M_s$
  • MAC: $(t, V)$

Coin

We consider the MAC together with AmountAttribute and ScriptAttribute to be a Coin.

$$\text{Coin} = ((r_a, a), (r_s, s), (t, V))$$

RandomizedCoin

RandomizedCoin

Before being sent to the Mint, the coin is "randomized" to break the link to the issuance. In other words, they are blinded a second time with a different generator.

We use the blinding term $r_a$ used for AmountAttribute and compute:

  • $U = \text{HashToCurve}(t)$, where $t$ is the MAC scalar value
  • $C_a = r_a\cdot G_\text{zamount} + M_a$
  • $C_s = r_a\cdot G_\text{zscript} + M_s$
  • $C_{x_0} = r_a\cdot G_{x_0} + U$
  • $C_{x_1} = r_a\cdot G_{x_1} + t\cdot U$
  • $C_v = r_a\cdot G_\text{zmac} + V$, where $V$ is the MAC public point value
  • RandomizedCoin: $(C_a, C_s, C_{x_0}, C_{x_1}, C_v)$

Note

$r_a$ is the only scalar that will produce a valid randomization.

Tweaking the amount in AmountAttribute

tweak amount

Amounts can be tweaked by both the Mint and client to produce new attributes that encode $a + \delta_a$.

  • $M_a' = M_a + \delta_aG_\text{amount}$

Nullifiers

Nullifiers are values (or a single value) used to mark credentials as spent, ensuring they cannot be reused. In the Cashu protocol, the nullifier for a coin is typically the $Y$ value within the Proof object.

Here, we decide to use $C_a$ from the RandomizedCoin as the nullifier. The rationale is rooted in the design of $\pi_\text{MAC}$, which requires $C_a$ to be constructed using the same witness term $r_a$ for both blinding and randomization. This dependency ensures that there is only one valid way to randomize $M_a$ while maintaining valid credentials. Consequently, $C_a$ is guaranteed to be unique and suitable as a nullifier.

Proof of same secret keys ($\pi_\text{iparams}$)

IparamsStatement

Proof $\pi_\text{iparams}$ of knowledge of $(w, w', x_0, x_1, y_a)$ such that:

  1. $w, w'$ were used to construct $C_w$:
$$C_w = w\cdot G_w + w'\cdot G_{w'}$$
  1. $x0, x1, y_a, y_s$ were used to construct $I$:
$$G_\text{z-mac} - I = x_0\cdot G_{x_0} + x_1\cdot G_{x_1} + y_a\cdot G_\text{z-amount} + y_s\cdot G_\text{z-script}$$
  1. the same secret values were used to construct $V$:
$$V = w\cdot G_w + x_0\cdot U + x_1\cdot t\cdot U + y_a\cdot M_a + y_s\cdot M_s$$

This is the equivalent of Cashu's current DLEQ proofs, where the Mint proves to the client they are signing with the same keys as for everybody else (no tagging).

Proof of Range for AmountAttribute $M_a$ ($\pi_\text{range}$)

RangeStatement

This is to prove that the amount encoded into $M_a$ does not exceed a particular limit $L$ (chosen as a power of 2).

The attribute's amount is decomposed into a bit-vector $\mathbf{b}$ of length $l = \log_2(L-1)$. $\mathbf{b}$ is then committed to:

$$\displaylines{ \mathbf{r'} \overset{$}\leftarrow \mathbb{Z}_q^l\\\ \mathbf{B} = \mathbf{b}\cdot G_\text{amount} + \mathbf{r'}\cdot G_\text{blind} }$$

$\pi_\text{range}$ then proves 3 relations in zero knowledge:

  1. The bit decomposition sums up to a:
$$a = \sum_{i=0}^l2^i\cdot b_i$$
  1. Knowledge of the discrete logs behind the bit-commitments vector $B$:
$$\mathbf{B} = \mathbf{b}\cdot G_\text{amount} + \mathbf{r'}\cdot G_\text{blind}$$
  1. discrete logs behind the decomposition are either $0$ or $1$ in value:
$$\displaylines{ \mathbf{b}\circ\mathbf{b} - \mathbf{b} = 0\\\ \text{($\circ$ is the Hadamard or element-wise product of vectors.)} }$$

Statement 3 leverages the fact that:

$$b^2 = b \iff b = 0 \lor b = 1$$

Proof of MAC ($\pi_\text{MAC}$):

CredentialsStatement

This proof shows that RandomizedCoin was computed from a Coin for which a valid MAC was issued.

The public inputs to this proof are the RandomizedCoins $(C_a, C_s, C_{x_0}, C_{x_1}, C_v)$

$\pi_\text{MAC}$ proves 3 relations:

  1. $Z = r_a\cdot I$ where $r_a$ is the blinding factor from AmountAttribute.
  2. $C_a = r_a\cdot G_\text{zamount} + r_a\cdot G_\text{blind} + a\cdot G_\text{amount}$ to prove $r_a$ is indeed the same as in AmountAttribute.
  3. $C_{x_1} = t\cdot C_{x_0} - t\cdot r_a\cdot G_{x_0} + r_a\cdot G_{x_1}$, where $t$ is the scalar value in the MAC.

Statement 1 works because the Mint uses private keys $sk$ and the RandomizedCoin's commitments to re-calculate $Z$ autonomously as:

$$Z = C_v - (w\cdot C_w + x_0\cdot C_{x_0} + x_1\cdot C_{x_1} + y_a\cdot C_a + y_s\cdot C_s)$$

Proof of Balance ($\pi_\text{balance}$):

BalanceStatement

This proof shows that the difference in encoded amount between the sum of many RandomizedCoins $C_{a_i}$ and many new AmountAttributes $M_{a_i}$ is exactly $\Delta_a$.

$\pi_\text{balance}$ proves 1 relation:

$$B = \sum_{i=0}^n\left(r_{a_i}\right)\cdot G_\text{zamount} + \sum_{i=0}^n\left(r_{a_i}-r'_{a_i}\right)\cdot G_\text{blind}$$

Where $r'_{a_i}$ (with the apex $'$) are the amount blinding terms for the new attributes.

This statement works because the Mint uses $\Delta_a$ to re-compute the verification value $B$ autonomously as:

$$B = \Delta_a\cdot G_\text{amount} + \sum_{i=0}^{n}\left(C_{a_i}-M_{a_i}\right)$$

Protocol

This section explains how a client/wallet (used interchangeably) interacts with a Mint (capital 'M' to distinguish it from the verb "minting").

Bootstrapping

To perform any interaction (e.g., mint, swap, or melt) with the Mint, a client needs Coins worth $0$ (46). This is because the Mint always requires a valid set of input RandomizedCoins for any other operation (mint/melt/swap).

To handle this, the client makes a special BootstrapRequest:

  1. The client requests a MAC for an AmountAttribute $M_a$ that encodes $0$, optionally including a ScriptAttribute $M_s$ encoding a script hash $s$. This would be used for things like spending conditions.
  2. The client generates a proof, $\pi_\text{bootstrap}$, to show that $M_a$ encodes $0$ (48).
  3. The client sends $(M_a, M_s, \pi_\text{bootstrap})$ to the Mint.

The Mint processes the BootstrapRequest as follows:

  1. It verifies the proof $\pi_\text{bootstrap}$ (53)
  2. If the proof is valid, it issues a MAC $(t, V)$ for $M_a$ (and $M_s$ if provided) (56).
  3. It creates and returns $\pi_\text{iparams}$ to prove that the private keys it used are not linked to individual users (57).

From the wallet's perspective, this bootstrapping process is only needed once per Mint.

SwapRequest

When a client wants to swap Coins, they:

  1. Create request outputs: new AmountAttribute and ScriptAttribute pairs that encode respectively the final wallet balance (minus any fees) and, optionally, the hash of the script describing the spending conditions (65-66).
  2. Create request inputs: generate RandomizedCoin from the old Coin which contains the attribute encoding the current balance and the MAC (the Mint's "attestation"/"signature"). If the client doesn't have any such Coin, they have to Bootstrap first. (72).

The client also generates the following ZK-proofs:

  • $\pi_\text{balance}$: Proves that the balance difference $\Delta_a$ (should equal $0$ or the fees) between old and new wallet balances is valid. Inputs: old and new AmountAttributes (78).
  • $\pi_\text{range}$: For each new AmountAttribute, proves the value is within the range $[0, L-1]$. (69).
  • $\pi_\text{MAC}$: Proves that the provided RandomizedCoins are valid and unspent. (75)
  • $\pi_\text{script}$: Ensures all new ScriptAttributes encode the same script hash $s$ as the old RandomizedCoins. (81).

Then the client sends:

  • old RandomizedCoins defined in (2) as inputs
  • new (AmountAttribute/ScriptAttribute) pairs' COMMITMENTS (not the secret values) as described in (1)
  • The script the coins were locked to, if any, together with its script-signature
  • All proofs as described above.

The Mint then (89-105):

  1. Acknowledges the balance difference $\Delta_a$ between inputs and outputs.
  2. Verifies that it hasn’t seen the RandomizedCoin $C_a$ before.
  3. Verifies all proofs.
  4. If all verifications are successful, the Mint issues new MACs for the outputs commitment pairs (108). As with the BootstrapRequest, the Mint also produces $\pi_\text{iparams}$ to prove to the wallet its private key usage (109).

Wallet-to-Wallet

Sending coins to another wallet is simpler, as sending wallet only needs to communicate the Coin of intended value to the receiving wallet, and the receiving wallet will immediately swap it for a new one encoding the same value.

No extra information is needed, as all proofs and randomization can be computed directly by the receiving wallet.

Blank Outputs for Overpaid Fee Change

In Cashu, wallets often overpay during melt operations to ensure successful transactions, accounting for the unpredictability of lightning fees.

To allow the Mint to return the excess coins to the client, the client provides "blank" BlindedMessages with no predefined amount. The Mint then assigns a value to these outputs and signs them with its keys.

With KVAC, this process is simplified:

  1. During a melt operation, the client declares a $\Delta_a$ between the inputs and outputs that exceeds the peg-out amount (amount in the melt quote). This claim is substantiated by $\pi_\text{balance}$.
  2. The Mint returns the overpaid amount $o$ by adjusting the commitment $M_a$ of the new AmountAttribute. Specifically, it tweaks the commitment as follows:
$$M_{a'} \gets M_a + o \cdot G_\text{amount}$$

CashuTranscript

CashuTranscript

CashuTranscript is a wrapper around a MerlinTranscript, which is used to manage a transcript for cryptographic operations. The MerlinTranscript itself is a tool for maintaining a running log of messages during interactive or non-interactive cryptographic protocols. It provides a way to securely commit to various inputs and derive challenges deterministically.

Key Features of CashuTranscript:

  1. Domain Separation:

    • domain_sep ensures that different contexts or types of operations within the protocol are distinguishable by their unique labels. This prevents potential cross-protocol attacks where inputs in one context might be interpreted as valid in another.

  2. Commitments:

    • The append method commits a group element to the transcript.

  3. Challenge Derivation:

    • The get_challenge method extracts a cryptographic challenge deterministically from the transcript. This challenge is used in proofs, ensuring it depends on all prior transcript data, providing strong security guarantees.

Role in Zero-Knowledge Proving and Verifying:

In a zero-knowledge proof (ZKP), the prover aims to convince the verifier of a statement's validity without revealing any secrets. CashuTranscript plays a crucial role in ensuring the soundness and security of this process.

  1. Non-Interactive Proofs:

    • Using the Fiat-Shamir heuristic, CashuTranscript turns interactive proofs into non-interactive ones by simulating the verifier's role in generating challenges. This makes it possible to create proofs that can be verified later without an interactive session.

  2. Binding:

    • The commitments recorded in the transcript bind the prover to specific values. This ensures that the prover cannot alter their proof after seeing the challenge.

  3. Challenge Integrity:

    • The challenges derived via CashuTranscript are deterministic but depend on the entire transcript. This means any tampering with the transcript will produce a different challenge, making it impossible to forge valid proofs.

  4. Security Against Replay Attacks:

    • Since the transcript includes domain separators and commitments to public and private inputs, reusing a proof in a different context will result in a mismatch in the challenge, invalidating the proof.

Explanation of the Generic Proof of Knowledge (PoK) Mechanism

Schnorr Prover/Verifier

The implementation creates and verifies Proofs of Knowledge (PoK) for linear relations using a non-interactive zero-knowledge proof (NIZKP) protocol. This approach makes use of the Fiat-Shamir heuristic, which transforms an interactive proof into a non-interactive one by using a cryptographic hash function.

1. Definitions and Setup

Linear Relation

A linear relation is a mathematical statement of the form:

$$\sum_{i=1}^n s_i P_i = V$$

where:

  • $(s_i)$ are secrets (values the prover knows but does not wish to reveal).
  • $(P_i)$ are public points (elements from a group/in most cases the previously mentioned generators).
  • $(V)$ is the verification value (public input).

The goal is for the prover to convince the verifier that they know the $(s_i)$ values that satisfy the relation without revealing the secrets.

2. Proving Phase

In the proving phase, the prover demonstrates knowledge of the secrets $({s_i})$ without revealing them.

Steps:

  1. Generate Random Terms:

    code

    For each secret $(s_i)$, the prover generates a random term $(k_i)$ (a private nonce):

$$k_i \sim \mathbb{Z}_q$$

  1. Compute Commitments:

    code

    The prover computes public-nonce commitments $(R)$ for the linear relation using the $(k_i)$:

$$R = \sum_{i=1}^n k_i P_i$$

  1. Append to Transcript:

    code

    The prover serializes the verification value (public input) $(V)$ and commitments $(R)$ and appends them to the running transcript.

  2. Compute Challenge:

    code

    The prover derives a challenge $(c)$ from the current state of the transcript:

$$c = H(R\ldots \ \text{||} \ V\ldots)$$

The challenge is a deterministic random scalar.

  1. Compute Responses:

    code

    For each secret $(s_i)$, the prover computes a response $(z_i)$:

$$z_i = k_i + c \cdot s_i$$

  1. Generate Proof:

    code

    The prover packages the responses $({z_i})$ and the challenge $(c)$ into a proof object:

$$\text{Proof} = \{z_1, z_2, \ldots, z_n, c\}$$

3. Verification Phase

In the verification phase, the verifier ensures the proof is valid without learning the secrets.

Steps:

  1. Extract Proof Components:

    code

    The verifier extracts the responses $({z_i})$ and challenge $(c)$ from the proof.

  2. Recompute Commitments:

    code

    Using the responses $({z_i})$ and public points $({P_i})$ given by the proof's statement, the verifier recomputes the commitments:

$$R' = \sum_{i=1}^n z_i P_i - c \cdot V$$
  • If $(R')$ matches the original commitments, it suggests the prover's responses are consistent with the claimed linear relation.

  1. Recompute Challenge:

    code

    The verifier computes the challenge from the commitments and the public inputs:

$$c' = H(R'\ldots \ \text{||} \ V\ldots)$$
  1. Validate Proof: The verifier checks if:
$$c' = c$$

If this equality holds, the proof is valid.

Key Insights

  • The use of random terms $(k_i)$ ensures that the proof does not leak information about the secrets $({s_i})$.
  • The cryptographic hash function $(H)$ guarantees that the challenge $(c)$ is unpredictable and tamper-proof.
  • The recomputation of $(R')$ in the verification phase confirms the consistency of the prover's claim.

Mathematical Details

Proof of Correctness: The responses $(z_i)$ are defined as:

$$z_i = k_i + c \cdot s_i$$

Substituting into the recomputed commitments during verification:

$$R' = \sum_{i=1}^n z_i P_i - c \cdot V = \sum_{i=1}^n (k_i + c \cdot s_i) P_i - c \cdot V$$

Expanding:

$$R' = \sum_{i=1}^n k_i P_i + c \cdot \sum_{i=1}^n s_i P_i - c \cdot V$$

Using the linear relation $(\sum_{i=1}^n s_i P_i = V)$, this simplifies to:

$$R' = \sum_{i=1}^n k_i P_i = R$$

Thus, the recomputed commitments $(R')$ match the original commitments $(R)$, ensuring the proof is valid.