Low latency multipliers and cryptographic puzzles | Hacker News Reader

Low latency multipliers and cryptographic puzzles

blog.janestreet.com

81 pointsjsnell20 comments

Interesting that the estimated date for solving the puzzle was based on Moore's law. There's an implicit assumption that nobody will factor the modulus before then.

RSA is as solid as ever.

>There were no magic tricks in his approach. It was just that Rivest’s original estimate was off by a factor of ten. While we don’t have 10GHz CPUs sitting in our desktops (mainly due to thermal issues), CPU and multi-core architecture has advanced dramatically.

Ummm, how exactly does multicore help solving this puzzle? It was designed specifically to be un-parallelizable.

IIRC, while they couldn't cheat the need for squarings, each squaring/multiplication itself has some internal parallelism which can be exploited, and GMP does some of that, and the Cryptophage team took that even further in conjunction with their exotic hardware. So the serial step could be accelerated more than Rivest predicted.

Sure, but that still has nothing to do with multiple CPU cores.

This was a good read about an area of computing I’ve only heard about in passing (specifically crypto miner design). But it was definitely over my head as someone who has never had to work with FPGAs.

Can anyone suggest a good online course, textbook, or article to get started understanding and working (via some simulation software so it’s cheap!) on FPGAs?

See https://github.com/aws/aws-fpga/blob/master/README.md#gettin...

FPGA for fun at https://www.fpga4fun.com/

I wonder how competitive GPU's would be with FPGA's on this type of problem.

FPGA's have the advantage that the circuit architecture can be designed specifically for the algorithm but as far as I know they have much lower gate density and clock speeds compared to top of the line GPU's.

In the case of bitcoin mining as far as I know GPU's passed the hat directly to ASIC's. I never heard that FPGA's were competitive for that.

GPUs do have much better gate density, and better clock speeds, but the problem here is so specialized that the improved raw speeds of a GPU don't remotely make up for its inflexibility.

Additionally, GPUs are optimized for throughput. CPUs are optimized for latency, I haven't seen the benchmarks but I'd blindly bet that a modern CPU could get lower latency on this problem than a modern GPU.

The blog post here solved the entire problem in just 3 clock cycles. I don't know how the numbers come back on a GPU or CPU, but the vast majority of the optimizations here are completely impossible on a standard instruction set, and would instead require doing dozens to hundreds of clock cycles. Going from 65 MHz to 5 GHz isn't going to make up for all the shortcuts you lose out on.

> In the case of bitcoin mining as far as I know GPU's passed the hat directly to ASIC's. I never heard that FPGA's were competitive for that.

They were, before the ASICs came. CPU -> GPU -> FPGA -> ASIC. A classic story of specialization.

Ehhh not really. There was some FPGA mining that happened in Bitcoin but it was always niche rather than at-scale.

FPGAs are a lot better than GPUs from the perspective of energy efficiency, but the FPGAs themselves are very expensive to purchase, and are a lot more specialized than GPUs. ASICs showed up before FGPAs ever really took off, and even if ASICs hadn't showed up it's not clear that FGPAs would have been superior on a total-cost basis to GPUs except in niche circumstances.

> are a lot more specialized than GPUs.

What do you mean by "more specialized" ? FPGA's can implement any logic circuit whereas GPU's are optimized for highly parallel arithmetic computations. I don't understand how that makes FPGA's "more specialized". It seems like they are in fact more general.

You can't buy FPGAs at Fry's and you can't use them for gaming when you're not mining.

FPGA designs can be more specialized than GPU kernels, because FPGAs are more general than GPUs.

They are specialized in generality /s

You have indicated that you do not want to be cookied by us. If you continue on our site, you are agreeing to our Ad and Cookie Policy. If you do not agree, please navigate away from this site.

I wonder what this means? Is there a timer until the cookie gets set?

Good point. It wasn’t immediately obvious that your first part was a quote from the site, but you’re right that it’s unclear. I don’t see how this could possibly be GDPR compliant.

Does the blog of a NYC-based trading company need to be GDPR compliant? They don't offer goods or services to EU residents AFAICT.

I guess Jane Street has customers in the EU. It is likely that occasionally they meet them in the EU. This might be sufficient to consider them as doing business in the EU, and submitting them to the GDPR.

It depends. The site is offered to EU residents, and the data gathered from EU residents may be shared with companies which do operate in the EU. I can see how this may circumvent the aims and goals of the GDPR and negatively impact EU citizens and residents. I don’t know if the site is liable for any of this, but it seems to be more than merely a hypothetical concern.

Reply on news.ycombinator.com