-
Notifications
You must be signed in to change notification settings - Fork 95
/
worker.go
146 lines (126 loc) · 3.89 KB
/
worker.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
package pow
import (
"context"
"errors"
"math"
"math/bits"
"sync"
"sync/atomic"
legacy "github.com/iotaledger/iota.go/consts"
"github.com/iotaledger/iota.go/curl/bct"
"github.com/iotaledger/iota.go/encoding/b1t6"
"github.com/iotaledger/iota.go/trinary"
)
// errors returned by the PoW
var (
ErrCancelled = errors.New("canceled")
ErrDone = errors.New("done")
)
// The Worker performs the PoW.
type Worker struct {
numWorkers int
}
// New creates a new PoW Worker.
// The optional numWorkers specifies how many go routines should be used to perform the PoW.
func New(numWorkers ...int) *Worker {
w := &Worker{
numWorkers: 1,
}
if len(numWorkers) > 0 && numWorkers[0] > 0 {
w.numWorkers = numWorkers[0]
}
return w
}
const ln3 = 1.098612288668109691395245236922525704647490557822749451734694333 // https://oeis.org/A002391
// Mine performs the PoW for data.
// It returns a nonce that appended to data results in a PoW score of at least targetScore.
// The computation can be canceled anytime using ctx.
func (w *Worker) Mine(ctx context.Context, data []byte, targetScore float64) (uint64, error) {
var (
done uint32
counter uint64
wg sync.WaitGroup
results = make(chan uint64, w.numWorkers)
closing = make(chan struct{})
)
// compute the digest
h := Hash.New()
h.Write(data)
powDigest := h.Sum(nil)
// stop when the context has been canceled
go func() {
select {
case <-ctx.Done():
atomic.StoreUint32(&done, 1)
case <-closing:
return
}
}()
// compute the minimum numbers of trailing zeros required to get a PoW score ≥ targetScore
targetZeros := uint(math.Ceil(math.Log(float64(len(data)+nonceBytes)*targetScore) / ln3))
workerWidth := math.MaxUint64 / uint64(w.numWorkers)
for i := 0; i < w.numWorkers; i++ {
startNonce := uint64(i) * workerWidth
wg.Add(1)
go func() {
defer wg.Done()
nonce, workerErr := w.worker(powDigest, startNonce, targetZeros, &done, &counter)
if workerErr != nil {
return
}
atomic.StoreUint32(&done, 1)
results <- nonce
}()
}
wg.Wait()
close(results)
close(closing)
nonce, ok := <-results
if !ok {
return 0, ErrCancelled
}
return nonce, nil
}
func (w *Worker) worker(powDigest []byte, startNonce uint64, target uint, done *uint32, counter *uint64) (uint64, error) {
if target > legacy.HashTrinarySize {
panic("pow: invalid trailing zeros target")
}
// use batched Curl hashing
c := bct.NewCurlP81()
var l, h [legacy.HashTrinarySize]uint
// allocate exactly one Curl block for each batch index and fill it with the encoded digest
buf := make([]trinary.Trits, bct.MaxBatchSize)
for i := range buf {
buf[i] = make(trinary.Trits, legacy.HashTrinarySize)
b1t6.Encode(buf[i], powDigest)
}
digestTritsLen := b1t6.EncodedLen(len(powDigest))
for nonce := startNonce; atomic.LoadUint32(done) == 0; nonce += bct.MaxBatchSize {
// add the nonce to each trit buffer
for i := range buf {
nonceBuf := buf[i][digestTritsLen:]
encodeNonce(nonceBuf, nonce+uint64(i))
}
// process the batch
c.Reset()
if err := c.Absorb(buf, legacy.HashTrinarySize); err != nil {
return 0, err
}
c.CopyState(l[:], h[:]) // the first 243 entries of the state correspond to the resulting hashes
atomic.AddUint64(counter, bct.MaxBatchSize)
// check the state whether it corresponds to a hash with sufficient amount of trailing zeros
// this is equivalent to computing the hashes with Squeeze and then checking TrailingZeros of each
if i := checkStateTrits(&l, &h, target); i < bct.MaxBatchSize {
return nonce + uint64(i), nil
}
}
return 0, ErrDone
}
func checkStateTrits(l, h *[legacy.HashTrinarySize]uint, n uint) int {
var v uint
for i := legacy.HashTrinarySize - n; i < legacy.HashTrinarySize; i++ {
v |= l[i] ^ h[i] // 0 if trit is zero, 1 otherwise
}
// return the index of the first zero bit, this corresponds to the index of the hash with n trailing zero trits
return bits.TrailingZeros(^v)
}