Network Working Group D. Harkins Internet-Draft The Industrial Lounge Intended status: Informational P. Lambert Expires: April 4, 2013 Nymble Design October 1, 2012 An M-party, N-state Game of Rochambeau draft-harkins-rochambeau-01 Abstract A protocol for the fair selection and random distribution of a single winner in a game with an arbitrary number of players is described. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, except to format it for publication as an RFC or to translate it into languages other than English. 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 http://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 April 4, 2013. Copyright Notice Copyright (c) 2012 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 (http://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 Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as Harkins & Lambert Expires April 4, 2013 [Page 1] Internet-Draft M-party, N-state Rochambeau October 2012 described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Requirements Language . . . . . . . . . . . . . . . . . . . . . 4 3. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. The Rochambeau Protocol . . . . . . . . . . . . . . . . . . . . 4 4.1. The N-state Game of Rochambeau . . . . . . . . . . . . . . 4 4.2. Adding M-players to the N-state Game of Rochambeau . . . . 5 4.3. Construction of a Commit . . . . . . . . . . . . . . . . . 6 4.4. Processing of a Commit . . . . . . . . . . . . . . . . . . 7 4.5. Construction of a Reveal . . . . . . . . . . . . . . . . . 7 4.6. Processing of a Reveal . . . . . . . . . . . . . . . . . . 7 5. Security Considerations . . . . . . . . . . . . . . . . . . . . 8 6. Informative References . . . . . . . . . . . . . . . . . . . . 9 Harkins & Lambert Expires April 4, 2013 [Page 2] Internet-Draft M-party, N-state Rochambeau October 2012 1. Introduction Paper, Rock, Scissors, or the functional equivalent, is a children's game played in a wide variety cultures. It enables 2 people to randomly select a winner (equivalently, a loser) by selecting 1 of three objects, each of which "wins" against another object and "loses" against another. For example, "paper covers (wins) rock, rock crushes (wins) scissors, and scissors cuts (wins) paper." Provided the 2 players do not select the same object, a winner (loser) is determined. In the event of a tie where both players select the same object, the game is repeated until there is a winner (loser). This game is colloquially referred to as "Rochambeau". Popular American culture has expanded this 3-state game into 5 with the addition of the objects "Spock" and "lizard" along with the new rules that Spock smashes scissors (win) and vaporizes rock (win) while he is poisoned by lizard (lose) and disproven by paper (lose), and that lizard poisons Spock (win) and eats paper (win) while being crushed by rock (lose) and decapitated by scissors (lose). Other obsessives have graphically described 25-state games, and even 101 state games but these have all been done for illustration only and have not been practical as actual games. Rochambeau is typically played to determine a winner and loser of a situation where an impartial arbiter is not available and agreement on winners and losers cannot be agreed to. For instance, "I buy, you fly" may be responded to with "No, I buy and you fly". To determine which party buys and which party flys it is necessary to perform a simple game of 2-party, 3-state Rochambeau, the winner buys and the loser flys. By increasing the number of states of Rochambeau the probability of a tie is decreased. In addition, increasing the number of states introduces the possibility of having more parties play the game. Five people eating dinner can choose who picks up the check by playing a game of 17 state Rochambeau, for instance. The utility of arbitrary sized games of Rochambeau played by humans is limited. It also becomes increasingly problematic as the number of players and states increases. But computers can easily handle the complexity of an M-party and N-state game of Rochambeau. The proliferation of hand-held computing devices such as mobile phones and tablets means that people are increasingly able to engage in M-party, N-state games of Rochambeau quite easily using their personal and portable computing devices. In addition, computers have many uses for determining winners (losers). For instance, selection of a designated router among a group of candidates; or choosing a controller among a set of meshed networking nodes. Typically this arbitrary choice has been decided by something like MAC address or IP address (the higher wins, the lower loses) but with this scheme the Harkins & Lambert Expires April 4, 2013 [Page 3] Internet-Draft M-party, N-state Rochambeau October 2012 result ends up skewed-- one party is going to always end up the winner. What is needed is a way to have a more uniform distribution of winners across distinct games and, since there is no mutually- trusted arbiter, a way to randomly select the winner among mutually distrustful entities (distrustful from the point of view of picking the winner). A protocol is described in this memo that allows for the creation of M-party, N-state games of Rochambeau. A method of determining the winner between any 2 of the M parties and a technique of combining this 2 party determination to all M parties is described. The protocol consists of each party committing to a selection of one of the N-states before disclosing the chosen state to all other M-1 parties. 2. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 3. Assumptions The following assumptions MUST hold for every game of M-party, N-state Rochambeau: o The size of the game, that is N, and the number of players, M, are known to every player prior to the beginning of the game. o The size of the game, N is an odd number. o A hash function, denoted here as H, with strong first pre-image resistance (see Section 5) is agreed upon by all M players prior to the beginning of the game. o Each player knows how to communicate with every other player in the game. This can be a multicast group or a full-M player mesh of pairwise connections or any other technique imaginable. 4. The Rochambeau Protocol 4.1. The N-state Game of Rochambeau At the core of the protocol is a single game of N-state Rochambeau between two players. The result of the game is either WIN, LOSE, or TIE. For any two players, i and j, and N-state game of Rochambeau R, if R(i,j,N) produces WIN then R(j,i,N) MUST produce LOSE, and if R(i,j,N) produces TIE then R(j,i,N) MUST also produce TIE. To play the single game of N-state Rochambeau, the players, i and j, generate unsigned integers less than N, called I and J, respectively and play the game. Harkins & Lambert Expires April 4, 2013 [Page 4] Internet-Draft M-party, N-state Rochambeau October 2012 The determination of the winner for a pair of players in the N-state game of Rochambeau is described by this algorithm: Rochambeau (I, J, N) { if (I == J) return TIE; if (is_odd((J - I) modulo N)) return WINNER; else return LOSER; } where is_odd(x) is true if the low order bit of x is one (1) Figure 1: N-state Rochambeau 4.2. Adding M-players to the N-state Game of Rochambeau The number of states of a game MUST be an odd number and SHOULD be large enough so that the probability of multiple players selecting the same state is acceptablly small. The probability that a 2 players in a game of 2-player, N-state Rochambeau result in a tie is 1/N. The number of players and states for an M-Player, N-State game of Rochambeau MUST be fixed before beginning of the game. The game may begin anytime after the fixing of M and N. The game consists of each player choosing a state, 0 < q < N, generating a Commit and sending it to every other player in the game while also receiving Commits from every other player in the game. After all Commits have been sent, each player then sends a Reveal to every other player in the game while also receiving Reveals from every other player in the game. Each Reveal discloses the state that the sender of the Reveal chose. At this time the game is declared over and (a) winner(s) is (are) determined. It MAY be necessary to call a halt to either the Commit phase or the Reveal phase of the protocol to prevent one or more players from preventing the completion of the game by the other players. If a time limit is employed for one phase, a time limit MUST also be employed for the other, although the limits MAY be different. Any player that does not send a Commit prior to expiry of a Commit time limit, or any player that does not send a Reveal (after sending a Commit) prior to expiry of a Reveal time limit, MUST be excluded from the game. Winners are determined by each party evaluating how it performed in Harkins & Lambert Expires April 4, 2013 [Page 5] Internet-Draft M-party, N-state Rochambeau October 2012 the N-state game of Rochambeau with every other player as well as how every other player performed in the N-state game of Rochambeau with every other player (including itself). To do this, a value of one (1) is assigned to a WINNER, minus one (-1) to a LOSER, and a value of zero (0) to a TIE, and the wins, losses and ties are summed to produce a single score. This summing and scoring is done for all M-1 games of all M players. The player(s) that scored the highest in its (their) sum of games is (are) declared "winner(s)". If there are K winners and K > one (1), then an N-state, K-player game of Rochambeau is played among them. This process-- K players summing the K-1 games of N-party Rochambeau, sorting, selecting (a) winner(s)-- until K = one (1). At that point the winner of the game has been identified. Upon completion of any game where there are more than one winner, the next game involving all K > one (1) winners MUST begin immediately. 4.3. Construction of a Commit To construct a Commit, MUST first convert his chosen state selection, q, into an octet string, called M, of length m such that 2^(8m) > N, the number of states in the game. This is done according to the Integer-to-Octet-String conversion technique of [RFC6090]. This encoding guarantees that all states will be represented in the same number of octets, with as many zero octets as needed to pad up to length m. After converting q into an octet string, M of length m, the player chooses a random string which SHOULD be at least 16 octets in length and passes the nonce and M to function H to produce output C: C = H(nonce, M) The bitlength of C will be known because all parties agreed to use H as the hash algorithm and the length of M will be known because it is tied to the value N (see the octet string conversion above) which all parties agreed to. A Commit is then constructed as: Harkins & Lambert Expires April 4, 2013 [Page 6] Internet-Draft M-party, N-state Rochambeau October 2012 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload type=Commit | length of nonce | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | nonce... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | C... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ where the nonce begins at the 5th octet and C immediately follows the nonce and is not necessarily left-justified to the 0th bit position. Commit payload 4.4. Processing of a Commit The recipient of a Commit extracts the nonce and C-value from the Commit payload and stores it along with any identifying information to disambiguate the sender from other players in the game. 4.5. Construction of a Reveal A Reveal contains q, the state chosen as part of a Commit. Each player in the game constructs a reveal using the value it used in construction of its own Commit. The state q SHALL be converted into an octet string, M, of length of m such that 2^(8m) > N, the number of states in the game-- the same as used in construction of the Commit. Since all players of the game know the value N they will all implicitly know the length m and therefore it is not necessary to convey the length of the octet string representation of q. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload type=Reveal | M... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reveal payload 4.6. Processing of a Reveal For every received Reveal, the receipient SHALL look up the nonce and C-value it obtained in a Commit that is identified with the sender of the Reveal-- each Reveal MUST be accompanied with a previous Commit. If a Reveal is received for which there was no corresponding Commit, Harkins & Lambert Expires April 4, 2013 [Page 7] Internet-Draft M-party, N-state Rochambeau October 2012 it MUST be discarded. The recipient of the Reveal SHALL then produce a verifier for the C-value, called C', as follows: C' = H(nonce, M) Where nonce is from the corresponding Commit and M is from the received Reveal. If C' is not equal to the the value C from the corresponding Commit, the sender of the Reveal is disqualified from the game from the perspective of the receiver of the Commit. It is assumed every other player in the game will disqualify the sender of the Reveal for exactly the same reason. If C' equals C from the corresponding Commit then the receipient of the Reveal SHALL convert the octet string, M, from the Reveal into an integer according to the Octet- String-to-Integer conversion technique of [RFC6090] and denote the integer x. If the value x is invalid-- if x < 1 or x >= N-- then the sender SHALL be disqualified from the game and the game SHALL be run as if it is an M-1 game. The receipient of the Reveal SHALL then run the N-state game of Rochambeau with its own selected state q and the converted state of the sender of the Commit/Reveal, x: value = Rochambeau(q, x, N) The result of the game-- WINNER, LOSER, or TIE-- SHALL be converted into a numeric result-- one (1), minus one (-1), or zero (0), respectively-- and summed with the results from the playing the N-state game of Rochambeau with every other player (see Section 4.2). 5. Security Considerations Each party commits to a state selection depending on the size of the game. For an adversary to gain an advantage in this game it would be necessary to find more than one value for M, called M(1)...M(i) that when hashed with the nonce would produce the same value C. The more more values that hash to C the greater the adversarial advantage. This difficulty of successful attack is identical to the difficulty in finding collisions in the chosen hash algorithm. It is therefore REQUIRED to use a cryptographic hash function with strong collision resistance. Harkins & Lambert Expires April 4, 2013 [Page 8] Internet-Draft M-party, N-state Rochambeau October 2012 In any N-state game of Rochambeau, for every chosen value q such that 0 < q > N there will be exactly (N-1)/2 other values that "win" against q and (N-1)/2 other values that "lose" against q. Therefore, without knowledge of the choices of any of the other M-1 players in the game, there is no advantage that can be gained by choosing a particular value. 6. Informative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic Curve Cryptography Algorithms", RFC 6090, February 2011. Authors' Addresses Dan Harkins The Industrial Lounge EMail: dharkins@lounge.org Paul Lambert Nymble Design EMail: paul@nymbus.net Harkins & Lambert Expires April 4, 2013 [Page 9]