[RFC] Random Extension 3.0

Larry Garfield

4 years ago

On Thu, Sep 2, 2021, at 10:10 AM, Go Kudo wrote:

> Hi Internals.
>
> Expanded from the previous RFC and changed it to an RFC that organizes the
> whole PHP random number generator. Also, the target version has been
> changed to 8.2.
>
> https://wiki.php.net/rfc/rng_extension
> https://github.com/php/php-src/pull/7453
>
> Hopefully you will get some good responses.
>
> Regards,
> Go Kudo

This looks pretty nice to my unskilled eye.  Two questions.

1) Why is the number generator a parent class rather than an interface?  It seems like an interface target.  And either way it needs more clarity about how you'd write one for reals.  (It returns an int, so does that mean getBytes() just derives from a series of ints?)

2) You don't mention the CSPRNG functions at all.  Is there any intention to fold those into this model as well, or to leave those as is?  Or is the Secure generator implementation intended to replace those?  It's unclear here.

--Larry Garfield

zeriyoshi

4 years ago

Thank you.

> Why is the number generator a parent class rather than an interface?

This is an implementation limitation. I could not find a way to define my
own object handler in interface.
As Nikita pointed out in a previous suggestion, the NumberGenerator now
uses php_random_ng_algo_user to generate random numbers faster than before,
even if it is a userland implementation.

> You don't mention the CSPRNG functions at all.

This is a mistake. I have corrected it. Thanks!

I will keep an eye on it throughout the next week, and if there are no
additional responses, I will start voting the week after next.

Regards,
Go Kudo

2021年9月3日(金) 3:26 Larry Garfield <larry@garfieldtech.com>:

Larry Garfield

4 years ago

On Fri, Sep 3, 2021, at 8:55 AM, Go Kudo wrote:

> Thank you.
>
> > Why is the number generator a parent class rather than an interface?
>
> This is an implementation limitation. I could not find a way to define my
> own object handler in interface.
> As Nikita pointed out in a previous suggestion, the NumberGenerator now
> uses php_random_ng_algo_user to generate random numbers faster than before,
> even if it is a userland implementation.

I'm still unclear how I'd write my own NumberGenerator right now.  I mean, I can extend the class, but I don't have a sense for what I'd do with it for non-testing/trivial implementations.  You say it's using an internal function to generate numbers, but in user space what would I do with that?  And when/why would I?

> > You don't mention the CSPRNG functions at all.
>
> This is a mistake. I have corrected it. Thanks!

I'm still not clear on the intent here.  Is the intent that I should stop using random_int()?  And if so, replace it with... what?  Do I have to supply a specific non-default generator?  That makes the usability worse, and more likely to be gotten wrong.

Also, in future scope you you have this sentence, which makes little sense:

>> Replace random_bytes() with random_bytes() for random numbers used in shuffle(), str_shuffle(), and array_rand().

--Larry Garfield

zeriyoshi

4 years ago

> I'm still unclear how I'd write my own NumberGenerator right now.  I

mean, I can extend the class, but I don't have a sense for what I'd do with
it for non-testing/trivial implementations.  You say it's using an internal
function to generate numbers, but in user space what would I do with that?
And when/why would I?

For example, I will create an application that does a lottery. I need to
estimate the load and test it. If I actually use random numbers to draw the
lots, the test results will be different each time.

It is true that this example can be solved by devising a better
implementation of the userland.

If this is the case, you may be wondering why we implement it this way.

Currently, there are several implementations of random number generators
written in PHP.

https://github.com/savvot/random

Although not in this library, I use an in-house interface that is
completely replaceable with random_int() for load testing in my production
brother.

Also, JIT was implemented in PHP 8.0. which has the potential to make it
possible to write in PHP what would otherwise have to be implemented in C
due to execution speed issues. In fact, the random number generator written
in PHP for my tests shows a significant performance improvement when JIT is
enabled. The ability to have a workable random number implementation in
userland should be useful for future extensions.

> Is the intent that I should stop using random_int()?

No, it's not. random_int() is a safe and easy CSPRNG, and is recommended
for future use.
The advantage of using Random\NumberGenerator\Secure is that it can shuffle
strings/arrays using the same random number source as random_int().

Something that is not included in this RFC but that I would like to
deprecate in the future is the mt_srand (srand) function. These have
internal state and are very harmful for extensions such as Swoole:

Also, shuffle() and str_shuffle() are very good functions, but I don't
think they should use the random number source generated by mt_srand. The
user may unintentionally use an unsecured random number.

I apologize for the difficulty in conveying this message. I've revised the
wording.

> Changes random source to php_random_int() in shuffle(), str_shuffle(),

and array_rand() .

2021年9月3日(金) 23:04 Larry Garfield <larry@garfieldtech.com>:

zeriyoshi

4 years ago

My apologies. I had skipped one.

> And either way it needs more clarity about how you'd write one for reals.

Added a simple example comparing it to mt_rand. What do you think of this?

2021年9月3日(金) 3:26 Larry Garfield <larry@garfieldtech.com>:

Nikita Popov

4 years ago

On Thu, Sep 2, 2021 at 5:10 PM Go Kudo <zeriyoshi@gmail.com> wrote:

> Hi Internals.
>
> Expanded from the previous RFC and changed it to an RFC that organizes the
> whole PHP random number generator. Also, the target version has been
> changed to 8.2.
>
> https://wiki.php.net/rfc/rng_extension
> https://github.com/php/php-src/pull/7453
>
> Hopefully you will get some good responses.
>

This looks pretty nice to me. A few bits of feedback:

* Unlike the previous versions of the RFC, this one also moves all of the
existing RNG-related functionality from ext/standard to ext/random. Why
does it do this? This doesn't really seem related to the problem this RFC
is solving.

* Regarding the abstract class Random\NumberGenerator: You currently need
the abstract class, because php_random_ng is tied to the object. An
alternative design that would allow Random\NumberGenerator to be an
interface would be to make it independent of the object, such that the
structure can be allocated in the Random constructor for userland
implementations. Of course, internal implementations could still embed it
as part of their objects -- just don't make it a requirement.

* The future scope mentions: "Changes random source to php_random_int() a
shuffle(), str_shuffle(), and array_rand()". I don't think it makes sense
to switch these functions to use cryptographic randomness by default...

Regards,
Nikita

zeriyoshi

4 years ago

Thanks nikita.

> ext/standard to ext/random. Why does it do this?

There are several reasons for this.

- The `random` extension name is already used by ext/standard and may
interfere with the build system.
- Due to the namespace rules for new extensions, it is inappropriate to
rename an extension.
- Due to history, the rand / mt_rand dependency is tricky and I thought it
was time to sort it out.
- I don't think it's a good idea to have multiple header files for a single
domain feature.
- As stated in the Future Scope, I wanted to be in a position to eliminate
module global random number state in the future.
- The existing implementation and the object implementation share most of
the same logic. It was necessary to merge them into one to make them common.

I certainly didn't want to require a workaround for PHP 8.2 or later for
extensions that depended on ext/standard respectively, but I decided that I
had no choice for the above reasons.

> just don't make it a requirement.

I would like to modify the design.

> I don't think it makes sense to switch these functions to use

cryptographic randomness by default...

While these may not need to be cryptographically secure, I don't think they
need to be state-dependent as well. Probably no one would look at the
function name and think that it depends on the module global state.

php_random_int() doesn't have any state anywhere (except OS) and can
generate the requested random number. I don't see any problem with these
functions using php_random_int() as a random number source.

Regards,
Go Kudo


2021年9月4日(土) 1:02 Nikita Popov <nikita.ppv@gmail.com>:

Dan Ackroyd

4 years ago

On Fri, 3 Sept 2021 at 18:41, Go Kudo <zeriyoshi@gmail.com> wrote:

>
> Nikita wrote:
>> this one also moves all of the existing RNG-related functionality
>> from ext/standard to ext/random.
>
> There are several reasons for this.
>
> - The `random` extension name is already used by ext/standard and may
> interfere with the build system.
> - Due to the namespace rules for new extensions, it is inappropriate to
> rename an extension.
> - Due to history, the rand / mt_rand dependency is tricky and I thought it
> was time to sort it out.
> - I don't think it's a good idea to have multiple header files for a single
> domain feature.

Have you considered how much work that is going to incur on downstream
projects?

If there's a good reason for moving stuff around then it can be
appropriate, but the RFC phrasing of:  "At the same time, the
following internal APIs will also be relocated. If you want to use
them, you can _simply_ include ext/random/random.h." sounds pretty
dismissive of causing possibly unneeded work for downstream projects.

cheers
Dan
Ack

zeriyoshi

4 years ago

This may not have been the best way to put it. The point I was trying to
make was that while BC Breaks do occur, they are very easy to solve.

The impact on downstream projects will be significant, and there may be
many extensions affected, since this change concerns a frequently used RNG
feature. However, in other words, it may need to be sorted out as soon as
possible.

However, I also understand the theory that this should be done in
conjunction with a major language change. Perhaps I should have suggested
this for PHP 8.0.

Either way, I'll try to separate these suggestions if necessary, but if we
were to try to provide an OOP API without BC Break, what do you think would
be the ideal form?

Regards,
Go Kudo

2021年9月5日(日) 4:24 Dan Ackroyd <Danack@basereality.com>:

Dan Ackroyd

4 years ago

Go Kudo wrote:

> Dan Ackroyd wrote:
>> you can _simply_ include ext/random/random.h." sounds pretty
>> dismissive of causing possibly unneeded work for downstream projects.
>
> The point I was trying to make was that while BC Breaks do occur, they are very easy to solve.

I've found it useful to think about "value = benefit minus cost".

I was calling out that it seems to be that this is a change you want
to do for aesthetic reasons and are justifying it by trivialising the
work involved. i.e. it has a tiny benefit that only has a positive
value if the cost is also tiny.

Although the change is simple:

* Any code base that includes standard/php_rand.h won't compile, and
people will have to find out what changed. Even though the fix may be
easy to implement, each of those people will have to figure it out for
themselves.

* quite a few people will have to learn (or relearn) how to use #if to
compare PHP version to include either standard/php_rand.h or
random/php_random.h if they want their code to work on more than 1 PHP
version.

* it makes more work for downstream distributors of PHP, as their
patches (including security patches) will need to be moved around.

If there's a good reason to move stuff around, then fine, but avoiding
creating extra work downstream is worth doing. And possibly is a hot
topic right now.

You could probably avoid a lot of downstream work by leaving a stub
file at standard/php_rand.h that includes random/php_random.h.

cheers
Dan
Ack

btw, if you could please avoid top-posting, that would be appreciated:
https://github.com/php/php-src/blob/master/docs/mailinglist-rules.md

"Do not top post. Place your answer underneath anyone you wish to
quote and remove any previous comment that is not relevant to your
post."

zeriyoshi

4 years ago

2021年9月23日(木) 2:05 Dan Ackroyd <Danack@basereality.com>:

> Go Kudo wrote:
> > Dan Ackroyd wrote:
> >> you can _simply_ include ext/random/random.h." sounds pretty
> >> dismissive of causing possibly unneeded work for downstream projects.
> >
> > The point I was trying to make was that while BC Breaks do occur, they
> are very easy to solve.
>
>
> I've found it useful to think about "value = benefit minus cost".
>
> I was calling out that it seems to be that this is a change you want
> to do for aesthetic reasons and are justifying it by trivialising the
> work involved. i.e. it has a tiny benefit that only has a positive
> value if the cost is also tiny.
>
> Although the change is simple:
>
> * Any code base that includes standard/php_rand.h won't compile, and
> people will have to find out what changed. Even though the fix may be
> easy to implement, each of those people will have to figure it out for
> themselves.
>
> * quite a few people will have to learn (or relearn) how to use #if to
> compare PHP version to include either standard/php_rand.h or
> random/php_random.h if they want their code to work on more than 1 PHP
> version.
>
> * it makes more work for downstream distributors of PHP, as their
> patches (including security patches) will need to be moved around.
>
> If there's a good reason to move stuff around, then fine, but avoiding
> creating extra work downstream is worth doing. And possibly is a hot
> topic right now.
>
> You could probably avoid a lot of downstream work by leaving a stub
> file at standard/php_rand.h that includes random/php_random.h.
>
> cheers
> Dan
> Ack
>
> btw, if you could please avoid top-posting, that would be appreciated:
> https://github.com/php/php-src/blob/master/docs/mailinglist-rules.md
>
> "Do not top post. Place your answer underneath anyone you wish to
> quote and remove any previous comment that is not relevant to your
> post."
>

I apologize for not knowing the rules of ML.
Is this correct?

It is true that it is better to maintain compatibility that can be
maintained.
However, I think this should be sorted out sometime. Perhaps it will be in
PHP 9.0.

First of all, I would like to change these RFC and implementations.

https://wiki.php.net/rfc/random_ext
https://wiki.php.net/rfc/rng_extension

Thank you.

Ben Ramsey

4 years ago

Go Kudo wrote on 9/2/21 10:10:

> Hi Internals.
>
> Expanded from the previous RFC and changed it to an RFC that organizes the
> whole PHP random number generator. Also, the target version has been
> changed to 8.2.
>
> https://wiki.php.net/rfc/rng_extension
> https://github.com/php/php-src/pull/7453
>
> Hopefully you will get some good responses.
>
> Regards,
> Go Kudo
>

This proposal seems like two different proposals to me:

- The first consolidates and cleans up RNG functions for internals
- The second exposes an OOP API for working with RNGs

Personally, I don't see the benefit of including this OOP API in the
core. I don't think it provides any benefits over similar abstractions
in userland, and in fact, I think this kind of API is best suited for
iteration in userland.

Cheers,
Ben

Marc

4 years ago

On 9/2/21 5:10 PM, Go Kudo wrote:

> Hi Internals.
>
> Expanded from the previous RFC and changed it to an RFC that organizes the
> whole PHP random number generator. Also, the target version has been
> changed to 8.2.
>
> https://wiki.php.net/rfc/rng_extension
> https://github.com/php/php-src/pull/7453
>
> Hopefully you will get some good responses.

For me (user land developer with no voting power) your RFC looks pretty :)

Beside the abstract vs interface question I have some other notes:

On the one hand you define "getBytes()" which returns a string and on
the other hand you define "shuffleString()" - is the first one a binary
string and the other a charset dependent string? I guess here
"shuffleString()" works on byte level and so it should be "shuffleBytes()".

Why are there no default values for min/max on "getInt()" - It seems
unnecessary to me to pass min/max arguments if you are just interested
in a random integer or passing max as well if you are interested in a
positive integer only.

Thanks for the nice RFC!

> Regards,
> Go Kudo

Marc

zeriyoshi

4 years ago

Thanks marc.

> "shuffleString()" works on byte level and so it should be

"shuffleBytes()".

Hmm. This may be a difficult problem related to the PHP language
specification. As with `str_shuffle()`, most people will probably use it to
shuffle strings. People who want to shuffle binaries are likely to
understand that in PHP it is synonymous with `shuffleBytes()`.

> Why are there no default values for min/max on "getInt()" - It seems

unnecessary to me to pass min/max arguments

My apologies. I completely forgot that I needed this.
Add this along with a fix for the RNG\NumberGenerator implementation.

Regards,
Go Kudo

2021年9月5日(日) 5:57 Marc <marc@mabe.berlin>:

Nikita Popov

4 years ago

On Sat, Sep 4, 2021 at 10:57 PM Marc <marc@mabe.berlin> wrote:

>
> On 9/2/21 5:10 PM, Go Kudo wrote:
> > Hi Internals.
> >
> > Expanded from the previous RFC and changed it to an RFC that organizes
> the
> > whole PHP random number generator. Also, the target version has been
> > changed to 8.2.
> >
> > https://wiki.php.net/rfc/rng_extension
> > https://github.com/php/php-src/pull/7453
> >
> > Hopefully you will get some good responses.
>
> For me (user land developer with no voting power) your RFC looks pretty :)
>
> Beside the abstract vs interface question I have some other notes:
>
> On the one hand you define "getBytes()" which returns a string and on
> the other hand you define "shuffleString()" - is the first one a binary
> string and the other a charset dependent string? I guess here
> "shuffleString()" works on byte level and so it should be "shuffleBytes()".
>
> Why are there no default values for min/max on "getInt()" - It seems
> unnecessary to me to pass min/max arguments if you are just interested
> in a random integer or passing max as well if you are interested in a
> positive integer only.
>

Because the default range is not obvious. For example mt_rand() without
min/max will actually return only non-negative integers, so someone might
expect $random->getInt() to do the same, even though it makes very little
sense. $random->getInt($n) could be interpreted either as a number in
$n..PHP_INT_MAX (if we just see it as leaving $max at the default value),
or 0..$n-1 (a very common convention for single-argument random integer
functions). Requiring both arguments makes the meaning unambiguous.

Regards,
Nikita

Nikita Popov

4 years ago

On Thu, Sep 2, 2021 at 5:10 PM Go Kudo <zeriyoshi@gmail.com> wrote:

> Hi Internals.
>
> Expanded from the previous RFC and changed it to an RFC that organizes the
> whole PHP random number generator. Also, the target version has been
> changed to 8.2.
>
> https://wiki.php.net/rfc/rng_extension
> https://github.com/php/php-src/pull/7453
>
> Hopefully you will get some good responses.
>

This RFC currently tries to keep some semblance of compatibility with the
existing mt_rand() algorithm by retaining the same implementation for
mapping the raw random number stream into a range. However, the algorithm
we use for that is not exactly state of the art and requires two full-width
divisions at minimum. There are more efficient scaling algorithms based on
fixed-point multiplication, which are "nearly divisionless" (
https://arxiv.org/pdf/1805.10941.pdf). The variant at
https://github.com/apple/swift/pull/39143 is entirely divisionless.

Doing this would improve performance (though I'm not sure by how much --
maybe once we add up our call overhead, it isn't important anymore?) but it
would provide a different sequence than mt_rand(). Something we might want
to consider.

Regards,
Nikita

zeriyoshi

4 years ago

Hi Nikita, sorry for the late reply.

This is a difficult problem. For now, MT19937 is left for compatibility. In
other words, if you don't need compatibility, there is no benefit to using
it.

What about implementing both a new MT and a compatible MT? A compatible MT
would have the following signature

```php

use Random\NumberGenerator\Numbergenerator;

/* for legacy compatibility */
class MT19937 implements NumberGenerator
{
public function __construct(int $mode = MT_RAND_MT19937, int $seed) {}
}

/* a new implementation */
class MersenneTwister implements NumberGenerator
{
public function __construct(int $seed) {}
}
```

I had originally removed the MT_RAND_PHP implementation on the grounds that
legacy implementations should not be retained, but if the regular Mersenne
twister is to be retained for compatibility, I think it should be as well.

Also, maybe we should opt for a more SIMD friendly RNG.

Regards,
Go Kudo

2021年9月7日(火) 17:28 Nikita Popov <nikita.ppv@gmail.com>:

Nikita Popov

4 years ago

On Thu, Sep 9, 2021 at 6:31 AM Go Kudo <zeriyoshi@gmail.com> wrote:

> Hi Nikita, sorry for the late reply.
>
> This is a difficult problem. For now, MT19937 is left for compatibility.
> In other words, if you don't need compatibility, there is no benefit to
> using it.
>
> What about implementing both a new MT and a compatible MT? A compatible MT
> would have the following signature
>
> ```php
>
> use Random\NumberGenerator\Numbergenerator;
>
> /* for legacy compatibility */
> class MT19937 implements NumberGenerator
> {
>     public function __construct(int $mode = MT_RAND_MT19937, int $seed) {}
> }
>
> /* a new implementation */
> class MersenneTwister implements NumberGenerator
> {
>     public function __construct(int $seed) {}
> }
> ```
>
> I had originally removed the MT_RAND_PHP implementation on the grounds
> that legacy implementations should not be retained, but if the regular
> Mersenne twister is to be retained for compatibility, I think it should be
> as well.
>
> Also, maybe we should opt for a more SIMD friendly RNG.
>

To clarify, what I had in mind here is not the MT generator itself, but the
scaling done in Random::getInt(). This scaling is independent of the used
source. So while the raw numbers generated by
Random\NumberGenerator\MT19937 would be the same as before, the result
produced by Random::getInt() with this source wouldn't be.

Regards,
Nikita

zeriyoshi

4 years ago

I had misunderstood this for a long time. Now I understand.
This is certainly something to think about.

However, I think we also need to consider compatibility. How about
something like the following?

```php
<?php

class MT19973_32
{
public const SCALE_NORMAL = 0;
public const SCALE_LEGACY = 1;
public function __construct(?int $seed, int $flag = self::SCALE_NORMAL)
{}
}
```

2021年10月4日(月) 19:24 Nikita Popov <nikita.ppv@gmail.com>:

Kamil Tekiela

4 years ago

Please don't add more answers to the class name. There is already going to
be a backlash if we name it  "MT19973" instead of "MersenneTwister"

zeriyoshi

4 years ago

The RFCs are in limbo, but we are currently thinking of including the
following RNGs in the proposal

- XorShift128Plus
- MT19937 (for compatibility)
- MT19937_64 (for more entropy and wider range)

While it is clear that MT19937 is simply MersenneTwister, it is not
accurate since there is MT19937_64. Also, currently, the constant name that
can be passed to mt_srand() is MT_RAND_MT19937, so I think it is consistent
to use MT19937.

If you mean that it should be MT19937 instead of MT19937_32, then I think
you are right.

Please let me know your opinion.

2021年10月7日(木) 21:56 Kamil Tekiela <tekiela246@gmail.com>:

Kamil Tekiela

4 years ago

Yes, I know the reason why we use MT19937 as the name, but this is not
really very user-friendly name. The actual algorithm could be documented in
the PHP manual but the name could be better. The problem with this name is
that most users simply don't care about the algorithm being used. At least
that is what it was until now. For example
https://phpmanualmasterpieces.tumblr.com/post/65965628369/so-php-such-documented

What I think would be better is to not provide two versions of MT at all
and just call it MersenneTwister. Users who require backwards compatibility
with rand() can do so in userland or keep using rand() for the moment.
Naming is a very minor problem, so I would be ok either way, but I am just
voicing an opinion that having two classes with 32 and 64 at the end, in
this day and age, will be very confusing for users. Better to avoid such
things in PHP.