crypto: Use a different library for ed25519/sr25519#6526
crypto: Use a different library for ed25519/sr25519#6526mergify[bot] merged 6 commits intotendermint:masterfrom
Conversation
0ace434 to
cf56be3
Compare
|
This pull request fixes 1 alert when merging cf56be3 into 96db0ae - view on LGTM.com fixed alerts:
|
cf56be3 to
aaa66e0
Compare
|
This pull request fixes 1 alert when merging aaa66e0 into 1f46a4c - view on LGTM.com fixed alerts:
|
|
Very excited for these to land! I feel like it would be nice to not have state machine tx pubkeys have risk of being cached / throwing out validator pubkeys. I don't think this should block merge, as current cosmos chains don't use Ed25519 for user signatures. One way this could be changed is by making a separate CachedVerify and Verify methods, or by making a cached pubkey struct, and have it managed at that layer, instead of managed via a hashmap on the back-end. I'll try to review the cryptography during the week. |
Cosmos-sdk has their own version of ed25519. We now look at the the Tendermint crypto package as solely tendermint related |
|
With the way I integrated support for the cache (lookup done at verification time), the overhead of a miss isn't terrible. The extra computational overhead imposed by the caching layer is confined to synchronization (in the form of two tiny critical sections), book keeping, and allocating the cache entry, everything else is (mostly) work that has to happen to verify anyway. It does also result in slightly more work for the GC since intermediaries that were stack allocated are now heap allocated. In comparison to not using the cache at all, a single-verification will take a penalty of ~3.6 usec on my laptop, which while not ideal isn't what I consider to be the end of the world. If this was to be more optimized, replacing the cache implementation with something tailored to the sort of access patterns that tendermint is expected to see should be simple (eg: have a cache that has a split backing store, with an LRU cache and a separate map, the latter which is manually managed populated on validator set changes). |
|
Oh thats not bad at all for cache miss times, seems good to me then
Ah thanks, didn't know this |
| // cacheSize is the number of public keys that will be cached in | ||
| // an expanded format for repeated signature verification. | ||
| // | ||
| // TODO/perf: Either this should exclude single verification, or be |
There was a problem hiding this comment.
We have an artificial limit of 10.000 validators (https://github.com/tendermint/tendermint/blob/HEAD/types/vote_set.go?q=maxvalset#L18). Should we open an issue with this? I don't think this will come up for a while because there are other limitations that would prevent 4096 validators.
tac0turtle
left a comment
There was a problem hiding this comment.
utACK. Would love another approval before approving
|
Just as a heads up, when I do the final rebase, I would like to bump the import to include oasisprotocol/curve25519-voi#63. The current STROBE implementation that is the same as the one pulled in by the existing merlin import causes most sr25519 operations to do horrific things to the heap, which I solved by writing a "from the specification" implementation of STROBE. Details in the PR. |
3979717 to
8710280
Compare
Codecov Report
@@ Coverage Diff @@
## master #6526 +/- ##
=======================================
Coverage 60.97% 60.98%
=======================================
Files 297 297
Lines 28030 28043 +13
=======================================
+ Hits 17092 17101 +9
+ Misses 9223 9222 -1
- Partials 1715 1720 +5
|
8710280 to
f415212
Compare
|
Ok, I went ahead and rebased the branch, and bumped the import to pickup the STROBE changes. As an added bonus I exposed the merlin implementation (forked from George Tankersley's) that I initially left as an internal package and switched the import there as well. It is API incompatible because ExtractBytes takes a destination buffer, and labels are strings, but I view both changes as improvements since they both make the code nicer to read. |
|
This pull request fixes 1 alert when merging f415212 into d6b4bc2 - view on LGTM.com fixed alerts:
|
|
This pull request has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. |
|
@Yawning sorry for the delay. Could you resolve the conflicts and we can get to merging |
f415212 to
7ee89d4
Compare
|
oh whoops, also a changelog entry. Sorry, just noticed this. Can it mention the breaking changes as well? cc @sunnya97 we are breaking sr25519 in 0.35. Do you need anything from us for straight edge. |
0d778c4 to
7a6e3a0
Compare
This should be done now.
If they do not use |
7a6e3a0 to
1b5655f
Compare
|
This pull request fixes 1 alert when merging 1b5655f into 917180d - view on LGTM.com fixed alerts:
|
|
@Yawning sorry to bother again. Can you update to master again, then the bot should be able to merge this. |
The old benchmark measured: * `sigsCount` GenPrivKey + Sign * `sigsCount` BatchVerifier.Add * `b.N/sigsCount` BatchVerifier.Verify (majority of the runtime). This is all sorts of nonsensical, especially give that there can be a non-trivial amount of overhead in `BatchVerifier.Add`. The rewritten benchmark measures: * `b.N/sigsCount` NewBatchVerifier * `b.N/sigsCount * sigsCount` BatchVerifier.Add * `b.N/sigsCount` BatchVerifier.Verify This is far more sensible as it better reflects the per-signature combined cost of instantiating the batch verifier, adding a signature to the batch, and the verify.
Having to redo quite a bit of computation in the event of a batch failure if the caller is actually interested in which signature failed, is rather sub-optimal. Change the batch verification interface to expose a one-shot batch verify + fallback call, so that sensible libraries can handle this case faster. This commit also leverages the failure information so that validation will only ever call one of `verifyCommitBatch` or `verifyCommitSingle`.
Switch the sr25519 implementation to curve25519-voi for better
performance, and code quality.
Performance comparisions should still be taken with a grain of salt
for the following reasons:
* curve25519-voi's sr25519 support can use more optimization.
* go-schnorrkel cuts corners in places by:
* Not doing delinearization at all when verifying batches
* Not using the secret key nonce at all when signing.
* Not sampling random scalars at all when verifying batches,
unless the import is bumped.
WARNING: This is a breaking change as the original tendermint sr25519
support expands the MiniSecretKey twice, while this implementation
only does it once.
1b5655f to
c5e0263
Compare
|
This pull request fixes 1 alert when merging c5e0263 into 167fa73 - view on LGTM.com fixed alerts:
|
Since I had to fork gtank's to add a transcript RNG, and ended up rewriting the STROBE implementation for my fork, the code might as well use it for every use of merlin as there are a number of improvements, the most notable being a dramatic reduction in the number of allocations done for the various STROBE calls.
c5e0263 to
744d486
Compare
|
This pull request fixes 1 alert when merging 744d486 into 167fa73 - view on LGTM.com fixed alerts:
|
At Oasis we have spend some time writing a new Ed25519/X25519/sr25519 implementation called curve25519-voi. This PR switches the import from ed25519consensus/go-schnorrkel, which should lead to performance gains on most systems.
Summary of changes:
Side issues fixed:
Open design questions/issues: