aboutsummaryrefslogtreecommitdiffstats
path: root/pow
diff options
context:
space:
mode:
authorFelix Lange <fjl@twurst.com>2014-10-23 21:01:27 +0800
committerFelix Lange <fjl@twurst.com>2014-10-23 21:01:27 +0800
commit69baa465ea69ae60eed802445cf0132b9eb69934 (patch)
treeb09da7582b5c4850d4db13aee808f2fef2f97de0 /pow
parent50fd46924900869e7210217c6a07979b544991c8 (diff)
parentfeef194829b07570e91873ed5d1e8cc51e8fa430 (diff)
downloadgo-tangerine-69baa465ea69ae60eed802445cf0132b9eb69934.tar
go-tangerine-69baa465ea69ae60eed802445cf0132b9eb69934.tar.gz
go-tangerine-69baa465ea69ae60eed802445cf0132b9eb69934.tar.bz2
go-tangerine-69baa465ea69ae60eed802445cf0132b9eb69934.tar.lz
go-tangerine-69baa465ea69ae60eed802445cf0132b9eb69934.tar.xz
go-tangerine-69baa465ea69ae60eed802445cf0132b9eb69934.tar.zst
go-tangerine-69baa465ea69ae60eed802445cf0132b9eb69934.zip
Merge eth-go repository into go-ethereum
mist, etheruem have been moved to cmd/
Diffstat (limited to 'pow')
-rw-r--r--pow/ar/block.go12
-rw-r--r--pow/ar/ops.go54
-rw-r--r--pow/ar/pow.go122
-rw-r--r--pow/ar/pow_test.go47
-rw-r--r--pow/ar/rnd.go66
5 files changed, 301 insertions, 0 deletions
diff --git a/pow/ar/block.go b/pow/ar/block.go
new file mode 100644
index 000000000..541092f7e
--- /dev/null
+++ b/pow/ar/block.go
@@ -0,0 +1,12 @@
+package ar
+
+import (
+ "math/big"
+
+ "github.com/ethereum/go-ethereum/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..8991a674b
--- /dev/null
+++ b/pow/ar/pow.go
@@ -0,0 +1,122 @@
+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
new file mode 100644
index 000000000..3db9659e0
--- /dev/null
+++ b/pow/ar/pow_test.go
@@ -0,0 +1,47 @@
+package ar
+
+import (
+ "fmt"
+ "math/big"
+ "testing"
+
+ "github.com/ethereum/go-ethereum/ethdb"
+ "github.com/ethereum/go-ethereum/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..7dbd99373
--- /dev/null
+++ b/pow/ar/rnd.go
@@ -0,0 +1,66 @@
+package ar
+
+import (
+ "math/big"
+
+ "github.com/ethereum/go-ethereum/ethcrypto"
+ "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(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))
+}