How to Simulate a Fraud-Proof Blockchain

Ignacio Hagopian
Feb 19 · 18 min read

Random-sampling scheme


Simulation as a verification

Fraud-proof network simulation

$ git clone https://github.com/jsign/fraudproofsim.git
$ cd fraudproofsim && go get ./...
$ go run main.go
It permits to compare, solve and verify fraud-proof networks.
Usage:
fraudproofsim [command]
Available Commands:
compare Compares the Standard and Enhanced models
help Help about any command
solve Solves c for k, s and p
verifypaper Verifies setups calculated in the paper
Flags:
--enhanced run an Enhanced Model
-h, --help help for fraudproofsim
--n int number of iterations to run per instance (default 500)
Use "fraudproofsim [command] --help" for more information about a command.

verifypaper command

$ go run main.go help solve
It solves c for k, s and p (p, within a threshold)
Usage:
fraudproofsim solve [k] [s] [p] [threshold?] [flags]
Flags:
-h, --help help for solve
Global Flags:
--enhanced run an Enhanced Model
--n int number of iterations to run per instance (default 500)
$ go run main.go verifypaper
k=16, s=50, c=28 => p=1 37ms
k=16, s=20, c=69 => p=0.994 28ms
k=16, s=10, c=138 => p=0.988 37ms
k=16, s=5, c=275 => p=0.986 37ms
k=16, s=2, c=690 => p=0.99 63ms
k=32, s=50, c=112 => p=0.996 137ms
k=32, s=20, c=280 => p=0.994 131ms
k=32, s=10, c=561 => p=0.988 136ms
k=32, s=5, c=1122 => p=0.992 143ms
k=32, s=2, c=2805 => p=0.994 175ms
k=64, s=50, c=451 => p=0.996 464ms
k=64, s=20, c=1129 => p=0.996 536ms
k=64, s=10, c=2258 => p=0.992 510ms
k=64, s=5, c=4516 => p=0.988 527ms
k=64, s=2, c=11289 => p=0.996 679ms
k=128, s=50, c=1811 => p=0.992 2193ms
k=128, s=20, c=4500 => p=0.702 2068ms
exit status 2

solve command

$ go run main.go help solve
It solves c for k, s and p (p, within a threshold)
Usage:
fraudproofsim solve [k] [s] [p] [threshold?] [flags]
Flags:
-h, --help help for solve
Global Flags:
--enhanced run an Enhanced Model
--n int number of iterations to run per instance (default 500)
$ go run main.go solve 64 10 .99 0.005
Solving for (k:64, s:10, p:0.99, threshold:0.005)
[1, 16384]: c=8192 p=1
[1, 8192]: c=4096 p=1
[1, 4096]: c=2048 p=0
[2048, 4096]: c=3072 p=1
[2048, 3072]: c=2560 p=1
[2048, 2560]: c=2304 p=1
[2048, 2304]: c=2176 p=0.002
[2176, 2304]: c=2240 p=0.902
[2240, 2304]: c=2272 p=1
[2240, 2272]: c=2256 p=0.994
Solution c=2256 with p=0.994 (4900ms)
$ go run main.go solve 64 10 .99 0.0001 --n 2000
Solving for (k:64, s:10, p:0.99, threshold:0.0001)
[1, 16384]: c=8192 p=1
[1, 8192]: c=4096 p=1
[1, 4096]: c=2048 p=0
[2048, 4096]: c=3072 p=1
[2048, 3072]: c=2560 p=1
[2048, 2560]: c=2304 p=1
[2048, 2304]: c=2176 p=0.0025
[2176, 2304]: c=2240 p=0.8955
[2240, 2304]: c=2272 p=0.9995
[2240, 2272]: c=2256 p=0.9885
[2256, 2272]: c=2264 p=0.9955
[2256, 2264]: c=2260 p=0.9945
[2256, 2260]: c=2258 p=0.992
[2256, 2258]: c=2257 p=0.994
[2256, 2257]: c=2256 p=0.9865
[2256, 2257]: c=2256 p=0.9915
Solution c=2256 with p=0.9915 (31346ms)
$ go run main.go solve 128 2 0.99 0.005
Solving for (k:128, s:2, p:0.99, threshold:0.005)
[1, 65536]: c=32768 p=0
[32768, 65536]: c=49152 p=1
[32768, 49152]: c=40960 p=0
[40960, 49152]: c=45056 p=0.796
[45056, 49152]: c=47104 p=1
[45056, 47104]: c=46080 p=1
[45056, 46080]: c=45568 p=1
[45056, 45568]: c=45312 p=1
[45056, 45312]: c=45184 p=0.956
[45184, 45312]: c=45248 p=0.976
[45248, 45312]: c=45280 p=0.998
[45248, 45280]: c=45264 p=0.986
Solution c=45264 with p=0.986 (34220ms)
$ go run main.go solve 256 2 0.99 0.005
Solving for (k:256, s:2, p:0.99, threshold:0.005)
[1, 262144]: c=131072 p=0
[131072, 262144]: c=196608 p=1
[131072, 196608]: c=163840 p=0
[163840, 196608]: c=180224 p=0.076
[180224, 196608]: c=188416 p=1
[180224, 188416]: c=184320 p=1
[180224, 184320]: c=182272 p=1
[180224, 182272]: c=181248 p=0.964
[181248, 182272]: c=181760 p=1
[181248, 181760]: c=181504 p=0.994
Solution c=181504 with p=0.994 (142453ms)

compare command

$ go run main.go help compare
Compares Standard and Enhanced model to understand their impact on soundness
Usage:
fraudproofsim compare [k] [s] [#points] [flags]
Flags:
-h, --help help for compare
Global Flags:
--enhanced run an Enhanced Model
--n int number of iterations to run per instance (default 500)
$ go run main.go compare 64 10 25
Solving c for (k: 64, s: 10) with precision .99+-.005:
[1, 16384]: c=8192 p=1
[1, 8192]: c=4096 p=1
[1, 4096]: c=2048 p=0
[2048, 4096]: c=3072 p=1
[2048, 3072]: c=2560 p=1
[2048, 2560]: c=2304 p=1
[2048, 2304]: c=2176 p=0
[2176, 2304]: c=2240 p=0.896
[2240, 2304]: c=2272 p=0.998
[2240, 2272]: c=2256 p=0.99
Found solution c=2256, now generating 25 points in [.50*c,1.5*c]=[1128, 3384]:
0%
3%
7%
11%
15%
19%
23%
27%
31%
35%
39%
43%
47%
51%
55%
59%
63%
67%
71%
75%
79%
83%
87%
91%
95%
99%
Plotted in plot.png
The result of the compare command for k=64 and s=10
$ go run main.go compare 64 50 50
Solving c for (k: 64, s: 50) with precision .99+-.005:
[1, 16384]: c=8192 p=1
[1, 8192]: c=4096 p=1
[1, 4096]: c=2048 p=1
[1, 2048]: c=1024 p=1
[1, 1024]: c=512 p=1
[1, 512]: c=256 p=0
[256, 512]: c=384 p=0
[384, 512]: c=448 p=0.93
[448, 512]: c=480 p=1
[448, 480]: c=464 p=1
[448, 464]: c=456 p=1
[448, 456]: c=452 p=0.998
[448, 452]: c=450 p=0.978
[450, 452]: c=451 p=0.992
Found solution c=451, now generating 50 points in [.50*c,1.5*c]=[225, 676]:
0%
1%
3%
...
97%
99%
Plotted in plot.png
Result of the compare command for k=64 and s=50
$ go run main.go compare 64 2 50
Solving c for (k: 64, s: 2) with precision .99+-.005:
[1, 16384]: c=8192 p=0
[8192, 16384]: c=12288 p=1
[8192, 12288]: c=10240 p=0
[10240, 12288]: c=11264 p=0.97
[11264, 12288]: c=11776 p=1
[11264, 11776]: c=11520 p=1
[11264, 11520]: c=11392 p=1
[11264, 11392]: c=11328 p=0.998
[11264, 11328]: c=11296 p=0.994
Found solution c=11296, now generating 50 points in [.50*c,1.5*c]=[5648, 16944]:
0%
1%
3%
5%
...
97%
99%
Plotted in plot.png
Result for the compare command for k=64 and s=2

Running times and bottlenecks

Possible Improvements

Domain-size and binary-search for solve command

Full-node decision-making for share request rejection

Running time and memory usage

Simulation configuration scan

Explore other possible codings and their impact on results

Conclusion

HackerNoon.com

how hackers start their afternoons.