Journal Un horodateur cryptographique en bash

Posté par  .
Étiquettes :
-31
28
juin
2011

Voilà, après trois jours de travail acharné, je publie une première version de mon concept d'horodateur cryptographique:

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

Il y a énormément de choses à dire sur ce projet, mais je fatigue là, donc je vais me limiter à l'essentiel.

Je publie le code sous licence DWTFYW. Si vous ne savez pas ce qu'est cet acronyme, c'est expliqué dans l'entête du code.

Tout est écrit en bash, et les ticks sont conservées dans un vulgaire fichier CSV. En gros il faut juste la version 4 de bash ou une supérieure, bc et dc, openssl, et les filtres GNU standards.

N'importe qui peut soumettre des ticks avec le client. Plus il y a de ticks soumis, plus le système est solide et l'échelle de temps se linéarise pour se rapprocher de la seconde. Un tick récent peut toujours se voir éjecter de la chaîne la plus ancienne, mais cette probabilité diminue exponentiellement au fur et à mesure que la chaîne grossit.

Ce n'est pas une cryptodevise. Je soupçonne que ça peut être utilisé comme tel mais dans ce cas ce n'est pas une monnaie à agrégat fixe, mais plutôt une monnaie gagée sur le temps. Je pense que du coup ça peut plaire à Stéphane Laborde avec sa théorie relative de la monnaie. En tout cas c'est conçu pour être utilisé par tout système distribué qui désire disposer d'une référence de temps objective et informatiquement prouvable, qui ne dépend pas de la confiance portée envers un détenteur particulier de référence temporelle.

Je pense sincèrement qu'il s'agit d'une invention très riche d'application. Faites-en bon usage.

  • # ???

    Posté par  . Évalué à 10.

    C'est quoi un "horodateur cryptographique" ??? A quoi ça sert ???

    • [^] # Re: ???

      Posté par  . Évalué à -10.

      RTFM

      • [^] # Re: ???

        Posté par  (site web personnel) . Évalué à 10.

        Lu et pas compris.

        A quoi ça sert, tu peux expliquer ?

        Genre montrer un cas d'utilisation de ton bazar parce que là ton journal est pratiquement destiné a n'être compris que par toi, c'est un peu dommage.

        Aussi, la politesse, ça fait jamais de mal.

      • [^] # Re: ???

        Posté par  . Évalué à 10.

        T'es un pote de samwang toi non ? Vous devriez ouvrir une école ou un cirque au choix...

    • [^] # Re: ???

      Posté par  . Évalué à -10.

      J'ai écrit:

      En tout cas c'est conçu pour être utilisé par tout système distribué qui désire disposer d'une référence de temps objective et informatiquement prouvable, qui ne dépend pas de la confiance portée envers un détenteur particulier de référence temporelle.

      Je suis désolé je ne peux pas faire plus clair.

      • [^] # Re: ???

        Posté par  (site web personnel) . Évalué à 10.

        Peut-être pourrais-tu tenter un dernier effort de vulgarisation et nous fournir un exemple pratique ?

        • [^] # Re: ???

          Posté par  . Évalué à -2.

          Ben l'idée de faire un horodateur dédié m'est venue alors que je travaillais à une place de marché décentralisée. En gros le jour où on aura un protocole d'horodatage cryptographique performant, les places de marché du monde entier pourront être entièrement décentralisés, puisqu'il sera possible de prouver l'antériorité d'un ordre par rapport à un autre.

      • [^] # Re: ???

        Posté par  . Évalué à 10.

        C'est quand même dommage d'écrire

        Je pense sincèrement qu'il s'agit d'une invention très riche d'application

        et de pas être foutu de donner un exemple.

        • [^] # Re: ???

          Posté par  . Évalué à 10.

          mais non, toi tu n'as pas lu le journal... Il préfère "se limiter à l'essentiel". Heureusement qu'il l'a fait, sinon, on aurait peut-être pu/dû comprendre.

      • [^] # Re: ???

        Posté par  . Évalué à 4.

        Si, si tu dois pouvoir.

        En tout cas j'espère que quelqu'un le peut, sinon tu vas rester tout seul.

        Comme je le (mal)comprends :
        Le truc c'est de faire compter les ordis avec une fonction compliquée qui fait que t'arrives à une correspondance comptage/temps écoulé (en gros ça demanderait trop d'énergie d'être capable de "tricher" en comptant plus vite) ???
        Ou pas ?

        • [^] # Re: ???

          Posté par  . Évalué à 8.

          Ah, ça me rappelle de vieux cours de systèmes distribués ... je ne sais pas si c'est bien de cela dont il s'agit, mais bref, lorsque de nombreux systèmes doivent s'échanger des messages, il arrive souvent qu'on aie des problèmes de synchronisation car on ne peut pas avoir facilement une base de temps commune à toutes les machines (typiquement chaque machine possède sa propre horloge, donc on ne peut pas 'dater' les messages transmis avec cette information).

          Du coup, on peut passer par un serveur unique qui fournit des estampilles (un genre d'ID/date) à chaque demande d'un client. De cette façon la base de temps est commune à tout le système (ou tous les systèmes plutôt ...).

          Bien sûr, il y a un problème lorsque le serveur d'estampilles tombe ... le but va donc être de trouver une méthode plus robuste. D'après mes vagues souvenirs, il y beaucoup d'architectures/méthodes/algorithmes différents pour résoudre ce problème. Par exemple dans certaines architectures, lorsque le serveur tombe, un nouveau serveur est désigné par une sorte de 'vote' par les autres machines. Dans d'autres cas, tous les noeuds sont au même niveau, et il faut utiliser des algos d'exclusion-mutuelle-distribuée tirés par les cheveux.
          J'ai l'impression que cela rejoint l'idée d'horodateur distribué, mais je peux me tromper complètement ...

          /mode_perplexe on

          • [^] # Re: ???

            Posté par  . Évalué à 2.

            Souvent on a pas besoin d'une horloge "absolue" : typiquement pour garder la cohérence.

            A ce moment il existe des algo qui permettent de jouer sur la délivrance des messages pour que sur tout les serveurs du cluster, les messages soient délivré dans un ordre cohérent (il y a des niveaux de cohérence en fonction de ton besoin).

            Bien sûr ça ne résiste pas à une faille bizantine (c'est bien comme ça qu'on dis ?), c'est à dire qu'un serveur agit pour détruire le groupe ou de manière aléatoire.

            Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

            • [^] # Re: ???

              Posté par  . Évalué à 2.

              En fait, il a fait un truc qui existe depuis longtemps, en moins bien :)
              Enfin si j'ai compris son article...

              http://fr.wikipedia.org/wiki/Horloge_logique

              Quelle idée de l'écrire en bash aussi ...

              • [^] # Re: ???

                Posté par  . Évalué à -3.

                Merci pour la référence, c'est exactement ça. Cet article m'a amené vers l'article anglais: http://en.wikipedia.org/wiki/Lamport_clock.

                C'est bien de ça dont il s'agit, à la différence près que chaque timestamp ici inclut une preuve cryptographique. Ce qui permet de travailler avec des noeuds dans lesquels on n'a pas confiance.

                • [^] # Re: ???

                  Posté par  . Évalué à 1.

                  Ben tu vois on pouvait faire plus compréhensible. Un troisième journal pour fêter çà ?

                • [^] # Re: ???

                  Posté par  . Évalué à 3.

                  C'est bien de ça dont il s'agit, à la différence près que chaque timestamp ici inclut une preuve cryptographique. Ce qui permet de travailler avec des noeuds dans lesquels on n'a pas confiance.

                  Oui enfin ça il faudrait encore le prouver, ce qui demande de commencer par être capable d'expliquer ton aglo et de définir ses propriétés.

                  Autrement y'a deux ou trois trucs qui ont déjà été prouvés concernant les systèmes distribués asynchrones dans le domaine des horloges logiques, du (partial|total)-order et des pannes byzantines ces 40 dernières années.

  • # tu vas...

    Posté par  (site web personnel) . Évalué à 10.

    mais je fatigue là, donc (...)

    ... Tu vas te reposer et ne plus écrire de journaux.

    • [^] # Re: tu vas...

      Posté par  . Évalué à 10.

      Moi quand je lis un journal comme ça ça me donne envie de lire "D'où viens-tu, Scrameustache ?", pour me rappeler que je peux comprendre des trucs sans trop forcer.

      • [^] # Re: tu vas...

        Posté par  . Évalué à 9.

        Je pertinente juste pour la référence à ma bande dessiné préféré de quand j'étais petit.

        C'était mieux à vent de toute façon.

        • [^] # Re: tu vas...

          Posté par  . Évalué à 4.

          Pareil. T'as quel âge par curiosité ? J'étais fan des galaxiens.

          • [^] # Re: tu vas...

            Posté par  . Évalué à 1.

            Bah à vu de nez comme moi bande de quarantenaires !

            • [^] # Re: tu vas...

              Posté par  . Évalué à 2.

              Comment je suis trop un jeune. J'ai à peine les trois quarts de cet âge canonique.

              • [^] # Re: tu vas...

                Posté par  (site web personnel) . Évalué à 2.

                Je tiens à témoigner qu'il y a aussi des ex-fans du crabe à moustache qui ont environ 87% de ton age.

                pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

  • # C'est pas faux

    Posté par  . Évalué à 10.

    C'est pas faux !

  • # Histoire de comprendre

    Posté par  . Évalué à 3.

    J'ai l'impression que cette phrase issue de la doc:

    "This is the whole point: creating a artificial sequence of events with a perfectly known probability. If we manage to do this, then the Shannon information associated to this probability has to be related to time"

    Pourrait permettre de comprendre, mais il manque quand même une info essentielle:
    comment est calculé le hash pour un temps donné?

  • # bash

    Posté par  . Évalué à 3.

    Un programme un peu complexe écrit en shell, j'ai quelques doutes, je commence à lire, puis je vois :

    # a function to compare two floating point numbers
dccompare() {
    # returns:
    # - '>' if $2 > $1
    # - '=' if $2 = $1
    # - '<' if $2 < $1
    dc <<<"
    [[>]Pq]sg
    [[=]Pq]se
    [[<]Pq]sl
    $1
    $2sa
    d la >g
    d la =e
    d la <l"
}

    C'est documenté, aucun problème, par contre pour trouver la source d'un bug et le corriger...

    • [^] # Re: bash

      Posté par  (site web personnel) . Évalué à 5.

      $1 c'est bien le premier paramètre, non ? et $2 le second ?
      Dans ce cas, dccompare($1, $2) retourne ">" si $1 < $2 ?

      Ben j'espère ne pas avoir bien compris comment ça marche :-(

      • [^] # Re: bash

        Posté par  . Évalué à 1.

        j'ai du relire trois fois ton commentaire pour comprendre et effectivement je suis d'accord avec toi

        dccompare($1, $2) retourne > si $2 > $1
        c'est carrément moins lisible que l'inverse (le retour ne suis pas l'ordre des paramètres)

        dccompare($1, $2) retourne > si $1 > $2
        ca aurai été bien plus lisible lors d'un appel.

    • [^] # Re: bash

      Posté par  . Évalué à 2.

      Je connais très mal dc, il y a pas moyen de faire ça en bash ? $1 et $2 sont de quels formes ?

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

      • [^] # Re: bash

        Posté par  . Évalué à 2.

        Bash ne supporte pas les nombre à virgule flottante à ma connaissance : $((1.1+2))=2.

        • [^] # Re: bash

          Posté par  . Évalué à 5.

          zsh non plus apparemment :

          echo $((1.1 + 2))
3.1000000000000001

          • [^] # Re: bash

            Posté par  . Évalué à 3.

            J'arrive pas à savoir si c'est une bonne blague ou une demande de pointeur sur un simulateur IEEE-754 ?

            • [^] # Re: bash

              Posté par  . Évalué à -1. 

              % python -c "print repr(1.1)"
1.1000000000000001

% echo $((1.1 * 10))
11.

      • [^] # Re: bash

        Posté par  . Évalué à 1.

        man dc ? :)

        allez, je suis pas chien, c'est l'option -e

        $ dc -e "1.2 3.1 + p"
4.3

        • [^] # Re: bash

          Posté par  . Évalué à 3.

          Waow ! Merci de me faire découvrir man que je ne connais pas du tout...

          Je n'ai pas étudié tout le code et le ne savais donc pas quel forme avait les deux nombres (hexadécimal, à virgule flottante,...) c'était ma seule question. Le code n'est pas aussi simple qu'une addition.

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

          • [^] # Re: bash

            Posté par  . Évalué à 1.

            ça me fait plaisir :)

            ouais en fait, j'avais interprété ton commentaire de travers. Je pensais que tu faisais une remarque sur l'utilisation de dc dans le petit bout de script au dessus mais en fait, non.

  • # oui mais.....

    Posté par  (site web personnel) . Évalué à 4.

    Je vais encore jeter un pavé dans la marre....

    Typiquement j'ai vu ce genre de problématique de synchronisation des timestamps au delà de la seconde sur des ordres bourses... Je vais pas rentrer dans le détail mais :

    Un bon ntpd au cul de tes machines, des serveurs de temps redondés en stratum stratosphérique qui eux peuvent attaquer l'horloge parlante et tout ce beau monde ca cause à la mesure !

    Fuse : j'en Use et Abuse !

    • [^] # Re: oui mais.....

      Posté par  . Évalué à 0.

      tout a fait c'est meme a la milliseconde sur les flux de donnees, et Un ntpd convient parfaitement...
      Quant au choix de bash pour ce genre de chose, je doute de la robutesse et de la fiabilite du processus.

      A quand la version -rt ?

      • [^] # Re: oui mais.....

        Posté par  . Évalué à 3.

        Les méthodes de synchronisation d'horloge sont utiles que dans une petite partie des problèmes de l'informatique distribuée. Ça ne résout aucunement les situations où on a besoin de déterminer la causalité entre des événements (horloge logique) ou quand tu as des participants non coopérants (panne byzantine). C'est très bien pour uniformiser des logs par contre...

        La plus grosse erreur en informatique c'est de penser que quelque chose peut tout résoudre. Alors balancer une solution sur un problème totalement incompréhensible c'est chaud quand même... (Où alors c'est d'oublier de penser que des gens plus intelligents que nous on déjà résolu la plupart des problèmes il y a 40 ans, je ne sais plus...)

Suivre le flux des commentaires

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