3 ms·

The computation described (compute x^(2^t) mod N) is designed to not be parallelizable.

by zodiac 7y ago

zaroth 7y ago
Interesting... so let's assume everyone can compute it in about the same amount of time, how does the "lottery" work? OK, I found this fairly informative [1]. It's designed to be an entropy source feeding into a proof-of-stake algorithm. If you can't run it "that much" faster than everyone else, it's more likely your result is not manipulated to steer an unfair portion of the block reward your way. I haven't read much about any of this. The point that seems to stick out most is the idea that "everyone" submits some amount of data, versus just the first to reach the difficulty target submitting. Once you have that concept, then you need time gates to control how quickly the rounds happen, and VDF can be used to dictate the clock rate. A conceptual piece I must still be missing is how all the submissions are aggregated, and why many/most can't just be ignored. Ah, fucking blockchain catnip. [1] - https://ethresear.ch/t/verifiable-delay-functions-and-attacks/2365 https://ethresear.ch/t/verifiable-delay-functions-and-attack...
- justindrake 7y ago
  ELI5 version: 100 people, one by one, (re)roll dice placed in a dark room. After the last person lights turn on, revealing a fair random number. The Verifiable Delay Function (VDF) ensures lights aren't turned on early. For a video explanation of the randomness mechanism see https://www.youtube.com/watch?v=zqL_cMlPjOI&feature=youtu.be https://www.youtube.com/watch?v=zqL_cMlPjOI&feature=youtu.be
superpermutat0r 7y ago
But squaring numbers is paralellizable. You pick an exponent you want and take a modulus only later. Iterative squaring is also trivial if exponent is a power of two. Calculating x^(2^t) mod n should take no time on any computer. I think the rest of the puzzle is fairly hard to guess.
- zodiac 7y ago
  Iterative squaring is not paralellizable - to compute x^4 as (x^2)^2 you have to compute t = x^2 first before starting the computation of t^2. Calculating x^(2^t) mod n takes t squarings.

The computation described (compute x^(2^t) mod N) is designed to not be parallelizable.

by zodiac 7y ago

The computation described (compute x^(2^t) mod N) is designed to not be parallelizable.

Interesting... so let's assume everyone can compute it in about the same amount of time, how does the "lottery" work? OK, I found this fairly informative [1]. It's designed to be an entropy source feeding into a proof-of-stake algorithm. If you can't run it "that much" faster than everyone else, it's more likely your result is not manipulated to steer an unfair portion of the block reward your way. I haven't read much about any of this. The point that seems to stick out most is the idea that "everyone" submits some amount of data, versus just the first to reach the difficulty target submitting. Once you have that concept, then you need time gates to control how quickly the rounds happen, and VDF can be used to dictate the clock rate. A conceptual piece I must still be missing is how all the submissions are aggregated, and why many/most can't just be ignored. Ah, fucking blockchain catnip. [1] - https://ethresear.ch/t/verifiable-delay-functions-and-attacks/2365 https://ethresear.ch/t/verifiable-delay-functions-and-attack...

justindrake 7y ago
ELI5 version: 100 people, one by one, (re)roll dice placed in a dark room. After the last person lights turn on, revealing a fair random number. The Verifiable Delay Function (VDF) ensures lights aren't turned on early. For a video explanation of the randomness mechanism see https://www.youtube.com/watch?v=zqL_cMlPjOI&feature=youtu.be https://www.youtube.com/watch?v=zqL_cMlPjOI&feature=youtu.be

superpermutat0r 7y ago

But squaring numbers is paralellizable. You pick an exponent you want and take a modulus only later. Iterative squaring is also trivial if exponent is a power of two. Calculating x^(2^t) mod n should take no time on any computer. I think the rest of the puzzle is fairly hard to guess.

zodiac 7y ago
Iterative squaring is not paralellizable - to compute x^4 as (x^2)^2 you have to compute t = x^2 first before starting the computation of t^2. Calculating x^(2^t) mod n takes t squarings.