From 3e47fa9b5052f57e40de33272eb9b6a0f0f5f537 Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Wed, 25 Apr 2018 23:06:16 +0200 Subject: Income transperency goes full optimality argument --- games/games.tex | 43 ++++++++++++++++++++++--------------------- games/rm.tex | 19 +++++++++++++++++++ 2 files changed, 41 insertions(+), 21 deletions(-) create mode 100644 games/rm.tex diff --git a/games/games.tex b/games/games.tex index 72c1793..365013f 100644 --- a/games/games.tex +++ b/games/games.tex @@ -901,11 +901,11 @@ We may assume the first case that $\cal A$ provides a false planchet outright because we produce a key exchange failure in the second case. We shall prove $E({p \over b + p} | X \neq \emptyset) \le {1\over\kappa}$ (\dag) -with the expectation taken over games with false planchets, meaning - any probability space used by the adversary, +meaning any probability space used by the adversary, times the uniform distribution on exchange keys $\V{skE}$, times the space of $\gamma$ choices by the exchange, i.e. the uniform distribution on $\kappa^X$. +with the expectation taken over games with false planchets We shall optimizes our adversary in ways that improve its $p \over b + p$. We cannot actually produce this optimized adversary ourselves, @@ -930,30 +930,31 @@ for at most one choice of $\gamma$ in $R_C$, We defined $R_C$ to be an anti-chain in the refresh forest, but emphasize that an adversary who looses an $R_C$ looses $C$ completely, -while an optimal adversary who wins an $R_C$ should not gamble again. -There is no way to influence $p$ or $b$ through withdrawals or spends -by corrupted users of course. In principle, one could decrease $b$ by - sharing from a corrupted user to a non-corrupted users, -but we may assume this does not occur either, again by optimality. - +while an optimal adversary who wins an $R_C$ should not gamble again. +Indeed, an adversary has no reason to touch its winnings from an $R_C$. +% There is no way to influence $p$ or $b$ through withdrawals or spends +% by corrupted users of course. In principle, one could decrease $b$ by +% sharing from a corrupted user to a non-corrupted users, +% but we may assume this does not occur either, again by optimality. -We obtain a valid game run by terminating a game early, or even by -blocking oracle calls on decedents of a particular coin $C$, - which we refer to as a strictly simpler game run. -We shall prove $E({p \over b + p}) = {1\over\kappa}$ (\dag) -with the expectation taken over games with false planchets - in which the adversary plays optimally - in that no strictly simpler game run increases $p \over b + p$. - -For any $R_C$, +An adversary may respond adaptively to $\gamma$ of course, but, +for any $R_C$, there are $\kappa$ game runs identical up through the commitment phase -of $R_C$ that diverge in simulator's random choice of $\gamma$, - and blocks $C$ afterwards. +of $R_C$ that diverge in simulator's random choice of $\gamma$. +% and suppress $C$'s decendents by optimality. If $v$ is the value of $R_C$ then one run adds $v$ to $p$, while - the remaining $\kappa-1$ runs add $v$ to $b$. + the remaining $\kappa-1$ runs add $v$ to $b$. + +We define $p_C$ and $b_C$ to be these contributions summed + over the $\kappa$ runs, so $\kappa p_C = b_C + p_C$. +Now $p = {1\over\kappa |X|} \sum_{C \in X} p_C$ + and $b = {1\over\kappa |X|} \sum_{C \in X} b_C$ +so $E({p \over b + p} | X \neq \emptyset) = {1\over\kappa}$, + which yields the inequality (\dag). + + -An adversary may respond adaptively to $\gamma$ of course, but induction on the length of the game now still produces disjoint groupings $\mathbb{G}$ of optimal games in which $\sum_{\mathbb{G}} {p \over b + p} = {1\over\kappa} |\mathbb{G}|$. diff --git a/games/rm.tex b/games/rm.tex new file mode 100644 index 0000000..61e1691 --- /dev/null +++ b/games/rm.tex @@ -0,0 +1,19 @@ + +We obtain a valid game run by terminating a game early of course, +We may consider the adversaries ${\cal A}_n$ obtained by terminating +$\cal A$ after the first $n$ refresh attempts $R_C$ with false planchets. +Also ${\cal A}_n$ inherits optimality from $\cal A$. + +We shall now prove $E({p \over b + p} | X \neq \emptyset) = {1\over\kappa}$ for ${\cal A}_n$. + +We shall prove $E({p \over b + p} | X \neq \emptyset) = {1\over\kappa}$ (\dag) +with the expectation taken over games with false planchets + in which the adversary plays optimally + in that no strictly simpler game run increases $p \over b + p$. + + +induction on the length of the game now still produces disjoint groupings +$\mathbb{G}$ of optimal games in which + $\sum_{\mathbb{G}} {p \over b + p} = {1\over\kappa} |\mathbb{G}|$. +We conclude that $E({p \over b + p}) = {1\over\kappa}$, as desired. + -- cgit v1.2.3