<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Taras Shchybovyk on Medium]]></title>
        <description><![CDATA[Stories by Taras Shchybovyk on Medium]]></description>
        <link>https://medium.com/@cryptofairy?source=rss-b3a405d735c6------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*kk_TdjMriNY8wa4i6vWL2g.png</url>
            <title>Stories by Taras Shchybovyk on Medium</title>
            <link>https://medium.com/@cryptofairy?source=rss-b3a405d735c6------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 13:38:41 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@cryptofairy/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[How I Got a 4× Reduction in V-JEPA 2’s Heaviest Computation]]></title>
            <link>https://medium.com/@cryptofairy/how-i-got-a-4-reduction-in-v-jepa-2s-heaviest-computation-d54376052d8d?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/d54376052d8d</guid>
            <category><![CDATA[vjepa2]]></category>
            <category><![CDATA[yolo-12]]></category>
            <category><![CDATA[meta]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[video-transformers]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Sun, 15 Feb 2026 23:14:42 GMT</pubDate>
            <atom:updated>2026-02-15T23:14:42.487Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Spatiotemporal Area Attention for Video Transformers</em></p><p>Not so long ago I started to have interest in AI video models and stumbled across V-JEPA 2 made by Meta — a model that can understand the context of video. My interest ended up with a 4× reduction in one of the heaviest computation parts — with almost zero cost to quality.</p><p>This post is the full story: what V-JEPA 2 is, how it works under the hood, what I changed, and whether it actually held up under real evaluation. Even if you’ve never touched machine learning, I want you to follow every step.</p><h4>A Neural Network Is a Prediction Machine</h4><p>Skip this section if you already know how neural networks work. If not — this is the foundation for everything that follows.</p><p>At its core, a neural network is a function designed to <strong>predict the next piece of data</strong>. You feed it some input, and it predicts what comes next. But unlike a regular function like sin(x) whose behavior is fixed, a neural network has <strong>millions of adjustable knobs</strong>:</p><pre>prediction = f(input, knobs)</pre><p>Each knob is called a <strong>weight</strong> or <strong>parameter</strong>. By adjusting these knobs, you can make f predict almost anything — the next word in a sentence, the next frame in a video, or what&#39;s hidden behind a mask.</p><p>But here’s the thing: before a network can predict anything, the data needs to be chopped into pieces the network can digest. These pieces are called <strong>tokens</strong>. And the way you create tokens changes everything.</p><h4>Tokens Are Not Just for Text</h4><p>When people hear “tokens,” they usually think of text — words or word fragments. GPT predicts the next <em>text token</em>. But tokens are a much more general idea. They’re just the <strong>smallest unit of data that a model works with</strong>.</p><p>For video, there are two very different ways to create tokens:</p><p><strong>Approach 1: Pixel tokens.</strong> Chop the video into small pixel patches and treat each patch as a token. The model then tries to predict the actual pixel values of missing or future patches. This is what models like Sora do — they work directly in <em>pixel space</em>. The upside: you can generate realistic-looking video. The downside: the model wastes enormous capacity predicting irrelevant details (exact leaf positions, water ripple patterns, subtle lighting).</p><p><strong>Approach 2: Embedding tokens.</strong> Instead of working with raw pixels, first compress each patch into an abstract vector of numbers — an <strong>embedding</strong>. An embedding is a learned summary that captures the <em>meaning</em> of a patch, not its exact pixel values. Two patches showing “a hand reaching for a cup” from slightly different angles would have very different pixels but very similar embeddings.</p><p>This is where V-JEPA 2 sits. It predicts <strong>embeddings, not pixels</strong>. It works in <em>meaning space</em>. This distinction is the single most important thing to understand about the model, and we’ll come back to it.</p><h3>What V-JEPA 2 Actually Is</h3><p><strong>V-JEPA 2</strong> is a video model built by Meta’s AI research lab (FAIR). It was trained on over a million hours of internet video — and it learned to understand the physical world well enough to control a robot arm in environments it has never seen.</p><p>No labels. No human annotations. Nobody told it “this is a dog running” or “this person is cooking.” It figured everything out on its own. How?</p><h4>Learning by Predicting What’s Hidden</h4><p>You know that feeling when you’re in a movie theatre and someone tall keeps standing up or walking in front of you? You can only see a fraction of the screen, but you still follow the plot — a hand reaches for something, a face reacts, and your brain fills in the rest. In V-JEPA 2’s case, that fraction is literally <strong>25%</strong> — the model only gets to see a quarter of the video.</p><p>V-JEPA 2 is trained exactly like that. During training, it takes a video clip, <strong>blocks out 75% of it</strong>, and tries to figure out what’s behind the obstruction. Not the actual pixels (we’ll get to why that matters), but an abstract <em>understanding</em> of what’s there.</p><p>After doing this across millions of videos, the model develops a deep sense of how the visual world works — objects, motion, gravity, cause and effect. Just like you’d eventually get really good at following movies from the worst seat in the house.</p><p>This approach is called <strong>self-supervised learning</strong>. The “supervision” (the training signal) comes from the data itself — the hidden patches <em>are</em> the answer key. No expensive human labeling required. This is a big deal because you can scale it to essentially unlimited video data.</p><h4>Why Predict Representations Instead of Pixels?</h4><p>This is the single most important design decision in V-JEPA 2, and it’s worth understanding. Most video AI models try to predict actual pixels. Given some frames, generate what the next frame looks like. Sounds intuitive, right? But it has a deep problem.</p><p><strong>The leaf problem</strong> (as Yann LeCun, Meta’s chief AI scientist and the architect behind JEPA, likes to illustrate): Imagine a video of a tree swaying in the wind. To predict the next frame’s pixels, the model needs to figure out exactly where every single leaf will be. That’s chaotic — essentially unpredictable. But what’s <em>actually</em> important about the scene? The tree is still there, it’s still swaying, nothing meaningful changed.</p><p>Pixel prediction forces the model to waste its capacity on irrelevant noise — exact leaf positions, precise water ripples, subtle lighting shifts.</p><p>V-JEPA 2 takes a different approach. It doesn’t predict pixels. It predicts <strong>representations</strong> — abstract summaries of what’s in each patch. In representation space, “tree swaying in wind” has a stable value even as the pixels change chaotically.</p><p>This is what JEPA stands for: <strong>Joint-Embedding Predictive Architecture</strong>. The model learns to predict in a <em>meaning space</em>, not a <em>pixel space</em>. It’s forced to learn what’s genuinely predictable about the physical world — trajectories, gravity, cause and effect — and ignore the noise.</p><h4>Under the Hood: Three Parts Working Together</h4><p>V-JEPA 2’s training involves three components:</p><pre>Video (with 75% masked) ──▶ ENCODER ──▶ Features of visible patches<br>                                              │<br>                                              ▼<br>  &quot;Where are the hidden     ──▶ PREDICTOR ──▶ Predicted features<br>   patches?&quot;                                  for hidden patches<br>                                              │<br>                                           Compare<br>                                              │<br>  Video (full, unmasked) ───▶ TARGET     ──▶ Actual features<br>                              ENCODER         for hidden patches</pre><p>The <strong>encoder</strong> is the main model — a large neural network that turns video patches into abstract features. This is the part that learns to understand video.</p><p>The <strong>predictor</strong> is a smaller network that takes the visible features and tries to predict what the hidden patches should look like in feature space.</p><p>The <strong>target encoder</strong> is a slowly-updating copy of the main encoder. It processes the full unmasked video to provide the “correct answers.” It updates slowly (using an exponential moving average) to provide a stable target — without this, the whole system could collapse into producing meaningless outputs.</p><p>After training is done, you throw away the predictor and target encoder. The encoder alone is the finished product — a video understanding engine.</p><h4>Transformers and Tokens: How the Encoder Actually Works</h4><p>The encoder is built on an architecture called a <strong>Vision Transformer (ViT)</strong>. To understand what I changed, you need to understand how it processes video.</p><h4>Chopping Video Into Tokens</h4><p>The model doesn’t look at video as a continuous stream of pixels. It chops the video into small <strong>patches</strong> — tiny cubes of space and time, each covering 16×16 pixels across 2 frames. Each patch is called a <strong>tubelet</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BvvkDMGt87t3NlNSmESDgg.png" /><figcaption>Tubulets within frame</figcaption></figure><pre>Video: 64 frames at 256×256 pixels<br>Each tubelet = 2 frames × 16px × 16px<br>Spatial patches per frame pair: (256÷16)² = 256<br>Temporal steps: 64÷2 = 32<br>Total tubelets: 256 × 32 = 8,192</pre><p>Each tubelet gets converted into a vector of 1,024 numbers — its <strong>embedding</strong>. Think of this embedding as a compressed summary of what that tiny chunk of video contains. Similar content produces similar embeddings; different content produces different ones.</p><p>So now the video isn’t an image sequence anymore. It’s a <strong>list of 8,192 tokens</strong>, each represented by 1,024 numbers. The model processes this list.</p><h4>How the Model Knows Where Each Token Came From</h4><p>Once you chop a video into tokens and line them up in a list, you’ve lost the spatial structure. Token #47 and token #3,891 are both just vectors — the model doesn’t know which came from the top-left corner and which came from the bottom-right.</p><p>V-JEPA 2 solves this with <strong>3D Rotary Position Embeddings (3D-RoPE)</strong>. The idea: instead of adding a position tag to each token, you <em>rotate</em> each token’s vector based on its (x, y, time) coordinates. When two tokens interact, the rotation naturally encodes how far apart they are in space and time. Nearby tokens get similar rotations; distant tokens get very different ones.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lk4F-Yon7qtSlg8p-aUu3Q.png" /><figcaption>Cube’s (embedding 12, 12, 12 …) movement from right to left (rotated embedding 12, 12, 123, …)</figcaption></figure><p>The “3D” part means the rotation happens across three axes — height, width, and time — since video is inherently three-dimensional.</p><h4>Self-Attention: The Expensive Part</h4><p>Now comes the core operation — and the bottleneck I set out to fix.</p><p>At each layer of the Transformer, every token needs to “look at” every other token and decide: <em>who should I pay attention to?</em> This is called <strong>self-attention</strong>.</p><p>Each token computes three things:</p><ul><li>A <strong>query</strong> — “what am I looking for?”</li><li>A <strong>key</strong> — “what do I contain?”</li><li>A <strong>value</strong> — “what information can I share?”</li></ul><p>Every token’s query gets compared against every other token’s key. High similarity means “pay attention to this one.” The model then takes a weighted mix of the values, where more relevant tokens contribute more.</p><p>But it’s <strong>expensive</strong>. With N tokens, every token talks to every other token. That’s N × N comparisons. Think of a room full of people where everyone must have a one-on-one conversation with everyone else:</p><ul><li>10 people → 45 conversations</li><li>100 people → ~5,000 conversations</li><li>4,608 people → <strong>over 10 million conversations</strong></li></ul><p>Double the people? Four times the conversations. The cost grows with the <strong>square</strong> of the token count — O(N²) in math notation.</p><p>V-JEPA 2’s encoder has <strong>24 layers</strong>, and this N² attention happens at <em>every single layer</em>. At 4,608 tokens (after masking), that’s over 10 million comparisons per layer, times 24 layers.</p><p>This is the bottleneck that caught my eye.</p><h4>My Change: Stop Talking to Everyone (Most of the Time)</h4><p>Back to our room of 4,608 people. What if, for <em>most</em> rounds of discussion, instead of everyone talking to everyone, we split the room into <strong>4 smaller groups</strong>? People only talk within their group. Suddenly each person has ~1,152 conversations instead of 4,608. That’s a <strong>4× reduction</strong> in total conversations.</p><p>But we can’t group randomly — we need the groups to make sense. Our “people” are video patches, and they have a natural structure: they come from specific <strong>spatial positions</strong> (where in the frame) and <strong>temporal positions</strong> (which frame).</p><p>Patches that are close together in space and time tend to be about the same thing — the same object moving, the same texture, the same part of the scene. So we group them by <strong>neighborhood</strong>: top-left of the first few frames goes in one group, bottom-right of the last few frames goes in another.</p><p>This idea is called <strong>area attention</strong> — it was originally introduced in YOLOv12 for 2D object detection. I extended it to handle video’s extra time dimension, which is how <strong>ST-A² (Spatiotemporal Area Attention)</strong> was born.</p><h4>Concrete Example</h4><p>Say we have a video forming a 16×16 spatial grid across 8 frames. With the default config (spatial_splits=2, temporal_splits=2), we split it into:</p><ul><li><strong>2 spatial halves</strong>: top half and bottom half</li><li><strong>2 time segments</strong>: first 4 frames and last 4 frames</li><li><strong>Total: 2 × 2 = 4 areas</strong></li></ul><p>A patch showing a person’s hand in the upper part of frame 2? It goes into the “top half / early frames” group. It only pays attention to other patches in that same area.</p><p>The math is just integer division on grid coordinates. No neural network overhead, no learned parameters — just slicing.</p><h4>The Process</h4><p>If you’re thinking “this is too clean,” you’re right. Remember that 75% masking? The remaining tokens aren’t neatly arranged in a grid. They’re scattered randomly across the whole video. You can’t just reshape the sequence and slice it.</p><p>Picture our room analogy again, but now randomly remove 75% of the people. The remaining ones are scattered everywhere. Before we can form our groups, we need to <strong>physically rearrange</strong> them.</p><p>Here’s how the implementation works:</p><ol><li><strong>Figure out where each token belongs</strong> — simple coordinate math</li><li><strong>Sort everyone into their groups</strong> — gather all the “top-left / early” tokens together, then “top-left / late,” and so on</li><li><strong>Even out the groups</strong> — since masking is random, some groups end up with more tokens than others. We add invisible placeholder tokens so every group is the same size (the model ignores them)</li><li><strong>Run attention within each group</strong> — one efficient batch operation</li><li><strong>Unsort</strong> — put everyone back in their original positions so the rest of the model doesn’t know anything changed</li></ol><p>Steps 2 and 5 add a little overhead (sorting takes time), but at high token counts, the attention savings crush it.</p><h4>Not All Layers Need This</h4><p>Here’s a design choice that took some thought.</p><p>The early layers of a Transformer learn low-level stuff — edges, colors, textures, short-range motion. These are inherently local. A texture pattern doesn’t need to know what’s happening across the video.</p><p>But the final layers do high-level reasoning — they’re trying to predict what’s behind the mask, and those masked patches could be <em>anywhere</em>. These layers need to see everything.</p><p>So I gave the <strong>first 18 layers (75%)</strong> area attention, and left the <strong>last 6 layers</strong> with full attention.</p><p>Think of a person looking at a very detailed painting. First, your eyes focus on individual sections — the face, the hands, the background — taking in all the fine details up close. Then you step back and take in the whole canvas to understand the big picture. The early layers are the close-up look; the final layers are the step back.</p><h4>Compatibility</h4><p>Meta released pretrained weights for V-JEPA 2. I wanted my modified model to load those exact weights — no conversion scripts, no retraining, no fuss.</p><p>The trick: my area attention module uses the <strong>exact same parameter names</strong> as the original. Same projection matrices, same dimensions, same everything. The only difference is what happens <em>between</em> loading the weights and producing the output. You can literally swap in my module, load Meta’s checkpoint file, and it just works.</p><p>This matters because pretraining V-JEPA 2 costs enormous compute — think hundreds of GPU-hours at minimum. If my modification required retraining from scratch, it would be a non-starter for most people.</p><h4>Testing It: The Full Pipeline</h4><p>I ran the complete evaluation on an NVIDIA L40S GPU 48GB. The pipeline had two parts: a computational cost sweep and a downstream quality test.</p><h4>Part 1: Speed — How Much Overhead Does Sorting Add?</h4><p>I ran the same training loop at four different video resolutions — comparing standard attention against area attention. Each run was 100 steps with random data, purely measuring speed and computational behavior.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/770/1*wXf61RR2RuT5LyIgEVJmfw.png" /></figure><p><strong>How to read this</strong>: “Time Overhead” means how much <em>slower</em> each step is (positive = slower). “Loss Delta” means how much the training loss changes (positive = slightly worse convergence).</p><p>The story is clear: <strong>the more tokens, the better area attention looks.</strong></p><p>At 512 tokens, the sorting overhead dominates and the loss suffers badly — there aren’t enough tokens per group for meaningful attention. But at 4,608 tokens (the resolution V-JEPA 2 actually trains at during its final phase), area attention adds <strong>essentially zero overhead</strong> while reducing the attention computation by 4×.</p><p>You might be wondering: if we reduced attention by 4×, why is it <em>slower</em> instead of faster? Three reasons:</p><ol><li><strong>Attention isn’t the only thing happening.</strong> Each layer also runs a feedforward network, layer normalization, RoPE computation, and other operations. Area attention only saves on the attention part — everything else stays the same.</li><li><strong>Sorting and unsorting cost something.</strong> The baseline doesn’t need to sort tokens at all. We added five new steps (assign, sort, pad, attend, unsort) and only one of them is cheaper than the original.</li><li><strong>75% masking already makes the baseline cheap.</strong> The full video has 8,192 tokens, but after masking the model only sees ~2,000–4,600. The baseline attention cost on this reduced count is already manageable — so there’s less to save.</li></ol><p>At 4,608 tokens, the attention savings and the sorting overhead roughly cancel out — hence the +0.4%. The real win comes at <strong>inference time</strong>, when there’s no masking and all 18,000+ tokens are visible. That’s where the quadratic cost explodes and area attention would make a real difference — but I haven’t benchmarked that yet.</p><h4>Part 2: Quality — Do the Representations Survive?</h4><p>Speed means nothing if the model learns garbage. To test quality, I used a standard benchmark called <strong>Kinetics-400 (K400)</strong> — a dataset of ~19,000 video clips spanning 400 everyday actions: playing drums, cooking, skateboarding, riding a bike, and so on.</p><p>The test is called a <strong>frozen probe</strong> evaluation. Here’s how it works:</p><ol><li><strong>Freeze</strong> the video encoder completely — its knobs are locked, it cannot adapt</li><li><strong>Attach</strong> a tiny classifier on top (called an “attentive probe” — 4 small transformer blocks)</li><li><strong>Train only the classifier</strong> to recognize actions in the videos</li></ol><p>If the encoder’s features are good, the classifier will learn to classify well despite the encoder being frozen. If area attention damaged the features, accuracy will drop.</p><p>It’s like testing a camera by handing the photos to a stranger and asking them to sort by category. You’re measuring the <strong>camera quality</strong>, not the stranger’s skill.</p><p>I tested three setups, all with identical classifier training:</p><ul><li><strong>Baseline</strong>: Meta’s original model, untouched</li><li><strong>ST-A² (no fine-tune)</strong>: Meta’s weights loaded straight into area attention layers — the model has <em>never seen</em> area attention before</li><li><strong>ST-A² (finetuned)</strong>: Same, but with 1,000 extra training steps to let the model adapt</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/898/1*ILb4hCah6OIQoTYnH7JOzA.png" /></figure><p>ST-A² retains <strong>97.4% of baseline accuracy</strong> without any fine-tuning at all.</p><p>Think about that for a second. The model was trained for thousands of GPU-hours with full attention. I swapped in a fundamentally different attention pattern — something it has never seen — and it kept 97.4% of its quality. The learned representations turned out to be far more robust than I expected.</p><h4>Fine-Tuning Didn’t Help</h4><p>This surprised me. I expected that giving the model 1,000 steps to adapt to area attention would close the gap. Instead, the finetuned version (82.70%) actually performed <em>slightly worse</em> than the non-finetuned version (82.85%).</p><p>Why? I assume it because the fine-tuning used only 19,000 videos from the K400 validation set. V-JEPA 2 was pretrained on millions of videos. 19,000 is a drop in the ocean — not enough for the model to learn anything useful, and potentially enough to slightly disturb the existing representations.</p><p>The real experiment would be pretraining from scratch with area attention enabled from step one. That would let the model learn representations that are <em>native</em> to partitioned attention. But that requires Meta-scale compute.</p><h4>Conclusion</h4><p>Let me be real about what this project is and isn’t.</p><p><strong>What it is</strong>: a clean engineering contribution that shows V-JEPA 2’s attention can be partitioned into spatiotemporal areas with near-zero cost at training scale and minimal quality loss. The implementation is drop-in compatible, the evaluation is reproducible, and the code is ready for review.</p><p><strong>What it isn’t</strong>: a breakthrough. The model doesn’t get <em>better</em> with area attention — it gets roughly 2 percentage points worse on downstream tasks. At training resolution with 75% masking, there’s no meaningful wall-clock speedup.</p><p><strong>Where it gets exciting</strong>: inference. During inference, there’s no masking. All tokens are visible. For a 384px, 64-frame video, that’s not 4,608 tokens — it’s over <strong>18,000 tokens</strong>. The quadratic cost of full attention at that scale is massive. Area attention could cut it dramatically, making real-time video understanding more practical. I haven’t profiled this yet, but the math is promising.</p><p>If Meta or anyone else decides to pretrain V-JEPA 2 with area attention from the start, the 2% gap would likely shrink or vanish — and the inference savings would come for free.</p><p>Everything — the implementation, evaluation scripts, and a one-command pipeline — is in my PR:</p><p><strong>PR</strong>: <a href="https://github.com/facebookresearch/vjepa2/pull/121">github.com/facebookresearch/vjepa2/pull/121</a></p><p>To reproduce all results on a single GPU (L40S recommended):</p><pre>git clone -b feat/st-a2-area-attention https://github.com/tarassh/vjepa2.git<br>bash vjepa2/scripts/setup_and_finetune.sh</pre><h4>References</h4><p>V-JEPA 2 <a href="https://arxiv.org/abs/2506.09985">https://arxiv.org/abs/2506.09985</a></p><p>YOLO 12 <a href="https://arxiv.org/abs/2502.12524">https://arxiv.org/abs/2502.12524</a></p><p><a href="https://github.com/facebookresearch/vjepa2/pull/121">github.com/facebookresearch/vjepa2/pull/121</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d54376052d8d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Multi-Party Computations: Multiplicative-to-Additive Conversion (MtA)]]></title>
            <link>https://medium.com/@cryptofairy/multi-party-computations-multiplicative-to-additive-conversion-mta-152e68aa539b?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/152e68aa539b</guid>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Mon, 04 Aug 2025 18:07:35 GMT</pubDate>
            <atom:updated>2025-08-04T18:07:35.331Z</atom:updated>
            <content:encoded><![CDATA[<p>In the previous article, we explored <a href="https://medium.com/@cryptofairy/multi-party-computations-oblivious-transfer-81efb872c8eb"><strong>Oblivious Transfer (OT)</strong></a>, one of the fundamental building blocks of Multi-Party Computation (MPC). Today, let’s step further by introducing <strong>Multiplicative-to-Additive (MtA)</strong> conversion — a critical ingredient for securely computing multiplication.</p><p>Just as OT enables secure selection without revealing private inputs, MtA securely computes multiplication without directly revealing inputs.</p><h4>Why MtA?</h4><p>In multi-party computations, there often arises the need to multiply two private numbers securely (a good example would be a <strong>zkTLS</strong> protocol). For instance, two participants, Alice and Bob, each holding private values <em>an</em> and <em>b</em>, want to compute shares of their product <em>a·b</em> without disclosing their individual inputs. Multiplication-to-Additive (MtA) conversion is precisely designed for this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*u2JeEOyrn0WiggP-aKczhQ.png" /></figure><p>Neither party sees the other’s secret, yet both contribute securely to the final result.</p><h4>How MtA works</h4><p>MtA relies on a combination of random masking and the Oblivious Transfer protocol discussed in the previous article. Simplified example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WgwTOMIegaH5rfWCexMJlg.png" /></figure><ol><li>Masking<br>Alice has secret <em>a,</em> which should not be revealed. Alice pics random number <em>δ</em> and creates two masked values based on the secret <em>a: <br>(δ-a, δ+a).</em></li><li>Bob choice<br>Bob choses a random bit <em>t∈ {0,1}</em> and computes number <em>v , </em>so <em>v·(-1)^t = b</em></li><li>Oblivious Transfer<br>Bob securely retrieves exactly one of the masked values:<br><strong><em>·</em></strong><em> </em>If t=0, Bob receives <em>δ-a<br></em><strong><em>·</em></strong><em> </em>If t=1, Bob receives <em>δ+a</em></li><li>Final Shares Computation<br><em> </em><strong><em>·</em></strong><em> </em>Bob’s share <em>s2 = v </em><strong><em>· (</em></strong><em>δ ± a)<br></em><strong><em>·</em></strong><em> </em>Alice’s share <em>s1 = -δ </em><strong><em>·</em></strong><em> v</em></li></ol><h4>Why It’s Secure</h4><p>MtA inherits the security properties directly from Oblivious Transfer:</p><ul><li><strong>Sender’s Privacy:<br></strong>Bob retrieves exactly one masked value. Without knowing <em>δ</em>, he learns nothing about Alice’s secret <em>a</em>.</li><li><strong>Receiver’s Privacy:<br></strong>Alice doesn’t learn the choice bit <em>t</em>, nor Bob’s value <em>b</em>. She sees only <em>v</em>, which alone reveals no sensitive information about Bob’s input.</li></ul><p>MtA elegantly converts a multiplicative operation into additive secret shares, making it a cornerstone of secure computation systems like threshold ECDSA and other advanced cryptographic protocols.</p><h4>Final Thoughts</h4><p>MtA demonstrates how subtle but powerful cryptographic protocols can provide privacy and correctness simultaneously. By combining clever masking techniques with the strength of Oblivious Transfer, MtA allows secure multiplications, further unlocking the potential of secure multi-party computations.</p><p>In the next article, we’ll delve one more MPC protocol, built on top of MtA which is used in well known zkTLS.</p><ol><li>Simple implementation: <a href="https://gist.github.com/tarassh/38553c0d51787fff0ee9b506facf07ae">https://gist.github.com/tarassh/38553c0d51787fff0ee9b506facf07ae</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=152e68aa539b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Multi-Party Computations: Oblivious Transfer]]></title>
            <link>https://medium.com/@cryptofairy/multi-party-computations-oblivious-transfer-81efb872c8eb?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/81efb872c8eb</guid>
            <category><![CDATA[oblivious-transfer]]></category>
            <category><![CDATA[mpc]]></category>
            <category><![CDATA[privacy]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Sun, 13 Jul 2025 21:19:29 GMT</pubDate>
            <atom:updated>2025-07-13T21:19:29.031Z</atom:updated>
            <content:encoded><![CDATA[<p>In the age of privacy-preserving computation, <strong>Multi-Party Computation (MPC)</strong> has emerged as one of the most powerful tools for enabling secure collaboration without exposing sensitive data. MPC allows multiple participants — each holding private inputs — to jointly compute a function over their combined data, <em>without revealing their individual inputs to each other</em>. The result? A mathematically secure protocol that outputs the correct result while preserving complete input confidentiality.</p><p>Whether it’s secure auctions, trusted setup ceremonies, or blockchain applications like threshold signatures, MPC offers a way to trust the computation <em>without trusting the participants</em>.</p><p>At its core, MPC relies on several fundamental cryptographic building blocks. In this article and the following, we’ll explore three key primitives — <strong>Oblivious Transfer (OT)</strong>, <strong>Multiplicative-to-Additive (MtA) Conversion</strong>, and <strong>Elliptic Curve Point Addition</strong> — along with a practical application. This application is part of a larger protocol, which we’ll dive into in the final article.</p><p><strong><em>Oblivious Transfer (OT)</em></strong><em> is a cryptographic protocol where a sender has multiple pieces of information, and the receiver chooses one to receive — </em>without the sender knowing which one was chosen<em>, and </em>without the receiver learning anything about the others<em>. It’s a fundamental building block for secure multi-party computation.</em></p><p>Let’s build up the protocol from simple concepts.</p><h4>Encryption-Decryption Key</h4><p>For two parties to communicate securely, they must establish a secure channel that uses encryption. In this example, we’ll use a simple XOR operation, where a shared bitmask serves as both the encryption and decryption key.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*66tvEUjyvTzXYC_tO6SeGg.png" /></figure><h4><strong>Elliptic Curve Diffie-Hellman (ECDH)</strong></h4><p>The next step is to establish a key (or mask) generation scheme that ensures both parties derive the same key securely — without the ability to cheat or influence the process. For this, we can use the well-known <strong>Elliptic Curve Diffie-Hellman (ECDH)</strong> key exchange protocol. The core idea of ECDH is that both parties independently compute the same shared elliptic curve point. This point is then hashed, and the resulting digest is used as the symmetric key for encryption and decryption.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wtHHFQpG9i9OD-hPehffrQ.png" /></figure><p>This diagram illustrates how two parties can securely agree on a shared secret using ECDH:</p><ol><li>Each party picks a private random scalar, <em>a</em> and <em>b</em></li><li>Alice computes <em>A</em> point, Bob computes <em>B</em> point and exchange those</li><li>Now both can independently compute shared point <em>S</em>: scalar multiplication is commutative (<em>a</em>·<em>b</em>·<em>G</em> == <em>b</em>·<em>a</em>·<em>G</em>)</li></ol><p>4. Hash shared point <em>S</em> with same hashing algorithm to get same key.</p><h4><strong>Oblivious Transfer (OT)</strong></h4><p>Now we can begin building the <strong>Oblivious Transfer (OT)</strong> protocol by combining two core components:</p><ul><li>XOR for encrypting and decrypting data, and</li><li>Elliptic Curve Diffie-Hellman (ECDH) as the foundation for securely establishing encryption keys between the parties.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xm0DitUbct3-pdGCJGSzXg.png" /></figure><p>Alice (the sender) has two messages: <em>m₀</em> and <em>m₁</em>. Bob (the receiver) wants to learn only one of them, determined by his choice bit <em>b ∈ {0,1}</em>.</p><p>At the end of the protocol, Bob will learn only <em>m_b</em>, and Alice will have no knowledge of which message was chosen.</p><p>The first step follows the standard Elliptic Curve Diffie-Hellman (ECDH) flow: <strong>Alice</strong> selects a random scalar a and computes the elliptic curve point <em>A = a·G</em>. She then sends this point A to <strong>Bob</strong>.</p><p>Now, <strong>Bob’s</strong> behavior diverges from the classic ECDH protocol. Based on his <strong>choice bit</strong> <em>b ∈ {0, 1}</em>, he computes the point B differently:</p><ul><li>If <em>b = 0</em> (Bob wants to receive message <em>m₀</em>): <em>B = b·G</em></li><li>If <em>b = 1</em> (Bob wants message <em>m₁</em>): <em>B = b·G + A</em></li></ul><p>This choice-dependent point <em>B </em>is then sent back to Alice.</p><p>The way <em>B </em>is constructed ensures that Alice <strong>cannot tell</strong> which path Bob took, keeping his choice hidden.</p><p>Now, <strong>Alice</strong>, without knowing how B was constructed or which message Bob is interested in, proceeds to derive two separate encryption keys — one for each message m₀ and m₁:</p><ul><li>For <em>m₀</em>. She computes the shared point <em>S₀ = a·B</em> and derives the mask:<br><em>mask₀ = H(S₀)</em></li><li>For <em>m₁</em>. She computes <em>S₁ = a·(B - A)</em> and derives:<br><em>mask₁ = H(S₁)</em></li></ul><p>Using these masks, Alice encrypts both messages with XOR:</p><pre>ciphertext₀ = m₀ ⊕ mask₀  <br>ciphertext₁ = m₁ ⊕ mask₁</pre><p>She then sends both <em>ciphertexts</em> to <strong>Bob</strong>, who — based on his initial choice of bit <em>b</em> — can compute the correct shared point and recover <strong>only one</strong> of the messages using <em>mask = H(S = b·A)</em>. The other remains inaccessible to him.</p><p><strong>What would happen if this step were identical to standard ECDH? <br></strong>The answer is: Bob could eventually learn <strong>both messages</strong>, which breaks the core security goal of Oblivious Transfer. In OT, Bob should learn <strong>only one message</strong>, and <strong>Alice should not know which one</strong> was chosen.</p><p>By introducing two different ways for Bob to compute the point B based on his choice bit, the protocol ensures that Alice must encrypt the two messages using <strong>two distinct shared secrets</strong> (<em>S₀</em> and <em>S₁</em>). This enforces that Bob can derive and decrypt <strong>only one of them</strong>, depending on his selected path.</p><p><strong>If Bob always uses the same decryption formula b·A = a·b·G, how does the protocol enforce security?<br></strong>The answer lies in how <strong>Alice adapts her computation</strong> based on the structure of B that Bob sends. This design ensures that the shared secret <em>a·b·G</em> is consistently derived — regardless of Bob’s choice bit — but in a way that keeps that choice hidden from Alice:</p><ul><li>If choice = 0:<br>Bob sends <em>B = b·G</em><br>→ Bob computes <em>b·A = a·b·G</em><br>→ Alice computes <em>a·B = a·b·G</em></li><li>If <strong>choice = 1</strong>:<br>Bob sends <em>B = b·G + A</em><br>→ Bob still computes <em>b·A = a·b·G</em><br>→ Alice computes <em>a·(B — A) = a·((b·G + A) — A) = a·b·G</em></li></ul><p>In both scenarios, Bob always uses the same decryption path (b·A), while Alice switches her encryption path depending on the form of B. This symmetry guarantees that Bob can decrypt <strong>only one message</strong>, and Alice cannot tell which one it was.</p><h3>Conclusion</h3><p>In this article, we’ve successfully built up and explored the <strong>Oblivious Transfer (OT)</strong> protocol, starting from simple encryption using XOR, progressing through secure key exchange with <strong>Elliptic Curve Diffie-Hellman (ECDH)</strong>, and finally combining both to achieve a privacy-preserving OT mechanism.</p><p>We demonstrated how OT allows a receiver to securely obtain one of two messages without revealing their choice — and without learning anything about the other message — ensuring strong privacy guarantees for both parties.</p><p>In the <strong>next article</strong>, we’ll dive into the next foundational building block of secure multi-party computation: <strong>Multiplicative-to-Additive (MtA) conversion</strong>, a powerful technique for transforming multiplicative secrets into additive shares — a key component for secure arithmetic over encrypted data.</p><p>Stay tuned!</p><h4>References</h4><p>OT paper: <a href="https://eprint.iacr.org/2015/267.pdf">https://eprint.iacr.org/2015/267.pdf</a></p><p>Simple Implementation: <a href="https://gist.github.com/tarassh/43aec62ad64e73f574d131cef2e92b10">https://gist.github.com/tarassh/43aec62ad64e73f574d131cef2e92b10</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=81efb872c8eb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sangria: A PLONK-ish folding scheme]]></title>
            <link>https://medium.com/@cryptofairy/sangria-a-plonk-ish-folding-scheme-2271204d2285?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/2271204d2285</guid>
            <category><![CDATA[plonk]]></category>
            <category><![CDATA[sangria]]></category>
            <category><![CDATA[zkp]]></category>
            <category><![CDATA[folding-schemes]]></category>
            <category><![CDATA[zksnark]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Tue, 13 Feb 2024 23:08:25 GMT</pubDate>
            <atom:updated>2024-02-13T23:08:25.305Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qHthKLFJQpcbB42OIaBfEA.png" /></figure><p>Folding schemes are optimization techniques used by Zero Knowledge Proofs. They target two main areas: memory usage and proof generation time reduction in zkVMs (Zero Knowledge Virtual Machines) and recursive computations, also known as Incrementally Verifiable Computation (IVC). Understanding and addressing these in the context of VMs can be quite complex for someone encountering this topic for the first time. Therefore, in this article, we will focus more on the folding scheme outside of zkVMs before delving into VM-specifics.</p><p>In ZKPs, we can divide the prover’s execution into two phases: “pre-proof” and proof generation. The “pre-proof” phase is the period where all the necessary data is gathered (witness vectors, public inputs, etc.). This is when the actual computation takes place. After this phase, we have a state that we want to prove. The proof generation phase is where this state is “arithmetized”, converted into polynomials, so that we can generate a proof using PLONK or another protocol. Folding schemes for IVC fit between these two phases.</p><h4>How it works?</h4><p>Previously, we have identified where folding schemes fit in the proof generation cycle. Now, we will discuss what folding is and how it works.</p><p>We are already familiar with arithmetic circuits that are required to generate a proof for a given statement or computation. Consider a very primitive circuit consisting of 3 gates (two multiplication gates and one addition gate), which generates the proof for the following equation: <em>a</em>×<em>b</em>+<em>c</em>×<em>d</em>=<em>e</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/778/1*tWKo9DtqxlIbpOPuccH1tQ.png" /><figcaption>Circuit with 3 gates</figcaption></figure><p>The wiring and gate locations are fixed; the variable part here is the data (input/output parameters and intermediate results between gates). This means we can actually reuse this circuit to generate a proof for another dataset.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*y90W0x77LqF0yT1IrI952g.png" /></figure><p>So, to generate the proof for these two datasets, we would typically need to run the proof generation process twice. However, what we can do is generate one proof for both datasets. The datasets have to be “folded” into one instance: the ‘a’ variable from the first dataset is “folded” with the ‘a’ variable from the second dataset, ‘b’ with ‘b’, and so on.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9GIUNXvh6fnTjXSQc5VCEw.png" /></figure><p>Folding” two variables (<em>a</em>′ and <em>a</em>′′) in mathematics is represented as a linear combination of those variables and a random value r<em>r</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*15f0MK5rEdZ1bXMPL57jnw.png" /></figure><p>This operation is much cheaper and faster than generating proofs for those two dataset instances separately. However, folding is not without its costs; there will be an overhead, as the new proof must also account for the data folding. Despite this, the overhead is significantly less than the cost of generating two separate proofs. By applying this pattern, we can fold the following variables similarly:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/404/1*SdP4Pdwq0QCg0dD59C-Q7Q.png" /></figure><p>However, if we return to the original equation the circuit aims to prove (<em>a</em>⋅<em>b</em>+<em>c</em>⋅<em>d</em>=<em>e</em>), we encounter a problem when applying our folding technique. When substituting real numbers into the equation, it becomes clear that this approach does not work as intended:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/424/1*x7ootfJhWF3r13MYCO03_g.png" /><figcaption>Values are taken from the circuits above.</figcaption></figure><p>This demonstrates that the folding approach, as initially outlined, misses an essential element. We will address this problem later in the article. For now, we have identified where in the proving cycle folding schemes are used and how they generally work.</p><h4><strong>Why to fold?</strong></h4><p>Before delving into the technical challenges of making folding work, let’s first address a more obvious question: Why should we fold two independent dataset instances in the first place? The answer lies in the context of larger computations, where you can divide the task into smaller, reusable circuits. This concept slightly resembles what zkVMs are designed for.</p><p>Consider the need to prove a very extensive computation. There are two approaches. The first is to build a circuit specifically for generating the proof for that computation. Unfortunately, this circuit cannot be reused for other tasks. The second approach involves using a zkVM, which, besides performing computations, produces related proofs. In the first scenario, significant time must be spent to develop, compile, and test the circuit. In the second, a zkVM is powered by a set of opcodes (commands) that execute programs written in a language compiled into these opcodes. A prime example is a zkEVM, where programs written in Solidity are translated into EVM-compatible opcodes and executed on the zkEVM.</p><p>In a zkVM, each command is a separate circuit, and executing them in a specific order according to a program allows us to generate the proof. It is well understood that the larger the program, the longer it takes to execute, a principle that also applies to proof generation: the larger the state we wish to prove, the more memory and time are required to generate it. Consequently, with every new step of the program, the memory used by the prover grows, and by the end of program execution, the zkVM must generate a proof for this enormous state.</p><p>The authors of the <a href="https://eprint.iacr.org/2021/370.pdf">Nova paper</a> propose a novel approach to implementing Incrementally Verifiable Computations using a folding scheme. At a higher level, the idea is as follows: during execution time, it is more efficient to generate the proof for the folded data and, at the end of the program, generate the remaining proofs. For instance, consider a program consisting of the following opcodes executed in order: A’, C’, B’, A’’, A’’’, C’’, B’’. First, the zkVM executes an opcode A with some data and accumulates the witness data, the same happens with C and B. When the next opcode A is executed with a new dataset, we can take the witness data from the first step and fold it with the new data, accumulating the result. A similar process occurs with C and B. In the end, the zkVM needs to generate the proof only for the accumulated “folded” instances of A, B, and C. After every folding, the prover generates a proof, which is then passed to the next step where the folding proof is verified.</p><h4>Sangria</h4><p>We have now reached the discussion on the implementation of folding. Earlier, we identified that merely using a linear combination to fold two instances is insufficient, as it results in an imbalance in the equation (<em>a</em>⋅<em>b</em>+<em>c</em>⋅<em>d</em>≠<em>e</em>). We noted that a crucial piece is missing from the equation, necessitating a more sophisticated approach than previously used. In ZKP, when arithmetising statements, we construct gate constraints (algebraic equations equal to zero).</p><p>The Nova paper introduced a folding scheme to R1CS arithmetization. In this work, I decided to experiment by integrating a Plonk-like folding scheme, which is named <a href="https://github.com/geometryresearch/technical_notes/blob/main/sangria_folding_plonk.pdf">Sangria</a>, into my original implementation of the Plonk protocol.</p><p>Let’s consider folding in the context of R1CS with the following formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iWhxLjv7jgc1jbfePRVfGA.png" /><figcaption>R1CS</figcaption></figure><p>Here, <em>A</em>, <em>B</em>, and <em>C</em> are matrices acting as gate selectors, and vector w<em>w</em> is our witness vector. The multiplication between <em>A</em>×<em>w</em> and <em>B</em>×<em>w</em> represents a Hadamard product (element-wise multiplication). For more information on R1CS and their use, you can refer to my previous articles on the Groth16 protocol:</p><p><a href="https://medium.com/coinmonks/under-the-hood-of-zksnark-groth16-protocol-2843b0d1558b">Under the hood of zkSNARK Groth16 protocol (part 1)</a></p><p>This formula includes two parts: the fixed matrices <em>A</em>, <em>B</em>, and <em>C</em> that can be reused for generating specific proofs, and the witness vector <em>w</em>, the variable part. When we have two different witness vector instances <em>w</em>′ and <em>w</em>′′, folding them using a linear combination results in a witness vector that does not satisfy the R1CS equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*5WOV7JfPa2hg7AcJAuTazg.png" /></figure><p>To correct this imbalance, the authors introduced the concept of “relaxing” the equation by incorporating a “slack” or error vector <em>e</em> and a scalar value <em>u</em>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*3ehEtk-dEFqvDJF62bZsPQ.png" /><figcaption>Relaxed R1CS</figcaption></figure><p>This relaxed equation accommodates both single and folded witness instances. For a single instance, the parameters are as follows: <em>u</em>=1 and vector <em>e</em> must contain all zeros. For a folded instance, parameters <em>u</em> and <em>e</em> must be calibrated to maintain equation balance.</p><p>Returning to a relaxed PLONK arithmetization — Sangria (aptly named for the idea of having relaxed constraints, what can be more relaxing than drinking Sangria?), let’s consider the original gate constraint equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*XVRuez38x1ITq2sZE_KI6Q.png" /><figcaption>PLONK gate constraint</figcaption></figure><p>The selector polynomials, denoted as <em>q</em>, are fixed, and the polynomialsa<em>a</em>, <em>b</em>, and <em>c</em> represent our witness — the data that can be altered to generate proofs for multiple data instances. Yet, folding instances <em>a</em>, <em>b</em>, <em>c</em> using a linear combination results in an unbalanced equation, not equal to zero.</p><p>To reintroduce balance, we must incorporate a new scalar variable <em>u</em> and a “slack” or error vector encoded into a polynomial:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*6t0gayrcv_3X-fYO_1NLug.png" /></figure><h4>Code</h4><p>All my previous articles have been accompanied by working code examples, and this article is no exception. The Sangria paper focuses on constraining gates and incorporating a relaxed version into the PLONK protocol, necessitating several modifications elsewhere.</p><p>For those interested in the original implementation of the Plonk protocol, you can find the articles here:</p><p><a href="https://medium.com/coinmonks/under-the-hood-of-zksnarks-plonk-protocol-part-1-34bc406d8303">Under the hood of zkSNARKs — PLONK protocol: Part 1</a></p><p>The complete code for the relaxed PLONK protocol is available here:</p><p><a href="https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_sangria.ipynb">zkSNARK-under-the-hood/plonk_sangria.ipynb at main · tarassh/zkSNARK-under-the-hood</a></p><p>In this article, I am focusing on the main areas of modification:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MnvTc5uhW6DKuNd-EWWLUA.png" /></figure><p>We have two different witness instances, and as you can see, only the <em>a</em>, <em>b</em>, <em>c</em> parts are different; the <em>q</em> vectors remain the same. Witness vectors <em>a</em>, <em>b</em>, and <em>c</em> are encoded into polynomials and folded together using a linear combination with a random value <em>r</em>.</p><pre># witness vectors<br>a1 = [2, 2, 3, 4, 4, 8, -28]<br>b1 = [2, 2, 3, 0, 9, 36, 0]<br>c1 = [4, 4, 9, 8, 36, -28, -25]<br><br>a2 = [4, 4, 5, 16, 16, 32, -368]<br>b2 = [4, 4, 5, 0, 25, 400, 0]<br>c2 = [16, 16, 25, 32, 400, -368, -365]<br><br>_A1 = to_poly(roots, a1, Fp)<br>_B1 = to_poly(roots, b1, Fp)<br>_C1 = to_poly(roots, c1, Fp)<br><br>_A2 = to_poly(roots, a2, Fp)<br>_B2 = to_poly(roots, b2, Fp)<br>_C2 = to_poly(roots, c2, Fp)<br><br>r = Fp.Random()<br><br>_A = _A1 + r * _A2<br>_B = _B1 + r * _B2<br>_C = _C1 + r * _C2<br><br># blind polynomials<br>A = _A + bA * Zh<br>B = _B + bB * Zh<br>C = _C + bC * Zh</pre><p>Now that we understand what the folded instance is, we can calculate the <em>u</em> and <em>e</em> parameters to obtain our gate polynomial:</p><pre>def find_error_polynomial(roots, u, _a, _b, _c, _ql, _qr, _qm, _qc, _qo, field):<br>    error_vector = []<br>    for root in roots:<br>        _e = u * (_a * _ql + _b * _qr + _c * _qo) + _a * _b * _qm + u**2 * (_qc)<br>        error_vector.append(-_e(root))<br>    return to_poly(roots, field(error_vector), field=field)<br><br>mu = Fp.Random()<br><br>E = find_error_polynomial(roots, mu, _A, _B, _C, QL, QR, QM, QC, QO, Fp)<br><br># gate constraint polynomial<br># g(x) = mu[a(x)*ql(x) + b(x)*qr(x) + c(x)*qo(x)] + a(x)*b(x)*qm(x) + qpi(x) + mu^2qc(x) + e<br>G = mu * (A * QL + B * QR + C * QO) + A * B * QM + mu**2 * (QC + PI) + E</pre><p>Fortunately, the permutation part does not need any changes, so rounds 2 and 3 of the protocol do not require updates. However, rounds 4 and 5 need modifications. In round 4, we evaluate the <em>E</em> polynomial at the <em>ζ</em> (zeta) value and use it as part of the transcript:</p><pre>e_zeta = E(zeta)</pre><p>Round 5 must be updated with the <em>E</em> polynomial evaluation over the <em>ζ</em> value and the <em>u</em> parameter, and the polynomial <em>Wζ</em>​ must also contain both the <em>E</em> polynomial and its evaluation:</p><pre>R = QM * a_zeta * b_zeta + mu * (QL * a_zeta + QR * b_zeta + QO * c_zeta) + mu**2 * QC + pi_zeta + e_zeta<br><br>...<br><br>Wzeta = (<br>    R<br>    + (A - a_zeta) * v<br>    + (B - b_zeta) * v**2<br>    + (C - c_zeta) * v**3<br>    + (S1 - s1_zeta) * v**4<br>    + (S2 - s2_zeta) * v**5<br>    + (E - e_zeta) * v**6<br>)</pre><p>The verifier must be updated accordingly:</p><pre>D_exp = (<br>    qm_exp * a_zeta * b_zeta<br>    + mu*(ql_exp * a_zeta<br>    + qr_exp * b_zeta<br>    + qo_exp * c_zeta)<br>    + mu**2 * qc_exp<br>    + e_zeta<br>)</pre><pre>F_exp = (<br>    D_exp<br>    + a_exp * v<br>    + b_exp * v**2<br>    + c_exp * v**3<br>    + s1_exp * v**4<br>    + s2_exp * v**5<br>    + e_exp * v**6<br>)<br><br>... <br><br>E_exp = (<br>    -r0<br>    + v * a_zeta<br>    + v**2 * b_zeta<br>    + v**3 * c_zeta<br>    + v**4 * s1_zeta<br>    + v**5 * s2_zeta<br>    + v**6 * e_zeta<br>    + u * z_omega_zeta<br>)</pre><p>What is missing here is the notion of witness folding represented as a separate polynomial constraint. Implementing such a constraint would embed this polynomial in the same manner as the <em>E</em> polynomial across all places.</p><p><strong>References</strong>:</p><p><a href="https://github.com/geometryresearch/technical_notes/blob/main/sangria_folding_plonk.pdf">https://github.com/geometryresearch/technical_notes/blob/main/sangria_folding_plonk.pdf</a></p><p><a href="https://eprint.iacr.org/2021/370.pdf">https://eprint.iacr.org/2021/370.pdf</a></p><p><a href="https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_sangria.ipynb">https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_sangria.ipynb</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2271204d2285" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Fiat-Shamir Exploit to Attack a Plonk Verifier]]></title>
            <link>https://medium.com/@cryptofairy/fiat-shamir-exploit-to-attack-a-plonk-verifier-d8ab544e9536?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/d8ab544e9536</guid>
            <category><![CDATA[openzeppelin]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[security]]></category>
            <category><![CDATA[plonk]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Mon, 18 Dec 2023 10:46:06 GMT</pubDate>
            <atom:updated>2023-12-18T10:46:06.205Z</atom:updated>
            <content:encoded><![CDATA[<p>This experiment was inspired by a recent YouTube <a href="https://www.youtube.com/watch?v=Sk-S8-n6Jo4">publication</a> from the OpenZeppelin team titled “The Last Challenge Attack”, which focused on an incorrectly implemented Plonk verifier. I decided to investigate how challenging it would be to replicate this attack if we had such a verifier in our possession. In this article, I will delve deeply into the problem and provide a working example of the attack.</p><p>In the security report, it is stated that the vulnerability was due to an incorrect implementation of the last challenge calculation. Despite the calculation providing ‘randomness’, the implementation was still vulnerable to attack.</p><p><a href="https://github.com/Consensys/gnark/security/advisories/GHSA-7p92-x423-vwj6">Plonk verifier KZG multi point verification</a></p><p>To understand the root cause of the attack, we need to revisit the basics of the Plonk protocol. In essence, Plonk utilizes the KZG commitment scheme for proof generation and verification. Originally, KZG is designed as an interactive commitment scheme.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Em9MeHjPtmMOxmSSZA_UBQ.png" /><figcaption>KZG commitment</figcaption></figure><p>The prover sends a commitment, denoted as [P], to a verifier. The verifier then selects a random value ‘r’ and sends it to the prover, who evaluates the polynomial at ‘r’. After this evaluation, the prover sends the calculated opening, P(r), back to the verifier. Based on the provided information, the verifier can either approve or reject the proof. It is in the <strong>verifier’s own interest</strong> to choose a value ‘r’ that the prover cannot predict. For instance, if the prover can anticipate ‘r’, they can easily deceive the verifier.</p><p>Plonk is a non-interactive protocol, which means that the KZG scheme is modified to support this characteristic. Thanks to the Fiat-Shamir heuristic, the prover and verifier can agree on random values (challenges) without interaction. This agreement is achieved by hashing the transcript of the protocol. Although hashing can facilitate consensus between the prover and verifier, it’s still possible to predict the values derived from it. Therefore, the protocol must be designed with a stronger relationship between its variables. Does this sound very abstract? Let’s make it more visual.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/914/1*e7smfXZlOKhEsbZYNc_bzg.png" /></figure><p>This equation is used by the verifier to determine the validity of the proof; if it holds, then the proof is accepted. The variable denoted as ‘u’ is our point of attack. What this equation does is compare the results of two pairing functions. But for now let’s focus on ‘u’ variable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eKfIUc4KQqJbau_ueRR7Tg.png" /></figure><p>The proof generation process in Plonk involves five rounds. At the end of each round, we obtain a more detailed transcript, with values in the columns [a], [b], etc., which constitute the proof. These values are used to generate challenges. By the end of the fifth round, it is clear that ‘u’ depends on transcripts from the previous rounds as well as on [Wz] and [Wzω]. This dependency is vital; if compromised, a malicious prover could potentially create fake proofs. The reason for this vulnerability is straightforward: the verifier is a smart contract deployed on the blockchain, and its code is publicly accessible. Achieving randomness on-chain is difficult because all nodes in the network must maintain the same state, meaning that any ‘randomness’ computed on one node must be replicable on others. This issue was the focal point of the report: the challenge ‘u’ was not dependent on the last two polynomial commitments. Without this dependency, ‘u’ can be precomputed, effectively becoming a constant. This reduction in complexity makes the verification equation easier to solve, potentially compromising the system’s integrity.</p><p>Let’s revisit our original equation. Upon reviewing it again, we can see that it forms a system of equations where [Wz] and [Wzω] are the unknown variables, and everything else, including ‘u’, can be computed beforehand. This implies that we have the capability to solve this system of equations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NnfHVJio9y6ujyJxlspIVA.png" /></figure><p>Now that we have a solution, creating a fake proof simply requires modifying any values of the original proof, including the public input. After these modifications, new values for [Wz] and [Wzω] can be calculated.</p><p>Let’s proceed to code this attack. But before we delve in, one small remark is necessary: verification is conducted over elliptic curve points. For convenience, we can forego encryption and even reduce the field size, choosing instead to work directly with polynomial values. This approach will yield the same results.</p><p>Complete attack script can be found here on the github</p><p><a href="https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_attack.ipynb">zkSNARK-under-the-hood/plonk_attack.ipynb at main · tarassh/zkSNARK-under-the-hood</a></p><h4>Coding</h4><p>First, we assume we have a verifier with the weakness:</p><pre># Values provided by the prover (round 1 to 5) is a proof.<br>a_exp = round1[0]<br>b_exp = round1[1]<br>c_exp = round1[2]<br><br>z_exp = round2[0]<br><br>tl_exp = round3[0]<br>tm_exp = round3[1]<br>th_exp = round3[2]<br><br>a_zeta, b_zeta, c_zeta, s1_zeta, s2_zeta, z_omega_zeta = round4<br><br>w_zeta_exp = round5[0]<br>w_omega_zeta_exp = round5[1]<br><br>beta = numbers_to_hash(round1 + [0], Fp)<br>gamma = numbers_to_hash(round1 + [1], Fp)<br>alpha = numbers_to_hash(round1 + round2, Fp)<br>zeta = numbers_to_hash(round1 + round2 + round3, Fp)<br><br>v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)<br># We assume that verifier generates value for u not dependent on round 5<br># u = numbers_to_hash(round1 + round2 + round3 + round4 + round5, Fp)<br><br># and algorithm is predictable, but here for simplicity we just hardcode the value<br>u = Fp(2)</pre><p>Prover has to use valid proof in order to get A, and B from the equations above.</p><pre>Zh_z = Zh(zeta)<br>L1_z = L1(zeta)<br>PI_z = PI(zeta)<br><br>r0 = (<br>    PI_z<br>    - L1_z * alpha**2<br>    - (a_zeta + beta * s1_zeta + gamma)<br>    * (b_zeta + beta * s2_zeta + gamma)<br>    * (c_zeta + gamma)<br>    * z_omega_zeta<br>    * alpha<br>)<br><br>D_exp = (<br>    qm_exp * a_zeta * b_zeta<br>    + ql_exp * a_zeta<br>    + qr_exp * b_zeta<br>    + qo_exp * c_zeta<br>    + qc_exp<br>)<br><br>D_exp += z_exp * (<br>    (a_zeta + beta * zeta + gamma)<br>    * (b_zeta + beta * zeta * k1 + gamma)<br>    * (c_zeta + beta * zeta * k2 + gamma)<br>    * alpha<br>    + L1_z * alpha**2<br>    + u<br>)<br><br>D_exp -= (<br>    s3_exp<br>    * (a_zeta + beta * s1_zeta + gamma)<br>    * (b_zeta + beta * s2_zeta + gamma)<br>    * alpha<br>    * beta<br>    * z_omega_zeta<br>)<br><br>D_exp -= (tl_exp + tm_exp * zeta**n + th_exp * zeta ** (2 * n)) * Zh_z<br><br>F_exp = (<br>    D_exp<br>    + a_exp * v<br>    + b_exp * v**2<br>    + c_exp * v**3<br>    + s1_exp * v**4<br>    + s2_exp * v**5<br>)<br><br>E_exp = (<br>    -r0<br>    + v * a_zeta<br>    + v**2 * b_zeta<br>    + v**3 * c_zeta<br>    + v**4 * s1_zeta<br>    + v**5 * s2_zeta<br>    + u * z_omega_zeta<br>)<br><br><br># This is  our A<br>e1 = w_zeta_exp + w_omega_zeta_exp * u<br><br># This is our B<br>e2 = (<br>    w_zeta_exp * zeta<br>    + w_omega_zeta_exp * (u * zeta * omega)<br>    + F_exp<br>    + (E_exp * Fp(p - 1))<br>)<br></pre><p>Now we need to what values to modify. In my case I am going to change value a_zeta from the proof which is calculated in round 4.</p><pre># Malicious prover modifies the proof by a value of choice<br>a_zeta = Fp(1)<br><br># dependent values has to be recalculated<br>round4[0] = a_zeta<br>v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)</pre><p>After the value is changed we need to calculate E_expand F_exp :</p><pre>// .... same as before<br><br>F_exp = (<br>    D_exp<br>    + a_exp * v<br>    + b_exp * v**2<br>    + c_exp * v**3<br>    + s1_exp * v**4<br>    + s2_exp * v**5<br>)<br><br>E_exp = (<br>    -r0<br>    + v * a_zeta<br>    + v**2 * b_zeta<br>    + v**3 * c_zeta<br>    + v**4 * s1_zeta<br>    + v**5 * s2_zeta<br>    + u * z_omega_zeta<br>)</pre><p>Now we can calculate our new [Wz] and [Wzω]:</p><pre># Capture original solutions to the equation<br>A = e1<br>B = e2<br><br># New adjusted solutions to the equation<br>C = F_exp - E_exp<br><br># New W(ω*zeta)<br>y = (B - C - A * zeta) * (u * omega * zeta - u * zeta) ** (-1)<br><br># New W(zeta)<br>x = (A * omega * zeta - B + C) * (omega * zeta - zeta) ** (-1)<br><br># make sure they are not same as original values<br>assert w_zeta_exp != x<br>assert w_omega_zeta_exp != y<br><br>e1_new = x + y * u<br>e2_new = x * zeta + y * (u * zeta * omega) + F_exp - E_exp<br><br>assert e1_new * tau == e2_new</pre><p>And we are ready to create forged proof:</p><pre>proof = {<br>    &quot;A&quot;: round1[0],<br>    &quot;B&quot;: round1[1],<br>    &quot;C&quot;: round1[2],<br>    &quot;Z&quot;: round2[0],<br>    &quot;Tl&quot;: round3[0],<br>    &quot;Tm&quot;: round3[1],<br>    &quot;Th&quot;: round3[2],<br>    &quot;Wzeta&quot;: x,<br>    &quot;Womega_zeta&quot;: y,<br>    &quot;a_zeta&quot;: a_zeta,<br>    &quot;b_zeta&quot;: round4[1],<br>    &quot;c_zeta&quot;: round4[2],<br>    &quot;s1_zeta&quot;: round4[3],<br>    &quot;s2_zeta&quot;: round4[4],<br>    &quot;z_omega_zeta&quot;: round4[5],<br>}</pre><p>Credit to the OpenZeppelin team for this insightful report. It serves as a fascinating showcase that has helped me understand how zk (zero-knowledge) protocols are constructed and balanced with security considerations.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d8ab544e9536" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Exploring Vulnerabilities: The zkSNARK Malleability Attack on the Groth16 Protocol]]></title>
            <link>https://medium.com/@cryptofairy/exploring-vulnerabilities-the-zksnark-malleability-attack-on-the-groth16-protocol-8c80d13751c5?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/8c80d13751c5</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zkp]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[security]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Tue, 05 Dec 2023 18:03:28 GMT</pubDate>
            <atom:updated>2023-12-05T18:03:28.898Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZL3Ym8m-aOu5STwv9yYUbg.png" /></figure><p>The recent recognition of zero-knowledge proofs (ZKPs) has garnered attention from a broader audience, including many non-technical individuals. However, this increased awareness can sometimes lead to the misconception that ZKPs are inherently secure simply because they are based on cryptographic principles. It’s important to understand that these protocols are designed by humans and may contain implementation flaws or even intentional backdoors, which can be exploited. Even the most advanced protocols might have vulnerabilities. Using such technologies blindly, without being aware of their potential weaknesses, can lead to real and tangible harm. In this article, we will explore the simplest and fastest method of executing a malleability attack on the Groth16 protocol.</p><p>The concept is relatively straightforward: an attacker can generate a new proof from an existing one without needing access to the proving key or private data. The verifier will then consider this newly created proof to be valid.</p><p>The first question that arises is: how can an attacker gain access to the proof? The answer is fairly straightforward. By their very nature, proofs are considered public and accessible to everyone. In the context of blockchain technology, to validate an event that occurred off-chain, we must provide the proof to a verifier. Typically, this verifier is a smart contract deployed on the blockchain. Since all activities on the chain are public, the proofs are readily accessible.</p><p>One of the simplest examples of this vulnerability can be seen in an airdrop contract, where a user must provide proof to claim tokens. Even if the contract subsequently stores the proof or its hash to prevent the same proof from being used again, this malleability issue could still allow a user to claim tokens twice.</p><p>For those who are not familiar with Groth16 protocol you can read the following series of articles with a deep dive into protocol implementation:</p><p><a href="https://medium.com/coinmonks/under-the-hood-of-zksnark-groth16-protocol-2843b0d1558b">Under the hood of zkSNARK Groth16 protocol (part 1)</a></p><p>Now, let’s examine where the vulnerability lies. Consider the following verification formula from the protocol:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/992/1*pCzxjoqaiD7EVOqjQbmlgA.png" /></figure><p>In this formula, A, B, and C are elliptic curve points provided by the prover as part of the proof. Almost everything else (except for the public input) forms part of the verifier key, which is usually embedded into a smart contract and deployed on the blockchain. Therefore, our attack will revolve around modifying the A, B, and C points. There are several ways to modify a proof, as detailed here:</p><p><a href="https://www.beosin.com/resources/beosin%E2%80%99s-research--transaction-malleability-attack-of-groth?lang=en-US">Beosin&#39;s Research | Transaction Malleability Attack of Groth16 Proof</a></p><p>However, there is a simpler method, which we will explore in this article. First, let’s examine the C point. We observe that it interacts with the verifier key through a pairing function (here represented as a dot). Modifying the C point will likely create an imbalance in the entire equation, necessitating potential adjustments to the A and B points. This approach, however, appears to be complex.</p><p>Fortunately, A and B are positioned on the opposite side of the formula. This suggests that we can find a valid solution by modifying only A and B, thereby maintaining the validity of the entire equation.</p><p>On Ethereum and other EVM-compatible chains, there is a precompiled contract at address 0x8 responsible for the verification of this formula. However, to utilize it, we need to slightly modify the formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9yZjDDClG__doCNd6tFFZg.png" /></figure><p>Precompiled contracts aggregate all the pairings between points, and the sum should equal zero, indicating that the proof is correct. You may notice that we had to move the pairing of A and B to the right side of the equation. Consequently, we also need to change the sign of point A to maintain the balance in the equation.</p><p>To simplify the concept of elliptic curve pairing, you can think of it as a ‘multiplication’ operation between points. The result might not be what you typically expect from multiplication, but in general, pairing retains some basic properties similar to multiplication. For instance, (−<em>a</em>)×<em>b</em>=<em>a</em>×(−<em>b</em>). This property is exactly what we need to utilize.</p><p>From the image below, we can observe that R is a point on the elliptic curve, and the opposite point, denoted as -R, is essentially the point R flipped over the y-axis.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*RhHLW4Anw0Q5aJhDcjkDgA.png" /></figure><p>I believe the path forward is quite straightforward from here. We simply need to flip the y-coordinate for points A and B, and as a result, the pairing outcome should remain identical.</p><p>Here I have deployed very trivial contract which emulates this attack so every on can check it.</p><p><a href="https://mumbai.polygonscan.com/address/0xca8ef9d16371be9b82bf9fb6a10ba687bee85e3d#code">MalleableProof | Address 0xca8ef9d16371be9b82bf9fb6a10ba687bee85e3d | PolygonScan</a></p><p>And here we have the code:</p><pre>// SPDX-License-Identifier: GPL-3.0<br>pragma solidity ^0.8.13;<br><br>contract MalleableProof {<br>    Groth16Verifier public verifier;<br><br>    uint256 constant q =<br>        21888242871839275222246405745257275088696311157297823662689037894645226208583;<br><br>    uint256[2] pA = [<br>        0x043dda925746db6abbc4a47f307c89fc64095025b0404f231e5a25b7d99f142f,<br>        0x27cd7c96181a03be504ec161b1fc3f68678ed1c4b7ea2e6347447d7df01f198c<br>    ];<br>    uint256[2][2] pB = [<br>        [<br>            0x010cd93d727ed43d29b02d8abb33b6c535ce4e9d76abeba8a017edab2c578697,<br>            0x08fb3dd1336516c8eb3451cc40047ae22ea75a8a39e5a25353b058f815f4ee27<br>        ],<br>        [<br>            0x0927c4e2813c2446764cd5ccbe0e9a71d05d8dfcb1b88024ab987882815e8e3a,<br>            0x188dee86bd4ff36704ff3d8ce1ce5cc79c024feb3d212d9a6d0026bf7e9c6394<br>        ]<br>    ];<br>    uint256[2] pC = [<br>        0x23f2b9fbb1af6b96e377e8ed3083f0815a6b013461bceee665bde037e22b87b8,<br>        0x1bcf05d9624319e7373ed846cfff7f5f7e6b8d2cc8b4860c8e11c3e91c1019ad<br>    ];<br>    uint256[1] pubSignals = [<br>        uint256(<br>            0x000000000000000000000000000000000000000000000000000000000000005c<br>        )<br>    ];<br><br>    constructor() {<br>        verifier = new Groth16Verifier();<br>    }<br><br>    function negate(uint256[2] memory point) internal pure returns (uint256[2] memory) {<br>        return [point[0], uint256(q - (point[1] % q))];<br>    }<br><br>    function negate(uint256[2][2] memory points) internal pure returns (uint256[2][2] memory) {<br>        return [[points[0][0], points[0][1]], [uint256(q - points[1][0] % q), uint256(q - (points[1][1] % q))]];<br>    }<br><br>    function test() public view returns(bool) {<br>        uint256[2] memory pA_neg = negate(pA);<br>        uint256[2][2] memory pB_neg = negate(pB);<br><br>        bytes32 originalProofHash = keccak256(abi.encodePacked(pA[0], pA[1], pB[0][0], pB[0][1], pB[1][0], pB[1][1], pC[0], pC[1], pubSignals[0]));<br>        bytes32 malleableProofHash = keccak256(abi.encodePacked(pA_neg[0], pA_neg[1], pB_neg[0][0], pB_neg[0][1], pB_neg[1][0], pB_neg[1][1], pC[0], pC[1], pubSignals[0]));<br><br>        require(originalProofHash != malleableProofHash, &quot;proofs are equal&quot;);<br><br>        require(verifier.verifyProof(pA, pB, pC, pubSignals), &quot;original proof failed&quot;);<br>        require(verifier.verifyProof(pA_neg, pB_neg, pC, pubSignals), &quot;malleable proof failed&quot;);<br><br>        return true;<br>    }<br>}<br><br>contract Groth16Verifier {<br>    // Scalar field size<br>    uint256 constant r =<br>        21888242871839275222246405745257275088548364400416034343698204186575808495617;<br>    // Base field size<br>    uint256 constant q =<br>        21888242871839275222246405745257275088696311157297823662689037894645226208583;<br><br>    // Verification Key data<br>    uint256 constant alphax =<br>        11902296347347039061914403575092544846359038134537957629176655874298370699911;<br>    uint256 constant alphay =<br>        3391855710907380668233433519135265813497031220290585864635015352649111711184;<br>    uint256 constant betax1 =<br>        16784052509360644757629301015206259316198090538012176085893013905461802331831;<br>    uint256 constant betax2 =<br>        12553085197744738873343062641154648040227321273919470712379455912841029058108;<br>    uint256 constant betay1 =<br>        19432553154467640750076643403468969701277919142567543087647109772606325611215;<br>    uint256 constant betay2 =<br>        10009875844390438955602042708425754795331778042892155353502209313012220600786;<br>    uint256 constant gammax1 =<br>        11559732032986387107991004021392285783925812861821192530917403151452391805634;<br>    uint256 constant gammax2 =<br>        10857046999023057135944570762232829481370756359578518086990519993285655852781;<br>    uint256 constant gammay1 =<br>        4082367875863433681332203403145435568316851327593401208105741076214120093531;<br>    uint256 constant gammay2 =<br>        8495653923123431417604973247489272438418190587263600148770280649306958101930;<br>    uint256 constant deltax1 =<br>        1899311077018330499661076917249789522364858944299631094464619341448064208677;<br>    uint256 constant deltax2 =<br>        2940006217620028071483555626688027143173059468880178649085394490329969301309;<br>    uint256 constant deltay1 =<br>        9341687543023852914223671728476937889999092849725638929381204194633096037884;<br>    uint256 constant deltay2 =<br>        17862496793411495277768192323260065881295964168547115804420567672808037688434;<br><br>    uint256 constant IC0x =<br>        17400396001955266182761672048518979776362947284593388197557812120968484015363;<br>    uint256 constant IC0y =<br>        7077915839858152427525208697187383436168898719005308255598939504725845408697;<br><br>    uint256 constant IC1x =<br>        14504255466195739587178955895060518312474127917266890870496962379534421099402;<br>    uint256 constant IC1y =<br>        17537483151726991648505521566767322181363618458103336910347616663390669720764;<br><br>    // Memory data<br>    uint16 constant pVk = 0;<br>    uint16 constant pPairing = 128;<br><br>    uint16 constant pLastMem = 896;<br><br>    function verifyProof(<br>        uint[2] calldata _pA,<br>        uint[2][2] calldata _pB,<br>        uint[2] calldata _pC,<br>        uint[1] calldata _pubSignals<br>    ) public view returns (bool) {<br>        assembly {<br>            function checkField(v) {<br>                if iszero(lt(v, q)) {<br>                    mstore(0, 0)<br>                    return(0, 0x20)<br>                }<br>            }<br><br>            // G1 function to multiply a G1 value(x,y) to value in an address<br>            function g1_mulAccC(pR, x, y, s) {<br>                let success<br>                let mIn := mload(0x40)<br>                mstore(mIn, x)<br>                mstore(add(mIn, 32), y)<br>                mstore(add(mIn, 64), s)<br><br>                success := staticcall(sub(gas(), 2000), 7, mIn, 96, mIn, 64)<br><br>                if iszero(success) {<br>                    mstore(0, 0)<br>                    return(0, 0x20)<br>                }<br><br>                mstore(add(mIn, 64), mload(pR))<br>                mstore(add(mIn, 96), mload(add(pR, 32)))<br><br>                success := staticcall(sub(gas(), 2000), 6, mIn, 128, pR, 64)<br><br>                if iszero(success) {<br>                    mstore(0, 0)<br>                    return(0, 0x20)<br>                }<br>            }<br><br>            function checkPairing(pA, pB, pC, pubSignals, pMem) -&gt; isOk {<br>                let _pPairing := add(pMem, pPairing)<br>                let _pVk := add(pMem, pVk)<br><br>                mstore(_pVk, IC0x)<br>                mstore(add(_pVk, 32), IC0y)<br><br>                // Compute the linear combination vk_x<br><br>                g1_mulAccC(_pVk, IC1x, IC1y, calldataload(add(pubSignals, 0)))<br><br>                // -A<br>                mstore(_pPairing, calldataload(pA))<br>                mstore(<br>                    add(_pPairing, 32),<br>                    mod(sub(q, calldataload(add(pA, 32))), q)<br>                )<br><br>                // B<br>                mstore(add(_pPairing, 64), calldataload(pB))<br>                mstore(add(_pPairing, 96), calldataload(add(pB, 32)))<br>                mstore(add(_pPairing, 128), calldataload(add(pB, 64)))<br>                mstore(add(_pPairing, 160), calldataload(add(pB, 96)))<br><br>                // alpha1<br>                mstore(add(_pPairing, 192), alphax)<br>                mstore(add(_pPairing, 224), alphay)<br><br>                // beta2<br>                mstore(add(_pPairing, 256), betax1)<br>                mstore(add(_pPairing, 288), betax2)<br>                mstore(add(_pPairing, 320), betay1)<br>                mstore(add(_pPairing, 352), betay2)<br><br>                // vk_x<br>                mstore(add(_pPairing, 384), mload(add(pMem, pVk)))<br>                mstore(add(_pPairing, 416), mload(add(pMem, add(pVk, 32))))<br><br>                // gamma2<br>                mstore(add(_pPairing, 448), gammax1)<br>                mstore(add(_pPairing, 480), gammax2)<br>                mstore(add(_pPairing, 512), gammay1)<br>                mstore(add(_pPairing, 544), gammay2)<br><br>                // C<br>                mstore(add(_pPairing, 576), calldataload(pC))<br>                mstore(add(_pPairing, 608), calldataload(add(pC, 32)))<br><br>                // delta2<br>                mstore(add(_pPairing, 640), deltax1)<br>                mstore(add(_pPairing, 672), deltax2)<br>                mstore(add(_pPairing, 704), deltay1)<br>                mstore(add(_pPairing, 736), deltay2)<br><br>                let success := staticcall(<br>                    sub(gas(), 2000),<br>                    8,<br>                    _pPairing,<br>                    768,<br>                    _pPairing,<br>                    0x20<br>                )<br><br>                isOk := and(success, mload(_pPairing))<br>            }<br><br>            let pMem := mload(0x40)<br>            mstore(0x40, add(pMem, pLastMem))<br><br>            // Validate that all evaluations ∈ F<br><br>            checkField(calldataload(add(_pubSignals, 0)))<br><br>            checkField(calldataload(add(_pubSignals, 32)))<br><br>            // Validate all evaluations<br>            let isValid := checkPairing(_pA, _pB, _pC, _pubSignals, pMem)<br><br>            mstore(0, isValid)<br>            return(0, 0x20)<br>        }<br>    }<br>}</pre><p>The code comprises two contracts: <strong>MalleableProof</strong> and <strong>Groth16Verifier</strong> (the latter is generated by Circom). <strong>MalleableProof</strong> utilizes the Groth16 verifier to check the proof. In this specific example, the proof is embedded within the contract, but in a real-world scenario, the proof would typically be supplied with the transaction.</p><pre>function test() public view returns(bool) {<br>      uint256[2] memory pA_neg = negate(pA);<br>      uint256[2][2] memory pB_neg = negate(pB);<br><br>      bytes32 originalProofHash = keccak256(abi.encodePacked(pA[0], pA[1], pB[0][0], pB[0][1], pB[1][0], pB[1][1], pC[0], pC[1], pubSignals[0]));<br>      bytes32 malleableProofHash = keccak256(abi.encodePacked(pA_neg[0], pA_neg[1], pB_neg[0][0], pB_neg[0][1], pB_neg[1][0], pB_neg[1][1], pC[0], pC[1], pubSignals[0]));<br><br>      require(originalProofHash != malleableProofHash, &quot;proofs are equal&quot;);<br><br>      require(verifier.verifyProof(pA, pB, pC, pubSignals), &quot;original proof failed&quot;);<br>      require(verifier.verifyProof(pA_neg, pB_neg, pC, pubSignals), &quot;malleable proof failed&quot;);<br><br>      return true;<br>  }</pre><p>The test() function essentially performs all the necessary checks for both the valid proof and the forged proof. Additionally, it ensures that the forged proof is not identical to the original. So, what does this all imply? An attacker can take a proof from the network, flip the y-coordinates for points A and B, and then submit it as a valid proof.</p><p>To prevent this behavior, there are several measures we can take: adding a signature to the proof, employing nullifiers, among other strategies. However, these solutions are beyond the scope of this article.</p><p>This simple example demonstrates that using ZKPs without fully understanding their limitations can lead to significant complications.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8c80d13751c5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Under the hood of zkSNARKs — PLONK protocol: part 6]]></title>
            <link>https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-6-5a030d15be68?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/5a030d15be68</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zkp]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[plonk]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Wed, 22 Nov 2023 12:16:15 GMT</pubDate>
            <atom:updated>2023-12-17T10:33:52.060Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1EEFOLYL-EE3bGj0mTeMtA.png" /></figure><h3>Under the hood of zkSNARKs — PLONK protocol: part 6</h3><p>Final article in PLONK series. Here we will implement Prover and the Verifier. In the previous article we coded trusted setup, gate and permutations polynomials, now we are ready to start generating proof.</p><p><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-5-4819dd56d3f1">Under the hood of zkSNARKs — PLONK protocol: part 5</a></p><h4>The Prover</h4><p>In the PLONK protocol, the prover is required to complete five rounds in a specified order. This process results in the creation of a proof comprising 9 Elliptic Curve Points and 6 Finite Field values.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AKhVZ2zppnI93rPzC0ymsw.png" /></figure><p>Final implementations also can be found here:</p><p><a href="https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_latest.ipynb">zkSNARK-under-the-hood/plonk_latest.ipynb at main · tarassh/zkSNARK-under-the-hood</a></p><h4>Round 1</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ov5oGoFQeYYfcqMs4UQjAw.png" /></figure><p>In Round 1, we need to compute wire polynomials, using the same technique employed for gate polynomials in the previous article. This technique involves converting vectors into polynomials via Lagrange interpolation. Additionally, it’s necessary to ‘blind’ the wire polynomials. For each of a, b, and c, we must generate blinding polynomials (such as b1x + b2, etc.). The use of blinding polynomials is based on a straightforward rationale. We utilize the KZG commitment scheme at the core, where each polynomial’s evaluation at a random value zeta reveals some information about the polynomial, contradicting the principles of zero-knowledge proofs. Hence, for our newly generated polynomials, we incorporate these blinding polynomials. Blinding polynomials are multiplied by the Vanishing polynomial <em>Zh</em> to generate correct polynomial commitments [a], [b], and [c]. Since evaluations occur over the roots of unity, <em>Zh</em> yields 0, making the blinding factor negligible. However, when the polynomials are evaluated at the random value zeta in round 4, the blinding polynomials will significantly affect the results.</p><pre>random_b = [Fp.Random() for i in range(0, 9)]<br><br># blinding polynomials<br>bA = galois.Poly(random_b[:2], field=Fp)<br>bB = galois.Poly(random_b[2:4], field=Fp)<br>bC = galois.Poly(random_b[4:6], field=Fp)<br><br># wire polynomials<br>_A = to_poly(roots, a, Fp)<br>_B = to_poly(roots, b, Fp)<br>_C = to_poly(roots, c, Fp)<br><br># Wire polynomials with blinding factor<br>A = _A + bA*Zh<br>B = _B + bB*Zh<br>C = _C + bC*Zh<br><br># gate constraints polynomial<br># g(x) = a(x)*ql(x) + b(x)*qr(x) + a(x)*b(x)*qm(x) + qc(x) + c(x)*qo(x)<br>G = A*QL + B*QR + A*B*QM + QC + C*QO<br><br>for i in range(0, len(roots)):<br>    assert G(roots[i]) == 0, f&quot;G({roots[i]}) != 0&quot;<br><br>assert G % Zh == 0, f&quot;G(x) % Zh(x) != 0&quot;<br><br># commitments [a], [b], [c]<br>round1 = [A(tau), B(tau), C(tau)]</pre><p><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part3-821855e49ce6">In Part 3</a>, we discussed how to constrain gate polynomials, so the introduction of polynomial G should not be surprising to the reader. Instead of sending a commitment to G, we transmit three commitments because the Q polynomials are also known to the verifier, enabling them to easily reconstruct the commitment to G. Also, G polynomial used to verify if it is constrained correctly — it should equal zero at all roots of unity, indicating that it can be divided by Zh without a remainder. If this assertion fails, it implies that there was an error in the construction of the polynomial.</p><h4>Round 2</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YGorRZIhiCq1dyFZgZX6WA.png" /></figure><p>Beta (β) and gamma (γ) are the first random values generated from a transcript in Round 1 ([a], [b], [c]). <a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-5-4819dd56d3f1">In Part 5</a>, I mentioned the Fiat-Shamir heuristic as a mechanism for obtaining random values. <a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part4-5e74bddebedb">Part 4</a> is dedicated entirely to the permutation polynomial z(x). The blinding polynomials in this context serve the same purpose as they did in Round 1.</p><pre><br>beta = numbers_to_hash(round1 + [0], Fp)<br>gamma = numbers_to_hash(round1 + [1], Fp)<br><br>_F = (A + I1 * beta + gamma) * (B + I2 * beta + gamma) * (C + I3 * beta + gamma)<br>_G = (A + S1 * beta + gamma) * (B + S2 * beta + gamma) * (C + S3 * beta + gamma)<br><br>acc_eval = [Fp(1)]<br>for i in range(0, n):<br>    acc_eval.append(<br>        acc_eval[-1] * (_F(roots[i]) / _G(roots[i]))<br>    )<br>assert acc_eval.pop() == Fp(1)<br>ACC = galois.lagrange_poly(roots, Fp(acc_eval))<br><br>bZ = galois.Poly(random_b[6:9], field=Fp)<br>Z = bZ * Zh + ACC<br><br>assert Z(roots[0]) == 1<br>assert Z(roots[-1]) == 1<br><br>round2 = [Z(tau)]</pre><h4>Round 3</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kQeXSIQtQe_tSBxjKX7xeA.png" /></figure><p>In Round 3, we encounter a substantial computational phase. The primary task involves calculating the polynomial t(x), pivotal for proving the entire statement. Let’s break this down:</p><ul><li>The first line involves the polynomial G from Round 1, divided by Zh(x) — the vanishing polynomials. This division aims to demonstrate that G equals 0 at every evaluation point (roots of unity). Therefore, if G(x)/Zh(x) divides without remainder, it indicates that the prover can provide a correct polynomial commitment for G.</li><li>Line #4, featuring L1(x), equals 1 for the first element in the roots of unity and 0 for the others. The permutation check formula, detailed in <a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part4-5e74bddebedb">Part 4</a>, begins from acc0=1. This necessitates addressing it in the t(x) polynomial.</li><li>The two middle polynomials can be simplified to f’(X)z(X) — g’(X)z(ωX) = 0 or, equivalently, f’(X)z(X) = g’(X)z(ωX). This simplification is to validate that the permutations are correct.</li><li>The role of the α value is crucial. Instead of proving that multiple different polynomials are zero at the roots of unity, the protocol combines them as linearly independent terms. This allows their validation together for all these polynomials, as elaborated in <a href="https://medium.com/coinmonks/under-the-hood-of-zksnarks-plonk-protocol-part-1-34bc406d8303">Part 1</a>.</li><li>Splitting the t(X) polynomial into three parts is a protocol trade-off. To calculate the commitment to t(X), the prover would typically require more time compared to other polynomials due to its higher degree. Additionally, this also necessitates a larger size for the trusted setup.</li></ul><pre>def shift_poly(poly: galois.Poly, omega: Fp):<br>    coeffs = poly.coeffs[::-1]<br>    coeffs = [c * omega**i for i, c in enumerate(coeffs)]<br>    return galois.Poly(coeffs[::-1], field=poly.field)<br><br>alpha = numbers_to_hash(round1 + round2, Fp)<br><br>Zomega = shift_poly(Z, omega=omega)<br><br>L1 = galois.lagrange_poly(roots, Fp([1] + [Fp(0)] * (n - 1)))<br><br>for i, r in enumerate(roots):<br>    # make sure L1 equal 1 at root[0] and 0 for the rest<br>    assert L1(r) == (Fp(1) if i == 0 else Fp(0))<br><br>T0 = G<br>assert T0 % Zh == 0, f&quot;T0(x) % Zh(x) != 0&quot;<br><br>T1 = (_F * Z - _G * Zomega) * alpha<br>assert T1 % Zh == 0, f&quot;T1(x) % Zh(x) != 0&quot;<br><br>T2 = (Z - galois.Poly([1], field=Fp)) * L1 * alpha**2<br>assert T2 % Zh == 0, f&quot;T2(x) % Zh(x) != 0&quot;<br><br>T = (T0 + T1 + T2)<br>assert T % Zh == 0, f&quot;T(x) % Zh(x) != 0&quot;<br><br>for r in roots:<br>    assert T(r) == 0, f&quot;T({r}) != 0&quot;<br><br>T = T // Zh<br><br>t_coeffs = T.coeffs[::-1]<br><br>Tl = galois.Poly(t_coeffs[:n][::-1], field=Fp)<br>Tm = galois.Poly(t_coeffs[n:2*(n)][::-1], field=Fp)<br>Th = galois.Poly(t_coeffs[2*(n):][::-1], field=Fp)<br><br>X_n = galois.Poly.Degrees([n, 0], coeffs=[1, 0], field=Fp)<br>X_2n = galois.Poly.Degrees([2*(n), 0], coeffs=[1, 0], field=Fp)<br># make sure that T was split correctly<br># T = TL + X^n * TM + X^2n * TH<br>assert T == (Tl + X_n * Tm + X_2n * Th)<br>assert T.degree == 3 * n + 5<br><br>b10 = Fp.Random()<br>b11 = Fp.Random()<br><br>Tl = Tl + b10 * X_n<br>Tm = Tm - b10 + b11 * X_n<br>Th = Th - b11<br>assert T == (Tl + X_n * Tm + X_2n * Th)<br><br>round3 = [Tl(tau), Tm(tau), Th(tau)]</pre><h4>Round 4</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Z5PqGHwMQqk1TWJnYwXrVw.png" /></figure><p>This round is the simplest The prover now needs to evaluate polynomials at a specific random point, zeta.</p><pre>zeta = numbers_to_hash(round1 + round2 + round3, Fp)<br><br>a_zeta = A(zeta)<br>b_zeta = B(zeta)<br>c_zeta = C(zeta)<br>s1_zeta = S1(zeta)<br>s2_zeta = S2(zeta)<br>z_omega_zeta = Zomega(zeta)<br><br>round4 = [a_zeta, b_zeta, c_zeta, s1_zeta, s2_zeta, z_omega_zeta]</pre><p><strong>Round 5</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bhPHVuhl3gjmsZ-1alUqIg.png" /></figure><p>In Round 5 of the PLONK protocol, we focus on constructing the <strong>linearization polynomial</strong> r(X). The PLONK paper, on<a href="https://eprint.iacr.org/2019/953.pdf"> page 18</a>, introduces an optimization technique titled ‘Reducing the number of field elements in the proof.’ This technique is applied to the r(X) polynomials. Let’s consider an example:</p><ul><li>The verifier aims to check the identity h1(X) · h2(X) − h3(X) ≡ 0. Typically, the prover would send the values of h1, h2, and h3 evaluated at a random point r, and the verifier would then check if h1(r) · h2(r) − h3(r) equals 0. In this scenario, the prover sends three field elements.</li><li>However, the prover could simply send a single value c = h1(r), and the verifier can then verify if a new polynomial L(X) = c · h2(X) − h3(X) equals zero at the same point. Here, L(X) is referred to as the <strong>linearization polynomial</strong>.</li><li>In the context of KZG, we can express this as computing [L] = c · [h2] − [h3]. This approach effectively reduces the number of field elements required in the proof.</li></ul><p>The next two W polynomials function as openings in the KZG polynomial commitment scheme. They are composed with other polynomials that we aim to prove. To ensure their linear independence, we use the value ‘v’, which is employed for batching multiple polynomials into one, as detailed in <a href="https://medium.com/coinmonks/under-the-hood-of-zksnarks-plonk-protocol-part-1-34bc406d8303">Part 1</a>.</p><pre>v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)<br><br>R = (QM * a_zeta * b_zeta +<br>    QL * a_zeta +<br>    QR * b_zeta +<br>    QO * c_zeta +<br>    QC)<br>R += (Z * <br>    (a_zeta + beta * zeta + gamma) *<br>    (b_zeta + beta * zeta * k1 + gamma) *<br>    (c_zeta + beta * zeta * k2 + gamma) * alpha)<br>R -= (z_omega_zeta *<br>    (a_zeta + beta * s1_zeta + gamma) *<br>    (b_zeta + beta * s2_zeta + gamma) * <br>    (c_zeta + beta * S3 + gamma) * alpha)<br>R += (Z - Fp(1)) * L1(zeta) * alpha**2<br>R -= Zh(zeta) * (Tl + zeta**n * Tm + zeta**(2*n) * Th)<br><br>X_minus_zeta = galois.Poly([1, -zeta], field=Fp)<br><br>Wzeta = R + \<br>        (A - a_zeta) * v + \<br>        (B - b_zeta) * v**2 + \<br>        (C - c_zeta) * v**3 + \<br>        (S1 - s1_zeta) * v**4 + \<br>        (S2 - s2_zeta) * v**5<br><br>assert Wzeta % X_minus_zeta == 0, f&quot;Wzeta(x) % X - zeta != 0&quot;<br>Wzeta = Wzeta // X_minus_zeta<br><br>X_minus_omega_zeta = galois.Poly([1, -(omega*zeta)], field=Fp)<br><br>Womega_zeta = (Z - z_omega_zeta)<br>assert Womega_zeta % X_minus_omega_zeta == 0, f&quot;Womega_zeta(x) % X - ω*zeta != 0&quot;<br>Womega_zeta = Womega_zeta // X_minus_omega_zeta<br><br>round5 = [Wzeta(tau), Womega_zeta(tau)]<br><br>u = numbers_to_hash(round1 + round2 + round3 + round4 + round5, Fp)</pre><p>Finally the proof consists of 9 points and 6 field elements:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3ZtmfR7xQQrrIYEgBbJEsA.png" /></figure><h4><strong>Verifier</strong></h4><p>Firstly, what the verifier needs to do with the proof is to check whether all 9 points are indeed on the elliptic curve, and whether the 6 elements are valid field elements. While I am not entirely certain of the reason for this, it might be related to mitigating the possibility of a weak curve attack. A weak curve attack in cryptography refers to a method of compromising elliptic curve cryptography (ECC) by exploiting weaknesses in the chosen elliptic curve. Therefore, an attacker might attempt to use points from a weaker curve to breach the protocol.</p><pre># Values provided by the prover (round 1 to 5) is a proof.<br>a_exp = round1[0]<br>b_exp = round1[1]<br>c_exp = round1[2]<br><br>z_exp = round2[0]<br><br>tl_exp = round3[0]<br>tm_exp = round3[1]<br>th_exp = round3[2]<br><br># Note: verifier has to verify that the following values are in the correct Fp field<br>a_zeta, b_zeta, c_zeta, s1_zeta, s2_zeta, z_omega_zeta = round4<br><br>w_zeta_exp = round5[0]<br>w_omega_zeta_exp = round5[1]<br><br># Note: verifier has to verify that the following values are on the curve<br>if encrypted:<br>    validate_point(qm_exp)<br>    validate_point(ql_exp)<br>    validate_point(qr_exp)<br>    validate_point(qo_exp)<br>    validate_point(qc_exp)<br>    validate_point(qpi_exp)<br>    validate_point(z_exp)<br>    validate_point(s1_exp)<br>    validate_point(s2_exp)<br>    validate_point(s3_exp)<br>    validate_point(tl_exp)<br>    validate_point(tm_exp)<br>    validate_point(th_exp)<br>    validate_point(a_exp)<br>    validate_point(b_exp)<br>    validate_point(c_exp)<br>    validate_point(w_zeta_exp)<br>    validate_point(w_omega_zeta_exp)</pre><p>Next, the verifier must calculate the challenges β, γ, α, zeta, v, and u using the elements provided in the proof.</p><pre>beta = numbers_to_hash(round1 + [0], Fp)<br>gamma = numbers_to_hash(round1 + [1], Fp)<br>alpha = numbers_to_hash(round1 + round2, Fp)<br>zeta = numbers_to_hash(round1 + round2 + round3, Fp)<br>v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)<br>u = numbers_to_hash(round1 + round2 + round3 + round4 + round5, Fp)</pre><p>All following steps are done according to paper:</p><pre># evaluate vanishing and L1 polynomial ar zeta<br>Zh_z = Zh(zeta)<br>L1_z = L1(zeta)<br># PI_z = PI(z) - for public input<br><br># Compute constant part of r polynomials,<br># r0 = PI_z - L1_z ...<br>r0 = (- L1_z * alpha**2 -<br>    (a_zeta + beta * s1_zeta + gamma) *<br>    (b_zeta + beta * s2_zeta + gamma) *<br>    (c_zeta + gamma) * z_omega_zeta * alpha)<br><br># Compute first part of batched polynomial commitment <br>D_exp = (qm_exp * a_zeta * b_zeta +<br>        ql_exp * a_zeta +<br>        qr_exp * b_zeta +<br>        qo_exp * c_zeta +<br>        qc_exp)<br><br>D_exp += (z_exp * (<br>        (a_zeta + beta * zeta + gamma) *<br>        (b_zeta + beta * zeta * k1 + gamma) *<br>        (c_zeta + beta * zeta * k2 + gamma) * alpha<br>        + L1_z * alpha**2 + u))<br><br>D_exp -= (s3_exp *<br>        (a_zeta + beta * s1_zeta + gamma) *<br>        (b_zeta + beta * s2_zeta + gamma) * <br>        alpha * beta * z_omega_zeta)<br><br>D_exp -= ((tl_exp + <br>        tm_exp * zeta**n  +<br>        th_exp * zeta**(2*n)) *<br>        Zh_z)<br><br><br>F_exp = (D_exp + <br>        a_exp * v +<br>        b_exp * v**2 +<br>        c_exp * v**3 +<br>        s1_exp * v**4 +<br>        s2_exp * v**5)<br><br>E_exp = (-r0 +<br>        v * a_zeta +<br>        v**2 * b_zeta +<br>        v**3 * c_zeta +<br>        v**4 * s1_zeta +<br>        v**5 * s2_zeta +<br>        u * z_omega_zeta)<br><br>if encrypted:<br>        E_exp = G1 * E_exp<br><br>e1 = w_zeta_exp + w_omega_zeta_exp * u<br>e2 = (w_zeta_exp * zeta + w_omega_zeta_exp * (u * zeta * omega) +<br>    F_exp + (E_exp * Fp(p-1)))<br><br>if encrypted:<br>    pairing1 = tau.tau2.pair(e1)<br>    pairing2 = G2.pair(e2)<br><br>    print(f&quot;pairing1 = {pairing1}&quot;)<br>    print(f&quot;pairing2 = {pairing2}&quot;)<br><br>    assert pairing1 == pairing2, f&quot;pairing1 != pairing2&quot;<br>else:<br>    print(&quot;\n\n--- e1, e2 ---&quot;)<br>    print(f&quot;e1 = {e1 * tau}&quot;)<br>    print(f&quot;e2 = {e2}&quot;)<br>    assert e1 * tau == e2</pre><p><em>UPD: The article was originally written without considering public input. The final script has now been updated to include one parameter based on public feedback</em>.</p><p>Final implementation:</p><p><a href="https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_latest.ipynb">zkSNARK-under-the-hood/plonk_latest.ipynb at main · tarassh/zkSNARK-under-the-hood</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5a030d15be68" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Under the hood of zkSNARKs — PLONK protocol: part 5]]></title>
            <link>https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-5-4819dd56d3f1?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/4819dd56d3f1</guid>
            <category><![CDATA[plonk]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zkp]]></category>
            <category><![CDATA[blockchian]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Sun, 19 Nov 2023 14:50:49 GMT</pubDate>
            <atom:updated>2023-11-30T18:51:06.065Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PvK_3Gp8orJ4F1Qn0jd4Ng.png" /></figure><h3>Under the hood of zkSNARKs — PLONK protocol: part 5</h3><p>Previous articles in the PLONK series served as preparations before we got our hands dirty and started implementing the protocol. Diving directly into the code would have made it difficult to understand the reasoning and rationale behind the things we are going to implement. The last significant concept we need to explain before proceeding is related to non-interactive proofs.</p><p><a href="https://medium.com/coinmonks/under-the-hood-of-zksnarks-plonk-protocol-part-1-34bc406d8303">Under the hood of zkSNARKs — PLONK protocol: Part 1</a></p><p>In Part 1, we delved into the core of the PLONK protocol, the KZG polynomial commitment scheme, which is interactive by design:</p><ul><li>The prover commits to a polynomial by sending a commitment to a verifier.</li><li>In return, the prover receives a random value <em>r</em> selected by the verifier.</li><li>Based on this random value <em>r</em>, the prover generates the next commitment and sends it back to the verifier.</li><li>The verifier then checks if the prover provided correct commitments, based on everything received from the prover and the random value <em>r</em>.</li></ul><p>Thanks to the Fiat-Shamir heuristic in PLONK, the KZG becomes non-interactive, meaning that the proof is the only piece of data sent to the verifier. Both the prover and verifier are able to agree on the random value <em>r</em> without any interaction. This is achieved using a hash function:</p><ul><li>The prover generates a commitment to a polynomial, denoted by the letter C, for example.</li><li>To obtain the random value <em>r</em>, the prover uses the hash function <em>H</em>, where <em>r</em>=<em>H</em>(<em>C</em>), and using the value <em>r</em>, generates the remaining commitment <em>Q</em>, and sends <em>C</em> and <em>Q</em> to the verifier.</li><li>The verifier, using the same hash function <em>H</em>, generates the value <em>r</em>=<em>H</em>(<em>C</em>) and, having all the necessary data, is able to verify the commitment <em>C</em>.</li></ul><h4>Preparation</h4><p>The final implementation of the PLONK protocol can be found here:</p><p><a href="https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_latest.ipynb">zkSNARK-under-the-hood/plonk_latest.ipynb at main · tarassh/zkSNARK-under-the-hood</a></p><p>We are using Python because this language is exceptionally suitable for educational purposes. We will be relying heavily on the <a href="https://galois.readthedocs.io/en/v0.3.6/">Galois</a> library, as it provides a very convenient interface for working with polynomials:</p><pre>import galois<br><br>P = galois.Poly([1, 4], field=galois.GF(7))<br>print(f&quot;P = {P}&quot;)<br>print(f&quot;P(1) = {P(1)}&quot;)<br># --- prints ---<br># P = x + 4<br># P(1) = 5</pre><p>Also, by using the monkey patching technique, we can extend the evaluation function so that polynomials can work with elliptic curve points:</p><pre>def new_call(self, at, **kwargs):<br>    # class SRS - Elliptic curve points from Trusted Setup<br>    if isinstance(at, SRS):<br>        coeffs = self.coeffs[::-1]<br>        result = at.tau1[0] * coeffs[0]<br>        for i in range(1, len(coeffs)):<br>            result += at.tau1[i] * coeffs[i]<br>        return result<br><br>    return galois.Poly.original_call(self, at, **kwargs)<br><br>galois.Poly.original_call = galois.Poly.__call__<br>galois.Poly.__call__ = new_call</pre><p>This clever trick helps us make the code compatible with both Finite Fields (in unencrypted form) and Elliptic Curves (in encrypted form). The rationale behind this approach is simple: it is easier to implement the protocol in an unencrypted form by selecting a Finite Field with a lower order (p=241 in our case). This makes it much easier to debug, locate, and troubleshoot bugs.</p><pre>import galois<br>import numpy as np<br>from utils import generator1, generator2, curve_order, normalize, validate_point<br><br>G1 = generator1()<br>G2 = generator2()<br><br><br>class SRS:<br>    &quot;&quot;&quot;Trusted Setup Class aka Structured Reference String&quot;&quot;&quot;<br>    def __init__(self, tau, n = 2):<br>        self.tau = tau<br>        self.tau1 = [G1 * int(tau)**i for i in range(0, n + 7)]<br>        self.tau2 = G2 * int(tau)<br><br>    def __str__(self):<br>        s = f&quot;tau: {self.tau}\n&quot;<br>        s += &quot;&quot;.join([f&quot;[tau^{i}]G1: {str(normalize(point))}\n&quot; for i, point in enumerate(self.tau1)])<br>        s += f&quot;[tau]G2: {str(normalize(self.tau2))}\n&quot;<br>        return s<br><br>def new_call(self, at, **kwargs):<br>    if isinstance(at, SRS):<br>        coeffs = self.coeffs[::-1]<br>        result = at.tau1[0] * coeffs[0]<br>        for i in range(1, len(coeffs)):<br>            result += at.tau1[i] * coeffs[i]<br>        return result<br><br>    return galois.Poly.original_call(self, at, **kwargs)<br><br>galois.Poly.original_call = galois.Poly.__call__<br>galois.Poly.__call__ = new_call</pre><p>Next, we need to define our Finite Field with order p = 241 and find roots of unity (<a href="https://medium.com/coinmonks/under-the-hood-of-zksnarks-plonk-protocol-part-2-ee00d6accb4d">as discussed in part 2</a>), which are necessary for polynomial evaluation.</p><pre># to switch between encrypted (ECC) and unencrypted mode (prime field p=241)<br>encrypted = False<br><br># Prime field p<br>p = 241 if not encrypted else curve_order<br>Fp = galois.GF(p)<br><br># We have 7 gates, next power of 2 is 8<br>n = 7<br>n = 2**int(np.ceil(np.log2(n)))<br>assert n &amp; n - 1 == 0, &quot;n must be a power of 2&quot;<br><br># Find primitive root of unity (generator)<br>omega = Fp.primitive_root_of_unity(n)<br>assert omega**(n) == 1, f&quot;omega (ω) {omega} is not a root of unity&quot;<br># ω = 30<br><br>roots = Fp([omega**i for i in range(n)])<br>print(f&quot;roots = {roots}&quot;)<br># roots = [  1  30 177   8 240 211  64 233]</pre><p><em>Note: Before the provers start generating the proof, the circuit wiring and permutation should be known beforehand. Therefore, the following code might give the wrong impression by including witnesses data (a, b, and c vectors) in it. Witness data is used to demonstrate the permutation relation to real values. In a real situation, a compiler would generate a circuit with placeholders for a, b, and c.</em></p><p>The circuit consists of 7 gates. For reasons explained in previous articles, we need to extend our vectors to 8 gates:</p><pre>def pad_array(a, n):<br>    return a + [0]*(n - len(a))<br><br># witness vectors<br>a = [2, 2, 3, 4, 4, 8, -28]<br>b = [2, 2, 3, 0, 9, 36, 3]<br>c = [4, 4, 9, 8, 36, -28, -25]<br><br># gate vectors<br>ql = [0, 0, 0, 2, 0, 1, 1]<br>qr = [0, 0, 0, 0, 0, -1, 0]<br>qm = [1, 1, 1, 1, 1, 0, 0]<br>qc = [0, 0, 0, 0, 0, 0, 3]<br>qo = [-1, -1, -1, -1, -1, -1, -1]<br><br># pad vectors to length n<br>a = pad_array(a, n)<br>b = pad_array(b, n)<br>c = pad_array(c, n)<br>ql = pad_array(ql, n)<br>qr = pad_array(qr, n)<br>qm = pad_array(qm, n)<br>qc = pad_array(qc, n)<br>qo = pad_array(qo, n)<br><br># --- padded vectors ----<br>a = [2, 2, 3, 4, 4, 8, -28, 0]<br>b = [2, 2, 3, 0, 9, 36, 3, 0]<br>c = [4, 4, 9, 8, 36, -28, -25, 0]<br>ql = [0, 0, 0, 2, 0, 1, 1, 0]<br>qr = [0, 0, 0, 0, 0, -1, 0, 0]<br>qm = [1, 1, 1, 1, 1, 0, 0, 0]<br>qc = [0, 0, 0, 0, 0, 0, 3, 0]<br>qo = [-1, -1, -1, -1, -1, -1, -1, 0]</pre><p>Now, we have to create permutation vectors (sigma) for a, b, and c:</p><pre>ai = range(0, n)<br>bi = range(n, 2*n)<br>ci = range(2*n, 3*n)<br><br>sigma = {<br>    ai[0]: ai[0], ai[1]: ai[1], ai[2]: ai[2], ai[3]: ci[0], ai[4]: ci[1], ai[5]: ci[3], ai[6]: ci[5], ai[7]: ai[7],<br>    bi[0]: bi[0], bi[1]: bi[1], bi[2]: bi[2], bi[3]: bi[3], bi[4]: ci[2], bi[5]: ci[4], bi[6]: bi[6], bi[7]: bi[7],<br>    ci[0]: ai[3], ci[1]: ai[4], ci[2]: bi[4], ci[3]: ai[5], ci[4]: bi[5], ci[5]: ai[6], ci[6]: ci[6], ci[7]: ci[7],<br>}<br><br>k1 = 2<br>k2 = 4<br>c1_roots = roots<br>c2_roots = roots * k1<br>c3_roots = roots * k2<br><br>c_roots = np.concatenate((c1_roots, c2_roots, c3_roots))<br><br>check = set()<br>for r in c_roots:<br>    assert not int(r) in check, f&quot;Duplicate root {r} in {c_roots}&quot;<br>    check.add(int(r))<br><br>sigma1 = Fp([c_roots[sigma[i]] for i in range(0, n)])<br>sigma2 = Fp([c_roots[sigma[i + n]] for i in range(0, n)])<br>sigma3 = Fp([c_roots[sigma[i + 2 * n]] for i in range(0, n)])<br><br>print_sigma(sigma, a, b, c, c_roots)<br># print_sigma outputs<br> w | value  | i      | sigma(i)<br>a0 |      2 |      1 |      1<br>a1 |      2 |     30 |     30<br>a2 |      3 |    177 |    177<br>a3 |      4 |      8 |      4<br>a4 |      4 |    240 |    120<br>a5 |      8 |    211 |     32<br>a6 |    -28 |     64 |    121<br>a7 |      0 |    233 |    233<br>-- | --     | --     | --    <br>b0 |      2 |      2 |      2<br>b1 |      2 |     60 |     60<br>b2 |      3 |    113 |    113<br>b3 |      0 |     16 |     16<br>b4 |      9 |    239 |    226<br>b5 |     36 |    181 |    237<br>b6 |      3 |    128 |    128<br>b7 |      0 |    225 |    225<br>-- | --     | --     | --    <br>c0 |      4 |      4 |      8<br>c1 |      4 |    120 |    240<br>c2 |      9 |    226 |    239<br>c3 |      8 |     32 |    211<br>c4 |     36 |    237 |    181<br>c5 |    -28 |    121 |     64<br>c6 |    -25 |     15 |     15<br>c7 |      0 |    209 |    209<br><br>--- Sigma ---<br>sigma1 = [  1  30 177   4 120  32 121 233]<br>sigma2 = [  2  60 113  16 226 237 128 225]<br>sigma3 = [  8 240 239 211 181  64  15 209]</pre><p>As explained in the <a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part4-5e74bddebedb">previous article</a>, to have a correct permutation proof, we need to mark each wire with a unique index, and these indexes have to be generated from roots of unity. The output clearly shows how permutations are encoded: for example, the a0 wire (value 2) has index 1 and is not connected with any other gate, so its permutation index sigma is also 1. The a5 wire (value 8), for instance, has index 211 and is permuted with index 32, which belongs to wire c3 (also value 8).</p><p>Now that the permutation map is ready, we can start creating polynomials. Let’s begin with gate polynomials:</p><pre>def to_galois_array(vector, field):<br>    # normalize to positive values<br>    a = [x % field.order for x in vector]<br>    return field(a)<br><br>def to_poly(x, v, field):<br>    assert len(x) == len(v)<br>    y = to_galois_array(v, field) if type(v) == list else v<br>    return galois.lagrange_poly(x, y)<br><br>QL = to_poly(roots, ql, Fp)<br>QR = to_poly(roots, qr, Fp)<br>QM = to_poly(roots, qm, Fp)<br>QC = to_poly(roots, qc, Fp)<br>QO = to_poly(roots, qo, Fp)<br># --- Gate Polynomials ---<br># QL = 187x^7 + 38x^6 + 119x^5 + 60x^4 + 70x^3 + 22x^2 + 106x + 121<br># QR = 64x^7 + 8x^6 + x^5 + 211x^4 + 177x^3 + 233x^2 + 240x + 30<br># QM = 57x^7 + 211x^6 + 73x^5 + 211x^4 + 168x^3 + 211x^2 + 184x + 91<br># QC = 24x^7 + 90x^6 + 217x^5 + 151x^4 + 24x^3 + 90x^2 + 217x + 151<br># QO = 240x^7 + 8x^6 + 177x^5 + 30x^4 + x^3 + 233x^2 + 64x + 210</pre><p><em>Note: For better performance, we would need to have polynomials in evaluated form and perform polynomial multiplications using FFT transformations. This would introduce more complexity to the code. But to align more closely with the formulas presented in the PLONK paper we will stick to the coefficient form.</em></p><p>We have encoded our q vectors into polynomials, and if I needed to get a value at index 8 (a root of unity) from polynomial QL, the result would be 2:</p><pre>#   i = [  0   1   2   3   4   5  6    7]<br>roots = [  1  30 177   8 240 211  64 233]<br>ql =    [  0   0   0   2   0   1   1   0]<br><br># QL(8) = 2</pre><p>Same technique we should use for permutation polynomials:</p><pre>S1 = to_poly(roots, sigma1, Fp)<br>S2 = to_poly(roots, sigma2, Fp)<br>S3 = to_poly(roots, sigma3, Fp)<br><br>I1 = to_poly(roots, c1_roots, Fp)<br>I2 = to_poly(roots, c2_roots, Fp)<br>I3 = to_poly(roots, c3_roots, Fp)</pre><p>Vanishing polynomial:</p><pre>def to_vanishing_poly(roots, field):<br>    # Z^n - 1 = (Z - 1)(Z - w)(Z - w^2)...(Z - w^(n-1))<br>    return galois.Poly.Degrees([len(roots), 0], coeffs=[1, -1], field=field)<br><br>Zh = to_vanishing_poly(roots, Fp)<br>for x in roots:<br>    assert Zh(x) == 0<br># --- Vanishing Polynomial ---<br># Zh = x^8 + 240 which translates to x^8 - 1 (240 == -1 in Prime Field p=241)</pre><h4>Trusted Setup</h4><p>To implement the trusted setup in our code, we don’t need extensive coding. It’s important to highlight that our trusted setup can operate in two modes, encrypted and unencrypted, by effectively utilising an encrypted flag.</p><pre>def generate_tau(encrypted):<br>    &quot;&quot;&quot; Generate a random tau in Fp or G1 &quot;&quot;&quot;<br>    return SRS(Fp.Random(), n) if encrypted else Fp.Random()<br><br>tau = generate_tau(encrypted)</pre><p>Next article will be dedicated to Prover and Verifier implementations.</p><p><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-6-5a030d15be68">Under the hood of zkSNARKs — PLONK protocol: part 6</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4819dd56d3f1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Under the hood of zkSNARKs — PLONK protocol: part4]]></title>
            <link>https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part4-5e74bddebedb?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/5e74bddebedb</guid>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[plonk]]></category>
            <category><![CDATA[zkp]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Tue, 14 Nov 2023 19:58:16 GMT</pubDate>
            <atom:updated>2023-11-19T14:52:40.566Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*COFAGFtqPefAlN3Q3yklwQ.png" /><figcaption>Permutations — seen by Openai</figcaption></figure><h3>Under the hood of zkSNARKs — PLONK protocol: part4</h3><p>This article will discuss the permutation check in PLONK, which I believe is the second most challenging aspect of the protocol. The most challenging part, in my opinion, is debugging and identifying errors in the code.</p><p><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part3-821855e49ce6">Under the hood of zkSNARKs — PLONK protocol: part3</a></p><p>In our previous discussion, we delved into the complexities of arithmetization in PLONK, exploring the details of gates and gate constraints. As the result we encoded all the states of the prover program into number of vectors:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/746/1*EcFks1f8tmlvsVCZTyddLQ.png" /></figure><p>Vectors ‘a’, ‘b’, and ‘c’ are referred to as the ‘witness vectors’. It’s crucial to maintain the confidentiality of these vectors, keeping them hidden from the verifier. On the other hand, vectors prefixed with the letter ‘q’ are known as ‘selector vectors’. These vectors function as a set of flags that enable the proper gating and wiring mechanisms within the system.</p><p>Vectors describe the program’s state, yet it doesn’t fully address the interconnection between gates. The creation of a robust proof in PLONK relies not only on the consistency of individual gates but also crucially on the consistency of wiring between these gates. This is where the real challenge lies:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lK8zKlF2fTSVDgyLq5Pi6w.png" /></figure><p>In this visualization, the colors represent the wiring between gates, a critical component that we need to construct meticulously. It’s important to note that our focus here shifts from the values, as was the case with gate constraints, to both the wires and their values.</p><p>To ensure proper functioning, each wire is assigned a unique index. Our task then is to verify that each wire is connected only once. This challenge essentially reduces to comparing two lists: we need to check whether every element in one list is also present in the other. To facilitate this, we use the following formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*p03Jnl2jNJsWqNieiPncfQ.png" /></figure><p>This formula looks scary and ugly, which is one of the reasons why Zero-Knowledge Proofs (ZKPs) can be challenging to understand. So, let’s break it down with a simple example. Imagine we have two lists:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/1*gPL_OiKzd89JEE4NCrvpaA.png" /></figure><p>Now, let’s try to perform an element-wise division and then multiply the results together.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/278/1*tn9v5CEIjjBvrTlSX-V73A.png" /></figure><p>The result will be 1, and this is because the elements effectively cancel each other out. But what if the second list had two instances of 1, like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/270/1*NTIz05S7_mzHDtJ-lCXhzA.png" /></figure><p>The result would then be 4. It’s a clever way to check if two lists contain the same elements, isn’t it? We can write down a formula for this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/390/1*z1H0CC119o7lbhON-2s1Gw.png" /></figure><p>Two lists: L and L’. We begin by dividing the first elements of each list and continue this process sequentially. The result of each division is multiplied by the result from the previous division. Since the first elements do not have a preceding division, we start with an initial value, setting acc0 = 1 as a placeholder. After completing this process for all elements, the final result should be 1. Now, let’s consider another pair of lists:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/198/1*UBncgS68pUHv0_eymNXyZg.png" /></figure><p>Using the formula previously discussed, you’ll notice that the result will also be 1, even though the lists are different. To fix this issue, we introduce an offset to the elements in the list. This offset is denoted by the symbol gamma (γ), which is a randomly chosen number. For example, let’s assume γ=4:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/452/1*Jw6cnjg5cU80T1fRpGtd6Q.png" /></figure><p>Up to now, our focus has been on verifying whether all elements from one list are present in another. The next logical step is to associate values with their corresponding wire indexes. Let’s introduce a function, sigma (σ), which returns a permutation index for lists L and L’ as examples, where L = [1, 3, 2, 4] and L’ = [1, 2, 4, 3]:</p><ul><li>σ(1) = 1, meaning the 1st element from L’ is also the 1st in L.</li><li>σ(2) = 3, meaning the 2nd element from L’ is the 3rd in L.</li><li>σ(3) = 4, meaning the 3rd element from L’ is the 4th in L.</li><li>σ(4) = 2, meaning the 4th element from L’ is the 2nd in L.</li></ul><p>We can encode L and L’ into tuples, where firs item is a value, second is an index and a sigma function for L’:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*8Eo3_dqNPW5OruIxPG-edA.png" /></figure><p>Now substitute σ with the values it returns:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/406/1*kLbtZyPc8gjgrzrvRuWncQ.png" /></figure><p>Using tuples (p, q), we can effectively represent the relationship between values and their corresponding indexes in the code. But for mathematicians this notation doesn’t make any sense so they would put it like this; take a random value beta (β) and encode L and L’ as (p + qβ):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/482/1*SLMUrKKAP1fwAFluTMroow.png" /></figure><p>So if we divide all values and multiply the results we will get 1:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/518/1*p-yrU9Zr0AmmHzaav385Vg.png" /></figure><p>And together with gamma (γ):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/710/1*O8Eb6GP8M_GNnzEaItXdZw.png" /></figure><p>Now we can generalize it into the formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*0hZ2m1GH0_AYfktWRyxJoA.png" /></figure><p>Do you see where we are going with this? We need to apply it to vectors a, b, and c.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/476/1*NGNOsTIR82po28t3qdGOZQ.png" /></figure><p>So, if we now proceed to multiply these divisions, the result will not be 1. This outcome is due to a key point I mentioned earlier: each permutation, represented as (iβ) and (βσ(i)), must have unique indexes. Consequently, we cannot use the same index values in vectors ‘b’ and ‘c’.</p><p>Let’s assume that the permutations for vector ‘a’ are indexed from 1 to ’n’. For vector ‘b’, we’ll use indexes from ‘2n’ to ‘3n’, and for vector ‘c’, we’ll use indexes starting from ‘3n’. Additionally, the values ‘2’ and ‘3’ in this context can be denoted as ‘k1’ and ‘k2’, respectively.</p><p>Regarding the sigma function, we now introduce three distinct sigma functions Sσ1, Sσ2, and Sσ3:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XMpDwxB8uO0suZE1I4Yq3w.png" /></figure><p>Now, with these considerations in place, the original formula becomes less scary than before. The remaining step involves transitioning from plain indexes, such as 1, 2, etc., to roots of unity. This shift is part of an optimization process discussed in the second part of our previous article, where we explored the benefits of replacing plain indexes with roots of unity for efficiency:</p><p><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-2-ee00d6accb4d">Under the hood of zkSNARKs — PLONK protocol: Part 2</a></p><p>Thus, we need to take a primitive root of unity (ω) and generate a series of indexes from it. This step is essential for our formula to reach its final form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*v_IoQgujlyq8UUfbcQsqSQ.png" /></figure><p>In next article we start to code protocol:</p><p><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-5-4819dd56d3f1">Under the hood of zkSNARKs — PLONK protocol: part 5</a></p><p><strong>References:</strong></p><ul><li>Plonk Permutations by David Wong <a href="https://www.youtube.com/watch?v=iY2ue8Kfsb0">https://www.youtube.com/watch?v=iY2ue8Kfsb0</a></li><li>Plonk Paper <a href="https://eprint.iacr.org/archive/2019/953/1599151811.pdf">https://eprint.iacr.org/archive/2019/953/1599151811.pdf</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5e74bddebedb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Under the hood of zkSNARKs — PLONK protocol: part3]]></title>
            <link>https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part3-821855e49ce6?source=rss-b3a405d735c6------2</link>
            <guid isPermaLink="false">https://medium.com/p/821855e49ce6</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zkp]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[plonk]]></category>
            <dc:creator><![CDATA[Taras Shchybovyk]]></dc:creator>
            <pubDate>Sat, 11 Nov 2023 23:37:29 GMT</pubDate>
            <atom:updated>2023-11-14T19:58:52.846Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*i0lHuI6MK-k5f1k8bm178w.png" /></figure><h3>Under the hood of zkSNARKs — PLONK protocol: part3</h3><p>Many materials available online explain the basics of the PLONK protocol, often referencing Vitalik’s example <em>P</em>(<em>x</em>)=<em>x³</em>+<em>x</em>+5=35 from his article:</p><p><a href="https://vitalik.ca/general/2019/09/22/plonk.html">Understanding PLONK</a></p><p>To offer a different perspective, this article will explore a modified equation that introduces additional complexities. We will use the equation <em>f</em>(<em>x</em>,<em>y</em>)=2<em>x²</em>−<em>x²y²</em>+3 and set it to equal -25, with <em>x</em>=2 and <em>y</em>=3. This equation features two input parameters, a subtraction operation, a negative result, the repeated use of an operation (<em>x²</em>), and multiplication by a constant (as seen in 2<em>x²</em>). These elements provide a broader understanding of how PLONK handles various computational scenarios.</p><h4>Arithmetization</h4><p>The first step in transforming an equation into a Zero-Knowledge Proof (ZKP) is arithmetization. As mentioned in the previous article, to generate a proper proof for the statement, it’s essential to capture all the states of the program during its execution. Arithmetization achieves this by converting the computation into a polynomial form, which allows for the efficient generation and verification of the proof within the ZKP framework.</p><p><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-2-ee00d6accb4d">Under the hood of zkSNARKs — PLONK protocol: Part 2</a></p><p>Using Circom, we can translate our problem into code like this:</p><pre>pragma circom 2.1.6;<br><br>template Example () {<br>    signal input x;<br>    signal input y;<br>    signal output out;<br><br>    signal xx;<br>    signal yy;<br><br>    xx &lt;== x * x; // Quadratic term: x squared<br>    yy &lt;== y * y; // Quadratic term: y squared<br><br>    // Intermediate signal for x*x*y*y<br>    signal xxyy;<br>    xxyy &lt;== xx * yy;<br><br>    // Final expression<br>    out &lt;== xx * 2 - xxyy + 3;<br>}<br><br>component main { public [ x, y ] } = Example();<br><br>/* INPUT = {<br>    &quot;x&quot;: &quot;2&quot;,<br>    &quot;y&quot;: &quot;3&quot;<br>} */</pre><p>This approach differs significantly from what an average developer might write in a language like Python:</p><pre>x = 2<br>y = 3<br>out = 2*x**2 - x**2*y**2 + 3</pre><p>Circom’s nature as a Domain Specific Language (DSL) aids in organizing code specifically for compiling into an arithmetic circuit. This structured format not only ensures that the code aligns with the mathematical requirements of the proofs but also optimizes the process of circuit generation and proof computation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/862/1*ziBTJn54Cajksz3iwWioSA.png" /><figcaption>Arithmetic Circuit</figcaption></figure><p>So, a clear pattern emerges in the circuit structure: each operation corresponds to a separate gate, denoted by <em>g0</em>, <em>g1</em>, …, etc. Each gate has two inputs (a, b) and one output ( c). Take gates g0 and g1, for example; both represent the same <em>x²</em> operation. In Circom, this calculation is performed once and then reused wherever needed, such as in <em>g0</em> and <em>g1</em>. The reason for having two identical gates relates to the permutation check, which ensures a 1-to-1 mapping of the wires (for example, output <em>c0</em> connects to input <em>a3</em>, <em>c1</em> to <em>a4</em>, and so on).</p><p>Another point of interest is gate <em>g3</em>. Here, you might notice that the second input for the constant 2 is not marked by ‘b’. This is because, in PLONK, multiplication can only involve variables, so ‘b’ is set to 0 in this case. However, constants are permissible in addition gates. The constant 2 for multiplication in gate <em>g3</em> comes from a selector vector, which we will address later, and its depicting in this gate is more symbolic.</p><p>Lastly, it’s important to note that there are no subtraction gates. All calculations are performed using Finite Field arithmetic. In this system, negative numbers are transformed into positive ones through modulo operations, aligning with the field’s properties.</p><h4>Constraining the gates</h4><p>The next step involves describing each gate in the arithmetic circuit using polynomial equations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/742/1*rg-WtwNJPgWKe-8TRAE6xA.png" /></figure><p>In these equation, the variables <em>a</em>, <em>b</em>, and <em>c</em> represent the wires associated with each gate, corresponding to their inputs and output. Alongside these, we have selector variables, denoted as <em>q</em>, which function like activators for the gates. They determine which wires and operations are engaged in the circuit at any given point.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/1*rPNCyXiyGdP_MgXyIXW59A.png" /></figure><p>Each gate in our arithmetic circuit is represented by specific polynomial equations, influenced by selector variables. For example, gate <em>g0</em> performs a multiplication of inputs <em>a</em>0 and <em>b</em>0. To enable this operation, the multiplication selector variable <em>qm</em> is set to 1, and the gate outputs <em>c</em>0. The output activation is facilitated by setting the output selector <em>qo</em> to -1, adhering to the constraint that our polynomial equations must sum to 0. Gates <em>g1</em>, <em>g2</em>, and <em>g4</em> are configured similarly to <em>g0</em>.</p><p>In gate g3, to multiply the value <em>a</em>3 by the constant 2, we set the selector variable <em>ql</em> to 2. This gate showcases how constants are incorporated into the computations. For subtraction, as seen in gate <em>g5</em>, the right selector <em>qr</em> is set to -1, representing the subtraction operation in polynomial form. Addition is handled in gate <em>g6</em>, where the addition of a constant 3 is facilitated through the constant selector <em>qc</em>.</p><p>We have all the values for the gates so we can encode them into following vectors:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/766/1*RbF8x1Y--LLr53FwOG7_Uw.png" /></figure><h4>Dummy Gates</h4><p>In the previous article, we discussed an optimization technique involving the vanishing polynomial in PLONK, where steps are marked using roots of unity instead of sequential numbers. This optimisation necessitates having a number of gates that is a power of 2.</p><p>Currently, our circuit comprises 7 gates. However, to meet the 2^n requirement in PLONK, the closest power of 2 is 8 (2³ = 8). This means we need to add an additional gate to make the total number 8. This extra gate is a ‘dummy gate’ — it doesn’t perform any real computation but serves as a placeholder to satisfy the power of 2 structure. By adding this dummy gate, we ensure that our circuit adheres to the optimal structure for PLONK’s efficiency mechanisms.</p><pre>def pad_array(a, n):<br>    return a + [0]*(n - len(a))<br><br># witness vectors<br>a = [2, 2, 3, 4, 4, 8, -28]<br>b = [2, 2, 3, 0, 9, 36, 3]<br>c = [4, 4, 9, 8, 36, -28, -25]<br><br># gate vectors<br>ql = [0, 0, 0, 2, 0, 1, 1]<br>qr = [0, 0, 0, 0, 0, -1, 0]<br>qm = [1, 1, 1, 1, 1, 0, 0]<br>qc = [0, 0, 0, 0, 0, 0, 3]<br>qo = [-1, -1, -1, -1, -1, -1, -1]<br><br># pad vectors to length n<br>a = pad_array(a, n)<br>b = pad_array(b, n)<br>c = pad_array(c, n)<br>ql = pad_array(ql, n)<br>qr = pad_array(qr, n)<br>qm = pad_array(qm, n)<br>qc = pad_array(qc, n)<br>qo = pad_array(qo, n)<br># -- results ---<br># a = [2, 2, 3, 4, 4, 8, -28, 0]<br># b = [2, 2, 3, 0, 9, 36, 3, 0]<br># c = [4, 4, 9, 8, 36, -28, -25, 0]<br># ql = [0, 0, 0, 2, 0, 1, 1, 0]<br># qr = [0, 0, 0, 0, 0, -1, 0, 0]<br># qm = [1, 1, 1, 1, 1, 0, 0, 0]<br># qc = [0, 0, 0, 0, 0, 0, 3, 0]<br># qo = [-1, -1, -1, -1, -1, -1, -1, 0]</pre><p>In the next article we will discuss permutation constraint.</p><ul><li><a href="https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part4-5e74bddebedb">Under the hood of zkSNARKs — PLONK protocol: part4</a></li><li><a href="https://github.com/tarassh/zkSNARK-under-the-hood/blob/main/plonk_latest.ipynb">zkSNARK-under-the-hood/plonk_latest.ipynb at main · tarassh/zkSNARK-under-the-hood</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=821855e49ce6" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>