[ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures

[Jaguar0625]

Creating a new thread for this bounty.

Bounty announcement

100'000 NXT will be paid for working JavaScript code that signs and verifies signatures using NRS algo.

- The licence must allow to use the code in any application
- Sign/verify speed must be not lower than 100 signatures per second on a 1 GHz CPU (1 core)
- All the code must be in a single non-obfuscated well-formatted .js file
- Input/output values must be strings like "8302504e4e57c6c65335289879c6915a273d3aae7bd086058e403fcd2bc18341"

The bounty is valid till the 20th of January, 2014 12:00:00 UTC. The complete code must be published in this thread.

[Jaguar0625]

I am going to work on converting the Curve25519 tonight.
I also created a repository where I'll be pushing changes if anyone else wants to help out: https://github.com/Jaguar0625/JavaScriptNrs.

Thanks!

[fmiboy]

I also started working!

[Jaguar0625]

I also started working!

I'd be willing to collaborate and split the bounty if you want.

[Jaguar0625]

Just to give an update, I went through the Curve25519 class and converted it to valid JavaScript. I tried to minimize the changes (since Java and JavaScript are both C based, there is a lot of commonality between their syntax). So, at this point, the JavaScript isn't optimal, but it should be pretty easy to compare against the source. I think it is important to keep the code similar until we get rid of all bugs and then we can optimize it, if necessary.

I think the next step would be to come up with a small test runner so we can gain some confidence that the port works. My idea would be some basic black box testing where we capture a bunch of inputs and outputs from the known good (Java) implementation and then replay them against the JavaScript implementation. Any differences will pinpoint bugs in the port.

Any other thoughts?

[BloodyRookie]

That was fast Jaguar. But tell me: with what data type did you replace the Java long type?

[tk808]

Bump

Fully support this bounty. Need more people to get involved with Nxt

[lr127]

Jaguar0625
I ran js.core & java.core for a same hash key - the result is different.
You can use java ScriptEngine for mix java & javascript code for testing.

[Jaguar0625]

That was fast Jaguar. But tell me: with what data type did you replace the Java long type?

I'm still thinking through that. Right now, I've found two possibilities.
- http://jsfromhell.com/classes/bignumber - nice because it would allow us to get rid of the long10 stuff.
- http://docs.closure-library.googlecode.com/git/class_goog_math_Long.html - will allow the code to stay more similar to the original code

I'm leaning towards the second until everything is working and then maybe switching to the first because it would allow us to remove some of the extra long stuff, but I still need to evaluate how intrusive the changes are. If they're equally intrusive, it might make sense sense to just use the first one from the beginning.

Jaguar0625
I ran js.core & java.core for a same hash key - the result is different.
You can use java ScriptEngine for mix java & javascript code for testing.

Thanks. I suspect there are still a few bugs that need to be investigated.

To be a little more transparent with my process, when I'm doing a bulk conversion of code from one language to another, I like to do it in phases:
(1) Do a bulk conversion so that there the code doesn't have any compiler errors in the new language
(1a) Build a test harness (it should almost certainly fail at this point)
(2) Make more significant changes (e.g. convert JavaScript to use correctly operate on 64-bit values) in a phased approach (so that each major change is a separate check-in)
(3) Bug fix / diff source and target code a lot
(4) If necessary, improve performance refactor.

Right now all I've done is phase 1. There's still a good amount of work remaining, but at least a decent groundwork has been laid.

[BloodyRookie]

That was fast Jaguar. But tell me: with what data type did you replace the Java long type?

I'm still thinking through that. Right now, I've found two possibilities.
- http://jsfromhell.com/classes/bignumber - nice because it would allow us to get rid of the long10 stuff.
- http://docs.closure-library.googlecode.com/git/class_goog_math_Long.html - will allow the code to stay more similar to the original code

I'm leaning towards the second until everything is working and then maybe switching to the first because it would allow us to remove some of the extra long stuff, but I still need to evaluate how intrusive the changes are. If they're equally intrusive, it might make sense sense to just use the first one from the beginning.

Well I am experimenting with the second possibility, but the Long10 build from Long is very slow. Function recip takes 10ms to compute.
Did you make some timing tests?

[^[GS]^]

Can you give some input and expected output?

Verification:
public key = "7c3ff12215636a7b246dea25d5e446a91fa59a9150c6ed50d8126ee86a648b68"
message = "0000a9d63800a0057c3ff12215636a7b246dea25d5e446a91fa59a9150c6ed50d8126ee86a648b6 87e2fad81dbf18f2da0860100640000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000"
signature = "4f0626ccd4edebb17e9d06e928b5b4e944aa7ef88a111081919794a3e265c206f9d9b0ce42a8d2e 7f6d902a172159bcd39dcaab8468373258fccea9e5d2ed319"
output = true

(The data from http://localhost:7874/nxt?requestType=getTransaction&transaction=14039483471941095190 and http://localhost:7874/nxt?requestType=getTransactionBytes&transaction=14039483471941095190)

Signing:

Similar, but take values from a transaction signed by ur account. This requires to reveal a secret phrase.

[Jaguar0625]

Did you make some timing tests?

I haven't yet, but maybe i should do that first. Good idea.

[Jaguar0625]

Did you make some timing tests?

I haven't yet, but maybe i should do that first. Good idea.

I committed a small test runner tonight that does 10000 adds, multiplies, subtracts, and divides with BigNumber, Long, and Int (as a baseline). These are the results I'm seeing on my dev machine:
(you can run it with this commandline: node longperftest.js)
488.002ms BigNumber
5.058ms Long
0.330ms Int

I think this effectively rules out BigNumber . [Looking at its implementation, it's slow because it supports arbitrarily large numbers by storing them as strings and then converting them to digits to perform operations on them. In addition, it doesn't support the bitwise operations that we need]

I also looked at the goog.math.Long implementation and it seems quite optimized. It is storing the high and low 32-bits in two 32-bit integers and then uses integer math directly. I don't see a lot of potential for optimizations. Unfortunately, JavaScript only natively supports 64-bit floating point numbers, so it's 64-bit integer math will never be as fast as languages that support 64-bit longs natively.

Regarding the slowness of recip, I'm doubtful that we will be able to get it much faster. If the intent is for having this code run in the browser, I think we're stuck. JavaScript servers (like node.js) would probably implement this logic in C/C++.

[hoax]

I don't believe that

Sign/verify speed must be not lower than 100 signatures per second on a 1 GHz CPU (1 core)

can be achieved.

I have working implementation of nrs: https://github.com/moadib/nxt_crypto_js

On my PC(core i5 2.6ghz) algo took approx 200ms for one signature on Google V8(chrome, nodejs).

I'm also tried compile c++ code to js with emscripten and it give approx 2x faster unreadable file. This is not enough too.

P.S. also i think that other(which not have Google V8) browsers will show worse results

[BloodyRookie]

I agree hoax, 10ms is impossible.

[BloodyRookie]

@hoax: I tried your code. It works. But somehow firefox has timing problems. Running crypto_sign needs about 630ms which is slow but not horrible. But crypto_verify needs more than 11 seconds ?!
Can you tell me why firefox is having trouble?

To compare with my version (i7 CPU 950 3.07GHz):

Code:

Test
message: This is a secret message that needs to be signed
secret phrase: This is my very secret phrase
public key: 698168d8669c9310d68101dfcc974ed4ef454692da6f028f68114db5fdcc4f6a
Signing...
Signature: 94956bf3de7cfdedb2562a0eff698fed7f3e54bbf4476fbb23a192ddea04040f68efa5d03c3f9ebec4109401b50433f1df267299d8b1ad2c485046c45e6b38da
Verifying...
verify returned: true
Speed test
Javascript needs 174.5ms/sign
Javascript needs 145.5ms/verify
Finished

Edit: Updated speed test result due to bug.

[Jaguar0625]

I don't believe that

Sign/verify speed must be not lower than 100 signatures per second on a 1 GHz CPU (1 core)

can be achieved.

I have working implementation of nrs: https://github.com/moadib/nxt_crypto_js

On my PC(core i5 2.6ghz) algo took approx 200ms for one signature on Google V8(chrome, nodejs).

I'm also tried compile c++ code to js with emscripten and it give approx 2x faster unreadable file. This is not enough too.

P.S. also i think that other(which not have Google V8) browsers will show worse results

I've seen found Curve::sign to be relatively fast, but i agree that it seems unlikely we'll be able to get Curve::verify to be fast.

[hoax]

@hoax: I tried your code. It works. But somehow firefox has timing problems. Running crypto_sign needs about 630ms which is slow but not horrible. But crypto_verify needs more than 11 seconds ?!
Can you tell me why firefox is having trouble?

To compare with my version (i7 CPU 950 3.07GHz):

Code:

Test
message: This is a secret message that needs to be signed
secret phrase: This is my very secret phrase
public key: 698168d8669c9310d68101dfcc974ed4ef454692da6f028f68114db5fdcc4f6a
Signing...
Signature: 94956bf3de7cfdedb2562a0eff698fed7f3e54bbf4476fbb23a192ddea04040f68efa5d03c3f9ebec4109401b50433f1df267299d8b1ad2c485046c45e6b38da
Verifying...
verify returned: true
Speed test
Javascript needs 174.5ms/sign
Javascript needs 145.5ms/verify
Finished

Edit: Updated speed test result due to bug.

Interesting, don't test on Firefox before. I believe that new version, which not use int10&Long can achieve your speed. I'll write here when update sources.

[BloodyRookie]

Interesting, don't test on Firefox before. I believe that new version, which not use int10&Long can achieve your speed. I'll write here when update sources.

On my computers, firefox is even faster than chrome. Testing on my Notebook (Core Duo 2.4GHz):

Chrome Version 31.0.1650.63 m

Code:

Speed test
Javascript needs 352.6ms/sign
Javascript needs 293.3ms/verify
Finished

Firefox Version 26.0

Code:

Speed test
Javascript needs 282.1ms/sign
Javascript needs 228.3ms/verify
Finished

I think the speed could be improved a lot but it will take time.
What are you replacing the int10 and Long with?

[Jaguar0625]

I just posted a working version of the curve stuff here: https://github.com/Jaguar0625/JavaScriptNrs

There's also some java code to generate (pseudo) random test data for sign, keygen, and verify.

The tests both verify correctness and calculate average time.

Numbers on my local machine are completely meaningless , but here's what i see with node.js:

> node test.js
Running test cases from ./data/signtest.dat
test cases: 20 (lines: 81)
0 failures / 20 passed
TOT: 2.196ms
AVG: 0.110ms

Running test cases from ./data/keygentest.dat
test cases: 100 (lines: 401)
0 failures / 100 passed
TOT: 8685.554ms
AVG: 86.856ms

Running test cases from ./data/verifytest.dat
test cases: 100 (lines: 401)
0 failures / 100 passed
TOT: 14027.910ms
AVG: 140.279ms