Edx25519 introduced and more details about reveal with age restrictions

1 files changed, 131 insertions, 14 deletions

diff --git a/design-documents/024-age-restriction.rst b/design-documents/024-age-restriction.rst
index ac4a7e15..6b97a451 100644
--- a/design-documents/024-age-restriction.rst
+++ b/design-documents/024-age-restriction.rst
@@ -72,7 +72,7 @@ The main ideas are simple:
    zeroth age group is :math:`\{0,\ldots,a_1-1\}`.
 
 #. An **unrestricted** *age commitment* is defined as a vector of length M of
-   pairs of EdDSA public and private keys on Curve25519. In other words: one
+   pairs of Edx25519_ public and private keys on Curve25519. In other words: one
    key pair for each age group after the zeroth:
    :math:`\bigl\langle (p_1, s_1), \ldots, (p_M, s_M) \bigr\rangle`
 
@@ -100,14 +100,13 @@ The main ideas are simple:
    SHA256 hash value of the age commitment (i.e. the M public keys) into the
    signature of the coin.  So instead of signing :math:`\text{FDH}_N(C_p)` with
    the RSA private key of a denomination with support for age restriction, we
-   sign :math:`\text{FDH}_N(C_p, h_a)`.  Here, :math:`C_p` is the EdDSA public
+   sign :math:`\text{FDH}_N(C_p, h_a)`.  Here, :math:`C_p` is the Edx25519_ public
    key of a coin and :math:`h_a` is the hash of the age commitment.
 
 TODO: Summarize the design based on the five functions ``Commit()``,
 ``Attest()``, ``Verify()``, ``Derive()``, ``Compare()``, once the paper from
 Özgür and Christian is published.
 
-
 Changes in the Exchange API
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
@@ -324,7 +323,7 @@ for the signature check is as before (borrowing notation from
 .. math::
    \text{FDH}_N(C_p)\; \stackrel{?}{=}\; \left(\sigma_C\right)^{e} \;\;\text{mod}\,N
 
-Here, :math:`C_p` is the EdDSA public key of a coin, :math:`\sigma_C` is its
+Here, :math:`C_p` is the Edx25519_ public key of a coin, :math:`\sigma_C` is its
 signature and :math:`\langle e, N \rangle` is the RSA public key of the
 denomination.
 
@@ -359,15 +358,29 @@ the amount of age groups defined in the field ``.age_groups`` of the
       // The size of the vector is defined by the Exchange implicetly as the
       // amount of age groups defined in the field ``.age_groups`` of the
       // ``ExtensionAgeRestriction``.
-      old_age_commitment?: EddsaPublicKey[];
+      old_age_commitment?: Edx25519PublicKey[];
 
       
       ...
    }
 
-TODO: describe how the exchange derives the κ-1 other age-restriction vectors
-and compares them to the one in ``.old_age_commitment``.
 
+The exchange can now check if the provided public keys ``.old_age_commitment``
+have the same SHA256 hash value when hashed in sequence as the
+``age_commitment_hash`` of the original coin from the call to melt.
+
+The existing `cut&choose protocol during the reveal phase
+</core/api-exchange.html#post--refreshes-$RCH-reveal>`__ is extended to perform
+the following additional computation and checks:
+
+Using the κ-1 transfer secrets from the reveal request, the exchange derives
+κ-1 age commitments from the ``old_age_commitment`` by calling
+``Edx25519_derive_public(old_age_commitment, s_κ)`` from Edx25519_.  Now
+provided with a total κ age commitments, it can calculate the corresponding κ
+age commitment hash values :math:`h_a` of those commitments.  With those, it
+can continue to perform the cut&choose protocol, i. e. calculate the disclosed
+κ-1 coin's signatures :math:`\text{FDH}_N(C_p, h_a)` and finally compare the
+hash over all κ signatures with the value given during the melt phase.
 
 Deposit
 ~~~~~~~
@@ -400,7 +413,7 @@ by evaluating
 .. math::
    \text{FDH}_N(C_p, h_a)\; \stackrel{?}{=}\; \left(\sigma_C\right)^{e} \;\;\text{mod}N
 
-Also again, :math:`C_p` is the EdDSA public key of a coin, :math:`\sigma_C` is
+Also again, :math:`C_p` is the Edx25519_ public key of a coin, :math:`\sigma_C` is
 its signature, :math:`\langle e, N \rangle` is the RSA public key of the
 denomination and :math:`h_a` is the value from ``age_commitment_hash``.
 
@@ -454,7 +467,7 @@ age by
 
    * and then  ―for each such coin― it has the right private key of the
      restricted age commitment to the age group into which the required minimum
-     age falls (i.e.  a non-empty entry at the right index in vector of EdDSA
+     age falls (i.e.  a non-empty entry at the right index in vector of Edx25519
      keys, see above).
 
    * and signs the required minimum age with each coin's private key
@@ -475,12 +488,12 @@ The object ``CoinPaySig`` used within a ``PayRequest`` during a POST to
    // are at least committed to the corresponding age group, this is the
    // signature of the minimum age as a string, using the private key to the
    // corresponding age group.
-   minimum_age_sig?: EddsaSignature;
+   minimum_age_sig?: Edx25519Signature;
 
    // If a minimum age was required by the order, this is age commitment bound
-   // to the coin, i.e. the complete vector of EdDSA public keys, one for each
+   // to the coin, i.e. the complete vector of Edx25519_ public keys, one for each
    // age group (as defined by the exchange).
-   age_commitment?: EddsaPublicKey[];
+   age_commitment?: Edx25519PublicKey[];
 
    }
 
@@ -491,7 +504,7 @@ The merchant can now verify
 
    .. math:: \text{FDH}_N(C_p, h_a)\; \stackrel{?}{=}\; \left(\sigma_C\right)^{e} \;\;\text{mod}N
 
-   Again, :math:`C_p` is the EdDSA public key of a coin, :math:`\sigma_C` is
+   Again, :math:`C_p` is the Edx25519_ public key of a coin, :math:`\sigma_C` is
    its signature, :math:`\langle e, N \rangle` is the RSA public key of the
    denomination and :math:`h_a` is the SHA256 hash value of the vector in
    ``age_commitment``.
@@ -548,7 +561,6 @@ Discussion / Q&A
 We had some very engaged discussions on the GNU Taler `mailing list <taler@gnu.org>`__:
 
 * `Money with capabilities <https://lists.gnu.org/archive/html/taler/2021-08/msg00005.html>`_
-  
 
 * `On age-restriction (was: online games in China) <https://lists.gnu.org/archive/html/taler/2021-09/msg00006.html>`__
 
@@ -557,3 +569,108 @@ We had some very engaged discussions on the GNU Taler `mailing list <taler@gnu.o
 
 The upcoming paper on anonymous age-restriction for GNU Taler from Özgür Kesim
 and Christian Grothoff will be cited here, once it is published.
+
+.. _Edx25519:
+
+Edx25519
+========
+
+Edx25519 is a variant of EdDSA on curve25519 which allows for repeated
+derivation of private and public keys, independently.  It is implemented in
+`GNUNET with commit ce38d1f6c9bd7857a1c3bc2094a0ee9752b86c32.
+<https://git.gnunet.org/gnunet.git/commit/?id=ce38d1f6c9bd7857a1c3bc2094a0ee9752b86c32>`__
+
+The private keys in Edx25519 initially correspond to the data after expansion
+and clamping in EdDSA.  However, this correspondence is lost after deriving
+further keys from existing ones.  The public keys and signature verification
+are compatible with EdDSA.
+
+The scheme is as follows:
+
+::
+
+    /* Private keys in Edx25519 are pairs (a, b) of 32 byte each.
+     * Initially they correspond to the result of the expansion
+     * and clamping in EdDSA.
+     */
+
+    Edx25519_generate_private(seed) {
+      /* EdDSA expand and clamp */
+      dh := SHA-512(seed)
+      a := dh[0..31]
+      b := dh[32..64]
+      a[0]  &= 0b11111000
+      a[31] &= 0b01111111
+      a[31] |= 0b01000000
+
+      return (a, b)
+    }
+
+    Edx25519_public_from_private(private) {
+      /* Public keys are the same as in EdDSA */
+      (a, _) := private
+      return [a] * G
+    }
+
+    Edx25519_blinding_factor(P, seed) {
+      /* This is a helper function used in the derivation of
+       * private/public keys from existing ones.  */
+      h1 := HKDF_32(P, seed)
+
+      /* Ensure that h == h % L */
+      h := h1 % L
+
+      /* Optionally: Make sure that we don't create weak keys. */
+      P' := [h] * P
+      if !( (h!=1) && (h!=0) && (P'!=E) ) {
+        return Edx25519_blinding_factor(P, seed+1)
+      }
+
+      return h
+    }
+
+    Edx25519_derive_private(private, seed) {
+      /* This is based on the definition in
+       * GNUNET_CRYPTO_eddsa_private_key_derive.  But it accepts
+       * and returns a private pair (a, b) and allows for iteration.
+       */
+      (a, b) := private
+      P := Edx25519_public_key_from_private(private)
+      h := Edx25519_blinding_factor(P, seed)
+
+      /* Carefully calculate the new value for a */
+      a1 := a / 8;
+      a2 := (h  * a1) % L
+      a' := (a2 *  8) % L
+
+      /* Update b as well, binding it to h.
+         This is an additional step compared to GNS. */
+      b' := SHA256(b ∥ h)
+
+      return (a', b')
+    }
+
+    Edx25519_derive_public(P, seed) {
+      h := Edx25519_blinding_factor(P, seed)
+      return [h]*P
+    }
+
+    Edx25519_sign(private, message) {
+      /* As in Ed25519, except for the origin of b */
+      (d, b) := private
+      P := Edx25519_public_from_private(private)
+      r := SHA-512(b ∥ message)
+      R := [r] * G
+      s := r + SHA-512(R ∥ P ∥ message) * d % L
+
+      return (R,s)
+    }
+
+    Edx25519_verify(P, message, signature) {
+      /* Identical to Ed25519 */
+      (R, s) := signature
+      return [s] * G == R + [SHA-512(R ∥ P ∥ message)] * P
+    }
+
+::
+