docs: Add Randomness tutorial

[jessiemongeon1]

[github-actions[bot]]

Comparing from 43d229ff0cf7814ebb51cae89f7032c03c64de4a to 2ef3b97baee64a8d0df8e4881b077902f1e9dbb5: The produced WebAssembly code seems to be completely unchanged.

[timohanke]

It seems that in this function we don't get the full range all the way to max. I mean not even the open interval [0,max).

  func chooseMax(f : Random.Finite, max : Nat) : ? Nat {
    assert max > 0;
    do ? {
      if (max == 1) return ? 0;
      var k = bit(f.coin()!);
      var n = max / 2;
      while (n > 1) {
        k := k * 2 + bit(f.coin()!);
        n := n / 2;
      };
      if (k < max)
        return ? k
      else chooseMax(f, max)!; // retry
    };
  };

For example say max = 3. Then n = 1, the while loop won't run at all, so we get k = 0 or 1 , which is the interval [0,2) not [0,3).

[timohanke]

A different remark: I think we should make clear what requires asynchronous randomness and what doesn't. Asynchronous randomness must be retrieved after bets are closed (we made that clear). But what if we try to shuffle the deck and the entropy is exhausted. Do we then really want to tell the developers they have to get new asynchronous randomness? That's bad for latency and unnecessary. They can extend the one entropy that they already retrieved asynchronously after the bets were closed and feed it into a deterministic PRNG. Since the bets are closed it's ok that this is deterministic. There is no point in getting the next entropy (if additional entropy is required) asynchronously again. And the asynchronous entropy isn't cryptographically "better" than the one from a PRNG either.

I would feed the entropy into sha2 for example to get an infinite stream. Then the shuffling will always complete in one execution round.

[crusso]

It seems that in this function we don't get the full range all the way to max. I mean not even the open interval [0,max).

  func chooseMax(f : Random.Finite, max : Nat) : ? Nat {
    assert max > 0;
    do ? {
      if (max == 1) return ? 0;
      var k = bit(f.coin()!);
      var n = max / 2;
      while (n > 1) {
        k := k * 2 + bit(f.coin()!);
        n := n / 2;
      };
      if (k < max)
        return ? k
      else chooseMax(f, max)!; // retry
    };
  };

For example say max = 3. Then n = 1, the while loop won't run at all, so we get k = 0 or 1 , which is the interval [0,2) not [0,3).

Sorry, Jessie just used my broken code (https://github.com/crusso/card-shuffle) at my suggestion. Without switching my brain on, is it enough to change the loop guard to

while (n > 0) { ... }

?

[crusso]

A different remark: I think we should make clear what requires asynchronous randomness and what doesn't. Asynchronous randomness must be retrieved after bets are closed (we made that clear). But what if we try to shuffle the deck and the entropy is exhausted. Do we then really want to tell the developers they have to get new asynchronous randomness? That's bad for latency and unnecessary. They can extend the one entropy that they already retrieved asynchronously after the bets were closed and feed it into a deterministic PRNG. Since the bets are closed it's ok that this is deterministic. There is no point in getting the next entropy (if additional entropy is required) asynchronously again. And the asynchronous entropy isn't cryptographically "better" than the one from a PRNG either.

I would feed the entropy into sha2 for example to get an infinite stream. Then the shuffling will always complete in one execution round.

Hmm, that suggests that our random maze example could also be improved (and, incidentally, might be suffering from the same bug). The maze generator keeps asking for more entropy when it runs out of bits too.

[timohanke]

n > 0

No, but using max - 1. The number of coins drawn should equal bitlength(max - 1).

  import Random "mo:base/Random";
  
  func bit(b : Bool) : Nat = if(b) 1 else 0;
  
  func chooseMax(f : Random.Finite, max : Nat) : ? Nat {
    assert max > 0;
    do ? {
      var n = max - 1 : Nat;
      var k = 0;
      while (n != 0) {
        k *= 2;
        k += bit(f.coin()!);
        n /= 2;
      };
      if (k < max) k else chooseMax(f, max)!;
    };
  };
  
  let f = Random.Finite("\0a");
  
  chooseMax(f, 256);

[jessiemongeon1]

@crusso Could you suggest some edits to address @timohanke 's feedback?

[crusso]

@timohanke is that a little better, if not perfect?

[timohanke]

@timohanke is that a little better, if not perfect?

Yeah, best we can do with only base available.