Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat: deterministic pseudorandom operations #140

Merged
merged 2 commits into from
Dec 22, 2022

Conversation

AaronFeickert
Copy link
Contributor

@AaronFeickert AaronFeickert commented Oct 26, 2022

This is a proof of concept for a deterministic shuffler and bounded number generator for use in consensus-critical applications. It provides a generic API that lets you choose your favorite CSPRNG.

Some protocol applications are likely to require the use of consensus-based pseudorandomness. For example, the network may need to choose or shuffle among validator nodes using chain state data as a common seed. This means that all such nodes must take this seed and use it to arrive at the same results. While rand has generic functionality for these kinds of operations using any random number generator, there is no guarantee that its algorithms for doing so will be the same across versions, which could lead to dependency issues.

This work provides one design that has no rand dependency. It offers a generic DeterministicRandomizer type that can be instantiated with any seedable CSPRNG. The tests use a ChaCha12-based generator that happens to be the standard one used in rand currently, but which we import explicitly from rand_chacha instead.

When a bounded u32 is requested, it takes a u64 value from the PRNG and reduces it. When a bounded u64 is requested, it takes two u64 values from the PRNG, uses bit shifting to produce a u128 value, and reduces it. This approach mitigates bias.

Comments welcome.

@AaronFeickert AaronFeickert changed the title feat: deterministic shuffling feat: deterministic pseudorandom operations Oct 26, 2022
@hansieodendaal
Copy link
Contributor

hansieodendaal commented Oct 27, 2022

Really interesting, just wondering why this is not also implemented (or should I say required) to produce a u64 output, by reducing a u128.

@AaronFeickert
Copy link
Contributor Author

AaronFeickert commented Oct 27, 2022

Really interesting, just wondering why this is not also implemented (or should I say required) to produce a u64 output, by reducing a u128.

Added! We can't get a u128 directly from the PRNG, but we can use bit shifting on two u64 values instead.

@AaronFeickert
Copy link
Contributor Author

Moving this from draft to ready, in case there's a desire to implement it directly.

@AaronFeickert AaronFeickert marked this pull request as ready for review November 2, 2022 16:42
Copy link
Contributor

@CjS77 CjS77 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's not clear why bounds are restricted to u32 here. Why wouldn't we just use u64?

src/deterministic_randomizer.rs Show resolved Hide resolved
src/deterministic_randomizer.rs Outdated Show resolved Hide resolved
@CjS77
Copy link
Contributor

CjS77 commented Nov 9, 2022

I'm leaning towards all or nothing on the rand dependency - either impl our own next_u64 (or next_u128 since it's more apropos) or use rand functions throughout.

@AaronFeickert
Copy link
Contributor Author

I'm leaning towards all or nothing on the rand dependency - either impl our own next_u64 (or next_u128 since it's more apropos) or use rand functions throughout.

The next_u64 functionality is provided by BlockRng in rand_core, so it's not strictly a rand dependency. The only things we would need to dip into rand for are using such a u64 in possibly version-specific modular reduction or shuffling routines, which is why we do those ourselves in this PR.

Do you think it could be the case that we'd still end up in dependency mismatch land if we update rand in the future and need to update rand_core with breaking changes as well?

@CjS77
Copy link
Contributor

CjS77 commented Nov 11, 2022

I'm leaning towards all or nothing on the rand dependency - either impl our own next_u64 (or next_u128 since it's more apropos) or use rand functions throughout.

The next_u64 functionality is provided by BlockRng in rand_core, so it's not strictly a rand dependency. The only things we would need to dip into rand for are using such a u64 in possibly version-specific modular reduction or shuffling routines, which is why we do those ourselves in this PR.

Do you think it could be the case that we'd still end up in dependency mismatch land if we update rand in the future and need to update rand_core with breaking changes as well?

That is my concern, yes.

@AaronFeickert AaronFeickert force-pushed the deterministic-shuffle branch 2 times, most recently from 49c19d2 to 509896d Compare November 17, 2022 23:54
hansieodendaal
hansieodendaal previously approved these changes Nov 18, 2022
Copy link
Contributor

@hansieodendaal hansieodendaal left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

utACK

src/deterministic_randomizer.rs Outdated Show resolved Hide resolved
@AaronFeickert
Copy link
Contributor Author

AaronFeickert commented Nov 18, 2022

@CjS77 brought up the idea that if we take this approach, it's better to implement next_u32 and next_u64 directly, rather than rely on the default implementations provided by rand_core. This would mean that rand_core is ideally only used for marker traits on acceptable CSPRNGs, and that any higher-level operations are manually implemented to avoid version-dependent changes to rand or rand_core functionality.

CjS77
CjS77 previously approved these changes Dec 21, 2022
Copy link
Contributor

@CjS77 CjS77 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One nit in the doc string, but LGTM

src/deterministic_randomizer.rs Outdated Show resolved Hide resolved
@CjS77 CjS77 merged commit 306cf1b into tari-project:main Dec 22, 2022
@AaronFeickert AaronFeickert deleted the deterministic-shuffle branch December 22, 2022 15:16
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants