Fast way to obtain entropy

Developers Motoko
1

Assuming P!=NP,

I need to create software that obtains array of 16 random bytes in such a way that no two such arrays are equal, if generated by this my software.

Obtaining entropy as described in Internet Computer Loading may be not optimal, because it takes time during startup of my application.

Is obtaining entropy fast enough not to significantly slowdown startup? If it is slow, what are alternatives? I would use time as the seed, but two instances of my app may happen to start exactly simultaneously. Or is probability of simultaneous startup low enough? (Time is measured in nanosecs.) If two seeds are the same, logical data corruption is possible (like one blog post text overwriting another post). I am also a little worried about canisters intentionally juggling with time to break my app (not much likely, but theoretically possible).

2

Well obviously because one has a N and one doesn’t.

Here’s the code we use for random number generation at Dragginz…

use crate::time;
use once_cell::sync::Lazy;
use std::sync::Mutex;
use tinyrand::{Rand, Seeded, StdRand};

//
// rand
//

static STD_RAND: Lazy<Mutex<StdRand>> = Lazy::new(|| Mutex::new(StdRand::seed(time::now_millis())));

/// Generate a random u16
#[must_use]
pub fn u16() -> u16 {
    STD_RAND.lock().expect("mutex").next_u16()
}

/// Generate a random u32
#[must_use]
pub fn u32() -> u32 {
    STD_RAND.lock().expect("mutex").next_u32()
}

/// Generate a random u64
#[must_use]
pub fn u64() -> u64 {
    STD_RAND.lock().expect("mutex").next_u64()
}

/// Generate a random u128
#[must_use]
pub fn u128() -> u128 {
    STD_RAND.lock().expect("mutex").next_u128()
}

//
// TESTS
//

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_unique_u64s() {
        use std::collections::HashSet;

        let mut set = HashSet::new();
        while set.len() < 1000 {
            let random_value = u64();
            assert!(set.insert(random_value), "value already in set");
        }
    }

    #[test]
    fn test_rng_uniformity() {
        let mut buckets = vec![0; 10];
        for _ in 0..10000 {
            let random_u16 = u16() as usize % 10;
            buckets[random_u16] += 1;
        }

        for count in buckets {
            assert!(
                (900..=1100).contains(&count),
                "Bucket count {count} outside of expected range"
            );
        }
    }

    #[test]
    fn test_rng_reseeding() {
        let mut rng1 = StdRand::seed(time::now_millis());
        let mut rng2 = StdRand::seed(time::now_millis() + 1);

        let mut matched = false;
        for _ in 0..100 {
            if rng1.next_u64() == rng2.next_u64() {
                matched = true;
                break;
            }
        }
        assert!(
            !matched,
            "RNGs with different seeds produced different values"
        );
    }
}

In our previous Motoko life we decided not to use the Random crate as it was a 2 second call and scheduling that to start async was a bit too complicated for us at the time.

What we ended up doing was a sha256 on the current time, generating 32 bytes of entropy from that and when it was used up it would automatically do another sha256 on the seed and replace the entropy.

Why not use a ULID?

use crate::{rand, time};
pub use ulid::Ulid;

/// Generate a ULID string with the current timestamp and a random value
#[must_use]
pub fn generate() -> String {
    let ts = time::now_millis();
    let rand = rand::u128();
    let ulid = Ulid::from_parts(ts, rand);

    ulid.to_string()
}

//
// TESTS
//

#[cfg(test)]
mod tests {
    use super::*;
    use std::{thread, time::Duration};

    #[test]
    fn test_generate_ulid() {
        let mut ulids = Vec::new();

        // Generate 5 ULIDs
        for _ in 0..5 {
            let ulid = generate();

            // ULID should not be empty
            assert!(!ulid.is_empty());

            // ULID should have correct length
            assert_eq!(ulid.len(), 26);

            // ULID should be unique
            assert!(!ulids.contains(&ulid));

            // ULID should start with "01"
            assert!(ulid.starts_with("01"));

            // Add ULID to the vector
            ulids.push(ulid);

            // Sleep to ensure the next ULID has a different timestamp
            thread::sleep(Duration::from_millis(1));
        }

        // ULIDs should be lexicographically sortable
        let mut sorted_ulids = ulids.clone();
        sorted_ulids.sort();
        assert_eq!(ulids, sorted_ulids);
    }
}

Not sure if that helps!

1 Like
3

You can use https://mops.one/prng
It will probably be best to mix that somehow with the proper IC random number generator. Depends on your use case. If you are rewarding based on this, https://internetcomputer.org/docs/current/motoko/main/base/Random/ is the way to go. It’s one of IC’s special abilities you don’t want to miss. If you need it for a library like Skip List, prng will get the job done.