RFC 2777
Publicly Verifiable Nomcom Random Selection
RFC 2777: Publicly Verifiable Nomcom Random Selection 🎀
Part 1 of 3 💖
Okay bestie, this one is from D. Eastlake 3rd at Motorola, published in February 2000 🌸 It's marked Informational, which means it's sharing info with the Internet community and is not a standard. It doesn't list anything it obsoletes or updates, so it's just vibing on its own ✨
Status of this Memo ✨
ngl this section is the fine print. It says this memo provides information for the Internet community, and it does not specify an Internet standard of any kind 🙈 It also says that distribution of this memo is unlimited, so share away 💅
Copyright Notice 🌈
The Internet Society holds the copyright on this one, dated 2000, and all rights are reserved 🧚
Abstract 🦋
Here's the whole idea: this doc describes a way to make random selections where anyone can check that the choice was truly unbiased 👑 The example they use is picking the voting members of the IETF Nominations Committee from the pool of eligible volunteers. Other situations could use the same techniques too 🔥
Acknowledgement 🫶
Matt Crawford made major contributions to this document, so shoutout to him 💜
Table of Contents 🍓
1. Introduction............................................2
2. General Flow of a Publicly Verifiable Process...........2
2.1 Determination of the Pool..............................2
2.2 Publication of the Algorithm...........................2
2.3 Publication of Selection...............................3
3. Randomness..............................................3
3.1 Sources of Randomness..................................3
3.2 Skew...................................................4
3.3 Entropy Needed.........................................4
4. A Suggested Precise Algorithm...........................5
5. Fully Worked Example....................................6
6. Security Considerations.................................7
7. Reference Code.........................................8
Appendix: History of NomCom Member Selection..............14
References................................................15
Author's Address..........................................15
Full Copyright Statement..................................161. Introduction ✨
Okay so under the IETF rules, every year 10 persons get randomly picked from the eligible people who volunteer to be the voting members of the nominations committee (NomCom) 💅 That committee nominates people for the Internet Engineering Steering Group (IESG) and the Internet Architecture Board (IAB) [RFC 2727]. The number of eligible volunteers in recent years has been roughly 40 to 60 🫶
This selection has to be totally unimpeachable, no cap 😭 Nobody should be able to make reasonable claims of bias or favoritism. It protects the IETF from bias, and it also protects the administrator of the selection (currently the appointed non-voting NomCom chair) from looking suspicious 🌸
A method where public information lets anyone verify that the selection was random totally hits that bar 🔥 This document shows an example of one.
2. General Flow of a Publicly Verifiable Process 🦋
Here's the general vibe. A selection of NomCom members that anyone can publicly verify as unbiased (or something similar) can follow the three steps below 🎀
2.1 Determination of the Pool 💖
First things first, you need to figure out the pool the selection gets made from 🧚
The appointed (non-voting) NomCom chair goes out and asks for volunteers. Then the names get passed through the IETF Secretariat to check eligibility. Current eligibility criteria are about IETF meeting attendance, and the Secretariat keeps those records 📋 The full list of eligible volunteers gets made public early enough that there's a reasonable amount of time to sort out any drama about who should be in the pool, probably a week to ten days before the selection 👑
2.2 Publication of the Algorithm 🌈
The exact algorithm gets made public, including the future sources of randomness 💅 Here's how it works. The eligible volunteers on the final list get ordered by being publicly numbered. Several public future sources of randomness, like government run lotteries, get specified. Then an exact algorithm is specified that picks eligible volunteers based on a strong hash function [RFC 1750] applied to those future sources of randomness 🔥
2.3 Publication of Selection ⭐
Once the prespecified sources of randomness produce their output, those values should be announced, along with a summary of how the algorithm was run for the selection 🫶 That way anyone can check that the correct randomness values were used and that the algorithm was executed properly 🙈
A cut-off time should also be set for any complaint that the algorithm was run with the wrong inputs or wasn't faithfully executed 😭 That's what finalizes the output and gives us a stable NomCom 💜
3. Randomness 🧚
The whole reason this is unbiased is that it's based on random information that gets revealed in the future 🔮 That means nobody who specifies the algorithm can know the outcome ahead of time. It's giving fairness. The random information also has to get publicly revealed in a timely fashion 💖
The random sources should not include anything a reasonable person would think is under the control or influence of the IETF or its components 🙅♀️ So no IETF meeting attendance statistics, no counts of documents issued, stuff like that 🎀
3.1 Sources of Randomness 🌸
Good information to use includes lottery winning numbers from specified runs of specified lotteries 🍀 Government run lotteries especially get a lot of care to make sure they produce random quantities 👑 Even if one were somehow rigged, it would almost certainly be tied to winning money in the lottery, not to IETF use 💅
Other options include things like the closing price of a stock on a particular day, the daily balance in the US Treasury on a specified day, the volume of trading on the New York Stock Exchange on a specified day, and so on 📈 (Heads up: the reference code given below won't handle integers that are too large 🙈) Sporting events can be used, but you have to be super careful about specifying exactly which quantities are presumed random and what happens if they get cancelled or delayed 😭
The last source of randomness, chronologically, needs to produce a substantial amount of the entropy needed 🔥 If most of the randomness came from the earlier sources, and someone has even limited influence over the final source, they could do an exhaustive analysis and use that influence to bias the selection the way they wanted. So it's best for the last source to be an especially strong and unbiased source of a large amount of randomness, like a government run lottery 💖
It's also best not to use too many different sources 🧚 Every additional source increases the chance that it gets delayed or cancelled, which calls contingency plans into play. Or worse, it could create a situation nobody anticipated 😬 That would either require arbitrary judgment from the NomCom chair (which defeats the randomness of the selection) or a re-run with a new set of sources, which causes a lot of delay 🫠 Probably a good number of sources is three ✨
3.2 Skew 🌈
Lots of the sources of randomness suggested above produce data that isn't uniformly distributed 📉 That's definitely true of stock prices and horse race results, for example 🐎 But using a strong mixing function [RFC 1750] will extract the available entropy and produce a hash value whose bits, remainder modulo a small divisor, and so on, are uniformly distributed 🦋
3.3 Entropy Needed 💜
What we're doing is selecting N items without replacement from a population of P items 🎀 The number of different ways to do that is shown below, where "!" represents the factorial function 🧮
P!
-------------
N! * (P - N)!To do this in a completely random fashion, you need as many random bits as the logarithm base 2 of that quantity 🔥 Here are some sample approximate numbers of random bits needed to select 10 NomCom members from various pool sizes 💅
Random Selection of Ten Items From Pool
Pool size 20 25 30 35 40 50 60 75 100
Bits needed 18 22 25 28 30 34 37 40 44Using an inadequate number of bits means not all of the possible selections would be available 😭 If there's a substantially inadequate amount of entropy, you'd get substantial correlations between the selection of two members of the pool, for example 🙈 But as a practical matter, for pool sizes likely to show up in IETF NomCom membership selection, 40 bits of entropy should always be adequate 💖 Even if there's a large pool and theoretically more bits are needed for complete randomness, 40 bits will make sure the probability of selecting each pool member differs from that of the other members, and the correlation between any pair of pool members, and so on, differs only insignificantly from completely random selection 🌸
An MD5 [RFC 1321] hash has 128 bits, so it can't produce more than that many bits of entropy 🧚 That said, this is three times what's likely to ever be needed for IETF NomCom membership selection 👑✨
4. A Suggested Precise Algorithm ✨
okay bestie, we need a precise algorithm for mixing the random sources and making the selection from them 🔥 no vibes-based picking allowed. The sources we talked about each give either one positive number (like a stock's closing price) or a small set of positive numbers (lotteries usually give 6 numbers from 1 to 40, a sporting event gives the scores of two teams, etc.). Here's a sample precise algorithm 💅
For each source that gives multiple numeric values, write each value as a decimal number ending in a period (or with a period between the whole part and the fractional part). No leading zeroes, except one leading zero if the integer part is zero, and no trailing zeroes after the period 🎀 Then sort them from smallest to largest, stick them together, and end with a "/". For a source that gives a single number, do the same thing, just with a trailing "/". Now every source has its own string, say s1/, s2/, and so on. Join those strings together in a pre-specified order, and turn each character into its ASCII code, giving s1/s2/.../. 🦋
Next, you get a sequence of random values by mixing all these sources together with the MD5 hash [RFC 1321] 🧚 Hash the string with a zero byte added before and after it for the first value, a 0x01 byte before and after it for the second value, and so on. Treat each derived value as a positive multiprecision integer.
If there are P eligible volunteers, pick the first voting member by dividing the first derived random value by P. The remainder plus one is the position of the selectee in the ordered list of volunteers 🌸 Pick the second voting member by dividing the second derived random value by P-1, and use the remainder plus one as the position in the list with the first selectee taken out. Keep going the same way for the rest. 💖
It's recommended that alphanumeric random sources be avoided, because they're much harder to canonicalize in a way that anyone can repeat independently 🙈 But if you do use any, remove all white space, punctuation, and special characters, and set every letter to upper case. That leaves only an unbroken run of letters A-Z and digits 0-9, which you treat as a canonicalized number like above and end with a "/".
5. Fully Worked Example 🎀
okay the example is where it all clicks, so let's go 👑 Assume this ordered list of 25 eligible volunteers gets published before the selection:
1. John 11. Pollyanna 21. Pride
2. Mary 12. Pendragon 22. Sloth
3. Bashful 13. Pandora 23. Envy
4. Dopey 14. Faith 24. Anger
5. Sleepy 15. Hope 25. Kasczynski
6. Grouchy 16. Charity
7. Doc 17. Love
8. Sneazy 18. Longsuffering
9. Handsome 19. Chastity
10. Cassandra 20. SmithNow assume this ordered list of randomness sources. It's a fake example, so no stressing 😭
- The People's Democracy of Betastani State Lottery six winning numbers (ignoring the seventh "extra" number) for 1 October 1998.
- Numbers of the winning horses at Hialeia for all races for the first day on or after x September 1998 on which at least two races are run.
- The Republic of Alphaland State Lottery daily number for 1 October 1998, treated as a single four digit integer.
- Closing price of Example Corporation stock on the Lunar Stock Exchange for the first business day after x September 1998 when it trades.
Here's the randomness that got publicly produced 🌈
Source 1: 9, 18, 26, 34, 41, 45
Source 2: 2, 5, 12, 8, 10
Source 3: 9319
Source 4: 13 11/16And the resulting key string, which is the whole vibe 🍓
9.18.26.34.41.45./2.5.8.10.12./9319./13.6875/The table below shows the hex of the MD5 of that key string, bracketed with a byte that goes 0x00, 0x01, 0x02, all the way through 0x09 💜 There's also the divisor for the size of the remaining pool at each stage, and the index of the selectee counted against the original numbering of everyone still in the pool. 😭✨
index hex value of MD5 div selected
1 746612D0A75D2A2A39C0A957CF825F8D 25 -> 12 <-
2 95E31A4429ED5AAF7377A15A8E10CD9D 24 -> 6 <-
3 AFB2B3FD30E82AD6DC35B4D2F1CFC77A 23 -> 8 <-
4 06821016C2A2EA14A6452F4A769ED1CC 22 -> 3 <-
5 94DA30E11CA7F9D05C66D0FD3C75D6F7 21 -> 2 <-
6 2FAE3964D5B1DEDD33FDA80F4B8EF45E 20 -> 24 <-
7 F1E7AB6753A773EFE46393515FDA8AF8 19 -> 11 <-
8 700B81738E07DECB4470879BEC6E0286 18 -> 19 <-
9 1F23F8F8F8E5638A29D332BC418E0689 17 -> 15 <-
10 61A789BA86BF412B550A5A05E821E0ED 16 -> 22 <-And the final selection, in the order it was picked 🏆
1. Pendragon (12) 6. Anger (24)
2. Grouchy (6) 7. Pollyanna (11)
3. Sneazy (8) 8. Chastity (19)
4. Bashful (3) 9. Hope (15)
5. Mary (2) 10. Sloth (22)6. Security Considerations 🔐
this section is seriously important, so pay attention 😤 Choose the randomness inputs very carefully, so there's no reasonable suspicion that the administrator controls them. The guidance from above still applies: use a small number of inputs that each carry a lot of entropy, and especially from the last one 💀 You also have to be just as careful that the algorithm is carried out faithfully with the chosen input values. Publishing the results and giving the wider community of interest a week or so to repeat the calculations is a reasonable way to guard against tampering with the implementation 🛡️
To keep the selections unpredictable, if a member of the nomcom has to be replaced because of death, resignation, expulsion, or anything like that, new publicly announced future random sources should be used to select the replacement 🌙
7. Reference Code ✨
okay bestie, this is the good stuff 💻🎀 the reference code is built on the MD5 reference code from [RFC 1321] ("RSA Data Security, Inc. MD5 Message-Digest Algorithm"), and the multiple floating point part was written by Matt Crawford 🫶
/****************************************************************
*
* Reference code for
* "Publicly Verifiable Nomcom Random Selection"
* Donald E. Eastlake 3rd
*
****************************************************************/
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "global.h"
#include "MD5.h"
/* local prototypes */
int longremainder ( unsigned char divisor,
unsigned char dividend[16] );
int getinteger ( char *string );
double NPentropy ( int N, int P );
/* limited to 16 inputs of up to sixteen integers each */
/****************************************************************/
main ()
{
int i, j, k, k2, err, keysize, pool, selection;
unsigned char unch, uc16[16], remaining, *selected;
long int temp, array[16];
MD5_CTX ctx;
char buffer[257], key [800], sarray[16][256];
pool = getinteger ( "Type size of pool:\n" );
if ( pool > 255 )
{
printf ( "Pool too big.\n" );
exit ( 1 );
}
selected = (unsigned char *) malloc ( pool );
if ( !selected )
{
printf ( "Out of memory.\n" );
exit ( 1 );
}
selection = getinteger ( "Type number of items to be selected:\n" );
if ( selection > pool )
{
printf ( "Pool too small.\n" );
exit ( 1 );
}
if ( selection == pool )
{
printf ( "All of the pool is selected.\n" );
exit ( 0 );
}
err = printf ( "Approximately %.1f bits of entropy needed.\n",
NPentropy ( selection, pool ) + 0.1 );
if ( err <= 0 ) exit ( 1 );
for ( i = 0, keysize = 0; i < 16; ++i )
{
if ( keysize > 500 )
{
printf ( "Too much input.\n" );
exit ( 1 );
}
/* get the "random" inputs. echo back to user so the user may
be able to tell if truncation or other glitches occur. */
err = printf (
"\nType #%d randomness or 'end' followed by new line.\n"
"Up to 16 integers or the word 'float' followed by up\n"
"to 16 x.y format reals.\n", i+1 );
if ( err <= 0 ) exit ( 1 );
gets ( buffer );
j = sscanf ( buffer,
"%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld",
&array[0], &array[1], &array[2], &array[3],
&array[4], &array[5], &array[6], &array[7],
&array[8], &array[9], &array[10], &array[11],
&array[12], &array[13], &array[14], &array[15] );
if ( j == EOF )
exit ( j );
if ( !j )
if ( buffer[0] == 'e' )
break;
else
{ /* floating point code by Matt Crawford */
j = sscanf ( buffer,
"float %ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]"
"%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]"
"%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]"
"%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]",
&array[0], sarray[0], &array[1], sarray[1],
&array[2], sarray[2], &array[3], sarray[3],
&array[4], sarray[4], &array[5], sarray[5],
&array[6], sarray[6], &array[7], sarray[7],
&array[8], sarray[8], &array[9], sarray[9],
&array[10], sarray[10], &array[11], sarray[11],
&array[12], sarray[12], &array[13], sarray[13],
&array[14], sarray[14], &array[15], sarray[15] );
if ( j == 0 || j & 1 )
printf ( "Bad format." );
else {
for ( k = 0, j /= 2; k < j; k++ )
{
/* strip trailing zeros */
for ( k2=strlen(sarray[k]); sarray[k][--k2]=='0';)
sarray[k][k2] = '\0';
err = printf ( "%ld.%s\n", array[k], sarray[k] );
if ( err <= 0 ) exit ( 1 );
keysize += sprintf ( &key[keysize], "%ld.%s",
array[k], sarray[k] );
}
keysize += sprintf ( &key[keysize], "/" );
}
}
else
{ /* sort values, not a very efficient algorithm */
for ( k2 = 0; k2 < j - 1; ++k2 )
for ( k = 0; k < j - 1; ++k )
if ( array[k] > array[k+1] )
{
temp = array[k];
array[k] = array[k+1];
array[k+1] = temp;
}
for ( k = 0; k < j; ++k )
{ /* print for user check */
err = printf ( "%ld ", array[k] );
if ( err <= 0 ) exit ( 1 );
keysize += sprintf ( &key[keysize], "%ld.", array[k] );
}
keysize += sprintf ( &key[keysize], "/" );
}
} /* end for i */
/* have obtained all the input, now produce the output */
err = printf ( "Key is:\n %s\n", key );
if ( err <= 0 ) exit ( 1 );
for ( i = 0; i < pool; ++i )
selected [i] = i + 1;
printf ( "index hex value of MD5 div selected\n" );
for ( unch = 0, remaining = pool;
unch < selection;
++unch, --remaining )
{
MD5Init ( &ctx );
MD5Update ( &ctx, &unch, 1 );
MD5Update ( &ctx, (unsigned char *)key, keysize );
MD5Update ( &ctx, &unch, 1 );
MD5Final ( uc16, &ctx );
k = longremainder ( remaining, uc16 );
/* printf ( "Remaining = %d, remainder = %d.\n", remaining, k ); */
for ( j = 0; j < pool; ++j )
if ( selected[j] )
if ( --k < 0 )
{
printf ( "%2d "
"%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X "
"%2d -> %2d <-\n",
unch+1, uc16[0],uc16[1],uc16[2],uc16[3],uc16[4],uc16[5],uc16[6],
uc16[7],uc16[8],uc16[9],uc16[10],uc16[11],uc16[12],uc16[13],uc16[14],
uc16[15], remaining, selected[j] );
selected[j] = 0;
break;
}
}
printf ( "\nDone, type any character to exit.\n" );
getchar ();
return 0;
}
/* prompt for an integer input */
/****************************************************************/
int getinteger ( char *string )
{
int i, j;
char tin[257];
while ( 1 )
{
printf ( string );
printf ( "(or 'exit' to exit) " );
gets ( tin );
j = sscanf ( tin, "%d", &i );
if ( ( j == EOF )
|| ( !j && ( ( tin[0] == 'e' ) || ( tin[0] == 'E' ) ) )
)
exit ( j );
if ( j == 1 )
return i;
} /* end while */
}
/* get remainder of dividing a 16 byte unsigned int
by a small positive number */
/****************************************************************/
int longremainder ( unsigned char divisor,
unsigned char dividend[16] )
{
int i;
long int kruft;
if ( !divisor )
return -1;
for ( i = 0, kruft = 0; i < 16; ++i )
{
kruft = ( kruft << 8 ) + dividend[i];
kruft %= divisor;
}
return kruft;
} /* end longremainder */
/* calculate how many bits of entropy it takes to select N from P */
/****************************************************************/
/* P!
log ( ----------------- )
2 N! * ( P - N )!
*/
double NPentropy ( int N, int P )
{
int i;
double result = 0.0;
if ( ( N < 1 ) /* not selecting anything? */
|| ( N >= P ) /* selecting all of pool or more? */
)
return 1.0; /* degenerate case */
for ( i = P; i > ( P - N ); --i )
result += log ( i );
for ( i = N; i > 1; --i )
result -= log ( i );
/* divide by [ log (base e) of 2 ] to convert to bits */
result /= 0.69315;
return result;
} /* end NPentropy */Appendix: History of NomCom Member Selection 🕰️👑
okay this is the tea ☕ for reference purposes, here's the list of the IETF Nominations Committee member selection techniques and chairs so far 🧚
YEAR CHAIR SELECTION METHOD
1993/1994 Jeff Case Clergy
1994/1995 Fred Baker Clergy
1995/1996 Guy Almes Clergy
1996/1997 Geoff Huston Spouse
1997/1998 Mike St.Johns Algorithm
1998/1999 Donald Eastlake 3rd This Algorithm
1999/2000 Avri Doria This AlogrithmClergy = names got written on pieces of paper, dropped in a receptacle, and a member of the clergy picked the Nomcom members 📜✨
Spouse = same as Clergy, except the chair's spouse made the selection 💍
Algorithm = algorithmic selection based on the same concepts as documented herein 🧮
This Algorithm = algorithmic selection using the algorithm and reference code (but not the fake example sources of randomness) described herein 🦋 the vibes are immaculate
References 📚
- RFC 1321: Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992.
- RFC 1750: Eastlake, D., 3rd, Crocker, S. and J. Schiller, "Randomness Recommendations for Security", RFC 1750, December 1994.
- RFC 2727: Galvin, J., "IAB and IESG Selection, Confirmation, and Recall Process: Operation of the Nominating and Recall Committees", BCP 10, RFC 2727, February 2000.
Author's Address 💌
Donald E. Eastlake, 3rd
Motorola
65 Shindegan Hill Road, RR #1
Carmel, NY 10512 USA
Phone: +1-914-276-2668 (h)
+1-508-261-5434 (w)
Fax: +1-508-261-4447 (w)
EMail: Donald.Eastlake@motorola.comFull Copyright Statement ©
okay legal time, but it's still important 🫶 here's the full copyright statement, word for word:
Copyright (C) The Internet Society (2000). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement 🌈
Funding for the RFC Editor function is currently provided by the Internet Society. Thank you, Internet Society, you're literally keeping the lights on 💖
📦 where this page comes from
- ietf: rfc2777 2000-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms