Anyone working on Solidity-verifiable VDF?


#1

I wonder if any one at this message board is looking on a VDF (verifiable delay function) which is efficiently verifiable in Solidity? We need random numbers in our project, and are looking on implementing such a VDF. The question is, how much gas would it take to verify a VDF in Solidity, and is it practical to do it ?


#2

In Ethereum 2.0 you should to get unbiasable random numbers almost for free via an EVM2.0 opcode. If you want a custom randomness scheme or a custom VDF at the application layer then the costs will depend on which VDF you use, the specifics of the prover, and potentially also the time parameter.

If you’re happy using SNARKs then the verification costs will be no larger than one SNARK verification as you can encapsulate the VDF verification steps in a SNARK. The proof sizes for the RSA VDFs we are considering for Ethereum 2.0 have proof sizes ranging the order of 0.5kB to 10kB, and verification times are on the order of 0.5ms to 10ms where the bulk is modular multiplications. (The Wesolowski scheme also has about 0.1ms of primality testing.)


#3

Justin - thank you. We need it in ETH 1.0 since our network is going to go live before ETH 2.0 …

Now I understand that we can not do Weselowski since we cant do primality testing in Solidity …

I think using SNARKS is a great idea. Do you mean like doing lots of SHA sequential hashes and doing a SNARK proof for it, which is verified in Solidity ?)) In your opinion, what would be the optimal function to do inside the SNARK?


#4

An important consideration is what commodity hardware you intend to use. Anything less than a top-of-the-range FPGA is probably a non-starter, unless you only need randomness very infrequently and use a large A_max.

Do you mean like doing lots of SHA sequential hashes and doing a SNARK proof for it, which is verified in Solidity

You could use Guralnick and Muller polynomials (see page 18 here) combined with SNARKs but these polynomials haven’t really been stress tested for security.

I think using SNARKS is a great idea.

I was thinking of doing a first round of Pietrzak or Wesolowski and then shrinking the proof using a SNARK to save on gas. Unfortunately RSA doesn’t play super well with SNARKs. Benedikt Bunz pointed to this paper which brought down RSA key exchange to 435k gates (for reference a sapling Zcash transaction is about 100k gates).


#5

Justin - thank you.

In our case we need RNG to pick servers for a side chain from a large server network, this needs to happen once in a life time of a side chain. It is OK for us to have three hour wait-out time, so essentially as long as the attacker is not 1000 times faster than we, we are fine …


#6

this needs to happen once in a life time of a side chain

Oh, that’s ideal. Can you just use a massive SHA3 hash chain with collaterisation and TrueBit-style challenges? :slight_smile:


#7

I think we can … Then we need to get the challengers … We are just a tiny startup with a tiny network - nobody would probably want to be a challenger :sob:


#8

Here is an interesting paper on graphene-based transistors that can work at 100 GZ

Theoretically using graphene you can do 25 faster VDF calculations than a custom ASIC that works at 4GZ …

And then there are DARPA programs for ultrafast GaAs transistors that can operate at up to 1THZ

http://antena.fe.uni-lj.si/literatura/Razno/Konferenca%20midem%202015/hemt/06005329.pdf

Also there is research that if you replace electrons with laser light, you can build transistors 1M times (!) faster than silicon ASIC

So it looks like doing a VDF on a PC is not really practical. And even an FPGA based VDF based on regular silicon chips may be not so secure …