Qu’est-ce que la récursivité ?

La récursion est utilisée le plus souvent dans les domaines des mathématiques, des statistiques et de l'informatique, mais elle est également largement utilisée dans toute une gamme d'autres disciplines, notamment la linguistique et la logique, ainsi que dans les applications réelles de l'intelligence artificielle et des jeux.

La récursivité fait référence au moment où une fonction s'appelle directement ou indirectement dans une ou plusieurs boucles circulaires.

La récursivité peut être utilisée pour affiner la précision du calcul et réduire les charges de calcul globales requises. En divisant un problème plus vaste et plus complexe en morceaux plus petits, également connu sous le nom de « diviser pour mieux régner », la récursion rend la résolution de la tâche plus rapide et plus réalisable. Une caractéristique clé est que la fonction fait appel à elle-même de manière répétée et successive pour obtenir une récursivité, définie en termes de cas de base et d'étapes récursives.

Le cas de base fait référence à l'instance la plus simple d'un problème avec toutes les entrées qui permettraient de calculer la sortie. Les étapes récursives appellent la même fonction mais les entrées diminuent en taille et/ou en complexité.

Les algorithmes itératifs et les algorithmes récursifs décomposent les problèmes en problèmes plus petits, mais les premiers nécessitent une logique de contrôle explicite pour gérer le séquençage des algorithmes. Le séquencement d'une fonction récursive est déterminé par l'interaction des données vectorielles et de la fonction récursive. Cela offre une plus grande flexibilité dans le traitement des structures de données qui ne peuvent pas être explicitement définies à l'avance.

Comment la récursion est-elle appliquée à la technologie Blockchain ?

La récursivité est une méthode pour générer des preuves sur la blockchain. Il dessert désormais plusieurs systèmes de production sur le réseau principal Ethereum. Par exemple, Arbitrum utilise un algorithme de bissection récursif pour son processus de résolution des litiges, tandis que StarkWare et zkSync utilisent tous deux la récursion pour obtenir des capacités de mise à l'échelle améliorées.

Sans technologie récursive, il existe une limite supérieure de transactions pouvant être incluses dans une preuve, qui est déterminée par la capacité de calcul d'un seul bloc. Avec la récursivité, une seule preuve peut être générée à partir de plusieurs preuves vérifiées contenant des centaines de milliers de transactions sous-jacentes. En d’autres termes, nous pouvons désormais traiter beaucoup plus de transactions dans une seule preuve, également appelée mise à l’échelle récursive.

La technologie récursive appliquée à la preuve sans connaissance est particulièrement importante car elle est considérée comme un élément essentiel de la solution pour résoudre l'évolutivité de la blockchain. En prenant comme exemple StarkNet de StarkWare, l'une des principales solutions de mise à l'échelle zk-rollup sur Ethereum, SHARP (SHARed Prover) prend les transactions d'applications distinctes sur StarkNet pour les regrouper et les compresser en une seule preuve ZK-STARK (ou simplement une preuve STARK). Le prouveur transmet ensuite la preuve au vérificateur, et c'est le travail de ce dernier de vérifier et d'enregistrer le changement d'état sur la couche 1. Il existe des restrictions quant à savoir qui peut être un prouveur en fonction des ressources informatiques requises.

Ajoutons maintenant la récursion à l'image. Plusieurs transactions (ou relevés) sont envoyées à SHARP et prouvées en parallèle. Chaque preuve est ensuite validée par un vérificateur STARK. Une fois vérifiés, ils sont ensuite fusionnés à nouveau par une instruction Recursive Verifier. Ce processus peut se répéter jusqu'à ce qu'une preuve finale soit soumise sur la couche 1 à un contrat intelligent de vérificateur Solidity. Cette preuve atteste ainsi de toutes les déclarations originales, permettant de traiter plusieurs transactions en chaîne en une seule preuve. En théorie, la boucle récursive peut se répéter indéfiniment, permettant ainsi une capacité « d’hyper-évolutivité ».

La récursion libère donc davantage le potentiel de la technologie de cumul et de la mise à l’échelle de couche 2.

Avantages de la récursivité

Les avantages de la récursivité pour les preuves de validité incluent une réduction du coût du gaz grâce à la réduction du coût par transaction grâce à la « compression » de plusieurs preuves en une seule. Cela permet de diviser davantage de transactions dans une seule preuve soumise à L1 qui amortit le coût du gaz par transaction. La barrière des ressources informatiques qui limitait la taille de la preuve n’est également plus une contrainte puisqu’il n’est pas nécessaire de prouver des déclarations extrêmement volumineuses en une seule fois.

Cela entraîne également une latence réduite. Les déclarations (contenant des transactions plus petites) peuvent être prouvées en parallèle et ne pas avoir à attendre que d'autres transactions arrivent. Les prouveurs n'ont plus besoin d'effectuer de gros calculs hors chaîne, et ainsi les barrières pour devenir un prouveur ont disparu, encourageant une approche décentralisée. réseau de prouveurs pour accroître la capacité de traitement du réseau.

De plus, les utilisateurs peuvent bénéficier de la « compression logarithmique » avec STARK, où prouver une déclaration prend un temps T et vérifier la preuve prend environ un temps log(T). La compression logarithmique est importante car la vérification d'une preuve contenant deux preuves d'exécution correcte prendra des étapes log(2log(T)). En d’autres termes, le temps de latence pour produire et valider des preuves récursives diminue sur une échelle logarithmique.

Grâce à la récursivité, les plates-formes et les applications ont la possibilité d'augmenter davantage leurs coûts et leurs performances.

Utilisations de la récursivité au-delà de la couche 2

La récursion ouvre la voie aux cas d’utilisation de la couche 3. Jusqu'à présent, l'accent a été mis sur l'utilisation de la récursivité pour générer des preuves sur la couche 2 qui seront finalement déposées sur la couche 1. Cependant, une nouvelle couche ouvre également la possibilité de soumettre des preuves de transaction de la couche 3 à la couche 2 où l'exécution est effectuée sur la couche supérieure. , et la preuve est finalement vérifiée sur la couche 2, ce qui peut permettre d'optimiser davantage les performances et de générer des avantages en termes de coûts. Les interactions entre la couche 3 et la couche 2 sont analogues à celles entre la couche 2 et la couche 1, tandis que l'intégrité et la sécurité des transactions sont préservées.

Plus précisément, les réseaux privés de couche 3 sont hautement personnalisables afin que les protocoles puissent définir leurs propres paramètres opérationnels, tels que la définition de la taille du lot de transactions pour équilibrer le coût et la vitesse des transactions ou la mise en œuvre de fonctionnalités de préservation de la confidentialité. La qualité sur mesure des couches 3 pour répondre à différents cas d'utilisation ainsi que les capacités de traitement améliorées de la récursion permettent à la fois une expérience de chaîne personnalisée tout en garantissant que les outils d'optimisation des performances et des coûts sont facilement disponibles. Les avantages de la couche 3 sont une hyper évolutivité grâce à l'exploitation de l'effet multiplicatif de la preuve récursive, de la confidentialité et d'une interopérabilité améliorée entre la couche 2 et la couche 3.

Au fil du temps, davantage de cas d'utilisation et d'avantages de la récursivité sur le développement de la blockchain seront réalisés. En déverrouillant le processus de parallélisation, cela rendra possible l’hyper-scaling, améliorant ainsi la latence et réduisant les frais de gaz en même temps.

Auteur

Jane Ma, co-fondatrice et co-chef de projet de zkLend, un protocole du marché monétaire L2 construit sur StarkNet, combinant l'évolutivité de zk-rollup, une vitesse de transaction supérieure et des économies de coûts avec la sécurité d'Ethereum. Le protocole offre une double solution : une solution autorisée et axée sur la conformité pour les clients institutionnels, et un service sans autorisation pour les utilisateurs DeFi – le tout sans sacrifier la décentralisation.