tree 830eb90f8ef0a921c92a1ab69fb6264517382e5a
parent ce1665b825f06ab0cd43f8250e3dca402f82a591
author David Benjamin <davidben@google.com> 1588197440 -0400
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1588871436 +0000

Use a (mostly) constant-time multi-scalar mult for Trust Tokens.

With multi-scalar multiplication, we're stuck pondering the doubling
case. But it's fine for trust tokens, because the points are independent
and the scalars are uniformly generated and not under attacker control.
That means the probability of hitting a double is negligible. (It's
equivalent to accidentally finding the discrete log of two independent
points.)

Before:
Did 306 TrustToken-Exp0-Batch1 generate_key operations in 2000725us (152.9 ops/sec)
Did 1428 TrustToken-Exp0-Batch1 begin_issuance operations in 2080325us (686.4 ops/sec)
Did 105 TrustToken-Exp0-Batch1 issue operations in 2070658us (50.7 ops/sec)
Did 88 TrustToken-Exp0-Batch1 finish_issuance operations in 2023864us (43.5 ops/sec)
Did 12283000 TrustToken-Exp0-Batch1 begin_redemption operations in 2000063us (6141306.5 ops/sec)
Did 315 TrustToken-Exp0-Batch1 redeem operations in 2084451us (151.1 ops/sec)
Did 35000 TrustToken-Exp0-Batch1 finish_redemption operations in 2024388us (17289.2 ops/sec)
Did 315 TrustToken-Exp0-Batch10 generate_key operations in 2045481us (154.0 ops/sec)
Did 138 TrustToken-Exp0-Batch10 begin_issuance operations in 2022158us (68.2 ops/sec)
Did 10 TrustToken-Exp0-Batch10 issue operations in 2148640us (4.7 ops/sec)
Did 8 TrustToken-Exp0-Batch10 finish_issuance operations in 2047452us (3.9 ops/sec)
Did 12167000 TrustToken-Exp0-Batch10 begin_redemption operations in 2000118us (6083141.1 ops/sec)
Did 315 TrustToken-Exp0-Batch10 redeem operations in 2084853us (151.1 ops/sec)
Did 35000 TrustToken-Exp0-Batch10 finish_redemption operations in 2014997us (17369.8 ops/sec)

Did 777 TrustToken-Exp1-Batch1 generate_key operations in 2034967us (381.8 ops/sec)
Did 3612 TrustToken-Exp1-Batch1 begin_issuance operations in 2052618us (1759.7 ops/sec)
Did 264 TrustToken-Exp1-Batch1 issue operations in 2084327us (126.7 ops/sec)
Did 220 TrustToken-Exp1-Batch1 finish_issuance operations in 2024603us (108.7 ops/sec)
Did 12691000 TrustToken-Exp1-Batch1 begin_redemption operations in 2000111us (6345147.8 ops/sec)
Did 777 TrustToken-Exp1-Batch1 redeem operations in 2070867us (375.2 ops/sec)
Did 35000 TrustToken-Exp1-Batch1 finish_redemption operations in 2019118us (17334.3 ops/sec)
Did 798 TrustToken-Exp1-Batch10 generate_key operations in 2090816us (381.7 ops/sec)
Did 357 TrustToken-Exp1-Batch10 begin_issuance operations in 2032751us (175.6 ops/sec)
Did 25 TrustToken-Exp1-Batch10 issue operations in 2046353us (12.2 ops/sec)
Did 21 TrustToken-Exp1-Batch10 finish_issuance operations in 2015579us (10.4 ops/sec)
Did 12695000 TrustToken-Exp1-Batch10 begin_redemption operations in 2000126us (6347100.1 ops/sec)
Did 740 TrustToken-Exp1-Batch10 redeem operations in 2032413us (364.1 ops/sec)
Did 35000 TrustToken-Exp1-Batch10 finish_redemption operations in 2011564us (17399.4 ops/sec)

After:
Did 483 TrustToken-Exp0-Batch1 generate_key operations in 2003131us (241.1 ops/sec) [+57.7%]
Did 1449 TrustToken-Exp0-Batch1 begin_issuance operations in 2089317us (693.5 ops/sec) [+1.0%]
Did 176 TrustToken-Exp0-Batch1 issue operations in 2094210us (84.0 ops/sec) [+65.7%]
Did 147 TrustToken-Exp0-Batch1 finish_issuance operations in 2006750us (73.3 ops/sec) [+68.5%]
Did 12217000 TrustToken-Exp0-Batch1 begin_redemption operations in 2000094us (6108212.9 ops/sec) [-0.5%]
Did 483 TrustToken-Exp0-Batch1 redeem operations in 2058132us (234.7 ops/sec) [+55.3%]
Did 35000 TrustToken-Exp0-Batch1 finish_redemption operations in 2026970us (17267.2 ops/sec) [-0.1%]
Did 504 TrustToken-Exp0-Batch10 generate_key operations in 2086204us (241.6 ops/sec) [+56.9%]
Did 144 TrustToken-Exp0-Batch10 begin_issuance operations in 2084670us (69.1 ops/sec) [+1.2%]
Did 16 TrustToken-Exp0-Batch10 issue operations in 2008793us (8.0 ops/sec) [+71.1%]
Did 14 TrustToken-Exp0-Batch10 finish_issuance operations in 2033577us (6.9 ops/sec) [+76.2%]
Did 12026000 TrustToken-Exp0-Batch10 begin_redemption operations in 2000018us (6012945.9 ops/sec) [-1.2%]
Did 483 TrustToken-Exp0-Batch10 redeem operations in 2056418us (234.9 ops/sec) [+55.5%]
Did 35000 TrustToken-Exp0-Batch10 finish_redemption operations in 2046766us (17100.1 ops/sec) [-1.6%]

Did 1239 TrustToken-Exp1-Batch1 generate_key operations in 2060737us (601.2 ops/sec) [+57.5%]
Did 3675 TrustToken-Exp1-Batch1 begin_issuance operations in 2085293us (1762.3 ops/sec) [+0.1%]
Did 420 TrustToken-Exp1-Batch1 issue operations in 2008121us (209.2 ops/sec) [+65.1%]
Did 378 TrustToken-Exp1-Batch1 finish_issuance operations in 2077226us (182.0 ops/sec) [+67.5%]
Did 12783000 TrustToken-Exp1-Batch1 begin_redemption operations in 2000134us (6391071.8 ops/sec) [+0.7%]
Did 1197 TrustToken-Exp1-Batch1 redeem operations in 2056802us (582.0 ops/sec) [+55.1%]
Did 35000 TrustToken-Exp1-Batch1 finish_redemption operations in 2030955us (17233.3 ops/sec) [-0.6%]
Did 1260 TrustToken-Exp1-Batch10 generate_key operations in 2095507us (601.3 ops/sec) [+57.5%]
Did 357 TrustToken-Exp1-Batch10 begin_issuance operations in 2029693us (175.9 ops/sec) [+0.2%]
Did 42 TrustToken-Exp1-Batch10 issue operations in 2050856us (20.5 ops/sec) [+67.6%]
Did 36 TrustToken-Exp1-Batch10 finish_issuance operations in 2027488us (17.8 ops/sec) [+70.4%]
Did 12140000 TrustToken-Exp1-Batch10 begin_redemption operations in 2000070us (6069787.6 ops/sec) [-4.4%]
Did 1210 TrustToken-Exp1-Batch10 redeem operations in 2079615us (581.8 ops/sec) [+59.8%]
Did 34000 TrustToken-Exp1-Batch10 finish_redemption operations in 2052918us (16561.8 ops/sec) [-4.8%]

Change-Id: Idd51d7e1d18f3b94edc4105e68fd50b5f44d87cd
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/41104
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Steven Valdez <svaldez@google.com>