summaryrefslogtreecommitdiff log msg author committer range
path: root/coinselection/ilp.tex
blob: 70708970bc307ab51150016c70d0fd0e1875ec43 (plain)
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163  \documentclass{article} \usepackage{amsmath,amssymb} \begin{document} \section{ILP variables} \begin{description} \item[$c$] Let $c \in {\cal C}$ represent a type of a fresh {\em coin} available in the wallet. Coins differ by type if they have a different denomination, fees or expiration date. \item[$a_c$] Let $a_c \ge 0$ represent the number of available fresh coins of type $c \in {\cal C}$. \item[$d_c$] Let $d_c > 0$ represent the denomination of coins of type $c \in {\cal C}$. \item[$f^{op}_c$] Let $f^{op}_c \ge 0$ represent the fee for of coins of type $c \in {\cal C}$ with $op \in \{withdraw,deposit,refresh,refund\}$. \item[$e_c$] Let $e_c \in {\mathbb R}^+$ be a cost function associated with the expiration time for coins of type $c \in {\cal C}$. Larger values are used to express longer expiration times and thus less urgency. $e_c \le f^{refresh}_c + f^{withdraw}_c$ (as otherwise we could just refresh immediately).\footnote{This is a slight simplification, as the refresh itself 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) \end{description} The solution to compute is represented by the coin selection: \begin{description} \item[$s_c$] Let $s_c \in {\mathbb R^+_0}$ represent the contribution of coins of type $c$ to the deposit operation (deposit ILP only) \item[$n_c$] Let $n_c \in {\mathbb N^+_0}$ represent the number of coins of type $c$ selected for the deposit/withdraw operation. \end{description} We will use an additional variable to model the non-linearity that arises from the customer possibly paying fees above the threshold $f$: \begin{description} \item[$\tau$] Let $\tau \in \{0,1\}$ represent the customer paying some fees ($s=1$) or no fees ($s=0$). \end{description} We will use the big-M method to stress that customers paying any fees is bad.\footnote{Note that 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, and $\beta$ as an additional cost factor to represent the (approximate) cost of a refresh. \section{Withdraw ILP} Simple model: \begin{align} \max \sum_{c \in {\cal C}} n_c \cdot d_c - \sum_{c \in {\cal C}} n_c \cdot f^{deposit}_c - \sum_{c \in {\cal C}} n_c \cdot \alpha \\ \texttt{such that} \quad \bigwedge_{c \in {\cal C}} n_c \cdot (d_c + f^{withdraw}_c) &\le w \label{eq:sound} \\ n_c &\in {\mathbb N}_0 \label{eq:nc1} \end{align} Explanations: \begin{description} \item[\eqref{eq:sound}] The withdraw operation is within the budget constraints. \item[\eqref{eq:nc1}] Force selected coins to be a discrete number. \end{description} The above model fails to consider expiration periods of coins. However, is realistic to assume that expiration periods of freshly withdrawn coins will be roughly equal. Coins types with equal denominations and fees where only the expiration time is worse should simply be excluded from ${\cal C}$ to reduce the size of the problem. It also deliberately fails to consider at all what types of coins we already have in the wallet, as that may disclose information about us which might hurt anonymity. This model also fails to capture that we might {\em like} to have coins in the range where we typically spend them. Again, biasing withdrawal based on such data might have negative 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 + \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} \\ \sum_{c \in {\cal C}} s_c &\ge p \label{eq:amount} \\ \sum_{c \in {\cal C}} (s_c - f^{deposit}_c \cdot n_c) + f &\ge p \label{eq:fees} \\ \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} \\ r_c \cdot d_c + s_c &\ge n_c \cdot d_c \label{eq:refresh} \\ r_c &\in \{0,1\} \label{eq:rc} \end{align} Explanations: \begin{description} \item[\eqref{eq:coinnum}] This equation ensures that the number of coins we selected of a type is sufficient to cover the total amount we want to pay with this type of coin. \item[\eqref{eq:exists}] This equation ensures that we do not select more coins of any type than we have in the wallet. \item[\eqref{eq:amount}] The merchant requires that the amount we pay exceeds the contract amount, irrespective of fees which the merchant may cover. \item[\eqref{eq:fees}] The merchant requires that we pay any left-over fees that are not covered by the merchant. \item[\eqref{eq:tau}] Force $\tau$ to be 1 if we pay more than the contract amount (i.e. we cover fees or otherwise simply pay more than necessary). \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! \section{Refresh ILP} The refresh ILP is basically the withdraw ILP. \section{Refund ILP} Probably OK to use a simplistic solution at the merchant; let's leave it out for now. \end{document}