« Proof of Work » pour les nuls
Qu’est ce que la crypto-monnaie KDA de Kadena ?
17 novembre 2021Qu’est ce que la crypto-monnaie SYL de XSL Labs ?
18 novembre 2021"Preuve de travail" ou "Proof of Work" pour les nuls
Nous sommes en 1997. Internet se développe à un rythme effréné. Mais, tandis que l’homme construit rapidement sa plus grande invention, quelques personnes malintentionnées complotent tranquillement pour tout gâcher.
Ils veulent abuser de la portée et de l’accessibilité d’Internet en l’inondant d’emails promotionnels non sollicités : du « spam », comme l’appellent les jeunes.
Et en 1997, les boîtes de réception sont partout d’accord : les spammeurs ont gagnés.
Pourquoi les gens envoient-ils du spam ?
La plupart des spams essaient de vendre quelque chose (publicité) ou essaie d’inciter un utilisateur à partager des informations sensibles (hameçonnage/Phishing) que l’expéditeur peut utiliser de manière malveillante.
Pourquoi est-il si facile d'envoyer des spams ?
Un email individuel est un petit fichier qui peut être reproduit et distribué quasi-instantanément à des millions de personnes pratiquement sans frais (par rapport aux meilleures options suivantes).
L’envoi d’e-mails est bon marché principalement parce que :
- Le canal de distribution (Internet) est essentiellement gratuit et ouvert à tous
- Il nécessite des ressources de calcul négligeables pour envoyer un e-mail
Le premier fait, au moins en 1997, était peu pratique à changer.
Mais le second était beaucoup plus négociable.
Et si nos protocoles de messagerie nécessitaient un ordinateur pour effectuer un effort de calcul modeste afin d’envoyer un message ?
L’envoi d’un seul email ne serait pas trop exigeant (peut-être ne prendrait-il qu’une seconde environ), mais envoyer des millions et des millions deviendrait rapidement un effort herculéen nécessitant des ressources de calcul massives, et donc coûteuses.
Cela a donné naissance à des systèmes de preuve de travail. (PoW)
Dans un système de preuve de travail, un ordinateur doit résoudre un problème de calcul d’un niveau de difficulté prédéterminé avant d’être autorisé à effectuer une action souhaitée.
Une fois que l’ordinateur a résolu le problème, il partage sa réponse comme « preuve » de ses efforts.
Un autre ordinateur est capable de vérifier rapidement la preuve et de permettre l’action souhaitée.
Dans le cas de la limitation du spam, nous voudrions que notre client de messagerie accepte uniquement un e-mail de quelqu’un qui a fourni la preuve qu’il a fait un effort pour nous le faire parvenir.
Alors, comment peut-on vérifier qu'un ordinateur a fait un effort particulier ?
Imaginez que nous ayons une fonction qui, pour une entrée donnée, produit une sortie de taille fixe.
Assez simple.
Lorsque nous envoyons une simple chaîne via notre fonction :
Il renvoie :
Il produit cette sortie chaque fois que nous envoyons cette chaîne exacte à travers lui.
Maintenant, regardez ce qui se passe lorsque nous modifions un seul caractère dans notre entrée :
Retour :
Le rendu est radicalement différent !
Cela rend impossible la rétro-ingénierie de la façon dont l’entrée est transformée en sortie. De minuscules modifications de notre entrée ne créent pas de changements évidents et mesurables dans la sortie.
N’oubliez pas non plus que notre sortie est toujours une chaîne de taille fixe. Dans cet exemple, notre sortie comportera toujours 64 caractères.
Par souci de simplicité, imaginons que chaque caractère de la chaîne de sortie ne peut être que l’une des 16 valeurs hexadécimales (0-9, af). Même avec ces contraintes, notre fonction donne un nombre énorme de sorties possibles.
Compte tenu de l’énorme gamme de valeurs de sortie possibles, nous serons en mesure de générer une chaîne de sortie unique pour à peu près n’importe quelle entrée.
Parfois, deux entrées différentes correspondent à la même valeur (une « collision »), mais dans notre fonction, cela est extrêmement rare.
En termes simples : notre fonction crée un identifiant unique pour presque toutes les entrées uniques.
Il existe un nom fantaisiste pour le type de fonction que nous venons de créer : une « fonction de hachage cryptographique ».
Les fonctions de hachage cryptographique ont quelques autres propriétés, mais notre exemple couvre les plus pertinentes. Donc…
Comment pouvons-nous utiliser cette fonction pour « prouver » qu'un ordinateur a effectué du travail ?
Rappelez-vous que notre fonction s’exécute rapidement. Il est facile à exécuter avec des entrées arbitraires et à produit une sortie unique.
Mais, imaginez si nous demandions :
En supposant que l’ordinateur n’ait jamais vu la chaîne de sortie particulière (et ait connu l’entrée qui l’a produite), il devrait commencer à faire des suppositions aléatoires et à vérifier la sortie.
Mais, rappelez-vous, cela peut prendre jusqu’à 16^64 pour obtenir la bonne réponse.
Cela pourrait littéralement prendre des milliards d’années à résoudre, alors à la place, nous pourrions poser une question beaucoup moins exigeante comme :
random_string= 'a638e5L'
Même s’ils découvraient une entrée, n, qui avait précédemment produit une sortie commençant par trois 0, cette même entrée n combinée à une chaîne aléatoire produirait une valeur très différente, les obligeant à repartir de zéro et à résoudre un n différent.
Maintenant, évidemment, notre fonction de génération de chaînes aléatoires devrait être vraiment aléatoire. Un générateur aléatoire à moitié calculé qui produirait les mêmes défis plus fréquemment que la probabilité pure augmenterait la probabilité qu’un challenger reçoive le même défi deux fois.
Mais, c’est une autre histoire pour un autre jour.
En mettant tout cela ensemble, une fonction simple pour deviner la valeur de n pourrait ressembler à ce qui suit :
def mint(challenge, work_factor):
guess = 0
while True:
n = str(guess)
if verify(challenge, work_factor, n):
print("Found the correct guess!")
return n
guess += 1
Dans le code ci-dessus, « challenge » est la chaîne aléatoire que nous enverrons à un challenger.
Et nous pourrions valider des suppositions aléatoires pour n avec quelque chose comme ça. Nous demandons simplement si Hash(n + random_string) renvoie une valeur commençant par un nombre suffisant de 0.
def verify(challenge, work_factor, n):
full_header = n + str(challenge)
h = hashlib.sha256()
h.update(full_header.encode('utf-8'))
hash_output = h.hexdigest()
for i in range(0, work_factor):
if not hash_output[i] == str(0):
return False
return True
Assez simple, non ?
Nous devrons développer quelques éléments supplémentaires pour rendre cela raisonnable, en particulier pour les concepts inventés pour lutter contre le spam (Hashcash, en particulier), mais j’espère que cela illustre la théorie sous-jacente de la preuve de travail. (ou PoW)
La preuve de travail qui sous-tend actuellement les principales crypto-monnaies est une extension et une mise en œuvre relativement élégante de l’idée décrite ici.
source : Steward Fortier
