1
package hashcash
2
 
3
import (
4
	"crypto/rand"
5
	"crypto/sha256"
6
	"encoding/base64"
7
	"encoding/binary"
8
	"errors"
9
	"strconv"
10
	"strings"
11
	"time"
12
)
13
 
14
// ErrParse is returned when fewer than 6 or more than 7 segments are split
15
var ErrParse = errors.New("could not split the hashcash parts")
16
 
17
// ErrInvalidTag is returned when the Hashcash version is unsupported
18
var ErrInvalidTag = errors.New("expected tag to be 'H'")
19
 
20
// ErrInvalidDifficulty is returned when the difficulty is outside of the acceptable range
21
var ErrInvalidDifficulty = errors.New("the number of bits of difficulty is too low or too high")
22
 
23
// ErrInvalidDate is returned when the date cannot be parsed as a positive int64
24
var ErrInvalidDate = errors.New("invalid date")
25
 
26
// ErrExpired is returned when the current time is past that of ExpiresAt
27
var ErrExpired = errors.New("expired hashcash")
28
 
29
// ErrInvalidSubject is returned when the subject is invalid or does not match that passed to Verify()
30
var ErrInvalidSubject = errors.New("the subject is invalid or rejected")
31
 
32
// ErrInvalidNonce is returned when the nonce
33
//var ErrInvalidNonce = errors.New("the nonce has been used or is invalid")
34
 
35
// ErrUnsupportedAlgorithm is returned when the given algorithm is not supported
36
var ErrUnsupportedAlgorithm = errors.New("the given algorithm is invalid or not supported")
37
 
38
// ErrInvalidSolution is returned when the given hashcash is not properly solved
39
var ErrInvalidSolution = errors.New("the given solution is not valid")
40
 
41
// MaxDifficulty is the upper bound for all Solve() operations
42
var MaxDifficulty = 26
43
 
44
// Sep is the separator character to use
45
var Sep = ":"
46
 
47
// no milliseconds
48
//var isoTS = "2006-01-02T15:04:05Z"
49
 
50
// Hashcash represents a parsed Hashcash string
51
type Hashcash struct {
52
	Tag        string    `json:"tag"`        // Always "H" for "HTTP"
53
	Difficulty int       `json:"difficulty"` // Number of "partial pre-image" (zero) bits in the hashed code
54
	ExpiresAt  time.Time `json:"exp"`        // The timestamp that the hashcash expires, as seconds since the Unix epoch
55
	Subject    string    `json:"sub"`        // Resource data string being transmitted, e.g., a domain or URL
56
	Nonce      string    `json:"nonce"`      // Unique string of random characters, encoded as url-safe base-64
57
	Alg        string    `json:"alg"`        // always SHA-256 for now
58
	Solution   string    `json:"solution"`   // Binary counter, encoded as url-safe base-64
59
}
60
 
61
// New returns a Hashcash with reasonable defaults
62
func New(h Hashcash) *Hashcash {
63
	h.Tag = "H"
64
 
65
	if 0 == h.Difficulty {
66
		// safe for WebCrypto
67
		h.Difficulty = 10
68
	}
69
 
70
	if h.ExpiresAt.IsZero() {
71
		h.ExpiresAt = time.Now().Add(5 * time.Minute)
72
	}
73
	h.ExpiresAt = h.ExpiresAt.UTC().Truncate(time.Second)
74
 
75
	if "" == h.Subject {
76
		h.Subject = "*"
77
	}
78
 
79
	if "" == h.Nonce {
80
		nonce := make([]byte, 16)
81
		if _, err := rand.Read(nonce); nil != err {
82
			panic(err)
83
		}
84
		h.Nonce = base64.RawURLEncoding.EncodeToString(nonce)
85
	}
86
 
87
	if "" == h.Alg {
88
		h.Alg = "SHA-256"
89
	}
90
	/*
91
		if "SHA-256" != h.Alg {
92
			// TODO error
93
		}
94
	*/
95
 
96
	return &h
97
}
98
 
99
// Parse will (obviously) parse the hashcash string, without verifying any
100
// of the parameters.
101
func Parse(hc string) (*Hashcash, error) {
102
	parts := strings.Split(hc, Sep)
103
	n := len(parts)
104
	if n < 6 || n > 7 {
105
		return nil, ErrParse
106
	}
107
 
108
	tag := parts[0]
109
	if "H" != tag {
110
		return nil, ErrInvalidTag
111
	}
112
 
113
	bits, err := strconv.Atoi(parts[1])
114
	if nil != err || bits < 0 {
115
		return nil, ErrInvalidDifficulty
116
	}
117
 
118
	// Allow empty ExpiresAt
119
	var exp time.Time
120
	if "" != parts[2] {
121
		expAt, err := strconv.ParseInt(parts[2], 10, 64)
122
		if nil != err || expAt < 0 {
123
			return nil, ErrInvalidDate
124
		}
125
		exp = time.Unix(int64(expAt), 0).UTC()
126
	}
127
 
128
	/*
129
		exp, err := time.ParseInLocation(isoTS, parts[2], time.UTC)
130
		if nil != err {
131
			return nil, ErrInvalidDate
132
		}
133
	*/
134
 
135
	sub := parts[3]
136
 
137
	nonce := parts[4]
138
 
139
	alg := parts[5]
140
 
141
	var solution string
142
	if n > 6 {
143
		solution = parts[6]
144
	}
145
 
146
	h := &Hashcash{
147
		Tag:        tag,
148
		Difficulty: bits,
149
		ExpiresAt:  exp.UTC().Truncate(time.Second),
150
		Subject:    sub,
151
		Nonce:      nonce,
152
		Alg:        alg,
153
		Solution:   solution,
154
	}
155
 
156
	return h, nil
157
}
158
 
159
// String will return the formatted Hashcash, omitting the solution if it has not be solved.
160
func (h *Hashcash) String() string {
161
	var solution string
162
	if "" != h.Solution {
163
		solution = Sep + h.Solution
164
	}
165
 
166
	var expAt string
167
	if !h.ExpiresAt.IsZero() {
168
		expAt = strconv.FormatInt(h.ExpiresAt.UTC().Truncate(time.Second).Unix(), 10)
169
	}
170
	return strings.Join(
171
		[]string{
172
			"H",
173
			strconv.Itoa(h.Difficulty),
174
			//h.ExpiresAt.UTC().Format(isoTS),
175
			expAt,
176
			h.Subject,
177
			h.Nonce,
178
			h.Alg,
179
		},
180
		Sep,
181
	) + solution
182
}
183
 
184
// Verify the Hashcash based on Difficulty, Algorithm, ExpiresAt, Subject and,
185
// of course, the Solution and hash.
186
func (h *Hashcash) Verify(subject string) error {
187
	if h.Difficulty < 0 {
188
		return ErrInvalidDifficulty
189
	}
190
 
191
	if "SHA-256" != h.Alg {
192
		return ErrUnsupportedAlgorithm
193
	}
194
 
195
	if !h.ExpiresAt.IsZero() && h.ExpiresAt.Sub(time.Now()) < 0 {
196
		return ErrExpired
197
	}
198
 
199
	if subject != h.Subject {
200
		return ErrInvalidSubject
201
	}
202
 
203
	bits := h.Difficulty
204
	hash := sha256.Sum256([]byte(h.String()))
205
	n := bits / 8 // 10 / 8 = 1
206
	m := bits % 8 // 10 % 8 = 2
207
	if m > 0 {
208
		n++ // 10 bits = 2 bytes
209
	}
210
 
211
	if !verifyBits(hash[:n], bits, n) {
212
		return ErrInvalidSolution
213
	}
214
	return nil
215
}
216
 
217
func verifyBits(hash []byte, bits, n int) bool {
218
	if 0 == bits {
219
		return true
220
	}
221
 
222
	for i := range n {
223
		if bits > 8 {
224
			bits -= 8
225
			if 0 != hash[i] {
226
				return false
227
			}
228
			continue
229
		}
230
 
231
		// (bits % 8) == bits
232
		pad := 8 - bits
233
		if 0 == hash[i]>>pad {
234
			return true
235
		}
236
	}
237
 
238
	return false
239
}
240
 
241
// Solve will search for a solution, returning an error if the difficulty is
242
// above the local or global MaxDifficulty, the Algorithm is unsupported.
243
func (h *Hashcash) Solve(maxDifficulty int) error {
244
	if "SHA-256" != h.Alg {
245
		return ErrUnsupportedAlgorithm
246
	}
247
 
248
	if h.Difficulty < 0 {
249
		return ErrInvalidDifficulty
250
	}
251
 
252
	if h.Difficulty > maxDifficulty || h.Difficulty > MaxDifficulty {
253
		return ErrInvalidDifficulty
254
	}
255
 
256
	if "" != h.Solution {
257
		if nil == h.Verify(h.Subject) {
258
			return nil
259
		}
260
		h.Solution = ""
261
	}
262
 
263
	hashcash := h.String()
264
	bits := h.Difficulty
265
	n := bits / 8 // 10 / 8 = 1
266
	m := bits % 8 // 10 % 8 = 2
267
	if m > 0 {
268
		n++ // 10 bits = 2 bytes
269
	}
270
 
271
	var solution uint32 = 0
272
	sb := make([]byte, 4)
273
	for {
274
		// Note: it's not actually important what method of change or encoding is used
275
		// but incrementing by 1 on an int32 is good enough, and makes for a small base64 encoding
276
		binary.LittleEndian.PutUint32(sb, solution)
277
		h.Solution = base64.RawURLEncoding.EncodeToString(sb)
278
		hash := sha256.Sum256([]byte(hashcash + Sep + h.Solution))
279
		if verifyBits(hash[:n], bits, n) {
280
			return nil
281
		}
282
		solution++
283
	}
284
}