Systèmes monétaires et argent virtuel

Systèmes monétaires et argent virtuel

MÉCANISMES D’ENCHÈRE

Les enchères à proprement parlé sont nées vers -500 avant J.C pour la vente d’esclaves. Deux systèmes étaient alors utilisés : la majorité des enchères étaient descendantes sauf pour la vente de belles femmes, qui étaient alors ascendantes(principale source de cette section).
Aujourd’hui, l’utilisation d’enchères est omniprésente. Que ce soit au niveau d’un pays pour la vente du spectre hertzien (CDMA, UMTS), la vente de l’électricité en Californie ou bien au niveau du simple internaute qui achète un vieil ordinateur portable sur eBay, tous utilisent un système d’enchères. En Europe, les appels d’offres des Marchés Publics représentent 8% du PIB.
Dans une enchère, chaque participant donne un prix qui serait prêt à payer pour l’acquisition d’un ou plusieurs objets. Un système évalue ensuite qui sont le ou les gagnants et indique le prix qui va être payé. Ce système varie suivant le type d’enchère.

De la Théorie des jeux aux Mécanismes d’Incitation Algorithmique

Les mécanismes d’incitation sont une branche spécifique de la théorie des jeux. Cette dernière fut développée principalement par John von Neumann et Oskar Morgenstern. C’est en recherchant une modélisation mathématique du jeu des échecs (problème soulevé alors par le mathématicien hongrois Ernst Zermelo), que John Von Neumann commença à jeter les premières bases de la théorie des jeux. Il trouva ainsi une stratégie unique déterminée selon toutes les possibilités choisies par l’adversaire. Il généralisera plus tard ce modèle avec l’aide de Oskar Morgensten à l’université de Princeton. Les résultats de ses recherches seront publiés dans Theory of games and economic behavior. La théorie peut alors être appliquée sur des jeux à somme nulle, où ce que l’un gagne l’autre perd, et principalement pour deux joueurs.
Loin encore de pouvoir être utilisée économiquement, la théorie fut alors très appliquée dans le domaine militaire.
Plus tard, John Forbes Nash généralisa alors la théorie de John von Neumann. Grâce à sa théorie des minimax (démontré en 1928), John von Neumann démontra l’existence d’équilibres pour les jeux à somme nulle pour deux participants non coopératifs. Cet équilibre se distinguait par le moment où aucun des deux participants n’a intérêt de changer de stratégie si l’autre ne la change pas également. Intuitivement, cet équilibre est l’état dans lequel chaque participant y trouve satisfaction. John Forbes Nash démontra qu’il existe un même équilibre, appelé équilibre de Nash, pour tous jeux, qu’ils soient à somme nulle ou non nulle et pour n’importe quel nombre de joueurs. Bien que peu considérée au début, sa théorie est aujourd’hui appliquée à de très nombreux domaines, qu’ils soient économiques ou informatiques. Il reçut à ce titre le prix Nobel 1 d’économie en 1994.

Architecture autonome

Traditionnellement, l’ISP ne pouvait pas en tout temps corriger les problèmes de bande passante de ses VPN, puisque la gestion était essentiellement statique. Il n’y avait aucune anticipation et une négociation était à chaque fois nécessaire afin de rentre toute modification possible. Pour répondre à ce premier problème, et rendre la gestion de la bande passante des VPN dynamiques, il faut mettre en place une architecture autonome, qui se suffit à elle-même.
Elle doit prendre les décisions, négocier les nouveaux paramètres et pouvoir les appliquer sans aucune intervention.
Afin de répondre à cette première problématique, l’Autonomic Service Architecture (ASA) est proposée par Yu Cheng et coll en 2006. C’est une architecture autonome qui gère l’ensemble des ressources. Elle est composée de nombreux composants qui interagissent ensemble automatiquement afin de réguler l’octroi de la bande passante aux clients du système, en suivant leurs besoins.
Chaque client signe un contrat (SLA) avec l’ISP indiquant la bande passante souhaitée ainsi que les divers termes de flexibilité que permet l’ASA. L’ensemble des SLA est stocké dans une base de données afin que l’architecture puisse le consulter en tout temps. Un système de surveillance des activités réseau (logimètre) est continuellement en service afin de pouvoir connaître en temps réel l’utilisation de la bande passante de chacun des VPN.
C’est à partir de cet ensemble d’informations que l’architecture ASA va prendre ses décisions.
La surveillance d’activité et la base de données des SLA permettent de détecter les problèmes.
La résolution se fait alors via un module de gestion des opérations. En accord avec les SLA, celui-ci va utiliser les ressources des VPN non surchargés et les réorienter vers les VPN surchargés.

Architecture distribuée

Internet est un très vaste champ d’applications pour les mécanismes d’incitations qui peuvent être appliqués à de nombreux modèles : routage entre domaines, partage de fichiers poste-à-poste (P2P), gestion de cache internet ou encore distribution de tâches. Tous ces modèles ont un point commun, directement lié du fait de l’utilisation d’internet : ils utilisent tous des entités distribuées et indépendantes cherchant à maximiser leur profit sans toujours considérer l’intérêt des autres entités.Afin de permettre l’utilisation des mécanismes d’incitation algorithmique (AMD) de façon distribuée, il est nécessaire d’en modifier quelque peu le fonctionnement pour permettre la participation de plusieurs entités indépendantes tout en gardant l’aspect incitatif.
En 2002, Joan Feigenbaum et coll. publièrent un ensemble de problèmes ouverts et de voies de recherche sur les mécanismes d’incitation algorithmique distribués (DAMD). Un des problèmes énoncés repose sur la difficulté d’utiliser des algorithmes distribués avec des entités indépendantes qui peuvent mentir ou se tromper. Ces difficultés sont liées au fait qu’il n’existe aucune entité ou aucun algorithme permettant de vérifier les réponses de chaque agent. L’intérêt des DAMD est alors d’inciter à donner les réponses attendues plutôt que de vérifier formellement celles-ci.
Klein et coll. proposent en 2008 un mécanisme d’incitation distribué en deux étapes appliqué à la gestion de transfert d’informations tactiques militaires. Comme ces informations sont nombreuses et le temps de transfert important, il faut prioriser l’information qui va traverser le maillage d’entités indépendantes. Pour ce faire, les auteurs proposent un mécanisme avec deux étapes plutôt qu’une habituellement. Au début de chaque itération, chaque participant annonce son importance. Un centre décide alors d’un plan optimal pour le transfert, en fonction des priorités, et l’annonce à tout le monde. Enfin, les participants transfèrent leur message, en suivant ou non le plan. Plus ils suivent le plan, plus ils seront payés. Cette solution peut paraître naïve, mais repose sur le fait qu’aucun ne peut surévaluer l’importance de son message, car celui-ci pourra toujours être évalué à la réception. Cette restriction est malheureusement très peu présente dans le problème d’allocation de bande passante. De plus, le centre doit être constamment à portée de chaque participant. Enfin, comme le meilleur plan de transfert est calculé uniquement par le centre, des petites itérations de l’ordre de la seconde ne sont plus envisageables

Systèmes monétaires et argent virtuel

Les systèmes d’enchères utilisés par les mécanismes d’incitation ont besoin d’un système de paiement utilisant, selon les cas, de la monnaie virtuelle ou non, afin de permettre un transfert d’argent entre les différents participants. De manière générale, ces systèmes de paiement doivent permettre des transferts ayant les propriétés d’être intègres, autorisés, confidentiels, disponibles et fiables. Ces cinq propriétés sont absolument nécessaires pour garantir qu’un transfert d’argent sera effectivement fait entre les deux participants désignés, de façon volontaire et du montant voulu. Tout manquement à une unique propriété met en faillite tout le système.
Un tel système est naturellement soumis à plusieurs attaques menaçant ces propriétés essentielles:
Attaque par rejeu :
Dans ce type d’attaque, on intercepte dans un premier temps un ou plusieurs messages (sans forcément en comprendre le sens) qu’on enregistre afin de pouvoir, dans un deuxième temps les retransmettre. Ceci peut permettre, par exemple, de faire des double spending, c’est-à-dire des doubles paiements. Ainsi, un marchand pourrait écouter un paiement d’un de ses clients et retransmettre une ou plusieurs fois celui-ci à la banque, récupérant ainsi plusieurs fois le paiement initial.
Terminal falsifié :
Dans le cas où l’utilisation d’un terminal est nécessaire et qu’il ne peut être authentifié, on peut falsifier ce terminal et effectuer une attaque man in the middle (MITM) entre l’utilisateur du terminal et l’exploitant en laissant le terminal intercepter ou modifier la communication. Par exemple, un client d’une banque désirant retirer de l’argent a besoin de sa carte et de s’authentifier grâce à un code PIN, mais il ne peut pas authentifier le guichet automatique, qui peut être un faux.
Attaque par force brute :
Il s’agit ici d’essayer de manière automatisée et systématique toutes possibilités d’entrées les d’un système de protection. Par exemple, on pourrait essayer toutes les possibilités de PIN d’une carte de crédit. Une variante plus efficace, mais moins probante utilise un dictionnaire plutôt que d’essayer toutes les possibilités.
Cryptanalyse :
La moins probable, mais la plus redoutable, cette méthode d’attaque repose sur la découverte d’une faille directement liée à la structure interne ou aux processus qui la composent. Elle peut être possible grâce à l’amélioration des connaissances ou des technologies rendant inutiles ou simples certains mécanismes d’encodage complexe. Par exemple, la découverte d’un algorithme de décomposition en temps polynomial de nombre en produit de facteurs premiers, rendrait tout à fait désuet les systèmes utilisant le fait qu’aucun algorithme n’est actuellement connu pour pouvoir factoriser un produit de nombres premiers en temps polynomial. Par exemple, le célèbre système cryptologique RSA serait alors cassé.

Engagement numérique et mise en gage

Un système d’engagement numérique peut être mis en place pour imposer une forte imputabilité à un participant effectuant une action. Son utilisation, avec l’authentification du participant, permet de garantir qu’une action a bel et bien été entreprise par tel participant. Cet outil permet de nous assurer qu’aucun participant ne pourra nier qu’il a formulé une offre d’achat, proposer de vendre des ressources ou reçu un paiement.L’engagement numérique, ou mise en gage (bit commitment) se déroule en deux phases :
a. La phase d’engagement permet à un participant de s’engager sans révéler cet engagement.
Tout d’abord, il choisit l’information sur laquelle il va s’engager, puis il la passe dans un système d’engagement, appelé commitment schemes qui va encoder l’information afin de la rendre opaque. Il existe deux types d’encodage. Soit il est réversible, et dans ce cas l’information doit pouvoir être décodée ultérieurement, le couple d’encodage/décodage devant garantir que l’entrée et la sortie sont identiques. Soit il n’est pas réversible, et dans ce cas le système d’encodage doit pouvoir être rendu public. L’information encodée est alors envoyée au destinataire, qui possède alors votre information, sans toutefois pouvoir la lire.
b. La phase de révélation permet au deuxième participant de comprendre l’information qu’il a entre les mains. Si l’encodage utilisé est réversible, alors le premier participant lui donne simplement la clé de décodage. Sinon, il lui annonce exactement ce que contient l’information qu’il possède. En encodant lui-même cette information, il doit obtenir exactement l’information encodée qu’il possède, et en déduire que c’est bien l’information annoncée.
Une fois la phase d’engagement effectuée, le participant ne peut revenir en arrière ou mentir sur ce quoi il s’est engagé. Toute l’information sera vérifiée au moment de la phase de révélation. De plus, si l’information est signée, non seulement on ne pourra pas nier l’information, mais celle-ci sera attribuée de façon certaine à un participant.
Des systèmes de mise en gage plus évolués permettent de ne révéler qu’une partie de l’information envoyée, en fonction de la nécessité du moment. On parle alors de systèmes d’engagement à révélation minimum.

Table des matières

INTRODUCTION
CHAPITRE 1 MÉCANISMES D’ENCHÈRE
1.1 Enchères
1.1.1 Enchère anglaise
1.1.2 Enchère hollandaise
1.1.3 Enchère privée de premier prix
1.1.4 Enchère de Vickrey
1.1.5 Enchère double
1.1.6 Enchère japonaise
1.1.7 Enchère suisse
1.2 De la Théorie des jeux aux Mécanismes d’Incitation Algorithmique
1.2.1 Historique
1.2.2 Définitions
1.3 Mécanismes de Vickrey-Clarke-Groves
1.3.1 Mécanisme de Vickrey
1.3.2 Mécanismes de Clarke et de Grove
1.3.3 Complexité des Mécanismes d’incitation
1.4 Problématique
CHAPITRE 2 TRAVAUX ANTÉRIEURS
2.1 Architecture autonome
2.2 Architecture distribuée
2.3 Approximation
2.4 Systèmes monétaires et argent virtuel
2.5 Engagement numérique et mise en gage
CHAPITRE 3 MODÉLISATION
3.1 Généralités
3.2 Menaces et hypothèses
3.3 Modèle simple
3.4 Modèle avancé
3.5 Imputabilité et paiements
3.5.1 Imputabilité
3.5.2 Système de paiement
CHAPITRE 4 IMPLÉMENTATION 
4.1 Choix techniques
4.2 Initialisation
4.2.1 Génération des SLA
4.2.2 Génération de l’utilisation de la bande passante
4.2.3 Initialisation de l’argent de base
4.2.4 Mise en place des stratégies
4.3 Déroulement
4.3.1 Annonces
4.3.2 Calculs
4.3.3 Sélection
4.3.4 Coût total et paiements
4.4 Résultats
CHAPITRE 5 RÉSULTATS ET INTERPRÉTATION
5.1 Simulation avec demandes équilibrées
5.1.1 Context
5.1.2 QoS
5.1.3 Comptes
5.2 Simulations avec demandes déséquilibrées
5.2.2 Simulation avec demandes déséquilibrées 5M-15m
5.2.3 Simulation avec demandes déséquilibrées 15M-5m
CONCLUSION

Télécharger le rapport complet