An M-party, N-state Game of Rochambeau
draft-harkins-rochambeau-00

Network Working Group                                         D. Harkins
Internet-Draft                                     The Industrial Lounge
Intended status: Informational                                P. Lambert
Expires: October 3, 2012                                   Nymble Design
                                                           April 1, 2012

                 An M-party, N-state Game of Rochambeau
                      draft-harkins-rochambeau-00

Status of This Memo

   This Internet-Draft is submitted to IETF 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), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   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."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on October 3, 2012.

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.

Harkins & Lambert        Expires October 3, 2012                [Page 1]
Internet-Draft         M-party, N-state Rochambeau            April 2012

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.

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  . . . . . . . . . . . . . . . . . . . . 8

Harkins & Lambert        Expires October 3, 2012                [Page 2]
Internet-Draft         M-party, N-state Rochambeau            April 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 described 25-state games, and even 101 state games.
   These have all typically 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 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 to 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.  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 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

Harkins & Lambert        Expires October 3, 2012                [Page 3]
Internet-Draft         M-party, N-state Rochambeau            April 2012

   winner among mutually distrustful entities.

   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 is described as well as a
   method for each party to commit to a selection of one of the N-states
   before disclosing the chosen state.

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.

   The determination of the winner for a pair of players in the N-state
   game of Rochambeau is described by this algorithm:

Harkins & Lambert        Expires October 3, 2012                [Page 4]
Internet-Draft         M-party, N-state Rochambeau            April 2012

                      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
   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

Harkins & Lambert        Expires October 3, 2012                [Page 5]
Internet-Draft         M-party, N-state Rochambeau            April 2012

   (1) is assigned to a WINNER, minus one (-1) to a LOSER, and a value
   of zero (1) 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.

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:

        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

Harkins & Lambert        Expires October 3, 2012                [Page 6]
Internet-Draft         M-party, N-state Rochambeau            April 2012

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,
   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

Harkins & Lambert        Expires October 3, 2012                [Page 7]
Internet-Draft         M-party, N-state Rochambeau            April 2012

   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.

   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.

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 October 3, 2012                [Page 8]