Danake is a lightweight micropayment system which allows anonymous services to bill for resource usage without compromising privacy or performance. It is named in reference to the danake, a silver coin of the Persian empire commonly placed in the mouth of the deceased to pay for passage into the underworld.

Using Danake, a service provider can issue credits to users based on some application-dependent policy, and allow those users to anonymously spend those credits to pay for services. The exact policy is considered out-of-scope for Danake itself, but for instance, a service provider could periodically issue credits to each user, or allow users to purchase credits using Zcash, etc.

Danake is a work-in-progress, and this document will continue to evolve over time. The table of contents is visible on the left or via the menu button at top-left. This document also supports full-text search, available by pressing s.

# Design Goals

As described in the introduction, Danake is a lightweight micropayment system. A service provider can issue usage credits to users, who can spend credits for services. Credit issuance can be anonymous, linked to a long-term identity, or somewhere in-between, but credits are spent anonymously, and every credential spend should be unlinkable from all other credential spends and issuances.

Users should not be able to spend usage credit multiple times or gain usage credits except from the application's issuance policy. Danake does not attempt to prevent users from trading usage credits on a secondary market, as doing so in the limit is not feasible anyways1. However, Danake also does not attempt to have any independent verifiability of credit amounts. Like a gift card, users must trust the service provider to redeem credits for services. This model can be contrasted to the model used in other "layer 2" payment systems, where counterparty trust is not required.

Danake's micropayment mechanism can either be surfaced to users, or kept as an implementation detail. For instance, a service wishing to prevent overuse by a single user but without wishing to monitor all users and keep usage statistics could periodically issue a fixed usage quota to each registered user; their user-agent can automatically spend credits to use the service as an implementation detail, without ever displaying a monetary usage quota to the user. For this reason, this document uses user to refer to a logical user (human or otherwise), and client to refer to a user's user-agent (software operating on their behalf).

The transport between client and server is considered out-of-scope for Danake, or more precisely, Danake assumes an anonymous transport from the client to the server. This can be provided by Tor2, or, alternatively, Danake can be used with HTTPS and an assumption that the server does not keep logs of user activity. The latter alternative is obviously not ideal, but still meaningfully better than having the service provider track per-user usage statistics.

Finally, because resource controls that cost more than the resources they are intended to control are impractical, Danake is intended to be fast enough to replace non-anonymous application authentication logic.

1

For instance, credits could be bound to a specific user-id and the client could prove consistency between a different user credential and their wallet credential ... but then users can just make requests on behalf of each other.

2

To be precise, this requires using a new Tor circuit for each micropayment the client intends to be unlinkable from previous micropayments.

# The Danake State Machine

A user's credit balance is stored in a wallet credential with attributes $$(w,n_w)$$, where $$w$$ is the wallet balance and $$n_w$$ is the wallet nullifier. Clients can transfer small portions of their wallet balance to tokens, which can be used to spend credits with the service provider until the token balance is depleted. A token is a credential with attributes $$(t,n_t)$$, where $$t$$ is the token balance and $$n_t$$ is the token nullifier. Both wallets and tokens have nullifier attributes so that they can only be used once; each presentation of a wallet or token is coupled with a (blinded) issuance request for a new wallet or token with an updated balance and a new nullifier.

These credentials are instantiated with CMZ13 (AMACs) credentials, described in a later section of the document.

While the simplest mechanism would be for the client to spend credits from the wallet credential directly, using intermediate tokens has a number of advantages:

1. Because presentation is sequential (each presentation reveals a nullifier and requests issuance of a new credential for future use), using intermediate tokens allows a client to make multiple presentations in parallel, rather than waiting for a complete server round-trip before spending more credits.

2. Because token credentials store less value than the wallet credentials, they can use smaller bitsizes for their range proofs, reducing the server's verification work for the more commonly used credentials.

3. Because token credentials have different issuer parameters, the epoch interval for token credentials can be shorter than the epoch interval for wallet credentials, which allows faster pruning of the nullifier sets for the more commonly used credentials.

4. Because token credentials have different issuer parameters, a deployment in a sharded setting (e.g., to a service backed by a CDN) could scope tokens to a particular shard (e.g., a CDN edge region or point-of-presence), requiring only local rather than global nullifier state for the more commonly used credentials.

The remainder of this chapter (table of contents to the left) describes the state transitions in Danake.

An example sequence of state transitions is illustrated below. Rectangular boxes denote credential states, and round boxes denote state changes. Each state change requires exactly one round-trip from the client to the server. Note that the value v in each spend step is not hardcoded but can be any arbitrary policy-determined credit amount.

 .───────────────────────.
(Wallet issuance (policy) )
───────────────────────'
│
▼
┌─────────────┐
│   Wallet    │   w_0:  wallet balance
│ (w_0, nw_0) │   nw_0: wallet nullifier
└─────────────┘
│
▼                                  ┌─────────────┐
.───────────────────.                        │    Token    │
(Buy token, value t_0 )──────────────────────▶│ (t_0, nt_0) │
───────────────────'                        └─────────────┘
│                                         │
▼                                         ▼
┌───────────────┐                           .───────────.
│    Wallet     │                          (Spend value v)
│  (w_1, nw_1)  │                           ───────────'
│w_1 = w_0 - t_0│                                 │
└───────────────┘                                 ▼
│                                  ┌─────────────┐
▼               ┌─────────────┐    │    Token    │
.───────────────────.     │    Token    │    │ (t_1, nt_1) │
(Buy token, value t_0 )───▶│ (t_0, nt_0) │    │t_1 = t_0 - v│
───────────────────'     └─────────────┘    └─────────────┘
│                      │                  │
▼                      ▼                  ▼
┌───────────────┐        .───────────.      .───────────.
│    Wallet     │       (Spend value v)    (Spend value v)
│  (w_1, nw_1)  │        ───────────'      ───────────'
│w_1 = w_0 - t_0│              │                  │
└───────────────┘              ▼                  ▼
│               ┌─────────────┐    ┌─────────────┐
▼               │    Token    │    │    Token    │
.───────────────────.     │ (t_1, nt_1) │    │ (t_2, nt_2) │
(Add value v (policy) )    │t_1 = t_0 - v│    │t_2 = t_1 - v│
───────────────────'     └─────────────┘    └─────────────┘
│                      │                  │
▼                      ▼
┌───────────────┐        .───────────.            │
│    Wallet     │       (Spend value v)
│  (w_2, nw_2)  │        ───────────'            │
│ w_2 = w_1 + v │              │
└───────────────┘              ▼                  ▼
│               ┌─────────────┐    ┌─────────────┐
│    Token    │    │    Token    │
│               │ (t_2, nt_2) │    │ (t_i, nt_i) │
│t_2 = t_1 - v│    │   t_i < v   │
│               └─────────────┘    └─────────────┘
│                  │ Drop
▼                                         │change
│                  ▼
Λ
│                 ▕ ▏
V
▼
┌─────────────┐
│    Token    │
│ (t_i, nt_i) │
│   t_i < v   │
└─────────────┘
│ Drop
│change
▼
Λ
▕ ▏
V


# Notation

The notation in this document differs from the notation in the CMZ13 paper but has the important advantages that the type of each variable is readily visible in its notation, and that the notation in the abstract description matches the notation in the implementation.

$$\mathbb G$$ denotes an abelian group of prime order $$p$$. As it is abelian, it is written additively. Group elements are denoted by upper-case letters $$A, B, \ldots$$, while scalars are denoted by lower-case letters $$a, b, \ldots$$; boldface letters $$\mathbf a, \mathbf G$$ denote a vector of elements (in these cases, a vector of scalars and a vector of group elements, respectively).

The inner product of two vectors is denoted by $$\langle-,-\rangle$$. Notice that with this notation, a multiscalar multiplication is written as $$\langle\mathbf a, \mathbf G\rangle$$, and all the usual inner-product identities can be used to rearrange terms. The concatenation of two vectors is written $$\mathbf x || \mathbf y$$.

The notation $$P \xleftarrow{\} \mathbb G$$ means that $$P$$ should be selected uniformly at random from the set $$\mathbb G$$.

Pedersen commitments are written as $\operatorname{Com}(v) = \operatorname{Com}(v, {\widetilde{v}}) = v \cdot B + {\widetilde{v}} \cdot {\widetilde{B}},$ where $$B$$ and $$\widetilde B$$ are the Pedersen generators used for the values and blinding factors, respectively. The blinding factor for the value $$v$$ is denoted by $$\widetilde v$$, so that it is clear which blinding factor corresponds to which value, and write $$\operatorname{Com}(v)$$ instead of $$\operatorname{Com}(v, \widetilde v)$$ for brevity.

The ElGamal encryption of a group element $$A$$ to the public key $$D$$ is written as $\operatorname{Enc}_D(A) = (rB, A + rD),$ where $$r$$ is the randomness used for the encryption and $$B$$ is the generator used for the public key $$D$$. The individual components are denoted by $$\operatorname{Enc}_D(A)_0$$ and $$\operatorname{Enc}_D(A)_1$$.

Non-interactive Schnorr proofs are denoted by the following Camenisch-Stadler-like notation, which matches the notation used in the zkp crate used to automatically derive the proof implementations: \begin{aligned} \operatorname{PK}&\{ \\ &\mathtt{CorrectElGamal}, \\ &(d, (r_i, m_i)_{i \in \mathcal H}), \\ &(D, (E_{i,0}, E_{i,1})_{i \in \mathcal H}), \\ &(B) \; : \\ &(E_{i,0}, E_{i,1}) = (r_i B, m_i B + r_i D) \; \forall i \in \mathcal H \\ \} \end{aligned}

Here the first line is an ASCII domain separation label used to identify the proof statement; the second line is a list of secret scalar variables (witness data); the third line is a list of public group element variables unique to each proof instance; the fourth line is a list of public group element variables common across all proof instances; the remaining lines are the statements to be proved. Distinguishing public variables which are common across all proof instances from ones which are unique to each proof instance allows a derived implementation to take advantage of precomputation and provide batch verification.

# CMZ13 Credentials

A message authentication code (MAC) scheme allows the holder of a secret key to produce a MAC witnessing the integrity of the message, which they can verify using the same secret key. This is the symmetric-cryptography analogue of a public-key signature scheme, in which the holder of a secret key can produce a signature witnessing the integrity of the message, which anyone can verify using the corresponding public key.

MACs allow the construction of keyed-verification credential systems, which the issuer of a credential uses a MAC to witness the integrity of a credential and later checks it on presentation. Most famously, this is the idea underlying Macaroons, which support other interesting features such as delegation and attenuation.

In their 2013 paper, Algebraic MACs and Keyed-Verification Anonymous Credentials, Chase, Meiklejohn, and Zaverucha apply this idea to anonymous credentials, introducing the concept of a keyed-verification anonymous credential (KVAC), where the issuer of an anonymous credential is also the verifier of the credential, and then showed how to construct anonymous credentials using algebraic MACs, i.e., MACs defined in some group rather than using bitwise operations.

The insight of keyed-verification credentials is that while most anonymous credential systems are built to allow a user to present credentials to third parties, in many cases, particularly resource access control, it's sufficient for verification to be restricted to the issuer of the credential. This functional restriction allows much more efficient constructions, because the credential can use symmetric-style rather than public-key-style cryptography.

This section reviews the CMZ'13 construction, describing key generation, blinded issuance, and credential presentation.

TODO: rewrite this section to make it more clear.

# MAC-GGM

The CMZ13 paper defines two algebraic MACs which can be used to construct credentials, $$\mathsf{MAC_{GGM}}$$ and $$\mathsf{MAC_{DDH}}$$, which are proved secure in the generic group model and under the decisional Diffie-Hellman assumption, respectively. However, $$\mathsf{MAC_{DDH}}$$ is more expensive and as noted in the paper, there is no reason to believe that $$\mathsf{MAC_{GGM}}$$ is not also secure under DDH, although there is no proof.

For reasons of efficiency we use $$\mathsf{MAC_{GGM}}$$. As noted in the paper, this is a generalization of a 2012 construction due to Yevgeniy Dodis, Eike Kiltz, Krzysztof Pietrzak, and Daniel Wichs. It is defined as follows:

• Setup. Choose $$\mathbb G$$ a group of prime order $$p$$. The messages will be elements of $$\mathbb F_p^n$$, i.e., $$n$$-tuples of field elements in $$\mathbb F_p$$.

• Key Generation. Choose $$\mathbf x = (x_0, x_1, \ldots, x_n) \xleftarrow{\} \mathbb F_p^{n+1}$$.

• MAC. Given a message $$\mathbf m \in \mathbb F_p^n$$, choose $$P \xleftarrow{\} \mathbb G \setminus \{ 0 \}$$ and compute $$Q = \langle \mathbf x, (1) || \mathbf m \rangle \cdot P$$. The tag is $$(P, Q)$$.

• Verify. Given a message $$\mathbf m \in \mathbb F_p^n$$ and a purported tag $$(P,Q)$$, accept if $$P \neq 0$$ and $$Q = \langle \mathbf x, (1) || \mathbf m \rangle \cdot P$$, otherwise reject.

Notice that although the tag $$(P,Q)$$ witnesses the integrity of the message $$\mathbf m$$, the tag itself is malleable: given $$r \in \mathbb F_p^\times$$, $$(rP, rQ)$$ also satisfies the verification equation. When used as part of an anonymous credential, this will be used to re-randomize the tag.

# Key Generation

The following procedure defines common parameters for all credentials:

• Setup. Choose $$\mathbb G$$ a group of prime order $$p$$. $$\mathbb G$$ should be equipped with a hash-to-group method suitable for choosing orthogonal generators. Select orthogonal generators $$B, \widetilde B$$.

To issue credentials, the issuer generates issuance secrets, which are used to create and verify credentials, and issuance parameters, which commit to the issuance secrets and are used by clients to verify that their credentials are issued with respect to the same issuance secrets as all other clients, preventing key partitioning attacks.

• Key Generation. Choose a $$\mathsf{MAC_{GGM}}$$ secret $$\mathbf x = (x_0, x_1, \ldots, x_n) \xleftarrow{\} \mathbb F_p^{n+1}$$. Also select a blinding factor $$\widetilde x_0 \xleftarrow{\} \mathbb F_p$$, then compute $$X_0 = x_0 B + \widetilde x_0 \widetilde B$$ and $$X_i = x_i \widetilde B$$ for $$i = 1, \ldots, n$$.

The issuance secrets are $$(\mathbf x, \widetilde x_0)$$ and the issuance parameters are $$\mathbf X$$.

FIXME: rewrite to make pedersen commitment structure more clear?

# Issuance

Following CMZ13, this description of blinded issuance denotes the set of hidden attribute indexes by $$\mathcal H \subseteq \{1,\ldots,n\}$$. At a high level, the issuer computes a MAC on the requested attributes, then returns it, together with a proof that it was computed with respect to the expected issuance parameters. To handle blinded attributes, the client generates an ephemeral ElGamal key, encrypts the attributes to be blinded, and proves that the encryptions were well-formed. Because ElGamal encryptions are homomorphic, a MAC on encrypted attributes can be converted into an encryption of a MAC on the plaintext attributes.

Issuance is an online protocol with the following steps.

1. Client. The client proceeds as follows.

1. The client generates an ephemeral ElGamal secret $$d \xleftarrow{\} \mathbb F_p$$ and computes the ephemeral public key $$D \gets d B$$.

2. For each blinded attribute $$m_i$$ indexed by $$i \in \mathcal H$$, the client chooses $$r_i \xleftarrow{\} \mathbb F_p$$ and computes $$\operatorname{Enc}_D(m_i B) \gets (r_i B, m_i B + r_i D)$$.1

3. The client proves that the encryptions were well-formed: \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{CorrectElGamal}, \\ &(d, (r_i, m_i)_{i \in \mathcal H}), \\ &(D, (\operatorname{Enc}_D(m_i B))_{i \in \mathcal H}), \\ &(B) \; : \\ &\operatorname{Enc}_D(m_i B) = (r_i B, m_i B + r_i D) \; \forall i \in \mathcal H \\ \} \end{aligned}

4. The client sends $$D$$, $$(m_i)_{i \in \mathcal H}$$, $$(\operatorname{Enc}_D(m_i B))_{i \in \mathcal H}$$ and $$\pi$$ to the server.

2. Issuer. The issuer verifies the client's proof and optionally performs other policy checks related to issuance. Now the issuer would like to select $$P \xleftarrow{\} \mathbb G$$ and compute $$Q \gets \langle \mathbf x, (1) || \mathbf m \rangle P$$, but this cannot be done directly as the attributes $$(m_i)_{i \in \mathcal H}$$ are not available. Instead, the issuer will compute $$\operatorname{Enc}_D(Q)$$ as follows, decomposing $$Q$$ as $$Q = Q_c + Q_b$$ and considering the contributions from cleartext attributes $$Q_c$$ and blinded attributes $$Q_b$$ separately:

1. The issuer selects $$b \xleftarrow{\} \mathbb F_p$$ and computes $$P \gets bB$$.
2. The issuer computes2 a partial MAC on the cleartext attributes $%Q_c \gets \langle % (x_0) || (x_i)_{i \not\in \mathcal H}, % (1) || (m_i)_{i \not\in \mathcal H}, %\rangle P. Q_c \gets \Big( x_0 + \sum_{i \not\in \mathcal H} x_i m_i \Big) P.$
3. The issuer selects randomness $$r \xleftarrow{\} \mathbb F_p$$ to compute $\operatorname{Enc}_D(Q_c) \gets (rB, Q_c + rD).$
4. The issuer uses $$E_i = \operatorname{Enc}_D(m_i B)$$ to compute $\operatorname{Enc}_D(Q_b) \gets \sum_{i \in \mathcal H} b x_i \operatorname{Enc}_D(m_i B).$
5. The issuer computes $\operatorname{Enc}_D(Q) \gets \operatorname{Enc}_D(Q_c) + \operatorname{Enc}_D(Q_b).$
6. The issuer proves that it performed its steps correctly and issued a credential with respect to the correct issuance parameters: \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{CorrectBlindIssuance}, \\ &( b, r, \mathbf x, \widetilde x_0, \mathbf t ), \\ &( P, D, (\operatorname{Enc}_D(m_i B))_{i \in \mathcal H}, \operatorname{Enc}_D(Q), \mathbf T ), \\ &(\mathbf X, B, \widetilde B) \; : \\ & X_0 = x_0 B + \widetilde x_0 \widetilde B, \\ & X_i = x_i \widetilde B \quad i = 1, \ldots, n, \\ & P = bB, \\ & T_i = bX_i, T_i = t_i \widetilde B \quad \forall i \in \mathcal H, \\ & \operatorname{Enc}_D(Q) = \Big( rB, \Big( x_0 + \sum_{i \not\in \mathcal H} x_i m_i \Big) P + rD \Big) + \sum_{i \in \mathcal H} t_i \operatorname{Enc}_D(m_i B) \\ \} \end{aligned} where $$t_i = bx_i$$, $$T_i = t_i\widetilde B$$ are auxiliary variables used to avoid writing statements involving secret products.
7. The issuer sends $$P$$, $$\operatorname{Enc}_D(Q)$$, $$T_i$$, and $$\pi$$ to the client.
3. Client. The client verifies the issuer's proof using the expected issuance parameters and decrypts $$\operatorname{Enc}_D(Q)$$ to obtain the tag $$(P,Q)$$.

FIXME: the notation in this description is hard to follow.

1

Because the client knows their own ephemeral secret, assuming an optimized fixed-base scalar multiplication is available, this can be optimized as $(E_{i,0}, E_{i,1}) \gets (r_i B, (m_i + r_i d)B) = (r_i B, m_i B + r_i D).$

2

Since $$P = pB$$, this can also be optimized as a fixed-base scalar multiplication.

# Presentation

FIXME: change description to explain why this works

Credential presentation is an online protocol with the following steps. As in the description of issuance, the the set of hidden attribute indexes is denoted by $$\mathcal H \subseteq \{1, \ldots, n\}$$. However, the set $$\mathcal H$$ need not be the same – different sets of attributes can be hidden or revealed between issuance and presentation.

1. Client. Given attributes $$\mathbf m$$ and a previously issued tag $$P_0, Q_0$$, the client proceeds as follows.
1. The client re-randomizes the tag by choosing $$t \xleftarrow{\} \mathbb F_p$$ and computing $$(P, Q) \gets (t P_0, t Q_0)$$.
2. The client commits to the hidden attributes by choosing $$\widetilde m_i \xleftarrow{\} \mathbb F_p$$ and computing $$\operatorname{Com}(m_i) = m_i P + \widetilde m_i \widetilde B$$ for each $$i \in \mathcal H$$. Notice that the Pedersen commitments are made with respect to the Pedersen generators $$(P, \widetilde B)$$ rather than $$(B, \widetilde B)$$.
3. The client commits to $$Q$$ by choosing $$r_Q \xleftarrow{\} \mathbb F_p$$ and computing $$C_Q \gets Q + r_QB$$.
4. The client uses the issuance parameters to compute a correction term $$V \gets \sum_{i \in \mathcal H} \widetilde m_i X_i - r_QB$$.
5. The client proves that the commitments and the correction term were computed correctly: \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{ClientPresentation}, \\ &(r_Q, (m_i, \widetilde m_i)_{i \in \mathcal H}), \\ &(P, V, (\operatorname{Com}(m_i))_{i \in \mathcal H}), \\ &(B, \widetilde B) \; : \\ & \operatorname{Com}(m_i) = m_i P + \widetilde m_i \widetilde B \quad \forall i \in \mathcal H \\ & V = \sum_{i \in \mathcal H} \widetilde m_i X_i - r_Q B \\ \} \end{aligned}
6. The client sends $$P$$, $$C_Q$$, $$(\operatorname{Com}(m_i))_{i \in \mathcal H}$$, $$(m_i)_{i \not\in \mathcal H}$$, and $$\pi$$ to the issuer.
2. Issuer. The issuer computes $$V$$ as $V \gets \Big( x_0 + \sum_{i \not\in \mathcal H} x_i m_i \Big) P + \sum_{i \in \mathcal H} x_i \operatorname{Com}(m_i)_{i \in \mathcal H} - C_Q$ and uses $$V$$ to verify $$\pi$$.

# Extensions to CMZ13

Danake uses the CMZ13 construction mostly unmodified, except for a few minor extensions detailed explicitly in this section.

1. While the CMZ13 paper describes proofs of correctness for each protocol step, Danake uses Merlin transcripts to chain these incremental proofs into proofs of correctness of an entire protocol run.

2. Danake uses nullifiers to provide credentials with use-once ("affine") semantics, allowing the encoding of more complex state machines at the cost of requiring the issuer to maintain a nullifier set.

3. Danake introduces a notion of credential epochs, which provide continual key rotation and nullifier set pruning.

# Chaining Proofs

Various parts of the CMZ13 construction make use of zero-knowledge proofs to have, e.g., the issuer prove to the client that the credential was issued with respect to the expected parameters, or the client prove to the issuer that their blinded attributes were well-formed encryptions.

This is a specific instance of a more general paradigm: the use of zero-knowledge proofs to be transformed from a setting with possibly-malicious participants, who may not behove correctly, to a setting with honest-but-curious participants, who perform the protocol steps correctly, but might try to learn extra information.

To do this, as each participant performs their protocol step, they also construct a zero-knowledge proof that they performed their step correctly, then sends that proof along with the protocol message to their counterparty, who can use it to check that the message was correctly constructed. The counterparty can then produce a proof that they performed their step correctly, and so on.

The CMZ13 proofs used by Danake are instantiated using Merlin to perform the Fiat-Shamir transformation, modeling transcript using the duplex sponge construction. One emergent property of this design, as explained in the Merlin blog post, is that because the prover and verifier perform identical transcript operations, they can interactively compose intermediate proofs of correctness of each step into proofs of correctness of the entire protocol, without requiring any implementation changes to the proving functions.

This works as follows. Both counterparties (in this case, the client and issuer) maintain their own transcript states. When one party proves that they performed their step correctly, they mutate the state of their transcript away from the state of their counterparty’s transcript. But when their counterparty verifies the proof, the counterparty’s transcript state is mutated in the same way, bringing the two parties’ transcripts back into sync. Now the roles reverse, with the next proving phase mutating the transcript again, and the counterparty’s verification synchronizing the transcripts.

Notice that the proof of each step is a noninteractive proof, but because they’re made on the same transcript, they’re composed with all of the proofs from all prior steps, forming a chain of verifications of the entire protocol.

# Affine Credentials

One application of a keyed-verification credential system, anonymous or otherwise, is secure client-side encoding of a state machine. Rather than having a server maintain state for each client in a central database, a server can offload state to its clients, relying on the security of the credential to prevent clients from tampering with their state.

This is particularly interesting when the credential system is an anonymous credential system, because clients can prove statements about their (previously-authenticated) state in zero knowledge, rather than revealing the state itself.

However, usefully encoding a state machine requires creating credentials that can only be presented once. Borrowing terminology from substructural type systems, these could be called "affine credentials".

Extending CMZ13 credentials to have use-once semantics is easy, by adding a nullifier attribute to a credential. During issuance, clients generate a random nullifier and requests blinded issuance of a credential with that nullifier. During presentation, clients reveal the nullifier, allowing the issuer to perform a set membership query.

This approach gives a hard guarantee that credentials are not presented twice, at the cost of requiring the issuer to maintain a nullifier set. However, the nullifier set can be continually pruned using the epoch system described in the next section.

# Credential Epochs

One practical issue with CMZ13 credentials is that the issuer's secret key material must be kept online to verify previously-issued credentials, and it must outlive the lifetime of the longest-lived credential. The first factor increases the risk of key compromise, while the second factor means that unplanned key rotation is effectively impossible, as it requires coordination from all credential holders.

For this reason, it's important to integrate a notion of key rotation into the system from the beginning:

if you're always rotating credentials, then credential rotation is just another thing your system does -- it's not a special mode that you have to reason about. @endsofthreads

To do this, we treat each credential type $$T$$ as being a family of dependent types indexed by integers. Integers correspond to time intervals called epochs, and each type $$T_i$$ represents a credential of type $$T$$ in epoch $$i$$. Each CMZ13 credential is issued with respect to some issuance parameters, and each epoch $$i$$ has designated primary parameters for credentials of type $$T$$.

Next, we define a rollover procedure which allows a client to convert a credential of type $$T_i$$ into a credential of type $$T_{i+1}$$. To do this, the client simultaneously presents a credential of type $$T_i$$ and requests blinded issuance of a new credential of type $$T_{i+1}$$, while supplying a zero-knowledge proof that the requested attributes are identical to the previous credential's attributes. If the previous credential had a nullifier, the client reveals the nullifier of the previous credential and generates a new nullifier for the new credential.

However, for the issuer to accept the previous credential or to issue a new credential, the issuer must have issuance parameters for both epochs $$i$$ and $$i+1$$.1 And because presentations are prepared by the client, the client should ideally be able to determine an epoch to use for a presentation without having to agree on a clock. To address both of these issues, we adopt a key schedule loosely inspired by Google's Cloud KMS. In this schedule, issuance parameters can have the following states:

• Primary, meaning that these issuance parameters are the canonical issuance parameters for this epoch, and can be used for credential presentations and rollovers;
• Active, meaning that these issuance parameters are not the canonical issuance parameters for this epoch, but can still be used for credential presentations and rollovers;
• Rollover, meaning that these issuance parameters cannot be used for credential presentations except for rollovers.

Each set of issuance parameters passes through states Active, Primary, Active, and Rollover before deletion, as indicated in the following diagram:

        ─────────Epoch─────────────────▶
-3 -2 -1  0  1  2  3  4  5  6  7

│    A  P  A  R
│       A  P  A  R
│          A  P  A  R
│             A  P  A  R
Issuance            A  P  A  R
Parameters              A  P  A  R
│                      A  P  A  R
▼                         A  P  A  R


Because the issuer accepts credentials issued with respect to the primary parameters from both previous and subsequent epochs, the client and issuer do not need to agree on exactly when the epoch boundary occurs. By observing late use of old parameters or early use of new parameters respectively, the issuer can detect when a client's clock is slightly slower or slightly faster than the issuer's clock, but only for a limited time and a specific request, because either (in the slower case) the client will soon roll over their credential or (in the faster case) other clients will soon roll over their credentials.

Because the issuer parameters are declared in advance (they become active parameters before they become primary parameters), clients can fetch parameters in advance, either from the issuer or from a transparency log. This forces the issuer to commit to specific parameters and prevents key-partitioning attacks.

This design requires that every client is online at least once every four epochs. The epoch duration is a deployment-specific system parameter that should be chosen so that this assumption is reasonable. To make the epoch index easy to calculate, the reference epoch is set to start at UNIX timestamp 0, so that the current epoch index can be calculated by dividing a UNIX timestamp by the epoch duration in seconds.

When using credentials with nullifiers, as described in the previous section, each credential type $$T_i$$ has a distinct nullifier set, and this set must be preserved as long as the corresponding parameters are in Active, Primary, or Rollover states. However, as soon as the parameters expire, the nullifier set can be immediately deleted. In this way, the epoch system for key rotation also automatically prunes the nullifier sets for each credential. Moreover, although the nullifier sets for parameters in Active and Rollover states need to be retained, they are likely to be accessed less frequently, so that only the nullifier set for the Primary parameters is in the hot path.

1

In practice it makes more sense to define a map from $$T_i$$ to $$T_{i+k}$$ to allow $$k$$-step rollover in case a client was offline for more than one epoch.

# Wallet Credentials

The wallet credential has attributes $$(w, n)$$, where $$w$$ represents the wallet balance and $$n$$ is a nullifier.

# Key Generation

• Describe key generation.
• Expand secret key material from a seed so that secret keys serialize as 32 bytes?

# Wallet Issuance

1. Client. The client proceeds as follows.

1. The client uses the current time and the epoch duration to determine the current epoch index and appropriate issuance parameters.

2. The client generates a random nullifier $$n \xleftarrow{\} \mathbb F_p$$.

3. The client generates an ephemeral ElGamal public key $$d \xleftarrow{\} \mathbb F_p$$ and computes the ephemeral public key $$D \gets d B$$.

4. The client generates randomness $$r \xleftarrow{\} \mathbb F_p$$ and computes $\operatorname{Enc}_D(n B) \gets (r B, (n + rd)B).$

5. The client forms the proof \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{wallet::issuance::client}, \\ &(d, n, r), \\ &(D, \operatorname{Enc}_D(n B)), \\ &(B) \; : \\ &\operatorname{Enc}_D(n B) = (rB, nB + rD) \\ \}. \end{aligned} The proof transcript should additionally be bound to the current epoch index and the expected issuance parameters. The client keeps the transcript state while awaiting a response.

6. The client sends the epoch index, $$D$$, $$\operatorname{Enc}(nB)$$, $$\pi$$, and any other policy-dependent data relevant to the request to the issuer.

2. Issuer. The issuer processes the request as follows.

1. The issuer checks that the issuance parameters for the epoch index specified by the client are in Active or Primary state.

2. The issuer checks the policy-dependent data specified by the client or performs other policy checks, determining the issuance amount $$0 \le w < 2^{64}$$.

3. The issuer verifies the proof $$\pi$$ and saves the transcript state.

4. The issuer selects $$b \xleftarrow{\} \mathbb F_p$$ and computes $$P \gets bB$$.

5. The issuer computes $$Q_c \gets (x_0 + x_1 w) P$$.

6. The issuer selects randomness $$r \xleftarrow{\} \mathbb F_p$$ to compute $\operatorname{Enc}_D(Q) \gets (rB, Q_c + rD) + b x_2 \operatorname{Enc}_D(nB).$

7. The issuer forms the proof \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{wallet::issuance::issuer}, \\ &( b, r, \mathbf x, \widetilde x_0, t_2 ), \\ &( P, (wP), D, \operatorname{Enc}_D(nB), \operatorname{Enc}_D(Q), T_2 ), \\ &(\mathbf X, B, \widetilde B) \; : \\ & X_0 = x_0 B + \widetilde x_0 \widetilde B, \; X_1 = x_1 \widetilde B, \; X_2 = x_2 \widetilde B, \\ & P = bB, \\ & T_2 = bX_2, \; T_2 = t_2 \widetilde B, \\ & \operatorname{Enc}_D(Q) = (rB, x_0 P + x_1 (wP) + rD) + t_2 \operatorname{Enc}_D(nB) \\ \}. \end{aligned} This proof should be added to the transcript from step (2.3), chaining the issuer's proof onto the client's proof.

8. The issuer sends $$P$$, $$\operatorname{Enc}_D(Q)$$, $$T_2$$, and $$\pi$$ to the client.

3. Client. The client processes the response as follows:

1. The client uses the transcript state from step (1.5) to verify $$\pi$$.

2. The client decrypts $$Q$$ by computing $Q \gets \operatorname{Enc}_D(Q)_1 - d \operatorname{Enc}_D(Q)_0.$

# Wallet Rollover

To rollover a wallet credential to a new epoch, the client requests blinded issuance of a new credential with the same wallet balance and a new nullifier.

1. Client. Given the credential attributes $$(w,n)$$ and tag $$(P_0,Q_0)$$ for a previously-issued wallet credential, the client proceeds as follows, simultaneously preparing a presentation of the previous wallet credential and a request for blinded issuance of a new credential. The client:

1. Uses the current time and the epoch duration to determine the epoch index for the new credential, denoting by $$\mathbf X$$ the issuance parameters for the current credential's epoch and by $$\mathbf X'$$ the issuance parameters for the new credential's epoch.

2. Re-randomizes the tag, choosing $$t \xleftarrow{\} \mathbb F_p$$ and computing $$(P, Q) \gets (t P_0, t Q_0)$$.

3. Computes $$\operatorname{Com}(w) = w P + \widetilde w \widetilde B$$ using randomness $$\widetilde w \xleftarrow{\} \mathbb F_p$$.

4. Commits to $$Q$$ by choosing $$r_Q \xleftarrow{\} \mathbb F_p$$ and computing $$C_Q = Q + r_Q B$$.

5. Computes a correction term $$V \gets \widetilde w X_1 - rB$$.

6. Generates a random nullifier for the new credential, $$n' \xleftarrow{\} \mathbb F_p$$.

7. Generates an ephemeral ElGamal public key $$d \xleftarrow{\} \mathbb F_p$$ and computes the ephemeral public key $$D \gets d B$$.

8. Generates randomness $$r_n, r_w \xleftarrow{\} \mathbb F_p$$ and computes $\operatorname{Enc}_D(w B) \gets (r_w B, (w + r_w d)B)$ and $\operatorname{Enc}_D(n' B) \gets (r_n B, (n' + r_n d)B).$

9. Forms the following proof, which combines credential presentation and blinded issuance statements: \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{wallet::rollover::client}, \\ &(d, w, \widetilde w, n', r_Q, r_w, r_n), \\ &( D, \operatorname{Enc}_D(w B), \operatorname{Enc}_D(n' B), P, V, \operatorname{Com}(w) ), \\ &(B, \widetilde B) \; : \\ &\operatorname{Enc}_D(n' B) = (r_n B, n' B + r_n D) \\ &\operatorname{Enc}_D(w B) = (r_w B, w B + r_w D) \\ &\operatorname{Com}(w) = w P + \widetilde w \widetilde B \\ & V = \widetilde w X_1 - r_Q B \\ \}. \end{aligned} The proof transcript should additionally be bound to the epoch indexes of the current epoch and of the requested epoch. The client keeps the transcript state while awaiting a response.

10. Sends the pair of epoch indices, the old nullifier $$n$$, $$D$$, $$\operatorname{Enc}(n'B)$$, $$\operatorname{Enc}(wB)$$, $$\operatorname{Com}(w)$$, $$P$$, $$C_Q$$, and $$\pi$$ to the issuer.

2. Issuer. The issuer processes the request as follows. The issuer:

1. Checks that the issuance parameters for the old epoch index specified by the client are in Active, Primary, or Rollover state, and that the issuance parameters for the new epoch index specified by the client are in the Active or Primary state. The old parameters are denoted by $$(\mathbf X, \mathbf x)$$ and the new parameters are denoted by $$(\mathbf X', \mathbf x')$$.

2. Checks whether the nullifier $$n$$ is in the wallet nullifier set for the old epoch, rejecting the request if it is present and adding it to the nullifier set if it is not present.

3. Computes $$V$$ using the old secrets as $V \gets (x_0 + x_2 n) B + x_1 \operatorname{Com}(w) - C_Q.$

4. Verifies the proof $$\pi$$ and saves the transcript state.

5. Selects $$b \xleftarrow{\} \mathbb F_p$$ and computes $$P \gets bB$$.

6. Selects $$r \xleftarrow{\} \mathbb F_p$$ to compute $\operatorname{Enc}_D(Q) \gets (rB, x_0' P + rD) + b x_1' \operatorname{Enc}_D(wB) + b x_2' \operatorname{Enc}_D(n'B)$ using the new secrets.

7. The issuer forms the proof \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{wallet::rollover::issuer}, \\ &( b, r, \mathbf x, \widetilde x_0, \mathbf x', \widetilde x_0', t_1, t_2 ), \\ &( P, D, \operatorname{Enc}_D(wB), \operatorname{Enc}_D(n'B), \operatorname{Enc}_D(Q), T_1, T_2 ), \\ &(\mathbf X, \mathbf X', B, \widetilde B) \; : \\ & X_0 = x_0 B + \widetilde x_0 \widetilde B, \; X_1 = x_1 \widetilde B, \; X_2 = x_2 \widetilde B, \\ & X_0' = x_0' B + \widetilde x_0' \widetilde B, \; X_1' = x_1' \widetilde B, \; X_2' = x_2' \widetilde B, \\ & P = bB, \\ & T_1 = bX_1', \; T_1 = t_1 \widetilde B, \\ & T_2 = bX_2', \; T_2 = t_2 \widetilde B, \\ & \operatorname{Enc}_D(Q) = (rB, x_0' P + rD) + t_1 \operatorname{Enc}_D(wB) + t_2 \operatorname{Enc}_D(n'B) \\ \}. \end{aligned} This proof should be added to the transcript from step (2.4), chaining the issuer's proof onto the client's proof.

8. The issuer sends $$P$$, $$\operatorname{Enc}_D(Q)$$, $$T_1$$, $$T_2$$, and $$\pi$$ to the client.

3. Client. The client processes the response as follows:

1. The client uses the transcript state from step (1.9) to verify $$\pi$$.

2. The client decrypts $$Q$$ by computing $Q \gets \operatorname{Enc}_D(Q)_1 - d \operatorname{Enc}_D(Q)_0.$

# Topup

Wallet topup allows a client to add credit to their wallet credential, revealing the credit increase (so that the issuer can check that the increase is in line with application-specific policy) but hiding the old and new balances.

1. Client. Given the credit topup amount $$c$$ as well as credential attributes $$(w,n)$$ and tag $$(P_0,Q_0)$$ for a previously-issued wallet credential, the client proceeds as follows, simultaneously preparing a presentation of the previous wallet credential and a request for blinded issuance of a new credential with balance $$w' = w + c$$. The client:

1. Uses the current time and the epoch duration to determine the current epoch index. If the existing credential's issuance parameters are not the primary issuance parameters for the current epoch, perform a rollover to the current parameters and restart the protocol.

2. Re-randomizes the tag, choosing $$t \xleftarrow{\} \mathbb F_p$$ and computing $$(P, Q) \gets (t P_0, t Q_0)$$.

3. Chooses randomness $$\widetilde w \xleftarrow{\} \mathbb F_p$$ and computes $$\operatorname{Com}(w) \gets w P + \widetilde w \widetilde B$$ and $$\operatorname{Com}(w') \gets w' P + \widetilde w \widetilde B$$.

4. Commits to $$Q$$ by choosing $$r_Q \xleftarrow{\} \mathbb F_p$$ and computing $$C_Q = Q + r_Q B$$.

5. Computes a correction term $$V \gets \widetilde w X_1 - rB$$.

6. Generates a random nullifier for the new credential, $$n' \xleftarrow{\} \mathbb F_p$$.

7. Generates an ephemeral ElGamal public key $$d \xleftarrow{\} \mathbb F_p$$ and computes the ephemeral public key $$D \gets d B$$.

8. Generates randomness $$r_n, r_w \xleftarrow{\} \mathbb F_p$$ and computes $\operatorname{Enc}_D(w' B) \gets (r_w B, (w' + r_w d)B)$ and $\operatorname{Enc}_D(n' B) \gets (r_n B, (n' + r_n d)B).$

9. Forms the following proof, combining credential presentation and blinded issuance: \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{wallet::topup::client}, \\ &(d, w, w', \widetilde w, n', r_Q, r_w, r_n), \\ &( D, \operatorname{Enc}_D(w' B), \operatorname{Enc}_D(n' B), P, V, \operatorname{Com}(w), \operatorname{Com}(w') ), \\ &(B, \widetilde B, \mathbf X) \; : \\ &D = d B \\ &\operatorname{Enc}_D(n' B) = (r_n B, n' B + r_n D) \\ &\operatorname{Enc}_D(w' B) = (r_w B, w' B + r_w D) \\ &\operatorname{Com}(w) = w P + \widetilde w \widetilde B \\ &\operatorname{Com}(w') = w' P + \widetilde w \widetilde B \\ & V = \widetilde w X_1 - r_Q B \\ \}. \end{aligned} The client retains the transcript state for the next step.

10. Using the same transcript, forms a rangeproof $$\rho$$ proving that $$\operatorname{Com}(w')$$ commits to a value in range $$[0,2^{64})$$, and retains the transcript state.

11. Sends the epoch index, the old nullifier $$n$$, $$D$$, $$\operatorname{Enc}(n'B)$$, $$\operatorname{Enc}(w'B)$$, $$\operatorname{Com}(w)$$, $$P$$, $$C_Q$$, $$\pi$$, and $$\rho$$ to the issuer.

2. Issuer. The issuer proceeds as follows. The issuer:

1. Checks the requested credit amount $$c$$ according to application policy.

2. Checks that the issuance parameters for the epoch index selected by the client are in Active or Primary state.

3. Checks whether the nullifier $$n$$ is in the wallet nullifier set for the selected epoch, rejecting the request if it is present and adding it to the nullifier set if it is not present.

4. Computes $$V$$ as $V \gets (x_0 + x_2 n) B + x_1 \operatorname{Com}(w) - C_Q.$

5. Computes $$\operatorname{Com}(w') \gets \operatorname{Com}(w) + cP$$.

6. Verifies the proof $$\pi$$ and retains the transcript state.

7. Verifies the proof $$\rho$$ and retains the transcript state.

8. Selects $$b \xleftarrow{\} \mathbb F_p$$ and computes $$P \gets bB$$.

9. Selects $$r \xleftarrow{\} \mathbb F_p$$ to compute $\operatorname{Enc}_D(Q) \gets (rB, x_0 P + rD) + b x_1 \operatorname{Enc}_D(w'B) + b x_2 \operatorname{Enc}_D(n'B).$

10. The issuer forms the proof \begin{aligned} \pi &\gets \operatorname{PK}\{ \\ &\mathtt{wallet::topup::issuer}, \\ &( b, r, \mathbf x, \widetilde x_0, t_1, t_2 ), \\ &( P, D, \operatorname{Enc}_D(w'B), \operatorname{Enc}_D(n'B), \operatorname{Enc}_D(Q), T_1, T_2 ), \\ &(\mathbf X, B, \widetilde B) \; : \\ & X_0 = x_0 B + \widetilde x_0 \widetilde B, \; X_1 = x_1 \widetilde B, \; X_2 = x_2 \widetilde B, \\ & P = bB, \\ & T_1 = bX_1', \; T_1 = t_1 \widetilde B, \\ & T_2 = bX_2', \; T_2 = t_2 \widetilde B, \\ & \operatorname{Enc}_D(Q) = (rB, x_0 P + rD) + t_1 \operatorname{Enc}_D(w'B) + t_2 \operatorname{Enc}_D(n'B) \\ \}. \end{aligned} This proof should be added to the transcript from step (2.7), chaining the issuer's proof onto the client's proofs.

11. The issuer sends $$P$$, $$\operatorname{Enc}_D(Q)$$, $$T_1$$, $$T_2$$, and $$\pi$$ to the client.

3. Client. The client processes the response as follows:

1. The client uses the transcript state from step (1.10) to verify $$\pi$$.

2. The client decrypts $$Q$$ by computing $Q \gets \operatorname{Enc}_D(Q)_1 - d \operatorname{Enc}_D(Q)_0.$

# Implementation

Danake is implemented in Rust. The proof statements are written declaratively, using the zkp crate to automatically derive implementations of each proof statement. Rangeproofs are provided by the bulletproofs library, and they are composed with the other proof statements using Merlin transcripts. Both the Bulletproofs and the Schnorr proofs generated by zkp use the ristretto255 group, as implemented in curve25519-dalek.

# Implementation status

## Core functionality

• Wallet functionality
• keygen
• issuance
• rollover
• topup
• Token functionality
• keygen
• purchase
• rollover
• spend
• Proper transcript design
• Nullifier queries (double-spend prevention)
• Epoch-aware keygen (should be able to generate keys for every epoch from a single root key)
• Simulator
• Arbitrary impl generating a stream of protocol events
• proptest checker for event streams

## Integrations

These would make Danake more practically useful:

• danake-proxy: reverse proxy that sits in front of an HTTP service and meters an HTTP API.

# Performance

Performance numbers are TBD based on implementation work. However, early prototypes suggest the following approximate server-side costs:

• Wallet topup: one set membership query plus less than 9 million Skylake cycles (3ms at 3GHz).
• Token spend: one set membership query plus less than 6 million Skylake cycles (2ms at 3GHz).

# Unresolved Questions

## Parameter Transparency

Ideally, the issuer should commit issuance parameters to a transparency log that clients can check independently -- could the issuer bundle parameters with proofs-of-inclusion?

## Transport Reliability

Currently Danake assumes a reliable transport; if a wallet transaction is dropped and the response is never received by the client, the client may be left hanging (having spent their previous token). There are a few workarounds for this (e.g., allowing clients to re-download the results of issuance?) and one of them should be chosen.

## Interaction with HTTP semantics

Ideally, Danake payments should be fast enough to allow billing of every HTTP request. One form this could take would be a danake-proxy that sits in front of a web application and inspects HTTP headers. How can this be made to interact properly with HTTP semantics around idempotency, etc? How can this be implemented on the client?

# (WIP) Related Work

This page contains an incomplete list of related work. In the future, it will be expanded to have more detailed comparisons.

## Privacy Pass

Privacy Pass is a privacy-preserving authentication protocol developed by George Tankersley, Filippo Valsorda, Alex Davidson, Ian Goldberg, and Nick Sullivan. Privacy Pass allows users to request single-use "tokens" from a server and redeem them unlinkably from their issuance. For instance, a user can obtain a collection of single-use tokens by solving a CAPTCHA, and later present those tokens to access web resources. This page contains a description of the protocol and various attack vectors.

In comparison to Danake tokens, which store a balance that can be drawn down in multiple spend transactions of different amounts, Privacy Pass tokens can be redeemed only once for an indivisible unit value. However, Danake's flexibility comes at a cost, as Privacy Pass redemptions are more efficient for the server.

## OpenPrivacy's Privacy Pass Extensions

Erinn Atwater and Sarah Jamie Lewis of OpenPrivacy are developing [extensions] to Privacy Pass which allow tokens to be purchased anonymously using cryptocurrency (e.g., shielded Zcash). These tokens can then be unlinkably redeemed for anonymous servers. This is the same use-case and threat model as Danake (TODO: check), but with more efficient token redemption.

## Brave's Privacy Pass Extensions

Brave has a design for using Privacy Pass for privacy-preserving ad confirmations (authors?). Because Privacy Pass tokens have unit value, they suggest using different (domain-separated) token issuers to correspond to each token value denomination.

## BOLT

BOLT is a "Layer 2" system which provides privacy-preserving off-chain payment channels with escrowed funds. Either counterparty can close the channel and obtain their funds net of whatever payments occurred. This is a more sophisticated threat model than Danake, where the service provider issues credit according to arbitrary policy and is trusted to redeem credit.

## Hyphae

Hyphae was an unimplemented design by Henry de Valence and Isis Lovecruft for an anonymous reputation-based distribution network for Tor bridges. It contains precursor ideas to Danake, in particular an AMACS-based micropayment system, but without credential epochs, key rotation, the wallet/token distinction, or Bulletproofs.