|
Title: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on 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. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 07, 2014, 11:55:20 PM 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! Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: fmiboy on January 08, 2014, 12:43:07 AM I also started working! :)
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 08, 2014, 02:09:04 AM I also started working! :) I'd be willing to collaborate and split the bounty if you want. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on 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? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on 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?
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: tk808 on January 08, 2014, 07:33:47 AM Bump
Fully support this bounty. Need more people to get involved with Nxt Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: lr127 on 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. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on 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. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on 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? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: ^[GS]^ on January 08, 2014, 05:51:58 PM 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. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on 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. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on 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 :). [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++. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 10, 2014, 07:42:12 AM I don't believe that
Quote 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 Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 10, 2014, 08:53:09 AM I agree hoax, 10ms is impossible.
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 10, 2014, 01:21:10 PM @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 Edit: Updated speed test result due to bug. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 10, 2014, 01:24:49 PM I don't believe that Quote 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. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 10, 2014, 04:26:41 PM @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 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. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on 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 Code: Speed test Firefox Version 26.0 Code: Speed test I think the speed could be improved a lot but it will take time. What are you replacing the int10 and Long with? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 11, 2014, 05:17:06 PM 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 Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 12, 2014, 10:21:22 AM My approach is a bit different, and I don't even have sign+verify yet. Will share results once I have some.
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 12, 2014, 11:15:36 AM I think the speed could be improved a lot but it will take time. Can you test my latest update?What are you replacing the int10 and Long with? I just posted a working version of the curve stuff here: https://github.com/Jaguar0625/JavaScriptNrs I'm afraid that using Long class for all math isn't good. I think that better use Long only in mul and sqr functions. Then we can remove all unnecessary optimizations from Long class. But fastest approach must forgive about Long class and use only JS-friendly math. I have working(and fast, more faster than latest version on github) sign function, but can't solve problems with verify, so continue my work. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 13, 2014, 07:24:38 AM Here is my implementation. Didn't optimize yet.
https://github.com/BloodyRookie/nxtCrypto/tree/master (https://github.com/BloodyRookie/nxtCrypto/tree/master) Core duo 2.4GHz: 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: 94956bf3de7cfdedb2562a0eff698fed7f3e54bbf4476fbb23a192ddea04040f68efa5d03c3f9eb ec4109401b50433f1df267299d8b1ad2c485046c45e6b38da Verifying... verify returned: true Speed test Javascript needs 35.7ms/getPublicKey Javascript needs 77.1ms/sign Javascript needs 73ms/verify Finished Edit: hoax, I test your latest version, it needs about 120ms/sign and 90ms/verify. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 13, 2014, 07:53:38 AM Yep, i also mean approach from https://github.com/kosta/confidential-publishing/blob/master/js/curve25519/curve25519.js :)
And your version of verifyalso return false for Code: var message = "Hello World!"; Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 13, 2014, 09:16:09 AM Yep, i also mean approach from https://github.com/kosta/confidential-publishing/blob/master/js/curve25519/curve25519.js :) And your version of verifyalso return false for Code: var message = "Hello World!"; Interesting... And the original Java code also returns false on verifying :D Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 13, 2014, 09:18:22 AM Yep, i also mean approach from https://github.com/kosta/confidential-publishing/blob/master/js/curve25519/curve25519.js :) And your version of verifyalso return false for Code: var message = "Hello World!"; Interesting... And the original Java code also returns false on verifying :D Ok, but your verify also return false for: 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. So, let's examine this approach further. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 13, 2014, 02:14:09 PM I just posted a working version of the curve stuff here: https://github.com/Jaguar0625/JavaScriptNrs I'm afraid that using Long class for all math isn't good. I think that better use Long only in mul and sqr functions. Then we can remove all unnecessary optimizations from Long class. But fastest approach must forgive about Long class and use only JS-friendly math. I have working(and fast, more faster than latest version on github) sign function, but can't solve problems with verify, so continue my work. I have a few ideas about how to optimize the long class, but I need to spend time with a profiler first and see where all the time is being spent. Has anyone tried this already? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 13, 2014, 02:15:03 PM So, right now, I think there are three working implementations: hoax, me, BloodyRookie. Am I missing anyone? Has anyone compared the performance of all three?
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 13, 2014, 02:21:39 PM Just an update from the other thread in case you missed it:
Regarding the performance criteria, are you referring to curve25519 or crypto operations per second? And, if you're looking for running this in the browser, what browsers are you looking at supporting? Considering curve25519's heavy reliance on 64-bit arithmetic (which JavaScript doesn't support natively), it will probably be a lot slower than you're expected (especially running outside of v8). Do you have test data you are using for a benchmark? Crypto operations. Chrome. No test data, I'll take an ordinary payment transaction. Also, are you giving the whole bounty to the fastest solution, or going to split it among functionally correct submissions? The fastest submission will get (a part of) the bounty. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 13, 2014, 02:24:35 PM Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js (https://github.com/rev22/curve255js), 16 bit arithmetic is used there. Doesn't have sign and verify though.
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 13, 2014, 02:28:45 PM hoax, did you test the original cpp code? I tried but I got funny results :(
BTW: I think the bounty should be split among those who have a fast working version. Giving all nxt to one guy because his code is 1% faster doesn't make sense to me. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 13, 2014, 10:32:10 PM my Curve (not Crypto) times:
I was measuring time with console.time, console.timeEnd, not sure how precise it is...
I still got some console.logs, which might tell why FF (last result) looks so bad. seems to me FF have pretty bad console handling. Also it's not finished yet... P.S. I'm amazed new opera has slightly better times > chrome, I thought they both use V8 edit out of curiosity, I've checked old opera (12.15) :D 2493ms, 2602ms, 3ms, 4264ms Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 13, 2014, 10:46:26 PM Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js (https://github.com/rev22/curve255js), 16 bit arithmetic is used there. Doesn't have sign and verify though. Thanks for the link! Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 14, 2014, 01:47:46 AM Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js (https://github.com/rev22/curve255js), 16 bit arithmetic is used there. Doesn't have sign and verify though. Thanks for the link! Just as an FYI, I swapped my getPublicKey implementation for the one from the link you provided and I saw an improvement of ~15% (without any additional optimizations) with the test message you're using. But I am not seeing as great an improvement with the test set I generated. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 14, 2014, 09:56:35 AM hoax, did you test the original cpp code? I tried but I got funny results :( Sources of what?I have a few ideas about how to optimize the long class, but I need to spend time with a profiler first and see where all the time is being spent. Has anyone tried this already? Look at my repo. I removed from Long all codepathsthat useless for long10 implementation. Also added multiplySmall, which faster when we multiple int64 by 1,2,4,9,19,38,76. Maybe we can optimize further but with loss of readability or insignificantly :) As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 14, 2014, 10:47:58 AM Sources of what? https://code.google.com/p/gvl/source/browse/crypt/curve25519.cpp?r=3c26171fd2d914484f03b7b63ca2065fa03a7aa3 As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work. The only thing not working is the is_negative function, right? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 14, 2014, 12:08:58 PM Sources of what? https://code.google.com/p/gvl/source/browse/crypt/curve25519.cpp?r=3c26171fd2d914484f03b7b63ca2065fa03a7aa3 And about "helloworld" false result: CfB said that this is normal behavior :O As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work. The only thing not working is the is_negative function, right? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 14, 2014, 03:55:17 PM My js ported directly from this, not from Nxt sources :) ok, but did you actually test the c++ program? The only thing not working is the is_negative function, right? Not only, as i can see.What else do you think is not working? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 14, 2014, 09:49:45 PM My code is finally working uff, took me a lot to figure out how to do that is_negative crap in my representation.
My current times: Code: priv in: 210, 196, 255, 153, 6, 54, 138, 84, 232, 24, 222, 198, 233, 178, 192, 61, 46, 110, 249, 92, 37, 250, 62, 206, 16, 71, 242, 136, 153, 234, 194, 151, Code: priv in: 212, 215, 120, 183, 50, 2, 38, 73, 6, 176, 105, 222, 132, 202, 18, 161, 165, 186, 129, 60, 222, 69, 25, 30, 201, 220, 102, 201, 246, 118, 112, 127, Is that fast or slow? (above I'm doing equivalent of java code): Code: Curve25519.keygen(pub,sigPriv,priv); // generate pub and sigPriv // time1 Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 14, 2014, 11:09:26 PM hoax, did you test the original cpp code? I tried but I got funny results :( I wouldn't be shocked if there is a bug in the Java code. Cfb's expectation that ~25% of signatures can't be verified is surprising to me. Also, the fact that the C++ code is using uint8 types whereas the JavaScript code is using longs for essentially the same thing is suspicious. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 14, 2014, 11:21:53 PM I think 25% is probably overestimate, but curve edit (I mean curve25519 ofc) as a function is not surjective, so one should expect that...
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 15, 2014, 01:24:50 AM hoax, did you test the original cpp code? I tried but I got funny results :( I wouldn't be shocked if there is a bug in the Java code. Cfb's expectation that ~25% of signatures can't be verified is surprising to me. Also, the fact that the C++ code is using uint8 types whereas the JavaScript code is using longs for essentially the same thing is suspicious. Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 15, 2014, 01:37:25 AM I put together a small test corpus in my repo https://github.com/Jaguar0625/JavaScriptNrs that you guys can use to test your implementations for correctness. (Basically black box testing where i validate the inputs and outputs are the same as the original Java code):
Just run the following after swapping in your implementation: Code: node test.js Not sure if this helps but i thought i'd share :). Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 15, 2014, 01:52:11 AM I have a few ideas about how to optimize the long class, but I need to spend time with a profiler first and see where all the time is being spent. Has anyone tried this already? Look at my repo. I removed from Long all codepathsthat useless for long10 implementation. Also added multiplySmall, which faster when we multiple int64 by 1,2,4,9,19,38,76. Maybe we can optimize further but with loss of readability or insignificantly :) As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work. I see. It looks like you removed the long 10 class and optimized the google long class. Are you getting good enough performance or thinking of scrapping the Long class altogether? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 06:20:04 AM My code is finally working uff, took me a lot to figure out how to do that is_negative crap in my representation. So what's the logic behind is_negative? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 15, 2014, 07:46:21 AM My code is finally working uff, took me a lot to figure out how to do that is_negative crap in my representation. So what's the logic behind is_negative? I've actually partially* answered to that in code flaws thread: Can you please ask that guy what the reasoning behind the strange is_negative(long10 x) function is? It's kind of hard to understand. I'm also interested in this. a) why there is is_overflow at all... (I thought it'd be simpler to have element of long10 have always reduced mod q....) b) the second part is magic, as there shouldn't be something like "negative", so I assume job of that xor is to split values into two groups... (why?) (edit: added is_negative, snippet) Code: /* checks if x is "negative", requires reduced input */ I might shed some more light upon that, but probably not today (UTC) edit: Oh, P.S. I'm getting quite terrible results from node.js - last time I checked they were 10 times worse than ones from the browser... I would appreciate if anyone would share his (her?) results from within the browser Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Come-from-Beyond on January 15, 2014, 09:03:00 AM Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod. It's a normal behavior, not a bug, don't waste too much time on that. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 15, 2014, 09:09:12 AM My js ported directly from this, not from Nxt sources :) ok, but did you actually test the c++ program? I'm getting quite terrible results from node.js - last time I checked they were 10 times worse than ones from the browser... I would appreciate if anyone would share his (her?) results from within the browser CPU - core i5 2.6ghz Chrome 32beta: crypto_sign - 64ms, crypto_verify - 32ms Node.js: crypto_sign - 88ms, crypto_verify - 44ms Firefox 26: crypto_sign - 80ms, crypto_verify - 60ms Results depends on "how you're measure" them :) Sometimes browser can be meditative and run JS slowly and i get worst results(~ x2 slower). And if i call this functions in 100x cycle then avg time is better(36ms, 29ms on chrome). Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 15, 2014, 10:05:30 AM Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod. It's a normal behavior, not a bug, don't waste too much time on that. That depends on algo. In case of Nxt's EC-KCDSA "k" value is picked not choosen randomly, So if you feed it with the same data, sig should be te same... (k is calculated from 1360-1365, that's Y in NXT code https://bitbucket.org/JeanLucPicard/nxt-public/src/4073c21098076d3469b3f74d49e73ffabe3a2001/Nxt.java?at=master#cl-1360 and it's based on "sig priv key" (s based on user's pub key) and message ) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Come-from-Beyond on January 15, 2014, 10:07:32 AM Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod. It's a normal behavior, not a bug, don't waste too much time on that. That depends on algo. In case of Nxt's EC-KCDSA "k" value is picked not choosen randomly, So if you feed it with the same data, sig should be te same... (k is calculated from 1360-1365, that's Y in NXT code https://bitbucket.org/JeanLucPicard/nxt-public/src/4073c21098076d3469b3f74d49e73ffabe3a2001/Nxt.java?at=master#cl-1360 and it's based on "sig priv key" (s based on user's pub key) and message ) Stick to NRS code. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 10:34:00 AM Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod. It's a normal behavior, not a bug, don't waste too much time on that. What? Same message, same secret phrase ==> same signature. Or I am missing something? One question: are timing attacks an issue for the client software (i.e. the javascript software)? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Come-from-Beyond on January 15, 2014, 10:36:55 AM Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod. It's a normal behavior, not a bug, don't waste too much time on that. What? Same message, same secret phrase ==> same signature. Or I am missing something? U r, let's go back to the topic. Don't pay attention to this part now. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 10:39:09 AM I might shed some more light upon that, but probably not today (UTC) I think I figured it out. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 10:56:57 AM I would appreciate if anyone would share his (her?) results from within the browser I am not speed testing the bare Curve25519 functions but the getPublicKey, sign and verify function from Cryto class (converted to javascript). On my i7 950 3.07GHz (you need to tell us what cpu u r using) using firefox v26 I get: Code: Speed test Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 15, 2014, 01:07:01 PM 2.4 GHz Intel Core i5
Chrome (initial approach, which was a straight port of the Java code using the Long class): Code: Javascript needs 167.5ms/getPublicKey Although, switching the getPublicKey function to the one from the native JS implementation dropped getPublicKey to 9.8ms [for some reason this change had a much larger impact in the browser than in node; I'm not sure why because they're both using V8]. I think @BloodyRookie has the right idea :). Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 15, 2014, 01:08:19 PM Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod. It's a normal behavior, not a bug, don't waste too much time on that. What? Same message, same secret phrase ==> same signature. Or I am missing something? U r, let's go back to the topic. Don't pay attention to this part now. Since the Java code is producing deterministic signatures, I'm assuming you want the JavaScript port to have the same behavior? If not, that would potentially open up other areas for optimization. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 15, 2014, 01:22:19 PM I would appreciate if anyone would share his (her?) results from within the browser I am not speed testing the bare Curve25519 functions but the getPublicKey, sign and verify function from Cryto class (converted to javascript). On my i7 950 3.07GHz (you need to tell us what cpu u r using) using firefox v26 I get: Code: Speed test glad you figured, I also went <100ms for whole sig+verify, will post details later (the thing is I operate on data in bit different format, so I'll have to preprocess it first... and that'll have penalty for sure) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 01:28:08 PM @gimre: On what kind of cpu r u testing, gimre?
@Jaguar0625: 9.8ms/getPublicKey with javascript? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 15, 2014, 01:39:24 PM What else do you think is not working? I was wrong :) But also confused by "It's a normal behavior"(c)CfBTitle: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 15, 2014, 01:51:48 PM @Jaguar0625: 9.8ms/getPublicKey with javascript? Yes, but don't worry, I ran your code too and it was faster :). These are the results for your code on my machine (i am using the test js/html from your repo): Code: Javascript needs 5.5ms/getPublicKey I suspect you're seeing slower numbers on your machine because you're testing in FireFox. AFAIK, Chrome has a faster JavaScript interpreter. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 15, 2014, 02:12:06 PM And for completeness, these are the numbers I see for hoax's implementation:
Code: Javascript needs 16.6ms/getPublicKey It looks like I have a lot of catching up to do :/. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Come-from-Beyond on January 15, 2014, 03:12:14 PM Since the Java code is producing deterministic signatures, I'm assuming you want the JavaScript port to have the same behavior? If not, that would potentially open up other areas for optimization. I want the same behavior. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Come-from-Beyond on January 15, 2014, 03:13:22 PM Javascript needs 5.5ms/getPublicKey Javascript needs 12ms/sign Javascript needs 9.5ms/verify So, who said that 10ms is impossible? :) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 15, 2014, 03:22:19 PM Javascript needs 5.5ms/getPublicKey Javascript needs 12ms/sign Javascript needs 9.5ms/verify So, who said that 10ms is impossible? :) But in overall, yes, i was too pessimistic :) On my pc(core i5 2.67ghz) i now get 7.5ms(avg) for sign and 5.5ms(avg) for verify in Chrome :) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 15, 2014, 03:36:23 PM Thanks to Jaguar0625 for tests. I just runned my latest version(on github) on them, all tests are passed :)
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 03:40:43 PM Hmmm...chrome is indeed faster but even on a 3GHz maschine I don't get your results:
Code: Javascript needs 12.22ms/getPublicKey What am I doing wrong? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 15, 2014, 03:45:25 PM @gimre: On what kind of cpu r u testing, gimre? laptop, i7, 2.2G@Jaguar0625: 9.8ms/getPublicKey with javascript? Yes, but don't worry, I ran your code too and it was faster :). These are the results for your code on my machine (i am using the test js/html from your repo): Code: Javascript needs 5.5ms/getPublicKey I suspect you're seeing slower numbers on your machine because you're testing in FireFox. AFAIK, Chrome has a faster JavaScript interpreter. WOW, these look incredible! Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 03:50:37 PM @hoax: I don't think your version of is_negative is compatible with the java version, or is it?
Code: /* checks if x is "negative", requires reduced input */ Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 15, 2014, 03:59:44 PM Hmmm...chrome is indeed faster but even on a 3GHz maschine I don't get your results: Code: Javascript needs 12.22ms/getPublicKey What am I doing wrong? Hmmm...chrome is indeed faster but even on a 3GHz maschine I don't get your results: Code: Javascript needs 12.22ms/getPublicKey What am I doing wrong? Just runned in ff26: 22ms(avg)/sign 16ms(avg)/verify. As i can see it depends on loop count(more loops - better time) and browser wish(sometimes it do everything slower(extensions, synchronization, etc??). We should test everything in same environment :) I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations). @hoax: I don't think your version of is_negative is compatible with the java version, or is it? Code: /* checks if x is "negative", requires reduced input */ This check for overflow. Tested on Jaguar0625 tests(generated from Java) and get 100/100 passed, so... You can correct me if i'm wrong. And you can remove in your sources second argument from Code: SHA256_write(m, m.length); Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 15, 2014, 04:51:15 PM @hoax: I don't think your version of is_negative is compatible with the java version, or is it? Code: /* checks if x is "negative", requires reduced input */ This check for overflow. Tested on Jaguar0625 tests(generated from Java) and get 100/100 passed, so... You can correct me if i'm wrong. Your code: is_negative(1) returns 0 (hopefully the & operator gets executed before >= operator). Java code: is_negative(1) returns 1. Since u use your is_negativ for both siging and verifying, it works. But if u sign with your code and try to verify with the java code, it should fail sometimes (didn't test that but it really should fail). Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 15, 2014, 06:00:14 PM My new results, I forgot to turn off miner when doing previous tests ;)
chrom-opera: Code: curveSelfTest : ok chrome: Code: curveSelfTest : ok I don't think I'll get to anything better than that... Also on what data do you operate inside functions? As I find requirement, to take input as "hex strings" quite ugly. P.S. My sign looks more or less like this: Code: function crypto_sign(privKey, messageHash) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 15, 2014, 06:02:34 PM Hmmm.....you didn't understand what I was trying to say, so here we go again. You're right. Thank you. I've fixed it and will look at this closer again :)Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 16, 2014, 12:06:51 AM We should test everything in same environment :) I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations). Here are the latest numbers for hoax's code: Code: Javascript needs 3.6ms/getPublicKey Nice job! Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 16, 2014, 06:15:09 AM We should test everything in same environment :) I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations). Here are the latest numbers for hoax's code: Code: Javascript needs 3.6ms/getPublicKey Nice job! Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 16, 2014, 05:24:09 PM Something told me, to do tests on Jaguar's test set, and glad I did, cause I've found small bug in my implementation.
Here's my code, https://github.com/gimer/curve25519nxt inside testing.js there are some simple tests along with Jaguar's tests. It's based on objects rather than modules. I doubt it'll beat hoax implementation though. Here are some numbers, from my machine. Code: testCurveKeygen: 764.000ms Oh, PS, also api is a bit strange, I'd find it more covenient if everything passed to JS would be wrapped in typed arrays already. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 17, 2014, 02:24:23 PM We should test everything in same environment :) I would be appreciated if Jaguar0625 measure time for my latest version(which use rev22 math with some optimizations). Here are the latest numbers for hoax's code: Code: Javascript needs 3.6ms/getPublicKey Nice job! Could I kindly ask you to run test also on my code? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 17, 2014, 11:24:33 PM Could I kindly ask you to run test also on my code? Are the inputs and outputs of all of your functions byte arrays? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 17, 2014, 11:27:45 PM I was finally able to get rid of all the Long math and replace it from fast math functions from curve255.js and got much better results :):
Code: Javascript needs 6.9ms/getPublicKey Still not as good as hoax's, but a lot better than my earlier numbers. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 18, 2014, 10:27:35 AM Could I kindly ask you to run test also on my code? Are the inputs and outputs of all of your functions byte arrays? almost, was it specified anywhere how input output should look like? take a look at github, there's description of input output there. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Come-from-Beyond on January 18, 2014, 10:29:17 AM almost, was it specified anywhere how input output should look like? Quote - Input/output values must be strings like "8302504e4e57c6c65335289879c6915a273d3aae7bd086058e403fcd2bc18341" Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 20, 2014, 01:06:03 AM Could I kindly ask you to run test also on my code? Are the inputs and outputs of all of your functions byte arrays? almost, was it specified anywhere how input output should look like? take a look at github, there's description of input output there. Sorry, had a busy weekend. I just ran your code tonight: Code: Public Key 6.904ms Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 20, 2014, 04:32:13 AM Finally finished my implementation: https://github.com/Jaguar0625/JavaScriptNrs.
Here are the numbers from my machine: Code: Public Key 3.027ms The code I am using to run the timing tests is also in the repo under the browser_test subdirectory in case anyone wants to verify the numbers :). Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 20, 2014, 10:02:58 AM So now we have 3 implementations that are essentially equal.
If one of these implementations win, wouldn't it be fair to split? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 20, 2014, 10:31:10 AM Can I get some consolation prize? ::)
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 20, 2014, 10:52:06 AM I am willing to split among those who invested a lot of time as long as the other guys are willing to do the same ;).
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 20, 2014, 12:45:29 PM who invested a lot of time ...heh, much more than I expected + wanted ;) but it was fun Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: hoax on January 20, 2014, 03:11:00 PM I am willing to split among those who invested a lot of time as long as the other guys are willing to do the same ;). I think it is fair.Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 20, 2014, 07:47:13 PM I am willing to split among those who invested a lot of time as long as the other guys are willing to do the same ;). I think it is fair.What about you, Jaguar? Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 21, 2014, 06:48:44 PM I am willing to split among those who invested a lot of time as long as the other guys are willing to do the same ;). I think it is fair.What about you, Jaguar? As for me, I don't think I deserve equal share, and if you don't mind splitting with me, I suggest 10/30/30/30 Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 21, 2014, 07:04:51 PM I am willing to split among those who invested a lot of time as long as the other guys are willing to do the same ;). I think it is fair.What about you, Jaguar? As for me, I don't think I deserve equal share, and if you don't mind splitting with me, I suggest 10/30/30/30 That's ok for me too ;) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: Jaguar0625 on January 22, 2014, 12:36:09 AM I agreed to the split in the main thread. Good job to all!
@ NRS crypto algo bounty contestants: Guys, u were talking about splitting the bounty to 4 parts. Did u come to a decision? If u r agree to split the bounty then I won't spend time on speedtests. Well I wouldn't mind. We all spend a lot of time coding. I guess hoax and gimre don't mind too, but I haven't heard Jaguar's opinion yet. I agree that a 25% split of the bounty is fair. We all spent a good amount of time on this. Of course, I also wouldn't be opposed to one of the founders tipping the fastest implementation ;). You can send my next to the address in my signature. Thanks! Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on January 22, 2014, 06:54:27 AM I guess these are proper acct numbers:
Jaguar: 14544444716689899421 hoax: 5637350814069846194 BloodyRookie: 11095639652683007953 me: 6669070404060812420 Jaguar, could you run one last batch of tests to confirm that your one is the fastest one? I should have some time during weekend, I think we all could take one more look at it, and try push it to the limits :) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: BloodyRookie on January 22, 2014, 08:45:44 AM I think Jaguars version is fast in chrome. When testing with firefox, my version ist very fast.
Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: freigeist on January 22, 2014, 11:24:20 AM I think Jaguars version is fast in chrome. When testing with firefox, my version ist very fast. Hello. If this is the case maybe then each one of you should write in the code or in the release notes on which platform the code has best performance. For example a developer could implement all your scripts in his code and load dynamically a script depending on the user platform to achieve best performances. Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: gimre on March 11, 2014, 08:01:03 AM I think Jaguars version is fast in chrome. When testing with firefox, my version ist very fast. Hello. If this is the case maybe then each one of you should write in the code or in the release notes on which platform the code has best performance. For example a developer could implement all your scripts in his code and load dynamically a script depending on the user platform to achieve best performances. I think web wallet on http://nxtra.org/nxt-client/ will include JS implementation. (BloodyRookie's I guess) Title: Re: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures Post by: San1ty on June 03, 2014, 07:44:36 PM Anyone have any tips on getting the accountid from a public key?
static long getId(byte[] publicKey) throws Exception { byte[] publicKeyHash = MessageDigest.getInstance("SHA-256").digest(publicKey); BigInteger bigInteger = new BigInteger(1, new byte[] {publicKeyHash[7], publicKeyHash[6], publicKeyHash[5], publicKeyHash[4], publicKeyHash[3], publicKeyHash[2], publicKeyHash[1], publicKeyHash[0]}); return bigInteger.longValue(); } I found this snippet in the source code but trying to replicate in JS gives me no results. Any help? |