[erlang-questions] [ANN] Erlang UUID

[Per Andersson]

On Thu, Mar 1, 2012 at 7:33 AM, Michael Truog <mjtruog@REDACTED> wrote:
> On 02/29/2012 01:09 PM, Per Andersson wrote:
>>
>>> Please also remember that the function to retrieve the MAC address from within Erlang is undocumented,
>> The function to retrieve MAC address from Erlang is not
>> undocumented anymore.
>>
>>     [0] http://www.erlang.org/doc/man/inet.html#getifaddrs-0
>>
>
> Thanks for mentioning that.

No problem. I think it was documented in R15.


>>> and "okeuday/uuid" v1 does not depend on an interface being available (i.e., for the MAC address) while
>>> "avtobiff/erlang-uuid" v1 will attempt to use random:uniform/1 to create more than 44bits of randomness if no interface is available.
>>>
>>> 2) There is an important problem within "avtobiff/erlang-uuid" for v4, since random:uniform/1 only provides 44 bits of randomness, if you are lucky (that is probably pushing it, since the algorithm may have been meant to only provide 32 bits), however, the v4 function is attempting to use random:uniform/1 to provide 48 bits and 62 bits, where the rest should become 0 because of the algorithm used by random:uniform/1.  The other problem with v4 is that it reseeds random:uniform/1 each time the function is called with erlang:now(), which creates additional latency and possibly makes the v4 uuid less-random (depending on how it is called, e.g., on a timer).  To see a better implementation for v4, using random:uniform/1, there is get_v4_urandom_bigint/0 and get_v4_urandom_native/0 in "okeuday/uuid", however, both solutions become slower in testing when compared with get_v4/0 which uses crypto:rand_bytes/1 instead of multiple calls to random:uniform/1.
>> Thanks for the comments on this. Erlang UUID no longer uses
>> random:uniform/1 to create anymore than 32 bits of random
>> data.
>>
>> However, how do you deduce that random:uniform/1 only provides
>> 44 bits of random data? Since a float is returned from random:random/0
>> which is used by random:uniform/1, isn't the total random bits 16 or 24
>> (4 and 3 words on 32-bit and 64-bit architectures respectively)?
>>
>>     [1] http://www.erlang.org/doc/efficiency_guide/advanced.html#id68291
>>
> I have not tried to track down the paper connected with the algorithm implemented within the random module (B.A. Wichmann and I.D.Hill, in 'An efficient and portable pseudo-random number generator', Journal of Applied Statistics. AS183. 1982, or Byte March 1987), so I am not sure if they were limited to 32 bit integers, but I assume they were.  When I looked at this awhile ago, I forgot to add 1 to the result, so it is actually 45 bits, not 44 bits.  Before looking at the algorithm, I knew empirically that the random module had some limitation that causes a lack of variation in the output I saw, and the way I consider it to be 45 bits is through looking at the input to the floating point number that is used (part of the random:uniform/0 code):
>    B1 = (A1*171) rem 30269,
>    B2 = (A2*172) rem 30307,
>    B3 = (A3*170) rem 30323,
>    put(random_seed, {B1,B2,B3}),
>    R = A1/30269 + A2/30307 + A3/30323,
>    R - trunc(R).
> So, {B1, B2, B3} becomes the next seed value {A1, A2, A3}.  Simplifying this, gives:
>    R = (918999161 * A1 + 917846887 * A2 + 917362583 * A3) / 27817185604309
> Whatever the values for A1, A2, and A3, (918999161 * A1 + 917846887 * A2 + 917362583 * A3) can not exceed 27817185604309 (30269 * 30307 * 30323) because of the previous modulus.  So, that means the algorithm breaks down, being unable to uniformly sample numbers beyond an N of 27817185604309, when considering the N provided to random:uniform/1.  When determining how many bits it takes to represent 27817185604309, you get:
> 1> (math:log(27817185604309) / math:log(2)) + 1.
> 45.6610416965467
>
> If you are concerned about the floating point part:
> 2> 1 / 27817185604309.
> 3.59489998098548e-14
>
> As shown here http://en.wikipedia.org/wiki/Double-precision_floating-point_format , 15.955 decimal digits can be represented within a double precision floating point number.  This is enough to contain the fraction, since Erlang is using double precision for the calculation, so it should not reduce the maximum number of bits that can be provided for uniformly random numbers.

Thanks for the run down on random bits!

I actually tracked down the paper and skimmed it. AFAIK It is possible
(and even recommended IIRC) to combine several generators for
exceeding the 32-bit limit. Since they when the paper was written used
16-bit arches also, but wanted a portable PRNG, combined generators
mean same on both 16-bit and 32-bit arches.


>>> 3) The other important difference is the license.  "avtobiff/erlang-uuid" is under a GPLv3 license, while "okeuday/uuid" is under a BSD license.  So, there is nothing blocking the commercial use of "okeuday/uuid" (please remember I am not a lawyer, nor am I giving legal advice).
>> It is of course entirely possible to develop commercial applications with
>> GPL'd software. What you can't do is to transform free software into
>> proprietary software.
>>
> This is a little misleading.  You can never sell anything that contains GPL software, so many people consider GPL software to poison a code-base, since it can limit a full stack from becoming a product (this is the reason why some BSD distributions want a compiler that is not gcc, etc.).  So, the most you can do with GPL software is sell the service that is written with it, assuming you always submit your proprietary code changes to the developer of the GPL project (disclaimer: please remember I am not a lawyer, nor am I giving legal advice).

Sorry but you are wrong. You can of course sell GPL'd software!
Remember RedHat sells RHEL of which great parts are GPL'd.
What you can't do is to distribute only binaries, you have to supply
(buildable!) source code upon demand. See the Free Software
Foundations FAQ on the subject.

    [0] http://www.gnu.org/licenses/gpl-faq.html#DoesTheGPLAllowMoney

So as long as you don't sell only binaries but also include the source
code (upon demand) you are complying with the GNU GPL.

If you provide a service (say on the world wide web) you don't have to
provide source code at all, so it is fully compliant with GPL to use GPL'd
software for your proprietary web service. That is what the Affero GPL is for,
to ensure that services also distribute source code. E. g. of AGPL users
are gitorious.org and jabber.se.


--
Per

> -- Michael
>