Transaction ordering dependence problem

octubre 8, 2018octubre 9, 2018 miguelpiniaDeja un comentario

Debido a la naturaleza del entorno de ejecución de los smart contracts, en los que se maneja dinero, existe un incentivo para que existan usuarios maliciosos para los que exploten las debilidades de implementación y obtengan lucro de dichas debilidades.

Consideremos el escenario, donde la blockchain se encuentra en un estado $\Delta$ y hay un bloque nuevo que incluye dos transacciones ( $T_{i}$ y $T_{j}$ ) que invocan a un mismo contrato. En tal escenario, los usuario desconocen cual es el estado en que se encuentra el contrato cuando se aplican la ejecución de su contrato. Por ejemplo, $T_i$ se puede aplicar en el estado $\Delta[\alpha]$ o en el estado $\Delta'[\alpha]$ que es cuando ya se aplicó $T_{j}$ . Esto implica que hay una discrepancia entre el estado que se encuentra el contrato que los usuarios invocan, y el estado actual depende del estado en que se hayan realizado las ejecuciones. Sólo el minero puede determinar el orden en que se ejecutan las transacciones. Esto tiene como consecuencia que el estado del contrato depende del orden en que el minero invocaba a las transacciones. Esto se conoce como Transaction Ordering Dependence (TOD).

TOD tiene puede ser utilizado para realizar ataques al estado de la blockchain de modo que se puedan obtener beneficios del modo en que se ejecutan estas transacciones.

Observemos el siguiente smart-contract que representa una tienda que vende un producto:

contract MarketPlace {
  uint public price;
  uint public stock;
  /.../
  function updatePrice(uint _price) {
    if (msg.sender == owner) price = _price;
  }
  function buy(uint quant) returns (uint) {
    if (quant > stock || msg.value < quant * price) throw;
    stock -= quant;
    /.../
  }
}

A partir del código anterior, supongamos la siguiente ejecución dentro de la blockchain:

$T_{c}$ y $T_{d}$ son transacciones que son invocadas de forma simultanea y son obtenidas por el mismo minero. $T_{c}$ corresponde a la transacción asociada con la compra de un objeto a la tienda y $T_{d}$ es la transacción que actualiza el precio del producto.
El minero mina el bloque que contiene a $T_{c}$ y a $T_{d}$
$T_{c}$ se ejecuta y compra.
$T_{d}$ se ejecuta y actualiza el producto.
Se escribe el estado de la ejecución de las transacciones dentro del bloque y se actualiza el estado $\Delta$ de la blockchain.

En esta ejecución todo funcionó de forma esperada sin que fallara nada. Pero que pasa si consideramos la siguiente ejecución:

$T_{c}$ y $T_{d}$ son transacciones que son invocadas de forma simultanea y son obtenidas por el mismo minero. $T_{c}$ corresponde a la transacción asociada con la compra de un objeto a la tienda y $T_{d}$ es la transacción que actualiza el precio del producto.
El minero mina el bloque que contiene a $T_{c}$ y a $T_{d}$
$T_{d}$ se ejecuta y actualiza el producto.
$T_{c}$ se ejecuta y compra.
Se escribe el estado de la ejecución de las transacciones dentro del bloque y se actualiza el estado $\Delta$ de la blockchain.

En este caso el cliente compró el producto a un precio más caro que el que él esperaba. Esto se traduce en que el dueño se benefició de la forma en que la transacción se ejecutó, aunque esto no fue de forma consiente. ¿Qué pasaría si nos aprovechamos de esta falla?

Veamos un caso más en el que el orden de la ejecución de los contratos puede causar un estado imprevisto en la ejecución bajo TOD. Sea el siguiente código:

contract Puzzle {
  address public owner;
  bool public locked;
  uint public reward;
  byte32 public diff;
  bytes public solution;

  function Puzzle() {
    owner = msg.sender;
    reward = msg.value;
    locked = false;
    diff = bytes(111111);
  }

  function () {
    if (msg.sender == owner) {
      if (locked) throw;
      owner.send(reward);
      reward = msg.value;
    } else {
      if (msg.data.length > 0) {
        if (locked) throw;
        if (sha256(msg.data) < diff) {
          msg.sender.send(reward);
          solution = msg.data;
          locked = true;
        }
      }
    }
  }
}

El contrato anterior recompensa a los usuarios quienes resuelven un acertijo computacional. Sólo si el hash del mensaje enviado por el jugador es menor que una diferencia predefinida, entonces, se paga la recompensa al jugador y se bloquea el contrato para que nadie más intente jugar después.

Igualmente consideremos dos ejecuciones de el contrato Puzzle en una blockchain. La primera ejecución la podemos describir de la siguiente forma:

$T_{d}$ y $T_{j}$ son dos transacciones que son invocadas de forma simultanea y son obtenidas por el mismo minero. $T_{d}$ es la transacción enviada por el dueño del contrato y $T_{j}$ la transacción del usuario que envía una solución válida para reclamar la recompensa.
El minero mina el bloque que contiene a $T_{d}$ y $T_{j}$
$T_{d}$ se ejecuta y actualiza la recompensa.
$T_{j}$ se ejecuta y recibe la nueva recompensa.
Se escribe el estado de la ejecución de las transacciones dentro del bloque se actualiza el estado $\Delta$ de la blockchain.

En este caso el jugador esperaba recibir la recompensa que el observó cuando envió su solución, pero el recibió una recompensa distinta, el cuál pudo haber sido un accidente, pero ¿y si no fue un accidente?

Transaction ordering dependence

octubre 8, 2018octubre 8, 2018 miguelpiniaDeja un comentario

¿Qué sucede cuando un contrato inteligente obtiene varias llamadas similares en el mismo bloque? Consideremos por ejemplo el siguiente Smart Contract:

contract greeter {
    string name;

    function setName(string name_) {
        name = name_;
    }

    function getName() constant returns(string) {
        return name;
    }
}

Entonces, propongamos las siguientes preguntas acerca de la ejecución y evaluación de este contrato inteligente.

¿Que sucede si Bob, Alice y Eve llaman al contrato Greeter y las tres llamadas son ejecutadas en el mismo bloque?: Las tres llamadas podrían invocarse, no necesariamente en secuencia, y el nombre en la última transacción es el que se va a almacenar en el bloque minado.
¿Todos van a obtener la respuesta propia con su propio nombre?: No. La función getName() debería regresar el nombre que se almacenó en el bloque minado, el cuál fue establecido por la última transacción.
¿Va a ejecutarse el contrato tres veces?: Si. La función setName(...) debería de ejecutarse tres veces.

Describamos cuál es el orden y el comportamiento concurrente de múltiples llamadas a un contrato en un bloque minado. Lo primero que hay que observar es que el minero ganador del bloque, es el que va a decidir el orden en que las transacciones son incluidas en el bloque. A partir de esto notemos que si las transacciones son de diferentes direcciones, estas van a ser ejecutadas en un orden arbitrario, pero si las transacciones provienen de una misma dirección, las ejecuciones siempre van a ser ejecutadas en el orden definido por los nonce de las transacciones.

Retomando la cuestión anterior, tenemos que:

La máquina virtual de ethereum debería de llamar setName(...) tres veces, pero la secuencia en que se van a ejecutar las transacciones va a ser ejecutada de forma arbitraria asumiendo que las transacciones provienen de diferentes direcciones (From:, diferentes cuentas).
El campo del nombre va a cambiarse tres veces, pero el nombre en la transacción final debería de ser almacenada en el bloque minado.
Invocaciones a getName() van a devolver el nombre almacenado en el bloque minado.
Invocaciones a getName() desde un smart contract ejecutado en el mismo bloque debería de obtener el valor de cualquiera de las ejecuciones de las transacciones asociadas al contrato Greeter.

Un ejemplo de ejecución de esto sería algo como lo siguiente:

Las transacciones son enviadas en el orden Alice, Bob y Eve.
El minero ganador ejecuta las transacciones en el orden Eve, Bob y Alice.
Un smart contract se ejecuta entre las transacciones de Bob y Alice.
El smart contract invoca getName() regresando Bob.
Después de que el bloque ha sido minado, el nombre almacenado en el bloque es Alice. Cualquier llamada hacia getName() va a regresar Alice.

Antecedentes de blockchains

septiembre 2, 2018septiembre 2, 2018 miguelpiniaDeja un comentario

Cypherpunks

Esta historia inicia con cypherpunks, resistencia y búsqueda de cambios en el sistema. Los punks, nacen en los años 70’s como una subcultura urbana cuya filosofía se puede resumir en:

«Hazlo tu mismo» ó «Hazlo a tu manera»
Rechaza los dogmas y cuestiona lo establecido
Desprecia las modas y la sociedad de masas.

Los punks siempre han sido caracterizados como la parte rebelde y anti-sistema de la sociedad. Al mismo tiempo en que nacen los punks, la criptografía era utilizada principalmente en secreto por militares y espías, pero todo cambia con la salida al público de dos documentos, el primero que fue publicado por el gobierno estadounidense siendo el Data Encryption Standar, el cuál es un sistema de cifrado simétrico en bloques, así como el trabajo de criptografía de llave pública de Whitfield Diffie y Martin Hellman.

Con estos trabajos, el origen de los cypherpunks viene de la mano del criptografo David Chaum donde desarrolla ideas sobre dinero digital anónimo en el artículo «Security without Identification: Transaction Systems to Make Big Brother Obsolete» y posteriormente con «Untraceable Electronic Cash». Con las ideas planteadas por Shaum y las ideas de Richard Stallman sobre el software libre, un grupo de personas fundan Cygnus Solutions, quienes proveían soporte comercial a software libre. Varios de los empleados de esta empresa fueron «mantenedores» de varios paquetes de software GNU. También fueron activistas que abogaban por la necesidad de la privacidad en la sociedad abierta de la era electrónica. De forma humorística, Jude Milhon (mejor conocida por su pseudonimo St. Jude), acuñe el término cypherpunk.

Los cypherpunks llevaron una lista de distribución de correo, la cuál fue muy activa donde se discutieron temas muy variados, que fueron desde matemáticas, criptografía, ciencias de la computación, discusión política y filosófica, argumentos personas hasta ataques y spam.

Las ideas básicas de este grupo se ṕueden encontrar en el documento «A cypherpunk’s Manifiesto», el cuál fue escrito por Eric Hughes en 1993. Los cypherpunks están dedicadados a la construcción de sistemas anónimos. Defiende la privacidad con criptografía, con sistemas de envio de correo anónimos, con firmas digitales y con dinero electrónico.

El último punto, es lo que posteriormente, junto con la crisis de 2008, daría paso a la creación de las blockchains y las criptomonedas.

Inicio del dinero electrónico, crisis del 2008 y bitcoin

Actualmente para realizar el intercambio de bienes y servicios, hacemos uso de dinero, el cuál es un medio que permite facilitar las transacciones, compra y venta, así como un medio para guardar valor. Este dinero es controlado por un banco central (nacional), con el objetivo de que exista suficiente para que las necesidades de las distintas actividades económicas se satisfagan.

¿Cómo funcionan los pagos en linea?

Cuando compramos un producto en línea, digamos en Amazon, utilizamos tarjetas de débito o crédito para poder pagarlos y que el vendedor en linea nos entregue el producto solicitado.

Los eventos que ocurren durante ese proceso suelen ser:

Llenar el carrito de compras con los productos que queremos comprar
Ingresamos los detalles de la tarjeta de débito o crédito para poder realizar el pago.
Enviar la orden de solicitud.
Amazon toma los detalles de la tarjeta de crédito y confirma con el sistema (sistema financiero que pueden ser bancos, compañías de tarjetas de crédito o algún otro intermediario).
El sistema confirma o cancela tu orden basado en que si hay suficientes fondos disponibles en tu cuenta.

Otro modelo existente es el que propone Paypal, donde funge como un intermediario, es decir, Paypal se sitúa entre tu y el vendedor y actúa como un tercero confiable. Paypal maneja la transacción en su nombre y notifican a Amazon. La ventaja de trabajar con Paypal es que no le proporcionas tus datos de la tarjeta de crédito/débito al vendedor. Sin embargo, es posible que los protocolos de Paypal tengan brechas de seguridad o ataques.

Actualmente es más fácil y cómodo proveer la información de tarjetas de crédito/débito a restaurantes, tiendas en linea y sitios de viaje. Esto debido a que no existen los mismos riesgos de realizar transacciones en linea que en los años 90.

Por otro lado, el tener un intermediario al momento de realizar una transacción, implica que no tienes privacidad acerca de las cosas que estás comprando o consumiendo, además de posibilidades de que existan brechas de seguridad en caso de que los bancos y otras compañías no lleven a cabo metodologías y prácticas de seguridad de forma correcta.

Debido a los riesgos anteriores, algunas personas buscaron tener alternativas al uso de bancos y otras entidades para servir de intermediarios entre particulares.

David Chaum y el doble gasto

En los años 80, se idearon propuestas para tener dinero electrónico, de modo que fuera similar a su equivalente físico, es decir, que tuviera las propiedades similares a las que tiene el dinero, siendo estas:

El banco no sea capaz de rastrear la forma en que lo gastas.
Permitir realizar transacciones offline si tener que esperar por una entidad de terceros para aprovar la transacción.

En los años 80, David Chaum introdujo las primeras ideas sobre dinero digital seguro, a través de primitivas criptográficas conocidas como firmas ciegas. Sus ideas permitían que las personas pudieran obtener dinero digital de un banco y gastarlo de una forma que no sea trazable por el banco o cualquier otro usuario.

Un problema que también se resolvió con las primitivas criptográficas que propuso David Chaum fue el del doble gasto (double spending). Este problema se da debido a la naturaleza del software; es fácilmente duplicar un recurso electrónico digital en las computadoras, entonces, si tuvieramos una moneda digital, sería fácilmente hacer dos o más copias que se pueden distribuir entre las personas.

Una forma de resolver el problema anterior, es el poner números seriales únicos en cada moneda digital y utilizar firmas criptográficas. Cuando una persona recibiera una moneda con tu firma en ella, entonces puede consultar si la moneda no ha sido gastada previamente utilizando el número serial. Así, el receptor pueden decidir si acepta la moneda o la rechaza. Si aceptan la moneda, se registra que ya se gasto en un ledger y así se podría continuar para registrar cuando se gasta una moneda. Este método funciona, pero dificilmente eficiente en escenarios de la vida real. Además de que no elimina la privacidad que se buscaba.

El otro método es el propuesto por David Chaum con las firmas ciegas, en el que se evita el doble gasto. Esta técnica se puede explicar de la siguiente forma:

Supongamos que Alice y Bob están realizando una transacción. Entonces Bob genera una nueva moneda para Alice y Alice elige el número de serie que después verificará el banco, el cuál le servirá para que Alice pueda obtener los recursos de Bob. Ese número de serie no es necesario que Bob lo conozca, Alice le pide a Bob que firme la moneda con el número de serie, entonces, con esto, Alice puede obtener posteriormente los recursos de Bob del banco. Sin embargo, esta técnica funciona, pero aún requiere de un servidor central de una autoridad central como el banco.

En 1989 David Chaum tomo estas ideas y comercializó con ellas para formar su compañía llamada DigiCash. Esta compañía fue pionera en la creación de sistemas y procesamiento de pagos en linea. La implementación del sistema de DigiCash fue llamada Ecash. De manera sorpresiva los bancos querían implementar la tecnología de Chaum. Ecash está basada en los protocolos de Chaum, estos protocolos mantienen a los clientes anónimos e inrastreables, pero no hace lo mismo con los mercaderes, ya que tienen que devolver las monedas tan pronto las reciben, por lo que su anonimidad se pierde. Eventualmente DigiCash cae en la ruina por su falta de convencimiento a los bancos.

Crisis del 2008 y Bitcoin

El problema de la crisis del 2008 en Estados Unidos, es causada por los bancos y el gobierno estadounidense. Al principio, la gente ganaba poco, y lo poco que ganaban lo guardaban en sus casas para mantener sus ingresos. Cuando empezaron a ganar más dinero, era claro que ya no podían seguir guardando sus recursos en casa, debido que podrían perderse o ser robados, por lo que empezaron a depositar sus ingresos en

Criptografía

Las criptomonedas y las blockchains, como ya se mencionó, hacen uso de la criptografía para poder operar de forma correcta de modo que resuelvan los problemas de anonimidad, seguridad y doble gasto. Entonces, para poder entender todos los conceptos asociados con blockchaino, es necesario establecer una serie de conceptos sobre criptografía.

La criptografía moderna aparece después de la segunda guerra mundial con la aparición de las técnicas de la criptografía de llave pública, así como la adopción del FIPS ??? (DES – Data Encryption Standar) como un estandar federal de procesamiento de información por parte de los Estados Unidos, como herramienta de cifrado simétrico, siendo el mecanismo de crifrado más conocido de la historia. Otros métodos de cifrado simétrico son: Triple DES, RC5, IDEA y ????.

Con respecto al cifrado de llave pública, en 1976, los doctores Diffie y Hellman publican New Directions in Cryptography, este artículo introducen el concepto de la llave pública, así como proveer un método ingenioso para el intercambio de llaves de crifrado. La fortaleza de la técnica propuesta reside en la intratabilidad del problema del logaritmo discreto. A pesar de que los autores no proveyeron una implementación, otros autores se basaron en la idea propuestas por Diffie y Hellman para construir otros esquemas de cifrado público. Por ejemplo, Rivest, Shamir y Adleman, en 1978 diseñan el esquema de cifrado de llave pública y de esquema de firmas digitales conocida como RSA (nombrado así por las iniciales de sus autores). La fortaleza de este sistema está basado el problema de la intratabilidad de la factorización de números primos muy grandes. Otro esquema muy conocido basado en el problema de logaritmo discreto, es el que encontró ElGamal en 1985.

Seguridad de la información y criptografía

La criptografía se entiende en términos de problemas relacionados a la seguridad de la información. Por ejemplo, cuando todas las entidades que participan en una transacción, deben tener cierta confidencia que ciertos objetivos asociados con seguridad de la información deben satisfacerse.

Tales objetivos son los siguientes:

Privacidad o confidencialidad
Integridad de los datos
Autenticación o identificación
Autenticación de mensajes
Firmas
Autorización
Validación
Control de acceso
Certificación
Timestamping
witnessing
Recepción
Confirmación
Ownership
Anonimidad
No-repudiación
Revocación

La criptografía va a resolver algunos de estos objetivos.

Definición: La criptografía es el estudio de técnicas matemáticas relacionadas

a aspectos de seguridad tales como confidencialidad, integridad de datos, autenticación de entidades y autenticacíon del origen de los datos.

De las metas descritas en la definición tenemos:

Confidencialidad es un servicio usado para mantener el contenido de la información disponible para aquellos autorizados para tenerla. Secrecía es un término sinónimo con confidencialidad y privacidad.
Integridad de datos es un servicio el cual evita la alteración no autorizado de los datos. Para asegurar integridad de los datos, debe tener la habilidad para detectar la manipulaciónde datos por entidades no autorizadas.
Autenticación es un servicio relacionado a la identificación. Esta función aplica para todos los participantes.
No repudiación es un servicio que previene que una entidad de denegar compromisos o acciones anteriores.

Computer geek

You know you're brilliant, but maybe you'd like to understand what you did two weeks from now.

Categoría: Blockchains