2
\$\begingroup\$

I have created a script to generate 5 random codes, check if any one of them exists in the database, and if not, insert the record. The script will throw an exception if a single code could not be generated.

The rationale is that of an arbitrary 5 random codes, at least one should be unique. If not, throw an exception.

Is there a better way to ensure that a random code is generated without trying infinitely?

Note: This is a LinqPad script in C#.

Approach #1: Total execution time ~15 seconds for 1k codes.

void Main()
{
    bool exceptionThrown = false;
    int NumberOfVouchersToGenerate = 1000;
    using (var scope = new TransactionScope())
    {
        try
        {
            for (int i = 0; i < NumberOfVouchersToGenerate; i++)
            {
                // generate a list of voucher codes 0 to N
                List<string> voucherCodes = Enumerable.Range(0, MaxGenerateUniqueVoucherAttempts)
                    .Select(_ => GenerateCode(VoucherCodeLength)).ToList();

                // see if any of the voucher codes we generated already exist in the database
                var existingVouchers = Vouchers.Select(v => v.Code).Where(v => voucherCodes.Contains(v)).ToList();

                // find a voucher code from the list we generated that is not currently being used in the database
                var availableVoucherCode = voucherCodes.Where(v => !existingVouchers.Select(e => e).Contains(v)).FirstOrDefault();

                if (availableVoucherCode != null)
                {
                    Vouchers.InsertOnSubmit(new Voucher { MapGuid = Guid.NewGuid(), Code = availableVoucherCode, Percent = 100, CreatedDate = DateTime.Now }); // entity framework equivalent to entity<T>.Add(T);
                    SubmitChanges(); // entity framework equiavalent to context.SaveChanges();
                    availableVoucherCode.Dump();
                }
                else
                {
                    throw new ArgumentException($"Could not generate {NumberOfVouchersToGenerate} unique codes.");
                }
            }
        }
        catch (Exception ex)
        {
            ex.Dump();
            exceptionThrown = true;
        }
        finally
        {
            if (!exceptionThrown)
                scope.Complete();
        }
    }
}

private const int VoucherCodeLength = 10;
private const int MaxGenerateUniqueVoucherAttempts = 5;
// since Random does not make any guarantees of thread-safety, use different Random instances per thread
private static readonly ThreadLocal<Random> _random = new ThreadLocal<Random>(() => new Random());

// Define other methods and classes here
private static string GenerateCode(int numberOfCharsToGenerate)
{
    char[] chars = "ACDEFGHJKLMNPQRTUVWXYZ234679".ToCharArray(); // uppercase only; remove similar looking characters such as 1IilS5s0Oo etc...

    var sb = new StringBuilder();
    for (int i = 0; i < numberOfCharsToGenerate; i++)
    {
        int num = _random.Value.Next(0, chars.Length);
        sb.Append(chars[num]);
    }
    return sb.ToString();
}

Approach #2: Total execution time ~12 seconds for 1k codes.

void Main()
{
    bool exceptionThrown = false;
    int NumberOfVouchersToGenerate = 1000;
    using (var scope = new TransactionScope())
    {
        try
        {
            // generate a list of voucher codes 0 to N
            List<string> voucherCodes = Enumerable.Range(0, NumberOfVouchersToGenerate)
                .Select(_ => GenerateCode(VoucherCodeLength)).ToList();

            // see if any of the voucher codes we generated already exist in the database
            var existingVouchers = Vouchers.Select(v => v.Code).Where(v => voucherCodes.Contains(v)).ToList();

            if (existingVouchers.Count() == 0)
            {
                foreach (var voucherCode in voucherCodes)
                {
                    Vouchers.InsertOnSubmit(new Voucher { MapGuid = Guid.NewGuid(), Code = voucherCode, Percent = 100, CreatedDate = DateTime.Now }); // entity framework equivalent to entity<T>.Add(T);
                    SubmitChanges(); // entity framework equiavalent to context.SaveChanges();
                    voucherCode.Dump();
                }
            }
            else
            {
                throw new ArgumentException($"Could not generate {NumberOfVouchersToGenerate} unique codes.");
            }
        }
        catch (Exception ex)
        {
            ex.Dump();
            exceptionThrown = true;
        }
        finally
        {
            if (!exceptionThrown)
                scope.Complete();
        }
    }
}

private const int VoucherCodeLength = 10;
// since Random does not make any guarantees of thread-safety, use different Random instances per thread
private static readonly ThreadLocal<Random> _random = new ThreadLocal<Random>(() => new Random());

// Define other methods and classes here
private static string GenerateCode(int numberOfCharsToGenerate)
{
    char[] chars = "ACDEFGHJKLMNPQRTUVWXYZ234679".ToCharArray(); // uppercase only; remove similar looking characters such as 1IilS5s0Oo etc...

    var sb = new StringBuilder();
    for (int i = 0; i < numberOfCharsToGenerate; i++)
    {
        int num = _random.Value.Next(0, chars.Length);
        sb.Append(chars[num]);
    }
    return sb.ToString();
}
\$\endgroup\$
2
  • \$\begingroup\$ What database are you using? sql-server? \$\endgroup\$ Commented Sep 21, 2016 at 18:59
  • \$\begingroup\$ @200_success Yes. SQL Server 2014. \$\endgroup\$ Commented Sep 21, 2016 at 19:12

2 Answers 2

Reset to default
7
\$\begingroup\$

There are numerous problems here.

  • There are 26^10 vouchers in the voucher space, but only 2^32 possible seeds to the random number generator. And the random number generator has a period of a few billion before it repeats. So most of your space cannot be generated. But that's not so bad. There are plenty of numbers which can be generated.

  • The random number generator on the thread is seeded with the current time. Which means that two threads that start at the same millisecond will produce the same sequence of vouchers forever; it is entirely possible that one of the threads will never succeed in producing a voucher that isn't already in the database. If you think that it is impossible for two threads to start in the same millisecond, I remind you that a millisecond is one million nanoseconds, and computers work on the nanosecond scale. There is plenty of opportunity for collision here. But maybe you can live with that.

  • The really horrible problem is: if I have access to one voucher I can run 2^32 simulations of your algorithm on my fast home machine and very quickly determine what the seed was for that instantiation of Random. I now have knowledge of every voucher that was generated by that thread in the past and the future. Do you want to give that information to everyone who has a single voucher? Basically once one voucher is public, the entire database is public.

  • Even if I don't have a voucher, I can run 2^32 simulations of different threads and generate probably vouchers, and try them out. One of them will be the right one.

This is a correctness and security nightmare waiting to happen.

The right way to do this is to generate crypto-strength vouchers. I leave it to you to work out how to do that.

Now let's suppose that you do. What is the probability of a collision given n unique vouchers already in the database? Obviously n / 26^10. If n is under a few million then obviously this is very small. But here's a better question: what is the probability of there being any collision at any time during the computation of those million vouchers? The chance of any collision rises extremely rapidly once the number of the vouchers in the database is on the order of the square root of the sample space. The square root of 26^10 is only 12 million! So you are very likely to get at least one voucher collision if you are putting around 12 million vouchers in the database.

If you want to make that chance of collision smaller, up the voucher size. Every time you add one more digit to the voucher, you multiply the amount of runway you have until a collision is likely by five.

If this subject interests you, see

https://blogs.msdn.microsoft.com/ericlippert/2010/03/22/socks-birthdays-and-hash-collisions/

for more discussion.

Now, if you don't care about any of this stuff, then there is a cheap way to generate random-seeming vouchers without having to store them in a database. Just number your vouchers one through 1000 and use a multiplicative inverse:

https://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/

But these have no security properties whatsoever. If someone knows this algorithm, then they know all the vouchers past present and future. This system is not secure against attack at all; it's just a nice way to "obfuscate" a small number.

UPDATE:

My understanding of new ThreadLocal<Random>(() => new Random()) was that it would generate a new instance of Random in each thread. Is this not correct?

That's correct. And this is the right thing to do, because Random is not threadsafe.

When you say, "I now have knowledge of every voucher that was generated by that thread in the past and the future," do you mean on that particular thread i.e. if 10 codes were generated on a particular batch, and I had access to one, I would then be able to determine the remaining 9?

That is exactly what I mean.

There are only 32 bits of actual randomness in the seed. Which means that there are only four billion possible sequences of vouchers produced by your algorithm. Which means that all I have to do is generate all four billion sequences until I find one that has my voucher, and hey, I now know what seed that thread used. So I know every voucher it generated in the past, and the future.

If that's not a property you care to have, then generate actually random vouchers, not pseudorandom vouchers.

Outside of that batch and thread, would you still be able to determine other codes?

Sure. In particular, I could generate the four billion vouchers that were each generated first by the four billion possible seeds and use those as guesses. Suppose you have generated 1000 vouchers. That gives me odds of one in four million of guessing one of them, once. And of course I can just keep on trying; nothing is stopping me. Compare that to the odds of guessing one of them if they were truly random: 1000 in 26 to the 10, a far larger number.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for this answer it's exactly what I was looking for. My understanding of new ThreadLocal<Random>(() => new Random()) was that it would generate a new instance of Random in each thread. Is this not correct? When you say, "I now have knowledge of every voucher that was generated by that thread in the past and the future," do you mean on that particular thread i.e. if 10 codes were generated on a particular batch, and I had access to one, I would then be able to determine the remaining 9? Outside of that batch and thread, would you still be able to determine other codes? \$\endgroup\$ Commented Sep 26, 2016 at 14:41
  • \$\begingroup\$ @user1477388: You're welcome. I'll address your follow-up questions in an update. \$\endgroup\$ Commented Sep 26, 2016 at 16:58
  • \$\begingroup\$ @user1477388: As the name implies, RNGCryptoServiceProvider is a more secure random number generator than Random. \$\endgroup\$ Commented Sep 26, 2016 at 19:50
0
\$\begingroup\$

My best solution to my own problem is the following:

  • Generate N vouchers into a single list
  • Create a single SQL query to check for existing items in the list of codes
  • If there are no existing items, add all vouchers to a single list of vouchers
  • Insert all on submit

Total execution time: ~1 second for 1k codes

void Main()
{
    bool exceptionThrown = false;
    int NumberOfVouchersToGenerate = 1000;
    List<Voucher> vouchers = new List<Voucher>();
    using (var scope = new TransactionScope())
    {
        try
        {
            // generate a list of voucher codes 0 to N
            List<string> voucherCodes = Enumerable.Range(0, NumberOfVouchersToGenerate)
                .Select(_ => GenerateCode(VoucherCodeLength)).ToList();

            // see if any of the voucher codes we generated already exist in the database
            var existingVouchers = Vouchers.Select(v => v.Code).Where(v => voucherCodes.Contains(v)).ToList();

            if (existingVouchers.Count() == 0)
            {
                foreach (var voucherCode in voucherCodes)
                {
                    vouchers.Add(new Voucher { MapGuid = Guid.NewGuid(), Code = voucherCode, Percent = 100, CreatedDate = DateTime.Now }); // entity framework equivalent to entity<T>.Add(T);
                    voucherCode.Dump();
                }
            }
            else
            {
                throw new ArgumentException($"Could not generate {NumberOfVouchersToGenerate} unique codes.");
            }
        }
        catch (Exception ex)
        {
            ex.Dump();
            exceptionThrown = true;
        }
        finally
        {
            if (!exceptionThrown)
            {
                Vouchers.InsertAllOnSubmit(vouchers);
                SubmitChanges(); // entity framework equiavalent to context.SaveChanges();
                scope.Complete();
            }
        }
    }
}

private const int VoucherCodeLength = 10;
// since Random does not make any guarantees of thread-safety, use different Random instances per thread
private static readonly ThreadLocal<Random> _random = new ThreadLocal<Random>(() => new Random());

// Define other methods and classes here
private static string GenerateCode(int numberOfCharsToGenerate)
{
    char[] chars = "ACDEFGHJKLMNPQRTUVWXYZ234679".ToCharArray(); // uppercase only; remove similar looking characters such as 1IilS5s0Oo etc...

    var sb = new StringBuilder();
    for (int i = 0; i < numberOfCharsToGenerate; i++)
    {
        int num = _random.Value.Next(0, chars.Length);
        sb.Append(chars[num]);
    }
    return sb.ToString();
}
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.