Replace ed25519 with libsodium

[johansten]

ed25519 hasn't been updated in years and is lagging behind what's otherwise available:
https://github.com/future-tense/ed25519-dalek#benchmarks

ed25519 might have been a good choice in terms of a smaller binary size, but this only used for node anyway, so the extra bloat doesn't matter as much.

I'd suggest libsodium/sodium-native, since that's an actual npm package, and since signature verification isn't that big of a deal; I'd be surprised if most people even know it's in the SDK.

I'd also suggest using the native bindings for key generation, instead of only using it for signing and verification.

Can do the work, just want a go/no-go

[orbitlens]

Agree that ed25519 package is outdated and often causes of installation errors.

However, I think it's worth to consider using the elliptic package instead. It's a pure JS implementation, so it doesn't require pre-built binaries. On my tests it gave me up to 50x performance increase in some cases comparing to the default tweetnacl implementation.

@johansten Could you please add this package to your benchmark code? To my mind, it's better to use pure JS lib instead of binary wrappers if the performance is roughly the same. The browser code will work faster too in this case.

Edit: Just checked bundles generated by Webpack. Apparently, Webpack always includes the elliptic package to the browser bundle in order to support Node crypto dependencies. So elliptic is already included in all my bundles.

[morleyzhi]

The crypto library will be removed in the next release, so that should also remove elliptic. (But I didn't test to make sure.)

I think replacing ed25519 is a good idea. I don't have any opinion about a replacement library, so I'm happy with any defensible position you take @johansten.

[orbitlens]

@morleyzhi

The crypto library will be removed in the next release

How? tweetnacl itself has a reference to Node's crypto module. Are you going to replace tweetnacl with something else?

[morleyzhi]

Searching their repo, it's only imported in tests, am I looking at the right thing?

https://github.com/dchest/tweetnacl-js/search?l=JavaScript&q=crypto&type=

[orbitlens]

@morleyzhi
Github shows only the first search occurrence for each file. Please check line 2366 in nacl-fast.js.

[morleyzhi]

Ah so it does. The browser bundle won't include that import though.

[johansten]

I've checked out elliptic a bit and it is promising; it gave me a 5-6x speedup. The problem I have with it now is that it adds ~200 kB to the bundle size. I've done some "light" manual tree-shaking, and gotten it down to around half of that, with more to go.

[orbitlens]

@johansten tweetnacl static size is about 61KB (11KB gzipped), while full elliptic package included by default in Webpack builds is ~109KB (28KB gzipped). Please check, maybe you have two different versions of elliptic in the output bundle?

[johansten]

@orbitlens I can't find elliptic in the js-stellar-base output bundle. There's the whole crc package, all of lodash, and a full sha.js. There's a serious need of tree shaking. I'm not sure how that'd work without restructuring the whole build process though.

[orbitlens]

@johansten I'm using Webpack to build application bundles. It has built-in tree shaking and works fine with ES5+. However, by default the bundle includes elliptic, bn.js, and some other packages used by Webpack to emulate Node's crypto module.

example.js

const {Keypair} = require('stellar-base')
Keypair.random()

example-webpack-config.js

const path = require('path'),
    webpack = require('webpack')

const settings = {
    mode: 'production',
    entry: {
        'bundle': [path.join(__dirname, './app.js')]
    },
    output: {
        path: path.join(__dirname, './distr/'),
        filename: '[name].js',
        publicPath: '/distr/'
    },
    module: {
        rules: [
            {
                test: /\.js?$/,
                loader: 'babel-loader',
                exclude: /node_modules/
            }
        ]
    }
}
module.exports = settings

It's possible to turn off Webpack's crypto emulation, but most developers don't dig too deep into the configuration settings. Therefore, we can safely assume that almost 100% of Stellar-powered web apps built with Webpack have elliptic package bundled (for example, StellarPort, StellarX, and many others).

[johansten]

@orbitlens

You sir are the winner! Found one piece of elliptic hiding in the Stargazer webpack bundle.
So I guess we shouldn't worry too much about bringing it into the sdk by default then.

[morleyzhi]

I just updated stellar-base and stellar-sdk to remove node builtins from the bundle. Unless my methodology was wrong, I was used your webpack config with Webpack Bundle Analyzer, and it no longer includes the crypto polyfill or elliptic. It does still include tweetnacl.

[tomquisel]

What's the best change to make based on this?

[johansten]

@tomquisel

Dependencies are always going to be a nightmare. I just noticed I have three different versions of stellar-base, because of dependencies I have that in turn haven't updated their deps. If you don't explicitly work on it, you most likely will depend on something that depends on crypto, and that means you already have elliptic. If it was up to me, I'd replace tweetnacl with elliptic, and then investigate how we can make the SDK as a whole more suitable for tree shaking.

[orbitlens]

Many thanks to @morleyzhi for removing dependencies like URI and other unneeded polyfills, I was about to make a PR myself with some of these changes. SDK runtime is getting lighter, and it's fantastic.

Agree with @johansten. It seems like elliptic is a lot faster in most cases. It also gives about 40x performance increase on new keypair generation. However, it relies on bn.js package, which is actually an alternative to bignumber.js. So it makes sense only if we are going to replace bignumber.js with bn.js (which gives a slight performance bonus as well). Otherwise, the result bundle size will be larger than the current bundle by @morleyzhi.

One more thing to consider, BigInt has made it to Stage 3. It is already supported in NodeJS 10.8.0+, recent Chrome and Opera. It may be wise to wait a few months and see which library is going to adopt this new standard, some packages (like BigInteger.js lib) have already upgraded. Native BigInt will be much faster than any third-party implementation. Long.js dependency can be also replaced by the new implementation, so we'll get an even smaller bundle.

A few more thoughts regarding the structure of the dependencies that will allow to squeeze out 200-300 KB more from the bundle:

• Most of lodash APIs can be replaced by native ES2015 functions, so we don't really need this dependency.
• StrKey encoding uses only one CRC algorithm, but all of them (more than 10 as far as I remember) are included in the resulted bundle. We can easily get rid of them by importing or copy-pasting a single required function.
• The same with sha.js

I'm volunteering to implement those proposals if we all agree on that.
(and I will probably move this to separate issues)

[tomquisel]

Gotcha, it sounds like we should wait to see how the BitInt situation shakes out before deciding on elliptic. I like your three ideas of lodash replacement (assuming we don't lose much readability, I think keyBy for example is more readable than reduce), CRC, and sha.js. @morleyzhi do those all sound like good ideas?

[morleyzhi]

I like those ideas to reduce the bundle size. I don't think reduce -> keyBy is a big enough upgrade to warrant the file size increase.

As far as tree-shaking is concerned: I worked on this a few weeks ago but came to the conclusion that it requires a lot of complicated changes, and I'm not positive the output will be worth it. Especially if we can just write Lodash out of the packages. Here's the rough todo list for that, which has to be done to all 3 libs:

• Upgrade webpack to 3 or 4
• Upgrade webpack's peer dependencies to the latest versions
• Rewrite all module.exports use to use imports / exports instead. All instances have to be rewritten for tree-shaking to work
• Figure out which files have side effects and which are side-effect-free. Mark the former.
• Modify all the unit and integration test setups to import the rewritten library the correct way such that tests continue to pass

You have to very precisely manage your codebase to get tree-shaking working, and I wasn't confident at the time that I could do that in a reasonable amount of time.

[johansten]

@orbitlens

Bignumber.js and BN aren't entirely equal, are they? BN is primarily for large integers and operations on them, Bignumber is for exact math w/ decimals.

Edit: I was going to sleep, but now I have to port my all-js reference implementation of ed25519 to BigInt :)

[orbitlens]

@morleyzhi It's true, tree shaking requires a lot of consideration, and we need to carefully refactor the code to support it. As I said, I can help you with all other things. This task list of yours doesn't seem to me like it requires a particularly complex refactor. Yes, a lot of work, but it's quite standard. Therefore, if we all agree that it should be done, I can start to work on this tomorrow.

@johansten Strictly speaking, most operations require only integer arithmetic, decimals are required only in price approximation (div operator). Can't say for sure without testing, but I have a few ideas how to implement this feature without loosing precision.

[johansten]

@orbitlens
True, we could just decide to work in 1e7 precision, and scale up/down in strings.

My ed25519-bigint looks to be about 5-6 times faster than elliptic, so big thanks for that hint. Definitely more testing needed, but I'd say it would be worth it to do a stripped elliptic with all the crud removed, and use that as a fallback for when people don't have bigint. Never mind the ramblings of a sleep deprived madman.

[morleyzhi]

This was closed here: stellar/js-stellar-base@bd6c268