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}
|
