**diff options**

Diffstat (limited to 'coinselection/ilp.tex')

-rw-r--r-- | coinselection/ilp.tex | 42 |

1 files changed, 36 insertions, 6 deletions

diff --git a/coinselection/ilp.tex b/coinselection/ilp.tex index ee74b60..b182000 100644 --- a/coinselection/ilp.tex +++ b/coinselection/ilp.tex @@ -19,6 +19,8 @@ changes the denomination. So technically this formula depends on the exact coins we would obtain from a refresh. But in a first approximation, some bound like this should hold for sanity.} +\item[$r_c$] Let $r_c \in \mathbb N_0$ represent the number of coins of type $c \in {\cal C}$ + that require a refresh after the operation because they were partially spent (deposit ILP only) \item[$p$] Let $p > 0$ be the amount to be paid in the spend/deposit operation (deposit ILP only) \item[$f$] Let $f \ge 0$ be the amount of fees the merchant would cover in the spend/deposit operation (deposit ILP only) \item[$w$] Let $w > 0$ be the amount to be withdrawn (withdraw ILP only) @@ -43,7 +45,8 @@ We will use the big-M method to stress that customers paying any fees is bad.\fo we could use a smaller $M$ to trade-off paying fees for using coins close to expiration. So maybe $M$ should just be a constant to represent this trade-off instead of the traditional big-$M$.} Thus, let $M$ be a sufficiently ``big'' number. We will use $\alpha$ as an -additional cost factor to model the bandwidth and computational cost per coin. +additional cost factor to model the bandwidth and computational cost per coin, and +$\beta$ as an additional cost factor to represent the (approximate) cost of a refresh. \section{Withdraw ILP} @@ -81,10 +84,36 @@ implications on privacy. \section{Deposit ILP} +The following deposit constraint system makes simplfiying assumptions +about the refresh by not fully considering the refresh costs. Imagine +a systen where we have a 1 EUR and a 10 EUR coin, and need to pay 6 +EUR. The system offers 1, 5 and 10 EUR coins. All fees are zero. In +this case, paying with both the 1 EUR and 10 EUR coins might be nice, +as we would get one 5 EUR coin as change. The algorithm below would +always choose paying with just the 10 EUR coin, getting four 1 EUR +coins in change. The simplification results from us not +differenciating between different refresh operations -- we consider +all of them as having roughly the same cost, thus the only objective +is to avoid refreshs overall, but not to pick ``nice'' refreshs. + +This is probably OK for two reasons: (1) the example is a bit +constructed, and is unlikely to appear this extreme with denominations +following powers of two. (2) a more comprehensive algorithm for the +example could still only consider the direct cost of the refresh +operation. However, it might be {\em nice} to have five 1 EUR coins +as this would avoid refresh costs for future operations (more exact +change!). Or it might be terrible, as nobody should eventually pay +with hundreds of 1 cent pieces! However, whether the wallet's coins +would devolve as a result is unclear. It seems likely that such change +would quickly be spent in the next transactions. Thus, analyzing this +choice cannot be done by looking at an individual operation. We might +adjust the model in a future version to capture the alternative design +and then study the affect on larger simulations of many transactions. + \begin{align} \min &M \cdot \tau + \sum_{c \in {\cal C}} s_c + \sum_{c \in {\cal C}} n_c \cdot \alpha) - + refresh-cost \\ + + \sum_{c \in {\cal C}} r_c \cdot \beta \\ \texttt{such that} \quad \bigwedge_{c \in {\cal C}} n_c \cdot d_c &\ge s_c \label{eq:coinnum} \\ \bigwedge_{c \in {\cal C}} n_c &\le a_c \label{eq:exists} \\ @@ -93,7 +122,9 @@ implications on privacy. \sum_{c \in {\cal C}} s_c - \tau p &\le p \label{eq:tau} \\ \tau &\in \{0,1\} \label{eq:bin} \\ n_c &\in {\mathbb N_0} \label{eq:nc} \\ - s_c &\in {\mathbb R^+_0} \label{eq:r} + s_c &\in {\mathbb R^+_0} \label{eq:r} \\ + r_c \cdot d_c + sc_c \ge n_c \cdot d_c \label{eq:refresh} \\ + r_c &\in \{0,1\}_ \label{eq:rc} \end{align} Explanations: @@ -111,14 +142,13 @@ Explanations: \item[\eqref{eq:bin}] Force $\tau$ to be 0 or 1 as per our model. \item[\eqref{eq:nc}] Force selected coins to be a discrete number. \item[\eqref{eq:r}] Force coin contributions to be non-negative. +\item[\eqref{eq:refresh}] If a coin was partially spent, force $r_c$ to be 1 instead of 0. +\item[\eqref{eq:rc}] Force $r_c$ to be 0 or 1 as per our model. \end{description} Note that the refresh cost is missing, as for that we will need to introduce a dependency on a withdraw operation as well! -TODO: introduce additional variable to model when coins need to be -refreshed, and model the refresh cost itself! - \section{Refresh ILP} |