Slow Performance...

[acegilz]

I am using the function pub_key = curve.generator.multiply_by_scalar(key) but I am noticing that for high scalars the performance of the function drops significantly.
Example is that if I load the last 100 records of the private key spectrum it takes 30 seconds to load the page on my computer instead of the 50ms compared with the first 100 records of the private key spectrum. Is there anything I can do? If not can you please let me know how can I switch this to an Openssl solution? thanks

[DavidEGrayson]

Hey, it's nice to hear I have users even if they are complaining! You're basically saying it takes 0.3 seconds to generate a public key, which is not surprising to me. I wrote this in the README of the library:

The algorithms have not been optimized for speed, and will probably never be, because that would hinder the goal of helping people understand ECDSA.

If you happen to be using the secp256k1 curve, you can take a look at my Ruby wrapper for libsecp256k1.

I can't really give you much advice on using OpenSSL because I find their interface to be quite confusing. I have posted some Ruby ECDSA code using OpenSSL on StackOverflow which you might find slightly useful.

I'll leave this issue open so that other users can be warned about the slow performance.

[acegilz]

David, first of all let me be clear, I am not complaining, I appreciate your work here, was just trying to find a way of optimise or know if there are optimisation plans. I read in the first place that you are not a cryptographer expert and Im ok with that :)
Im trying to make something similar to directory.io and happens that their last page loads in the same speed as the first one, mine is 1.000x + slower than the first.
After reading something about this and watching this video (starting in minute 15)
https://youtu.be/iB3HcPgm_FI?t=15m4s
Im afraid the problem may be that you may be missing that thing called "double-and-add"

[acegilz]

and by the way, Im following this, I'm afraid it was written by you also:
https://royalforkblog.github.io/2014/07/31/address-gen/

[DavidEGrayson]

I am definitely using the double-and-add technique. Here is the source code for multiply_by_scalar where it is used:

ruby_ecdsa/lib/ecdsa/point.rb

Lines 116 to 127 in 2216043

	def multiply_by_scalar(i)
	raise ArgumentError, 'Scalar is not an integer.' if !i.is_a?(Integer)
	raise ArgumentError, 'Scalar is negative.' if i < 0
	result = group.infinity
	v = self
	while i > 0
	result = result.add_to_point(v) if i.odd?
	v = v.double
	i >>= 1
	end
	result
	end

If you look at the loop you can see that the speed of multiply_by_scalar will be affected by the highest 1 bit in the scalar and also the number of 1 bits. I think that technique is the simplest practical way to do the multiplication, so I couldn't do anything simpler.

[DavidEGrayson]

No, I didn't write that blog post and I'm not sure why you would be afraid of that.

Also, are you exclusively using the secp256k1 curve (which is used by Bitcoin) or are you using other curves as well?

[acegilz]

yes, Im only using the secp256k1 curve to generate the public key of the point like on the tutorial I sent.
Theres nothing to be afraid of if you had wrote it, I meant I suspect/ I think.
I saw your stackoverflow question and was wondering if theres a way to get the x or y points individually. I can get the full coordinate via point.to_bn.to_s but I think I need x and y separated to generate the pubkey

[acegilz]

but I would like to use your gem and understand how we could speed this up. If directory.io can load the last page with 128records in few miliseconds we need to achieve that too

[acegilz]

I dont think so.. open a page somewhere in ifinity with 70 zeros that no one else have ever reached and it happens pretty fast. I dont know if its miliseconds but its less than a second and the more important is that it takes the same time as the first page

[acegilz]

or eventually this is performing ok and they may be calculating in parallel all the requests at the same time, instead of 0.3* number_of_keys. If that could be made it would take just 0.3 secs to load everything. I will try this approach

[DavidEGrayson]

The number of keys you can do in parallel would be the number of CPU cores you have on the server(s) for the request, which would probably be 8 or less unless you're doing something fancy. So I think it would still take at least 0.3 * number_of_keys / 8.

[acegilz]

yes, I have reached that conclusion too, tried Parallel but the end result is exactly the same. I will resign and display 20 per page only

[acegilz]

Unfortunately your ruby wrapper of libsecp256k1 is also not working, what is the best way to put it working, if its even possible atm, that may help as you suggested.. since Im only using that curve

[DavidEGrayson]

Yeah, I was going to suggest that you try using my libsecp256k1-rb wrapper. If my wrapper is not working, and you are installing it correctly, the issue is probably due to breaking changes in the libsecp256k1 library. You might try installing versions of the C library from around April 2015, for example this commit:
bitcoin-core/secp256k1@5c2a4fa

I lost a lot of my interest in that project because the maintainers took this attitude that their library would only support high-level cryptosystems and they would make it hard for anyone who wants to do regular elliptic curve operations like addition or multiplication. Those operations might still be possible in a convoluted way though. Another reason why I have not maintained my wrapper is because the libsecp256k1 people have not released version 1.0.0 yet, so there is no stability in the library's API. If they would start having a stable API, I would be more interested in supporting a wrapper for it.

Of course, it would be best if you could use my wrapper with the latest version of the library. You might need to do a diff of the C library from commit 5c2a4fad1cca052462095e3da9f3a224ed63bd73 to the current HEAD commit to see what has changed since April 2015. The only changes you would need to worry about would be changes in the public header files in the "include" directory of the library. After seeing what changes were made in the C API, it should be possible to make equivalent changes in the Ruby code.