Jaguar0625 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 07, 2014, 11:49:03 PM |
|
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.
|
NEM - nem.io
|
|
|
|
fmiboy
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 12:43:07 AM |
|
I also started working! ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
Jaguar0625 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 02:09:04 AM |
|
I also started working! ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) I'd be willing to collaborate and split the bounty if you want.
|
NEM - nem.io
|
|
|
Jaguar0625 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 03:43:02 AM |
|
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?
|
NEM - nem.io
|
|
|
BloodyRookie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 07:05:49 AM |
|
That was fast Jaguar. But tell me: with what data type did you replace the Java long type?
|
Nothing Else Matters NEM: NALICE-LGU3IV-Y4DPJK-HYLSSV-YFFWYS-5QPLYE-ZDJJ NXT: 11095639652683007953
|
|
|
tk808
Legendary
Offline
Activity: 1512
Merit: 1124
Invest in your knowledge
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 07:33:47 AM |
|
Bump
Fully support this bounty. Need more people to get involved with Nxt
|
|
|
|
lr127
Newbie
Offline
Activity: 35
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 10:17:01 AM |
|
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 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 01:56:56 PM |
|
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.
|
NEM - nem.io
|
|
|
BloodyRookie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 02:19:52 PM |
|
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?
|
Nothing Else Matters NEM: NALICE-LGU3IV-Y4DPJK-HYLSSV-YFFWYS-5QPLYE-ZDJJ NXT: 11095639652683007953
|
|
|
^[GS]^
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 112
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 08, 2014, 05:51:58 PM |
|
|
|
|
|
Jaguar0625 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2014, 01:08:16 AM |
|
Did you make some timing tests?
I haven't yet, but maybe i should do that first. Good idea.
|
NEM - nem.io
|
|
|
Jaguar0625 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2014, 02:15:35 AM |
|
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 ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) . [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++.
|
NEM - nem.io
|
|
|
hoax
Newbie
Offline
Activity: 36
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2014, 07:42:12 AM |
|
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_jsOn 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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2014, 08:53:09 AM |
|
I agree hoax, 10ms is impossible.
|
Nothing Else Matters NEM: NALICE-LGU3IV-Y4DPJK-HYLSSV-YFFWYS-5QPLYE-ZDJJ NXT: 11095639652683007953
|
|
|
BloodyRookie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2014, 01:21:10 PM Last edit: January 10, 2014, 02:40:25 PM by 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): 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.
|
Nothing Else Matters NEM: NALICE-LGU3IV-Y4DPJK-HYLSSV-YFFWYS-5QPLYE-ZDJJ NXT: 11095639652683007953
|
|
|
Jaguar0625 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2014, 01:24:49 PM |
|
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_jsOn 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.
|
NEM - nem.io
|
|
|
hoax
Newbie
Offline
Activity: 36
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2014, 04:26:41 PM Last edit: January 10, 2014, 05:05:58 PM by 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): 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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2014, 06:50:21 PM |
|
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 Speed test Javascript needs 352.6ms/sign Javascript needs 293.3ms/verify Finished Firefox Version 26.0 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?
|
Nothing Else Matters NEM: NALICE-LGU3IV-Y4DPJK-HYLSSV-YFFWYS-5QPLYE-ZDJJ NXT: 11095639652683007953
|
|
|
Jaguar0625 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 11, 2014, 05:17:06 PM |
|
I just posted a working version of the curve stuff here: https://github.com/Jaguar0625/JavaScriptNrsThere'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 ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) , 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
|
NEM - nem.io
|
|
|
|