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:
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:
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?
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?