From cb845b9bc84dada9d03eb9d9cb9ccfa96c7ce06c Mon Sep 17 00:00:00 2001 From: obscuren Date: Fri, 10 Oct 2014 22:44:20 +0200 Subject: Implemented AR PoW --- pow/ar/block.go | 11 +++++ pow/ar/ops.go | 54 ++++++++++++++++++++++++ pow/ar/pow.go | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++ pow/ar/pow_test.go | 47 +++++++++++++++++++++ pow/ar/rnd.go | 66 +++++++++++++++++++++++++++++ 5 files changed, 300 insertions(+) create mode 100644 pow/ar/block.go create mode 100644 pow/ar/ops.go create mode 100644 pow/ar/pow.go create mode 100644 pow/ar/pow_test.go create mode 100644 pow/ar/rnd.go (limited to 'pow') diff --git a/pow/ar/block.go b/pow/ar/block.go new file mode 100644 index 000000000..cc02028cd --- /dev/null +++ b/pow/ar/block.go @@ -0,0 +1,11 @@ +package ar + +import ( + "math/big" + "github.com/ethereum/eth-go/ethtrie" +) + +type Block interface { + Trie() *ethtrie.Trie + Diff() *big.Int +} diff --git a/pow/ar/ops.go b/pow/ar/ops.go new file mode 100644 index 000000000..3a099be08 --- /dev/null +++ b/pow/ar/ops.go @@ -0,0 +1,54 @@ +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 new file mode 100644 index 000000000..504b8d7ce --- /dev/null +++ b/pow/ar/pow.go @@ -0,0 +1,122 @@ +package ar + +import ( + "math/big" + + "github.com/ethereum/eth-go/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 new file mode 100644 index 000000000..d4d419b3a --- /dev/null +++ b/pow/ar/pow_test.go @@ -0,0 +1,47 @@ +package ar + +import ( + "fmt" + "math/big" + "testing" + + "github.com/ethereum/eth-go/ethdb" + "github.com/ethereum/eth-go/ethtrie" +) + +type TestBlock struct { + trie *ethtrie.Trie +} + +func NewTestBlock() *TestBlock { + db, _ := ethdb.NewMemDatabase() + return &TestBlock{ + trie: ethtrie.New(db, ""), + } +} + +func (self *TestBlock) Diff() *big.Int { + return b(10) +} + +func (self *TestBlock) Trie() *ethtrie.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 new file mode 100644 index 000000000..4862d058d --- /dev/null +++ b/pow/ar/rnd.go @@ -0,0 +1,66 @@ +package ar + +import ( + "math/big" + + "github.com/ethereum/eth-go/ethcrypto" + "github.com/ethereum/eth-go/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(ethcrypto.Sha3(b.Bytes())) + } else if b, ok := v.([]interface{}); ok { + return ethutil.BigD(ethcrypto.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(ethcrypto.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)) +} -- cgit From f3473312ba90b37b9a4100592a8c4d5d5bf245b7 Mon Sep 17 00:00:00 2001 From: Felix Lange Date: Fri, 31 Oct 2014 18:40:32 +0100 Subject: all: fix rename breakage --- pow/ar/block.go | 4 ++-- pow/ar/pow_test.go | 8 ++++---- pow/ar/rnd.go | 8 ++++---- 3 files changed, 10 insertions(+), 10 deletions(-) (limited to 'pow') diff --git a/pow/ar/block.go b/pow/ar/block.go index 541092f7e..2124b53b4 100644 --- a/pow/ar/block.go +++ b/pow/ar/block.go @@ -3,10 +3,10 @@ package ar import ( "math/big" - "github.com/ethereum/go-ethereum/ethtrie" + "github.com/ethereum/go-ethereum/trie" ) type Block interface { - Trie() *ethtrie.Trie + Trie() *trie.Trie Diff() *big.Int } diff --git a/pow/ar/pow_test.go b/pow/ar/pow_test.go index 3db9659e0..b1ebf9281 100644 --- a/pow/ar/pow_test.go +++ b/pow/ar/pow_test.go @@ -6,17 +6,17 @@ import ( "testing" "github.com/ethereum/go-ethereum/ethdb" - "github.com/ethereum/go-ethereum/ethtrie" + "github.com/ethereum/go-ethereum/trie" ) type TestBlock struct { - trie *ethtrie.Trie + trie *trie.Trie } func NewTestBlock() *TestBlock { db, _ := ethdb.NewMemDatabase() return &TestBlock{ - trie: ethtrie.New(db, ""), + trie: trie.New(db, ""), } } @@ -24,7 +24,7 @@ func (self *TestBlock) Diff() *big.Int { return b(10) } -func (self *TestBlock) Trie() *ethtrie.Trie { +func (self *TestBlock) Trie() *trie.Trie { return self.trie } diff --git a/pow/ar/rnd.go b/pow/ar/rnd.go index 7dbd99373..c62f4e062 100644 --- a/pow/ar/rnd.go +++ b/pow/ar/rnd.go @@ -3,7 +3,7 @@ package ar import ( "math/big" - "github.com/ethereum/go-ethereum/ethcrypto" + "github.com/ethereum/go-ethereum/crypto" "github.com/ethereum/go-ethereum/ethutil" ) @@ -21,16 +21,16 @@ func (self ByteNode) Big() *big.Int { func Sha3(v interface{}) *big.Int { if b, ok := v.(*big.Int); ok { - return ethutil.BigD(ethcrypto.Sha3(b.Bytes())) + return ethutil.BigD(crypto.Sha3(b.Bytes())) } else if b, ok := v.([]interface{}); ok { - return ethutil.BigD(ethcrypto.Sha3(ethutil.Encode(b))) + 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(ethcrypto.Sha3(ethutil.Encode(v))) + return ethutil.BigD(crypto.Sha3(ethutil.Encode(v))) } return nil -- cgit From 1b98cbbfa4f587107fa15fccde7d22102ea4b1c0 Mon Sep 17 00:00:00 2001 From: obscuren Date: Wed, 10 Dec 2014 16:45:16 +0100 Subject: Moved pow --- pow/block.go | 9 ++++++ pow/ezp/pow.go | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ pow/pow.go | 8 ++++++ 3 files changed, 106 insertions(+) create mode 100644 pow/block.go create mode 100644 pow/ezp/pow.go create mode 100644 pow/pow.go (limited to 'pow') diff --git a/pow/block.go b/pow/block.go new file mode 100644 index 000000000..4759e19fb --- /dev/null +++ b/pow/block.go @@ -0,0 +1,9 @@ +package pow + +import "math/big" + +type Block interface { + Diff() *big.Int + HashNoNonce() []byte + N() []byte +} diff --git a/pow/ezp/pow.go b/pow/ezp/pow.go new file mode 100644 index 000000000..cdf89950f --- /dev/null +++ b/pow/ezp/pow.go @@ -0,0 +1,89 @@ +package ezp + +import ( + "math/big" + "math/rand" + "time" + + "github.com/ethereum/go-ethereum/crypto" + "github.com/ethereum/go-ethereum/ethutil" + "github.com/ethereum/go-ethereum/logger" + "github.com/ethereum/go-ethereum/pow" + "github.com/obscuren/sha3" +) + +var powlogger = logger.NewLogger("POW") + +type EasyPow struct { + hash *big.Int + HashRate int64 + turbo bool +} + +func New() *EasyPow { + return &EasyPow{} +} + +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.Diff() + 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 pow.verify(hash, diff, sha) { + return sha + } + } + + if !pow.turbo { + time.Sleep(20 * time.Microsecond) + } + } + + return nil +} + +func (pow *EasyPow) 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 (pow *EasyPow) Verify(block pow.Block) bool { + return pow.verify(block.HashNoNonce(), block.Diff(), 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) +} -- cgit From 49e0267fe76cfd13eaf3e5e26caa637b93dbdd29 Mon Sep 17 00:00:00 2001 From: obscuren Date: Thu, 18 Dec 2014 13:12:54 +0100 Subject: Locks, refactor, tests * Added additional chain tests * Added proper mutex' on chain * Removed ethereum dependencies --- pow/ezp/pow.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'pow') diff --git a/pow/ezp/pow.go b/pow/ezp/pow.go index cdf89950f..bfe3ea098 100644 --- a/pow/ezp/pow.go +++ b/pow/ezp/pow.go @@ -21,7 +21,7 @@ type EasyPow struct { } func New() *EasyPow { - return &EasyPow{} + return &EasyPow{turbo: true} } func (pow *EasyPow) GetHashrate() int64 { -- cgit