summaryrefslogtreecommitdiff
path: root/games
diff options
context:
space:
mode:
authorJeff Burdges <burdges@gnunet.org>2018-04-25 02:07:10 +0200
committerJeff Burdges <burdges@gnunet.org>2018-04-25 02:07:10 +0200
commit0edaad75bb56814a2186fa488b540ede18581f6f (patch)
treee03a6ea023a8ad3d3bf3091010be8abf042c8bca /games
parent745b5a51ce854d7dba1c4a38584761e6160042d0 (diff)
downloadpapers-0edaad75bb56814a2186fa488b540ede18581f6f.tar.gz
papers-0edaad75bb56814a2186fa488b540ede18581f6f.tar.bz2
papers-0edaad75bb56814a2186fa488b540ede18581f6f.zip
sleepy time
Diffstat (limited to 'games')
-rw-r--r--games/games.tex32
1 files changed, 22 insertions, 10 deletions
diff --git a/games/games.tex b/games/games.tex
index 402f4ad..e5bb2fc 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -493,13 +493,13 @@ Let \oraSet{Income} stand for access to the oracles
\item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{Income}}(pkExchange)$
\item Augment the wallets of all non-corrupted users with their
transitive closure using the \algo{Link} protocol.
- Spend all remaining value on coins in wallets of non-corrupted users with \algo{Deposit}.\footnote{If \algo{Deposit} can only be run once per coin, then run a similar alggorithm that ignores this check.}
+ Spend all remaining value on coins in wallets of non-corrupted users with \algo{Deposit}.\footnote{If \algo{Deposit} can only be run once per coin, then run a similar algorithm that ignores this check.}
\item Let $L$ be the sum of unspent value for valid coins in $C_1, \dots\, C_\ell$, after
accounting for the previous spending step.
\item Let $w$ be the sum of coins withdrawn by non-corrupted users,
- $w'$ be the sum of coins withdrawn by corruped users, and $s$ be the value marked as spent
+ $w'$ be the sum of coins withdrawn by corrupted users, and $s$ be the value marked as spent
by non-corrupted users.
- \item Return $p \over b + p$ where $b := w - s$ gives the lost coins and $p := L - w'$ gives the adversary's winnings.
+ \item If defined, we return $p \over b + p$ where $b := w - s$ gives the lost coins and $p := L - w'$ gives the adversary's winnings.
Also, we note our adversary wins the strong income transparency game if $L - w' > 0$.
\comment{$(L, w, w', s)$ Big stile break so split into two games. Return ratio. Two expectations is wrong. }
\end{enumerate}
@@ -904,17 +904,29 @@ false planchet has only a $1\over\kappa$ chance of succeeding.
If such a malicious refresh is detected, the coin becomes unspendable,
and contributes to the lost coins $b := w - s$
instead of the winnings $p := L - w'$ aka $|X|$.
-We observe $b + p$ gives the value of refreshes attempted with false planchets.
-We shall now prove $E({p \over b + p}) = {1\over\kappa}$ (\dag)
+We observe $b + p$ gives the value of refreshes attempted with
+false planchets. Of course $p = 0$ and $b = 0$ if the adversary never
+uses false planchets, so no $R_C$ occur, leaving $p \over b + p$ undefined.
+
+We shall prove $E({p \over b + p}) = {1\over\kappa}$ (\dag)
+with the expectation taken over games with false planchets.
+We obtain a valid game by terminating a game early, so
+ we work by induction on the length of the game.
+
+% https://math.stackexchange.com/questions/852890/expectation-of-random-variables-ratio
+If we group together the games identical up until some $R_C$ with value $v$,
+then we find $R_C$
+...
+contributes $v\over\kappa$ to $p$ and $\kappa v$ to $b + p$.
+
+
by grouping games identical up to an $R_C$
according to the simulator's random choice of $\gamma$.
-We obtain a valid game by terminating a game early, so
- we construct the desire grouping by induction on the length of the game.
-Of course $b = 0$ if no $R_C$ occur.
+Of course
We defined $R_C$ to be an anti-chain in the refresh forest, but
-we emphasize that an adversary who wins an $R_C$ need not gamble again,
-while an an adversary who looses an $R_C$ looses $C$.
+emphasize that an adversary who wins an $R_C$ should not gamble again,
+while an adversary who looses an $R_C$ looses $C$.
It follows that each $R_C$ contributes ${1\over\kappa}$ towards the total expectation.
{RETHINK WHAT HAPPENS HERE AND ABOVE}
We conclude that $E({p \over b + p}) = {1\over\kappa}$, as desired.