Les preuves de connaissances zéro semblent souvent mystérieuses parce que les mathématiques derrière elles sont très avancées. Nous voulons éliminer cette confusion et aider tout le monde à comprendre ce que les preuves de connaissances zéro font réellement. Dans ce post, nous présentons un bloc de construction important utilisé dans de nombreux systèmes de preuve de connaissance zéro: Après cela, nous expliquons , l'un des types les plus populaires et pratiques de schémas d'engagement polynomial. polynomial commitment schemes KZG Nous décrivons ensuite comment et comment . Finally, we show how zk-rollups and Proto-Danksharding can work together smoothly and efficiently — something that is possible specifically because . KZG is used inside zk-rollups Ethereum also uses KZG in Proto-Danksharding both systems use polynomial commitment schemes Why are we talking about polynomials? Les polynômes sont des outils mathématiques puissants car ils nous permettent de représenter efficacement des objets grands ou complexes. Un exemple commun est de représenter un vecteur n-dimensionnel d'éléments de champ v en utilisant un polynôme unique. Nous le faisons en construisant un polynôme φ(x) qui passe à travers les points (i, v_i) pour chaque index i = 1, 2, ..., n. Par exemple, le vecteur 3 dimensional v = [2, 0, 6] peut être codé par le polynôme Parce que la mise en valeur des valeurs , à et En général, étant donné n points, il existe toujours un polynôme unique de degré au plus n − 1 qui passe à travers tous. φ(x) = 4x² − 14x + 12 φ(1) = 2 φ(2) = 0 φ(3) = 6 Le processus de construction de ce polynôme est appelé interpolation polynomiale, et l'une des techniques les plus utilisées est , qui fournit une formule directe pour construire le polynôme à partir des points donnés.Avec cette méthode, nous savons maintenant comment construire un polynôme de degré au maximum . Interpolation de Lagrange n − 1 from exactly n constraints Dans la section précédente, nous avons appris que si vous savez , vous pouvez toujours déterminer un polynôme unique dont le degré est au plus Maintenant, nous voulons aller un pas de plus et comprendre Le polynôme est calculé à partir des coordonnées de ces n points. n points n − 1 Comment Une méthode commune et simple pour ce faire est appelée interpolation de Lagrange. Même si les formules officielles peuvent sembler compliquées, l'idée de base est très simple. L'interpolation de Lagrange nous donne un moyen direct de construire le polynôme qui passe à travers tous les points donnés. Par exemple, supposons que nous souhaitons trouver un polynôme de degré au maximum 2 (c'est-à-dire un polynôme carré). Pour ce faire, nous avons besoin exactement de 3 points, et le polynôme doit satisfaire tous les trois de ces contraintes. En utilisant les coordonnées de ces 3 points, l'interpolation de Lagrange construira le polynôme exact qui les correspond parfaitement. P φ(1) = 2 φ (2) = 0 φ(3) = 6 Pour ce faire, nous allons construire 3 sous-polynômes (un par contrainte) , et Au plus haut degré . P₁ P₂ P₃ 2 Ces 3 sous-polynômes doivent suivre ces sous-restrictions : x P₁(x) P₂(x) P₃(x) 1 2 0 0 2 0 0 0 3 0 0 6 1 2 0 0 2 0 0 0 3 0 0 6 Chaque sous-polynôme évalue dans tous les domaines, sauf un. 0 Enfin, nous avons fixé : P(x) = P₁(x) + P₂(x) + P₃(x) Vérifions rapidement, en référence à l'onglet précédent, que Respectez toutes vos contraintes : P P(1) = P₁(1) + P₂(1) + P₃(1) = 2 + 0 + 0 = 2 P(2) = P₁(2) + P₂(2) + P₃(2) = 0 + 0 + 0 = 0 P(3) = P₁(3) + P₂(3) + P₃(3) = 0 + 0 + 6 = 6 Nous venons de vérifier que respect de ses 3 contraintes. Maintenant, construisons , à et . P P₁ P₂ P₃ Building P₁ Using the , we can define P₁ as: factorised form P₁(x) = A(x − 2)(x − 3) satisfait déjà aux contraintes : P₁ P₁(2) = P₁(3) = 0 Maintenant, trouvons comme par exemple : A P₁(1) = 2 Nous avons l’équation suivante : P₁(1) = A(1 - 2)(1 - 3) = 2 Ce qui nous donne : A = 2 Et enfin : P₁(x) = 2(x − 2)(x − 3) Il répond désormais à ses trois sous-réglages. P₁ Bâtiment P2 Utilisant le , we can define comme : Forme fabriquée P2 P₂(x) = B(x - 1)(x − 3) satisfait déjà aux contraintes : P2 P₂(1) = P₂(3) = 0 Maintenant, trouvons comme par exemple : B P₂(2) = 0 Nous avons l’équation suivante : P₂(2) = B(2 − 1)(2 − 3) = 0 Ce qui nous donne : B = 0 Et enfin : P₁(x) = 0(x − 1)(x − 3) = 0 Il répond désormais à ses trois sous-réglages. P₂ Construction du P3. Utilisant le Nous pouvons définir comme : Forme fabriquée P3 P₃(x) = C(x − 1)(x − 2) satisfait déjà aux contraintes : P₃ P₃(1) = P₃(2) = 0 Maintenant, trouvons comme par exemple : C P₃(3) = 6 Nous avons l’équation suivante : P₃(3) = C(3 - 1)(3 - 2) = 6 Ce qui nous donne : C = 3 Et enfin : P₃(x) = 3(x - 1)(x - 2) Il répond désormais à ses trois sous-réglages. P₃ Building P As previously seen, P(x) = P₁(x) + P₂(x) + P₃(x) Replacing , and by their respective expression, we get: P₁ P₂ P₃ P(x) = (x - 2)(x - 3) + 0 + 3(x - 1)(x - 2) P(x) = (x² - 5x + 6) + 3(x² - 3x + 2) P(x) = x² - 5x + 6 + 3x² - 9x + 6 P(x) = 4x² - 14x + 12 After expansion and simplification, we obtain: P(x) = 4x² - 14x + 12 Vérifier p Voyons vite ceci Il respecte les 3 contraintes : P P(1) = 4(1²) - 14(1) + 12 = 4 - 14 + 12 = 2 P(2) = 4(2²) - 14(2) + 12 = 16 - 28 + 12 = 0 P(3) = 4(3²) - 14(3) + 12 = 36 - 48 + 12 = 6 What are polynomial commitment schemes, and why are they useful? Les schémas d'engagement polynomial sont des outils spéciaux qui permettent à quelqu'un de s'engager à un polynomial entier sans montrer ce que le polynomial est réellement. , meaning you cannot change the message after committing, and Les polynômes suivent les mêmes règles, mais au lieu de s'engager à un seul message, vous vous engagez à un polynôme entier avec de nombreux coefficients. binding hiding The powerful part of polynomial commitments is that you can later prove the value of the polynomial at specific points without revealing the entire polynomial. For example, if someone wants to prove that their secret polynomial Vous avez la valeur à , ils peuvent le faire sans exposer le reste du polynomial. Ils donnent simplement une courte preuve qui montre est vrai, et le vérificateur peut le vérifier en utilisant l'engagement antérieur. Le vérificateur n'apprend rien d'autre sur le polynôme lui-même. Cette fonctionnalité est incroyablement utile dans les preuves de connaissances zéro, où l'objectif est de prouver que quelque chose est vrai sans révéler d'informations supplémentaires. ϕ(x) 66 x = 4 “ϕ(4) = 66” Another reason polynomial commitments are useful is that the commitment is much smaller than the polynomial. A polynomial may have hundreds or thousands of values, but the commitment can be just a single small group element, like 48 bytes. This is extremely important for blockchains, where storing or posting large data is expensive. By compressing a large polynomial into one tiny commitment, systems like et Cela permet d’économiser beaucoup d’espace et de réduire les coûts. zk-rollups Proto-Danksharding Pour rendre cela plus facile à comprendre, imaginez Alice a un polynôme secret, comme φ(x) = 3x2 + 5x + 2. Elle ne veut pas révéler le polynôme, mais Bob veut la preuve que φ(4) = 66. Alice s'engage au polynôme en utilisant un schéma d'engagement polynomial et envoie Bob l'engagement. Plus tard, elle révèle seulement la valeur 66 et fournit une preuve courte montrant que cette valeur est correcte pour x = 4. Bob vérifie la preuve contre l'engagement et devient convaincu, sans jamais apprendre quoi que ce soit d'autre sur le polynôme. C'est pourquoi les engagements polynomials sont des outils puissants dans la cryptographie moderne et essentiels pour les systèmes blockchain évolutifs. KZG Polynomial Commitment KZG Polynomial Commitment 1. Commitment Dans un engagement polynomial, le testeur transforme d'abord ses données en un polynomial. Ensuite, ils créent un "engagement" cryptographique spécial à ce polynomial. Vous pouvez penser à cet engagement comme sceller le polynomial à l'intérieur d'une boîte verrouillée: le testeur ne peut pas le changer plus tard, et le testeur ne peut pas voir ce qui est à l'intérieur. Cette étape garantit deux choses - le polynomial ne peut pas être modifié ( ) et son contenu reste privé ( ) de binding hiding 2. Evaluation Ensuite, le probateur veut prouver quelque chose au sujet du polynôme . So they pick a point x, plug it into the polynomial, and calculate the answer . They send only this value y, plus a small proof that shows the value came from the committed polynomial. The actual polynomial stays hidden the whole time. This allows the prover to show the polynomial behaves correctly at one point without exposing the entire polynomial. Sans le révéler y=P(x) 3. Verification Enfin, le vérificateur vérifie si la valeur correspond vraiment au polynomial engagé au point Utilisant l'engagement et la preuve, le vérificateur effectue une vérification cryptographique. must be true — even though they never saw the polynomial itself. If the prover tries to lie or cheat, the verification step will catch it. This makes polynomial commitments secure and very useful in technologies like zero-knowledge proofs and Ethereum scaling. y x P(x)=y KZG Polynomial Commitment Scheme KZG Polynomial Commitment Scheme KZG has . four main steps Step 1 - Trusted Setup Une configuration unique effectuée avant que le système ne fonctionne. Choisissez un générateur g d'un groupe de courbe elliptique G (couplages de support). Choisissez le degré maximum l du polynomial. Choisissez une valeur aléatoire secrète : τ ∈ Fp Compute and publish: (g, g^τ, g^(τ^2), ...., g^(τ^l)) Only these powers of are public. gᵗ The value τ must remain secret forever. If someone knows τ, they can forge proofs. Step 2 - Commit to a Polynomial Suppose we have the polynomial: ϕ(x) = ∑ᵢ₌₀ˡ ϕᵢ xⁱ We want to compute the commitment: C = g^{ϕ(τ)} Although the committer cannot compute directly since he doesn’t know , he can compute it using the output of the setup g^{ϕ(τ)} τ τ Step 3 - Create a Proof for Evaluation ϕ(a)=b Pour prouver cela : ϕ(a)=b Calculer le quotient polynomial : q(x) = ϕ(x) - b / x - a Ceci n’est valable que si l’évaluation est correcte. Puis comptez la preuve : π = g^{q(τ)} Voici la preuve de l'évaluation KZG. Step 4 - Verification donnés : L’engagement C = g^{φ(τ)} La preuve π = g^{q(τ)} Evaluation claim ϕ(a)=b Le vérificateur vérifie : e(c/g^b,g) = e(π,g^τ/g^a) Here 𝑒 ( ⋅ , ⋅ ) is a . bilinear pairing Cette équation équivaut à vérifier : q(τ) = ϕ(τ) - b /τ - a Si la vérification d'accouplement est retenue, l'évaluation est acceptée comme correcte. Brève explication de la vérification des pairs Les LHS : = à (b) C est le nombre de e(C/g^b, g) e(g,g)ϕ RHS: = à (π = g^{q(τ)}) e(π, g^τ/g^a) e(g,g)q(τ)⋅(τ−a) L'égalité implique φ(τ)−b = q(τ)(τ−a), l'identité quantique évaluée à τ, qui impose φ(a)=b si q(x) a été correctement formé. (q(x) = φ(x) - b / x - a) Brève explication de la vérification des pairs Les LHS : = à (b) C est le nombre de e(C/g^b, g) e(g,g)ϕ Le RHS : = à (π = g^{q(τ)}) e(π, g^τ/g^a) e(g,g)q(τ)⋅(τ−a) L'égalité implique φ(τ)−b = q(τ)(τ−a), l'identité quantique évaluée à τ, qui impose φ(a)=b si q(x) a été correctement formé. (q(x) = φ(x) - b / x - a) Use Cases: Les rouleaux In zk-rollups, we must prove that the work done on Layer 2 (L2) is correct. To do this, all the steps of the computation are converted into a big table (a 2D matrix). This happens during a process called Chaque colonne de cette table représente une partie du calcul, et chaque colonne peut être transformée en polynomiale. Ainsi, au lieu de traiter directement une énorme matrice, nous travaillons avec une liste de polynomials. La correction du calcul peut ensuite être décrite en utilisant des règles mathématiques entre ces polynomials. Par exemple, imaginez que trois colonnes de la table représentent trois polynomials: Génération témoin A( x ) B( x ) c(x) Une règle pourrait dire que a(x)⋅b(x)−c(x)=0 Cela signifie "le premier polynôme multiplié par le second doit être égal au troisième." column 1 × column 2 must produce column 3. Au lieu de vérifier cette règle pour chaque valeur possible de x (ce qui serait lent), zk-rollups vérifier seulement à quelques points aléatoires. Si je veux vérifier si deux longues listes correspondent à une règle, je n’ai pas besoin de comparer chaque élément – vérifier quelques éléments aléatoires me dit généralement si l’ensemble de la relation est valide. Example: Les schémas d’engagement polynomial – tels que KZG – sont parfaits pour cela. Le rollup s’engage à tous les polynômes qui décrivent le calcul L2 (quelque chose comme les verrouiller dans une boîte cryptographique). Plus tard, le vérificateur peut demander les valeurs de ces polynômes à des points aléatoires spécifiques. Avec ces valeurs et les engagements, le vérificateur vérifie si les règles de correction s’appliquent. Le proto-gratitude d’Ethereum (EIP-4844) est une mise à niveau conçue pour rendre beaucoup moins cher pour les rollups de publier leurs données sur la couche 1 d'Ethereum. . This type of transaction includes a large piece of data called a (environ 128 kB). cependant, ce blob est des contrats intelligents ou de la couche d'exécution. les contrats intelligents ne peuvent voir qu'une to the blob, not the blob itself. Le proto-merci Transaction Blob Transaction Blob not commitment Maintenant la question est : Une option est de prendre le blob et juste Mais le hashing est limité: si nous stockons seulement un hash, alors plus tard, nous ne pouvons rien prouver sur les données à l'intérieur du blob sans révéler l'ensemble du blob. How should Ethereum create this commitment to the blob? hash it Au lieu de cela, nous pouvons traiter le blob comme un polynôme. (Avant, nous avons expliqué comment les vecteurs ou les données peuvent être représentés comme des polynômes.) comme KZG, Ethereum peut s'engager dans le blob d'une manière qui non seulement cache les données, mais permet également la vérification de certaines propriétés . polynomial commitment scheme Télécharger tout le blob Cette capacité est essentielle pour ce qu'on appelle DAS permet aux validateurs de vérifier si le blob est disponible et correct . Instead, validators download only tiny random pieces. Thanks to the math behind polynomial commitments, if enough random samples are correct, validators can be highly confident that the whole blob is available. (Although DAS is not included in the very first version of Proto-Danksharding, it will be added soon as Ethereum continues toward “full Danksharding.”) (DAS) Échantillonnage de disponibilité des données Télécharger tous les 128 KB Échantillonnage de disponibilité des données Ethereum a choisi as the polynomial commitment scheme for Proto-Danksharding and future sharding upgrades. Researchers compared several schemes, and concluded that KZG provides the best balance of efficiency, proof size, and simplicity for Ethereum’s roadmap in the short and medium term. KZG How zk-rollups and Ethereum’s Proto-Danksharding interact zk-rollups et Proto-Danksharding d'Ethereum peuvent sembler être des systèmes séparés, mais ils utilisent tous les deux les engagements KZG de manière à leur permettre de travailler ensemble de manière fluide. Scroll utilise KZG pour s'engager dans les calculs effectués sur la couche 2, tandis que Ethereum utilise KZG pour s'engager dans de grands blocs de données publiés sur la couche 1. Lorsque Scroll termine de traiter un lot de transactions L2 et calcule une nouvelle racine d'état, il doit publier trois choses sur l'Ethereum L1: T - la liste des transactions L2, Si - la nouvelle racine d'état après l'application de ces transactions, π - la preuve que la nouvelle racine d'état est correcte. Ethereum doit vérifier deux choses: que la nouvelle racine d'état Si est valide (ce qui signifie que les transactions ont été exécutées correctement), et que la liste de transactions T est exactement celle utilisée pour produire cette racine d'état.Il doit donc y avoir un moyen de lier la liste de transactionsT à la preuve π. Les magasins Ethereum comme a Ce qui signifie que le client n’a accès qu’à un à ce blob - appellons cet engagement Pendant ce temps, la preuve also contains KZG commitments to various polynomials used during the computation, including the polynomial that represents the transaction list. That polynomial has its own commitment inside the proof—call it . T Blob de données KZG commitment Cₜ π Cₚ Now we have two different KZG commitments ( Le Blob et de la preuve) que représentent la même φt polynomiale (la représentation polynomiale de la liste de transactions). et En fait, il s’agit des mêmes données. Cₜ Cₚ should Cₜ Cₚ Pour ce faire, nous utilisons une technique appelée L’idée est simple : La preuve de l’équivalence La preuve de l’équivalence Choisissez une valeur aléatoire = hash(Ct Cp) Cela rend z imprévisible et unique à ces deux engagements. Both commitments are then “opened” at the point z, each producing a value . That is, prove that: a ϕₜ(z) = a under commitment , and Cₜ ϕₜ(z) = a under commitment . Cₚ Si les deux engagements donnent la même valeur au même point aléatoire, alors avec une probabilité extrêmement élevée, ils représentent le même polynôme. Exemple : Imaginez deux personnes, chacune prétendant qu’elles ont le même polynôme secret. Au lieu de révéler le polynôme entier, chacune l’évalue à un point aléatoire, disant x = 103. : Imagine two people, each claiming they have the same secret polynomial. Instead of revealing the whole polynomial, each evaluates it at a random point-say x = 103. If both evaluations match, the chance of them having two different polynomials that coincidentally agree at that exact random point is astronomically small. Example Cette même logique permet à Ethereum de vérifier que la liste de transactions utilisée dans la preuve est exactement la même que la liste de transactions publiée dans le blob. π Un bon bonus est que ce contrôle d'équivalence fonctionne même si les deux engagements utilisent Par exemple, l'un pourrait être KZG et l'autre FRI. Tant que les deux engagements soutiennent l'ouverture à un moment donné, le vérificateur peut les comparer, ce qui rend cette approche très flexible. Différents Différents Erasure Coding With Polynomials Un autre concept puissant utilisé à la fois dans KZG et PeerDAS est Cette technique permet de récupérer des données même si des parties de celle-ci sont manquantes.En utilisant les polynômes, nous pouvons prendre un petit ensemble de valeurs originales et les étendre à un ensemble plus long en évaluant le polynôme à des points supplémentaires. . This is exactly how Ethereum’s data-availability sampling (DAS) works: nodes don’t need every piece of data, only a random sample that lets them reconstruct the original information with high probability. erasure coding if the degree stays the same, the original data can be recovered from subset of enough points tout tout Pourquoi les engagements polynomials sont-ils nécessaires ? Why Polynomial Commitments Are Needed? Using polynomials and erasure codes solves many problems, but creates a new one: How do we prove that a piece of data truly belongs to the committed polynomial? C’est là où come in. A KZG commitment allows: KZG polynomial commitments committing to a polynomial with a single small group element prouver qu'un point de données est l'une des évaluations du polynôme verifying the proof without downloading the polynomial or reconstructing it Cette propriété est essentielle pour la feuille de route d’échelle d’Ethereum, car les validateurs doivent vérifier la disponibilité des données efficacement sans lire les mégabytes de données blob. et Utiliser les polynômes pour diviser les données , à et Chaque blob est traité comme un polynôme dont les évaluations remplissent les données. Lorsque les données sont étendues et organisées en colonnes, les validateurs ne reçoivent que de petites pièces, mais la structure polynomiale assure que toutes les pièces sont cohérentes. Chaque preuve confirme qu'une cellule spécifique correspond au polynomial commis dans l'en-tête du bloc. Peerdes Le proto-merci columns cells blobs KZG proofs Grâce aux engagements polynomials, Ethereum peut évoluer en toute sécurité la disponibilité des données tout en réduisant considérablement la charge sur les nœuds individuels. et des peers. Éditeur 4844 Ensuite, nous allons examiner de plus près comment fonctionne PeerDAS, comment les engagements de KZG y jouent un rôle clé et comment le codage de suppression permet au réseau de récupérer les données manquantes. Ensuite, nous allons examiner de plus près comment fonctionne PeerDAS, comment les engagements de KZG y jouent un rôle clé et comment le codage de suppression permet au réseau de récupérer les données manquantes.
