Anonymous Credit Tokens

1.1. Key Properties

The protocol provides the following properties:¶

1. Unlinkability: The issuer cannot link credit issuance to spending, or connect multiple transactions by the same client. This property is information-theoretic, not merely computational.¶

2. Partial Spending: Clients can spend any amount up to their balance and receive anonymous change without revealing their previous or current balance, enabling flexible spending.¶

3. Double-Spend Prevention: Cryptographic nullifiers ensure each token is used only once, without linking it to issuance.¶

4. Balance Privacy: During spending, only the amount being spent is revealed, not the total balance in the token, protecting clients from balance-based profiling.¶

The design of the protocol also takes efficiency and simplicity into consideration, making it suitable for high-volume web services and straightforward to implement.¶

1.2. Use Cases

Anonymous Credit Tokens can be applied to various scenarios:¶

• Rate Limiting: Services can issue daily credit allowances that clients spend anonymously for API calls or resource access.¶

• API Credits: API providers can sell credit packages that developers use to pay for API requests without creating a detailed usage history linked to their identity. This enables:¶

  • Pre-paid API access without requiring credit cards for each transaction¶

  • Anonymous API usage for privacy-sensitive applications¶

  • Usage-based billing without tracking individual request patterns¶

  • Protection against competitive analysis through usage monitoring¶

1.3. Protocol Overview

The protocol involves two parties: an issuer (typically a service provider) and clients (typically users of the service). The interaction follows three main phases:¶

1. Setup: The issuer generates a key pair and publishes the public key.¶

2. Issuance: A client requests credits from the issuer. The issuer creates a blind signature on the credit value and a client-chosen nullifier, producing a credit token.¶

3. Spending: To spend credits, the client reveals a nullifier and proves possession of a valid token associated with that nullifier having sufficient balance. The issuer verifies the proof, checks the nullifier hasn't been used before, and issues a new token (which remains hidden from the issuer) for any remaining balance.¶

1.4. Relation to Existing Work

This protocol builds upon several cryptographic primitives:¶

• BBS Signatures [BBS]: The core signature scheme that enables efficient proofs of possession. We use a variant that is privately verifiable, which avoids the need for pairings and makes our protocol more efficient.¶

• Sigma Protocols [SIGMA]: The zero-knowledge proof framework used for issuing and spending credits.¶

• Fiat-Shamir Transform [FIAT-SHAMIR]: The technique to make the interactive proofs non-interactive.¶

The protocol can be viewed as a specialized instantiation of keyed-verification anonymous credentials [KVAC] optimized for numerical values and partial spending.¶

2.1. Notation

This document uses the following notation:¶

• ||: Concatenation of byte arrays.¶

• x <- S: Uniformly sampling x from the set S using rng.random_scalar().¶

• x = y: Assignment of the value y to the variable x.¶

• [n]: The set of integers {0, 1, ..., n-1}.¶

• |x|: The length of byte array x.¶

• 0x is a prefix to denote integer values in hexadecimal base.¶

• We use additive notation for group operations, so group elements are added together like a + b and scalar multiplication of a group element by a scalar is written as a * n, with group element a and scalar n.¶

The protocol uses the following data types:¶

• Byte Array: A sequence of bytes.¶

• Group: An interface of a prime-order group as defined in Section 2.1 of [RFC9497].¶

• Group Element: An element of the group.¶

• Scalar: An element from the scalar field of the group.¶

• PRNG: An interface for a cryptographically secure pseudorandom number generator with a random_scalar() -> Scalar method. The PRNG MUST be backed by a CSPRNG in accordance with [FIPS186]. See Appendix B for the abstract interface definition.¶

• LinearRelation: An interface for building an interactive sigma protocol as defined in Section 2.2.6 of [SIGMA].¶

• NISigmaProtocol: An interface that implements the Fiat-Shamir transform as defined in Section 5 of [FIAT-SHAMIR]. This interface is parametrized with a Codec that encodes prover messages and verifier challenges, and a function used to compute challenges. See [FIAT-SHAMIR] for requirements of these parameters.¶

The specific parameters and implementations are defined in Section 6.¶

2.2. Zero-knowledge Proofs of Knowledge

Proofs of knowledge are based on interactive sigma protocols, which are made non-interactive through the Fiat-Shamir transform [FST]. The concrete proofs use the LinearRelation and NISigmaProtocol interfaces defined above.¶

The NISigmaProtocol requires a session identifier that uniquely identifies the session being proven. Once initialized, the Prover can generate proofs of knowledge of a witness satisfying the statement, while the Verifier can validate these proofs.¶

append_pedersen(statement, P, Q, R):
  Input:
    - statement: LinearRelation.
    - P: Group Element.
    - Q: Group Element.
    - R: Group Element.

  Steps:
    1. k0_var, k1_var = statement.allocate_scalars(2)
    2. P_var, Q_var, R_var = statement.allocate_elements(3)
    3. statement.append_equation(R_var, [(k0_var, P_var), (k1_var, Q_var)])
    4. statement.set_elements([(P_var, P), (Q_var, Q), (R_var, R)])

append_dleq(statement, P, Q, X, Y):
  Input:
    - statement: LinearRelation.
    - P: Group Element.
    - Q: Group Element.
    - X: Group Element.
    - Y: Group Element.

  Steps:
    1. k_var = statement.allocate_scalars(1)
    2. P_var, Q_var, X_var, Y_var = statement.allocate_elements(4)
    3. statement.append_equation(X_var, [(k_var, P_var)])
    4. statement.append_equation(Y_var, [(k_var, Q_var)])
    5. statement.set_elements([(P_var, P), (Q_var, Q), (X_var, X), (Y_var, Y)])

append_range_proof(statement, H1, H2, H3, Com, L):
  Input:
    - statement: LinearRelation.
    - H1: Group Element.
    - H2: Group Element.
    - H3: Group Element.
    - Com: Array of L Group Elements (bit commitments).
    - L: Integer (bit length).
  Output:
    - b_vars: Array of L scalar variable handles.
    - s_vars: Array of L scalar variable handles.
    - s2_vars: Array of L scalar variable handles.
    - kstar_var: Scalar variable handle.
    - k2_var: Scalar variable handle.

  Steps:
    // Allocate scalar variables
    1. b_vars = statement.allocate_scalars(L)
    2. s_vars = statement.allocate_scalars(L)
    3. s2_vars = statement.allocate_scalars(L)
    4. kstar_var, k2_var = statement.allocate_scalars(2)

    // Allocate element variables
    5. H1_var, H2_var, H3_var = statement.allocate_elements(3)
    6. Com_vars = statement.allocate_elements(L)

    // Set element values
    7. statement.set_elements([(H1_var, H1), (H2_var, H2),
         (H3_var, H3)])
    8. For j = 0 to L-1:
    9.     statement.set_elements([(Com_vars[j], Com[j])])

    // Bit 0: opening equation
    // Com[0] = b[0]*H1 + kstar*H2 + s[0]*H3
   10. statement.append_equation(Com_vars[0],
         [(b_vars[0], H1_var), (kstar_var, H2_var), (s_vars[0], H3_var)])

    // Bit 0: binary constraint equation
    // Com[0] = b[0]*Com[0] + k2*H2 + s2[0]*H3
   11. statement.append_equation(Com_vars[0],
         [(b_vars[0], Com_vars[0]), (k2_var, H2_var),
          (s2_vars[0], H3_var)])

    // Bits 1 to L-1
   12. For j = 1 to L-1:
         // Opening equation: Com[j] = b[j]*H1 + s[j]*H3
   13.     statement.append_equation(Com_vars[j],
             [(b_vars[j], H1_var), (s_vars[j], H3_var)])
         // Binary constraint: Com[j] = b[j]*Com[j] + s2[j]*H3
   14.     statement.append_equation(Com_vars[j],
             [(b_vars[j], Com_vars[j]), (s2_vars[j], H3_var)])

   15. return (b_vars, s_vars, s2_vars, kstar_var, k2_var)

3.1. System Parameters

Each instance of the protocol defines the following parameters:¶

• domain_separator is a non-empty byte array that uniquely identifies an instance of the protocol. It ensures cryptographic separation between different ACT instances.¶

• L is the bit length for representing credit values, such that L <= MAX_BIT_LENGTH, where MAX_BIT_LENGTH is defined per suite.¶

• H1, H2, H3, H4 are auxiliary group generators used for commitments. H4 is used for binding a request context. The SetGenerators function deterministically generates them through hashing. The discrete-logarithm relations between any pair of these generators and the main generator MUST NOT be known to any party. The SetGenerators function achieves this by deriving each generator independently via HashToGroup with distinct domain separation tags and verifying pairwise distinctness. This prevents attacks whereby malicious parameters could compromise security.¶

SetGenerators(G, domain_separator):
  Input:
    - G: Group.
    - domain_separator: Byte Array.
  Output:
    - H1, H2, H3, H4: Group Element.

  Steps:
    1. G0 = G.Generator()
    2. H1, H2, H3, H4 = [G0]*4
    3. counter = 0
    4. while len({G0, H1, H2, H3, H4}) < 5:
    5.   ctr = I2OSP(counter, 1)
    6.   H1 = G.HashToGroup("GenH1" || ctr || domain_separator)
    7.   H2 = G.HashToGroup("GenH2" || ctr || domain_separator)
    8.   H3 = G.HashToGroup("GenH3" || ctr || domain_separator)
    9.   H4 = G.HashToGroup("GenH4" || ctr || domain_separator)
   10.   counter += 1
   11. return H1, H2, H3, H4

The domain_separator SHOULD follow this structured format:¶

domain_separator = "ACT-v1:" || organization || ":" || service || ":" || deployment_id || ":" || version

where:¶

• organization: A unique identifier for the organization (e.g., "example-corp", "acme-inc").¶

• service: The specific service or application name (e.g., "payment-api", "rate-limiter").¶

• deployment_id: The deployment environment (e.g., "production", "staging", "us-west-1").¶

• version: An ISO 8601 date (YYYY-MM-DD) indicating when parameters were generated.¶

Example: "ACT-v1:example-corp:payment-api:production:2024-01-15"¶

This structured format ensures:¶

1. Protocol identification through the "ACT-v1:" prefix¶

2. Organizational namespace isolation¶

3. Service-level separation within organizations¶

4. Environment isolation (production vs staging)¶

5. Version tracking for parameter updates¶

Using generic or unstructured domain separators creates security risks through parameter collision and MUST NOT be used. When parameters need to be updated (e.g., for security reasons or protocol upgrades), a new version date MUST be used, creating entirely new parameters.¶

3.2. Key Generation

The issuer generates a key pair as follows:¶

KeyGen(G, rng):
  Input:
    - G: Group.
    - rng: PRNG.
  Output:
    - sk: Scalar.        # Private key
    - pk: Group Element. # Public key

  Steps:
    1. sk = rng.random_scalar()
    2. pk = sk * G.Generator()
    3. return sk, pk

3.3. Token Issuance

The issuance protocol is an interactive protocol between a client and the issuer:¶

IssueRequest(rng):
  Input:
    - rng: PRNG.
  Output:
    - request: Issuance request
    - state: Client state for later verification

  Steps:
    1. k <- Zq  // Nullifier (will prevent double-spending)
    2. r <- Zq  // Blinding factor
    3. K = H2 * k + H3 * r

    // Generate proof of knowledge of (k, r) such that K = H2 * k + H3 * r
    4. statement = LinearRelation(group)
    5. append_pedersen(statement, H2, H3, K)
    6. session_id = domain_separator + "request"
    7. prover = NISigmaProtocol(session_id, statement)
    8. witness = [k, r]
    9. pok = prover.prove(witness, rng)
   10. request = (K, pok)
   11. state = (k, r, K)
   12. return (request, state)

IssueResponse(sk, request, c, ctx, rng):
  Input:
    - sk: Issuer's private key
    - request: Client's issuance request
    - c: Credit amount to issue (c >= 0)
    - ctx: Request context scalar
    - rng: PRNG.
  Output:
    - response: Issuance response
  Exceptions:
    - InvalidIssuanceRequestProof, raised when the client proof verification fails

  Steps:
    // Verify proof of knowledge of (k, r) such that K = H2 * k + H3 * r
    1. Parse request as (K, pok)
    2. statement = LinearRelation(group)
    3. append_pedersen(statement, H2, H3, K)
    4. session_id = domain_separator + "request"
    5. verifier = NISigmaProtocol(session_id, statement)
    6. if not verifier.verify(pok):
    7.     raise InvalidIssuanceRequestProof

    // Create BBS signature on (c, ctx, k, r)
    8. e <- Zq
    9. X_A = G.Generator() + H1 * c + H4 * ctx + K    // K = H2 * k + H3 * r
   10. A = X_A * (1/(e + sk))
   11. X_G = G.Generator() * (e + sk)

   // Generate proof of knowledge of (e+sk) such that X_A = A * (e+sk) and X_G = G.Generator() * (e+sk)
   12. statement = LinearRelation(group)
   13. append_dleq(statement, A, G.Generator(), X_A, X_G)
   14. session_id = domain_separator + "respond" + Encode(c) + Encode(ctx)
   15. prover = NISigmaProtocol(session_id, statement)
   16. witness = [e + sk]
   17. pok = prover.prove(witness, rng)
   18. response = (A, e, c, pok)
   19. return response

VerifyIssuance(pk, response, ctx, state):
  Input:
    - pk: Issuer's public key
    - response: Issuer's response
    - ctx: Request context scalar
    - state: Client state from request generation
  Output:
    - token: Credit token
  Exceptions:
    - InvalidIssuanceResponseProof, raised when the server proof verification fails

  Steps:
    1. Parse response as (A, e, c, pok)
    2. Parse state as (k, r, K)

    // Verify proof of knowledge of (e+sk) such that X_A = A * (e+sk) and X_G = G.Generator() * (e+sk)
    3. X_A = G.Generator() + H1 * c + H4 * ctx + K
    4. X_G = G.Generator() * e + pk
    5. statement = LinearRelation(group)
    6. append_dleq(statement, A, G.Generator(), X_A, X_G)
    7. session_id = domain_separator + "respond" + Encode(c) + Encode(ctx)
    8. verifier = NISigmaProtocol(session_id, statement)
    9. if not verifier.verify(pok):
   10.     raise InvalidIssuanceResponseProof
   11. token = (A, e, k, r, c, ctx)
   12. return token

3.4. Token Spending

The spending protocol allows a client to spend s credits from a token containing c credits (where 0 <= s <= c):¶

ProveSpend(token, s, rng):
  Input:
    - token: Credit token (A, e, k, r, c, ctx)
    - s: Amount to spend (0 <= s <= c)
    - rng: PRNG.
  Output:
    - proof: Spend proof
    - state: Client state for receiving change

  Steps:
    // Randomize the signature
    1. r1, r2 <- Zq
    2. B = G.Generator() + H1 * c + H2 * k + H3 * r + H4 * ctx
    3. A' = A * (r1 * r2)
    4. B_bar = B * r1
    5. r3 = 1/r1

    // Decompose c - s into bits and create commitments
    6. m = c - s
    7. (b[0], ..., b[L-1]) = BitDecompose(m)
    8. kstar <- Zq
    9. s_com[0] <- Zq
   10. Com[0] = H1 * b[0] + H2 * kstar + H3 * s_com[0]
   11. For j = 1 to L-1:
   12.     s_com[j] <- Zq
   13.     Com[j] = H1 * b[j] + H3 * s_com[j]

    // Compute derived public values
   14. A_bar = B_bar * r2 - A' * e  // Equivalent to A' * sk
   15. H1_prime = G.Generator() + H2 * k + H4 * ctx
   16. For j = 0 to L-1:
   17.     s2[j] = (1 - b[j]) * s_com[j]
   18. k2 = (1 - b[0]) * kstar

    // Build LinearRelation statement
   19. statement = LinearRelation(group)

    // Eq 1: A_bar = e*(-A') + r2*B_bar
    // (Rearranged BBS signature validity)
   20. e_var, r2_var = statement.allocate_scalars(2)
   21. negA_var, B_bar_var, A_bar_var = statement.allocate_elements(3)
   22. statement.append_equation(A_bar_var,
         [(e_var, negA_var), (r2_var, B_bar_var)])
   23. statement.set_elements([(negA_var, -A'),
         (B_bar_var, B_bar), (A_bar_var, A_bar)])

    // Eq 2: H1_prime = r3*B_bar + c*(-H1) + r*(-H3)
    // (Credential structure)
   24. r3_var, c_var, r_var = statement.allocate_scalars(3)
   25. negH1_var, negH3_var, H1p_var = statement.allocate_elements(3)
   26. statement.append_equation(H1p_var,
         [(r3_var, B_bar_var), (c_var, negH1_var), (r_var, negH3_var)])
   27. statement.set_elements([(negH1_var, -H1),
         (negH3_var, -H3), (H1p_var, G.Generator() + H2 * k + H4 * ctx)])

    // Eqs 3..2+2L: Range proof (2L equations)
   28. (b_vars, s_com_vars, s2_vars, kstar_var, k2_var) =
         append_range_proof(statement, H1, H2, H3, Com, L)

    // Eq 2L+3: Commitment consistency
    // Com_total = c*H1 + kstar*H2 + sum(s_com[j]*2^j*H3)
   29. Com_total = H1 * s + Sum(Com[j] * 2^j for j in [L])
   30. H1_var2, H2_var2, Com_total_var = statement.allocate_elements(3)
   31. statement.set_elements([(H1_var2, H1), (H2_var2, H2),
         (Com_total_var, Com_total)])
   32. terms = [(c_var, H1_var2), (kstar_var, H2_var2)]
   33. For j = 0 to L-1:
   34.     coeff_H3_var = statement.allocate_elements(1)
   35.     statement.set_elements([(coeff_H3_var, H3 * (2^j))])
   36.     terms.append((s_com_vars[j], coeff_H3_var))
   37. statement.append_equation(Com_total_var, terms)

    // Assemble witness (indexed by allocated scalar variables)
   38. witness[e_var] = e
   39. witness[r2_var] = r2
   40. witness[r3_var] = r3
   41. witness[c_var] = c
   42. witness[r_var] = r
   43. For j = 0 to L-1:
   44.     witness[b_vars[j]] = b[j]
   45.     witness[s_com_vars[j]] = s_com[j]
   46.     witness[s2_vars[j]] = s2[j]
   47. witness[kstar_var] = kstar
   48. witness[k2_var] = k2

    // Generate non-interactive proof
   49. session_id = domain_separator + "spend" + Encode(k) + Encode(ctx)
   50. prover = NISigmaProtocol(session_id, statement)
   51. pok = prover.prove(witness, rng)

    // Construct output
   52. r_star = sum(s_com[j] * 2^j for j in [L])
   53. proof = (k, s, ctx, A', B_bar, Com, pok)
   54. state = (kstar, r_star, m, ctx)
   55. return (proof, state)

VerifyAndRefund(sk, proof, t, rng):
  Input:
    - sk: Issuer's private key
    - proof: Client's spend proof
    - t: Partial refund amount (0 <= t <= s)
    - rng: PRNG.
  Output:
    - refund: Refund for remaining credits
  Exceptions:
    - DoubleSpendError: raised when the nullifier has been used before
    - InvalidSpendProof: raised when the spend proof verification fails
    - InvalidRefundAmount: raised when t > s or t does not fit in L bits

  Steps:
    1. Parse proof and extract nullifier k, spend amount s, and ctx
    // Validate refund amount
    2. if t > s:
    3.     raise InvalidRefundAmount
    4. if t >= 2^L:
    5.     raise InvalidRefundAmount
    // The following steps (6-11) MUST be performed atomically
    // to prevent double-spending via race conditions.
    6. // Check nullifier hasn't been used
    7. if k in used_nullifiers:
    8.     raise DoubleSpendError
    // Verify the proof; raises IdentityPointError or
    // InvalidClientSpendProof on failure (see VerifySpendProof)
    9. VerifySpendProof(sk, proof)
   10. // Record nullifier
   11. used_nullifiers.add(k)
   12. // Issue refund for remaining balance
   13. K' = Sum(Com[j] * 2^j for j in [L])
   14. refund = IssueRefund(sk, K', t, ctx, rng)
   15. return refund

IssueRefund(sk, K', t, ctx, rng):
  Input:
    - sk: Issuer's private key
    - K': Commitment to remaining balance and new nullifier
    - t: Partial refund amount
    - ctx: Request context scalar
    - rng: PRNG.
  Output:
    - refund: Refund response

  Steps:
    // Create new BBS signature on remaining balance
    1. e <- Zq
    2. X_A = G.Generator() + K' + H1 * t + H4 * ctx
    3. A = X_A * (1/(e + sk))
    4. X_G = G.Generator() * (e + sk)

    // Generate proof of knowledge of (e + sk) such that X_A = A * (e + sk) and X_G = G.Generator() * (e + sk)
    5. statement = LinearRelation(group)
    6. append_dleq(statement, A, G.Generator(), X_A, X_G)
    7. session_id = domain_separator + "refund" + Encode(e) + Encode(t) + Encode(ctx)
    8. prover = NISigmaProtocol(session_id, statement)
    9. witness = [e + sk]
   10. pok = prover.prove(witness, rng)
   11. refund = (A, e, t, pok)
   12. return refund

ConstructRefundToken(pk, spend_proof, refund, state):
  Input:
    - pk: Issuer's public key
    - spend_proof: The spend proof sent to issuer
    - refund: Issuer's refund response
    - state: Client state (k*, r*, m, ctx)
  Output:
    - token: New credit token or INVALID
  Exceptions:
    - InvalidRefundProof: When the refund proof verification fails
    - InvalidRefundAmount: When t does not fit in L bits or m+t does not fit in L bits

  Steps:
    1. Parse refund as (A, e, t, pok)
    2. Parse state as (k*, r*, m, ctx)

    // Validate t fits in L bits
    3. if t >= 2^L:
    4.     raise InvalidRefundAmount

    // Compute new balance
    5. new_balance = m + t

    // Validate new balance fits in L bits
    6. if new_balance >= 2^L:
    7.     raise InvalidRefundAmount

    // Reconstruct commitment
    8. K' = Sum(spend_proof.Com[j] * 2^j for j in [L])
    9. X_A = G.Generator() + K' + H1 * t + H4 * ctx
   10. X_G = G.Generator() * e + pk

    // Verify proof of knowledge of (e + sk) such that X_A = A * (e + sk) and X_G = G.Generator() * (e + sk)
   11. statement = LinearRelation(group)
   12. append_dleq(statement, A, G.Generator(), X_A, X_G)
   13. session_id = domain_separator + "refund" + Encode(e) + Encode(t) + Encode(ctx)
   14. verifier = NISigmaProtocol(session_id, statement)
   15. if not verifier.verify(pok):
   16.     raise InvalidRefundProof

   // Construct new token
   17. token = (A, e, k*, r*, new_balance, ctx)
   18. return token

VerifySpendProof(sk, proof):
  Input:
    - sk: Issuer's private key
    - proof: Spend proof from client
  Exceptions:
    - IdentityPointError: raised when A' is the identity
    - InvalidClientSpendProof: raised when the proof verification fails

  Steps:
    1. Parse proof as (k, s, ctx, A', B_bar, Com, pok)

    // Check A' is not identity
    2. if A' == Identity:
    3.     raise IdentityPointError

    // Compute issuer's view
    4. A_bar = A' * sk
    5. H1_prime = G.Generator() + H2 * k + H4 * ctx
    6. Com_total = H1 * s + Sum(Com[j] * 2^j for j in [L])

    // Build the same LinearRelation as ProveSpend
    7. statement = LinearRelation(group)

    // Eq 1: A_bar = e*(-A') + r2*B_bar
    8. e_var, r2_var = statement.allocate_scalars(2)
    9. negA_var, B_bar_var, A_bar_var = statement.allocate_elements(3)
   10. statement.append_equation(A_bar_var,
         [(e_var, negA_var), (r2_var, B_bar_var)])
   11. statement.set_elements([(negA_var, -A'),
         (B_bar_var, B_bar), (A_bar_var, A_bar)])

    // Eq 2: H1_prime = r3*B_bar + c*(-H1) + r*(-H3)
   12. r3_var, c_var, r_var = statement.allocate_scalars(3)
   13. negH1_var, negH3_var, H1p_var = statement.allocate_elements(3)
   14. statement.append_equation(H1p_var,
         [(r3_var, B_bar_var), (c_var, negH1_var), (r_var, negH3_var)])
   15. statement.set_elements([(negH1_var, -H1),
         (negH3_var, -H3), (H1p_var, H1_prime)])

    // Eqs 3..2+2L: Range proof (2L equations)
   16. (b_vars, s_com_vars, s2_vars, kstar_var, k2_var) =
         append_range_proof(statement, H1, H2, H3, Com, L)

    // Eq 2L+3: Commitment consistency
   17. H1_var2, H2_var2, Com_total_var = statement.allocate_elements(3)
   18. statement.set_elements([(H1_var2, H1), (H2_var2, H2),
         (Com_total_var, Com_total)])
   19. terms = [(c_var, H1_var2), (kstar_var, H2_var2)]
   20. For j = 0 to L-1:
   21.     coeff_H3_var = statement.allocate_elements(1)
   22.     statement.set_elements([(coeff_H3_var, H3 * (2^j))])
   23.     terms.append((s_com_vars[j], coeff_H3_var))
   24. statement.append_equation(Com_total_var, terms)

    // Verify non-interactive proof
   25. session_id = domain_separator + "spend" + Encode(k) + Encode(ctx)
   26. verifier = NISigmaProtocol(session_id, statement)
   27. if not verifier.verify(pok):
   28.     raise InvalidClientSpendProof

3.5. Cryptographic Primitives

Encode(value):
  Input:
    - value: Element or Scalar
  Output:
    - encoding: ByteString

  Steps:
    1. If value is an Element:
    2.     return SerializeElement(value)  // Ne bytes
    3. If value is a Scalar:
    4.     return SerializeScalar(value)   // Ns bytes

BitDecompose(s):
  Input:
    - s: Scalar value
  Output:
    - bits: Array of L scalars (each 0 or 1)

  Steps:
    1. bytes = s.to_bytes_le()  // 32 bytes, little-endian
    2. For i = 0 to L-1:
    3.     byte_index = i / 8
    4.     bit_position = i % 8
    5.     bit = (bytes[byte_index] >> bit_position) & 1
    6.     bits[i] = Scalar(bit)
    7. return bits

CreditToScalar(amount):
  Input:
    - amount: Integer credit amount (0 <= amount < 2^L)
  Output:
    - s: Scalar representation
  Exceptions:
    - AmountTooBigError: raised when the amount exceeds 2^L

  Steps:
    1. if amount >= 2^L:
    2.     raise AmountTooBigError
    3. return Scalar(amount)

ScalarToCredit(s):
  Input:
    - s: Scalar value
  Output:
    - amount: Integer credit amount or ERROR
  Exceptions:
    - ScalarOutOfRangeError: raised when the bytes 16..32 of the scalar value are nonzero

  Steps:
    1. bytes = s.to_bytes_le()
    2. // Check high bytes are zero
    3. For i = 16 to 31:
    4.     if bytes[i] != 0:
    5.         return ScalarOutOfRangeError
    6. amount = bytes[0..15] as u128
    7. return amount

4.1. Message Encoding

All protocol messages are encoded using the TLS presentation language from Section 3 of [TLS13]. The following sections define the structure of each message type.¶

struct {
    opaque K[Ne];         /* Compressed Ristretto point, Ne bytes */
    opaque pok<1..2^16-1>; /* NISigmaProtocol proof */
} IssuanceRequestMsg;

struct {
    opaque A[Ne];         /* Compressed Ristretto point, Ne bytes */
    opaque e[Ns];         /* Scalar, Ns bytes */
    opaque c[Ns];         /* Scalar, Ns bytes */
    opaque pok<1..2^16-1>; /* NISigmaProtocol proof */
} IssuanceResponseMsg;

struct {
    opaque k[Ns];           /* Nullifier scalar, Ns bytes */
    opaque s[Ns];           /* Spend amount scalar, Ns bytes */
    opaque ctx[Ns];         /* Request context scalar, Ns bytes */
    opaque A_prime[Ne];     /* Compressed Ristretto point, Ne bytes */
    opaque B_bar[Ne];       /* Compressed Ristretto point, Ne bytes */
    opaque Com[L][Ne];      /* L compressed Ristretto points, L*Ne bytes */
    opaque pok<1..2^16-1>; /* NISigmaProtocol proof */
} SpendProofMsg;

struct {
    opaque A_star[Ne];    /* Compressed Ristretto point, Ne bytes */
    opaque e_star[Ns];    /* Scalar, Ns bytes */
    opaque t[Ns];         /* Partial refund amount scalar, Ns bytes */
    opaque pok<1..2^16-1>; /* NISigmaProtocol proof */
} RefundMsg;

struct {
    uint16 error_code;
    opaque error_message<0..2^16-1>;
} ErrorMsg;

4.2. Protocol Flow

The complete protocol flow with message types:¶

Client                                          Issuer
  |                                               |
  |-- IssuanceRequestMsg ------------------------>|
  |                                               |
  |<-- IssuanceResponseMsg -----------------------|
  |                                               |
  | (client creates token)                        |
  |                                               |
  |-- SpendProofMsg ----------------------------->|
  |                                               |
  |<-- RefundMsg or ErrorMsg ---------------------|
  |                                               |

5.1. Nullifier Management

Implementations MUST maintain a persistent database of used nullifiers to prevent double-spending. The nullifier storage requirements grow linearly with the number of spent tokens. Implementations MAY use the following strategies to manage storage:¶

1. Expiration: If tokens have expiration dates, old nullifiers can be pruned.¶

2. Sharding: Nullifiers can be partitioned across multiple databases.¶

3. Bloom Filters: Probabilistic data structures can reduce memory usage with a small false-positive rate.¶

5.2. Constant-Time Operations

To prevent timing attacks, implementations MUST use constant-time scalar arithmetic and point operations. See the timing attack mitigations in the Security Considerations for detailed requirements.¶

5.3. Randomness Generation

All randomness is provided through the PRNG interface (see Appendix B). The PRNG is used for private key generation, blinding factors, and proof randomness. See Appendix B for the interface definition and requirements.¶

5.4. Point Validation

All Ristretto points received from external sources MUST be validated:¶

1. Deserialization: Verify the point deserializes to a valid Ristretto point¶

2. Non-Identity: Verify the point is not the identity element¶

3. Subgroup Check: Ristretto guarantees prime-order subgroup membership¶

Example validation:¶

ValidatePoint(P):
  1. If P fails to deserialize:
  2.     return INVALID
  3. If P == Identity:
  4.     return INVALID
  5. // Ristretto ensures prime-order subgroup membership
  6. return VALID

All implementations MUST validate points at these locations:¶

• When receiving K in issuance request¶

• When receiving A in issuance response¶

• When receiving A' and B_bar in spend proof¶

• When receiving Com[j] commitments in spend proof¶

• When receiving A* in refund response¶

5.5. Error Handling

Implementations SHOULD NOT provide detailed error messages that could leak information about the verification process. A single INVALID response should be returned for all verification failures.¶

5.6. Parameter Selection

The bit length L determines the range of credit values (0 to 2^L - 1). Implementations MUST enforce L <= MAX_BIT_LENGTH to fit within the group order. Larger L supports higher credit values but increases proof size and verification time linearly.¶

6.1. ACT(ristretto255, SHAKE128)

The group is ristretto255 as specified in [RFC9496]. It also specifies the Order(), Identity(), and Generator() functions.¶

The HashToGroup(msg) function uses hash_to_ristretto255(msg, DST) [RFC9380] with DST = "HashToGroup-" || domain_separator, and expand_message = expand_message_xmd using SHA-512.¶

SerializeElement(A) is the 'Encode' function from Section 4.3.2 of [RFC9496] producing an array of Ne=32 bytes.¶

DeserializeElement(bytes) is the 'Decode' function from Section 4.3.1 of [RFC9496]. This function must validate that the input is the valid canonical byte representation of an element of the group. This function must raise an error if deserialization fails, or if the resulting element is the group identity element.¶

SerializeScalar(s) outputs a Ns=32 byte array representing the little-endian encoding of the scalar value with the top three bits set to zero.¶

DeserializeScalar(bytes) attempts to deserialize a scalar from a little-endian 32-byte string. This function must fail if the input does not represent an integer between zero and Order()-1 inclusive. Note that this means the top three bits of the input MUST be zero.¶

The NISigmaProtocol interface is implemented by NISchnorrProofShake128Ris255 as follows:¶

class Ristretto255Codec(ByteSchnorrCodec):
    GG = ristretto255

class NISchnorrProofShake128Ris255(NISigmaProtocol):
    Protocol = SchnorrProof
    Codec = Ristretto255Codec
    Hash = SHAKE128

where SHAKE128 is the extendable-output function defined in [FIPS202].¶

The PRNG is instantiated as defined in Appendix B.¶

Set MAX_BIT_LENGTH=252 bits.¶

7.1. Security Model and Definitions

7.2. Cryptographic Assumptions

Security relies on:¶

1. The q-SDH Assumption in the Ristretto255 group. We refer to [TZ23] for the formal definition.¶

2. Random Oracle Model: The hash function used by the NISigmaProtocol (SHAKE128 in the ristretto255 suite) is modeled as a random oracle.¶

7.3. Privacy Limitations

The protocol does NOT provide:¶

1. Network-Level Privacy: IP addresses and network metadata can still link transactions.¶

2. Amount Privacy: The spent amount s is revealed to the issuer.¶

3. Timing Privacy: Transaction timing patterns could potentially be used for correlation.¶

7.4. Implementation Vulnerabilities and Mitigations

7.5. Known Attack Scenarios

7.6. Protocol Composition and State Management

7.7. Quantum Resistance

This protocol is NOT quantum-resistant. The discrete logarithm problem can be solved efficiently by quantum computers using Shor's algorithm. Organizations requiring long-term security should consider post-quantum alternatives. However, user privacy is preserved even in the presence of a cryptographically relevant quantum computer.¶

9.1. Normative References

[FIAT-SHAMIR]

Orrù, M., "Fiat-Shamir Transformation", Work in Progress, Internet-Draft, draft-irtf-cfrg-fiat-shamir-00, 8 August 2025, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-fiat-shamir-00>.

[FIPS186]

"Digital Signature Standard (DSS)", National Institute of Standards and Technology (U.S.), DOI 10.6028/nist.fips.186-5, February 2023, <https://doi.org/10.6028/nist.fips.186-5>.

[FIPS202]

"SHA-3 standard :: permutation-based hash and extendable-output functions", National Institute of Standards and Technology (U.S.), DOI 10.6028/nist.fips.202, 2015, <https://doi.org/10.6028/nist.fips.202>.

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

[RFC9380]

Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., and C. A. Wood, "Hashing to Elliptic Curves", RFC 9380, DOI 10.17487/RFC9380, August 2023, <https://www.rfc-editor.org/rfc/rfc9380>.

[RFC9496]

de Valence, H., Grigg, J., Hamburg, M., Lovecruft, I., Tankersley, G., and F. Valsorda, "The ristretto255 and decaf448 Groups", RFC 9496, DOI 10.17487/RFC9496, December 2023, <https://www.rfc-editor.org/rfc/rfc9496>.

[RFC9497]

Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A. Wood, "Oblivious Pseudorandom Functions (OPRFs) Using Prime-Order Groups", RFC 9497, DOI 10.17487/RFC9497, December 2023, <https://www.rfc-editor.org/rfc/rfc9497>.

[SIGMA]

Orrù, M. and C. Yun, "Interactive Sigma Proofs", Work in Progress, Internet-Draft, draft-irtf-cfrg-sigma-protocols-00, 8 August 2025, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-sigma-protocols-00>.

[TLS13]

Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, <https://www.rfc-editor.org/rfc/rfc8446>.

9.2. Informative References

[BBS]

"Short Group Signatures", 2004, <https://crypto.stanford.edu/~dabo/pubs/papers/groupsigs.pdf>.

[FST]

Fiat, A. and A. Shamir, "How To Prove Yourself: Practical Solutions to Identification and Signature Problems", Springer Berlin Heidelberg, Lecture Notes in Computer Science pp. 186-194, DOI 10.1007/3-540-47721-7_12, ISBN ["9783540180470"], April 2007, <https://doi.org/10.1007/3-540-47721-7_12>.

[KVAC]

"Keyed-Verification Anonymous Credentials", 2014, <https://eprint.iacr.org/2013/516.pdf>.

[TZ23]

"Revisiting BBS Signatures", 2023, <https://eprint.iacr.org/2023/275>.

B.1. Abstract Interface

interface PRNG:
  random_scalar() -> Scalar
    // Returns a uniformly distributed random scalar in [0, q).
    // The implementation MUST draw sufficient entropy (at least 64 bytes)
    // and reduce modulo the group order q.

In production, the PRNG MUST be backed by a CSPRNG in accordance with [FIPS186]. The random_scalar() method draws 64 bytes from the underlying CSPRNG and reduces modulo the group order to produce a uniformly distributed scalar.¶

B.2. SeededPRNG for Test Vectors

For deterministic test vector generation, the following SeededPRNG construction uses SHAKE128 as the underlying stream:¶

class SeededPRNG(PRNG):
  state: SHAKE128 instance

  SeededPRNG(seed):
    Input:
      - seed: Byte Array.
    Steps:
      1. self.state = SHAKE128.init()
      2. self.state.absorb(seed)

  random_scalar() -> Scalar:
    Output:
      - s: Scalar.
    Steps:
      1. bytes = self.state.squeeze(64)  // 64 bytes of output
      2. s = from_little_endian_bytes(bytes) mod q
      3. return s

where SHAKE128 is defined in [FIPS202].¶

WARNING: SeededPRNG MUST NOT be used in production. It is provided solely for generating reproducible test vectors. Production implementations MUST use OS-provided entropy sources.¶

C.1. anonymous-credit-tokens

Organization: Google¶

Description: Reference implementation in Rust¶

Maturity: Beta¶

Coverage: Complete protocol implementation¶

License: Apache 2.0¶

Contact: sgschlesinger@gmail.com¶

URL: https://github.com/SamuelSchlesinger/anonymous-credit-tokens¶