Método y sistema para almacenar y leer datos en o a partir de un almacenamiento de valor de clave.

Un método para almacenar (put) datos (v) en un almacenamiento de valor de clave que tiene una pluralidad de n servidores (S1,

S2, S3, S4), en el que t< n servidores (S1, S2, S3, S4) pueden fallar de forma arbitraria y en el que se cumple 3t+1 ≥ n,

caracterizado por las etapas de

a) Generar una información de compromiso (commit) para una información secreta (secret),

b) Difundir un primer mensaje (1a), que incluye los datos (v) que deben almacenarse, una clave (k) correspondiente a los datos (v) y la información de compromiso generada (commit) para los n servidores,

c) Almacenar (saving1) la información incluida en el primer mensaje (1a) en al menos un número de servidores (S1, S2, S3),

d) Proporcionar una primera información (1b) de confirmación de almacenamiento por al menos n-t servidores (S1, S2, S3),

e) Difundir un segundo mensaje (2a) que incluye una clave (k) correspondiente y la información secreta (secret) para los n servidores (S1, S2, S3, S4),

f) Almacenar (saving2) la información incluida en el segundo mensaje (2a), y

g) Proporcionar una segunda información (2b) de confirmación de almacenamiento por al menos n-t servidores (S1, S2, S3).

Método y sistema para almacenar y leer datos en o a partir de un almacenamiento de valor de clave

La presente Invención se refiere a un método para almacenar datos en un almacenamiento de valor de clave que tiene una pluralidad de n servidores, en el que t < n servidores pueden fallar de forma arbitraria y en el que se cumple 3t+1 = n.

La presente Invención se refiere además a un método para leer datos almacenados en un almacenamiento de valor de clave que tiene una pluralidad de n servidores, en el que t < n servidores pueden fallar de forma arbitrarla y en el que se cumple 3t+1 = n.

La presente Invención se refiere además a un sistema para almacenar datos en un almacenamiento de valor de clave que tiene una pluralidad de n servidores, en el que t < n servidores pueden fallar de forma arbitraria y en el que se cumple 3t+1 = n y a un lector para leer datos almacenados en el almacenamiento de valor de clave, preferentemente para realizar un método de acuerdo con una de las reivindicaciones 1-13.

La presente invención se refiere además a un sistema para leer datos almacenados en un almacenamiento de valor de clave que tienen una pluralidad de n servidores en el que t < n servidores pueden fallar de forma arbitraria y en el que se cumple 3t+1 = n y a un lector para leer datos almacenados en el almacenamiento de valor de clave, preferentemente para realizar un método de acuerdo con una de las reivindicaciones 1-13.

Los almacenamientos de valor de clave, también llamados almacenes de valor de clave (KVS) están obteniendo un interés creciente para varios sistemas distribuidos a gran escala que van desde bases de datos, motores de búsqueda, plataformas basadas en la nube, por ejemplo, marcos de programación en la nube como map-reduce, para aplicaciones colaborativas como las sociales redes. Por ejemplo, a menudo las bases de datos de almacenamiento convencionales implementan índices de búsqueda en la parte superior de un almacén de valor de clave distribuida para la escalabilidad y el rendimiento. Los almacenes de valor de clave no solo pueden servir como una capa de almacenamiento para las capas de nivel superior, sino que también pueden servir como aplicaciones directamente, tal como en el intercambio de archivos par a par. Si, por ejemplo, se bloquea uno o más de los servidores de almacenamiento debido a un error de software o de hardware o similar, el almacén de valor de clave compensará tal fallo. Los almacenes de valor de clave como Cassandra, Redis, HBase, Dynamo y Memcached toleran fallos o bloqueos de servidores de almacenamiento empleando la replicación.

Una característica deseable de los almacenes de valor de clave es garantizar la coherencia de los datos y la disponibilidad incluso en el caso de que se realice un acceso simultáneo de diferentes usuarios. El más alto grado de coherencia de los datos es la denominada coherencia atómica, lo que significa que si un cierto valor se almacena bajo una cierta clave o una operación de lectura devuelve el valor, entonces cada operación de lectura posterior devuelve el valor v correspondiente o un valor v más nuevo pero nunca un valor que sea más antiguo que v. Los almacenes de valores de clave convencionales soportan la coherencia atómica a nivel de las claves individuales y el acceso transaccional a múltiples claves se realiza en capas de nivel superior. Para muchas aplicaciones, la coherencia atómica es obligatoria.

La disponibilidad es complementaria a la coherencia, es decir, si un cliente, que se supone que es un cliente correcto del almacén de valor de clave, recurre a una operación de lectura o escritura entonces la operación debería tener éxito a pesar de los servidores defectuosos e independientemente del comportamiento de otros clientes potenclalmente defectuosos.

Para un número creciente de aplicaciones y sistemas, que dependen de un almacén de valor de clave como una capa de almacenamiento del núcleo, la robustez del almacén de valor de clave también es importante. Sin embargo, debido a la complejidad creciente de los sistemas distribuidos, que consisten de un gran número de nodos interconectados, la probabilidad de que falle algún nodo está aumentando. El riesgo de tales fallos accidentales de hardware y software, por ejemplo, los errores de software, también aumentan reduciendo significativamente la robustez del almacén de valor de clave. Un riesgo emergente adicional son las vulnerabilidades explotadas: Debido a la aparición de la computación en la nube, los datos se externalizan a las plataformas de servicio de la nube que son directamente accesibles desde internet. Una de las consecuencias son las vulnerabilidades explotables de las plataformas de servicio de la nube, por ejemplo, debido a los errores de software que resultan en unas potenciales pérdidas de datos y en la corrupción de los datos.

Para superar estos problemas, la literatura no de patente de James Hendricks, Gregory R. Ganger, Michael K. Reiter: "Low-overhead byzantine fault-tolerantstorage", SOSP 27: 73-86 describe las operaciones de lectura necesarias para devolver solo en ejecuciones libres de contención para tolerar lectores bizantinos, lo que significa que pueden fallar de forma arbitraria.

En la literatura no de patente de Barbara Liskov, Rodrigo Rodrigues XP1927339: Tolerating Byzantine Faulty Clients In a Quorum System. Se usan las firmas digitales ICDCS 26 para tolerar lectores bizantinos.

En la literatura no de patente de Amltanand S. Aiyer, Lorenzo Alvisi, Rlda A Bazzi: "Bounded Walt-Free Implementation of Optimally Resilient Byzantlne Storage Without (Unproven) Cryptographlc Assumptlons", DISC 27: 7-19, XP191743 los canales de comunicación que se describen, entregan finalmente cada mensaje a todos los servidores, lo que en los sistemas asincronos es difícil de implementar. Además, la latencia de lectura exhibida por el método descrito en la misma es lineal en el número de servidores.

La literatura no de patente de Dan Dobre et al: "Efflclent Robust Storage Uslng Secret Tokens" 3 de noviembre de 29 (3-11-29), Estabilización, Seguridad y Seguridad de los Sistemas distribuidos, Sprlnger Berlín. Heldelberg, Berlín, Heldelberg. Página(s) 269-283, XP19133325. ISN: 978-3-642-5117-3 muestra un almacenamiento robusto garantizando el progreso en todas las condiciones y nunca devuelve un valor antiguo ni un valor forjado usando testigos secretos.

Una de las desventajas es que los métodos convencionales mencionados anteriormente para los datos no autenticados no son prácticos debido a la alta latencia, la falta de escalabllldad y la falta de progreso en la contención. Además la mayoría de los métodos convencionales que no usan firmas están optimizados para un solo

escritor.

Por lo tanto, es un objetivo de la presente Invención proporcionar métodos y sistemas para almacenar y leer datos hacia o desde un almacenamiento de valor de clave que tolera fallos Bizantinos, en particular, mediante los

servidores y los lectores.

Es un objetivo adicional que la presente Invención proporcione métodos y sistemas para almacenar y leer datos hacia o desde un almacenamiento de valor de clave que sean una firma libre y proporcionen coherencia atómica.

Es incluso un objetivo adicional de la presente Invención proporcionar métodos y sistemas para almacenar y leer datos hacia o desde un almacenamiento de valor de clave que sean escalables.

Es incluso un objetivo adicional de la presente invención proporcionar métodos y sistemas para almacenar y leer datos hacia o desde un almacenamiento de valor de clave que reduzcan la latencia para los datos de escritura y lectura.

Es un objetivo adicional de la presente invención proporcionar métodos y sistemas para almacenar y leer datos hacia o desde un almacenamiento de valor de clave que permita un mayor número de servidores pueden fallar de

forma arbitraria.

Es incluso un objetivo adicional de la presente Invención proporcionar métodos y sistemas para almacenar y leer datos hacia o desde un almacenamiento de valor de clave que sean más robustos que cualquier método o sistema de firma libre convencional.

Es incluso un objetivo adicional de la presente Invención proporcionar métodos y sistemas para almacenar y leer datos hacia o desde un almacenamiento de valor de clave que permitan una fácil ¡mplementaclón con costes bajos y con una mayor flexibilidad con respecto a los datos que deben leerse o almacenarse.

De acuerdo con la invención, los objetivos mencionados anteriormente se consiguen mediante un método de la reivindicación 1.

De acuerdo con la reivindicación 1 el método para almacenar datos en un almacenamiento de valor de clave que tiene una pluralidad de n servidores,... [Seguir leyendo]

1. Un método para almacenar (put) datos (v) en un almacenamiento de valor de clave que tiene una pluralidad de n servidores (S-i, S2, S3, S4), en el que t < n servidores (S-i, S2, S3, S4) pueden fallar de forma arbitraria y en el que se cumple 3t+1 = n,

caracterizado por las etapas de

a) Generar una información de compromiso (commit) para una información secreta (secret),

b) Difundir un primer mensaje (1a), que incluye los datos (v) que deben almacenarse, una clave (k) correspondiente a los datos (v) y la información de compromiso generada (commit) para los n servidores,

c) Almacenar (saving-i) la información incluida en el primer mensaje (1a) en al menos un número de servidores

(Si, S2, S3),

d) Proporcionar una primera información (1 b) de confirmación de almacenamiento por al menos n-t servidores

(Si, S2, S3),

e) Difundir un segundo mensaje (2a) que incluye una clave (k) correspondiente y la información secreta (secret) para los n servidores (S-i, S2, S3, S4),

f) Almacenar (saving2) la información incluida en el segundo mensaje (2a), y

g) Proporcionar una segunda información (2b) de confirmación de almacenamiento por al menos n-t servidores

(S-i, S2, S3).

2. Un método para leer (get) datos (v) almacenados en un almacenamiento de valor de clave que tiene una pluralidad de n servidores (S-i, S2, S3, S4), en el que t < n servidores (S-i, S2, S3, S4) pueden fallar de forma arbitraria y en el que se cumple 3t+1 = n,

caracterizado por las etapas de

A) Difundir un primer mensaje (1a) que incluye una clave (k) correspondiente a los datos (v) que deben leerse

B) Recoger (1b) candidatos (C2, C¡, Cant¡guo) de los datos (v) que deben leerse desde al menos 2t+1 servidores

(S2, S3, S4),

C) Escribir de nuevo (2a) la información secreta (secret) correspondiente a la información de compromiso (commit) y a la información correspondiente a los datos (v) que deben leerse,

D) Validar (verification) los candidatos (C2, C¡, Cantiguo) recogidos en base a un emparejamiento de la información de compromiso (commit) y la información secreta (secret),

E) Determinar los candidatos para los datos (v) que deben leerse de acuerdo con los candidatos (V¡) validados

F) Seleccionar los datos que deben leerse en base a los t+1 mensajes (2b) de respuesta, que incluyen el mismo candidato de los datos (v) que deben leerse y la información secreta correspondiente (secret).

3. El método de acuerdo con la reivindicación 1, caracterizado por que la información (ts) de marca de tiempo se genera y se asigna a los datos (v) que deben almacenarse.

4. El método de acuerdo con una de las reivindicaciones 1-3, caracterizado por que la información (ts) de marca de tiempo generada es consistente globalmente.

5. El método de acuerdo con una de las reivindicaciones 1, 3 y 4, caracterizado por que antes de asignar la información (ts) de marca de tiempo a los datos (v) que deben almacenarse, se recoge la información (ts) de marca de tiempo generada.

6. El método de acuerdo con una de las reivindicaciones 1, 3-5, caracterizado por que antes de realizar la etapa c) y/o la etapa f) se evalúa la información (ts) de marca de tiempo.

7. El método de acuerdo con una de las reivindicaciones 1-6, caracterizado porque se verifica una validación de la información (ts) de marca de tiempo, preferentemente intercambiando al menos simétricamente la información de marca de tiempo autenticada.

8. El método de acuerdo con una de las reivindicaciones 1-7, caracterizado porque la información de compromiso (commit) se genera mediante un cálculo de clave (hashing) y/o

la información de compromiso (commit) se genera usando un valor (x¡) aleatorio y un valor de polinomio de un polinomio (P) aleatorio de grado t aplicado al valor (x¡) aleatorio, en el que preferentemente

la información de compromiso (commit) depende del servidor (S-i, S2, S3, S4), preferentemente para cada servidor (S-i, S2, S3, S4) se genera una información de compromiso separada correspondiente (commit).

9. El método de acuerdo con una de las reivindicaciones 1-8, caracterizado por que los canales seguros se usan para el mensaje y/o el intercambio de información, preferentemente los canales punto a punto autenticados.

1. El método de acuerdo con las reivindicaciones 2-3, caracterizado por que los candidatos (C2, C¡, Cant¡guo) incluyen una clave (k) almacenada y la información secreta (secret) más recientemente almacenada y/o más recientemente recibida.

11. El método de acuerdo con la reivindicación 2, caracterizado por que un conjunto (C) de unión de todos los candidatos (C2, C¡, Cant¡guo) se transmite en la etapa C).

12. El método de acuerdo con una de las reivindicaciones 2, 1-11, caracterizado porque se proporcionan un tercer mensaje que incluye los candidatos (C2, C¡, Cant¡guo) recogidos de acuerdo con la etapa B) y un cuarto mensaje que incluye los candidatos (V-i, V2, Vant¡guo) validados de acuerdo con la etapa D) al recibir el primer mensaje (1a).

13. El método de acuerdo con la reivindicación 12, caracterizado por que los candidatos para los datos (v) que deben leerse se filtran al recibir el cuarto mensaje.

14. Un sistema para almacenar datos (v) en un almacenamiento de valor de clave que tiene una pluralidad de n servidores (S-i, S2, S3, S4) en el que t < n servidores pueden fallar de forma arbitraria y en el que se cumple 3t+1 = n, y un escritor (w) para escribir los datos (v) en el almacenamiento de valor de clave, para realizarse con un método de acuerdo con una de las reivindicaciones 1-13,

caracterizado por que

el escritor (w) está configurado para que pueda funcionar para difundir un primer mensaje (1a) que incluye los datos (v) que deben almacenarse, una clave (k) correspondiente para los datos (v) y una información de compromiso (commit), generados a partir de una información secreta (secret), para los n servidores (S-i, S2, S3, S4), porque al menos un número de servidores (S-i, S2, S3, S4) está configurado para que pueda funcionar para almacenar la información incluida en el primer mensaje (1a), por que

el escritor (w) está configurado para que pueda funcionar para difundir un segundo mensaje (2a) que incluye una clave (k) correspondiente y la información secreta (secret) para los n servidores (Si, S2, S3, S4) después de recibir la primera Información (1b) de confirmación de almacenamiento mediante al menos los n-t servidores (S-i, S2, S3, S4), y por que

al menos los n-t servidores (S-i, S2, S3, S4) están configurados para que puedan funcionar para proporcionar una segunda Información (2b) de confirmación de almacenamiento después de almacenar la información del segundo mensaje (2a) Incluida en el segundo mensaje (2a).

15. Un sistema para leer los datos almacenados en un almacenamiento de valor de clave que tiene una pluralidad de n servidores, en el que t < n servidores (Si, S2, S3, S4) pueden fallar de forma arbitraria y en el que se cumple 3t+1 = n, y un lector (rd) para leer los datos (v) almacenados en el almacenamiento de valor de clave, para realizarse con un método de acuerdo con una de las reivindicaciones 1-13,

caracterizado por que

el lector (rd) está configurado para que pueda funcionar para difundir un primer mensaje (1a) que incluye una clave (k) correspondiente a los datos (v) que deben leerse, para recoger los candidatos (C2, C¡, Cantiguo) correspondientes a los datos (v) que deben leerse a partir de al menos 2t+1 servidores (S-i, S2, S3, S4), para escribir de nuevo la información secreta (secret) correspondiente a la información de compromiso (commit), generada a partir de la información secreta (secret) y la información correspondiente a los datos (v) que deben leerse, y para seleccionar los datos (v) que deben leerse en base a los t+1 mensajes (C2, C¡, Cant¡guo) de respuesta que incluyen el mismo candidato (C2, C¡, Cant¡guo) que debe leerse y la información secreta (secret) correspondiente, en el que los candidatos (C2, C¡, Cant¡guo) para los datos (v) que deben leerse se han determinado de acuerdo con los candidatos (V¡) validados en los que los candidatos (C2, C¡, Cant¡guo) recogidos se han validado en base a un emparejamiento de la información de compromiso (commit) y la información secreta (secret).