[taler-exchange] branch master updated: implement STEFAN value calculation

[gnunet]

This is an automated email from the git hooks/post-receive script.

grothoff pushed a commit to branch master
in repository exchange.

The following commit(s) were added to refs/heads/master by this push:
     new 37885514 implement STEFAN value calculation
37885514 is described below

commit 378855142edc575c55b446f34d748ef3c4fe74f7
Author: Christian Grothoff <christian@grothoff.org>
AuthorDate: Thu Aug 24 20:50:47 2023 +0200

    implement STEFAN value calculation
---
 src/include/taler_exchange_service.h |  55 ++++++
 src/lib/.gitignore                   |   1 +
 src/lib/Makefile.am                  |  17 ++
 src/lib/exchange_api_stefan.c        | 324 +++++++++++++++++++++++++++++++++++
 src/lib/test_stefan.c                | 217 +++++++++++++++++++++++
 5 files changed, 614 insertions(+)

diff --git a/src/include/taler_exchange_service.h 
b/src/include/taler_exchange_service.h
index 471263f7..a1a1e399 100644
--- a/src/include/taler_exchange_service.h
+++ b/src/include/taler_exchange_service.h
@@ -825,6 +825,61 @@ void
 TALER_EXCHANGE_keys_decref (struct TALER_EXCHANGE_Keys *keys);
 
 
+/**
+ * Use STEFAN curve in @a keys to convert @a brut to @a net.  Computes the
+ * expected minimum (!) @a net amount that should for sure arrive in the
+ * target amount at cost of @a brut to the wallet. Note that STEFAN curves by
+ * design over-estimate actual fees and a wallet may be able to achieve the
+ * same @a net amount with less fees --- or if the available coins are
+ * abnormal in structure, it may take more.
+ *
+ * @param keys exchange key data
+ * @param brut gross amount (actual cost including fees)
+ * @param[out] net net amount (effective amount)
+ * @return #GNUNET_OK on success, #GNUNET_NO if the
+ *   resulting @a net is zero (or lower)
+ */
+enum GNUNET_GenericReturnValue
+TALER_EXCHANGE_keys_stefan_b2n (
+  const struct TALER_EXCHANGE_Keys *keys,
+  const struct TALER_Amount *brut,
+  struct TALER_Amount *net);
+
+
+/**
+ * Use STEFAN curve in @a keys to convert @a net to @a brut.  Computes the
+ * expected maximum (!) @a brut amount that should be needed in the wallet to
+ * transfer @a net amount to the target account.  Note that STEFAN curves by
+ * design over-estimate actual fees and a wallet may be able to achieve the
+ * same @a net amount with less fees --- or if the available coins are
+ * abnormal in structure, it may take more.
+ *
+ * @param keys exchange key data
+ * @param net net amount (effective amount)
+ * @param[out] brut gross amount (actual cost including fees)
+ * @return #GNUNET_OK on success, #GNUNET_NO if the
+ *   resulting @a brut is zero (only if @a net was zero)
+ */
+enum GNUNET_GenericReturnValue
+TALER_EXCHANGE_keys_stefan_n2b (
+  const struct TALER_EXCHANGE_Keys *keys,
+  const struct TALER_Amount *net,
+  struct TALER_Amount *brut);
+
+
+/**
+ * Round brutto or netto value computed via STEFAN
+ * curve to decimal places commonly used at the exchange.
+ *
+ * @param keys exchange keys response data
+ * @param[in,out] val value to round
+ */
+void
+TALER_EXCHANGE_keys_stefan_round (
+  const struct TALER_EXCHANGE_Keys *keys,
+  struct TALER_Amount *val);
+
+
 /**
  * Test if the given @a pub is a the current signing key from the exchange
  * according to @a keys.
diff --git a/src/lib/.gitignore b/src/lib/.gitignore
new file mode 100644
index 00000000..6664876f
--- /dev/null
+++ b/src/lib/.gitignore
@@ -0,0 +1 @@
+test_stefan
diff --git a/src/lib/Makefile.am b/src/lib/Makefile.am
index f69a4e81..6ff8e237 100644
--- a/src/lib/Makefile.am
+++ b/src/lib/Makefile.am
@@ -74,6 +74,7 @@ libtalerexchange_la_SOURCES = \
   exchange_api_reserves_history.c \
   exchange_api_reserves_open.c \
   exchange_api_reserves_status.c \
+  exchange_api_stefan.c \
   exchange_api_transfers_get.c \
   exchange_api_withdraw.c \
   exchange_api_withdraw2.c
@@ -107,5 +108,21 @@ libtalerauditor_la_LIBADD = \
   -lgnunetjson \
   -lgnunetutil \
   -ljansson \
+  -lm \
   $(LIBGNURLCURL_LIBS) \
   $(XLIB)
+
+
+check_PROGRAMS = \
+ test_stefan
+
+TESTS = \
+ $(check_PROGRAMS)
+
+
+test_stefan_SOURCES = \
+  test_stefan.c
+test_stefan_LDADD = \
+  $(top_builddir)/src/lib/libtalerexchange.la \
+  $(top_builddir)/src/util/libtalerutil.la \
+  -lgnunetutil
diff --git a/src/lib/exchange_api_stefan.c b/src/lib/exchange_api_stefan.c
new file mode 100644
index 00000000..a0650c77
--- /dev/null
+++ b/src/lib/exchange_api_stefan.c
@@ -0,0 +1,324 @@
+/*
+  This file is part of TALER
+  Copyright (C) 2023 Taler Systems SA
+
+  TALER is free software; you can redistribute it and/or modify it under the
+  terms of the GNU General Public License as published by the Free Software
+  Foundation; either version 3, or (at your option) any later version.
+
+  TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+  A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License along with
+  TALER; see the file COPYING.  If not, see
+  <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file lib/exchange_api_stefan.c
+ * @brief calculations on the STEFAN curve
+ * @author Christian Grothoff
+ */
+#include "platform.h"
+#include "taler_json_lib.h"
+#include <gnunet/gnunet_curl_lib.h>
+#include "exchange_api_handle.h"
+#include <math.h>
+
+
+/**
+ * Determine smallest denomination in @a keys.
+ *
+ * @param keys exchange response to evaluate
+ * @return NULL on error (no denominations)
+ */
+static const struct TALER_Amount *
+get_unit (const struct TALER_EXCHANGE_Keys *keys)
+{
+  const struct TALER_Amount *min = NULL;
+
+  for (unsigned int i = 0; i<keys->num_denom_keys; i++)
+  {
+    const struct TALER_EXCHANGE_DenomPublicKey *dk
+      = &keys->denom_keys[i];
+
+    if ( (NULL == min) ||
+         (1 == TALER_amount_cmp (min,
+                                 /* > */
+                                 &dk->value)) )
+      min = &dk->value;
+  }
+  GNUNET_break (NULL != min);
+  return min;
+}
+
+
+/**
+ * Convert amount to double for STEFAN curve evaluation.
+ *
+ * @param a input amount
+ * @return (rounded) amount as a double
+ */
+static double
+amount_to_double (const struct TALER_Amount *a)
+{
+  double d = (double) a->value;
+
+  d += a->fraction / ((double) TALER_AMOUNT_FRAC_BASE);
+  return d;
+}
+
+
+/**
+ * Convert double to amount for STEFAN curve evaluation.
+ *
+ * @param a input amount
+ * @return (rounded) amount as a double
+ */
+static void
+double_to_amount (double dv,
+                  const char *currency,
+                  struct TALER_Amount *rval)
+{
+  double rem;
+
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_amount_set_zero (currency,
+                                        rval));
+  rval->value = floorl (dv);
+  rem = dv - ((double) rval->value);
+  if (rem < 0.0)
+    rem = 0.0;
+  rem *= TALER_AMOUNT_FRAC_BASE;
+  rval->fraction = floorl (rem);
+  if (rval->fraction >= TALER_AMOUNT_FRAC_BASE)
+  {
+    /* Strange, multiplication overflowed our range,
+       round up value instead */
+    rval->fraction = 0;
+    rval->value += 1;
+  }
+}
+
+
+enum GNUNET_GenericReturnValue
+TALER_EXCHANGE_keys_stefan_b2n (
+  const struct TALER_EXCHANGE_Keys *keys,
+  const struct TALER_Amount *brut,
+  struct TALER_Amount *net)
+{
+  const struct TALER_Amount *min;
+  double log_d = amount_to_double (&keys->stefan_log);
+  double lin_d = amount_to_double (&keys->stefan_lin);
+  double abs_d = amount_to_double (&keys->stefan_abs);
+  double bru_d = amount_to_double (brut);
+  double min_d;
+  double fee_d;
+  double net_d;
+
+  if (TALER_amount_is_zero (brut))
+  {
+    *net = *brut;
+    return GNUNET_NO;
+  }
+  min = get_unit (keys);
+  if (NULL == min)
+    return GNUNET_SYSERR;
+  if (1 != TALER_amount_cmp (min,
+                             /* <= */
+                             &keys->stefan_lin))
+  {
+    /* This cannot work, linear STEFAN fee estimate always
+       exceed any gross amount. */
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  min_d = amount_to_double (min);
+  fee_d = abs_d
+          + log_d * log2 (bru_d / min_d)
+          + lin_d * (bru_d / min_d);
+  if (fee_d > bru_d)
+  {
+    GNUNET_assert (GNUNET_OK ==
+                   TALER_amount_set_zero (brut->currency,
+                                          net));
+    return GNUNET_NO;
+  }
+  net_d = bru_d - fee_d;
+  double_to_amount (net_d,
+                    brut->currency,
+                    net);
+  return GNUNET_OK;
+}
+
+
+/**
+ * Our function
+ * f(x) := ne + ab + lo * log2(x/mi) + li * x / mi - x
+ * for #newton().
+ */
+static double
+eval_f (double mi,
+        double ab,
+        double lo,
+        double li,
+        double ne,
+        double x)
+{
+  return ne + ab + lo * log2 (x / mi) + li * (x / mi) - x;
+}
+
+
+/**
+ * Our function
+ * f'(x) := lo / log(2) / x + li / mi - 1
+ * for #newton().
+ */
+static double
+eval_fp (double mi,
+         double lo,
+         double li,
+         double ne,
+         double x)
+{
+  return lo / log (2) / x + li / mi - 1;
+}
+
+
+/**
+ * Use Newton's method to find x where f(x)=0.
+ *
+ * @return x where "eval_f(x)==0".
+ */
+static double
+newton (double mi,
+        double ab,
+        double lo,
+        double li,
+        double ne)
+{
+  const double eps = 0.00000001; /* max error allowed */
+  double min_ab = ne + ab; /* result cannot be smaller than this! */
+  double lin_factor = (mi - li); /* how many coins do we need per coin for 
linear factor? */
+  /* compute lower bounds by various heuristics */
+  double min_ab_li = min_ab + min_ab * li / lin_factor;
+  double min_ab_li_lo = min_ab_li + log2 (min_ab_li / mi) * lo;
+  double min_ab_lo = min_ab + log2 (min_ab / mi) * lo;
+  double min_ab_lo_li = min_ab_lo + min_ab_lo * li / lin_factor;
+  /* take global lower bound */
+  double x_min = GNUNET_MAX (min_ab_lo_li,
+                             min_ab_li_lo);
+  double x = x_min; /* use lower bound as starting point */
+
+  /* Objective: invert
+     ne := br - ab - lo * log2 (br/mi) - li (br/mi)
+     to find 'br'.
+     Method: use Newton's method to find root of:
+     f(x) := ne + ab + lo * log2 (x/mi) + li * x / mi - x
+     using also
+     f'(x) := lo / log(2) / x  + li / mi - 1
+  */
+  /* Loop to abort in case of divergence;
+     100 is already very high, 2-4 is normal! */
+  for (unsigned int i = 0; i<100; i++)
+  {
+    double fx = eval_f (mi, ab, lo, li, ne, x);
+    double fxp = eval_fp (mi, lo, li, ne, x);
+    double x_new = x - fx / fxp;
+
+    if (fabs (x - x_new) <= eps)
+    {
+      GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+                  "Needed %u rounds from %f to result BRUT %f => NET: %f\n",
+                  i,
+                  x_min,
+                  x_new,
+                  x_new - ab - li * (x_new / mi) - lo * log2 (x / mi));
+      return x_new;
+    }
+    if (x_new < x_min)
+    {
+      GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+                  "Divergence, obtained very bad estimate %f after %u 
rounds!\n",
+                  x_new,
+                  i);
+      return x_min;
+    }
+    x = x_new;
+  }
+  GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+              "Slow convergence, returning bad estimate %f!\n",
+              x);
+  return x;
+}
+
+
+enum GNUNET_GenericReturnValue
+TALER_EXCHANGE_keys_stefan_n2b (
+  const struct TALER_EXCHANGE_Keys *keys,
+  const struct TALER_Amount *net,
+  struct TALER_Amount *brut)
+{
+  const struct TALER_Amount *min;
+  double lin_d = amount_to_double (&keys->stefan_lin);
+  double log_d = amount_to_double (&keys->stefan_log);
+  double abs_d = amount_to_double (&keys->stefan_abs);
+  double net_d = amount_to_double (net);
+  double min_d;
+  double brut_d;
+
+  if (TALER_amount_is_zero (net))
+  {
+    *brut = *net;
+    return GNUNET_NO;
+  }
+  min = get_unit (keys);
+  if (NULL == min)
+    return GNUNET_SYSERR;
+  if (1 != TALER_amount_cmp (min,
+                             /* <= */
+                             &keys->stefan_lin))
+  {
+    /* This cannot work, linear STEFAN fee estimate always
+       exceed any gross amount. */
+    GNUNET_break_op (0);
+    return GNUNET_SYSERR;
+  }
+  min_d = amount_to_double (min);
+  brut_d = newton (min_d,
+                   abs_d,
+                   log_d,
+                   lin_d,
+                   net_d);
+  double_to_amount (brut_d,
+                    net->currency,
+                    brut);
+  return GNUNET_OK;
+}
+
+
+void
+TALER_EXCHANGE_keys_stefan_round (
+  const struct TALER_EXCHANGE_Keys *keys,
+  struct TALER_Amount *val)
+{
+  const struct TALER_Amount *min;
+  uint32_t mod = 1;
+  uint32_t frac;
+  uint32_t rst;
+
+  min = get_unit (keys);
+  if (NULL == min)
+    return;
+  frac = min->fraction;
+  while (0 == frac % 10)
+  {
+    mod *= 10;
+    frac /= 10;
+  }
+  rst = val->fraction % mod;
+  if (rst < mod / 2)
+    val->fraction -= rst;
+  else
+    val->fraction += mod - rst;
+}
diff --git a/src/lib/test_stefan.c b/src/lib/test_stefan.c
new file mode 100644
index 00000000..6941538f
--- /dev/null
+++ b/src/lib/test_stefan.c
@@ -0,0 +1,217 @@
+/*
+  This file is part of TALER
+  Copyright (C) 2023 Taler Systems SA
+
+  TALER is free software; you can redistribute it and/or modify it under the
+  terms of the GNU General Public License as published by the Free Software
+  Foundation; either version 3, or (at your option) any later version.
+
+  TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+  A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License along with
+  TALER; see the file COPYING.  If not, see
+  <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file lib/test_stefan.c
+ * @brief test calculations on the STEFAN curve
+ * @author Christian Grothoff
+ */
+#include "platform.h"
+#include "taler_json_lib.h"
+#include <gnunet/gnunet_curl_lib.h>
+#include "exchange_api_handle.h"
+
+
+/**
+ * Check if @a a and @a b are numerically close.
+ *
+ * @param a an amount
+ * @param b an amount
+ * @return true if both values are quite close
+ */
+static bool
+amount_close (const struct TALER_Amount *a,
+              const struct TALER_Amount *b)
+{
+  struct TALER_Amount delta;
+
+  switch (TALER_amount_cmp (a,
+                            b))
+  {
+  case -1: /* a < b */
+    GNUNET_assert (0 <
+                   TALER_amount_subtract (&delta,
+                                          b,
+                                          a));
+    break;
+  case 0:
+    /* perfect */
+    return true;
+  case 1: /* a > b */
+    GNUNET_assert (0 <
+                   TALER_amount_subtract (&delta,
+                                          a,
+                                          b));
+    break;
+  }
+  GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+              "Rounding error is %s\n",
+              TALER_amount2s (&delta));
+  if (delta.value > 0)
+  {
+    GNUNET_break (0);
+    return false;
+  }
+  if (delta.fraction > 5000)
+  {
+    GNUNET_break (0);
+    return false;
+  }
+  return true; /* let's consider this a rounding error */
+}
+
+
+int
+main (int argc,
+      char **argv)
+{
+  struct TALER_EXCHANGE_DenomPublicKey dk;
+  struct TALER_EXCHANGE_Keys keys = {
+    .denom_keys = &dk,
+    .num_denom_keys = 1
+  };
+  struct TALER_Amount brut;
+  struct TALER_Amount net;
+
+  (void) argc;
+  (void) argv;
+  GNUNET_log_setup ("test-stefan",
+                    "INFO",
+                    NULL);
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:0.13",
+                                         &dk.value));
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:1",
+                                         &keys.stefan_abs));
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:0.13",
+                                         &keys.stefan_log));
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:0.15",
+                                         &keys.stefan_lin));
+
+  /* stefan_lin >= unit value, not allowed, test we fail */
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:4",
+                                         &brut));
+  GNUNET_log_skip (1,
+                   GNUNET_NO);
+  GNUNET_assert (GNUNET_SYSERR ==
+                 TALER_EXCHANGE_keys_stefan_b2n (&keys,
+                                                 &brut,
+                                                 &net));
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:4",
+                                         &net));
+  GNUNET_log_skip (1,
+                   GNUNET_NO);
+  GNUNET_assert (GNUNET_SYSERR ==
+                 TALER_EXCHANGE_keys_stefan_n2b (&keys,
+                                                 &net,
+                                                 &brut));
+
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:0.13",
+                                         &keys.stefan_lin));
+
+  /* stefan_lin == unit value, not allowed, test we fail */
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:4",
+                                         &brut));
+  GNUNET_log_skip (1,
+                   GNUNET_NO);
+  GNUNET_assert (GNUNET_SYSERR ==
+                 TALER_EXCHANGE_keys_stefan_b2n (&keys,
+                                                 &brut,
+                                                 &net));
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:4",
+                                         &net));
+  GNUNET_log_skip (1,
+                   GNUNET_NO);
+  GNUNET_assert (GNUNET_SYSERR ==
+                 TALER_EXCHANGE_keys_stefan_n2b (&keys,
+                                                 &net,
+                                                 &brut));
+  GNUNET_assert (0 == GNUNET_get_log_skip ());
+  GNUNET_assert (GNUNET_OK ==
+                 TALER_string_to_amount ("MAGIC:0.1",
+                                         &keys.stefan_lin));
+
+  /* try various values for lin and log STEFAN values */
+  for (unsigned int li = 1; li < 13; li += 1)
+  {
+    keys.stefan_lin.fraction = li * TALER_AMOUNT_FRAC_BASE / 100;
+
+    for (unsigned int lx = 1; lx < 100; lx += 1)
+    {
+      keys.stefan_log.fraction = lx * TALER_AMOUNT_FRAC_BASE / 100;
+
+      /* Check brutto-to-netto is stable */
+      for (unsigned int i = 0; i<10; i++)
+      {
+        struct TALER_Amount rval;
+
+        brut.value = i;
+        brut.fraction = i * TALER_AMOUNT_FRAC_BASE / 10;
+        GNUNET_assert (GNUNET_SYSERR !=
+                       TALER_EXCHANGE_keys_stefan_b2n (&keys,
+                                                       &brut,
+                                                       &net));
+        GNUNET_assert (GNUNET_SYSERR !=
+                       TALER_EXCHANGE_keys_stefan_n2b (&keys,
+                                                       &net,
+                                                       &rval));
+        if (TALER_amount_is_zero (&net))
+          GNUNET_assert (TALER_amount_is_zero (&rval));
+        else
+        {
+          GNUNET_assert (amount_close (&brut,
+                                       &rval));
+          TALER_EXCHANGE_keys_stefan_round (&keys,
+                                            &rval);
+          GNUNET_assert (amount_close (&brut,
+                                       &rval));
+        }
+      }
+
+      /* Check netto-to-brutto is stable */
+      for (unsigned int i = 0; i<10; i++)
+      {
+        struct TALER_Amount rval;
+
+        net.value = i;
+        net.fraction = i * TALER_AMOUNT_FRAC_BASE / 10;
+        GNUNET_assert (GNUNET_SYSERR !=
+                       TALER_EXCHANGE_keys_stefan_n2b (&keys,
+                                                       &net,
+                                                       &brut));
+        GNUNET_assert (GNUNET_SYSERR !=
+                       TALER_EXCHANGE_keys_stefan_b2n (&keys,
+                                                       &brut,
+                                                       &rval));
+        GNUNET_assert (amount_close (&net,
+                                     &rval));
+        TALER_EXCHANGE_keys_stefan_round (&keys,
+                                          &rval);
+        GNUNET_assert (amount_close (&net,
+                                     &rval));
+      }
+    }
+  }
+  return 0;
+}

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.