Bitcoin ABC  0.22.13
P2P Digital Currency
main_impl.h
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2017 Tomas van der Wansem *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5  **********************************************************************/
6 
7 #ifndef _SECP256K1_MODULE_MULTISET_MAIN_
8 #define _SECP256K1_MODULE_MULTISET_MAIN_
9 
10 
12 
13 #include "hash.h"
14 #include "field.h"
15 #include "group.h"
16 
21 static void multiset_from_gej_var(secp256k1_multiset *target, const secp256k1_gej *input) {
22  if (input->infinity) {
23  memset(&target->d, 0, sizeof(target->d));
24  } else {
25  secp256k1_fe_get_b32(target->d, &input->x);
26  secp256k1_fe_get_b32(target->d+32, &input->y);
27  secp256k1_fe_get_b32(target->d+64, &input->z);
28  }
29 }
30 
34 static void gej_from_multiset_var(secp256k1_gej *target, const secp256k1_multiset *input) {
35  secp256k1_fe_set_b32(&target->x, input->d);
36  secp256k1_fe_set_b32(&target->y, input->d+32);
37  secp256k1_fe_set_b32(&target->z, input->d+64);
38 
39  target->infinity = secp256k1_fe_is_zero(&target->z) ? 1 : 0;
40 }
41 
50 static void ge_from_data_var(secp256k1_ge *target, const unsigned char *input, size_t inputLen, int inverse) {
51  secp256k1_sha256 hasher;
52  unsigned char buffer[8+32];
53  unsigned char trial[32];
54  uint64_t prefix;
55 
56  /* Hash to buffer, leaving space for 8-byte prefix */
58  secp256k1_sha256_write(&hasher, input, inputLen);
59  secp256k1_sha256_finalize(&hasher, buffer+8);
60 
61  /* Loop through trials, with 50% success per loop
62  * We can assume it ends within 2^64. */
63  for(prefix=0; 1; prefix++)
64  {
65  secp256k1_fe x;
66 
67  /* Set prefix in little-endian */
68  buffer[0] = prefix & 0xFF;
69  buffer[1] = (prefix>>8) & 0xFF;
70  buffer[2] = (prefix>>16) & 0xFF;
71  buffer[3] = (prefix>>24) & 0xFF;
72  buffer[4] = (prefix>>32) & 0xFF;
73  buffer[5] = (prefix>>40) & 0xFF;
74  buffer[6] = (prefix>>48) & 0xFF;
75  buffer[7] = (prefix>>56) & 0xFF;
76 
77  /* Hash to trial */
79  secp256k1_sha256_write(&hasher, buffer, sizeof(buffer));
80  secp256k1_sha256_finalize(&hasher, trial);
81 
82  if (!secp256k1_fe_set_b32(&x, trial)) {
83  continue;
84  }
85 
86  /* We let y is even be the element and odd be its inverse */
87  if (!secp256k1_ge_set_xo_var(target, &x, inverse)) {
88  continue;
89  }
90 
93  break;
94  }
95 }
96 
98 static int multiset_add_remove(const secp256k1_context* ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen, int remove) {
99  secp256k1_ge newelm;
100  secp256k1_gej source, target;
101 
102  VERIFY_CHECK(ctx != NULL);
103  ARG_CHECK(multiset != NULL);
104  ARG_CHECK(input != NULL);
105 
106  gej_from_multiset_var(&source, multiset);
107  ge_from_data_var(&newelm, input, inputLen, remove);
108 
109  /*
110  * The `target` group element needs to be initialized.
111  * If the result of the addition is infinity, the field elements won't be
112  * set and the `secp256k1_fe_normalize` calls below will branch on
113  * uninitialized data.
114  */
116  secp256k1_gej_add_ge_var(&target, &source, &newelm, NULL);
117 
118  secp256k1_fe_normalize(&target.x);
119  secp256k1_fe_normalize(&target.y);
120  secp256k1_fe_normalize(&target.z);
121  multiset_from_gej_var(multiset, &target);
122 
123  return 1;
124 }
125 
127 int secp256k1_multiset_add(const secp256k1_context* ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen) {
128  return multiset_add_remove(ctx, multiset, input, inputLen, 0);
129 }
130 
132 int secp256k1_multiset_remove(const secp256k1_context* ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen) {
133  return multiset_add_remove(ctx, multiset, input, inputLen, 1);
134 }
135 
138  secp256k1_gej gej_multiset, gej_input, gej_result;
139 
140  VERIFY_CHECK(ctx != NULL);
141  ARG_CHECK(multiset != NULL);
142  ARG_CHECK(input != NULL);
143 
144  gej_from_multiset_var(&gej_multiset, multiset);
145  gej_from_multiset_var(&gej_input, input);
146 
147  /*
148  * The `gej_result` group element needs to be initialized.
149  * If the result of the addition is infinity, the field elements won't be
150  * set and the `secp256k1_fe_normalize` calls below will branch on
151  * uninitialized data.
152  */
153  secp256k1_gej_set_infinity(&gej_result);
154  secp256k1_gej_add_var(&gej_result, &gej_multiset, &gej_input, NULL);
155 
156  secp256k1_fe_normalize(&gej_result.x);
157  secp256k1_fe_normalize(&gej_result.y);
158  secp256k1_fe_normalize(&gej_result.z);
159  multiset_from_gej_var(multiset, &gej_result);
160 
161  return 1;
162 }
163 
165 int secp256k1_multiset_finalize(const secp256k1_context* ctx, unsigned char *resultHash, const secp256k1_multiset *multiset) {
166  secp256k1_sha256 hasher;
167  unsigned char buffer[64];
168  secp256k1_gej gej;
169  secp256k1_ge ge;
170 
171  VERIFY_CHECK(ctx != NULL);
172  ARG_CHECK(resultHash != NULL);
173  ARG_CHECK(multiset != NULL);
174 
175  gej_from_multiset_var(&gej, multiset);
176 
177  if (gej.infinity) {
178  /* empty set is encoded as zeros */
179  memset(resultHash, 0x00, 32);
180  return 1;
181  }
182 
183  /* we must normalize to affine first */
184  secp256k1_ge_set_gej(&ge, &gej);
187  secp256k1_fe_get_b32(buffer, &ge.x);
188  secp256k1_fe_get_b32(buffer+32, &ge.y);
189 
191  secp256k1_sha256_write(&hasher, buffer, sizeof(buffer));
192  secp256k1_sha256_finalize(&hasher, resultHash);
193 
194  return 1;
195 }
196 
202 
203  VERIFY_CHECK(ctx != NULL);
204 
205  multiset_from_gej_var(multiset, &inf);
206 
207  return 1;
208 }
209 
210 #endif /* _SECP256K1_MODULE_MULTISET_MAIN_ */
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Check whether a group element is the point at infinity.
#define VERIFY_CHECK(cond)
Definition: util.h:68
static void gej_from_multiset_var(secp256k1_gej *target, const secp256k1_multiset *input)
Converts a multiset to group element (Jacobian) Infinite uses special value, z = 0.
Definition: main_impl.h:34
static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr)
Set r equal to the sum of a and b.
static int secp256k1_fe_is_zero(const secp256k1_fe *a)
Verify whether a field element is zero.
secp256k1_fe x
Definition: group.h:25
int secp256k1_multiset_add(const secp256k1_context *ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen)
Adds a data element to the multiset.
Definition: main_impl.h:127
secp256k1_context * ctx
const char * prefix
Definition: rest.cpp:754
Opaque multiset; this is actually a group element.
#define SECP256K1_GEJ_CONST_INFINITY
Definition: group.h:32
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:24
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Set a group element (jacobian) equal to the point at infinity.
static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr)
Set r equal to the sum of a and b (with b given in affine coordinates).
unsigned char d[96]
int secp256k1_multiset_combine(const secp256k1_context *ctx, secp256k1_multiset *multiset, const secp256k1_multiset *input)
Adds input multiset to multiset.
Definition: main_impl.h:137
static int multiset_add_remove(const secp256k1_context *ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen, int remove)
Adds or removes a data element.
Definition: main_impl.h:98
const char * source
Definition: rpcconsole.cpp:56
int secp256k1_multiset_remove(const secp256k1_context *ctx, secp256k1_multiset *multiset, const unsigned char *input, size_t inputLen)
Removes a data element from the multiset.
Definition: main_impl.h:132
#define ARG_CHECK(cond)
Definition: secp256k1.c:29
static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a)
Set a group element equal to another which is given in jacobian coordinates.
int infinity
Definition: group.h:28
int secp256k1_multiset_finalize(const secp256k1_context *ctx, unsigned char *resultHash, const secp256k1_multiset *multiset)
Hash the multiset into resultHash.
Definition: main_impl.h:165
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
secp256k1_fe x
Definition: group.h:15
static void multiset_from_gej_var(secp256k1_multiset *target, const secp256k1_gej *input)
Converts a group element (Jacobian) to a multiset.
Definition: main_impl.h:21
static void ge_from_data_var(secp256k1_ge *target, const unsigned char *input, size_t inputLen, int inverse)
Converts a data element to a group element (affine)
Definition: main_impl.h:50
static void secp256k1_sha256_write(secp256k1_sha256 *hash, const unsigned char *data, size_t size)
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd)
Set a group element (affine) equal to the point with the given X coordinate, and given oddness for Y...
static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a)
Set a field element equal to 32-byte big endian value.
int secp256k1_multiset_init(const secp256k1_context *ctx, secp256k1_multiset *multiset)
Inits the multiset with the constant for empty data, represented by the Jacobian GE infinite...
Definition: main_impl.h:200
secp256k1_fe z
Definition: group.h:27
static void secp256k1_fe_normalize(secp256k1_fe *r)
Field element module.
static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a)
Convert a field element to a 32-byte big endian value.
static void secp256k1_sha256_initialize(secp256k1_sha256 *hash)
secp256k1_fe y
Definition: group.h:26
static int secp256k1_ge_is_valid_var(const secp256k1_ge *a)
Check whether a group element is valid (i.e., on the curve).
secp256k1_fe y
Definition: group.h:16
static void secp256k1_sha256_finalize(secp256k1_sha256 *hash, unsigned char *out32)