Initialement publié en anglais part StarkWare le 1 Juillet, 2019. Part 2 sur 4

Ceci est la deuxième partie de notre découverte en profondeur sur StarkDEX, expliquant les différents composants de StarkDEX Alpha. Dans la première partie, nous avons donné un aperçu du système et discuté des flux d’utilisateurs et du batching¹– si vous ne l’avez pas déjà lu, nous vous encourageons à le faire avant de lire cet article.

Dans cet article, nous décrirons en détail nos smart contract, notre terminologie spécifique au système et comment elle se traduit par l’affirmation d’une transition étatique valide que nous démontrons.

Objectifs de conception

L’objectif principal du contrat intelligent est de garantir l’auto-garde des utilisateurs, ainsi que la possibilité de négocier sur un exchange. Pour l’évolutivité, le contrat ne stocke pas la totalité de l’état d’équilibre comme le font les exchange décentralisés. Au lieu de cela, il enregistre une représentation succincte de l’état de la balance – un engagement Merkle (32 octets pour l’état entier). Nous garantissons l’intégrité de l’état en exigeant une preuve STARK valide pour chaque mise à jour de l’engagement de l’état, démontrant la validité de la mise à jour. Grâce à notre mécanisme d’évacuation, les utilisateurs peuvent toujours récupérer leurs fonds, même si le service de change ne répond pas ou décide de les censurer de manière malveillante.

Conception de haut niveau

Il existe deux contrats centraux: (a) Le contrat StarkVerifier – Un contrat apatride qui reçoit comme entrée une preuve STARK et sa contribution publique, et vérifie l’exactitude de la contribution publique à l’aide de la preuve. Si la preuve est acceptée, l’apport public est alors transmis au contrat StarkExchange afin d’en manipuler l’état. (b) Le contrat StarkExchange – Ce contrat maintient un engagement – une représentation succincte des soldes. De plus, elle tient des registres des dépôts et des retraits on-chain.

Notation

Clé utilisateur StarkDEX La clé utilisateur StarkDEX est utilisée par StarkDEX pour vérifier les signatures ECDSA des utilisateurs. La signature est vérifiée dans le cadre de la preuve, et comme la courbe elliptique utilisée sur Ethereum n’est pas compatible STARK, nous utilisons une implémentation ECDSA sur une courbe différente, compatible STARK. Cela oblige les utilisateurs à générer des paires de clés supplémentaires afin d’utiliser le système StarkDEX. Afin de distinguer la clé Ethereum standard de la clé utilisateur StarkDEX, nous l’appelons ici et dans le code «clé STARK».

Vault² Les vaults (coffres-forts) sont utilisées pour stocker les soldes. Chaque vault est identifié par un identifiant unique, et étiqueté par la clé publique de son propriétaire (STARK) et l’identifiant d’actif qu’il stocke (akatoken Id). Le contenu d’un vault est la quantité de pièces dans le vault. Les utilisateurs peuvent avoir plusieurs vault, stockant différentes portions d’un même bien.

Quantité d’actif Dans le système de preuve, nous sommes limités par 63 bits pour la représentation des montants (par conception), donc nous normalisons chaque actif en utilisant une quantité dédié, défini lors de l’enregistrement de l’actif. Une seule unité d’un montant quantifié (de n’importe quel actif) devrait avoir une valeur approximative de 10 à 4 USD, à l’exclusion des jetons non fongibles. Par exemple, en échangeant de l’éther wrapped, nous utiliserions une quantité d’environ 103 Gwei (wrapped) et permet de négocier des montants allant de 10-4 USD à 1015 USD, ce qui semble suffisant pour la plupart des utilisations pratiques. La quantité d’un bien peut devenir obsolète à la suite de changements extrêmes de sa valeur. Pour éviter que cela ne se produise, un actif peut être enregistré à nouveau avec un identifiant différent et une quantité mis à jour, ce qui permet l’existence simultanée de plusieurs versions de l’actif.

Flux utilisateur standard

Inscription

Pour s’inscrire, l’utilisateur appelle registerde la fonction contractuelle et lui fournit sa clé publique STARK. Le contrat associe la clé Ether de l’appelant à la clé STARK fournie. Cette association est essentielle pour la traduction d’adresses d’utilisateur pendant les flux de retrait et de dépôt, car dans le système, les utilisateurs StarkDEX sont identifiés par leur clé STARK.

Depôt

Pour déposer des fonds dans le système, l’utilisateur invoque la fonction de deposit, en lui fournissant le tokenId identifiant l’actif, un vaultId et le quantizedAmount à déposer. Lors du dépôt d’un nouvel actif, pour laquelle l’utilisateur n’a pas de vault, l’utilisateur doit contacter StarkDEX pour obtenir un ID de vault dédié à cette ressource. Dans la pratique, une telle communication peut se faire de manière transparente à partir de l’interface. Les enregistrements de dépôt on-chain sont identifiés par le triplet de (starkKey, tokenId, vaultId), et la seule restriction imposée par le contrat aux dépôts d’utilisateurs est que la clé STARK soit compatible avec la clé Ether du déposant. C’est à StarkDEX de choisir quels dépôts sont légitimes. Si certains dépôts ne sont pas récupérés par StarkDEX pour une raison quelconque, que ce soit parce que les (tokenId, vaultId) n’ont pas été fournis par l’opérateur ou parce que l’opérateur devient malveillant, l’utilisateur peut annuler le dépôt en utilisant le mécanisme d’évacuation. Enfin, si le dépôt est légitime, les fonds sont transférés de l’espace des dépôts on-chain à l’espace off-chain à l’aide d’une preuve attestant que le solde off-chain du vault a été augmenté du montant exact.

Retrait
Pour retirer des fonds de l’exchange, l’utilisateur doit d’abord contacter StarkDEX par un canal off-chain (e.g., le site Web de l’exchange) et demander de transférer des fonds de la zone off-chain à la zone on-chain. Une fois qu’une preuve confirme le transfert de fonds vers la zone on-chain, l’utilisateur peut se rétracter directement du contrat StarkDEX en utilisant la fonction de retrait. La fonction ne reçoit qu’un tokenId, identifie la clé de l’utilisateur à partir de la requête et transfère la quantité (de cet actif spécifique) stockée dans la espace de retrait on-chain de l’utilisateur directement dans le wallet de l’utilisateur.

Si StarkDEX ne répond pas à la demande de l’utilisateur de retirer de l’espace off-chain, l’utilisateur peut utiliser le mécanisme d’évacuation pour s’assurer que l’utilisateur reçoit toujours ses fonds.

Escape Hatch Flows

Le mécanisme d’évacuation est conçue pour permettre à l’utilisateur de conserver la possibilité de retirer des fonds indépendamment de la disponibilité de StarkDEX (nous publierons un article séparé sur la gamme de solutions de disponibilité de données dans les prochaines semaines).

Comme nous l’avons montré dans notre poste précédent, il y a trois domaines dans lesquels les fonds (en fait, leurs dossiers) peuvent être présents: l’espace des dépôts on-chain, l’espace des retraits on-chain et l’espace de négociation off-chain.

Rappelons le flux standard de fonds entre les espaces: dépôts → trading → retraits.

Chaque déplacement d’un espace à un autre nécessite la participation de StarkDEX. En utilisant le flux standard, les utilisateurs peuvent extraire des fonds uniquement de l’espace des retraits on-chain. Le mécanisme d’évacuation permet aux utilisateurs d’extraire des fonds des deux autres espace.

Mécanisme d’évacuation de l’espace des dépôts On-Chain

L’objectif principal de ce mécanisme d’évacuation est d’extraire les fonds même si StarkDEX, malicieusement ou non, ne retire pas le dépôt (c’est-à-dire ne déplace pas les fonds off-chain).

Les utilisateurs peuvent récupérer des fonds de l’espace des dépôts on-chain en suivant le flux décrit ici.

Un utilisateur doit d’abord appeler la fonction depositCancel, lui fournissant le tokenId et le vaultId, demandant d’annuler le transfert du dépôt de l’actif demandé dans le vaults demandé. La demande d’annulation est verrouillée dans le temps pour éviter une condition de course entre la demande et les preuves entrantes envoyées par l’exchange; ainsi, appeler depositCance enregistre seulement la demande, activant le verrouillage dans le temps. Après une période de temps suffisamment longue (définie arbitrairement à 1 jour dans le contrat Alpha), l’utilisateur peut appeler depositReclaim avec les mêmes paramètres, en transférant tous les fonds du vaults demandé vers le wallet de l’utilisateur.

Notez qu’à tout moment entre les deux appels, une preuve de réduction du montant on-chain peut être acceptée. Dans ce cas, le second appel ne transfère que les fonds laissés on-chain dans le wallet de l’utilisateur.

Mécanisme d’évacuation de l’espace de trading off-chain

Le retrait forcé de fonds de StarkDEX se fait de deux façons différentes que nous expliquons en détail plus loin dans cette section: (1) Tant que l’échange est opérationnelle, le smart contract garantit que l’échange ne censure aucun utilisateur. (2) Une fois que l’échange ignore la demande de retrait d’un seul utilisateur, le contrat permet à l’utilisateur ignoré de fermer l’échange (nous disons que l’échange devient «gelée» dans cet état) et permet aux utilisateurs de retirer leurs fonds en affichant une liaison de leur contenu du vault, vers la racine Merkle des soldes DB. Maintenant pour les détails.

Phase (1): Échange opérationnel

Si les demandes de retrait de fonds de l’utilisateur (off-chain) sont ignorées par l’échange, celle-ci peut appeler la fonction escapeRequest, en lui fournissant un vaultId, en avertissant l’exchange qu’il doit retirer les fonds de l’utilisateur du vaults demandé. Pour prévenir les attaques DoS sur l’échange, qui doit répondre à chacune de ces requêtes (dans un délai donné), des frais non négligeables seraient perçus pour escapeRequest. Si dans un délai déterminé (défini arbitrairement à cinq jours dans l’alpha) StarkDEX ne fournit pas de preuve déplaçant tout le contenu du coffre-fort vers l’espace de retrait on-chain ou montrant que le vault n’appartient pas à l’appelant, alors l’utilisateur peut appeler la fonction escapeFreeze, bloquer l’échange et passer à la phase suivante.

Phase (2): Gel des échanges

Une fois l’échange gelée, toutes les preuves présentées par celle-ci sont automatiquement rejetées par le contrat, gelant ainsi l’état des balances off-chain de la DB en fixant sa racine Merkle et en la rendant immuable. Pendant le gel de l’état, tous les utilisateurs peuvent retirer leurs fonds en présentant au contrat une preuve directe de propriété de l’actif. Cette partie n’a pas été implémentée dans l’Alpha, et peut être implémentée de manière succincte en utilisant STARKs, ou moins succincte en fournissant explicitement les chemins d’authentification Merkle d’un vault à la racine DB (gelée).

État du contrat StarkDEX

Dans les sections précédentes, nous avons présenté plusieurs parties de l’état du contrat StarkDEX, à savoir les dépôts on-chain et les espaces de retrait, ainsi qu’une structure de stockage des demandes de sortie des utilisateurs. Toutes ces structures sont modifiées dynamiquement par des actions invoquées par les utilisateurs on-chain. Dans la section suivante, nous décrivons l’interaction du contrat StarkDEX avec l’exchange opérateur mais nous montrons d’abord comment l’état off-chain est projeté dans le contrat StarkDEX: l’engagement Merkle des vaults, l’engagement Merkle des accords, et le numéro de séquence qui augmente à chaque mise à jour de l’état.

L’engagement Merkle des vaults

Comme décrit plus haut, les soldes des utilisateurs sont conservés dans des vaults, chaque vault est représenté par un ID unique et un triple (starkKey, tokenId, amount), où la starkKey identifie le propriétaire du vault, le tokenId identifie l’actif qui y est stocké, et le montant est le montant (quantifié) actuellement stocké dans le vault. Un stockage du vault (starkKey=0, tokenId=0, amount=0) est appelé «vide.» Les ID du vault sont des entiers consécutifs entre 0 et 231-1, donc chaque ID définit un chemin unique vers une feuille d’un arbre Merkle de hauteur 31, où l’information est stockée. Le contrat StarkDEX gère les soldes off-chain en stockant la racine de l’arbre Merkle des vaults (et sa hauteur), en veillant à ce que toute modification de son état soit le résultat d’un dépôt (légal), d’un retrait ou d’un règlement. Si la racine Merkle des vaults est mise à jour à la suite d’un dépôt ou d’un retrait, le contrat StarkDEX confirme que les soldes on-chain sont mis à jour en conséquence.

Disponibilité des données

Notez qu’en cas de gel du contrat StarkDEX (voir la section escape hatch flows), il est essentiel que les utilisateurs aient accès à l’état complet du vault. C’est ce qu’on appelle le problème de disponibilité des données. Comme solution actuelle, StarkDEX utilise un comité de parties fiables (par ex. StarkWare, 0x, Ethereum Foundation, échanges, etc.) et s’attend à ce que chaque nouvelle source soit signée par une majorité du comité, garantissant ainsi la disponibilité publique des données. Notez que (1) le mécanisme de disponibilité des données n’est pas implémenté dans l’Alpha et (2) si d’autres solutions de disponibilité des données sont considérées comme des «meilleures pratiques standard», nous prévoyons de les utiliser à la place.

La racine de Merkle des colonies Les accords Merkle root

Chaque règlement est identifié par un ID unique, signé par les deux parties (créateur et preneur). Comme pour l’arborescence Merkle des vaults, les identifiants de règlement sont dans l’intervalle 0…2³¹–1 et nous enregistrons l’ensemble des règlements exécutés en utilisant un arbre Merkle avec des feuilles de valeur booléenne, où chaque feuille correspond à un identifiant de règlement (la valeur booléenne signifie si le règlement a été exécuté ou non). La source de l’arbre de Merkle (et sa hauteur) est également stockée dans le contrat StarkDEX, et est nécessaire pour s’assurer qu’aucun règlement n’est exécuté deux fois. Cette fonctionnalité n’est que partiellement implémentée dans l’Alpha.

Numéro de séquence

Le numéro de séquence est un identifiant monotone croissant de l’état off-chain, et avec la racine de Merkle et la hauteur de l’arbre des vaults, est signé par les membres du comité. Son but est de s’assurer que chaque modification de la racine est vérifiée par le comité, même si la nouvelle racine représente un état d’équilibre répétitif. Sans le numéro de séquence, quelqu’un pourrait sauvegarder toutes les signatures du comité, et si un état se répète, il pourrait retenir les données du comité et utiliser l’ancienne signature sur le même état, que le comité pourrait ne pas être en mesure de rétablir.

Actions de l’opérateur StarkDEX

L’exchange peut modifier l’état StarkDEX en appliquant l’une des opérations suivantes: (a) dépôt de l’espace on-chain à l’espace off-chain. b) l’exécution d’un règlement c) le retrait de l’espace off-chain vers la zone on-chain. (d) répondre aux mécanisme d’évacuation de l’espace off-chain (appelée « retrait complet »). Ci-dessous, nous décrirons comment chacune de ces opérations influent sur l’état du contrat StarkDEX, et les exigences pour valider la légitimité des opérations.

Dépôts: Des espaces On-Chain à Off-Chain

Les paramètres d’une opération de dépôt sont (starkKey, vaultId, tokenId, amount).
L’opération nécessite que le solde on-chain correspondant contienne au moins une (quantifier) amountde l’actif requis, et que le vault avec l’ID requis dans l’état off-chain (représenté par la racine de Merkle) appartiennent à la même clé STARK ou est vide.

Ce qui suit est garanti une fois le dépôt finalisé:

• Le montant requis est réduit du solde on-chain et ajouté au vault off-chain.
• Les valeurs starkKey et tokenId du vault off-chain sont cohérentes avec les paramètres
• Les changements de l’état off-chain se reflètent dans les vaults on-chain “Merkle root”

Règlements

Les paramètres d’un règlement sont les suivants:

• Deux clés STARK et signatures; une pour chaque partie
• Deux identifiants de jeton et montants représentants les actifs échangés
• Quatre cartes d’identité du vault. Chaque partie dispose de deux vaults (une pour chaque bien)
• ID de règlement

L’opération nécessite ce qui suit :

• Connaissance de la signature de son créateur sur les ID du vault du créateur, les ID de jeton, les montants et l’ID de règlement
• Connaissance de la signature du preneur sur le message signé par le créateur, ainsi que des ID du vault du preneur
• L’ID du règlement n’a pas déjà été utilisé (pas dans l’alpha)
• Les vaults appartiennent aux propriétaires attendus (créateur/preneur) et stockent les biens nécessaires

Une fois l’accord finalisé, sont garanties ce qui suit:

• Les montants requis sont déduits des vaults sortants correspondants et ajoutés aux vaults entrants correspondants
• L’ID de l’accord est changé de non-utilisé à utilisé, dans l’arbre de Merkle des accords
• Si un vault a amount=0 après l’exécution du règlement, il est vidé de sorte qu’il a maintenant aussi starkKey=tokenId=0
• Les changements de l’état off-chain se reflètent dans les vaults on-chain de la racine Merkle.

Il est intéressant de mentionner qu’un vault qui était vide au début peut appartenir à n’importe qui et peut stocker n’importe quel actif.

Notez que le seul effet de cette opération sur l’état du contrat StarkDEX est sur les racines de Merkle. Il en va de même pour un lot de plusieurs accords– il n’est pas nécessaire de transmettre les données des accords, il suffit d’envoyer une seule épreuve STARK pour l’ensemble du lot, avec les nouvelles racines Merkle. Cela donne à StarkDEX la possibilité d’assembler d’énormes quantités de transactions dans un seul bloc Ethereum.

Retraits: de Off-Chain à On-Chain

L’opération de retrait est (naturellement) très semblable à l’opération de dépôt. Ses paramètres sont (starkKey, vaultId, tokenId, amount) ainsi, et il nécessite que le coffre-fort off-chain ait les paramètres attendus (StarkKeydu propriétaire, et stocker les actifs de tokenId), et ait suffisamment de fonds. Il s’assure que cette opération réduit la quantité du coffre-fort off-chain en conséquence (affectant la racine de Merkle), et marque le coffre comme vide si sa quantité est 0. De plus, il vérifie que le solde de retrait on-chain correspondant à starkKey,tokenIdest augmenté en conséquence.

Répondre aux demandes de mécanisme d’évacuation

Une requête de mécanisme d’évacuation n’est valide que si l’ID du vault demandé appartient bien à l’appelant. L’architecture actuelle ne fournit pas suffisamment d’informations au contrat StarkDEX pour vérifier la validité d’un mécanisme d’évacuation au moment de la soumission, donc le système traite également les mécanismes d’évacuation invalides. Pour exécuter une demande de sortie, l’exploitant doit envoyer une preuve au contrat, soit (1) prouvant que le vault appartient bien à l’auteur de la demande et qu’une opération de retrait a été invoquée, après quoi le vault est devenu vide, soit (2) prouvant que le vault demandé n’appartient pas à l’auteur de la demande et que, par conséquent, son état ne doit pas changé à la suite de cette opération.

Ceci conclut la section décrivant le contrat StarkDEX principal (aka StarkExchange). Dans la section suivante nous découvrons l’instruction vérifiée par le contrat StarkVerifier.

L’instruction StarkDEX

L’instruction vérifiée par le contrat de vérification StarkDEX est l’exécution séquentielle valide d’un lot d’actions de l’opérateur, projetées dans les racines Merkle et l’entrée publique, qui est utilisée pour modifier les enregistrements on-chain.

Regroupement d’opérations utilisant les preuves STARK

StarkDEX utilise les preuves STARK pour regrouper de nombreuses opérations. Chaque preuve atteste de l’intégrité d’un public input (qui est transmise on-chain), qui est utilisé pour modifier l’état du contrat StarkDEX. Supposons pour le moment que la seule opération est l’accord. Dans le cas présent, les public input auraient pu être de deux origines Merkle, initiale et finale. L’instruction vérifiée dans ce cas serait la connaissance d’une séquence des accords valides changeant l’état des vaults de la racine initiale à la racine finale (voir figure 4). En pratique, un public input contient des précisions supplémentaires. Il y a deux raisons principales.

La première raison est que, comme indiqué précédemment, les dépôts et les retraits modifient les soldes on-chain, de sorte que les informations relatives à de tels changements doivent être envoyées. La deuxième raison est de tenir compte pour les informations qui influent sur l’algorithme de vérification – la taille du lot, par exemple.

Dans StarkDEX, l’intégrité du public input est vérifiée par le contrat StarkVerifier (qui lui n’a pas d’état) en utilisant une preuve STARK . Ce n’est que si la preuve est acceptée que le public input requis pour la modification de l’état StarkDEX sera transmise au contrat StarkExchange. Le contrat StarkExchange confirme que ces types de commandes de mise à jour sont envoyés uniquement à partir du contrat StarkVerifier, garantissant ainsi la validité de chaque mise à jour. Ensuite, nous décrivons les champs de public inputs utilisés dans notre opération STARK. Nous nous concentrons sur les champs qui ont une incidence sur le contrat StarkDEX et, par souci de simplicité, négligeons les champs nécessaires au bon fonctionnement du vérificateur (p.ex. taille du lot).

Merkle Roots

Chaque opérations est envoyée avec quatre racines Merkle vers le public input, à savoir les racines initiales et finales de l’arbre des vaults, et les racines initiales et finales de l’arbre des accords. Le contrat StarkDEX garantit que les racines initiales correspondent aux racines actuellement stockées, et que la racine du vault est signée par le comité (voir la section sur la disponibilité des données) avec le numéro de séquence correct. Les tailles font partie de la public input, pour répondre aux besoins futurs d’agrandissement d’un des arbres, mais la fonctionnalité n’est pas implémentée dans l’Alpha. Après avoir confirmé que les racines initiales et les tailles correspondent à l’état du contrat, les racines du contrat sont mises à jour aux valeurs finales.

Opérations autres que l’accord

Toute opération autre que l’accord nécessite des données du public input indiquant les changements effectués dans la zone off-chain, et ces données sont utilisées pour modifier la zone des fonds on-chain. Pour des raisons techniques (simplification de la conception de la AIR — Algebraic Intermediate Representation), nous utilisons le même format pour toutes les opérations (sauf pour les accords, qui n’exigent pas la participation du public). Le format de public input pour chaque opération est (vaultId, starkKey, tokenId, amountBefore, amountAfter).

La preuve STARK garantit ce qui suit:

• L’opération a été appliquée au vault avec l’ID attendu
• Le vault appartient au propriétaire de starkKey, et stocke les actifs du tokenId requis (ou est vide)
• L’opération a changé le solde dans le vault de amountBefore à amountAfter

On peut noter que ce format est en effet suffisant pour prouver la légitimité de toute opération modifiant l’état on-chain, comme indiqué précédemment, y compris la nécessité de répondre aux requêtes d’évacuation, valides ou non.

Ceci conclut notre analyse détaillée des composants on-chain de StarkDEX. Dans le prochain post de la série StarkDEX Deep Dive, nous détaillerons ce qui va dans la construction d’un moteur STARK pour DEXes.

Si vous avez des questions ou des suggestions, veuillez les commenter ici ou nous contacter sur Twitter @StarkWareLtd.

Michael Riabzev & Alon Frydberg

StarkWare Industries

Traduction faite par @cleminso