1
$\begingroup$

I came across the Solana network utilizing sha256 as a "proof of history". They are using it as a pseudo-VDF (verifiable delay function). The reason it's pseudo is because verification is done by full-effort recompute in parallel using intermediate values.

I am curious whether or not the way sha256 is implemented on modern CPU's is as good as it can get on silicon. Or close to it.

sha256/shacal256 is an unbalanced Feistel block cipher which updates 2 words out of 8 every round using modular addition and some other bitwise operations.

The way the sha256 extension works on the x86 cpu:

sha256msg1 ...
vpalignr ...
paddd ...
sha256msg2 ...

sha256rnds2 x, y
sha256rnds2 y, x

This performs 4 rounds of sha256, out of 64 rounds. sha256msg1 to sha256msg2 are only performed for 3/4 of those rounds. The 512 bit input/key is expanded to 2048 bits, with the first 512 bits processesed as is.

As per these tables the clock cycle latency for AMD zen4:

SHA256MSG1   3
SHA256MSG2   5
SHA256RNDS2  4
paddd        1
vpalignr     unk, maybe 3?

Does this achieve the ideal objective of a pseudo-VDF of being near-optimal in silicon? Can an ASIC perform sha256 in fewer clock cycles, and if so by what margin?

Edit:

I need to point out that throughput and power efficiency is irrelevant for this use case. This is about the smallest amount of a time a single sha256 computation can run at.

This is about whether or not it's possible to construct a sha256 circuit that would finish in less time than the CPU with the sha256 extension. Is there some way for an ASIC to complete faster?

$\endgroup$
2
  • $\begingroup$ I see hardly this is on-topic hereafter the answers. I think this suites more into ee. $\endgroup$
    – kelalaka
    Oct 23, 2023 at 15:06
  • 1
    $\begingroup$ I don't understand why people are talking about throughput and power efficiency, it doesn't matter how many sha256 you can run if you have to iterate for a long time, VDF was clearly mentioned... $\endgroup$ Oct 23, 2023 at 15:12

1 Answer 1

0
$\begingroup$

This is a question with a lot of different nuances. Usually, the speed that I can run an algorithm on a custom ASIC is a function of how I can cool it. For instance, Si is a cheap substrate, but it's indirect bandgap so there are collisions in the channel. Direct bandgap substrates are much more expensive but have fewer collisions, but are not generally commodity parts.

Now for the circuits, clockless SHA-256 implementations exist in academia and in IP libraries that are much faster than their synchronous counterparts. Synchronous systems, ie: it has a clock, are the bedrock of most processors and are clocked at the slowest case required to make timing; however, performance cases generally are not commodity. I have personally never used these cores, but you have "reservation stations" as boundaries between the asynchronous and synchronous, and this allows you do just "pull the data" as soon as it's done. This is the same system that we use for dividers as you don't know when the instruction will complete (an advantage of super-scalar processors). In this way, you can run the circuits at the maximum throughput of the circuit.

Now speculation: I'm going to guess that if you gave me some on-chip cache (not dielets) and freedom to just stream read the buffer, I could do about 100x in a custom ASIC in throughput compared to a CPU. That's generally the ball-park I see for stream processing.

$\endgroup$
3
  • $\begingroup$ I need to point out that throughput and power efficiency is irrelevant for this use case. This is about the smallest amount of a time a single sha256 computation can run at. $\endgroup$ Oct 23, 2023 at 15:08
  • $\begingroup$ @LightTunnelEnd I just looked and the spec that I pulled from a synchronous IP library is 128G-bits/sec at 1Ghz. That's about ~500MiB/sec. I didn't look at the buffer requirements. $\endgroup$
    – b degnan
    Oct 23, 2023 at 16:40
  • 1
    $\begingroup$ openssl speed -evp sha256 can do 2 GB/sec @ 3-4 Ghz. I think it would require different optimization criteria hitherto no one wanted to make. I asked the question in part to see if such optimizations that would best a CPU on single sha256 execution latency could even be made, and if so by what margin. $\endgroup$ Oct 23, 2023 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.