Un défi informatique peut-il être transformé en preuve de travail?

L'apparence apparemment inutile de l'extraction de crypto-monnaie a soulevé la question d'alternatives utiles, voir ces questions sur Bitcoin , CST , MO . Je me demande s'il existe un algorithme qui peut convertir pratiquement n'importe quel défi de calcul $\mathcal C$ (dont la solution peut être vérifiée efficacement) en un autre tel défi $\Psi(\mathcal C)$ (qui est utilisé pour la preuve de travail) de telle sorte que

1. La fonction $\Psi$ est randomisée, en utilisant une séquence aléatoire (publique) $r$ .
2. Résoudre $\Psi(\mathcal C)$ est généralement aussi dur que la résolution de $\mathcal C$ .
3. Si une solution est trouvée pour , puis une solution peut être efficacement calculé pour le défi d' origine .$x$$\Psi(\mathcal C)$$\Psi^{-1}(x)$$\mathcal C$
4. Connaître une solution pour n'aide pas à trouver une solution pour .$\mathcal C$$\Psi(\mathcal C)$

$\;\:\:$ 4 '(mise à jour). Comme l'a souligné Noah dans un commentaire, la condition précédente doit être renforcée pour exiger que le prétraitement ne donne également aucun avantage dans la résolution de .$\mathcal C$$\Psi(\mathcal C)$

Cette dernière condition est nécessaire pour que personne ne peut être mis dans une position avantageuse simplement parce qu'ils savent une solution de . En utilisant cette méthode, les gens pourraient soumettre des problèmes de calcul qu'ils souhaitent résoudre et une autorité centrale pourrait en choisir quelques-uns dignes d'être résolus (comme trouver des étrangers ou casser des mots de passe). Notez que cela ne semble pas être un problème si le problème prend même une semaine à résoudre (je suppose que ces extraterrestres ne peuvent pas être aussi bons à se cacher;), car cela pourrait entraîner une plus grande récompense pour une solution. Quoi qu'il en soit, ces sujets ne sont pas liés à la solution de mon problème théorique, mais bien sûr, je suis heureux d'en discuter dans les commentaires / sur le forum.$\mathcal C$

Une solution possible serait la suivante: mappe en , c'est-à-dire pour résoudre et un autre défi difficile à calculer. Un problème avec ceci est que connaître une solution à rend la résolution de un peu plus facile (combien plus facile dépend de la difficulté de ). Un autre problème est que est devenu plus difficile que .$\Psi$$\mathcal C$$(\mathcal C,HASH_r)$$\mathcal C$$\mathcal C$$\Psi(\mathcal C)$$HASH_r$$\Psi(\mathcal C)$$\mathcal C$

( Remarque : Andreas Björklund a suggéré une solution dans les commentaires qui, je pense, est meilleure que celle décrite ci-dessous. Voir http://eprint.iacr.org/2017/203 , par Ball, Rosen, Sabin et Vasudevan. En bref, ils fournissent des preuves de travail basées sur des problèmes tels que les vecteurs orthogonaux dont la dureté est bien comprise et auxquels de nombreux problèmes (par exemple, k-SAT) peuvent être réduits de manière relativement efficace. Leur instance PoW est aussi difficile que un vecteur orthogonal dans le pire des cas, même si l'instance d'entrée est facile, de sorte qu'ils évitent un inconvénient majeur de la solution décrite ci-dessous.$\Psi(\mathcal{C})$$\mathcal{C}$

La solution décrite ci-dessous pourrait bénéficier de sa simplicité --- elle peut être décrite à un non-expert --- mais elle me semble beaucoup moins intéressante théoriquement.)

Une solution est possible si l'on fait l'hypothèse forte que "l'algorithme le plus rapide pour est fondamentalement aléatoire" (et si nous modélisons une fonction de hachage cryptographique comme un oracle aléatoire). Une façon de formaliser cela est de dire que$\mathcal{C}$

1. $\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$ (sinon, je suppose que ce n'est pas vraiment un défi valide);
2. l'algorithme randomisé le plus rapide pour s'exécute au temps attendu sur une instance typique; et$\mathcal{C}$$T$
3. il existe une fonction efficacement calculable de au domaine des solutions à pour telle qu'il existe toujours un avec une solution à .$f$$\{0,1\}^k$$\mathcal{C}$$k \approx \log_2 T$$s \in \{0,1\}^k$$f(s)$$\mathcal{C}$

Notez que l'hypothèse que implique que la recherche par force brute de est essentiellement l'algorithme optimal pour . C'est donc une hypothèse assez forte. D'un autre côté, si ne satisfait pas ces propriétés, alors il m'est difficile d'imaginer satisfaire à la fois vos conditions (2) et (4).$k \approx \log_2 T$$\{0,1\}^k$$\mathcal{C}$$\mathcal{C}$

Puis, étant donné une fonction de hachage , que nous modélisons comme un oracle aléatoire, nous définissons comme suit, où pour certains est l'entrée aléatoire de . Le but est de sortir telle sorte que soit une solution à . En d'autres termes, devrait hacher à "bonnes pièces aléatoires" pour l'algorithme ci-dessus.$H : \{0,1\}^* \to \{0,1\}^k$$\Psi_H(\mathcal{C}; r)$$r \in \{0,1\}^\ell$$\ell \gg k$$\Psi_H$$x \in \{0,1\}^*$$f(H(r,x))$$\mathcal{C}$$(r,x)$

Voyons que cela satisfait toutes vos conditions.

1. "La fonction est randomisée, en utilisant une séquence aléatoire (publique) ." Vérifier!$\Psi$$r$
2. "La résolution de est généralement aussi difficile que la résolution de ." Notez que l'algorithme randomisé simple pour s'exécute dans le temps prévu au plus plus les frais généraux polynomiaux, et par hypothèse est essentiellement le temps d'exécution de l'algorithme optimal pour .$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi_H(\mathcal{C},r)$$2^k$$2^k \approx T$$\mathcal{C}$
3. "Si une solution est trouvée pour , alors une solution peut être calculée efficacement pour le défi d'origine ." Cela peut être fait en calculant , qui est une solution à par hypothèse.$x$$\Psi(\mathcal{C})$$\Psi^{-1}(x)$$\mathcal{C}$$f(H(r,x))$$\mathcal{C}$
4. "Connaître une solution pour n'aide pas à trouver une solution pour ." Par définition, la résolution de nécessite de trouver tel que est une solution à . Puisque nous avons modélisé comme un oracle aléatoire, nous pouvons réduire la durée d'exécution attendue de tout algorithme qui résout ce problème par la complexité de requête optimale attendue du problème de requête dans lequel est donné par une boîte noire et nous sommes invités à trouver un solution au même problème. Et, encore une fois parce que est un oracle aléatoire, la complexité de la requête attendue est juste l'inverse de la fraction des éléments$\mathcal{C}$$\Psi(\mathcal{C})$$\Psi_H(\mathcal{C}; r)$$x$$f(H(r,x))$$\mathcal{C}$$H$$H$$H$$x \in \{0,1\}^k$ qui sont des solutions (jusqu'à un facteur constant). Par hypothèse, le temps d'exécution optimal attendu de tout algorithme pour est , ce qui implique que cette fraction ne peut pas être beaucoup plus grande que . Puisque et est choisi uniformément au hasard, cela est même vrai avec le prétraitement qui peut dépendre de et (mais pas ) , et en particulier c'est vrai même si nous connaissons une solution à à l'avance.$\mathcal{C}$$T \approx 2^{k}$$2^{-k}$$\ell \gg k$$r \in \{0,1\}^\ell$$H$$\mathcal{C}$$r$$\mathcal{C}$

La technique simple suivante que j'appelle la technique de loterie en solution (SLT) peut être utilisée en conjonction avec d'autres techniques (comme avoir plusieurs problèmes de prisonnier de guerre, la technique mentionnée dans la réponse de Noah Stephens-Davidowitz, etc.) pour aider à transformer les défis informatiques en preuves viables des problèmes de travail. Le SLT aide à atténuer les problèmes liés aux problèmes d'extraction de crypto-monnaie autres que les conditions 1-4.

Supposons que soit un défi de calcul de la forme «trouver un hachage approprié avec une chaîne telle que ».$\mathcal{C}$$k$$x$$(k,x)\in D$

Problème Configuration : Supposons que est un ensemble, est une fonction de hachage cryptographique et est une constante. Supposons en outre que est une information facile à obtenir après avoir déterminé que mais qui ne peut pas être obtenue autrement.$\Psi(\mathcal{C})$$D$$H$$C$$\textrm{Data}(k,x)$$(k,x)\in D$

Problème Objectif : Trouver une paire telle que est un hachage approprié et où , et où .$\Psi(\mathcal{C})$$(k,x)$$k$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$

Voyons maintenant comment le problème satisfait aux exigences 1-4.$\Psi(\mathcal{C})$

1. Nous devons supposer que est déjà randomisé pour que le SLT satisfasse cette propriété.$\mathcal{C}$

2-3. deviendra généralement plus difficile que et c'est une bonne chose. La difficulté d'un problème de preuve de travail doit être finement ajustable, mais le problème d'origine peut ou peut ne pas avoir un niveau de difficulté finement ajustable (rappelez-vous que la difficulté à extraire Bitcoin est ajustée toutes les deux semaines) . La difficulté du problème est égale à la difficulté de trouver un certain multiplié par . Par conséquent, comme la constante est finement réglable, la difficulté de est également finement réglable.$\Psi(\mathcal{C})$$\mathcal{C}$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)\in D$$\frac{2^{n}}{C}$$C$$\Psi(\mathcal{C})$

Même si le problème est plus difficile que le problème d'origine , presque tout le travail pour résoudre le problème sera consacré à la simple recherche une paire avec plutôt que de calculer des hachages (on ne peut pas calculer si ou pas avant un a calculé et on ne peut pas calculer moins de vérifier que ).$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$$\textrm{Data}(k,x)$$\textrm{Data}(k,x)$$\textrm{Data}(k,x)\in D$

Bien sûr, le fait que soit plus difficile que présente de nouvelles préoccupations. Pour un problème utile, il est très probable que l'on veuille stocker les paires où dans une base de données. Cependant, pour recevoir la récompense en bloc, le mineur ne doit révéler qu'une paire où et au lieu de toutes les paires indépendamment du fait que ou non. Une solution possible à ce problème est que les mineurs révèlent simplement toutes les paires où$\Psi(\mathcal{C})$$\mathcal{C}$$(k,x)$$(k,x)\in D$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))<C$$(k,x)$$(k,x)\in D$par courtoisie. Les mineurs auront également la possibilité de rejeter les chaînes si les mineurs ont pas posté leur juste part de paires . Peut-être, on devrait compter le nombre de paires pour le calcul de qui a également la chaîne valide la plus longue. Si la plupart des mineurs publient leurs solutions, alors le processus de résolution de produira autant de solutions que le processus de résolution de .$(k,x)\in D$$(k,x)\in D$$\Psi(\mathcal{C})$$\mathcal{C}$

Dans le scénario où les mineurs affichent toutes les paires , satisferaient l'esprit des conditions 2-3.$(k,x)\in D$$\Psi(\mathcal{C})$

4. $\Psi(\mathcal{C})$ peut ou non satisfaire la condition fonction du problème spécifique.$4$

$\textbf{Other Advantages of this technique:}$

Le SLT offre d'autres avantages que les conditions 1 à 4 qui sont souhaitables ou nécessaires pour un problème de preuve de travail.

1. Améliorer l'équilibre sécurité / efficacité: le SLT aidera dans le cas où peut être trop facile à résoudre ou trop difficile à vérifier. En général, est beaucoup plus difficile à résoudre que , mais est à peu près aussi facile à vérifier que .$\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{C}$$\Psi(\mathcal{C})$$\mathcal{C}$

2. Suppression d'un problème cassé / non sécurisé: le SLT pourrait être utilisé pour éliminer par algorithme les mauvais problèmes de POW dans une crypto-monnaie avec un problème de POW de sauvegarde et plusieurs problèmes de POW. Supposons qu'une entité trouve un algorithme très rapide pour résoudre le problème . Ensuite, un tel problème n'est plus un problème de preuve de travail approprié et devrait être supprimé de la crypto-monnaie. La crypto-monnaie doit donc avoir un algorithme qui supprime de la crypto-monnaie chaque fois que quelqu'un a publié un algorithme qui résout le problème trop rapidement mais qui ne supprime jamais le problème sinon. Voici un aperçu d'un tel algorithme de suppression de problème utilisé pour supprimer un problème que nous appellerons Problème$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$A$ .

une. Alice paie des frais importants (les frais couvriront les coûts que les mineurs encourent pour vérifier l'algorithme) puis publient l'algorithme que nous appellerons l'algorithme K qui brise le problème dans la blockchain. Si l'algorithme K repose sur une grande quantité de données précalculées , Alice publie la racine Merkle de ce données précalculées .$A$$PC$$PC$

b. Des instances aléatoires du problème A sont produites par la Blockchain. Alice publie ensuite les parties des données précalculées qui sont nécessaires pour que l'algorithme K fonctionne correctement avec leur branche Merkle afin de prouver que les données proviennent réellement du . Si l'algorithme d'Alice s'est alimenté rapidement avec le données précalculé , le problème est supprimé et Alice reçoit une récompense pour avoir publié l'algorithme qui supprime le problème de la blockchain.$PC$$PC$

Cette procédure de suppression des problèmes coûte cher en calcul aux mineurs et aux valideurs. Cependant, le SLT supprime la plupart des difficultés de calcul de cette technique afin qu'elle puisse être utilisée si nécessaire dans une crypto-monnaie (les instances où cette technique est utilisée seront probablement assez rares).

3. Les pools miniers sont plus réalisables: dans les crypto-monnaies, il est souvent très difficile de gagner la récompense du bloc. Étant donné que les récompenses en bloc sont très difficiles à gagner, les mineurs exploitent souvent des choses appelées pools de minage dans lesquels les mineurs combinent leurs ressources pour résoudre un problème et dans lesquels ils partagent la récompense en bloc proportionnellement au nombre de «quasi-accidents» qu'ils ont trouvés. . Un problème possible pour est qu'il peut être difficile de produire une notion qualitative de ce qui constitue un «quasi-accident» pour le problème et l'algorithme pour trouver un quasi-accident peut être différent de la algorithme pour résoudre . Étant donné que les mineurs de la piscine rechercheront des quasi-accidents, ils peuvent ne pas être très efficaces pour résoudre$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$$\mathcal{C}$ (et donc, peu de personnes rejoindront les pools de minage). Cependant, pour , il existe une notion claire d'un quasi-accident, à savoir, un quasi-accident est une paire où mais où , et l'algorithme de recherche des quasi-accidents pour sera le même que l'algorithme de recherche de solutions à .$\Psi(\mathcal{C})$$(k,x)$$(k,x)\in D$$H(k||x||\textrm{Data}(k,x))\geq C$$\Psi(\mathcal{C})$$\Psi(\mathcal{C})$

4. Non-progrès: un problème de preuve de travail est dit sans progrès si le temps qu'il faut à une entité ou un groupe d'entités pour trouver le bloc suivant sur la blockchain suit la distribution exponentielle où la constante est directement proportionnelle à la quantité de puissance de calcul que l' entité utilise pour résoudre un problème . L'absence de progrès est nécessaire pour les problèmes d'extraction de crypto-monnaie afin que les mineurs reçoivent une récompense de bloc proportionnelle à leur puissance d'extraction pour réaliser la décentralisation. Le SLT aide certainement les problèmes miniers à atteindre la liberté de progrès.$P$$e^{-\lambda x}$$\lambda$$P$