[ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures - page 4.

BloodyRookie

hero member

Activity: 687

Merit: 500

Quote from: hoax on January 14, 2014, 05:56:35 AM

Sources of what?

https://code.google.com/p/gvl/source/browse/crypt/curve25519.cpp?r=3c26171fd2d914484f03b7b63ca2065fa03a7aa3

Quote from: hoax on January 14, 2014, 05:56:35 AM

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?

hoax

newbie

Activity: 36

Merit: 0

Quote from: BloodyRookie on January 13, 2014, 10:28:45 AM

hoax, did you test the original cpp code? I tried but I got funny results Sad

Sources of what?

Quote from: Jaguar0625 on January 13, 2014, 10:14:09 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.

Jaguar0625

sr. member

Activity: 299

Merit: 250

Quote from: Jaguar0625 on January 13, 2014, 06:46:26 PM

Quote from: BloodyRookie on January 13, 2014, 10:24:35 AM

Using the Long class is too slow, Jaguar, take a look at 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.

Jaguar0625

sr. member

Activity: 299

Merit: 250

Quote from: BloodyRookie on January 13, 2014, 10:24:35 AM

Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js, 16 bit arithmetic is used there. Doesn't have sign and verify though.

Thanks for the link!

gimre

legendary

Activity: 866

Merit: 1002

my Curve (not Crypto) times:
I was measuring time with console.time, console.timeEnd, not sure how precise it is...

x	chrom-opera 19	chrome 31	ff 26
public Without s	~35ms	~46ms	~68ms
public with s	~70ms	~70ms	~60ms
sign	~1ms	~1ms	~1ms
verify	~57ms	~72ms	~178ms

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) Cheesy

2493ms, 2602ms, 3ms, 4264ms

BloodyRookie

hero member

Activity: 687

Merit: 500

hoax, did you test the original cpp code? I tried but I got funny results Sad

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.

BloodyRookie

hero member

Activity: 687

Merit: 500

Using the Long class is too slow, Jaguar, take a look at https://github.com/rev22/curve255js, 16 bit arithmetic is used there. Doesn't have sign and verify though.

Jaguar0625

sr. member

Activity: 299

Merit: 250

Just an update from the other thread in case you missed it:

Quote from: Come-from-Beyond on January 13, 2014, 02:16:32 AM

Quote from: Jaguar0625 on January 12, 2014, 06:06:57 PM

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.

Quote from: Jaguar0625 on January 12, 2014, 06:06:57 PM

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.

Jaguar0625

sr. member

Activity: 299

Merit: 250

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?

Jaguar0625

sr. member

Activity: 299

Merit: 250

Quote from: hoax on January 12, 2014, 07:15:36 AM

Quote from: Jaguar0625 on January 11, 2014, 01:17:06 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?

hoax

newbie

Activity: 36

Merit: 0

Quote from: BloodyRookie on January 13, 2014, 05:16:09 AM

Quote from: hoax on January 13, 2014, 03: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!";
var secretPhrase = "secretPhrase";

Interesting...
And the original Java code also returns false on verifying Cheesy

Yep, just noticed that. Damn, i spend a lot of time for fixing wrong testcase!

Ok, but your verify also return false for:

Quote from: Come-from-Beyond on January 06, 2014, 10:50:25 AM

Quote from: wesleyh on January 06, 2014, 10:41:55 AM

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.

BloodyRookie

hero member

Activity: 687

Merit: 500

Quote from: hoax on January 13, 2014, 03: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!";
var secretPhrase = "secretPhrase";

Interesting...
And the original Java code also returns false on verifying Cheesy

hoax

newbie

Activity: 36

Merit: 0

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!";
var secretPhrase = "secretPhrase";

BloodyRookie

hero member

Activity: 687

Merit: 500

Here is my implementation. Didn't optimize yet.

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.

hoax

newbie

Activity: 36

Merit: 0

Quote from: BloodyRookie on January 10, 2014, 02:50:21 PM

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

Can you test my latest update?

Quote from: Jaguar0625 on January 11, 2014, 01:17:06 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.

gimre

legendary

Activity: 866

Merit: 1002

My approach is a bit different, and I don't even have sign+verify yet. Will share results once I have some.

Jaguar0625

sr. member

Activity: 299

Merit: 250

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

BloodyRookie

hero member

Activity: 687

Merit: 500

Quote from: hoax on January 10, 2014, 12:26:41 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
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?

hoax

newbie

Activity: 36

Merit: 0

Quote from: BloodyRookie on January 10, 2014, 09:21:10 AM

@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.

Jaguar0625

sr. member

Activity: 299

Merit: 250

Quote from: hoax on January 10, 2014, 03: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

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.

Topic: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures - page 4. (Read 8406 times)