Simple Random Candidate Selection

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 23 May 2024.¶

Copyright Notice

Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

It is common to need to pick a subset of people from a larger group using a random selection method. This is often done on an ad hoc basis, but for some selections, a more formal process is needed, particularly if the people in the larger group don't all trust the administrator of the selection process to be unbiased.¶

This document gives a simple, understandable process that can be done for groups and subsets of arbitrary size. The process is purposely transparent and reproducible. It works with any group of entities that have names: people, companies, locations, and so on.¶

As a simple example, a future leadership committee will have a fixed size. The members of the committee will be selected from a large pool of volunteers. Someone is in charge of collecting the names of the volunteers and making a randomized selection among them for the leadership committee. They can use the process in this document to make that selection in a way that is both provably random and understandable.¶

As described later in this document, the process can also be used for weighted selections (Section 5) and for randomly sorting lists of candidates (Section 6).¶

Due to the formatting used in this document, the reader is encouraged to read the HTML version, although the text version is still usable.¶

See [I-D.thomson-elegy-vrs] for a similar method as described here.¶

2. Overview of the Process

A few terms are used throughout this document:¶

ceremony:

The act of collecting names into a pool, making a random selection from the pool, and publishing the entire process in a clear and transparent method.¶

ceremony administrator (CA):

The person who performs the steps of the ceremony.¶

candidate:

A person, organization, or other namable entity that is possibly being selected during the ceremony.¶

candidate name:

The name used by each candidate in the pool. The candidate name is expressed as a string of Unicode characters in UTF-8 format [Unicode] [UTF-8].¶

difficult-to-predict string (D):

A publicly-visible string that is only known after the pool of candidates has been closed. (Note that this is different from what is normally called a "random number" or a "random string". True random numbers or strings are designed to be nearly impossible to predict, whereas D in this process has weak but sufficient randomness.)¶

selection size (S):

The number of candidates that will be selected from the pool.¶

3. Specifics for the Process

7623.10

4. Handling Ceremony Process Issues

Ceremonies don't always go as planned. For example, after a ceremony completes, one or more of the selected candidates might be removed from the selected set due to voluntary withdrawal or established rules (such as no two candidates being from the same geographic region). In such cases, no new ceremony is needed: the CA simply selects the next candidate(s) on the list that is ordered by hash values.¶

Similarly, if after the selection process is completed, the size S of the selected set needs to increase, the CA simply selects the next candidate(s) on the list that is ordered by hash values.¶

5. Performing a Weighted Selection of Candidates

In some candidate selections, the CA wants to give candidates a weighted chance of being selected. For example, a legislature might select its leadership randomly, but weights the chance of being selected by the size of the membership of the political party in the legislature. The CA can create the pool with multiple names for each party, giving each name a number.¶

For example, assume a legislature has 27 members of the Orange party, 20 members of the Yellow party, and 7 members of the Green party. The CA could create a pool consisting of the names "Orange1", "Orange2", ... "Orange27", "Yellow1", "Yellow2", ... "Yellow20", "Green1", "Green2", ... "Green7". The selected party would be the one whose name appears in the first name of the list of hashes.¶

6. Performing a Random Ordering of Candidates

Some use cases do not involve a selection of candidates from a larger list, but instead sorting the list of candidates randomly. The process given in this document can be easily used to do this: set S to the size of the pool, peform the steps of the ceremony, and create the output list in the last step as all S candidates in alphabetic order from highest to lowest of the hash values.¶

7. IANA Considerations

This document has no IANA considerations.¶

8. Security Considerations

The value D used in this process is explicitly not cryptographically strong; in fact, it might provide only a few bits of randomness. The FTSE 100 Index might be predictable after the third digit from the right, but not the last three digits, meaning that they only have randomness of about 10 bits. The value of D is concatenated into each candidate string before the whole string is hashed, so incorrectly predicting even one character of D completely changes the value of the hash for comparison.¶

A cryptographic hash function like SHA-256 has the property that changing any individual bit of the input will change every bit in the output with a 50% chance, regardless of the position of the bit in the input. Appending a small amount of randomness at the end of the input is just as effective as prepending the randomness at the beginning of the input nd just as effective as mixing the randomness throughout the input. The procedure in this document appends the string from the FTSE 100 Index at the end of the candidate name because it makes viewing the pre-hashed result easier while still causing the maximum change to the resulting hash value.¶

A candidate who has a lot of leeway in choosing their name can possibly increase their chance of being selected by as much as 0.1% with such source of randomness. The procedure in this document assumes that candidates have very little leeway in choosing their names; the CA must accept each name before it is put into the pool. The combination of the limited leeway for choosing the names in the pool and the necessity to predict D exactly in order to gain any benefit means that D needs much less randomness that a random number that would be used during encryption or authentication.¶

Appendix A. Sample Code

The following is a list of figures for an implementation of the procedure shown in this document.¶

• The Python script in Figure 1 implements the algorithm from this document.¶

• The file that contains the list of names is shown in Figure 2. (The names are the winners of the Nobel laureates in Literature for 2016 through 2021.)¶

• A file showing the UTF-8 representation of the names from Figure 2 is shown in Figure 3. This file is suitable for showing to the candidates.¶

• The file that contains the S and D on separate lines is shown in Figure 4.¶

• Figure 5 shows the result of running the program with that file as input.¶

#!/usr/bin/env python3

# Program to randomly select some candidates from a group
#  See draft-hoffman-random-candidate-selection

import hashlib, sys
from pathlib import Path

# Helper function to turn a UTF-8 string into its hex representation
def hexify(in_str):
  return "".join([hex(c)[2:] for c in in_str.encode("utf8")])

# Sanity check the input files given on the command line
if len(sys.argv) == 1:
  exit("Must give the name of the candidate file, and possibly " + \
    "the selection file, on the command line. Exiting.")
candidate_path = Path(sys.argv[1])
if not candidate_path.exists():
  exit(f"The file {str(candidate_path)} doesn't exist. Exiting.")
try:
  candidate_f = candidate_path.open(mode="rt", encoding="utf8")
except:
  exit("The candidates file doesn't appear to be in UTF-8. Exiting.")
candidate_lines = candidate_f.read().splitlines()
# See if there is a second file for selecting
if len(sys.argv) == 3:
  run_including_selection = True
  selection_path = Path(sys.argv[2])
  if not selection_path.exists():
    exit(f"The file {str(selection_path)} doesn't exist. Exiting.")
  try:
    selection_f = selection_path.open(mode="rt", encoding="utf8")
  except:
    exit("The selection file doesn't appear to be UTF-8. Exiting.")
  selection_lines = selection_f.read().splitlines()
  # Extract D and S from the selection file
  S_str = selection_lines[0]
  try:
    S = int(S_str)
  except:
    print(f"The first line of the selection file, '{S_str}', " + \
      "is not an integer. Exiting.")
  # D_str is the string for D, D_hex is the hex version for display
  D_str = selection_lines[1]
  D_hex = hexify(D_str)
else:
  run_including_selection = False

# Get the candidates information
C_info = []
for C_str in candidate_lines:
  C_hex = hexify(C_str)
  if run_including_selection:
    C_with_D_str = C_str + D_str
    C_with_D_hex = hexify(C_with_D_str)
    C_with_D_hash = hashlib.sha256(C_with_D_hex.encode("utf-8"))
    C_info.append([C_str, C_hex, C_with_D_str, C_with_D_hex, \
      C_with_D_hash.hexdigest()])
  else:
    C_info.append([C_str, C_hex])

# Print the results
if run_including_selection:
  print(f"S is {S}")
  print(f"D is \"{D_str}\"")
  print(f" {D_hex}\n")
  print("Candidate information, sorted by hash of name including D")
  selected = []
  # Sort by the hex of C_with_D_hash
  for this_info in sorted(C_info, key=lambda a: a[4], reverse=True):
    # Decrement S for each name that is selected
    if S > 0:
      selected.append(this_info[0])
      S -= 1
    print(f"{this_info[2]}")
    print(f" {this_info[3]}")
    print(f" {this_info[4]}")
  print("\nSelected:\n    " + "\n    ".join(selected))
else:
  for this_info in C_info:
    print(f"{this_info[0]}")
    print(f" {this_info[1]}")

Bob Dylan
石黒 一雄
Olga Tokarczuk
Peter Handke
Louise Glück
Abdulrazak Gurnah

Bob Dylan
 426f622044796c616e
石黒 一雄
 e79fb3e9bb9220e4b880e99b84
Olga Tokarczuk
 4f6c676120546f6b6172637a756b
Peter Handke
 50657465722048616e646b65
Louise Glück
 4c6f7569736520476cc3bc636b
Abdulrazak Gurnah
 416264756c72617a616b204775726e6168

3
7623.10

S is 3
D is "7623.10"
 373632332e3130

Candidate information, sorted by hash of name including D
石黒 一雄7623.10
 e79fb3e9bb9220e4b880e99b84373632332e3130
 f2e0d3bbd8eac635d799702bead0fbdf07ff79ef94a261789de50e81adb38a13
Louise Glück7623.10
 4c6f7569736520476cc3bc636b373632332e3130
 a54e282cbaa1f29543cd13d9a29e07e3a38413360172b722f8259c2baa3c38dd
Peter Handke7623.10
 50657465722048616e646b65373632332e3130
 8bb3bc197c6462b033e4d8e8cf703b13b1c55172572a85d56c639db5c57d3866
Olga Tokarczuk7623.10
 4f6c676120546f6b6172637a756b373632332e3130
 56166c4e0e6ca027f4150bac5ce83fbf5652e440214fd255308472fed9f8fb1b
Abdulrazak Gurnah7623.10
 416264756c72617a616b204775726e6168373632332e3130
 340413dc6b2574f5ddc5e88e1c986a229d9defccbae249789b07a5d2337981ff
Bob Dylan7623.10
 426f622044796c616e373632332e3130
 05eb403f4f59f5a7b21f5e5a4e8dbfbac59344fd5e8708ab618b5e2ed27a52de

Selected:
    石黒 一雄
    Louise Glück
    Peter Handke

Author's Address