GNUnet 0.21.2
gnsrecord_pow.c
Go to the documentation of this file.
1/*
2 This file is part of GNUnet
3 Copyright (C) 2013, 2016 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
9
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20
21
26#include "platform.h"
27#include "gnunet_util_lib.h"
29#include "gnunet_signatures.h"
30#include "gnunet_protocols.h"
31#include <inttypes.h>
32
37struct BestPow
38{
42 uint64_t pow;
43
47 unsigned int bits;
48};
49
50
56{
61
66
70 uint64_t current_pow;
71
76 unsigned int epochs;
77
81 unsigned int difficulty;
82
83};
84
85static struct GNUNET_CRYPTO_PowSalt salt = { "GnsRevocationPow" };
86
93static unsigned int
95{
96 double sum = 0.0;
97 for (unsigned int j = 0; j<POW_COUNT; j++)
98 sum += ph->best[j].bits;
99 double avg = sum / POW_COUNT;
100 return avg;
101}
102
103
106{
108 const struct GNUNET_CRYPTO_PublicKey *pk;
109 size_t ksize;
110
111 pk = (const struct GNUNET_CRYPTO_PublicKey *) &pow[1];
113 spurp = GNUNET_malloc (sizeof (*spurp) + ksize);
114 spurp->timestamp = pow->timestamp;
116 spurp->purpose.size = htonl (sizeof(*spurp) + ksize);
118 (char*) &spurp[1],
119 ksize);
120 return spurp;
121}
122
123
126 const struct GNUNET_CRYPTO_PublicKey *key)
127{
129 unsigned char *sig;
130 size_t ksize;
131 int ret;
132
134 spurp = GNR_create_signature_message (pow);
135 sig = ((unsigned char*) &pow[1] + ksize);
136 ret =
139 &spurp->purpose,
140 sig,
141 key);
142 GNUNET_free (spurp);
143 return ret == GNUNET_OK ? GNUNET_OK : GNUNET_SYSERR;
144}
145
146
149{
150 const struct GNUNET_CRYPTO_PublicKey *pk;
151
152 pk = (const struct GNUNET_CRYPTO_PublicKey *) &pow[1];
153 return check_signature_identity (pow, pk);
154}
155
156
167 unsigned int difficulty,
169{
170 char buf[sizeof(struct GNUNET_CRYPTO_PublicKey)
171 + sizeof (struct GNUNET_TIME_AbsoluteNBO)
172 + sizeof (uint64_t)] GNUNET_ALIGN;
173 struct GNUNET_HashCode result;
174 struct GNUNET_TIME_Absolute ts;
175 struct GNUNET_TIME_Absolute exp;
177 struct GNUNET_TIME_Relative buffer;
178 /* LSD0001: D' */
179 unsigned int score = 0;
180 unsigned int tmp_score = 0;
181 unsigned int epochs;
182 uint64_t pow_val;
183 ssize_t pklen;
184 const struct GNUNET_CRYPTO_PublicKey *pk;
185
186 pk = (const struct GNUNET_CRYPTO_PublicKey *) &pow[1];
187
191 if (GNUNET_OK != check_signature (pow))
192 {
194 "Proof of work signature invalid!\n");
195 return GNUNET_SYSERR;
196 }
197
201 for (unsigned int i = 0; i < POW_COUNT - 1; i++)
202 {
203 if (GNUNET_ntohll (pow->pow[i]) >= GNUNET_ntohll (pow->pow[i + 1]))
204 return GNUNET_NO;
205 }
206 GNUNET_memcpy (&buf[sizeof(uint64_t)],
207 &pow->timestamp,
208 sizeof (uint64_t));
210 if (0 > pklen)
211 {
212 GNUNET_break (0);
213 return GNUNET_NO;
214 }
215 GNUNET_memcpy (&buf[sizeof(uint64_t) * 2],
216 pk,
217 pklen);
218 for (unsigned int i = 0; i < POW_COUNT; i++)
219 {
220 pow_val = GNUNET_ntohll (pow->pow[i]);
221 GNUNET_memcpy (buf, &pow->pow[i], sizeof(uint64_t));
223 buf,
224 sizeof(buf),
225 &result);
228 "Score %u with %" PRIu64 " (#%u)\n",
229 tmp_score, pow_val, i);
230
231 score += tmp_score;
232
233 }
234 score = score / POW_COUNT;
235 if (score < difficulty)
236 return GNUNET_NO;
237 /* LSD0001: (D'-D+1) */
238 epochs = score - difficulty + 1;
239
245 epochs);
250 10);
251 exp = GNUNET_TIME_absolute_add (ts, ttl);
252 exp = GNUNET_TIME_absolute_add (exp,
253 buffer);
254
255 if (0 != GNUNET_TIME_absolute_get_remaining (ts).rel_value_us)
256 return GNUNET_NO; /* Not yet valid. */
257 /* Revert to actual start time */
259 buffer);
260
261 if (0 == GNUNET_TIME_absolute_get_remaining (exp).rel_value_us)
262 return GNUNET_NO; /* expired */
263 return GNUNET_YES;
264}
265
266
269 struct GNUNET_GNSRECORD_PowP *pow)
270{
273 const struct GNUNET_CRYPTO_PublicKey *pk;
274 size_t ksize;
275 char *sig;
276
283 pk = (const struct GNUNET_CRYPTO_PublicKey *) &pow[1];
287 sig = ((char*) &pow[1]) + ksize;
289 &rp->purpose,
290 (void*) sig);
291 GNUNET_free (rp);
292 if (result == GNUNET_SYSERR)
293 return GNUNET_NO;
294 else
295 return result;
296}
297
298
301 struct GNUNET_GNSRECORD_PowP *pow)
302{
304
305 pk = (struct GNUNET_CRYPTO_PublicKey *) &pow[1];
307 return sign_pow_identity (key, pow);
308}
309
310
317void
319 struct GNUNET_GNSRECORD_PowP *pow)
320{
322}
323
324
327 int epochs,
328 unsigned int difficulty)
329{
332
333
335 pc->pow = pow;
337 epochs);
338 pc->pow->ttl = GNUNET_TIME_relative_hton (ttl);
340 UINT64_MAX);
341 pc->difficulty = difficulty;
342 pc->epochs = epochs;
343 return pc;
344}
345
346
354static int
355cmp_pow_value (const void *a, const void *b)
356{
357 return (GNUNET_ntohll (*(uint64_t*) a) - GNUNET_ntohll (*(uint64_t*) b));
358}
359
360
373{
374 char buf[sizeof(struct GNUNET_CRYPTO_PublicKey)
375 + sizeof (uint64_t)
376 + sizeof (uint64_t)] GNUNET_ALIGN;
377 struct GNUNET_HashCode result;
378 const struct GNUNET_CRYPTO_PublicKey *pk;
379 unsigned int zeros;
380 int ret;
381 uint64_t pow_nbo;
382 ssize_t ksize;
383
384 pc->current_pow++;
385 pk = (const struct GNUNET_CRYPTO_PublicKey *) &(pc->pow[1]);
386
390 for (unsigned int i = 0; i < POW_COUNT; i++)
391 if (pc->current_pow == pc->best[i].pow)
392 return GNUNET_NO;
393 pow_nbo = GNUNET_htonll (pc->current_pow);
394 GNUNET_memcpy (buf, &pow_nbo, sizeof(uint64_t));
395 GNUNET_memcpy (&buf[sizeof(uint64_t)],
396 &pc->pow->timestamp,
397 sizeof (uint64_t));
399 GNUNET_assert (0 < ksize);
400 GNUNET_memcpy (&buf[sizeof(uint64_t) * 2],
401 pk,
402 ksize);
404 buf,
405 sizeof(buf),
406 &result);
408 for (unsigned int i = 0; i < POW_COUNT; i++)
409 {
410 if (pc->best[i].bits < zeros)
411 {
412 pc->best[i].bits = zeros;
413 pc->best[i].pow = pc->current_pow;
414 pc->pow->pow[i] = pow_nbo;
416 "New best score %u with %" PRIu64 " (#%u)\n",
417 zeros, pc->current_pow, i);
418
419 break;
420 }
421 }
422 ret = calculate_score (pc) >= pc->difficulty + pc->epochs ? GNUNET_YES :
423 GNUNET_NO;
424 if (GNUNET_YES == ret)
425 {
426 /* Sort POWs) */
427 qsort (pc->pow->pow, POW_COUNT, sizeof (uint64_t), &cmp_pow_value);
428 }
429 return ret;
430}
431
432
433size_t
435{
436 size_t size;
437 size_t ksize;
438 const struct GNUNET_CRYPTO_PublicKey *pk;
439
440 size = sizeof (struct GNUNET_GNSRECORD_PowP);
441 pk = (const struct GNUNET_CRYPTO_PublicKey *) &pow[1];
443 size += ksize;
445 return size;
446}
447
448
456void
458{
459 GNUNET_free (pc);
460}
461
462
static unsigned int calculate_score(const struct GNUNET_GNSRECORD_PowCalculationHandle *ph)
Calculate the average zeros in the pows.
Definition: gnsrecord_pow.c:94
enum GNUNET_GenericReturnValue check_signature(const struct GNUNET_GNSRECORD_PowP *pow)
enum GNUNET_GenericReturnValue sign_pow_identity(const struct GNUNET_CRYPTO_PrivateKey *key, struct GNUNET_GNSRECORD_PowP *pow)
enum GNUNET_GenericReturnValue sign_pow(const struct GNUNET_CRYPTO_PrivateKey *key, struct GNUNET_GNSRECORD_PowP *pow)
struct GNUNET_GNSRECORD_SignaturePurposePS * GNR_create_signature_message(const struct GNUNET_GNSRECORD_PowP *pow)
Create the revocation metadata to sign for a revocation message.
static int cmp_pow_value(const void *a, const void *b)
Comparison function for quicksort.
static struct GNUNET_CRYPTO_PowSalt salt
Definition: gnsrecord_pow.c:85
enum GNUNET_GenericReturnValue check_signature_identity(const struct GNUNET_GNSRECORD_PowP *pow, const struct GNUNET_CRYPTO_PublicKey *key)
static int ret
Final status code.
Definition: gnunet-arm.c:94
struct GNUNET_HashCode key
The key used in the DHT.
struct GNUNET_CRYPTO_PrivateKey pk
Private key from command line option, or NULL.
static struct GNUNET_TIME_Relative ttl
Current record $TTL to use.
static struct GNUNET_FS_PublishContext * pc
Handle to FS-publishing operation.
static char * rp
Relying party.
static int result
Global testing status.
static struct GNUNET_TIME_Relative epoch_duration
Epoch length.
static unsigned int epochs
-e option.
API that can be used to manipulate GNS record data.
Constants for network protocols.
uint64_t GNUNET_CRYPTO_random_u64(enum GNUNET_CRYPTO_Quality mode, uint64_t max)
Generate a random unsigned 64-bit value.
@ GNUNET_CRYPTO_QUALITY_WEAK
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
size_t GNUNET_GNSRECORD_proof_get_size(const struct GNUNET_GNSRECORD_PowP *pow)
#define POW_COUNT
The proof-of-work narrowing factor.
void GNUNET_GNSRECORD_pow_stop(struct GNUNET_GNSRECORD_PowCalculationHandle *pc)
Stop a PoW calculation.
enum GNUNET_GenericReturnValue GNUNET_GNSRECORD_pow_round(struct GNUNET_GNSRECORD_PowCalculationHandle *pc)
Calculate a key revocation valid for broadcasting for a number of epochs.
void GNUNET_GNSRECORD_pow_init(const struct GNUNET_CRYPTO_PrivateKey *key, struct GNUNET_GNSRECORD_PowP *pow)
Initializes a fresh PoW computation.
struct GNUNET_GNSRECORD_PowCalculationHandle * GNUNET_GNSRECORD_pow_start(struct GNUNET_GNSRECORD_PowP *pow, int epochs, unsigned int difficulty)
Starts a proof-of-work calculation given the pow object as well as target epochs and difficulty.
enum GNUNET_GenericReturnValue GNUNET_GNSRECORD_check_pow(const struct GNUNET_GNSRECORD_PowP *pow, unsigned int difficulty, struct GNUNET_TIME_Relative epoch_duration)
Check if the given proof-of-work is valid.
unsigned int GNUNET_CRYPTO_hash_count_leading_zeros(const struct GNUNET_HashCode *h)
Count the number of leading 0 bits in h.
Definition: crypto_hash.c:177
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_sign_raw_(const struct GNUNET_CRYPTO_PrivateKey *priv, const struct GNUNET_CRYPTO_EccSignaturePurpose *purpose, unsigned char *sig)
Sign a given block.
Definition: crypto_pkey.c:281
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_signature_verify_raw_(uint32_t purpose, const struct GNUNET_CRYPTO_EccSignaturePurpose *validate, const unsigned char *sig, const struct GNUNET_CRYPTO_PublicKey *pub)
Verify a given signature.
Definition: crypto_pkey.c:363
ssize_t GNUNET_CRYPTO_public_key_get_length(const struct GNUNET_CRYPTO_PublicKey *key)
Get the compacted length of a GNUNET_CRYPTO_PublicKey.
Definition: crypto_pkey.c:85
#define GNUNET_log(kind,...)
ssize_t GNUNET_CRYPTO_write_public_key_to_buffer(const struct GNUNET_CRYPTO_PublicKey *key, void *buffer, size_t len)
Writes a GNUNET_CRYPTO_PublicKey to a compact buffer.
Definition: crypto_pkey.c:145
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_key_get_public(const struct GNUNET_CRYPTO_PrivateKey *privkey, struct GNUNET_CRYPTO_PublicKey *key)
Retrieves the public key representation of a private key.
Definition: crypto_pkey.c:619
uint64_t GNUNET_ntohll(uint64_t n)
Convert unsigned 64-bit integer to host byte order.
Definition: common_endian.c:54
ssize_t GNUNET_CRYPTO_signature_get_raw_length_by_type(uint32_t type)
Get the compacted length of a signature by type.
Definition: crypto_pkey.c:225
void GNUNET_CRYPTO_pow_hash(const struct GNUNET_CRYPTO_PowSalt *salt, const void *buf, size_t buf_len, struct GNUNET_HashCode *result)
Calculate the 'proof-of-work' hash (an expensive hash).
Definition: crypto_pow.c:42
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:37
#define GNUNET_ALIGN
gcc-ism to force alignment; we use this to align char-arrays that may then be cast to 'struct's.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
GNUNET_GenericReturnValue
Named constants for return values.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
@ GNUNET_ERROR_TYPE_ERROR
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_remaining(struct GNUNET_TIME_Absolute future)
Given a timestamp in the future, how much time remains until then?
Definition: time.c:405
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:111
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_ntoh(struct GNUNET_TIME_AbsoluteNBO a)
Convert absolute time from network byte order.
Definition: time.c:737
#define GNUNET_TIME_UNIT_WEEKS
One week.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_subtract(struct GNUNET_TIME_Absolute start, struct GNUNET_TIME_Relative duration)
Subtract a given relative duration from the given start time.
Definition: time.c:469
struct GNUNET_TIME_Relative GNUNET_TIME_relative_multiply(struct GNUNET_TIME_Relative rel, unsigned long long factor)
Multiply relative time by a given factor.
Definition: time.c:484
struct GNUNET_TIME_RelativeNBO GNUNET_TIME_relative_hton(struct GNUNET_TIME_Relative a)
Convert relative time to network byte order.
Definition: time.c:618
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_add(struct GNUNET_TIME_Absolute start, struct GNUNET_TIME_Relative duration)
Add a given relative duration to the given start time.
Definition: time.c:450
struct GNUNET_TIME_Relative GNUNET_TIME_relative_divide(struct GNUNET_TIME_Relative rel, unsigned long long factor)
Divide relative time by a given factor.
Definition: time.c:550
struct GNUNET_TIME_AbsoluteNBO GNUNET_TIME_absolute_hton(struct GNUNET_TIME_Absolute a)
Convert absolute time to network byte order.
Definition: time.c:638
#define GNUNET_TIME_UNIT_YEARS
One year (365 days).
static unsigned int size
Size of the "table".
Definition: peer.c:68
#define GNUNET_SIGNATURE_PURPOSE_GNS_REVOCATION
GNS zone key revocation (GNS)
API for proof of work.
Definition: gnsrecord_pow.c:38
unsigned int bits
Corresponding zero bits in hash.
Definition: gnsrecord_pow.c:47
uint64_t pow
PoW nonce.
Definition: gnsrecord_pow.c:42
uint32_t size
How many bytes does this signature sign? (including this purpose header); in network byte order (!...
uint32_t purpose
What does this signature vouch for? This must contain a GNUNET_SIGNATURE_PURPOSE_XXX constant (from g...
Value for a salt for GNUNET_CRYPTO_pow_hash().
A private key for an identity as per LSD0001.
uint32_t type
Type of public key.
An identity key as per LSD0001.
The handle to a PoW calculation.
Definition: gnsrecord_pow.c:56
unsigned int difficulty
The difficulty (leading zeros) to achieve.
Definition: gnsrecord_pow.c:81
unsigned int epochs
Epochs how long the PoW should be valid.
Definition: gnsrecord_pow.c:76
struct BestPow best[POW_COUNT]
Current set of found PoWs.
Definition: gnsrecord_pow.c:60
struct GNUNET_GNSRECORD_PowP * pow
The final PoW result data structure.
Definition: gnsrecord_pow.c:65
uint64_t current_pow
The current nonce to try.
Definition: gnsrecord_pow.c:70
Struct for a proof of work as part of the revocation.
struct GNUNET_TIME_AbsoluteNBO timestamp
The timestamp of the revocation.
uint64_t pow[32]
The PoWs.
The signature object we use for the PoW.
struct GNUNET_TIME_AbsoluteNBO timestamp
The timestamp of the revocation.
struct GNUNET_CRYPTO_EccSignaturePurpose purpose
The signature purpose.
A 512-bit hashcode.
Time for absolute time used by GNUnet, in microseconds and in network byte order.
Time for absolute times used by GNUnet, in microseconds.
Time for relative time used by GNUnet, in microseconds.