Journal décentraliser une base de données en utilisant l'information de Shannon

Posté par grondilu le 26 juin 2011 à 13:45.

Étiquettes : aucune

-6

juin

2011

Voilà une idée qui m'est venue récemment et que j'aimerais vous faire partager. Il s'agit d'une méthode générale pour décentraliser n'importe quelle base de données.

Chaque noeud possède une version de la base, et pour soumettre une entrée de modification de base aux autres noeuds (par exemple un CREATE TABLE), chaque noeud doit accompagner sa demande d'une preuve de travail. L'idée est la même que pour bitcoin, mais je voulais trouver un algorithme plus simple pour l'ajustement de la difficulté. L'idée m'est alors venue d'utiliser l'information de Shannon.

I(e) = -ln( P(e) )
(pour un évènement e)

En informatique, ça peut donner une unité de mesure extensible pour la preuve de travail. J'ai alors écrit une fonction bash pour la calculer:

shannon() {
    # le deuxième argument est optionnel: c'est l'unité d'information
    # désirée (2 pour le bit, 2^8=256 pour l'octet, etc...) 
    h="${1^^}"
    if [[ "$h" =~^[A-F0-9]+$ ]]
    then bc -l <<<"scale=64; ibase=16; l(${h//?/F)${2!+/l($(printf %x "$2"))}"
    else return -1
}

On la calcul en fournissant en entrer un hash. Par exemple, le montant du sha256 de la chaîne "Hello world!" est :

$ shannon "$(openssl dgst -sha256  -binary <<<<"Hello world!" |xxd -p -c 64)"

Je n'ai pas mon ordi sous la main là (je suis dans un cybercafé), donc je vous laisse calculer.

La chaîne obtenue est à la fois la quantité d'information et la preuve de travail (comme la relation entre le hash et l'information est bijective, il suffit de conserver suffisamment de décimales après la virgule)

Pour avoir un montant plus élevé, il faut effectuer un travail:

$ for nonce in {0..100}
  do
      echo -n "$nonce "
      shannon "$(openssl dgst -sha256 -binary <<<"Hello world! $nonce" |xxd -p -c 64)"
  done |
  sort -k 2 -g |
  head -1

La encore sans mon ordi je ne peux pas vérifier ce code mais vous avez compris l'idée.
Ainsi, pour soumettre une entrée de modification de base, il faut soumettre un fichier du type:

[shanon information of a previous entry]
[SQL command | NoSQL command | Whatever ...]
[nonce]

L'information totale d'une telle chaîne est la somme des informations de chaque entrée. Il suffit de choisir la chaîne ayant la plus haute information.

# ERRATUM

Posté par grondilu le 26 juin 2011 à 13:48. Évalué à 0.
bigre ça n'a pas manqué, j'ai eu beau me relire, j'ai fait des erreurs:
```
shannon() {
    # le deuxième argument est optionnel: c'est l'unité d'information
    # désirée (2 pour le bit, 2^8=256 pour l'octet, etc...) 
    h="${1^^}"
    if [[ "$h" =~^[A-F0-9]+$ ]]
    then bc -l <<<"scale=64; ibase=16; l(${h//?/F}/$h)${2!+/l($(printf %x "$2"))}"
    else return -1
    fi
}
```
désolé
- [^] # Re: ERRATUM
  
  Posté par BFG le 26 juin 2011 à 13:51. Évalué à 10.
  
  Pourquoi avoir écrit ça en shell ? C'est assez difficile à lire, et la technicité du journal n'aide pas du tout. (pour tout dire, je n'ai strictement rien compris)
  - [^] # Re: ERRATUM
    
    Posté par Thomas Douillard le 26 juin 2011 à 15:04. Évalué à 10.
    
    J'ai rien compris non plus, par contre je suis complètement perplexe sur les bouts que j'ai l'impression de comprendre un peu ...
    
    Déja calculer l'entropie d'un Hash ça m'a l'air douteux, par construction. Le hash doit pas être loin de la quantité d'information d'un truc aléatoire ou très bien compressé, donc tu dois avoir à peu prêt une valeur constante.
    
    Ensuite omme la relation entre le hash et l'information est bijective, Euh comment dire ? Non ? t'as un nombre fini de hash et un nombre potentiellement infini d'informations, ça ne peut pas être bijectif. Cf. la recherche de collisions MD5.
# Patience, patience...

Posté par grondilu le 27 juin 2011 à 21:17. Évalué à -2.

ça m'a pris deux jours entiers mais j'ai fini par écrire un prototype d'horodateur cryptographique reposant sur ce principe de fonctionnement. Je l'ai un peu testé et ça a l'air de fonctionner. Par contre ça reste en bash donc ce sera un peu limité point de vue performance.

Je le publie demain c'est promis.
- [^] # Re: Patience, patience...
  
  Posté par stopspam le 27 juin 2011 à 22:51. Évalué à 1.
  
  ça a l'air intéressant. Tu aurais un petit exemple concret à proposer si ça te prends pas trop de temps ?
- [^] # Re: Patience, patience...
  
  Posté par Ontologia (site web personnel) le 28 juin 2011 à 11:37. Évalué à 2.
  
  Est-ce que tu pourrais un peu approfondir le parallèle entre bitcoin et ton idée, parce que je crois que personne n'a compris là...
  
  « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
# gni

Posté par steph1978 le 27 juin 2011 à 23:55. Évalué à 3.

En lisant le titre, je ne comprenais pas le moinsage (-6 alors que j'écris).
Mais en lisant le contenu, j'ai compris.
J'ai compris que je n'ai rien compris.
Qu'est ce que ça fait, comment, pourquoi ?
Comment ça se met en pratique ?
Franchement, merci pour la tentative de partage, c'est toujours appréciable.
Mais si tu voulais prendre le temps de bien formuler le problème, la solution et sa mise en pratique, nous aurions tous à y gagner.
# chose promise, chose due :)

Posté par grondilu le 28 juin 2011 à 12:54. Évalué à -2.

Voilà:

http://s0.barwen.ch/~grondilu/cgi-bin/timestamp

Je vais écrire une nouvelle entrée de journal cet aprem' sur le sujet.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.