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 ?
1 Like
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.)
1 Like
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?
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).
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 …
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? 
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 
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
https://www.livescience.com/62561-laser-computer-speed-quantum.html
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 …
I’ve implemented Wesolowski VDF verifier in solidity for 2048 bit RSA settings. Verification takes around 200k gas after eip2565.
1 Like
Nice!
We will look into it
There is an RSA VDF verifier in Solidity here by @pvienhage : GitHub - 0xProject/VDF: A Solidity implementation of a VDF verifier contract
It’s definitely not production ready though
Nice!
We may use it at SKALE in the next release
1 Like
This might not be pure enough for your purposes, but one quick and dirty way to harvest random entropy on-chain is to leverage the Efficient Market Hypothesis.
Pick some trading pair and medium-frequency horizon, where price movements are approximately normal. Say 5 minutes on ETH/USDT. Collect one bit of entropy using the following formula:
- Price moves up by at least one sigma (and holds for 5+ blocks) → 1
- Price moves down by at least one sigma (and holds for 5+ blocks) → 0
- Otherwise, no entropy. Wait another period.
An attacker would have to spend very large resources to manipulate a liquid market. The reason we add 5+ blocks, is because it prevents an attacker from manipulating within a single block or a hostile miner from manipulating within a consecutive sequence of blocks that it controls. 5+ blocks requires genuine defense against speculative attacks by arbitrageurs.
You can also accelerate the entropy rate by looking at multiple markets, but you have to make sure to de-correlate the cross-sectional returns so that the bits are independent.
Hi @kilic
I am a bit late into this conversation, but I had a look at the repository above (GitHub - kilic/evmvdf: Delay Function Verification Smart Contract). Great work!! However, it has 2 fundamental issues that I can see:
-
Fractional division
It is doing a division to a fractional value (0…1), and decimals are not supported in the big num library, eg const b = r2.div(challenge.l); -
Modular exponentiation
The Wesolowski paper and other implementations (eg GitHub - poanetwork/vdf: An implementation of Verifiable Delay Functions in Rust) do not use the RSA modulus in their pow functions, instead uses GMP’s pure pow function.
Because of (1) the evaluator in vdf.ts will not work. And for (2), I am not sure the implication of using modm over pow, and since it is different from the formula in the paper, will it open the solution up to potential attacks?