Searching for Optimal Strategies in Proof-of-Stake Mining Games with Access to External Randomness

Anthony Hein, advised by Prof. Matt Weinberg and Dr. Matheus Ferreira

Department of Computer Science, Princeton University

April 10, 2022

4 n-Deficit Tolerance Family of Strategies

plot = Plot[
{
α,
(((α^2) (4-9 α+4 (α^2)))/(1-α-2 (α^2)+(α^3))),
-(((α^2) (-4+8 α+(α^2)-7 (α^3)+3 (α^4)))/(1-α-2 (α^2)+3 (α^4)-3 (α^5)+(α^6))),
(((α^2) (4-12 α+12 (α^2)-7 (α^3)+3 (α^4)+(α^5)-5 (α^6)+4 (α^7)-(α^8)))/(1-2 α+(α^3)-(α^4)+(α^5)-6 (α^7)+9 (α^8)-5 (α^9)+(α^10))),
},
{α,0.32,0.34},
PlotTheme->"Monochrome",
PlotLegends->{"Honest", "1-Deficit Tolerance (SM)", "2-Deficit Tolerance (NSM)", "4-Deficit Tolerance"},
PlotStyle->{Directive[RGBColor[0.560,0.690,0.196] ,Thick], Directive[RGBColor[0.921,0.384,0.211],Thick],Directive[RGBColor[0.368, 0.505,0.709],Thick], Directive[RGBColor[0.882,0.611,0.145],Thick]},
PlotLabel->"Revenue Comparison Between Various Strategies",
AspectRatio->1/2,
TicksStyle->Larger,
AxesLabel->{"α","Revenue"}
]

8.1 Optimal Capitulation from $B_{1,x}$ to $B_0$

plot = Plot[
((1-2α+(α^2))/(α^2)),
{α,0.3080,0.3247},
PlotLegends->"Expressions",
PlotLabel->"",
AspectRatio->1/2,
PlotStyle->Thick,
TicksStyle->Larger,
AxesLabel->{"α","x"}
]

11 4-Deficit Tolerance is Not Optimal for Mining Strength $\apos$

Plot[
{(((((((1-α)/α)))^1)-1)/((((((1-α)/α)))^2)-1)),(((((((1-α)/α)))^2)-1)/((((((1-α)/α)))^3)-1)),(((((((1-α)/α)))^3)-1)/((((((1-α)/α)))^4)-1))},
{α,0.32,0.34},
PlotTheme->"Monochrome",
PlotLegends->{"x=2", "x=3", "x=4"},
PlotStyle->{Directive[RGBColor[0.560,0.690,0.196] ,Thick], Directive[RGBColor[0.921,0.384,0.211],Thick],Directive[RGBColor[0.368, 0.505,0.709],Thick]},
PlotLabel->"Probability of Recovering Block 1",
AspectRatio->1/2,
TicksStyle->Larger,
AxesLabel->{"α","Probability"}
]

12 Automating the Search for Optimal Strategies

p=Simplify[α(2−α)+(1−α)(α(α(3−α)+(1−α)(α(2−α)−α+(1−α)(α(α(3−α)+(1−α)(α(α(α((1−α)(((2α)/(1-2α))+3)+3)+(1−α)(((((α/(1-α))))^2)−2α+((((α/(1-α))))^1)+3))+(1−α)(((((α/(1-α))))^3)+((((α/(1-α))))^2)−α+((2α)/(1-α))))−α+(1−α)(((((α/(1-α))))^4)+((((α/(1-α))))^3)+((((α/(1-α))))^2)−α)))−α+(1−α)(α(α(α(α((1−α)((((3α)/(1-2α)))+4)+2)+(1−α)(((((α/(1-α))))^2)−α+((((α/(1-α))))^1)+(1−α)((α/(1-2α))+2)+1))+(1−α)(α(((((α/(1-α))))^2)+((((α/(1-α))))^1)+(1−α)((α/(1-2α))+2)+1)−α+(1−α)(((((α/(1-α))))^4)+((((α/(1-α))))^3)−α+((2α)/(1-α)))))+(1−α)(α(α(((((α/(1-α))))^2)+((((α/(1-α))))^1)+(1−α)((α/(1-2α))+2)+1)+(1−α)(((((α/(1-α))))^4)+((((α/(1-α))))^3)−α+((2α)/(1-α))))−α+(1−α)(((((α/(1-α))))^5)+((((α/(1-α))))^4)+((((α/(1-α))))^2)−α)))−α+(1−α)(((((α/(1-α))))^5)+((((α/(1-α))))^4)−α)))))−α+(1−α)(α(α(α(4−α)+(1−α)(2−2α))+(1−α)(α(2−α)−α+(1−α)(α(α(3−α)+(1−α)(α(α(((((α/(1-α))))^2)+(1−α)((α/(1-2α))+2)+2)+(1−α)(((((α/(1-α))))^4)+((((α/(1-α))))^2)−α+((2α)/(1-α))))−α+(1−α)(((((α/(1-α))))^5)+((((α/(1-α))))^3)+((((α/(1-α))))^2)−α)))−α+(1−α)(((((α/(1-α))))^5)+((((α/(1-α))))^3)−α))))−α+(1−α)(−α(1−α)+α(((((α/(1-α))))^3)−α+1)−α)))]

N[Solve[{0 ==(1-α)(-λ) +(α^2)((2+(α/(1-2α)))(1-λ))+α(1-α)(p-λ), α==λ, 0<α<1/2}]]

D Omitted Proofs from Section 4

pu[x_,α_]:=(((((1-α)/α))-1)/((((((1-α)/α)))^(x-1))-1))

pl[x_,α_]:=(((((((1-α)/α)))^(x-1))-(((1-α)/α)))/((((((1-α)/α)))^(x-1))-1))

bu[x_,α_]:=((((2α-1))^(-1))/(1-(((1-α)/α))))(((x-1)-1)((((1-α)/α))+1)+2(x-1)((((((1-α)/α))-(((((1-α)/α)))^(x-1)))/((((((1-α)/α)))^(x-1))-1))))

bl[x_,α_]:=If[x>=3,((((2α-1))^(-1))/((((1-α)/α))-(((((1-α)/α)))^(x-1))))(((((1-α)/α))+(((((1-α)/α)))^(x-1)))+2(x-1)((((((((1-α)/α)))^x)-(((((1-α)/α)))^(x-1)))/(1-(((((1-α)/α)))^(x-1)))))),0]

𝓋ah[i_,α_,λ_]:=(1/(1-(∑_(x=2)^i)(α(((1-α))^x))))(α(2(1-λ)) -(((1-α))^i)((i+1)λ) +(∑_(x=2)^i)((α^2)(((1-α))^(x-1))(pu[x,α](3+(bu[x,α]+(x-1)-1)/2)(1-λ)+pl[x,α]((2+(bl[x,α]-1)/2)(1-λ)-x λ))) +(∑_(x=2)^i)(α(((1-α))^x)(-x λ)))

𝓋[i_,α_,λ_]:= -(1-α)λ +(α^2)(2+(α/(1-2α)))(1-λ) +(α^2)(1-α)(2(1-λ)) -α(((1-α))^(i+1))((i+1)λ) +(∑_(x=2)^i)((α^3)(((1-α))^x)(pu[x,α](3+(bu[x,α]+(x-1)-1)/2)(1-λ)+pl[x,α]((2+(bl[x,α]-1)/2)(1-λ)-x λ))) +(∑_(x=2)^i)((α^2)(((1-α))^(x+1))(-x λ+𝓋ah[i,α,λ]))

Simplify[Solve[𝓋[1,α,λ] ==0, λ]][[1]][[1]]

N[Simplify[Solve[𝓋[1,α,α] ==0 && 0<α<1/2, α]]][[1]][[1]]

Simplify[Solve[𝓋[2,α,λ] ==0, λ]][[1]][[1]]

N[Simplify[Solve[𝓋[2,α,α] ==0 && 0<α<1/2, α]]][[1]][[1]]

Simplify[Solve[𝓋[3,α,λ] ==0, λ]][[1]][[1]]

N[Simplify[Solve[𝓋[3,α,α] ==0 && 0<α<1/2, α]]][[1]][[1]]

Simplify[Solve[𝓋[4,α,λ] ==0, λ]][[1]][[1]]

N[Simplify[Solve[𝓋[4,α,α] ==0 && 0<α<1/2, α]]][[1]][[1]]

Simplify[Solve[𝓋[5,α,λ] ==0, λ]][[1]][[1]]

N[Simplify[Solve[𝓋[5,α,α] ==0 && 0<α<1/2, α]]][[1]][[1]]

Simplify[Solve[𝓋[6,α,λ] ==0, λ]][[1]][[1]]

N[Simplify[Solve[𝓋[6,α,α] ==0 && 0<α<1/2, α]]][[1]][[1]]

E Omitted Proofs from Section 5

E.1 Omitted Proofs from Section 5.1

Reduce[x((α/(1-2α)))(1-λ)-x λ>=0&&0<α<(1/2)&&x>=1,λ]

The inequality on λ can be rewritten as λ ≤ (α/(1-α))which is already a well-known upper-bound to λ, so this result means that this is true for all α.

H Omitted Proofs from Section 8

H.1 Omitted Proofs from Section 8.1

Reduce[(j-1+(x-1)((α/(1-2α))))(1-λ)-x λ>j(1-λ)&&0<α<1/2&&x>=1&&α≤λ≤(α/(1-α)),x]

Note that the following is always satisfied:

(λ/(1+λ))<α<=λ

So, this inequality reduces to the following:

x>=((1-α-λ+αλ)/(α-λ+αλ))

N[Solve[1-α==α((2+(α/(1-2α)))(1-α))+(1-α)(V-α)]]

N[Reduce[((1-3α+(α^2))/(1-2α))<=Sum[(α^i),{i,1,5}]]]

H.2 Omitted Proofs from Section 8.2

Reduce[(-(Subscript[k, A])+(x-(Subscript[k, A]))((α/(1-2α))))(1-λ)-x λ>0&&0<α<1/2&&x>=0&&(Subscript[k, A])>=0&&α≤λ≤(α/(1-α)),x]

For the same reasons, this reduces to:

x>=(((Subscript[k, A])-α (Subscript[k, A])-λ (Subscript[k, A])+α λ (Subscript[k, A]))/(α-λ+α λ))

I Omitted Proofs from Section 9

I.3 Omitted Proofs from Section 9.3

Reduce[α((2+(α/(1-2α)))(1-λ)+k+((((α/(1-α))))^(x-2)))+(1-α)((((((α/(1-α))))^x)+(k+1)((α/(1-α))))-λ)<k+1-λ&&0<α<1/3&&α==λ&&x==2,k]/.λ->α

Plot[((1-7 α+13 (α^2)-7 (α^3)+(α^4))/(-1+5 α-8 (α^2)+4 (α^3))),{α,0.308,1/3}]

N[((1-7 α+13 (α^2)-7 (α^3)+(α^4))/(-1+5 α-8 (α^2)+4 (α^3)))/.α->1/3]

Reduce[α((2+(α/(1-2α)))(1-λ)+k+((((α/(1-α))))^(x-2)))+(1-α)((((((α/(1-α))))^x)+(k+1)((α/(1-α))))-λ)<k+1-λ&&0<α<1/3&&α==λ&&x==3,k]/.λ->α

Plot[((-1+7 α-16 (α^2)+16 (α^3)-8 (α^4)+(α^5))/(1-6 α+13 (α^2)-12 (α^3)+4 (α^4))),{α,0.308,1/3}]

N[((-1+7 α-16 (α^2)+16 (α^3)-8 (α^4)+(α^5))/(1-6 α+13 (α^2)-12 (α^3)+4 (α^4)))/.α->1/3]

Reduce[α((2+(α/(1-2α)))(1-λ)+k+((((α/(1-α))))^(x-2)))+(1-α)((((((α/(1-α))))^x)+(k+1)((α/(1-α))))-λ)<k+1-λ&&0<α<1/3&&α==λ&&x==4,k]/.λ->α

Plot[((1-8 α+24 (α^2)-36 (α^3)+28 (α^4)-9 (α^5)+(α^6))/(-1+7 α-19 (α^2)+25 (α^3)-16 (α^4)+4 (α^5))),{α,0.308,1/3}]

N[((1-8 α+24 (α^2)-36 (α^3)+28 (α^4)-9 (α^5)+(α^6))/(-1+7 α-19 (α^2)+25 (α^3)-16 (α^4)+4 (α^5)))/.α->1/3]

p=Simplify[α+(α^2)(1-α)+α(((1-α))^2)((((α/(1-α))))^2)+(α^3)(((1-α))^2)+α(((1-α))^3)((((α/(1-α))))^3)+(α^3)(((1-α))^3)((α/(1-α)))+α(((1-α))^4)((((α/(1-α))))^4)+(((1-α))^4)((((α/(1-α))))^5)]

N[Solve[{0 ==(1-α)(-λ) +(α^2)((2+(α/(1-2α)))(1-λ))+α(1-α)(p-λ), α==λ, 0<α<1/2}]]

p=Simplify[α+(α^2)(1-α)+α(((1-α))^2)((((α/(1-α))))^2)+(α^3)(((1-α))^2)+α(((1-α))^3)((((α/(1-α))))^3)+(α^3)(((1-α))^3)((α/(1-α)))+α(((1-α))^4)((((α/(1-α))))^4)]

N[Solve[{0 ==(1-α)(-λ) +(α^2)((2+(α/(1-2α)))(1-λ))+α(1-α)(p-λ), α==λ, 0<α<1/2}]]

p=Simplify[α+(α^2)(1-α)+α(((1-α))^2)((((α/(1-α))))^2)+(α^3)(((1-α))^2)+α(((1-α))^3)((((α/(1-α))))^3)+(α^2)(((1-α))^3)(((α^2)/(1-α+(α^2))))+α(((1-α))^4)((((α/(1-α))))^4)]

N[Solve[{0 ==(1-α)(-λ) +(α^2)((2+(α/(1-2α)))(1-λ))+α(1-α)(p-λ), α==λ, 0<α<1/2}]]

I.4 Omitted Proofs from Section 9.4

Reduce[α(1+(3+2((α/(1-2α))))(1-λ))+(1-α)(2-2λ)<3-λ&&0<α<1/2&&α==λ]/.λ->α

Simplify[(((((((1-α)/α)))^(x-2))-1)/((((((1-α)/α)))^(x-1))-1))/.x->3]

Simplify[((((2α-1))^(-1))/(1-(((((1-α)/α)))^(x-2))))(((((((1-α)/α)))^(x-2))+1)+2(x-1)((((((((1-α)/α)))^(x-2))-(((((1-α)/α)))^(x-1)))/((((((1-α)/α)))^(x-1))-1))))/.x->3]

Simplify[(((((((1-α)/α)))^(x-1))-(((((1-α)/α)))^(x-2)))/((((((1-α)/α)))^(x-1))-1))/.x->3]

Simplify[((((2α-1))^(-1))/((((((1-α)/α)))^(x-2))-(((((1-α)/α)))^(x-1))))((x-2)((((((1-α)/α)))^(x-2))+(((((1-α)/α)))^(x-1)))+2(x-1)((((((((1-α)/α)))^(2x-3))-(((((1-α)/α)))^(x-1)))/(1-(((((1-α)/α)))^(x-1))))))/.x->3]

Reduce[α (V + (1 + (α/(1-2α)))(1-λ))+(1-α)α(V+1-λ)+(((1-α))^2)(-2λ+k-λ)<V&&0<α<(1/3)&&λ==α&&k>=3&&V>=k+1-λ,V]

Simplify[(((((((1-α)/α)))^(x-2))-1)/((((((1-α)/α)))^(x-1))-1))/.x->4]

Simplify[((((2α-1))^(-1))/(1-(((((1-α)/α)))^(x-2))))(((((((1-α)/α)))^(x-2))+1)+2(x-1)((((((((1-α)/α)))^(x-2))-(((((1-α)/α)))^(x-1)))/((((((1-α)/α)))^(x-1))-1))))/.x->4]

Simplify[(((((((1-α)/α)))^(x-1))-(((((1-α)/α)))^(x-2)))/((((((1-α)/α)))^(x-1))-1))/.x->4]

Simplify[((((2α-1))^(-1))/((((((1-α)/α)))^(x-2))-(((((1-α)/α)))^(x-1))))((x-2)((((((1-α)/α)))^(x-2))+(((((1-α)/α)))^(x-1)))+2(x-1)((((((((1-α)/α)))^(2x-3))-(((((1-α)/α)))^(x-1)))/(1-(((((1-α)/α)))^(x-1))))))/.x->4]

Reduce[α (V + (1 + (α/(1-2α)))(1-λ))+(1-α)((α/(1-α+(α^2))))(V+(((((1+α-(α^2))/(1-α+(α^2)))+1)/2))(1-λ))+(1-α)(((((-1+α))^2)/(1-α+(α^2))))(-(1+(((2/(1-α+(α^2)))+2)/2))λ+((((2/(1-α+(α^2)))-2)/2))+k-λ)<V&&0<α<(1/3)&&λ==α&&k>=4&&V>=k+1-λ,V]

J Omitted Proofs from Section 10

p=Simplify[α+(α^2)(1-α)+α(((1-α))^3)((((α/(1-α))))^3)+(α^3)(((1-α))^2)+α(((1-α))^4)((((α/(1-α))))^4)+(α^3)(((1-α))^3)((α/(1-α)))+α(((1-α))^5)((((α/(1-α))))^5)]

N[Solve[{0 ==(1-α)(-λ) +(α^2)((2+(α/(1-2α)))(1-λ))+α(1-α)(p-λ), α==λ, 0<α<1/2}]]

p=Simplify[α+(α^2)(1-α)+α(((1-α))^3)((((α/(1-α))))^3)+(α^3)(((1-α))^2)+α(((1-α))^4)((((α/(1-α))))^4)+(α^2)(((1-α))^3)(((α^2)/(1-α+(α^2))))+α(((1-α))^5)((((α/(1-α))))^5)]

N[Solve[{0 ==(1-α)(-λ) +(α^2)((2+(α/(1-2α)))(1-λ))+α(1-α)(p-λ), α==λ, 0<α<1/2}]]

K Omitted Proofs from Section 11

N[Reduce[((((((((1-α)/α)))^(x-1))-1)/((((((1-α)/α)))^x)-1)))(2+x+(1/2)(((((2α-1))^(-1))/(1-(((((1-α)/α)))^(x-1))))(((((((1-α)/α)))^(x-1))+1)+2x((((((((1-α)/α)))^(x-1))-(((((1-α)/α)))^x))/((((((1-α)/α)))^x)-1))))+1)(1-α))+((((((((1-α)/α)))^x)-(((((1-α)/α)))^(x-1)))/((((((1-α)/α)))^x)-1)))(x+(1/2)(((((2α-1))^(-1))/((((((1-α)/α)))^(x-1))-(((((1-α)/α)))^x)))((x-1)((((((1-α)/α)))^(x-1))+(((((1-α)/α)))^x))+2x((((((((1-α)/α)))^(2x-1))-(((((1-α)/α)))^x))/(1-(((((1-α)/α)))^x)))))-(x-1)))(1-α)>=x+1-α&&0<α<1/3&&x==2]]

N[Reduce[((((((((1-α)/α)))^(x-1))-1)/((((((1-α)/α)))^x)-1)))(2+x+(1/2)(((((2α-1))^(-1))/(1-(((((1-α)/α)))^(x-1))))(((((((1-α)/α)))^(x-1))+1)+2x((((((((1-α)/α)))^(x-1))-(((((1-α)/α)))^x))/((((((1-α)/α)))^x)-1))))+1)(1-α))+((((((((1-α)/α)))^x)-(((((1-α)/α)))^(x-1)))/((((((1-α)/α)))^x)-1)))(x+(1/2)(((((2α-1))^(-1))/((((((1-α)/α)))^(x-1))-(((((1-α)/α)))^x)))((x-1)((((((1-α)/α)))^(x-1))+(((((1-α)/α)))^x))+2x((((((((1-α)/α)))^(2x-1))-(((((1-α)/α)))^x))/(1-(((((1-α)/α)))^x)))))-(x-1)))(1-α)>=x+1-α&&0<α<1/3&&x==3]]