mining.go
1 package main 2 3 import ( 4 "fmt" 5 "math" 6 "math/big" 7 "encoding/hex" 8 "github.com/obscuren/sha3" 9 "testing" 10 "strconv" 11 ) 12 13 //For use in benchmarking 14 const tree_depth = 5 15 const tape_width = 32 //int(math.Pow(2,tree_depth)) < would be nice, but go won't recognize as const 16 const tape_depth = 100 17 18 //Number of operations that are drawn from to form the tape and the tree 19 const num_ops = 9 20 //This is the number of times the PoW algorithm is run 21 const sample_size = 100 22 23 func Bytes2Hex(d []byte) string { 24 return hex.EncodeToString(d) 25 } 26 27 func Hex2Bytes(str string) []byte { 28 h, _ := hex.DecodeString(str) 29 return h 30 } 31 32 func plus(z *big.Int, x *big.Int, y *big.Int) *big.Int { 33 var lim big.Int 34 lim.Exp(big.NewInt(2),big.NewInt(256), big.NewInt(0)) 35 z.Add(x,y) 36 return z.Mod(z,&lim) 37 38 } 39 40 func times(z *big.Int, x *big.Int, y *big.Int) *big.Int { 41 var lim, x1, y1 big.Int 42 lim.Exp(big.NewInt(2),big.NewInt(256), big.NewInt(0)) 43 x1.Set(x) 44 y1.Set(y) 45 z.Mul(x,y) 46 z.Mod(z,&lim) 47 return z 48 } 49 50 func mod(z *big.Int, x *big.Int, y *big.Int) *big.Int { 51 52 if (x.Cmp(big.NewInt(0)) == 0 || y.Cmp(big.NewInt(0)) == 0) { 53 return big.NewInt(0) 54 } 55 if x.Cmp(y) == -1 { //if x < y 56 z.Mod(y,x) 57 } else if x.Cmp(y) == 1 { //if x > y 58 z.Mod(x,y) 59 } 60 return z 61 } 62 63 func xor(z *big.Int, x *big.Int, y *big.Int) *big.Int {return z.Xor(x,y)} 64 65 func nxor(z *big.Int, x *big.Int, y *big.Int) *big.Int { 66 z.Xor(x,y) 67 return z.Not(z) 68 } 69 70 func and(z *big.Int, x *big.Int, y *big.Int) *big.Int {return z.And(x,y)} 71 72 func not(z *big.Int, x *big.Int, y *big.Int) *big.Int { 73 _ = y 74 return z.Not(x) 75 } 76 77 func or(z *big.Int, x *big.Int, y *big.Int) *big.Int {return z.Or(x,y)} 78 79 func rshift(z *big.Int, x *big.Int, y *big.Int) *big.Int { 80 var lim big.Int 81 lim.Exp(big.NewInt(2),big.NewInt(256), big.NewInt(0)) 82 z.Rsh(x,7) 83 return z.Mod(z,&lim) 84 } 85 86 87 func GetOp(i int) func(z *big.Int, x *big.Int, y *big.Int) *big.Int{ 88 switch i { 89 case 0: 90 return plus 91 case 1: 92 return xor 93 case 2: 94 return not 95 case 3: 96 return times 97 case 4: 98 return mod 99 case 5: 100 return rshift 101 case 6: 102 return or 103 case 7: 104 return and 105 case 8: 106 return nxor 107 } 108 return plus 109 } 110 111 //the tapelink is used to t 112 type Tapelink struct { 113 I int64 114 J int64 115 op func(z *big.Int, x *big.Int, y *big.Int) *big.Int 116 } 117 118 func Sha3Bin(data []byte) []byte { 119 d := sha3.NewKeccak256() 120 d.Write(data) 121 return d.Sum(nil) 122 } 123 124 func BenchmarkSha3Bin(b *testing.B){ 125 for i:= 0; i < b.N; i++ { 126 Sha3Bin([]byte(string(i))) 127 } 128 } 129 130 //generates a tape of operations that is w*d long 131 func gen_tape(seed int64, w int, d int) []Tapelink { 132 var X = big.NewInt(0) 133 var Y = big.NewInt(0) 134 Y.Exp(big.NewInt(2),big.NewInt(80), nil) 135 var M = big.NewInt(0) 136 var T []Tapelink 137 for i := 0; i < w*d; i++{ 138 // add empty link to tape 139 T = append(T, *new(Tapelink)) 140 141 // generate new entropy as needed 142 if (int64(X.Cmp(Y)) == -1) {X.SetBytes(Sha3Bin([]byte(strconv.FormatInt(seed + int64(i), 10))))} 143 144 // Pick random index I 145 T[i].I = M.Mod(X,big.NewInt(int64(w))).Int64() 146 M = big.NewInt(int64(w)) 147 X = X.Div(X,M) 148 149 // Pick random index J 150 mm := big.NewInt(M.Mod(X,big.NewInt(int64(w-1))).Int64() + int64(1) + T[i].I) 151 T[i].J = M.Mod(mm, big.NewInt(int64(w))).Int64() 152 M = big.NewInt(int64(w-1)) 153 X = X.Div(X,M) 154 155 // Pick random operation 156 T[i].op = GetOp(int(M.Mod(X, big.NewInt(int64(num_ops))).Int64())) 157 M = big.NewInt(int64(num_ops)) 158 X = X.Div(X,M) 159 } 160 return T 161 } 162 163 func BenchmarkGen_tape(b *testing.B){ 164 var X big.Int 165 var s int64 166 b.ResetTimer() 167 for i := 0; i < b.N; i++ { 168 b.StopTimer() 169 X.SetBytes(Sha3Bin([]byte(string(i)))) 170 s = X.Int64() 171 b.StartTimer() 172 gen_tape(s, tape_width, tape_depth) 173 } 174 175 } 176 177 func gen_inputs(seed int64, w int) []big.Int { 178 var A []big.Int 179 for i := 0; i < w; i++ { 180 A = append(A, *new(big.Int)) 181 if (i % 256 == 0) { 182 A[i].SetBytes(Sha3Bin([]byte(strconv.FormatInt(seed + int64(i), 10)))) 183 } else { 184 A[i].Lsh(&A[i-1], 1) 185 } 186 } 187 return A 188 } 189 190 func BenchmarkGen_inputs(b *testing.B){ 191 var X big.Int 192 var s int64 193 b.ResetTimer() 194 for i := 0; i < b.N; i++ { 195 b.StopTimer() 196 X.SetBytes(Sha3Bin([]byte(string(i)))) 197 s = X.Int64() 198 b.StartTimer() 199 gen_inputs(s, tape_width) 200 } 201 } 202 203 //this changes the inputs as it goes through a tape with d links 204 func run_tape(tape []Tapelink, inputs []big.Int, d int) { 205 var X *big.Int 206 X = big.NewInt(0) 207 for i := 0; i < d; i++ { 208 X = tape[i].op(X, &inputs[tape[i].I], &inputs[tape[i].J]) 209 inputs[tape[i].I].Set(X) 210 } 211 } 212 213 func BenchmarkRun_tape(b *testing.B){ 214 b.ResetTimer() 215 for i := 0; i < b.N; i++ { 216 b.StopTimer() 217 T := gen_tape(int64(i), tape_width, tape_depth) 218 I := gen_inputs(int64(i), tape_width) 219 b.StartTimer() 220 run_tape(T,I,tape_width*tape_depth) 221 } 222 } 223 224 225 //returns a 2^d - 1 length tape of operations (no I or J's in the Tapelinks) 226 func gen_tree(seed int64, d int) []Tapelink { 227 M := big.NewInt(0) // dummy variable 228 X := big.NewInt(0) // entropy variable 229 Y := big.NewInt(0) // entropy buffer size 230 Y.Exp(big.NewInt(2),big.NewInt(80), nil) 231 var T []Tapelink // the tree will be stored here 232 233 for i := 0; i < int(math.Pow(2, float64(d))) - 1; i++{ 234 235 T = append(T, *new(Tapelink)) 236 237 //giving it more entropy, if X < 2^32 238 if (X.Cmp(Y) == -1) {X.SetBytes(Sha3Bin([]byte(strconv.FormatInt(seed + int64(i),10))))} 239 240 //filling the tape with random ops 241 T[i].op = GetOp(int(M.Mod(X, big.NewInt(num_ops)).Int64())) 242 M = big.NewInt(num_ops) 243 X = X.Div(X,M) 244 } 245 return T 246 } 247 248 func BenchmarkGen_tree(b *testing.B) { 249 var X big.Int 250 var s int64 251 b.ResetTimer() 252 for i := 0; i < b.N; i++ { 253 b.StopTimer() 254 X.SetBytes(Sha3Bin([]byte(string(i)))) 255 s = X.Int64() 256 b.StartTimer() 257 gen_tree(s, tree_depth) 258 } 259 } 260 261 //there should be 2^d inputs and 2^d - 1 links in the tape. not complying is an unhandled exception 262 func run_tree(inputs []big.Int, tree []Tapelink, d int) *big.Int { 263 X := big.NewInt(0) 264 counter := 0 265 for j := 0; j < d; j++ { 266 for i := 0; i < int(math.Pow(2,float64(d - j - 1))); i++ { 267 X = tree[counter].op(X, &inputs[2*i], &inputs[2*i + 1]) 268 inputs[i].Set(X) 269 counter += 1 270 } 271 } 272 273 return &inputs[0] 274 } 275 276 func BenchmarkRun_tree(b *testing.B) { 277 var X big.Int 278 b.ResetTimer() 279 for i := 0; i < b.N; i++ { 280 b.StopTimer() 281 var inputs []big.Int 282 for j := 0; j < tape_width; j++ { 283 X.SetBytes(Sha3Bin([]byte(string(j + i*tape_width)))) 284 inputs = append(inputs, X) 285 } 286 tree := gen_tree(X.Int64(), tree_depth) 287 b.StartTimer() 288 run_tree(inputs, tree, tree_depth) 289 } 290 } 291 292 func sha_cap(s []string, n int) []byte{ 293 var feed string 294 feed = "" 295 for i := 0; i < n; i++ { 296 feed += s[i] 297 } 298 return Sha3Bin([]byte(feed)) 299 } 300 301 302 func BenchmarkSha_cap(b *testing.B){ 303 var X big.Int 304 var s []string 305 b.ResetTimer() 306 for i := 0; i < b.N; i++ { 307 b.StopTimer() 308 X.SetBytes(Sha3Bin([]byte(string(i)))) 309 s = append(s, X.String()) 310 b.StartTimer() 311 sha_cap(s,1) 312 } 313 } 314 315 func main(){ 316 var seed int64 317 var sample []big.Int 318 319 320 seed = int64(13300331) 321 322 for i := 0; i < sample_size; i++ { 323 324 Tape := gen_tape(seed, tape_width, tape_depth) 325 Tree := gen_tree(seed, tree_depth) 326 327 seed += int64(i*i) 328 if i%10 == 0 { 329 fmt.Printf("i: %d\n",i) 330 } 331 I := gen_inputs(seed, tape_width) 332 run_tape(Tape, I, tape_depth*tape_width) 333 334 335 output := *run_tree(I, Tree, tree_depth) 336 if output.Cmp(big.NewInt(0)) == 0 { 337 fmt.Printf("We have a zero from the tree, form operation: \n") 338 fmt.Println(Tree[len(Tree)-1]) 339 340 } 341 342 343 var blockhashes []string 344 blockhashes = append(blockhashes, output.String()) 345 346 sample = append(sample, output) 347 H := sha_cap(blockhashes, 1) 348 349 output.SetBytes(H) 350 //sample = append(sample, output) 351 } 352 353 var collisions int = 0 354 for i := 0; i < sample_size; i++ { 355 //fmt.Println(sample[i]) 356 for j:=0; j < i; j++ { 357 //if sample[i] == sample[j] { 358 if sample[i].Cmp(&sample[j]) == 0 { 359 collisions += 1 360 //fmt.Printf("collision on i, j: %d, %d", i, j) 361 //fmt.Println(sample[i]) 362 } 363 } 364 } 365 fmt.Printf("number of outputs with same value: %d out of %d\n", (1+int(math.Pow(float64(1+8*collisions),0.5)))/2, sample_size) 366 }