SHA256-based VDF


#1

Just started reading about VDFs…

Noticed that Solana’s VDF is basically a recursive SHA256. A brief explanation of the model:

The rationale is: " …thanks to Bitcoin there has been significant research in making this cryptographic hash function fast. This function is impossible to speed up by using a larger die area, like a Look Up Table, or unrolling it without impact to clock speed. Both Intel and AMD are releasing consumer chips that can do a full round of SHA256 in 1.75 cycles. Because of this, we have pretty good certainty that a custom ASIC will not be 100x faster, let alone 1000x, and most likey will be within 30% of what is available to the network. We can construct protocols that exploit this bound and only allow an attacker a very limited, easily detected and shortlived oportunity for a denial of service attack."

Any thoughts on this? Would it be worth considering for the Ethereum beacon chain? Thanks. :slight_smile:


#2

How do they prove the result to clients that don’t have these magic chips built in?

Arithmetic is also something that there’s been huge research on speeding up, so I still think MIMC+STARK is better.


#3

Thanks for highlighting Solana :slight_smile: We do want to use a VDF for Ethereum 2.0 randomness. Verifying hash chains in parallel does not readily work for us (unless we use a cryptoeconomic VDF) for a few reasons:

  1. Low latency: Verification must be low latency to reduce the randomness lookahead and prevent DoS attacks.
  2. Light clients: Verification of VDF outputs must be doable by light clients with limitted parallelism (e.g. an entry-level DigitalOcean instance).
  3. Full nodes: Full nodes (including validators) should ideally not require “exotic” hardware such as GPUs for verification.

It is possible Solana could benefit from moving to Sloth (or better, Sloth++) instead of SHA256. My favourite VDF is by Benjamin Wesolowski, specifically the instantiation in RSA groups. I am currently looking into the viability of building a commodity ASIC for it to minimise the speed advantage an attacker may get. Filecoin and Chia are two other projects looking into VDF ASICs.


#4

They state that the output can be verified in parallel on clients’ GPUs: “Each recorded slice can be verified from start to finish on separate cores in 1/(number of cores) time it took to generate. So a modern day GPU with 4000 cores can verify a second in 0.25 milliseconds.”

You might be right. I generally love everything STARK-related. :slight_smile: Thanks for the link, haven’t look into MIMC yet, but it was on my reading list already. :slight_smile:


#5

thanks for mentioning the project! I am happy to answer any questions, please poke holes :slight_smile:


#6

I guess we dont see GPUs all that exotic, since you can purchase them everywhere. We are using GPUs for just about everything, ed255 ecdsa, and hopefully soon contract execution. You get the cheapest cores per dollar on GPUs.


#7

My main concern is that GPUs exclude light clients, and cloud providers such as DigitalOcean.

Edit: It looks like DigitalOcean will support GPUs at some point.


#8

If no GPU handy and okay with longer startup and finality times, 2 or more CPU cores will suffice. Here’s the code: https://github.com/solana-labs/solana/blob/v0.7.2/src/ledger.rs#L421. Tests down below.


#9

oof, you expect these digital ocean clients to be custodians of keys?


#10

Thanks for clarifying. IMHO, points 1 and 2 are valid, point 3 not so much (GPUs are more or less widely available).

Thanks for the links, added to the reading list. :slight_smile:

ASICs are my biggest concern regarding VDFs, and the main reason why I’m more inclined towards threshold cryptography when it comes to randomness. The plan to start the production of commodity VDF AISCs is really ambitious and challenging, and honestly I wonder if it’s realistic at all… I might be wrong, of course, hardware is not my thing after all…


#11

No problem, :slight_smile: I’m glad to see you here. You guys are really experienced as far as I can see (especially with hardware/low level), and it seems to me like there’s a lot of substance to your project (which is not always the case with newer crypto projects :joy:). Having that in mind, I hope you will communicate and join efforts with @JustinDrake and others from Ethereum/Filecoin/Chia, I’m sure all projects will benefit. :star_struck::tada::confetti_ball: