diff options
| -rw-r--r-- | src/include/taler_exchange_service.h | 55 | ||||
| -rw-r--r-- | src/lib/.gitignore | 1 | ||||
| -rw-r--r-- | src/lib/Makefile.am | 17 | ||||
| -rw-r--r-- | src/lib/exchange_api_stefan.c | 324 | ||||
| -rw-r--r-- | src/lib/test_stefan.c | 217 |
5 files changed, 614 insertions, 0 deletions
diff --git a/src/include/taler_exchange_service.h b/src/include/taler_exchange_service.h index 471263f78..a1a1e3997 100644 --- a/src/include/taler_exchange_service.h +++ b/src/include/taler_exchange_service.h @@ -826,6 +826,61 @@ 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 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; +} |