aboutsummaryrefslogtreecommitdiff
path: root/src/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/.gitignore1
-rw-r--r--src/lib/Makefile.am17
-rw-r--r--src/lib/exchange_api_stefan.c324
-rw-r--r--src/lib/test_stefan.c217
4 files changed, 559 insertions, 0 deletions
diff --git a/src/lib/.gitignore b/src/lib/.gitignore
new file mode 100644
index 000000000..6664876f2
--- /dev/null
+++ b/src/lib/.gitignore
@@ -0,0 +1 @@
+test_stefan
diff --git a/src/lib/Makefile.am b/src/lib/Makefile.am
index f69a4e81a..6ff8e2371 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 000000000..a0650c77f
--- /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 000000000..6941538f2
--- /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;
+}