This repository has been archived by the owner on Jan 9, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 583
/
equi.h
135 lines (117 loc) · 3.55 KB
/
equi.h
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
#pragma once
// Equihash solver
// Copyright (c) 2016-2016 John Tromp
#include "blake2/blake2.h"
#ifdef __APPLE__
#include "osx_barrier.h"
#include <machine/endian.h>
#include <libkern/OSByteOrder.h>
#define htole32(x) OSSwapHostToLittleInt32(x)
#else
#ifdef WIN32
#include "pthreads/pthread.h"
#undef _POSIX_THREADS
#endif
#endif
#include <stdint.h> // for types uint32_t,uint64_t
#include <string.h> // for functions memset
#include <stdlib.h> // for function qsort
#include <stdbool.h>
typedef uint32_t u32;
typedef unsigned char uchar;
// algorithm parameters, prefixed with W to reduce include file conflicts
#ifndef WN
#define WN 200
#endif
#ifndef WK
#define WK 9
#endif
#define PARAMETER_N WN
#define PARAMETER_K WK
#define NDIGITS (WK+1)
#define DIGITBITS (WN/(NDIGITS))
#define PROOFSIZE (1<<WK)
#define BASE (1<<DIGITBITS)
#define NHASHES (2*BASE)
#define HASHESPERBLAKE (512/WN)
#define HASHOUT (HASHESPERBLAKE*WN/8)
typedef u32 proof[PROOFSIZE];
void setheader(blake2b_state *ctx, const char *header, const u32 headerLen, const char* nce, const u32 nonceLen) {
uint32_t le_N = WN;
uint32_t le_K = WK;
uchar personal[] = "ZcashPoW01230123";
memcpy(personal+8, &le_N, 4);
memcpy(personal+12, &le_K, 4);
blake2b_param P[1];
P->digest_length = HASHOUT;
P->key_length = 0;
P->fanout = 1;
P->depth = 1;
P->leaf_length = 0;
P->node_offset = 0;
P->node_depth = 0;
P->inner_length = 0;
memset(P->reserved, 0, sizeof(P->reserved));
memset(P->salt, 0, sizeof(P->salt));
memcpy(P->personal, (const uint8_t *)personal, 16);
blake2b_init_param(ctx, P);
blake2b_update(ctx, (const uchar *)header, headerLen);
blake2b_update(ctx, (const uchar *)nce, nonceLen);
}
enum verify_code { POW_OK, POW_DUPLICATE, POW_OUT_OF_ORDER, POW_NONZERO_XOR };
const char *errstr[] = { "OK", "duplicate index", "indices out of order", "nonzero xor" };
void genhash(blake2b_state *ctx, u32 idx, uchar *hash) {
blake2b_state state = *ctx;
u32 leb = (idx / HASHESPERBLAKE);
blake2b_update(&state, (uchar *)&leb, sizeof(u32));
uchar blakehash[HASHOUT];
blake2b_final(&state, blakehash, HASHOUT);
memcpy(hash, blakehash + (idx % HASHESPERBLAKE) * WN/8, WN/8);
}
int verifyrec(blake2b_state *ctx, u32 *indices, uchar *hash, int r) {
if (r == 0) {
genhash(ctx, *indices, hash);
return POW_OK;
}
u32 *indices1 = indices + (1 << (r-1));
if (*indices >= *indices1)
return POW_OUT_OF_ORDER;
uchar hash0[WN/8], hash1[WN/8];
int vrf0 = verifyrec(ctx, indices, hash0, r-1);
if (vrf0 != POW_OK)
return vrf0;
int vrf1 = verifyrec(ctx, indices1, hash1, r-1);
if (vrf1 != POW_OK)
return vrf1;
for (int i=0; i < WN/8; i++)
hash[i] = hash0[i] ^ hash1[i];
int i, b = r * DIGITBITS;
for (i = 0; i < b/8; i++)
if (hash[i])
return POW_NONZERO_XOR;
if ((b%8) && hash[i] >> (8-(b%8)))
return POW_NONZERO_XOR;
return POW_OK;
}
int compu32(const void *pa, const void *pb) {
u32 a = *(u32 *)pa, b = *(u32 *)pb;
return a<b ? -1 : a==b ? 0 : +1;
}
bool duped(proof prf) {
proof sortprf;
memcpy(sortprf, prf, sizeof(proof));
qsort(sortprf, PROOFSIZE, sizeof(u32), &compu32);
for (u32 i=1; i<PROOFSIZE; i++)
if (sortprf[i] <= sortprf[i-1])
return true;
return false;
}
// verify Wagner conditions
int verify(u32 indices[PROOFSIZE], const char *header, const u32 headerlen, const char *nonce, u32 noncelen) {
if (duped(indices))
return POW_DUPLICATE;
blake2b_state ctx;
setheader(&ctx, header, headerlen, nonce, noncelen);
uchar hash[WN/8];
return verifyrec(&ctx, indices, hash, WK);
}