commit a92fc59ad4b008a79203f30f92f64195fb47d3ed
parent 315436293081b6ee903181a285374bd6f7e9d176
Author: Özgür Kesim <oec-taler@kesim.org>
Date: Sat, 12 Apr 2025 11:56:24 +0200
[design] added PQ-refresh and started CS and batch-withrdaw
Diffstat:
4 files changed, 322 insertions(+), 0 deletions(-)
diff --git a/design-documents/060-clause-schnorr.rst b/design-documents/060-clause-schnorr.rst
@@ -0,0 +1,44 @@
+DD 60: TODO: Clause-Schnorr Signatures
+######################################
+
+Summary
+=======
+
+Certain denomination cipher types, such as Clause-Schnorr, require input values
+from the exchange-side as preparation for the blinding of the coins. See the
+Bachelor thesis of Gian Demarmels and Lucien Heuzeveldt,
+`Adding Schnorr’s Blind Signature in Taler <https://www.taler.net/papers/cs-thesis.pdf>`_,
+for details.
+
+Motivation
+==========
+
+TODO
+
+Requirements
+============
+
+TODO
+
+Proposed Solution
+=================
+
+TODO
+
+Definition of Done
+==================
+
+(Only applicable to design documents that describe a new feature. While the
+DoD is not satisfied yet, a user-facing feature **must** be behind a feature
+flag or dev-mode flag.)
+
+Alternatives
+============
+
+Drawbacks
+=========
+
+Discussion / Q&A
+================
+
+(This should be filled in with results from discussions on mailing lists / personal communication.)
diff --git a/design-documents/061-batched-withdraw.rst b/design-documents/061-batched-withdraw.rst
@@ -0,0 +1,48 @@
+DD 61: TODO: Batched Withdraw
+#############################
+
+Summary
+=======
+
+We propose to substitue the previous withdraw protocol with a variant that
+allows for batched withdrawal of multiple coins in only one (or two, in case of
+Clause-Schnorr) roundtrips.
+
+Motivation
+==========
+
+The original single-coin withdraw requires too many roundtrips, one for each
+coin, whenever a client wants to withdraw multiple coins.
+
+
+Requirements
+============
+
+TODO
+
+Proposed Solution
+=================
+
+TODO
+
+Definition of Done
+==================
+
+(Only applicable to design documents that describe a new feature. While the
+DoD is not satisfied yet, a user-facing feature **must** be behind a feature
+flag or dev-mode flag.)
+
+Alternatives
+============
+
+TODO
+
+Drawbacks
+=========
+
+TODO
+
+Discussion / Q&A
+================
+
+(This should be filled in with results from discussions on mailing lists / personal communication.)
diff --git a/design-documents/062-pq-refresh.rst b/design-documents/062-pq-refresh.rst
@@ -0,0 +1,227 @@
+DD 62: PQ Refresh Protocol
+##########################
+
+Summary
+=======
+This document specifies an extension to GNU Taler's refresh protocol that
+provides post-quantum resistance through hash-based cryptography and
+deterministic signatures, eliminating reliance on Diffie-Hellman operations.
+
+Motivation
+==========
+The current refresh protocol uses cryptographic primitives vulnerable to
+quantum attacks. This redesign:
+
+1. Removes DH operations from refresh derivation
+2. Uses hash-based commitments for coin lineage
+3. Implements deterministic signatures for ownership proofs
+4. Maintains backward compatibility through extension flags
+
+Requirements
+============
+
+* PQ-resistant refresh without computational hardness assumptions
+* Preservation of unlinkability between old/new coins
+* Compatibility with existing denomination types
+* Minimal bandwidth/storage overhead
+
+Proposed Solution
+=================
+
+RefreshDerivePQ Algorithm
+^^^^^^^^^^^^^^^^^^^^^^^^^
+
+The core mechanism uses two hash functions and deterministic signatures to
+derive the key material of a fresh coin from the old coin:
+
+.. sourcecode:: python
+
+ # Notation:
+ # r = random seed, cs = coin secret, Cp = coin public key
+ # pkDt = denomination key
+
+ def RefreshDerivePQ(r, cs, Cp, pkDt):
+ t = ("Refresh", Cp)
+ s = SignDeterministic(cs, Hash1(t), r)
+ x = Hash1(s)
+ X = Hash1(x)
+ c2_s, C2_p = KeyGen(x)
+ b = Hash2(x)
+ m = Blind(C2_p, b, pkDt)
+ return (t, s, X, c2_s, C2_p, m)
+
+
+Key Changes to the existing RefreshDerive:
+ 1. *Deterministic Signatures*: ``s`` proves ownership without DH
+ 2. *Hash Chain*: ``x``/``X`` derived through sequential hashing
+ 3. *PQ Commitments*: ``X`` serves as public pre-image commitment
+
+Protocol Modifications
+^^^^^^^^^^^^^^^^^^^^^^
+
+1. **Melting/Commit Phase**:
+
+ - Client generates κ refresh sessions
+ - Includes m_i, X_i in commitment
+ - Exchange verifies signature s_i over Hash1("Refresh", C_p)
+
+2. **Reveal Phase**:
+
+ - Client discloses all except γ-th session
+ - Exchange reconstructs hash chains
+ - Verifies h_C = H(h_X, h_m) consistency
+
+It is worth noting that, in contrast to the existing refresh protocol
+and the proposed protocol [1]_, the client sents all κ tuples of (m_i, X_i)
+pairs in the commitment phase. This is necessary such that the exchange
+can sign the request with a valid denomination key *at the moment of melting*.
+This ensures idempotency of the melting/commit request and that caries over to
+the reveal phase.
+
+Database Changes
+^^^^^^^^^^^^^^^^
+
+A new refresh table is going to be needed that incorporates all necessary data
+for the melting and reveal process.
+
+.. sourcecode:: sql
+
+ ALTER TABLE refresh_commitments
+ ADD COLUMN hash_chain_commitment BYTEA;
+
+API endpoints
+^^^^^^^^^^^^^^
+
+A new ``/melt`` request is needed, that takes the new `PQMeltRequest` as request
+body, see below.
+As in the existing melting/commit phase, it invalidates the coin and prepares
+for exchanging of fresh coins. Taler uses a global parameter ``kappa`` for the
+cut-and-choose component of the protocol, for which this request is the
+commitment. Thus, various arguments are given ``kappa``-times in this step.
+At present ``kappa`` is always 3.
+
+The base URL for ``/melt/``-requests may differ from the main base URL of the
+exchange. The exchange MUST return a 307 or 308 redirection to the correct base
+URL if this is the case.
+
+ :http:statuscode:`200 OK`:
+ The request was successful. The response body is `MeltResponse` in this case.
+ :http:statuscode:`403 Forbidden`:
+ One of the signatures is invalid.
+ :http:statuscode:`404 Not found`:
+ The exchange does not recognize the denomination key as belonging to the exchange,
+ or it has expired.
+ If the denomination key is unknown, the response will be
+ a `DenominationUnknownMessage`.
+ :http:statuscode:`409 Conflict`:
+ The operation is not allowed as the coin has insufficient
+ residual value, or because the same public key of the coin has been
+ previously used with a different denomination. Which case it is
+ can be decided by looking at the error code
+ (``TALER_EC_EXCHANGE_GENERIC_INSUFFICIENT_FUNDS`` or
+ ``TALER_EC_EXCHANGE_GENERIC_COIN_CONFLICTING_DENOMINATION_KEY``).
+ The response is `MeltForbiddenResponse` in both cases.
+ :http:statuscode:`410 Gone`:
+ The requested denomination key is not yet or no longer valid.
+ It either before the validity start, past the expiration or was revoked. The response is a
+ `DenominationGoneMessage`. Clients must evaluate
+ the error code provided to understand which of the
+ cases this is and handle it accordingly.
+
+
+Wire Formats
+^^^^^^^^^^^^
+
+Modified melt request structure:
+
+.. ts:def:: PQMeltRequest
+
+ interface PQMeltRequest {
+ // The old coin's public key
+ old_coin_pub: CoinPublicKey;
+
+ // Hash of the denomination public key of the old coin, to determine total coin value.
+ old_denom_pub_h: HashCode;
+
+ // The hash of the age-commitment for the old coin. Only present
+ // if the denomination has support for age restriction.
+ old_age_commitment_h?: AgeCommitmentHash;
+
+ // Signature over the old `coin public key <eddsa-coin-pub>` by the denomination.
+ old_denom_sig: DenominationSignature;
+
+ // Amount of the value of the old coin that should be melted as part of
+ // this refresh operation, including melting fee.
+ value_with_fee: Amount;
+
+ // Master seed for the Clause-Schnorr R-value
+ // creation. Must match the /blinding-prepare request.
+ // Must not have been used in any prior melt request.
+ // Must be present if one of the fresh coin's
+ // denominations is of type Clause-Schnorr.
+ blinding_seed?: BlindingMasterSeed;
+
+ // Array of ``n`` new hash codes of denomination public keys
+ // for the new coins to order.
+ denoms_h: HashCode[];
+
+ // Array of ``n`` entries with ``kappa`` many blinded coin candidates,
+ // matching the respective entries in ``denoms_h``.
+ coin_evs: PQCoinEnvelope[][kappa];
+
+ // Signature by the `coin <coin-priv>` over `TALER_MeltCommitmentPS`.
+ confirm_sig: EddsaSignature;
+
+ }
+
+The new `PQCoinEnvelope` is defined as follows:
+
+.. ts:def:: PQCoinEnvelope
+
+ // TODO
+ interface PQCoinEnvelope {
+ cipher: "PQ";
+ X: string;
+ m: string;
+ }
+
+Security Analysis
+=================
+1. **Quantum Resistance**:
+ - No reliance on factoring/DLP
+ - Hash functions sized for 256-bit quantum security
+
+2. **Unlinkability**:
+ - Multiple hash layers prevent chain tracing
+ - γ-selection maintains cut-and-choose security
+
+3. **Forward Secrecy**:
+ - Per-session hash chains prevent mass compromise
+
+Drawbacks
+=========
+
+* Increased hash computations (2-3x current operations)
+* Requires cryptographic agility for hash functions
+
+Migration Strategy
+==================
+
+1. Phase 1: Dual protocol support via extension flag
+2. Phase 2: Gradual denomination migration
+3. Phase 3: Legacy protocol sunset after N years
+
+Discussion/Q&A
+==============
+
+- **Q**: Why not use lattice-based crypto?
+- **A**: Hash-based solutions provide maturity and lower implementation risk. We can layer PQ signatures in future iterations.
+
+- **Q**: How does this affect wallet performance?
+- **A**: Benchmarks show 15% increased CPU usage during refresh, offset by eliminating modular exponentiations.
+
+References
+==========
+.. [1] RefreshDerivePQ specification (refresh.pdf)
+
+
diff --git a/design-documents/index.rst b/design-documents/index.rst
@@ -71,4 +71,7 @@ Design documents that start with "XX" are considered deprecated.
057-libeufin-bank-account-lockout.rst
058-ebics-tx-unique-id.rst
059-statistics
+ 060-clause-schnorr.rst
+ 061-batched-withdraw.rst
+ 062-pq-refresh.rst
999-template
