Merge pull request #3 from ethereum/develop

Update to develop

12 files changed, 308 insertions, 301 deletions

diff --git a/pow/ar/block.go b/pow/ar/block.go
deleted file mode 100644
index 2124b53b4..000000000
--- a/pow/ar/block.go
+++ /dev/null
@@ -1,12 +0,0 @@
-package ar
-
-import (
-	"math/big"
-
-	"github.com/ethereum/go-ethereum/trie"
-)
-
-type Block interface {
-	Trie() *trie.Trie
-	Diff() *big.Int
-}
diff --git a/pow/ar/ops.go b/pow/ar/ops.go
deleted file mode 100644
index 3a099be08..000000000
--- a/pow/ar/ops.go
+++ /dev/null
@@ -1,54 +0,0 @@
-package ar
-
-import "math/big"
-
-const lenops int64 = 9
-
-type OpsFunc func(a, b *big.Int) *big.Int
-
-var ops [lenops]OpsFunc
-
-func init() {
-	ops[0] = Add
-	ops[1] = Mul
-	ops[2] = Mod
-	ops[3] = Xor
-	ops[4] = And
-	ops[5] = Or
-	ops[6] = Sub1
-	ops[7] = XorSub
-	ops[8] = Rsh
-}
-
-func Add(x, y *big.Int) *big.Int {
-	return new(big.Int).Add(x, y)
-}
-func Mul(x, y *big.Int) *big.Int {
-	return new(big.Int).Mul(x, y)
-}
-func Mod(x, y *big.Int) *big.Int {
-	return new(big.Int).Mod(x, y)
-}
-func Xor(x, y *big.Int) *big.Int {
-	return new(big.Int).Xor(x, y)
-}
-func And(x, y *big.Int) *big.Int {
-	return new(big.Int).And(x, y)
-}
-func Or(x, y *big.Int) *big.Int {
-	return new(big.Int).Or(x, y)
-}
-func Sub1(x, y *big.Int) *big.Int {
-	a := big.NewInt(-1)
-	a.Sub(a, x)
-
-	return a
-}
-func XorSub(x, y *big.Int) *big.Int {
-	t := Sub1(x, nil)
-
-	return t.Xor(t, y)
-}
-func Rsh(x, y *big.Int) *big.Int {
-	return new(big.Int).Rsh(x, uint(y.Uint64()%64))
-}
diff --git a/pow/ar/pow.go b/pow/ar/pow.go
deleted file mode 100644
index 8991a674b..000000000
--- a/pow/ar/pow.go
+++ /dev/null
@@ -1,122 +0,0 @@
-package ar
-
-import (
-	"math/big"
-
-	"github.com/ethereum/go-ethereum/ethutil"
-)
-
-type Entry struct {
-	op   OpsFunc
-	i, j *big.Int
-}
-
-type Tape struct {
-	tape  []Entry
-	block Block
-}
-
-func NewTape(block Block) *Tape {
-	return &Tape{nil, block}
-}
-
-func (self *Tape) gen(w, h int64, gen NumberGenerator) {
-	self.tape = nil
-
-	for v := int64(0); v < h; v++ {
-		op := ops[gen.rand64(lenops).Int64()]
-		r := gen.rand64(100).Uint64()
-
-		var j *big.Int
-		if r < 20 && v > 20 {
-			j = self.tape[len(self.tape)-1].i
-		} else {
-			j = gen.rand64(w)
-		}
-
-		i := gen.rand64(w)
-		self.tape = append(self.tape, Entry{op, i, j})
-	}
-}
-
-func (self *Tape) runTape(w, h int64, gen NumberGenerator) *big.Int {
-	var mem []*big.Int
-	for i := int64(0); i < w; i++ {
-		mem = append(mem, gen.rand(ethutil.BigPow(2, 64)))
-	}
-
-	set := func(i, j int) Entry {
-		entry := self.tape[i*100+j]
-		mem[entry.i.Uint64()] = entry.op(entry.i, entry.j)
-
-		return entry
-	}
-
-	dir := true
-	for i := 0; i < int(h)/100; i++ {
-		var entry Entry
-		if dir {
-			for j := 0; j < 100; j++ {
-				entry = set(i, j)
-			}
-		} else {
-			for j := 99; i >= 0; j-- {
-				entry = set(i, j)
-			}
-		}
-
-		t := mem[entry.i.Uint64()]
-		if big.NewInt(2).Cmp(new(big.Int).Mod(t, big.NewInt(37))) < 0 {
-			dir = !dir
-		}
-	}
-
-	return Sha3(mem)
-}
-
-func (self *Tape) Verify(header, nonce []byte) bool {
-	n := ethutil.BigD(nonce)
-
-	var w int64 = 10000
-	var h int64 = 150000
-	gen := Rnd(Sha3([]interface{}{header, new(big.Int).Div(n, big.NewInt(1000))}))
-	self.gen(w, h, gen)
-
-	gen = Rnd(Sha3([]interface{}{header, new(big.Int).Mod(n, big.NewInt(1000))}))
-	hash := self.runTape(w, h, gen)
-
-	it := self.block.Trie().Iterator()
-	next := it.Next(string(new(big.Int).Mod(hash, ethutil.BigPow(2, 160)).Bytes()))
-
-	req := ethutil.BigPow(2, 256)
-	req.Div(req, self.block.Diff())
-	return Sha3([]interface{}{hash, next}).Cmp(req) < 0
-}
-
-func (self *Tape) Run(header []byte) []byte {
-	nonce := big.NewInt(0)
-	var w int64 = 10000
-	var h int64 = 150000
-
-	req := ethutil.BigPow(2, 256)
-	req.Div(req, self.block.Diff())
-
-	for {
-		if new(big.Int).Mod(nonce, b(1000)).Cmp(b(0)) == 0 {
-			gen := Rnd(Sha3([]interface{}{header, new(big.Int).Div(nonce, big.NewInt(1000))}))
-			self.gen(w, h, gen)
-		}
-
-		gen := Rnd(Sha3([]interface{}{header, new(big.Int).Mod(nonce, big.NewInt(1000))}))
-		hash := self.runTape(w, h, gen)
-
-		it := self.block.Trie().Iterator()
-		next := it.Next(string(new(big.Int).Mod(hash, ethutil.BigPow(2, 160)).Bytes()))
-
-		if Sha3([]interface{}{hash, next}).Cmp(req) < 0 {
-			return nonce.Bytes()
-		} else {
-			nonce.Add(nonce, ethutil.Big1)
-		}
-	}
-}
diff --git a/pow/ar/pow_test.go b/pow/ar/pow_test.go
deleted file mode 100644
index b1ebf9281..000000000
--- a/pow/ar/pow_test.go
+++ /dev/null
@@ -1,47 +0,0 @@
-package ar
-
-import (
-	"fmt"
-	"math/big"
-	"testing"
-
-	"github.com/ethereum/go-ethereum/ethdb"
-	"github.com/ethereum/go-ethereum/trie"
-)
-
-type TestBlock struct {
-	trie *trie.Trie
-}
-
-func NewTestBlock() *TestBlock {
-	db, _ := ethdb.NewMemDatabase()
-	return &TestBlock{
-		trie: trie.New(db, ""),
-	}
-}
-
-func (self *TestBlock) Diff() *big.Int {
-	return b(10)
-}
-
-func (self *TestBlock) Trie() *trie.Trie {
-	return self.trie
-}
-
-func (self *TestBlock) Hash() []byte {
-	a := make([]byte, 32)
-	a[0] = 10
-	a[1] = 2
-	return a
-}
-
-func TestPow(t *testing.T) {
-	entry := make([]byte, 32)
-	entry[0] = 255
-
-	block := NewTestBlock()
-
-	pow := NewTape(block)
-	nonce := pow.Run(block.Hash())
-	fmt.Println("Found nonce", nonce)
-}
diff --git a/pow/ar/rnd.go b/pow/ar/rnd.go
deleted file mode 100644
index c62f4e062..000000000
--- a/pow/ar/rnd.go
+++ /dev/null
@@ -1,66 +0,0 @@
-package ar
-
-import (
-	"math/big"
-
-	"github.com/ethereum/go-ethereum/crypto"
-	"github.com/ethereum/go-ethereum/ethutil"
-)
-
-var b = big.NewInt
-
-type Node interface {
-	Big() *big.Int
-}
-
-type ByteNode []byte
-
-func (self ByteNode) Big() *big.Int {
-	return ethutil.BigD(ethutil.Encode([]byte(self)))
-}
-
-func Sha3(v interface{}) *big.Int {
-	if b, ok := v.(*big.Int); ok {
-		return ethutil.BigD(crypto.Sha3(b.Bytes()))
-	} else if b, ok := v.([]interface{}); ok {
-		return ethutil.BigD(crypto.Sha3(ethutil.Encode(b)))
-	} else if s, ok := v.([]*big.Int); ok {
-		v := make([]interface{}, len(s))
-		for i, b := range s {
-			v[i] = b
-		}
-
-		return ethutil.BigD(crypto.Sha3(ethutil.Encode(v)))
-	}
-
-	return nil
-}
-
-type NumberGenerator interface {
-	rand(r *big.Int) *big.Int
-	rand64(r int64) *big.Int
-}
-
-type rnd struct {
-	seed *big.Int
-}
-
-func Rnd(s *big.Int) rnd {
-	return rnd{s}
-}
-
-func (self rnd) rand(r *big.Int) *big.Int {
-	o := b(0).Mod(self.seed, r)
-
-	self.seed.Div(self.seed, r)
-
-	if self.seed.Cmp(ethutil.BigPow(2, 64)) < 0 {
-		self.seed = Sha3(self.seed)
-	}
-
-	return o
-}
-
-func (self rnd) rand64(r int64) *big.Int {
-	return self.rand(b(r))
-}
diff --git a/pow/block.go b/pow/block.go
new file mode 100644
index 000000000..62df2b5ff
--- /dev/null
+++ b/pow/block.go
@@ -0,0 +1,9 @@
+package pow
+
+import "math/big"
+
+type Block interface {
+	Difficulty() *big.Int
+	HashNoNonce() []byte
+	N() []byte
+}
diff --git a/pow/dagger/dagger.go b/pow/dagger/dagger.go
new file mode 100644
index 000000000..310f8abdd
--- /dev/null
+++ b/pow/dagger/dagger.go
@@ -0,0 +1,160 @@
+package dagger
+
+import (
+	"hash"
+	"math/big"
+	"math/rand"
+	"time"
+
+	"github.com/ethereum/go-ethereum/crypto/sha3"
+	"github.com/ethereum/go-ethereum/ethutil"
+	"github.com/ethereum/go-ethereum/logger"
+)
+
+var powlogger = logger.NewLogger("POW")
+
+type Dagger struct {
+	hash *big.Int
+	xn   *big.Int
+}
+
+var Found bool
+
+func (dag *Dagger) Find(obj *big.Int, resChan chan int64) {
+	r := rand.New(rand.NewSource(time.Now().UnixNano()))
+
+	for i := 0; i < 1000; i++ {
+		rnd := r.Int63()
+
+		res := dag.Eval(big.NewInt(rnd))
+		powlogger.Infof("rnd %v\nres %v\nobj %v\n", rnd, res, obj)
+		if res.Cmp(obj) < 0 {
+			// Post back result on the channel
+			resChan <- rnd
+			// Notify other threads we've found a valid nonce
+			Found = true
+		}
+
+		// Break out if found
+		if Found {
+			break
+		}
+	}
+
+	resChan <- 0
+}
+
+func (dag *Dagger) Search(hash, diff *big.Int) *big.Int {
+	// TODO fix multi threading. Somehow it results in the wrong nonce
+	amountOfRoutines := 1
+
+	dag.hash = hash
+
+	obj := ethutil.BigPow(2, 256)
+	obj = obj.Div(obj, diff)
+
+	Found = false
+	resChan := make(chan int64, 3)
+	var res int64
+
+	for k := 0; k < amountOfRoutines; k++ {
+		go dag.Find(obj, resChan)
+
+		// Wait for each go routine to finish
+	}
+	for k := 0; k < amountOfRoutines; k++ {
+		// Get the result from the channel. 0 = quit
+		if r := <-resChan; r != 0 {
+			res = r
+		}
+	}
+
+	return big.NewInt(res)
+}
+
+func (dag *Dagger) Verify(hash, diff, nonce *big.Int) bool {
+	dag.hash = hash
+
+	obj := ethutil.BigPow(2, 256)
+	obj = obj.Div(obj, diff)
+
+	return dag.Eval(nonce).Cmp(obj) < 0
+}
+
+func DaggerVerify(hash, diff, nonce *big.Int) bool {
+	dagger := &Dagger{}
+	dagger.hash = hash
+
+	obj := ethutil.BigPow(2, 256)
+	obj = obj.Div(obj, diff)
+
+	return dagger.Eval(nonce).Cmp(obj) < 0
+}
+
+func (dag *Dagger) Node(L uint64, i uint64) *big.Int {
+	if L == i {
+		return dag.hash
+	}
+
+	var m *big.Int
+	if L == 9 {
+		m = big.NewInt(16)
+	} else {
+		m = big.NewInt(3)
+	}
+
+	sha := sha3.NewKeccak256()
+	sha.Reset()
+	d := sha3.NewKeccak256()
+	b := new(big.Int)
+	ret := new(big.Int)
+
+	for k := 0; k < int(m.Uint64()); k++ {
+		d.Reset()
+		d.Write(dag.hash.Bytes())
+		d.Write(dag.xn.Bytes())
+		d.Write(big.NewInt(int64(L)).Bytes())
+		d.Write(big.NewInt(int64(i)).Bytes())
+		d.Write(big.NewInt(int64(k)).Bytes())
+
+		b.SetBytes(Sum(d))
+		pk := b.Uint64() & ((1 << ((L - 1) * 3)) - 1)
+		sha.Write(dag.Node(L-1, pk).Bytes())
+	}
+
+	ret.SetBytes(Sum(sha))
+
+	return ret
+}
+
+func Sum(sha hash.Hash) []byte {
+	//in := make([]byte, 32)
+	return sha.Sum(nil)
+}
+
+func (dag *Dagger) Eval(N *big.Int) *big.Int {
+	pow := ethutil.BigPow(2, 26)
+	dag.xn = pow.Div(N, pow)
+
+	sha := sha3.NewKeccak256()
+	sha.Reset()
+	ret := new(big.Int)
+
+	for k := 0; k < 4; k++ {
+		d := sha3.NewKeccak256()
+		b := new(big.Int)
+
+		d.Reset()
+		d.Write(dag.hash.Bytes())
+		d.Write(dag.xn.Bytes())
+		d.Write(N.Bytes())
+		d.Write(big.NewInt(int64(k)).Bytes())
+
+		b.SetBytes(Sum(d))
+		pk := (b.Uint64() & 0x1ffffff)
+
+		sha.Write(dag.Node(9, pk).Bytes())
+	}
+
+	return ret.SetBytes(Sum(sha))
+}
diff --git a/pow/dagger/dagger_test.go b/pow/dagger/dagger_test.go
new file mode 100644
index 000000000..f3a71d1eb
--- /dev/null
+++ b/pow/dagger/dagger_test.go
@@ -0,0 +1,19 @@
+package dagger
+
+import (
+	"math/big"
+	"testing"
+
+	"github.com/ethereum/go-ethereum/ethutil"
+)
+
+func BenchmarkDaggerSearch(b *testing.B) {
+	hash := big.NewInt(0)
+	diff := ethutil.BigPow(2, 36)
+	o := big.NewInt(0) // nonce doesn't matter. We're only testing against speed, not validity
+
+	// Reset timer so the big generation isn't included in the benchmark
+	b.ResetTimer()
+	// Validate
+	DaggerVerify(hash, diff, o)
+}
diff --git a/pow/dash/crypto.c b/pow/dash/crypto.c
new file mode 100644
index 000000000..9c5a62d16
--- /dev/null
+++ b/pow/dash/crypto.c
@@ -0,0 +1,5 @@
+extern char *Sha3(char *, int);
+char *sha3_cgo(char *data, int l)
+{
+	return Sha3(data, l);
+}
diff --git a/pow/dash/crypto.go b/pow/dash/crypto.go
new file mode 100644
index 000000000..0644a54ae
--- /dev/null
+++ b/pow/dash/crypto.go
@@ -0,0 +1,14 @@
+package dash
+
+/*
+char *sha3_cgo(char *, int); // Forward declaration
+*/
+import "C"
+import (
+	"github.com/ethereum/go-ethereum/crypto"
+)
+
+//export Sha3
+func Sha3(data []byte, l int) []byte {
+	return crypto.Sha3(data)
+}
diff --git a/pow/ezp/pow.go b/pow/ezp/pow.go
new file mode 100644
index 000000000..5abe6950e
--- /dev/null
+++ b/pow/ezp/pow.go
@@ -0,0 +1,93 @@
+package ezp
+
+import (
+	"math/big"
+	"math/rand"
+	"time"
+
+	"github.com/ethereum/go-ethereum/crypto"
+	"github.com/ethereum/go-ethereum/crypto/sha3"
+	"github.com/ethereum/go-ethereum/ethutil"
+	"github.com/ethereum/go-ethereum/logger"
+	"github.com/ethereum/go-ethereum/pow"
+)
+
+var powlogger = logger.NewLogger("POW")
+
+type EasyPow struct {
+	hash     *big.Int
+	HashRate int64
+	turbo    bool
+}
+
+func New() *EasyPow {
+	return &EasyPow{turbo: false}
+}
+
+func (pow *EasyPow) GetHashrate() int64 {
+	return pow.HashRate
+}
+
+func (pow *EasyPow) Turbo(on bool) {
+	pow.turbo = on
+}
+
+func (pow *EasyPow) Search(block pow.Block, stop <-chan struct{}) []byte {
+	r := rand.New(rand.NewSource(time.Now().UnixNano()))
+	hash := block.HashNoNonce()
+	diff := block.Difficulty()
+	i := int64(0)
+	start := time.Now().UnixNano()
+	t := time.Now()
+
+	for {
+		select {
+		case <-stop:
+			powlogger.Infoln("Breaking from mining")
+			pow.HashRate = 0
+			return nil
+		default:
+			i++
+
+			if time.Since(t) > (1 * time.Second) {
+				elapsed := time.Now().UnixNano() - start
+				hashes := ((float64(1e9) / float64(elapsed)) * float64(i)) / 1000
+				pow.HashRate = int64(hashes)
+				powlogger.Infoln("Hashing @", pow.HashRate, "khash")
+
+				t = time.Now()
+			}
+
+			sha := crypto.Sha3(big.NewInt(r.Int63()).Bytes())
+			if verify(hash, diff, sha) {
+				return sha
+			}
+		}
+
+		if !pow.turbo {
+			time.Sleep(20 * time.Microsecond)
+		}
+	}
+
+	return nil
+}
+
+func (pow *EasyPow) Verify(block pow.Block) bool {
+	return Verify(block)
+}
+
+func verify(hash []byte, diff *big.Int, nonce []byte) bool {
+	sha := sha3.NewKeccak256()
+
+	d := append(hash, nonce...)
+	sha.Write(d)
+
+	verification := new(big.Int).Div(ethutil.BigPow(2, 256), diff)
+	res := ethutil.U256(ethutil.BigD(sha.Sum(nil)))
+
+	return res.Cmp(verification) <= 0
+}
+
+func Verify(block pow.Block) bool {
+	return verify(block.HashNoNonce(), block.Difficulty(), block.N())
+}
diff --git a/pow/pow.go b/pow/pow.go
new file mode 100644
index 000000000..c94ee40ba
--- /dev/null
+++ b/pow/pow.go
@@ -0,0 +1,8 @@
+package pow
+
+type PoW interface {
+	Search(block Block, stop <-chan struct{}) []byte
+	Verify(block Block) bool
+	GetHashrate() int64
+	Turbo(bool)
+}