Electroneum
ed25519-donna-batchverify.h
Go to the documentation of this file.
1 /*
2  Ed25519 batch verification
3 */
4 
5 #define max_batch_size 64
6 #define heap_batch_size ((max_batch_size * 2) + 1)
7 
8 /* which limb is the 128th bit in? */
9 static const size_t limb128bits = (128 + bignum256modm_bits_per_limb - 1) / bignum256modm_bits_per_limb;
10 
11 typedef size_t heap_index_t;
12 
13 typedef struct batch_heap_t {
14  unsigned char r[heap_batch_size][16]; /* 128 bit random values */
18  size_t size;
19 } batch_heap;
20 
21 /* swap two values in the heap */
22 static void
23 heap_swap(heap_index_t *heap, size_t a, size_t b) {
24  heap_index_t temp;
25  temp = heap[a];
26  heap[a] = heap[b];
27  heap[b] = temp;
28 }
29 
30 /* add the scalar at the end of the list to the heap */
31 static void
32 heap_insert_next(batch_heap *heap) {
33  size_t node = heap->size, parent;
34  heap_index_t *pheap = heap->heap;
35  bignum256modm *scalars = heap->scalars;
36 
37  /* insert at the bottom */
38  pheap[node] = (heap_index_t)node;
39 
40  /* sift node up to its sorted spot */
41  parent = (node - 1) / 2;
42  while (node && lt256_modm_batch(scalars[pheap[parent]], scalars[pheap[node]], bignum256modm_limb_size - 1)) {
43  heap_swap(pheap, parent, node);
44  node = parent;
45  parent = (node - 1) / 2;
46  }
47  heap->size++;
48 }
49 
50 /* update the heap when the root element is updated */
51 static void
52 heap_updated_root(batch_heap *heap, size_t limbsize) {
53  size_t node, parent, childr, childl;
54  heap_index_t *pheap = heap->heap;
55  bignum256modm *scalars = heap->scalars;
56 
57  /* sift root to the bottom */
58  parent = 0;
59  node = 1;
60  childl = 1;
61  childr = 2;
62  while ((childr < heap->size)) {
63  node = lt256_modm_batch(scalars[pheap[childl]], scalars[pheap[childr]], limbsize) ? childr : childl;
64  heap_swap(pheap, parent, node);
65  parent = node;
66  childl = (parent * 2) + 1;
67  childr = childl + 1;
68  }
69 
70  /* sift root back up to its sorted spot */
71  parent = (node - 1) / 2;
72  while (node && lte256_modm_batch(scalars[pheap[parent]], scalars[pheap[node]], limbsize)) {
73  heap_swap(pheap, parent, node);
74  node = parent;
75  parent = (node - 1) / 2;
76  }
77 }
78 
79 /* build the heap with count elements, count must be >= 3 */
80 static void
81 heap_build(batch_heap *heap, size_t count) {
82  heap->heap[0] = 0;
83  heap->size = 0;
84  while (heap->size < count)
85  heap_insert_next(heap);
86 }
87 
88 /* extend the heap to contain new_count elements */
89 static void
90 heap_extend(batch_heap *heap, size_t new_count) {
91  while (heap->size < new_count)
92  heap_insert_next(heap);
93 }
94 
95 /* get the top 2 elements of the heap */
96 static void
97 heap_get_top2(batch_heap *heap, heap_index_t *max1, heap_index_t *max2, size_t limbsize) {
98  heap_index_t h0 = heap->heap[0], h1 = heap->heap[1], h2 = heap->heap[2];
99  if (lt256_modm_batch(heap->scalars[h1], heap->scalars[h2], limbsize))
100  h1 = h2;
101  *max1 = h0;
102  *max2 = h1;
103 }
104 
105 /* */
106 static void
107 ge25519_multi_scalarmult_vartime_final(ge25519 *r, ge25519 *point, bignum256modm scalar) {
109  size_t limb = limb128bits;
111 
112  if (isone256_modm_batch(scalar)) {
113  /* this will happen most of the time after bos-carter */
114  *r = *point;
115  return;
116  } else if (iszero256_modm_batch(scalar)) {
117  /* this will only happen if all scalars == 0 */
118  memset(r, 0, sizeof(*r));
119  r->y[0] = 1;
120  r->z[0] = 1;
121  return;
122  }
123 
124  *r = *point;
125 
126  /* find the limb where first bit is set */
127  while (!scalar[limb])
128  limb--;
129 
130  /* find the first bit */
131  flag = topbit;
132  while ((scalar[limb] & flag) == 0)
133  flag >>= 1;
134 
135  /* exponentiate */
136  for (;;) {
137  ge25519_double(r, r);
138  if (scalar[limb] & flag)
139  ge25519_add(r, r, point);
140 
141  flag >>= 1;
142  if (!flag) {
143  if (!limb--)
144  break;
145  flag = topbit;
146  }
147  }
148 }
149 
150 /* count must be >= 5 */
151 static void
152 ge25519_multi_scalarmult_vartime(ge25519 *r, batch_heap *heap, size_t count) {
153  heap_index_t max1, max2;
154 
155  /* start with the full limb size */
156  size_t limbsize = bignum256modm_limb_size - 1;
157 
158  /* whether the heap has been extended to include the 128 bit scalars */
159  int extended = 0;
160 
161  /* grab an odd number of scalars to build the heap, unknown limb sizes */
162  heap_build(heap, ((count + 1) / 2) | 1);
163 
164  for (;;) {
165  heap_get_top2(heap, &max1, &max2, limbsize);
166 
167  /* only one scalar remaining, we're done */
168  if (iszero256_modm_batch(heap->scalars[max2]))
169  break;
170 
171  /* exhausted another limb? */
172  if (!heap->scalars[max1][limbsize])
173  limbsize -= 1;
174 
175  /* can we extend to the 128 bit scalars? */
176  if (!extended && isatmost128bits256_modm_batch(heap->scalars[max1])) {
177  heap_extend(heap, count);
178  heap_get_top2(heap, &max1, &max2, limbsize);
179  extended = 1;
180  }
181 
182  sub256_modm_batch(heap->scalars[max1], heap->scalars[max1], heap->scalars[max2], limbsize);
183  ge25519_add(&heap->points[max2], &heap->points[max2], &heap->points[max1]);
184  heap_updated_root(heap, limbsize);
185  }
186 
187  ge25519_multi_scalarmult_vartime_final(r, &heap->points[max1], heap->scalars[max1]);
188 }
189 
190 /* not actually used for anything other than testing */
191 unsigned char batch_point_buffer[3][32];
192 
193 static int
194 ge25519_is_neutral_vartime(const ge25519 *p) {
195  static const unsigned char zero[32] = {0};
196  unsigned char point_buffer[3][32];
197  curve25519_contract(point_buffer[0], p->x);
198  curve25519_contract(point_buffer[1], p->y);
199  curve25519_contract(point_buffer[2], p->z);
200  memcpy(batch_point_buffer[1], point_buffer[1], 32);
201  return (memcmp(point_buffer[0], zero, 32) == 0) && (memcmp(point_buffer[1], point_buffer[2], 32) == 0);
202 }
203 
204 int
205 ED25519_FN(ed25519_sign_open_batch) (const unsigned char **m, size_t *mlen, const unsigned char **pk, const unsigned char **RS, size_t num, int *valid) {
206  batch_heap ALIGN(16) batch;
207  ge25519 ALIGN(16) p;
208  bignum256modm *r_scalars;
209  size_t i, batchsize;
210  unsigned char hram[64];
211  int ret = 0;
212 
213  for (i = 0; i < num; i++)
214  valid[i] = 1;
215 
216  while (num > 3) {
217  batchsize = (num > max_batch_size) ? max_batch_size : num;
218 
219  /* generate r (scalars[batchsize+1]..scalars[2*batchsize] */
220  ED25519_FN(ed25519_randombytes_unsafe) (batch.r, batchsize * 16);
221  r_scalars = &batch.scalars[batchsize + 1];
222  for (i = 0; i < batchsize; i++)
223  expand256_modm(r_scalars[i], batch.r[i], 16);
224 
225  /* compute scalars[0] = ((r1s1 + r2s2 + ...)) */
226  for (i = 0; i < batchsize; i++) {
227  expand256_modm(batch.scalars[i], RS[i] + 32, 32);
228  mul256_modm(batch.scalars[i], batch.scalars[i], r_scalars[i]);
229  }
230  for (i = 1; i < batchsize; i++)
231  add256_modm(batch.scalars[0], batch.scalars[0], batch.scalars[i]);
232 
233  /* compute scalars[1]..scalars[batchsize] as r[i]*H(R[i],A[i],m[i]) */
234  for (i = 0; i < batchsize; i++) {
235  ed25519_hram(hram, RS[i], pk[i], m[i], mlen[i]);
236  expand256_modm(batch.scalars[i+1], hram, 64);
237  mul256_modm(batch.scalars[i+1], batch.scalars[i+1], r_scalars[i]);
238  }
239 
240  /* compute points */
241  batch.points[0] = ge25519_basepoint;
242  for (i = 0; i < batchsize; i++)
243  if (!ge25519_unpack_negative_vartime(&batch.points[i+1], pk[i]))
244  goto fallback;
245  for (i = 0; i < batchsize; i++)
246  if (!ge25519_unpack_negative_vartime(&batch.points[batchsize+i+1], RS[i]))
247  goto fallback;
248 
249  ge25519_multi_scalarmult_vartime(&p, &batch, (batchsize * 2) + 1);
250  if (!ge25519_is_neutral_vartime(&p)) {
251  ret |= 2;
252 
253  fallback:
254  for (i = 0; i < batchsize; i++) {
255  valid[i] = ED25519_FN(ed25519_sign_open) (m[i], mlen[i], pk[i], RS[i]) ? 0 : 1;
256  ret |= (valid[i] ^ 1);
257  }
258  }
259 
260  m += batchsize;
261  mlen += batchsize;
262  pk += batchsize;
263  RS += batchsize;
264  num -= batchsize;
265  valid += batchsize;
266  }
267 
268  for (i = 0; i < num; i++) {
269  valid[i] = ED25519_FN(ed25519_sign_open) (m[i], mlen[i], pk[i], RS[i]) ? 0 : 1;
270  ret |= (valid[i] ^ 1);
271  }
272 
273  return ret;
274 }
275 
struct batch_heap_t batch_heap
bignum25519 x
Definition: ed25519-donna.h:82
#define ALIGN(x)
bignum25519 y
Definition: ed25519-donna.h:82
size_t heap_index_t
bignum256modm scalars[heap_batch_size]
bignum25519 z
Definition: ed25519-donna.h:82
unsigned char r[heap_batch_size][16]
#define heap_batch_size
unsigned char batch_point_buffer[3][32]
mdb_size_t count(MDB_cursor *cur)
#define bignum256modm_limb_size
#define bignum256modm_bits_per_limb
heap_index_t heap[heap_batch_size]
void ED25519_FN() ed25519_randombytes_unsafe(void *p, size_t len)
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
#define max_batch_size
void * memcpy(void *a, const void *b, size_t c)
bignum256modm_element_t bignum256modm[9]
key zero()
Definition: rctOps.h:70
int ed25519_sign_open(const unsigned char *m, size_t mlen, const ed25519_public_key pk, const ed25519_signature RS)
ge25519 points[heap_batch_size]
int ED25519_FN() ed25519_sign_open_batch(const unsigned char **m, size_t *mlen, const unsigned char **pk, const unsigned char **RS, size_t num, int *valid)
uint32_t bignum256modm_element_t