zk-SNARKs and zk-STARKs Explained

Binance Academy · 2022-11-05T01:43:01.000Z

Privacy has always been viewed as a valuable feature within the cryptocurrency community. It is the precursor to fungibility, which is necessary for a widely used form of money. Similarly, most crypto-asset holders don’t want their holdings and transaction history to be completely public. Among the various cryptographic techniques aiming to provide privacy to blockchains, the zk-SNARK and zk-STARK proofs are two noteworthy examples. zk-SNARK stands for zero-knowledge succinct non-interactive argument of knowledge, and zk-STARK represents zero-knowledge succinct transparent argument of knowledge. zk-SNARK proofs are used by cryptocurrency projects (such as Zcash), on blockchain-based payment systems, and as a way to securely authenticate clients to servers. But while zk-SNARKs have made significant headway to being well-established and adopted, zk-STARK proofs are now being touted as the new and improved version of the protocol, addressing many of the previous drawbacks of zk-SNARKs. The Ali Baba's Cave Parable In 1990, a paper entitled "How to Explain Zero-Knowledge Protocols to Your Children" was published by cryptographer Jean-Jacques Quisquater (along with other collaborators). The paper introduces the concept of zk proofs with a parable involving Ali Baba's Cave. Since its creation, the parable has been adapted several times, and we now have multiple variations. Still, the underlying information is essentially the same. Let’s imagine a ring-shaped cave with a single entry and a magic doorway that separates the two side paths apart. In order to go through the magic doorway, one needs to whisper the correct secret words. So consider that Alice (yellow) wants to prove to Bob (blue) that she knows what the secret words are - while still keeping them secret. To do so, Bob agrees to wait outside while she enters the cave and walks until the end of one of the two possible paths. In this example, she decides to go through Path 1. After a while, Bob walks by the entrance and shouts which side he wants Alice to appear from (Path 2 in this case). If Alice truly knows the secret, she will reliably show up from the path Bob names. The whole process may be repeated several times as a way to confirm that Alice is not choosing the right path by luck. Ali Baba’s Cave parable illustrates the concept of zero-knowledge proofs, which are part of the zk-SNARK and zk-STARK protocols. ZK proofs can be used to prove possession of certain knowledge without revealing any information about it. zk-SNARKs Zcash is one of the earliest examples of a project that uses zk-SNARKs. While other privacy projects like Monero employ ring signatures and other techniques, zk-SNARKs fundamentally changes the way data is shared. The privacy of Zcash is derived from the fact that transactions in the network can remain encrypted but still be verified as valid by using zero-knowledge proofs. So, those who are enforcing consensus rules don’t need to know all of the data underlying each transaction. It’s worth mentioning that privacy features in Zcash are not active by default but are rather optional and dependent on manual setup. Zero-knowledge proofs allow one individual to prove to another that a statement is true without disclosing any information beyond the validity of the statement. The parties involved are commonly referred to as a prover and a verifier, and the statement they hold in secret is called a witness. The main objective of these proofs is to reveal as little data as possible between the two parties. In other terms, one can use zero-knowledge proofs to prove that they have certain knowledge without revealing any information about the knowledge itself. Within the SNARK acronym, “succinct” means that these proofs are smaller in size and can be quickly verified. “Non-interactive” means that there is little to no interaction between the prover and the verifier. Older versions of zero-knowledge protocols usually require the prover and verifier to communicate back and forth and, therefore, are considered “Interactive” ZK proofs. But in “non-interactive” constructions, provers and verifiers only have to exchange one proof. Currently, zk-SNARK proofs are dependent on an initial trusted setup between a prover and verifier, meaning that a set of public parameters is required to construct zero-knowledge proofs and, thus, private transactions. These parameters are almost like the rules of the game; they are encoded into the protocol and are one of the necessary factors in proving a transaction is valid. However, this creates a potential centralization issue because the parameters are often formulated by a very small group. While an initial trusted setup is fundamental to today’s zk-SNARK implementations, researchers are working to find other alternatives as a way to reduce the amount of trust required in the process. The initial setup phase is important in preventing counterfeit spending because if someone had access to the randomness that generated the parameters, they could create false proofs that seemed valid to the verifier. In Zcash, the initial setup phase is known as the Parameter Generation Ceremony. Moving onto the “Arguments of Knowledge” piece of the acronym. zk-SNARKs are considered computationally sound, meaning that a dishonest prover has a very low chance of successfully cheating the system without actually having the knowledge (or witness) to support their statement. This property is known as soundness and assumes that the prover has limited computing power. Theoretically, a prover with enough computational power could create fake proofs, and this is one of the reasons quantum computers are considered by many to be a threat to zk-SNARKs (and blockchain systems). Zero-knowledge proofs are quickly verifiable and usually take up much less data than a standard Bitcoin transaction. This opens up a pathway for zk-SNARK technology to be used as both a privacy and a scalability solution. zk-STARKs zk-STARKs were created by Eli-Ben Sasson, a professor at the Technion-Israel Institute of Technology. As an alternative version of zk-SNARK proofs, zk-STARKs are generally considered a more efficient variant of the technology - potentially faster and cheaper, depending on the implementation. But more importantly, zk-STARKs do not require an initial trusted setup (hence, the “T” for transparent). Technically speaking, zk-STARKs do not require an initial trusted setup because they rely on leaner cryptography through collision-resistant hash functions. This approach also eliminates the number-theoretic assumptions of zk-SNARKs that are computationally expensive and theoretically prone to attack by quantum computers. In other terms, zk-STARK proofs present a simpler structure in terms of cryptographic assumptions. However, this novel technology comes with at least one major disadvantage: the size of the proofs is bigger when compared to zk-SNARKs. Such a difference in data size may present limitations depending on the context of use, but it is probably something that can be figured out as the technology is further tested and investigated. Closing Thoughts It is clear that both zk-SNARKs and zk-STARKs appeal to the growing concern regarding privacy. Within the cryptocurrency world, these protocols have great potential and might be a groundbreaking avenue toward mainstream adoption.

La confidentialité a toujours été considérée comme une fonctionnalité précieuse au sein de la communauté des cryptomonnaies. C’est le précurseur de la fongibilité, nécessaire pour une forme de monnaie largement utilisée. De même, la plupart des détenteurs de crypto-actifs ne souhaitent pas que leurs avoirs et l’historique de leurs transactions soient entièrement publics. Parmi les différentes techniques cryptographiques visant à assurer la confidentialité des blockchains, les preuves zk-SNARK et zk-STARK en sont deux exemples remarquables.
zk-SNARK signifie argument de connaissance succinct et non interactif sans connaissance, et zk-STARK représente un argument de connaissance succinct et transparent sans connaissance. Les preuves zk-SNARK sont utilisées par des projets de crypto-monnaie (tels que Zcash), sur des systèmes de paiement basés sur la blockchain et comme moyen d'authentifier en toute sécurité les clients auprès des serveurs. Mais alors que les zk-SNARK ont fait des progrès significatifs pour être bien établis et adoptés, les preuves zk-STARK sont désormais présentées comme la nouvelle version améliorée du protocole, corrigeant bon nombre des inconvénients précédents des zk-SNARK.
La parabole de la caverne d'Ali BabaEn 1990, un article intitulé « Comment expliquer les protocoles de connaissance zéro à vos enfants » a été publié par le cryptographe Jean-Jacques Quisquater (avec d'autres collaborateurs). L'article introduit le concept de preuves zk avec une parabole impliquant la grotte d'Ali Baba. Depuis sa création, la parabole a été adaptée à plusieurs reprises, et on en connaît désormais de multiples variantes. Pourtant, les informations sous-jacentes sont essentiellement les mêmes.
Imaginons une grotte en forme d’anneau avec une seule entrée et une porte magique qui sépare les deux chemins latéraux. Pour franchir la porte magique, il faut murmurer les bons mots secrets. Considérez donc qu'Alice (jaune) veut prouver à Bob (bleu) qu'elle connaît les mots secrets - tout en les gardant secrets. Pour ce faire, Bob accepte d'attendre dehors le temps qu'elle entre dans la grotte et marche jusqu'au bout d'un des deux chemins possibles. Dans cet exemple, elle décide de suivre le chemin 1.
Au bout d'un moment, Bob passe devant l'entrée et crie de quel côté il veut qu'Alice apparaisse (Chemin 2 dans ce cas).
Si Alice connaît vraiment le secret, elle apparaîtra de manière fiable à partir du chemin nommé par Bob.
L’ensemble du processus peut être répété plusieurs fois afin de confirmer qu’Alice ne choisit pas le bon chemin par hasard.
La parabole de la Caverne d'Ali Baba illustre le concept de preuves sans connaissance, qui font partie des protocoles zk-SNARK et zk-STARK. Les preuves ZK peuvent être utilisées pour prouver la possession de certaines connaissances sans révéler aucune information à leur sujet.
zk-SNARKZcash est l'un des premiers exemples de projets utilisant des zk-SNARK. Alors que d'autres projets de confidentialité comme Monero utilisent des signatures en anneau et d'autres techniques, zk-SNARK change fondamentalement la façon dont les données sont partagées. La confidentialité de Zcash découle du fait que les transactions sur le réseau peuvent rester cryptées tout en étant vérifiées comme valides à l'aide de preuves sans connaissance. Ainsi, ceux qui appliquent les règles de consensus n’ont pas besoin de connaître toutes les données sous-jacentes à chaque transaction. Il convient de mentionner que les fonctionnalités de confidentialité de Zcash ne sont pas actives par défaut mais sont plutôt facultatives et dépendent d'une configuration manuelle.
Les preuves sans connaissance permettent à un individu de prouver à un autre qu'une déclaration est vraie sans divulguer aucune information au-delà de la validité de la déclaration. Les parties impliquées sont communément appelées un prouveur et un vérificateur, et la déclaration qu'elles détiennent en secret est appelée un témoin. L'objectif principal de ces preuves est de révéler le moins de données possible entre les deux parties. En d’autres termes, on peut utiliser des preuves de connaissance nulle pour prouver qu’on possède certaines connaissances sans révéler aucune information sur la connaissance elle-même.
Dans l’acronyme SNARK, « succinct » signifie que ces preuves sont de plus petite taille et peuvent être rapidement vérifiées. « Non interactif » signifie qu'il y a peu ou pas d'interaction entre le prouveur et le vérificateur. Les anciennes versions des protocoles à connaissance nulle nécessitent généralement que le prouveur et le vérificateur communiquent dans les deux sens et sont donc considérées comme des preuves ZK « interactives ». Mais dans les constructions « non interactives », prouveurs et vérificateurs n’ont à échanger qu’une seule preuve.
Actuellement, les preuves zk-SNARK dépendent d'une configuration initiale de confiance entre un prouveur et un vérificateur, ce qui signifie qu'un ensemble de paramètres publics est requis pour construire des preuves sans connaissance et, donc, des transactions privées. Ces paramètres sont presque comme les règles du jeu ; ils sont codés dans le protocole et constituent l’un des facteurs nécessaires pour prouver la validité d’une transaction. Cependant, cela crée un problème potentiel de centralisation car les paramètres sont souvent formulés par un très petit groupe.
Bien qu’une configuration initiale fiable soit fondamentale pour les implémentations actuelles de zk-SNARK, les chercheurs s’efforcent de trouver d’autres alternatives afin de réduire le niveau de confiance requis dans le processus. La phase de configuration initiale est importante pour prévenir les dépenses contrefaites, car si quelqu'un avait accès au caractère aléatoire qui a généré les paramètres, il pourrait créer de fausses preuves qui semblaient valables au vérificateur. Dans Zcash, la phase de configuration initiale est connue sous le nom de cérémonie de génération de paramètres.
Passons à la partie « Arguments de connaissance » de l'acronyme. Les zk-SNARK sont considérés comme étant fiables sur le plan informatique, ce qui signifie qu'un prouveur malhonnête a très peu de chances de réussir à tromper le système sans avoir réellement les connaissances (ou le témoin) pour étayer sa déclaration. Cette propriété est connue sous le nom de solidité et suppose que le prouveur dispose d’une puissance de calcul limitée.
Théoriquement, un prouveur doté d'une puissance de calcul suffisante pourrait créer de fausses preuves, et c'est l'une des raisons pour lesquelles les ordinateurs quantiques sont considérés par beaucoup comme une menace pour les zk-SNARK (et les systèmes blockchain).
Les preuves sans connaissance sont rapidement vérifiables et nécessitent généralement beaucoup moins de données qu'une transaction Bitcoin standard. Cela ouvre la voie à l’utilisation de la technologie zk-SNARK à la fois comme solution de confidentialité et d’évolutivité.
zk-STARKLes zk-STARK ont été créés par Eli-Ben Sasson, professeur à l'Institut de technologie Technion-Israël. En tant que version alternative des preuves zk-SNARK, les zk-STARK sont généralement considérées comme une variante plus efficace de la technologie - potentiellement plus rapide et moins chère, selon l'implémentation. Mais plus important encore, les zk-STARK ne nécessitent pas de configuration initiale fiable (d'où le « T » pour transparent).
Techniquement parlant, les zk-STARK ne nécessitent pas de configuration initiale fiable car ils s'appuient sur une cryptographie plus simple grâce à des fonctions de hachage résistantes aux collisions. Cette approche élimine également les hypothèses de la théorie des nombres des zk-SNARK qui sont coûteuses en calcul et théoriquement sujettes aux attaques des ordinateurs quantiques.
En d’autres termes, les preuves zk-STARK présentent une structure plus simple en termes d’hypothèses cryptographiques. Cependant, cette nouvelle technologie présente au moins un inconvénient majeur : la taille des preuves est plus grande que celle des zk-SNARK. Une telle différence dans la taille des données peut présenter des limites en fonction du contexte d’utilisation, mais c’est probablement quelque chose qui pourra être compris à mesure que la technologie sera testée et étudiée plus en détail.
Pensées finalesIl est clair que les zk-SNARK et les zk-STARK répondent aux préoccupations croissantes concernant la confidentialité. Dans le monde des cryptomonnaies, ces protocoles ont un grand potentiel et pourraient constituer une voie révolutionnaire vers une adoption généralisée.

La parabole de la caverne d'Ali Baba

zk-SNARK

zk-STARK

Pensées finales

Découvrez-en plus sur le créateur

Dernières actualités