lsd0009

draft-guetschow-taler-protocol.md (22703B)

---

 ---
 v: 3
 
 title: "The GNU Taler Protocol"
 docname: draft-guetschow-taler-protocol
 category: info
 
 ipr: trust200902
 workgroup: independent
 stream: independent
 keyword:
   - taler
   - cryptography
   - ecash
   - payments
 
 #venue:
 #  repo: https://git.gnunet.org/lsd0009.git/
 #  latest: https://lsd.gnunet.org/lsd0009/
 
 author:
  -
     name: Mikolai Gütschow
     org: TUD Dresden University of Technology
     abbrev: TU Dresden
     street: Helmholtzstr. 10
     city: Dresden
     code: D-01069
     country: Germany
     email: mikolai.guetschow@tu-dresden.de
 
 normative:
   RFC20:
   RFC2104:
   RFC5869:
   RFC6234:
   HKDF: DOI.10.1007/978-3-642-14623-7_34
   SHS: DOI.10.6028/NIST.FIPS.180-4
 
 informative:
 
 
 --- abstract
 
 \[ TBW \]
 
 --- middle
 
 # Introduction
 
 \[ TBW \]
 
 Beware that this document is still work-in-progress and may contain errors.
 Use at your own risk!
 
 # Notation
 
 - `"abc"` denotes the literal string `abc` encoded as ASCII [RFC20]
 - `a | b` denotes the concatenation of a with b
 - `len(a)` denotes the length in bytes of the byte string a
 - `padZero(y, a)` denotes the byte string a, zero-padded to the length of y bytes
 - `bits(x)`/`bytes(x)` denotes the minimal number of bits/bytes necessary to represent the multiple precision integer x
 - `uint(y, x)` denotes the `y` least significant bits of the integer `x` encoded in network byte order (big endian)
 - `uint16(x)`/`uint32(x)`/`uint64(x)`/`uint256(x)`/`uint512(x)` is equivalent to `uint(16, x)`/`uint(32, x)`/`uint(64, x)`/`uint(256, x)`/`uint(512, x)`, respectively
 - `random(y)` denotes a randomly generated sequence of y bits
 - `a * b (mod N)` / `a ** b (mod N)` denotes the multiplication / exponentiation of multiple precision integers a and b, modulo N
 
 # Cryptographic Primitives
 
 ## Cryptographic Hash Functions
 
 ### SHA-256 {#sha256}
 
 ~~~
 SHA-256(msg) -> hash
 
 Input:
     msg     input message of length L < 2^61 octets
 
 Output:
     hash    message digest of fixed length HashLen = 32 octets
 ~~~
 
 `hash` is the output of SHA-256 as per Sections 4.1, 5.1, 6.1, and 6.2 of [RFC6234].
 
 ### SHA-512 {#sha512}
 
 ~~~
 SHA-512(msg) -> hash
 
 Input:
     msg     input message of length L < 2^125 octets
 
 Output:
     hash    message digest of fixed length HashLen = 64 octets
 ~~~
 
 `hash` is the output of SHA-512 as per Sections 4.2, 5.2, 6.3, and 6.4 of [RFC6234].
 
 ### SHA-512-256 (truncated SHA-512) {#sha512-trunc}
 
 ~~~
 SHA-512-256(msg) -> hash
 
 Input:
     msg     input message of length L < 2^125 octets
 
 Output:
     hash    message digest of fixed length HashLen = 32 octets
 ~~~
 
 The output `hash` corresponds to the first 32 octets of the output of SHA-512 defined in {{sha512}}:
 
 ~~~
 temp = SHA-512(msg)
 hash = temp[0:31]
 ~~~
 
 Note that this operation differs from SHA-512/256 as defined in [SHS] in the initial hash value.
 
 
 ## Message Authentication Codes
 
 ### HMAC {#hmac}
 
 ~~~
 HMAC-Hash(key, text) -> out
 
 Option:
     Hash    cryptographic hash function with output length HashLen
 
 Input:
     key     secret key of length at least HashLen
     text    input data of arbitary length
 
 Output:
     out     output of length HashLen
 ~~~
 
 `out` is calculated as defined in [RFC2104].
 
 
 ## Key Derivation Functions
 
 ### HKDF {#hkdf}
 
 The Hashed Key Derivation Function (HKDF) used in Taler is an instantiation of [RFC5869]
 with two different hash functions for the Extract and Expand step as suggested in [HKDF]:
 `HKDF-Extract` uses `HMAC-SHA512`, while `HKDF-Expand` uses `HMAC-SHA256` (cf. {{hmac}}).
 
 ~~~
 HKDF(salt, IKM, info, L) -> OKM
 
 Inputs:
     salt    optional salt value (a non-secret random value);
               if not provided, it is set to a string of 64 zeros.
     IKM     input keying material
     info    optional context and application specific information
               (can be a zero-length string)
     L       length of output keying material in octets
               (<= 255*32 = 8160)
 
 Output:
     OKM      output keying material (of L octets)
 ~~~
 
 The output OKM is calculated as follows:
 
 ~~~
 PRK = HKDF-Extract(salt, IKM) with Hash = SHA-512 (HashLen = 64)
 OKM = HKDF-Expand(PRK, info, L) with Hash = SHA-256 (HashLen = 32)
 ~~~
 
 ### HKDF-Mod
 
 Based on the HKDF defined in {{hkdf}}, this function returns an OKM that is smaller than a given multiple precision integer N.
 
 ~~~
 HKDF-Mod(N, salt, IKM, info) -> OKM
 
 Inputs:
     N        multiple precision integer
     salt     optional salt value (a non-secret random value);
               if not provided, it is set to a string of 64 zeros.
     IKM      input keying material
     info     optional context and application specific information
               (can be a zero-length string)
 
 Output:
     OKM      output keying material (smaller than N)
 ~~~
 
 The final output `OKM` is determined deterministically based on a counter initialized at zero.
 
 ~~~
 counter = 0
 do until OKM < N:
     x = HKDF(salt, IKM, info | uint16(counter), bytes(N))
     OKM = uint(bits(N), x)
     counter += 1
 ~~~
 
 ## Non-Blind Signatures
 
 ### Ed25519
 
 ## Blind Signatures
 
 ### RSA-FDH {#rsa-fdh}
 
 #### Supporting Functions
 
 ~~~
 RSA-FDH(msg, pubkey) -> fdh
 
 Inputs:
     msg     message
     pubkey  RSA public key consisting of modulus N and public exponent e
 
 Output:
     fdh     full-domain hash of msg over pubkey.N
 ~~~
 
 `fdh` is calculated based on HKDF-Mod from {{hkdf-mod}} as follows:
 
 ~~~
 info = "RSA-FDA FTpsW!"
 salt = uint16(bytes(pubkey.N)) | uint16(bytes(pubkey.e))
      | pubkey.N | pubkey.e
 fdh = HKDF-Mod(pubkey.N, salt, msg, info)
 ~~~
 
 The resulting `fdh` can be used to test against a malicious RSA pubkey
 by verifying that the greatest common denominator (gcd) of `fdh` and `pubkey.N` is 1.
 
 ~~~
 RSA-FDH-Derive(bks, pubkey) -> out
 
 Inputs:
     bks     blinding key secret of length L = 32 octets
     pubkey  RSA public key consisting of modulus N and public exponent e
 
 Output:
     out     full-domain hash of bks over pubkey.N
 ~~~
 
 `out` is calculated based on HKDF-Mod from {{hkdf-mod}} as follows:
 
 ~~~
 info = "Blinding KDF"
 salt = "Blinding KDF extractor HMAC key"
 fdh = HKDF-Mod(pubkey.N, salt, bks, info)
 ~~~
 
 #### Blinding
 
 ~~~
 RSA-FDH-Blind(msg, bks, pubkey) -> out
 
 Inputs:
     msg     message
     bks     blinding key secret of length L = 32 octets
     pubkey  RSA public key consisting of modulus N and public exponent e
 
 Output:
     out     message blinded for pubkey
 ~~~
 
 `out` is calculated based on RSA-FDH from {{rsa-fdh}} as follows:
 
 ~~~
 data = RSA-FDH(msg, pubkey)
 r = RSA-FDH-Derive(bks, pubkey)
 r_e = r ** pubkey.e (mod pubkey.N)
 out = r_e * data (mod pubkey.N)
 ~~~
 
 #### Signing
 
 ~~~
 RSA-FDH-Sign(data, privkey) -> sig
 
 Inputs:
     data    data to be signed, an integer smaller than privkey.N
     privkey RSA private key consisting of modulus N and private exponent d
 
 Output:
     sig     signature on data by privkey
 ~~~
 
 `sig` is calculated as follows:
 
 ~~~
 sig = data ** privkey.d (mod privkey.N)
 ~~~
 
 #### Unblinding
 
 ~~~
 RSA-FDH-Unblind(sig, bks, pubkey) -> out
 
 Inputs:
     sig     blind signature
     bks     blinding key secret of length L = 32 octets
     pubkey  RSA public key consisting of modulus N and public exponent e
 
 Output:
     out     unblinded signature
 ~~~
 
 `out` is calculated as follows:
 
 ~~~
 r = RSA-FDH-Derive(bks, pubkey)
 r_inv = inverse of r (mod pubkey.N)
 out = sig * r_inv (mod pubkey.N)
 ~~~
 
 #### Verifying
 
 ~~~
 RSA-FDH-Verify(msg, sig, pubkey) -> out
 
 Inputs:
     msg     message
     sig     signature of pubkey over msg
     pubkey  RSA public key consisting of modulus N and public exponent e
 
 Output:
     out     true, if sig is a valid signature
 ~~~
 
 `out` is calculated based on RSA-FDH from {{rsa-fdh}} as follows:
 
 ~~~
 data = RSA-FDH(msg, pubkey)
 exp = sig ** pubkey.e (mod pubkey.N)
 out = (data == exp)
 ~~~
 
 ### Clause-Schnorr
 
 # Datatypes
 
 ## Amount
 
 Amounts are represented in Taler as positive fixed-point values
 consisting of `value` as the non-negative integer part of the base currency,
 the `fraction` given in units of one hundred millionth (1e-8) of the base currency,
 and `currency` as the 3-11 ASCII characters identifying the currency.
 
 Whenever used in the protocol, the binary representation of an `amount` is
 `uint64(amount.value) | uint32(amount.fraction) | padZero(12, amount.currency)`.
 
 ## Timestamps
 
 Absolute timestamps are represented as `uint64(x)` where `x` corresponds to
 the microseconds since `1970-01-01 00:00 CEST` (the UNIX epoch).
 The special value `0xFFFFFFFFFFFFFFFF` represents "never".
 <!--
 // todo: check if needed and correct
 Relative timestamps are represented as `uint64(x)` where `x` is given in microseconds.
 The special value `0xFFFFFFFFFFFFFFFF` represents "forever".
 -->
 
 ## Signatures
 
 All messages to be signed in Taler start with a header containing their size and
 a fixed signing context (purpose) as registered by GANA in the
 [GNUnet Signature Purposes](https://gana.gnunet.org/gnunet-signatures/gnunet_signatures.html)
 registry. Taler-related purposes start at 1000.
 
 ~~~
 Sign-Msg(purpose, msg) -> out
 
 Inputs:
     purpose signature purpose as registered at GANA
     msg     message content (excl. header) to be signed
 
 Output:
     out     complete message (incl. header) to be signed
 ~~~
 
 `out` is formed as follows:
 
 ~~~
 out = uint32(len(msg)) | uint32(purpose) | msg
 ~~~
 
 // todo: explain persist, check, knows, sum, indexing (if left of equal sign, single entry; if not refers to whole list)
 
 # The Taler Crypto Protocol
 
 ## Withdrawal {#withdrawal}
 
 The wallet generates `n > 0` coins (`coinᵢ`) and requests `n` signatures (`blind_sigᵢ`) from the exchange,
 attributing value to the coins according to `n` chosen denominations (`denomᵢ`).
 The total value and withdrawal fee (defined by the exchange per denomination)
 must be smaller or equal to the amount stored in the single reserve used for withdrawal.
 
 // todo: extend with extra roundtrip for CBS
 
 ~~~
             wallet                                  exchange
 knows denomᵢ.pub                        knows denomᵢ.priv
                |                                        |
 +-----------------------------+                         |
 | (W1) reserve key generation |                         |
 +-----------------------------+                         |
                |                                        |
                |----------- (bank transfer) ----------->|
                | (subject: reserve.pub, amount: value)  |
                |                                        |
                |                      +------------------------------+
                |                      | persist (reserve.pub, value) |
                |                      +------------------------------+
                |                                        |
 +-----------------------------------+                   |
 | (W2) coin generation and blinding |                   |
 +-----------------------------------+                   |
                |                                        |
                |-------------- /withdraw -------------->|
                |    (reserve.pub, ~(coinᵢ.h_denom),     |
                |           ~blind_coin, sig0)           |
                |                                        |
                |                      +--------------------------------+
                |                      | (E1) coin issuance and signing |
                |                      +--------------------------------+
                |                                        |
                |<----------- (~blind_sig) --------------|
                |                                        |
 +----------------------+                                |
 | (W3) coin unblinding |                                |
 +----------------------+                                |
                |                                        |
 ~~~
 
 where (for RSA, without age-restriction)
 
 ~~~
 (W1) reserve key generation (wallet)
 
 reserve = EdDSA-Keygen()
 persist (reserve, value)
 ~~~
 
 The wallet derives coins and blinding secrets using a HKDF from a single master secret per withdrawal operation,
 together with an integer index.
 This is strictly speaking an implementation detail since the master secret is never revealed to any other party,
 and might be chosen to be implemented differently.
 
 ~~~
 (W2) coin generation and blinding (wallet)
 
 master_secret = random(256)
 persist master_secret
 coin_seedᵢ = HKDF(uint32(i), master_secret, "taler-withdrawal-coin-derivation", 64)
 blind_secretᵢ = coin_seedᵢ[32:]
 coinᵢ.priv = coin_seedᵢ[:32]
 coinᵢ.pub = EdDSA-GetPub(coinᵢ.priv)
 coinᵢ.h_denom = SHA-512(uint32(0) | uint32(1) | denomᵢ.pub)
 blind_coinᵢ = RSA-FDH-Blind(SHA-512(coinᵢ.pub), blind_secretᵢ, denomᵢ.pub)
 msg = Sign-Msg(WALLET_RESERVE_WITHDRAW,
     ( sum(denomᵢ.value) | sum(denomᵢ.fee_withdraw)
     | SHA-512( SHA-512(~(denomᵢ.pub)) | uint32(0x1) | blind_coinᵢ )
     | uint256(0x0) | uint32(0x0) | uint32(0x0) ))
 sig = EdDSA-Sign(reserve.priv, msg)
 ~~~
 
 ~~~
 (E1) coin issuance and signing (exchange)
 
 denomᵢ = Denom-Lookup(coinᵢ.h_denom)
 check denomᵢ.pub known and not withdrawal-expired
 check EdDSA-Verify(reserve.pub, msg, sig)
 check reserve KYC status ok or not needed
 total = sum(~(denomᵢ.value)) + sum(~(denomᵢ.fee_withdraw))
 check reserve.balance >= total
 reserve.balance -= total
 blind_sigᵢ = RSA-FDH-Sign(blind_coinᵢ, denomᵢ.priv)
 persist withdrawal
 ~~~
 
 ~~~
 (W4) coin unblinding (wallet)
 
 coinᵢ.sig = RSA-FDH-Unblind(blind_sigᵢ, blind_secretᵢ, denomᵢ.pub)
 check RSA-FDH-Verify(SHA-512(coinᵢ.pub), coinᵢ.sig, denomᵢ.pub)
 persist (coinᵢ, blind_secretᵢ)
 ~~~
 
 ## Payment {#payment}
 
 The wallet obtains `contract` information for an `order` from the merchant
 after claiming it with a `nonce`.
 Payment of the order is prepared by signing (partial) deposit authorizations (`depositᵢ`) of coins (`coinᵢ`),
 where the sum of all contributions (`contributionᵢ <= denomᵢ.value`) must match the `contract.price` plus potential deposit fees.
 The payment is complete as soon as the merchant successfully redeems the deposit authorizations at the exchange (cf. {{deposit}}).
 
 ~~~
             wallet                                  merchant
 knows valid coinᵢ                       knows merchant.priv
                                         knows exchange, payto
                |                                        |
                |                      +-----------------------+
                |                      | (M1) order generation |
                |                      +-----------------------+
                |                                        |
                |<------- (QR-Code / NFC / URI) ---------|
                |          (order.{id,token?})           |
                |                                        |
 +-----------------------+                               |
 | (W1) nonce generation |                               |
 +-----------------------+                               |
                |                                        |
                |------- /orders/{order.id}/claim ------>|
                |       (nonce.pub, order.token?)        |
                |                                        |
                |                      +--------------------------+
                |                      | (M2) contract generation |
                |                      +--------------------------+
                |                                        |
                |<---- (contract, merchant.pub, contract_sig) ----|
                |                                        |
 +--------------------------+                            |
 | (W2) payment preparation |                            |
 +--------------------------+                            |
                |                                        |
                |------- /orders/{order.id}/pay -------->|
                |              (~deposit)                |
                |                                        |
                |                      +--------------------+
                |                      | (M3) deposit check |
                |                      +--------------------+
                |                                        |
                |<--------------- (sig) -----------------|
                |                                        |
 +---------------------------+                           |
 | (W3) payment verification |                           |
 +---------------------------+                           |
                |                                        |
 ~~~
 
 where (without age restriction, policy and wallet data hash)
 
 ~~~
 (M1) order generation (merchant)
 
 wire_salt = random(128)
 persist order = (id, price, info, token?, wire_salt)
 ~~~
 
 ~~~
 (W1) nonce generation (wallet)
 
 nonce = EdDSA-Keygen()
 persist nonce.priv
 ~~~
 
 Note that the private key of `nonce` is currently not used anywhere in the protocol.
 However, it could be used in the future to prove ownership of an order transaction,
 enabling use-cases such as "unclaiming" or transferring an order to another person,
 or proving the payment without resorting to the individual coins.
 
 ~~~
 (M2) contract generation (merchant)
 
 h_wire = HKDF(wire_salt, payto, "merchant-wire-signature", 64)
 determine timestamp, refund_deadline, wire_deadline
 contract = (order.{id,price,info,token?}, exchange, h_wire, timestamp, refund_deadline, wire_deadline)
 check contract.order.token == token
 contract.nonce = nonce.pub
 persist contract
 h_contract = SHA-512(canonicalJSON(contract))
 msg = Sign-Msg(MERCHANT_CONTRACT, h_contract)
 contract_sig = EdDSA-Sign(merchant.priv, msg)
 ~~~
 
 ~~~
 (W2) payment preparation (wallet)
 
 h_contract = SHA-512(canonicalJSON(contract))
 msg = Sign-Msg(MERCHANT_CONTRACT, h_contract)
 check EdDSA-Verify(merchant.pub, msg, contract_sig)
 check contract.nonce = nonce
 TODO: double-check extra hash check?
 ~selection = CoinSelection(contract.{exchange,price}) TODO: include MarkDirty here
 (coinᵢ, denomᵢ, contributionᵢ) = selectionᵢ
 h_contract = SHA-512(canonicalJSON(contract))
 msgᵢ = Sign-Msg(WALLET_COIN_DEPOSIT,
     ( h_contract | uint256(0x0)
     | uint512(0x0) | contract.h_wire | coinᵢ.h_denom
     | contract.timestamp | contract.refund_deadline
     | contributionᵢ + denomᵢ.fee_deposit
     | denomᵢ.fee_deposit | merchant.pub | uint512(0x0) ))
 sigᵢ = EdDSA-Sign(coinᵢ.priv, msgᵢ)
 depositᵢ = (coinᵢ.{pub,sig,h_denom}, contributionᵢ, sigᵢ)
 persist (contract, ~sig, ~deposit)
 ~~~
 
 // TODO: explain CoinSelection
 // TODO: maybe better {sigᵢ} instead of ~sig?
 // TODO: maybe introduce symbol for pub/priv
 // TODO: maybe rename Sign-Msg as name is currently a bit confusing
 
 ~~~
 (M3) deposit check (merchant)
 
 check sum(depositᵢ.contribution) == contract.price
 check Deposit(~deposit)
 msg = Sign-Msg(MERCHANT_PAYMENT_OK, h_contract)
 sig = EdDSA-Sign(merchant.priv, msg)
 ~~~
 
 ~~~
 (W3) payment verification (wallet)
 
 msg = Sign-Msg(MERCHANT_PAYMENT_OK, h_contract)
 check EdDSA-Verify(merchant.pub, msg, sig)
 ~~~
 
 ## Deposit {#deposit}
 
 // todo: add introductory text
 
 ~~~
        merchant/wallet                              exchange
 knows exchange.pub                      knows exchange.priv
 knows contract_sig                      knows denomᵢ.pub
 knows payto, wire_salt                                  |
 knows contract, ~deposit                                |
                |                                        |
 +--------------------------+                            |
 | (M1) deposit preparation |                            |
 +--------------------------+                            |
                |                                        |
                |----------- /batch-deposit ------------>|
                |    (info, h_contract, ~deposit         |
                |     merchant.pub, contract_sig)        |
                |                                        |
                |                      +-------------------------+
                |                      | (E1) deposit validation |
                |                      +-------------------------+
                |                                        |
                |<--- (timestamp, exchange.pub, sig) ----|
                |                                        |
 +---------------------------+                           |
 | (M2) deposit verification |                           |
 +---------------------------+                           |
                |                                        |
 ~~~
 
 where (without age restriction, policy and wallet data hash)
 
 ~~~
 (M1) Deposit preparation (merchant/wallet)
 
 h_contract = SHA-512(canonicalJSON(contract))
 info.time = contract.{timestamp, wire_deadline, refund_deadline}
 info.wire = (payto, wire_salt)
 ~~~
 
 ~~~
 (E1) Deposit validation (exchange)
 
 coinᵢ = depositᵢ.coin
 denomᵢ = Denom-Lookup(coinᵢ.h_denom)
 check denomᵢ.pub known and not deposit-expired
 h_wire = HKDF(info.wire.wire_salt, info.wire.payto, "merchant-wire-signature", 64)
 msgᵢ = Sign-Msg(WALLET_COIN_DEPOSIT,
     ( h_contract | uint256(0x0)
     | uint512(0x0) | h_wire | coinᵢ.h_denom
     | info.time.timestamp | info.time.refund_deadline
     | depositᵢ.contribution + denomᵢ.fee_deposit
     | denomᵢ.fee_deposit | merchant.pub | uint512(0x0) ))
 check EdDSA-Verify(coinᵢ.pub, msgᵢ, depositᵢ.sig)
 check RSA-FDH-Verify(SHA-512(coinᵢ.pub), coinᵢ.sig, denomᵢ.pub)
 check not overspending
 persist deposit-record, mark-spent
 schedule bank transfer to payto
 timestamp = now()
 msg = Sign-Msg(EXCHANGE_CONFIRM_DEPOSIT,
     ( h_contract | h_wire | uint512(0x0)
     | timestamp | info.time.wire_deadline
     | info.time.refund_deadline
     | sum(depositᵢ.contribution) - sum(denomᵢ.fee_deposit)
     | SHA-512(depositᵢ.sig) | merchant.pub ))
 sig = EdDSA-Sign(exchange.priv, msg)
 ~~~
 
 ~~~
 (M2) Deposit verification (merchant/wallet)
 
 h_wire = HKDF(wire_salt, payto, "merchant-wire-signature", 64)
 msg = Sign-Msg(EXCHANGE_CONFIRM_DEPOSIT,
     ( h_contract | h_wire | uint512(0x0)
     | timestamp | contract.wire_deadline
     | contract.refund_deadline
     | sum(depositᵢ.contribution) - sum(denomᵢ.fee_deposit)
     | SHA-512(depositᵢ.sig) | merchant.pub ))
 check EdDSA-Verify(exchange.pub, msg, sig)
 ~~~
 
 ## Refresh {#refresh}
 
 // todo
 
 ## Refund {#refund}
 
 // todo
 
 ## Recoup {#recoup}
 
 // todo
 
 ## Wallet-to-Wallet Push Payment {#w2w-push}
 
 // todo
 
 ## Wallet-to-Wallet Pull Payment {#w2w-pull}
 
 // todo
 
 # Security Considerations
 
 \[ TBD \]
 
 # IANA Considerations
 
 None.
 
 --- back
 
 # Change log
 
 # Acknowledgments
 {:numbered="false"}
 
 \[ TBD \]
 
 This work was supported in part by the German Federal Ministry of
 Education and Research (BMBF) within the project Concrete Contracts.