[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [tor/master] Use ed25519-donna's batch verification support when applicable.
commit 78fad380cda75b0de86f0d8d2b4d7e55f239f326
Author: Yawning Angel <yawning@xxxxxxxxxxxxxxx>
Date: Wed Aug 12 16:01:28 2015 +0000
Use ed25519-donna's batch verification support when applicable.
The code was always in our Ed25519 wrappers, so enable it when using
the ed25519-donna backend, and deal with the mocking related
crypto_rand silliness.
Implements feature 16533.
---
changes/feature16533 | 4 +
src/common/crypto_ed25519.c | 112 +++++++++++---------
src/ext/ed25519/donna/ed25519-randombytes-custom.h | 2 +-
3 files changed, 69 insertions(+), 49 deletions(-)
diff --git a/changes/feature16533 b/changes/feature16533
new file mode 100644
index 0000000..e9fea94
--- /dev/null
+++ b/changes/feature16533
@@ -0,0 +1,4 @@
+ o Minor features (performance)
+ - Improve the runtime speed of Ed25519 signature verification by using
+ Ed25519-donna's batch verification support when there are a lot of
+ signatures to verify at once. Implements ticket 16533.
diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c
index 3a62932..7e995f4 100644
--- a/src/common/crypto_ed25519.c
+++ b/src/common/crypto_ed25519.c
@@ -37,6 +37,8 @@ typedef struct {
unsigned char *);
int (*sign)(unsigned char *, const unsigned char *, size_t,
const unsigned char *, const unsigned char *);
+ int (*open_batch)(const unsigned char **, size_t *, const unsigned char **,
+ const unsigned char **, size_t, int *);
int (*blind_secret_key)(unsigned char *, const unsigned char *,
const unsigned char *);
@@ -57,6 +59,7 @@ static const ed25519_impl_t impl_ref10 = {
ed25519_ref10_open,
ed25519_ref10_sign,
+ NULL,
ed25519_ref10_blind_secret_key,
ed25519_ref10_blind_public_key,
@@ -74,6 +77,7 @@ static const ed25519_impl_t impl_donna = {
ed25519_donna_open,
ed25519_donna_sign,
+ ed25519_sign_open_batch_donna,
ed25519_donna_blind_secret_key,
ed25519_donna_blind_public_key,
@@ -197,57 +201,69 @@ ed25519_checksig_batch(int *okay_out,
const ed25519_checkable_t *checkable,
int n_checkable)
{
- int res, i;
-
- res = 0;
- for (i = 0; i < n_checkable; ++i) {
- const ed25519_checkable_t *ch = &checkable[i];
- int r = ed25519_checksig(&ch->signature, ch->msg, ch->len, ch->pubkey);
- if (r < 0)
- --res;
- if (okay_out)
- okay_out[i] = (r == 0);
- }
-
-#if 0
- /* This is how we'd do it if we were using ed25519_donna. I'll keep this
- * code around here in case we ever do that. */
- const uint8_t **ms;
- size_t *lens;
- const uint8_t **pks;
- const uint8_t **sigs;
- int *oks;
-
- ms = tor_malloc(sizeof(uint8_t*)*n_checkable);
- lens = tor_malloc(sizeof(size_t)*n_checkable);
- pks = tor_malloc(sizeof(uint8_t*)*n_checkable);
- sigs = tor_malloc(sizeof(uint8_t*)*n_checkable);
- oks = okay_out ? okay_out : tor_malloc(sizeof(int)*n_checkable);
-
- for (i = 0; i < n_checkable; ++i) {
- ms[i] = checkable[i].msg;
- lens[i] = checkable[i].len;
- pks[i] = checkable[i].pubkey->pubkey;
- sigs[i] = checkable[i].signature.sig;
- oks[i] = 0;
- }
-
- ed25519_sign_open_batch_donna_fb(ms, lens, pks, sigs, n_checkable, oks);
+ int i, res;
+ const ed25519_impl_t *impl = get_ed_impl();
- res = 0;
- for (i = 0; i < n_checkable; ++i) {
- /* XXX/yawning: Propagate to okay_out? */
- if (!oks[i])
- --res;
+ if (impl->open_batch == NULL) {
+ /* No batch verification implementation available, fake it by checking the
+ * each signature individually.
+ */
+ res = 0;
+ for (i = 0; i < n_checkable; ++i) {
+ const ed25519_checkable_t *ch = &checkable[i];
+ int r = ed25519_checksig(&ch->signature, ch->msg, ch->len, ch->pubkey);
+ if (r < 0)
+ --res;
+ if (okay_out)
+ okay_out[i] = (r == 0);
+ }
+ } else {
+ /* ed25519-donna style batch verification available.
+ *
+ * Theoretically, this should only be called if n_checkable >= 3, since
+ * that's the threshold where the batch verification actually kicks in,
+ * but the only difference is a few mallocs/frees.
+ */
+ const uint8_t **ms;
+ size_t *lens;
+ const uint8_t **pks;
+ const uint8_t **sigs;
+ int *oks;
+ int all_ok;
+
+ ms = tor_malloc(sizeof(uint8_t*)*n_checkable);
+ lens = tor_malloc(sizeof(size_t)*n_checkable);
+ pks = tor_malloc(sizeof(uint8_t*)*n_checkable);
+ sigs = tor_malloc(sizeof(uint8_t*)*n_checkable);
+ oks = okay_out ? okay_out : tor_malloc(sizeof(int)*n_checkable);
+
+ for (i = 0; i < n_checkable; ++i) {
+ ms[i] = checkable[i].msg;
+ lens[i] = checkable[i].len;
+ pks[i] = checkable[i].pubkey->pubkey;
+ sigs[i] = checkable[i].signature.sig;
+ oks[i] = 0;
+ }
+
+ res = 0;
+ all_ok = impl->open_batch(ms, lens, pks, sigs, n_checkable, oks);
+ for (i = 0; i < n_checkable; ++i) {
+ if (!oks[i])
+ --res;
+ }
+ /* XXX: For now sanity check oks with the return value. Once we have
+ * more confidence in the code, if `all_ok == 0` we can skip iterating
+ * over oks since all the signatures were found to be valid.
+ */
+ tor_assert(((res == 0) && !all_ok) || ((res < 0) && all_ok));
+
+ tor_free(ms);
+ tor_free(lens);
+ tor_free(pks);
+ if (! okay_out)
+ tor_free(oks);
}
- tor_free(ms);
- tor_free(lens);
- tor_free(pks);
- if (! okay_out)
- tor_free(oks);
-#endif
-
return res;
}
diff --git a/src/ext/ed25519/donna/ed25519-randombytes-custom.h b/src/ext/ed25519/donna/ed25519-randombytes-custom.h
index e49368b..3fb0959 100644
--- a/src/ext/ed25519/donna/ed25519-randombytes-custom.h
+++ b/src/ext/ed25519/donna/ed25519-randombytes-custom.h
@@ -13,5 +13,5 @@
static void
ED25519_FN(ed25519_randombytes_unsafe) (void *p, size_t len)
{
- crypto_rand(p, len);
+ crypto_rand_unmocked(p, len);
}
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits