Bitcoin : Cryptographie et cryptomonnaies

Quels sont les problèmes à résoudre du point de vue de l’utilisation du système dans Bitcoin ?

• Élimination des intermédiaires et de la centralisation

• Envoi d’argent et authentification

• Suivi des soldes des comptes

• Transactions complexes

• Prévenir les fraudes, e.g. double dépense

• Pertes de bitcoin

• Anonymat

• Confiance

• Génération des bitcoins / amorce du système

Quelles sont les problèmes à résoudre du point de vue du fonctionnement interne du système de Bitcoin ?

• Ouverture : N’importe qui doit pouvoir participer, Volatilité des nœuds, Hétérogénéité, Langage de programmation, Transparence

• Transactions : Historique, Ordre, Multi-parties, Différées, Garantir qu’une transaction sera traitée, Réversibilité des transactions, Double dépense

• Structures de données réparties : Tenue du grand livre, Efficacité des calculs, Sécurité (se protéger et détecter les fraudes)

• Calculs répartis : Efficacité, Intégrité des données et du système, Structures de données, Latence, Consensus (preuve de travail), Décentralisation

• Sécurité : Anonymat vs identité, Gestion des clés publiques et privées (Si on perd sa clé), Confiance (Audit, Intégrité des transactions), nœuds malicieux.

• Autres : Motiver les mineurs, Amorcer le système et l’entretenir (génération de la monnaie)

Comment la monnaie fiduciaire et les cryptomonnaies s’opposent telle ?

Monnaie fiduciaire :

• Contrôle de l'approvisionnement (fausses monnaies)

• Renforcement des propriétés de sécurité.

• Prévention des fraudes.

• Implique un système bancaire avec des lois et de la centralisation.

Cryptomonnaies :

• Aucune autorité centrale.

• Utilisation de la technologie pour encoder les règles dans le système.

• Utilisation de fonction de hachage cryptographique. et de signatures digitales.

Qu'est-ce qu’une fonction de hachage ?

Processus/fonction mathématique qui prend une entrée (ou "message") et génère une chaîne de caractères de longueur fixe appelée une valeur de hachage.

Quelles sont les 6 propriétés d’un fonction de hachage ?

1. Entrée = chaîne de caractères de taille variable

2. Sortie = chaîne de taille fixe

3. La valeur de hachage se calcule très rapidement (O(n) pour une chaine de taille n)

4. Résistance aux collisions

5. Dissimulation et liaison

6. « Puzzle friendliness »

NB : 4, 5, et 6 sont propres aux fonctions de hachage cryptographique

En quoi consiste la propriété de résistance aux collisions des fonctions de hachage cryptographique ?

• Définition : Une fonction de hachage H est dite résistante aux collisions s’il est infaisable de trouver deux valeurs x et y telles que x <> y et H (x) = H(y).

  Infaisable n’implique pas qu’on ne peut trouver une collision » mais plutôt introuvable dans un laps de temps réaliste.

  Application : On ne peut pas changer/modifier un message pour un autre ce qui est utile vérifier l’intégrité d’un fichier ou d’un message (empreinte numérique)

En quoi consiste la propriété de dissimulation et liaison des fonctions de hachage cryptographique ?

• Dissimulation (hiding)

  pour toute valeur de hachage h, il devrait être difficile de trouver un message m tel que H(m) = h

• Liaison (binding) :

  liaison entre le message et sa clé de hachage (on ne peut pas changer/ modifier un message).

Application : Engagement (commitment)

Comment fait-on pour conserver les propriétés de la fonction de hachage cryptographique sur un ensemble pas assez grand ?

Concaténer l’entrée avec une valeur tirée d’une distribution de probabilité très étendue (ex. aléatoire).

Ex: Engagement (voir image)

Que signifie la propriété de puzzle friendliness des fonctions de hachage cryptographique ?

• Problème difficile à résoudre :

  Si pour toute sortie y à n-bit, (y = la clé de hachage) et si n est choisi dans une distribution très étendue (n = nonce) :

  il est infaisable de trouver un m tel que H(n ‖ m) = y dans un temps significativement moindre que 2^n.

  Autrement dit si on possède une partie de l’entrée (n) et la sortie (y), il est très difficile de trouver le reste de l’entrée (m).

• La solution est facile à vérifier :

  Il suffit de calculer la clé de hachage et de vérifier si elle vérifie la contrainte  H(n \\ prev_hash \\ m) < cible.      

Quel est le nombre de bits des clés de hachage qu’utilise bitcoin ?

Dans Bitcoin, on prend un message de taille quelconque et on le découpe en blocs de 512 bits pour produire une clé de hachage 256 bits

C’est quoi un pointeur de hachage ?

Contient :

• Un pointeur vers de l’information emmagasinée qui sert à retrouver cette information

• Une clé de hachage cryptographique de l’information

  qui sert à vérifier que l’information n’a pas été modifiée

C’est quoi une chaîne de bloc ?

Structure de données construite avec des pointeurs de hachage

Comment les chaines de bloc assurent t-elles la sécurité de l’ informations ?

• La clé de hachage contenue dans un pointeur de hachage est calculée sur toutes les données du bloc précédent (incluant le pointeur de hachage du bloc qui précède le bloc précédent).

• Il est donc impossible de trafiquer un bloc dans la chaine de blocs sans que les autres ne le sachent (car pour modifier un bloc, il faut modifier tous les blocs subséquents + le pointeur de hachage détenu par l’usager)

Pourquoi est-ce important d’inclure le pointeur de hachage du bloc précédent dans le calcul de la valeur de hachage ?

Pour éviter contourner ces 2 faiblesses :

• Modifier les données d’un seul bloc et le hash de ce bloc sans devoir répercuter le changement dans toute la chaine

• Dérouter la chaine en modifiant le pointeur

C’est quoi l’arbre de Merkle ?

Arbre binaire construit avec des pointeurs de hachage.

• Feuilles -> données

• Nœud non terminal : clé de hachage des fils

NB : Les feuilles de l'arbre Merkle sont de gauche à droite dans le même ordre que la liste des transactions du bloc.

A quoi sert l’arbre de Merkle (avantages) ?

• Mise en évidence de modifications des nœuds

• Efficacité pour le parcours (démonter la validité/intégrité d’une transaction sans devoir emmagasiner l’arbre au complet)

• Preuve de non-appartenance

Comment l’arbre de Merkle permet t-il de faire les audits ?

Il permet de démontrer la validité d’un sous-ensemble de transactions incluses dans un ensemble plus large sans révéler :

• ni l’ensemble de transactions complet,

• ni le sous-ensemble

Comment sont utilisés les chaines de blocs et les arbres de Merkle dans les Bitcoin ?

La chaîne de blocs Bitcoin contient deux structures de hachage différentes :

• Le premier est une chaîne de hachage de blocs qui relie les différents blocs entre eux.

• Le second est interne à chaque bloc et est un arbre Merkle de transactions au sein des blocs.

Quelle information minimale faut-il pour prouver qu’une transaction appartient à un bloc (exemple) ?

Pour savoir si Td est dans l’arbre de Merkle, il faut télécharger seulement une partie de l’arbre de Merkle

• les nœuds intermédiaires en orange,

• la racine en vert, qui sera aussi dans la chaine de blocs

• Calculer Hd, puis Hcd, etc.

Quel sont propriétés souhaitées de la signature digitale ?

• Seulement l’auteur peut utiliser sa signature

• Tout le monde peut vérifier la signature

• Une signature est liée à un document donné (elle ne peut pas être copiée, ni utilisée pour d’autres documents)

Relation entre clé privée et clé publique

Génération conjointe :

• Sont liées mathématiquement de manière asymétrique

• Les données encryptées par une clé ne peuvent être décryptées que par l’autre clé ( il est possible de dériver la clé publique à partir de la clé privée mais l’inverse est quasi impossible)

Quelles sont les propriétés de la clé publique ?

• Ne permet pas de retrouver la clé privée

• Utilisation : Encrypter des données, Vérifier une signature numérique

Quelles sont les propriétés de la clé privée ?

• Décrypter les données encryptées avec la clé publique

• Signer numériquement des données

Comment signer et vérifier une signature digitale ?

1. Générer une paire (clé privée, clé publique)

   • (sk, pk) := generates(keysize)

2. Signer le message avec la clé privée

   • On signe tout le message :

     Approche 1 : signature: = sign(sk, message)

   • On signe plutôt la clé de hachage du message car c’est plus efficace :

   • Approche 2 : signature := encrypt(sk, hash(message))

3. Vérifier la signature d’un message avec la clé publique

   • Approche 1 : isValid := verify(pk, message, signature)

   • Approche 2 : isValid := isEqual(decrypt(pk, signature), hash(message))

Qu’implique utiliser une signature digitale avec la cryptomonnaie ?

• Signer avec la clé (privée) = encrypter la valeur de hachage du document avec la clé privée

• Signer un pointeur de hachage = signer la structure de données complète vers laquelle le pointeur point :

  • Signer le pointeur de hachage de la tête de la chaine de blocs est équivalent à signer toutes les transactions contenues dans la chaine de blocs

  • Signer la racine d’un arbre de Merkle est équivalent à signer toutes les transactions contenues dans l’arbre de Merkle

  • Raison : toute modification d’une partie de la structure de données va entrainer des inconsistances dans la racine

Qu’appelle t-on “adresses” dans le jargon de Bitcoin ?

C’est la valeur de hachage d'une clé publique qui constitue l’identité d’une personne

Qu’est ce qui constitue l’identité d’une personne dans Bitcoin ?

• Sa clé publique (valeur de hachage)

• On peut générer autant d’identité “différentes” car on peut générer autant de paires (sk, pk) que l’on veut.

• Généralement appelé “adresse” dans le jargon Bitcoin