barajar una baraja

Cifrado conmutativo:

Alice y Bob quieren barajar una baraja de cartas, de modo que ninguno sepa lo que contiene la mano del otro, pero las manos están separadas (es decir, solo uno puede tener una carta en particular).

Protocolo:

Alice y Bob deciden un protocolo de encriptación con las siguientes características

1. E _K (X) es X cifrado con clave K
2. D _K [ E _K (X) ] = X para todo K y X
3. mi _k [ mi _j (x) ] = mi _j [ mi _k (x) ]
   • es decir , E(X) es conmutativo
4. Dados X y E _K (X) , es computacionalmente imposible derivar K
5. Dados X e Y , J y K tales que E _J (X) = E _K (Y) no se pueden encontrar
   • es decir , E(x) es resistente a colisiones

Ahora que Alice y Bob tienen un esquema de cifrado:

1. Bob toma las cincuenta y dos tarjetas ( "2C","3C",..."AS" ) y cifra cada una con la clave B
2. Bob baraja las cartas encriptadas en orden aleatorio y le envía el mazo a Alice.
   • Alice no puede ver las cartas, ya que no conoce B
3. Alice selecciona cinco cartas y se las devuelve a Bob.
   • Esta es la mano de Bob. Bob puede ver estas cartas, ya que conoce B
4. Alice le envía cinco tarjetas más a Bob, pero primero las cifra con la clave A.
   • Cada tarjeta ahora está encriptada como E _A [ E _B (X) ] , que es equivalente a E _B [ E _A (X) ] por la propiedad #4.
5. Bob descifra estas tarjetas y las devuelve
   • Bob no puede ver las cartas , ya que no conoce A. Alice, sin embargo, puede verlos y estos son su mano.

Se pueden sacar más cartas usando un procedimiento similar. Después del juego, Alice y Bob revelan A y B para que puedan verificar que ninguno de los jugadores hizo trampa.

De hecho, existen esquemas de cifrado con las propiedades enumeradas, incluido un método similar a RSA. Ver mi Fuente para más detalles.

Uso en contratos:

Los contratos se pueden usar para administrar los mensajes entre jugadores y distribuir recompensas. El contrato no necesita ejecutar ninguna lógica a menos que los jugadores no estén de acuerdo con los resultados. En caso de desacuerdo, el retador debe aportar suficiente Ether para cubrir los costos de gasolina para verificar el juego. Luego, el otro jugador debe ejecutar la llamada para verificar el resultado del juego. El combustible se reembolsa al jugador veraz, y el tramposo cancela o pierde la ronda.

Dado que los contratos de Ethereum pueden verificar su código fuente, esto debería ser tan simple como usar un RNG para elegir cartas al azar de una baraja. Cualquiera que desee verificar que la baraja está barajada adecuadamente puede verificar el código fuente del contrato.

Dado que la generación de buena aleatoriedad se aborda en otra parte , esta respuesta supone que el contrato de barajado de cartas tiene acceso a buenos números aleatorios.

Uso de la aleatoriedad bajo demanda

Se puede producir un mazo bien barajado seleccionando cartas al azar de un mazo sin barajar y construyendo un nuevo mazo hasta que se agote el mazo sin barajar.

contract Deck {
   uint8[52] deck;

   function getRandomNumber() returns (uint) {
       ...;
   }

   function shuffle() {
      uint8[52] memory unshuffled;

      for (uint8 i=0; i < 52; i++) {
          unshuffled[i] = i;
      }

      uint cardIndex;

      for (i=0; i < 52; i++) {
          cardIndex = getRandomNumber() % (52 - i);
          deck[i] = unshuffled[cardIndex];
          unshuffled[cardIndex] = unshuffled[52 - i - 1]
      }
   }
}

Este contrato representa cada una de las 52 cartas como un número entero entre 0 y 51 inclusive. Una llamada a la shufflefunción llenará la deckvariable de almacenamiento con una baraja de 52 cartas con orden aleatorio.

Respondiendo a entradas aleatorias.

Esto supone que la aleatoriedad se puede solicitar de forma segura, lo que no es necesariamente factible. Si este no es el caso y la aleatoriedad debe incluirse en el contrato, entonces el siguiente concepto general debería funcionar igualmente bien.

contract Deck {
   uint8[52] deck;

   function shuffle(bytes randomBytes) {
      if (randomBytes.length < 52) throw;

      uint8[52] memory unshuffled;

      for (uint8 i=0; i < 52; i++) {
          unshuffled[i] = i;
      }

      uint8 cardIndex;

      for (i=0; i < 52; i++) {
          cardIndex = uint8(randomBytes[i]) % (52 - i);
          deck[i] = unshuffled[cardIndex];
          unshuffled[cardIndex] = unshuffled[52 - i - 1];
      }
   }
}

Esta versión del contrato requiere que se incluyan al menos 52 bytes de aleatoriedad con la llamada a shuffle.

Si desea que las tarjetas no se repitan, entonces en realidad es un problema bastante difícil. Un problema más simple es si no nos importa si la misma carta se reparte varias veces (por ejemplo, usted tiene un as de picas y yo tengo un as de picas).

Consideremos un juego simple con 2 jugadores. A cada jugador se le repartirá 1 carta y está bien que ambos jugadores reciban la misma carta. Se puede pensar que las dos cartas se reparten de dos barajas diferentes. Para implementar esto, podemos pensar en cada carta como un índice entre 0 y 51 (ambos inclusive). A continuación se explica cómo generar de manera justa la carta del jugador 1, para que solo él sepa cuál es.

1. El jugador 2 genera un número aleatorio en el rango 0..51 llamado p2_offset. A continuación, genera una cadena aleatoria llamada p2_secret (por ejemplo, "pcjshjfgn"). Luego, envía sha3(p2_offset, p2_secret) a la cadena de bloques.
2. El jugador 1 genera un número aleatorio en el rango de 0 a 51 llamado p1_offset y una cadena aleatoria p1_secret y envía sha3(p1_offset, p1_secret) a la cadena de bloques.
3. El jugador 2 revela p2_offset y p2_secret al contrato de Ethereum, lo que verifica que sha3 de esos valores coincidan con lo que envió anteriormente.
4. El jugador 1 ahora puede descubrir cuál es su carta haciendo (p2_offset + p1_offset) mod 52. Observe que el jugador 2 no sabe qué cartas son porque p1_offset no lo conoce.
5. El jugador 1 puede revelar su carta enviando p1_offset y p1_secret al contrato. Nuevamente, el contrato verificará que sha3 de esos valores coincidan con lo que el jugador 1 envió antes.

El mismo enfoque se puede utilizar para generar la tarjeta del jugador 2.

Asegurarme de que cada tarjeta aparezca solo una vez creo que es bastante desafiante. Podríamos decir que una vez