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 30 November 2023.¶

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 nave names: people, companies, locations, dates ("18 August 2022"), 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.¶

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

2. Overview of the Process

A few terms are used throughout this document:¶

ceremony:

The act of collecting names, making the random selection, and publishing the entire process.¶

ceremony administrator (CA):

The person who performs the steps of the ceremony.¶

candidate:

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

candidate name:

The name selected by each candidate for the selection process. The candidate name is expressed as a string of Unicode characters [Unicode] in UTF-8 format [UTF-8].¶

difficult-to-predict number (D):

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

3. Specifics for the Process

4. Handling 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.¶

(Note that the process in this document is quite different than that in [NomCom] and [NomCom-bis], where unselecting an already-selected candidate can cause a new random selection for all the remaining candidates. Such reestablishing of the candidate pool can cause confusion and hurt among the candidates who were first selected, then later unselected, due to no fault of the their own.)¶

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. 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-genarea-reandom-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")])

# Santity 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)} does not exist. Exiting.")
try:
  file_contents = candidate_path.open(mode="rt", encoding="utf8")
except:
  exit("The candidates file do not appear to be in UTF-8. Exiting.")
candidate_lines = file_contents.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)} does not exist. Exiting.")
  try:
    file_contents = selection_path.open(mode="rt", encoding="utf8")
  except:
    exit("The selection file does not appear to be UTF-8. Exiting.")
  selection_lines = file_contents.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 = selection_lines[1]
  D_hex = hexify(D_str)
else:
  run_including_selection = False

# Get the candidates information
C_info = []
c_names = candidate_lines
diff_set = set()
for C_str in c_names:
  C_hex = "".join([hex(c)[2:] for c in C_str.encode("utf8")])
  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" U+{D_hex}\n")
  print("Candidate information, sorted by hash of name including D")
  selected = []
  for this_info in sorted(C_info, key=lambda a: a[4], reverse=True):
    if S > 0:
      selected.append(this_info[0])
      S -= 1
    print(f"{this_info[2]}")
    print(f" U+{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" U+{this_info[1]}")

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

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

3
7623.10

S is 3
D is "7623.10"
 U+373632332e3130

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

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

6. IANA Considerations

This document has no IANA considerations.¶

7. 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. For example, stock indexes that contain many stocks might be predictable after the third digit from the right, meaning that they only have randomness of about 10 bits. 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. If the CA feels that candidates have too much leeway in selecting their names and is concerned about candidates gaming the ceremony even to that tiny extent, that CA needs to choose a source for D with more randomness.¶

Such selection is outside the scope of this document because it would make the process more complicated or less understandable. Instead, this document relies on the CA to only allow sensible representation of candidate names and to accept a tiny chance that candidates can both predict D and be able to change the name they use to reflect that predicted value.¶

Author's Address