<?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 Xin Jiang on Medium]]></title>
        <description><![CDATA[Stories by Xin Jiang on Medium]]></description>
        <link>https://medium.com/@ppio_dohko?source=rss-43af36c6ceea------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*FJ174Phu0CeSrzsl.jpg</url>
            <title>Stories by Xin Jiang on Medium</title>
            <link>https://medium.com/@ppio_dohko?source=rss-43af36c6ceea------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 04:41:52 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@ppio_dohko/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 Micropayments Will Save The Blockchain]]></title>
            <link>https://medium.com/ppio/how-micropayments-will-save-the-blockchain-d083fcc502de?source=rss-43af36c6ceea------2</link>
            <guid isPermaLink="false">https://medium.com/p/d083fcc502de</guid>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[payment-channels]]></category>
            <category><![CDATA[micropayments]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[state-channels]]></category>
            <dc:creator><![CDATA[Xin Jiang]]></dc:creator>
            <pubDate>Thu, 16 Jan 2020 10:24:35 GMT</pubDate>
            <atom:updated>2020-01-16T10:53:47.171Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*MNcWjQ30Y3uwld4A" /></figure><p>If blockchain is to be truly commercial, it is inevitable that payments and settlements will take place on the chain. It is no surprise that in order to do so, we would need to reduce a blockchain’s operational costs as much as possible.</p><p>Probabilistic micropayment is one of the solutions to this problem.</p><p>The original concept of probabilistic payment predates blockchain technology. In 1996, David Wheeler first <a href="https://www.semanticscholar.org/paper/Transactions-Using-Bets-Wheeler/6583c552f30c5a61abd7b10b88a226d377613f7b">published a paper</a> explaining the concept of probabilistic payment and how to apply it to electronic protocols that use random number promises.</p><p>Then in 1997, <a href="https://en.wikipedia.org/wiki/Ron_Rivest">Ronald Rivest</a> published a paper on how to apply probabilistic payments to electronic micropayments.</p><p>In 2015, Pass and Shelat proposed in their paper “<a href="https://eprint.iacr.org/2016/332.pdf">Micropayments for Decentralized Currencies</a>” a method to apply probabilistic micropayments to tokens such as BTC, and pointed out that previous solutions all relied on trusted third parties.</p><p>In recent years, research on probability payments has gradually extended to zero-knowledge proofs, and is used to help build decentralized blockchain protocols and anonymous micropayments.</p><p>To better understand probabilistic micropayments, we need to know what micropayments are and why we need them.</p><h3>1. Micropayments</h3><p>The act of paying is all too familiar in the world, no matter if it’s exchanging physical currency or purchasing with Apple Pay, we know it well. But in the blockchain world, a simple payment becomes slightly more complicated. With a blockchain, the third-party is now removed from the transaction. And without that independent third party, the two parties involved in a trade have little reason to trust each other; with either side potentially believing the other will not act in a fair and just manner.</p><p>Here’s how a transaction can look on the blockchain:</p><p>Alice and Bob are trading on Ethereum, where Alice uses ETH to purchase bandwidth services provided by Bob. In this scenario, if Alice pays Bob first, she will worry Bob won’t provide her with bandwidth services. At the same time, Bob worries that if he provides bandwidth first, Alice will refuse to pay after using it.</p><p>As a result, both sides are unable to carry out the transaction because of trust issues.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/784/0*2AGTOY3SFzJyjUdy" /><figcaption>Alice and Bob’s dilemma — neither side trusts each other so no deal is made</figcaption></figure><p>Let’s say this was happening in the real world and not on the blockchain. How would it work?</p><p>By relying on third parties.</p><p>Alice first entrusts the money to a trusted third party. When Bob sees that Alice has entrusted the money, he will provide his service to Alice. After the service is completed, the trusted third party transfers the escrow funds to Bob’s account. If during this process, either party deceives the other through cheating, fraud, or other means, the harmed party can seek a third party for arbitration.</p><p>Back in the blockchain world, there is no trusted third party that can arbitrate a dispute. So the next best thing is to reduce the risk by reducing the size of the trade; breaking up a large transaction into a series of smaller ones.</p><p>For example, Alice downloads 100GB of data from Bob and in return pays Bob a total of 1 ETH. To prevent Bob from taking the money without rendering services, Alice can split the transaction into 100 pieces. In this case, for every 0.01 ETH received by Bob, he will send 1GB of data to Alice. After Alice confirms that the received data is correct, she will transfer another 0.01 ETH, in which Bob will send another 1GB. This will repeat until 100GB has been transferred to complete the transaction.</p><p>If Bob receives the <em>n</em>th 0.01 ETH, he no longer gives Alice data, then Alice will only lose the <em>n</em>th amount of 0.01 ETH at most. The smaller the units shared in the transaction, the less one side has to lose.</p><p>The act of breaking a large payment into a series of smaller payments in order to reduce risk is, you guessed it,<em> micropayments</em>.</p><p>Micropayments solve the problem of trading between two untrusted parties. However, it does not completely solve the risk of trading, it merely reduces it.</p><h3>2. Payment Channel</h3><p>Although micropayments allow two people who do not trust each other to trade, there is a cost involved when implementing this solution on the chain.</p><p>We all know that an <em>on-chain transfer</em> is a transaction sent by the payer. The transaction is considered successful after the transaction is packaged and is confirmed by the block-producing node. However, sending transactions comes with a cost:</p><ol><li>There are fees for sending transactions, such as burning <em>gas</em> on Ethereum</li><li>It takes time to confirm the transaction, ranging from minutes to hours</li></ol><p>Considering the cost of money and time, micropayments on the chain become infeasible.</p><p>For example, each time Alice pays 0.01 ETH to Bob, he sends a transfer transaction. The gas fee burned by the transaction may require 0.005 ETH, and the two parties must wait before a second transaction can be performed.</p><p>Obviously, the handling fee here is too high and the efficiency too low.</p><p>Therefore, it is necessary to reduce the number of transactions on the chain and to shorten the waiting time for a transaction.</p><p>Payment channels solve both of these problems. Payment channels are also called state channels (in the strictest sense, payment channels are actually a subset of state channels. The essence of a payment channel is a smart contract from which funds can be held, but where withdrawals from the contract must meet specific conditions.</p><p>According to the payment direction, payment channels can be divided into one-way payment channels and two-way payment channels.</p><p>Taking a one-way payment channel as an example, Alice can escrow money in the payment channel in advance, and specify in the contract that the receiver can only be Bob. Then for each payment, Alice gives Bob a credit under the chain. The credit contains <em>the address of the channel, the amount paid, the Nonce value, and Alice’s signature</em>. When Bob receives the voucher, he can withdraw money from the payment channel contract. However, Bob does not need to withdraw the money as soon as he receives the voucher; he can withdraw the entire transaction with the last voucher.</p><p>The reason for this is that the voucher is an incremental payment credential e.g. the amount of Alice’s first payment credit to Bob is 0.01 ETH, the second payment credit is 0.02 ETH, and so on. Therefore, as long as Bob receives the new, larger amount of credits after each transaction, the old smaller amount then becomes useless. Bob only needs to keep the latest and valid voucher. After the transaction is over, Bob can use this voucher to withdraw the money.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/0*Rq0K6TNMhwsHS2xF" /><figcaption>Using a payment channel will reduce the number of on-chain transaction</figcaption></figure><p>Based on the payment channel, and in the case that both parties are being honest, generally, only two transactions on-the-chain are needed to complete the transaction between the two parties. This greatly improves transaction efficiency and reduces transaction costs.</p><h3>3. Probabilistic Micropayments</h3><p>Although a one-to-one payment method mentioned above can be implemented, a more realistic scenario will require a method that offers a<em> one-to-many</em> payment.</p><p>For example, a user requests to download3 the same resource from several different servers in order to complete the download more quickly. The user would then need to establish a payment channel with multiple download service providers. Each download service provider would submit a payment on the chain after the download is completed. This puts a lot of pressure on the chain.</p><p>And this is where probabilistic micropayments do their magic.</p><p>Probabilistic micropayments are the addition of probability to micropayments. Simply put, the recipient will receive the payment with a certain probability, and the <em>mathematical expectation</em> of receiving that payment is the same as that of receiving the payment.</p><p>For example:</p><p>Alice is dealing with two service providers at the same time. If the standard one-way payment channel is followed, Alice will create two smart contracts on the chain, one for each provider, and then will put an advance payment into two payment channels. As before, a credit of ETH 0.01 is then sent to each service provider, and withdrawal is required for each service provider.</p><p>If Alice used a probabilistic micropayment scheme, then she only needs to make a one-time advance payment into a contract, and then pay 1 ETH to the service provider with a probability of 1%. If the total number of services used by Alice does not change, then only one service provider, in probability, will receive a credit of 1 ETH.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/0*I6B7TpJsdpenjvmU" /><figcaption>Probabilistic micropayments can further reduce the number of on-chain transactions</figcaption></figure><p>Of course, since it is probabilistic, there will be a special case where Alice wins <em>n</em> prizes while using the service, so Alice actually pays <em>n</em> ETH. Here <em>n</em> can be greater than 1 (paying more than 1 ETH) or it can be equal to 0 (not paying, resulting in a free service). But in the long run in the example above, Alice’s average payment will approach the mathematical expectation of 1 ETH * 1% = 0.01 ETH.</p><p>In other words, as long as Alice uses probabilistic payments for a long time, she will not lose or make a profit.</p><h3>4. Principle of Probabilistic Micropayments</h3><p>What is the principle behind probability payments?</p><p>The answer is randomness.</p><p>Before Alice makes a probabilistic payment to Bob, Bob will randomly generate a secret number. Then Bob will send the abstract of the secret, namely the <em>Hash(secret)</em>, to Alice.</p><p>Each value sent as follows:</p><ul><li><strong>ChannelAddress</strong> is the address of the payment channel</li><li><strong>BobAddress</strong> is the address of Bob’s wallet</li><li><strong>Nonce</strong> refers to the value of Nonce in the channel; used for anti-replay</li><li><strong>FaceValue</strong> is the denomination value, such as 1 ETH</li><li><strong>WinProp </strong>is the winning ratio multiplied by 2 ^ 256, For example, WinProp = 0.01 * (2 ^ 256) which corresponds to a 1% chance of winning</li></ul><p>After Bob receives the vouchers, he can judge whether he has won the prize or not by the following methods:</p><p>Bob calculates h1 =Hash(ChannelAddress, Hash(secret), BobAddress, Nonce, FaceValue, WinProp, SigAlice), h2 =Hash(h1, secret). If h2 &lt; WinProp wins, Bob can use this voucher to withdraw money from the channel.</p><p>Since Alice does not know Bob’s secret number at the moment she signs the voucher, Alice cannot construct a signature so that Bob cannot win. At the same time, Bob did not have Alice’s signature on the voucher at the moment when he randomly generated his secret number, so he couldn’t construct a secret that was guaranteed to win.</p><p>This shows that neither side can cheat. The only factor that makes a payment successful is probability.</p><h3>5. To Sum It Up</h3><p>A probabilistic micropayment is an interesting payment idea. It is equivalent to aggregating multiple micropayments through probability. This aggregation also makes for fewer transactions on-the-chain.</p><p>Payments in traditional payment schemes are deterministic. For each payment, the payer will pay the withdrawal voucher, which includes a fee, to the payee. With this withdrawal voucher, the payee must mention the payment in the chain channel contract. In short, if the payer pays, the payee will receive the money.</p><p>In a probabilistic micropayment scheme, the payer does not pay the recipient a withdrawal voucher for each payment operation. Instead, an uncertain withdrawal voucher is paid. This new type of voucher is similar to a “lottery ticket”. After receiving this type of lottery ticket, the payee can draw the prize. If the payee wins, then the ticket becomes a definite withdrawal voucher, which can be mentioned in the contract of the channel on the chain. If the payee doesn’t win, the ticket becomes worthless. The winning factor depends entirely on randomness. Neither the payer or the payee unilaterally controls it.</p><p>The uncertainty of probabilistic micropayment has its advantages and disadvantages:</p><p>1. Sometimes, it will cause the payer to pay more than the actual payable amount, which is equivalent to an overpayment. Other times it will cause the service party to lose meaning they won’t be paid.</p><p>2. Although probabilistic micropayment has its advantages in a one-to-many payment scenario, this type of payment method also essentially increases the risk of double-spending. Therefore, the payer must mortgage enough funds in the contract to reduce this risk and make the service party willing to trade with it.</p><p>As a result, the use of probabilistic micropayments needs to be determined according to real-life scenarios where it will be used. What we have learned from probabilistic micropayments is not only a technical solution but also its idea. It teaches us that certainty and efficiency can be transformed into each other within a certain range.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d083fcc502de" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ppio/how-micropayments-will-save-the-blockchain-d083fcc502de">How Micropayments Will Save The Blockchain</a> was originally published in <a href="https://medium.com/ppio">ppio</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to Generate a Groth16 Proof for Forgery]]></title>
            <link>https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd?source=rss-43af36c6ceea------2</link>
            <guid isPermaLink="false">https://medium.com/p/9f857b0dcafd</guid>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[groth]]></category>
            <dc:creator><![CDATA[Xin Jiang]]></dc:creator>
            <pubDate>Thu, 21 Nov 2019 09:47:13 GMT</pubDate>
            <atom:updated>2019-11-28T11:10:47.091Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*zSi6moTzgB2Cqc9w" /></figure><p><em>We explore how an attacker can generate a new and valid proof based on an existing Groth16 proof without having to obtain the witness of the prover.</em></p><h3>1. Introduction and Background</h3><p>Groth16 is one of the most famous zkSNARK proving schemes. There are also other proving schemes, such as PGHR13, GM17. Compared with early proving schemes, Groth16 has a smaller proof size (only two 𝔾₁ elements and one 𝔾₂ element) and a faster proving &amp; verification speed (only one equation needs to be verified). Groth16 has been widely used in many projects, such as Zcash, Filecoin, etc.</p><p><strong>G</strong>roth<strong>16</strong> is a zero-knowledge proof protocol proposed by Daniel <a href="https://eprint.iacr.org/2016/260.pdf">Jens <strong>G</strong>roth</a> in the paper “<a href="https://eprint.iacr.org/2016/260.pdf">On the Size of Pairing-based Non-interactive Arguments</a>” published in 20<strong>16</strong>.</p><p>Please note that the name of the general algorithm is composed of the first letter of the author’s surname and the year. Similar ways of naming algorithms include <strong>GGPR13</strong> — an algorithm proposed by Rosario <strong>G</strong>ennaro, Craig <strong>G</strong>entry, Bryan <strong>P</strong>arno, Mariana <strong>R</strong>aykova in 2013 in the paper “<a href="https://eprint.iacr.org/2012/215.pdf">Quadratic Span Programs and Succinct NIZKs without PCPs</a>”.</p><h3>2. An Overview of the Groth16 Algorithm</h3><p>Like other QAP-based algorithms, in a Groth16 scheme, a prover needs to prove that he knows a secret called <em>witness </em><em>(aₗ₊₁, aₗ₊₂, …, aₘ)</em> which satisfies the following equation with public <em>statement (a₁, a₂, …, aₗ)</em> and <em>a₀ = 1.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*bTn_H_8O_SvfZe9V" /></figure><p><em>uᵢ(X),vᵢ(X),wᵢ(X),h(X),t(X)</em> in the above equation is related to the specific problem to be proved and is not related to the secret <em>witness </em>held by the prover and the public <em>statement</em>.</p><h4>2.1 Setup Phase</h4><p>In the setup phase, pick <em>α, β, γ, δ, x ← ℤₚ*</em>, define <em>τ = (α, β, γ, δ, x)</em>, and compute <em>σ=([σ₁]₁, [σ₂]₂),</em> where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/978/0*VOjF6GZg1rhakoq2" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/451/0*Qkv41VI-2hxMEFKD" /></figure><p>Here <em>[σ₁]₁</em> are elements on the elliptic curve 𝔾₁. Also <em>[σ₂]₂</em> are elements on the elliptic curve 𝔾₂.</p><p>Please note: After the calculation of <em>[σ₁]₁</em>, <em>[σ₂]₂</em> is completed, the original random parameter sets <em>σ₁</em> and <em>σ₂</em> need to be discarded. They are also known as “<strong>toxic waste</strong>”. If they are not discarded, the entire system will be considered unsafe, because a person who knows <em>σ₁</em> and <em>σ₂ </em>can generate false proof without the<em> </em><em>witness</em>.</p><h4>2.2 Proving Stage</h4><p>The prover randomly picks <em>r, s</em> ← ℤₚ and uses witness <em>(aₗ₊₁, aₗ₊₂, …, aₘ)</em>, statement <em>(a₁, a₂, …, aₗ)</em> and <em>a₀ = 1</em> to compute proof <em>π = ([A]₁, [C]₁, [B]₂)</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/0*zx98-vTAh1X-bFFU" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/523/0*k3r_AyFn0zJPnM2I" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*D0bfP3ci5bgq63WS" /></figure><h4>2.3 Verification Phase</h4><p>Substitute statement <em>(a₁, a₂, …, aₗ)</em> and <em>a₀ = 1</em> to verify that the following equation is equal.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ihjNRGCM6l6hbc89" /></figure><p>If equal, proof <em>π = ([A]₁, [C]₁, [B]₂)</em> is correct; otherwise, proof <em>π</em> is invalid.</p><h3>3. The Security of Groth16</h3><p>Groth16 has a qualitative leap in efficiency compared to previous proof algorithms, however, attention should be paid to security when employing it. If you are not careful, you can make vulnerabilities. The famous open source project <a href="https://github.com/Zokrates/ZoKrates">Zokrates</a> in its <a href="https://zokrates.github.io/reference/proving_schemes.html#g16-malleability">tutorial </a>states:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*fRkm5YM8oxZFYBW-" /></figure><p>The core point of this description is that an attacker can generate a new and valid proof based on an existing Groth16 proof without having to obtain the witness of the prover. But the methods to generate such a proof are not mentioned in the paper. This aroused great interest. In response, I carefully read the Groth16 thesis hoping to find some clues.</p><p><strong>Note: </strong>Groth16 has a malleability problem, and no vulnerabilities have been found on the algorithm so far. However, when designing a system with Groth16, if you do not pay attention to the malleability problem, the system may cause a vulnerability.</p><h3>4. Attack Idea</h3><p>As described in the <a href="https://github.com/Zokrates/ZoKrates">Zokrates</a> <a href="https://zokrates.github.io/reference/proving_schemes.html#g16-malleability">tutorial</a>, we can see that the proof generated by the attacker must be generated based on an existing and correct proof.</p><p>First, we can observe and verify the equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*qk2Sczvhmm3DAzam" /></figure><p>It seems we can come to the idea that if the attacker can construct a new proof <em>π’ = ([A’]₁, [C’]₁, [B’]₂) </em>based on the existing proof <em>π = ([A]₁, [C]₁, [B]₂)</em>, and satisfy the following equation with <em>π’ = ([A’]₁, [C’]₁, [B’]₂)</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*1GCu5VgduiYk7NYC" /></figure><p>then the attacker achieves.</p><p>From here:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/149/0*FGaprcgt06LkrEnl" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/238/0*QzVTBDmolHREMuuk" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/248/0*rWYOlrC14VKoPoOi" /></figure><p>Then:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*_8MT7duc3QrNGJMn" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*DxoxWA19TIAJzlAG" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*kKtjDk9MQyfkFDGI" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*3hQtW_zmoWz8gKr5" /></figure><p>Then obtain evidence. More generally, pick a random number <em>η</em> ← ℤₚ, and <em>η</em> ≠ 0, construct</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/274/0*-NygecfJczds1Ami" /></figure><p>You can then make the verification equation</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Ljb0Sl5QqMiSCVmJ" /></figure><p>Of course, there are other construction methods. For example, <a href="https://github.com/huyuguang"><strong>Yuguang Hu</strong></a> of <a href="https://secbit.io/"><strong>Secbit </strong></a>proposed a better construction method: Select a random number <em>x</em> ← ℤₚ, and <em>x</em> ∉ {0, 1}, to make</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/177/0*kTUSbaoJ2HicFlJO" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/0*8HWr1alwgCNHa7Op" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/152/0*fmV3cz_GZDHbo_r9" /></figure><p>This way is simpler, smarter and easier to understand.</p><p>Of course, you can also use there two ways together.</p><h3>5. Attack Practice</h3><p>It is clear in theory, but it needs to be verified by practice. To test it, we can experiment with the “<a href="https://zokrates.github.io/sha256example.html#prove-knowledge-of-pre-image"><strong>sha256</strong></a>” example in the <strong>Zokrates </strong>tutorial.</p><p>In this example, the prover generates zkSNARK proof to prove that he knows the pre-image 5 of sha256 0xc6481ee2c5ff4164af680b8cfaa5e8ed3120eeff89c4f307c4a6faaae059ce10. It is suggested to try this <a href="https://zokrates.github.io/sha256example.html#prove-knowledge-of-pre-image"><strong>example </strong></a>first, and then read on.</p><p>Note that the default proving scheme for Zokrates is Groth16 and the elliptic curve based on it is<strong> alt_bn128</strong> (also known as bn256).</p><h4><strong>5.1 Compiler Circuit</strong></h4><p>First, use the circuit in the example directly:</p><pre>import “hashes/sha256/512bitPacked” as sha256packed</pre><pre>def main(private field a, private field b, private field c, private field d) -&gt; (field):<br> h = sha256packed([a, b, c, d])<br> h[0] == 263561599766550617289250058199814760685<br> h[1] == 65303172752238645975888084098459749904<br> return 1</pre><p>Save it as <em>hashexample.zok</em> and compile</p><pre>./zokrates compile -i hashexample.zok</pre><p>The compiled circuit will be saved in the<em> out</em> file by default.</p><h4>5.2 Setup</h4><p>Next initialize the circuit,</p><pre>./zokrates setup</pre><p>By default, this command reads the circuit in the <em>out</em> file, initializes it, and writes vk to <em>verification.key </em>and pk to <em>proving.key</em>. For the verification.key, we will use the delta (<em>δ</em>).</p><p>The delta (<em>δ</em>) in <em>verification.key</em> generated by this initialization is:</p><pre>…<br>vk.delta = [0x08d8de30e1b96070599f473822831a5c84675e1ae26d38df88065be710c1ae51, 0x16d8e6761d0e470349897bb92b9a29f50934f76b8208226baef2f107a1914ec4], [0x141806f6a7fc82fbb2b73b544fe06902d2fb0c0ef68531801d92c2937a6d39a3, 0x2587d44143e5ef58550d5691ae14f73ed529cc756b619e4bb10bc7ed02c993a3]<br>…</pre><p>Note: this delta (<em>δ</em>) represents a point on <strong>alt_bn128</strong> (𝔾₂). The abscissa <em>x</em> and ordinate <em>y</em> of each point on <strong>alt_bn128</strong> (𝔾₂) are complex numbers, and each complex number has an imaginary part and a real part. Therefore, four values are required to represent such a point.</p><p>Then we can directly generate the smart contract code to verify the proof</p><pre>./zokrates export-verifier</pre><p>The command generates a smart contract code based on the <em>verification.key</em> and saves it in <em>verifier.sol</em>. This smart contract can be deployed directly to Ethererum.</p><h4>5.3 Generating Proof</h4><p>Next, we calculate the <em>witness</em> according to the <em>private input</em></p><pre>./zokrates compute-witness -a 0 0 0 5</pre><p>Then, according to the <em>witness</em>, we generate proof</p><pre>./zokrates generate-proof</pre><p>The proof will be saved in the <em>proof.json </em>file</p><pre>{<br> “proof”: {<br> “a”: [“0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”, “0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1”],<br> “b”: [[“0x04567073d4db9932c4e6fec8c5c715bbc7d981bbd2771aba57988bedaf2654f7”, “0x1fcbe2f4653402e614d7a5aee078180a6063869c139b352450184015387d0d4f”], [“0x0b6f1e65d68b60e377194800473d1f06498ee37ac14d814732fd9858b1ffa102”, “0x03faefb041fee3b4c82eaa96c278c55c09d5937a7101d66bd1dc9e30366e1fba”]],<br> “c”: [“0x000f6a3ba957a10e387494b36da172de81e71db3fbb3cf131122439c10c3c35e”, “0x1ed51ff80897f736c03ac95176e48272c3bb4573262d271aeceaaed89707c428”]<br> },<br> “inputs”: [“0x0000000000000000000000000000000000000000000000000000000000000001”]<br>}</pre><h4>5.4 Implementation of Attack</h4><p>The attack process involves replacing <em>b</em> and <em>c</em> in the above proof.json file with <em>b + ηδ</em> and <em>c + ηa</em> respectively. To keep it simple, let’s set <em>η</em> = 1.</p><p>Note that “+” here is the addition of two points on the elliptic curve, not the simple addition of numbers.</p><p>We need to write some code to complete this process.</p><p><strong>Note:</strong> as mentioned earlier, Zokrates uses the curve of <strong>alt_bn128</strong>. We need to find the corresponding library of <strong>alt_bn128</strong> to help us to calculate the points on the elliptic curve. The good news is that it’s in Ethereum and it’s <a href="http://ethereum/go-ethereum/crypto/bn256/cloudflare">used out of the box</a>.</p><p>Next, write a simple program (<a href="https://github.com/caiyesd/gen-g16-proof/blob/master/main.go">gen-g16-proof</a>) to calculate <em>[B’]₂ = [B + ηδ]₂</em>, <em>[C’]₁ = [C + ηA]₁</em> according to <em>[A]₁, </em><em>[C]₁, </em><em>[B]₂, </em><em>[δ]₂</em>:</p><p><strong>Note</strong>: <em>[δ]₂</em> in the above procedure comes from the verification.key, whereas <em>[A]₁, </em><em>[B]₂, </em><em>[C]₁</em> from <em>proof.json</em>. Integrate them into <em>input.json</em> (<a href="https://github.com/caiyesd/gen-g16-proof/blob/master/input.json">reference format here</a>).</p><p>Execute command:</p><pre>gen-g16-proof -i input.json -o output.json</pre><p>After that, new <em>[B’]₂</em> and <em>[C’]₁</em> values can be obtained in <em>output.json</em> (<a href="https://github.com/caiyesd/gen-g16-proof/blob/master/output.json">reference format here</a>).</p><p>Note: The reader needs to replace <em>delta, </em><em>a, </em><em>b, </em><em>c</em> in the above <em>input.json</em> according to the value generated by his own runtime. And get the newly calculated <em>b</em> and <em>c</em> from <em>output.json</em>.</p><p>Replace the values of <em>b </em>and <em>c</em> in <em>output.json</em> with <em>b</em> and <em>c</em> in the original <em>proof.json</em> and save as <em>proof2.json</em>. See below:</p><pre>{<br> “proof”: {<br> “a”: [“0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”, “0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1”],<br> “b”: [[“0x302d34ff018f8abeea4b0ea206048a8c69c8cc8d4f7ddcc1bd613dcb539de567”, “0x0927c6aac8cf8b3cf7534f06d80b791f07725ad1ee3a5246c6a6bd5533335ff4”], [“0x29140540827fad8c7f4b55877678ffa1c52d4a72a49f25c83495d18e9aa1b358”, “0x23533b6d3c4df0aa49924cc9462aa1e278b4c58d3037a9bc9ab4026a18fbeefb”]],<br> “c”: [“0x1de4d89b61640eead90df97fe4fcf7c76509941094657406caf0ec71c83bf537”, “0x26c6778ea34fb888c44ba3a4c0e53fb6b83c90c0759201efe23886a85670018c”]<br> },<br> “inputs”: [“0x0000000000000000000000000000000000000000000000000000000000000001”]<br>}</pre><p>Next, according to <em>proof.json</em> and <em>proof2.json</em>, the parameters of calling the smart contract are generated respectively. Here, <em>proof2.json</em> is constructed by the attacker based on <em>proof.json</em>.</p><pre><strong>$ ./zokrates print-proof -f remix -j proof.json</strong></pre><pre>[“0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”,”0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1&quot;],[[“0x04567073d4db9932c4e6fec8c5c715bbc7d981bbd2771aba57988bedaf2654f7”,”0x1fcbe2f4653402e614d7a5aee078180a6063869c139b352450184015387d0d4f”],[“0x0b6f1e65d68b60e377194800473d1f06498ee37ac14d814732fd9858b1ffa102”,”0x03faefb041fee3b4c82eaa96c278c55c09d5937a7101d66bd1dc9e30366e1fba”]],[“0x000f6a3ba957a10e387494b36da172de81e71db3fbb3cf131122439c10c3c35e”,”0x1ed51ff80897f736c03ac95176e48272c3bb4573262d271aeceaaed89707c428&quot;],[“0x0000000000000000000000000000000000000000000000000000000000000001”]</pre><pre><strong>$ zokrates print-proof -f remix -j proof2.json</strong></pre><pre>[“0x282f666473dbcc1a4c4c3d39dca1bc7e5014ee3ad3e2732b3894715d2587e035”,”0x10b8cab5c7bc0d142efac1ce2b984a8721dd7114a38ab59717660fcb7fbb9bc1&quot;],[[“0x302d34ff018f8abeea4b0ea206048a8c69c8cc8d4f7ddcc1bd613dcb539de567”,”0x0927c6aac8cf8b3cf7534f06d80b791f07725ad1ee3a5246c6a6bd5533335ff4&quot;],[“0x29140540827fad8c7f4b55877678ffa1c52d4a72a49f25c83495d18e9aa1b358”,”0x23533b6d3c4df0aa49924cc9462aa1e278b4c58d3037a9bc9ab4026a18fbeefb”]],[“0x1de4d89b61640eead90df97fe4fcf7c76509941094657406caf0ec71c83bf537”,”0x26c6778ea34fb888c44ba3a4c0e53fb6b83c90c0759201efe23886a85670018c”],[“0x0000000000000000000000000000000000000000000000000000000000000001”]</pre><p>Finally, deploy the <em>verifier.sol</em> generated in the setup phase to the Ethereum network, and call the <em>verifier.verifyTx()</em> method with the parameters of the above call contract.</p><p>In the research of this article, the following results were obtained on the<em> rinkeby</em> network.</p><ul><li>verifier contract: <a href="https://rinkeby.etherscan.io/address/0x46d6b34cdfc3dd78ab471132c8884444b3914a1f">0x46d6b34c…</a></li><li>proof.json: <a href="https://rinkeby.etherscan.io/tx/0x728ddfc2c21ef3f1122532eb5429f2380bd4ea6834ca732de53aae1eba50b69a">0x728ddfc2…</a></li><li>proof2.json: <a href="https://rinkeby.etherscan.io/tx/0x91f65d9d651d5675a1a99f61eab325b7d9f6d64a0278392f1c99d6057552d977">0x91f65d9d…</a></li></ul><p>You can also try to modify eta (<em>η</em>) in the <em>input.json </em>or try other ways<em> </em>to construct a more effective proof.</p><h3>6. How To Defend</h3><p>There are four suggested ways to defend. We will use Zokrates once again as a reference:</p><ul><li><strong>Signed proofs</strong></li></ul><p>A requirement is to submit the zkSNARK proof and the prover’s signature together. In this way, even if an attacker forges a proof, the prover’s signature cannot be forged.</p><ul><li><strong>Nullifiers</strong></li></ul><p>Consider some or all of the public input in the proof as a nullifier. Since the above attack method cannot change the public input, the nullifier can only be used once, which can effectively prevent such attacks.</p><ul><li><strong>Usage of an Ethereum address as a public input to the program</strong></li></ul><p>Consider making the address (<em>msg.sender) </em>that submits the proof as part of the public input. However, this requires the circuit to be taken into account when designing.</p><ul><li><strong>Usage of non-malleable schemes such as GM17</strong></li></ul><p>The last method is to change to other proving schemes. This is obvious, but it loses the advantage of the efficiency of Groth16.</p><h3>7. Summary</h3><p>Groth16 is an excellent zkSNARK proving scheme as the size of the proof is smaller, and the speed of generating and verifying the proof is faster. Groth16 is a technically mature proof and has been widely used in various types of projects including Zcash and Filecoin, among others.</p><p>When a new system is designed with Groth16, it’s important to consider the possibility that an attacker may generate a new proof with a disclosed proof. Therefore the system designer should not use Groth16 straight away; instead, consideration towards specific business scenarios and potential attack models are needed before implementation. From there, appropriate measures can be taken to avoid defects and loopholes.</p><ol><li>G16 Paper <a href="https://eprint.iacr.org/2016/260.pdf">On the Size of Pairing-based Non-interactive Arguments</a>, <a href="http://www0.cs.ucl.ac.uk/staff/j.groth/">Jens Groth</a>.</li><li>Zokrates <a href="https://zokrates.github.io/reference/proving_schemes.html#g16-malleability">g16 malleability</a></li><li>Zokrates <a href="https://zokrates.github.io/sha256example.html#prove-knowledge-of-pre-image">sha256 example</a></li><li>Ethereum <a href="https://github.com/ethereum/go-ethereum/crypto/bn256/cloudflare">bn256 library</a></li><li><a href="https://github.com/caiyesd/gen-g16-proof/blob/master/main.go">gen-g16-proof</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9f857b0dcafd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd">How to Generate a Groth16 Proof for Forgery</a> was originally published in <a href="https://medium.com/ppio">ppio</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ZK Rollup: Making Scalable Blockchains Possible]]></title>
            <link>https://medium.com/ppio/zk-rollup-making-scalable-blockchains-possible-7308b695d929?source=rss-43af36c6ceea------2</link>
            <guid isPermaLink="false">https://medium.com/p/7308b695d929</guid>
            <category><![CDATA[layer-2]]></category>
            <category><![CDATA[zkrollup]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <dc:creator><![CDATA[Xin Jiang]]></dc:creator>
            <pubDate>Fri, 01 Nov 2019 12:01:57 GMT</pubDate>
            <atom:updated>2019-11-04T09:04:11.561Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aX9pvL_YJVN5gaWQJg1s0Q.jpeg" /></figure><p><strong>A clever way to make layer 2 scaling possible, we explain what is a ZK Rollup.</strong></p><p>The creation of blockchain technology was a paradigm-shifting event that created a system of trust without the reliance of a third-party authority. But the implementation of this revolutionary technology continues to pose a significant challenge related to efficiency: transactions per second (TPS) are not high enough to compete against preexisting systems. Take Bitcoin which only supports 7 transactions per second or Ethereum with 15 per second, and then contrast that with a payment provider like <a href="https://usa.visa.com/dam/VCOM/download/corporate/media/visanet-technology/aboutvisafactsheet.pdf">Visa which can process 65,000 per second</a>. For blockchain to support large-scale applications, new technology is needed — which is exactly what a number of labs, scientists, and developers are working on. At present, there are two major layer expansions that address this issue:</p><p><strong>Layer 1 Scaling: </strong>Directly increase the transaction processing capacity on the chain; also known as on-chain scaling. Common technical solutions are sharding and DAG.</p><p><strong>Layer 2 Scaling: </strong>A considerable part of the workload is performed off-chain before being transferred on-chain once complete. Common technologies include <a href="https://medium.com/ppio/ppio-state-channel-design-42ae695ed3c">State Channel</a>, Plasma, Truebit, and the recently popular ZK Rollup.</p><h3><strong>Principle</strong></h3><p>The essence of a ZK Rollup is to compress and store the user state on-chain in a Merkle tree, and transfer the state transition of the user states to the off-chain. At the same time, a zkSNARK proof is used to ensure the correctness of the off-chain state transition. The cost of changing the user state directly on the chain is relatively high, whereas the cost of using a smart contract on the chain to verify whether a zero-knowledge proof’s <em>proof</em> is correct is relatively low. In addition, the necessary transfer information is submitted to the contract together to facilitate the user to check the account. Here is how it works.</p><h3><strong>Two Types of Roles</strong></h3><p><strong>Transactor</strong>: A normal user. This role corresponds to an external account on Ethereum. The user builds the transfer transaction and signs it with the private key before sending the transaction to the relayer.</p><p><strong>Relayer</strong>:<strong> </strong>Responsible for collecting and verifying the user’s transaction, then packaging the transaction in batches, and generating the proof of zkSNARK. The relayer finally submits the core data of the user’s transaction, the proof of zkSNARK, and the Merkle root of the new user states to the smart contract on the chain.</p><p>Of course, the relayer will not provide services for the transactor free of charge. After all, the relayer needs to consume gas to submit the zkSNARK proof and the transaction data to the chain. Therefore, the transaction sent by the transactor to the relayer must also include the corresponding handling fee.</p><h3><strong>State Transition Function</strong></h3><p>When the relayer receives the transaction, it must <em>“execute”</em> it. The execution of a transaction essentially changes the status of the related account. The state transition function (STF) is the function to change the status of those accounts.</p><p>The state is for the state machine, and each state machine has a state at some point. We can assume that the initial state of a state machine is <em>S[0]</em>. When an Action <em>T[1]</em> is applied to the state machine, the <em>state</em> of the state machine migrates. We can use the following formula to represent the migration process.</p><pre>S[1] = STF(S[0], T[1])</pre><p>Here, <em>S[0]</em> is the initial state, and <em>S[1]</em> is the state after the state machine executes Action <em>T[1]</em>.</p><p>Then there are several new actions <em>T[2], T[3], …, T[n]</em>that continue to act on the state machine, and the state of the state machine will migrate in turn.</p><pre>S[2] = STF(S[1], T[2])</pre><pre>S[3] = STF(S[2], T[3])</pre><pre>…</pre><pre>S[n] = STF[S[n-1], T[n]]</pre><p>Simply put, we can also <em>T[1], T[2], …, T[n]</em>. As a whole, the state migration process can be simplified to:</p><pre>S[n] = STF(S[0], T[1], T[2], …, T[n])</pre><p>More generally, assuming that the state of the current state machine is <em>PRE_STATE</em>, then there are <em>n</em> number of actions <em>T[1], T[2], …, T[n] </em>acting in turn on the state machine, after which the state of the state machine enters <em>POST_STATE</em>. This can be expressed as:</p><pre>POST_STATE = STF(PRE_STATE, T[1], T[2], …, T[n])</pre><p>If the above action is replaced by a transfer transaction, and the account set in the system is regarded as a state machine, then the whole process is merely the process of transaction execution on the chain. The execution of this transaction changes the global state of the whole chain. The global state on the chain is also the state collection of each account. The state of all accounts is composed into a Merkle tree. The leaf nodes of the tree are the account states, and the root of the tree can be used to represent the state collection. Therefore, <em>PRE_STATE</em> and <em>POST_STATE</em> are also the roots of the global account status tree.</p><h3><strong>Account Status Model</strong></h3><p>The account states of the whole system in the chain can be managed by a Merkle tree. The leaf node of Merkle tree is the users’ status information. Similarly, ZK Rollup can also use a similar Merkle tree to organize its account status.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*oTRHUIQrFhk9tKXD" /></figure><p>The simplest account state can include the public key, nonce, and balance of the account. The leaf node has a unique location in the Merkle tree, so the index of the location can indirectly reference this account information.</p><p>If we use three bytes to represent the index information, this Merkle tree can support a total of 2²⁴ = 16777216 accounts. This is enough for a general system. Therefore, for example, the account address of Ethereum<strong> </strong>can be changed from an address with 20 bytes to just 3 bytes of the leaf node index of the Merkle tree. In this way, the account address becomes “compressed”.</p><p>In addition to compressing the account address, we can also compress the transfer amount data. For example, for Ethereum the amount is represented by a 256 bit large integer, but there is actually little need to use a super large or super small amount here. If we assume that the minimum unit of transfer in the system is 0.001 ETH, and the transfer amount is represented by 4 bytes, we can support the transfer of 0.001–4,294,967.295 ETH, which is enough for the general system. If there is a situation where it is not enough, you can add more bytes to represent the amount, or introduce floating-point representation.</p><p>The handling fee is similar to the transfer amount, and the actual handling fee will fluctuate within a certain range, so we can also set a minimum unit for the handling fee, e.g. 0.001 ETH. Then 1 byte is used to represent the handling fee of 0.001–0.255 ETH. In this case the handling fee is paid by the transactor to the relayer.</p><p>Similarly, we can assume that the number of transfers of an account based on normal usage will not number in the tens of thousands, so it is almost enough to use two bytes to represent the nonce of an account because two bytes can represent a range of 0–65535.</p><p>Finally, the signature field cannot be compressed. Taking Ethereum as an example, the signature <em>(r, s, v)</em> requires a total of 65 bytes. In fact, EdDSA signatures are widely used in the ZK Rollup system.</p><p>Therefore, the format of a transaction is roughly as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/401/1*9fO7Mf1nab-BcUxPMDNRQQ.png" /></figure><p>The length of each field in the above transaction is only for reference. When implementing the specific system, it is necessary to adjust the length of the field according to the actual situation to prevent the occurrence of field overflow. However, in principle it can be saved. With less data for transactions, then more transactions can be accommodated while using the same storage capacity.</p><h3><strong>Proof and Verification</strong></h3><p>After understanding the state transition function and the account state model, let’s take a look at what happens after the relayer collects the transaction.</p><p>We just mentioned that in the ZK Rollup system, the account information of all users is managed by a Merkle tree. The root of the Merkle tree is recorded in the smart contract on the chain, and the value of this root also represents the current state of all accounts in the whole system. When a user initiates a transaction, the state will change. But changes must be made in accordance with the following rules.</p><ul><li>First, you must ensure the legitimacy of the transaction:</li><li>Is there enough money to pay the transfer amount and handling fee?</li><li>Is the nonce of the transferred account correct?</li><li>Is the signature of the transaction correct?</li><li>Next, the relayer performs the transfer, modifies the outgoing account in the Merkle tree and the leaf node of the transferred account, and recalculates the root of the new Merkle tree.</li><li>Repeating the second step, the relayer will process multiple transactions at once in a sequential order, and then submit the root of the final calculated Merkle tree as a new state to the smart contract on the chain.</li></ul><p>However, there are problems in the above process: if only the root of the state tree is submitted to the contract, how can users believe that the new state root is truthfully calculated according to the above logic? Or what if the relayer does something intentionally harmful, like increasing the handling fee of the transaction?</p><p>One way to solve this problem is to ask the relayer to commit the root of the state tree to the contract, and also submit all transactions to the contract, so that anyone can verify whether the relayer has cheated when calculating the new state tree according to these transactions. However, this is equivalent to moving all the data under the chain back to the chain, and does not achieve the purpose of layer 2 scaling.</p><p>This problem can be solved by using zero-knowledge proof. The ZK in ZK Rollup is actually the abbreviation of zero-knowledge. After collecting a series of transactions, the relayer needs to generate a PROOF with predefined ZK circuits:</p><ol><li>Make sure that the <em>nonce</em>,<em> value</em>, and <em>fees</em> in each transaction <em>T[1], T[2], …, T[n]</em> are correct and the signature is correct.</li><li>Ensure that there is no problem with the state migration process, i.e. <em>STF(PRE_STATE, T[1], T[2], …, T[n]) = POST_STATE</em></li></ol><p>Then, the PROOF is submitted to the chain contract together with <em>POST_STATE, t[1], t[2], …, t[n]</em>. Where <em>t[1], t[2], …, t[n]</em> is the simplified information of transaction, excluding nonce and signature. So <em>t[i]</em> is smaller than <em>T[i]</em>.</p><p>Then the smart contract only needs to verify whether the <em>PROOF</em> is correct. If the <em>PROOF</em> is correct and the state saved in the contract is equal to the <em>PRE_STATE</em>, then the new state <em>POST_STATE</em> will be recorded in the contract and the original state will be replaced.</p><p>Since the relayer must generate the <em>PROOF</em> of zkSNARK before it can be submitted to the contract, the <em>PROOF</em> will not be validated if the relayer wrongly modifies the user’s transaction.</p><p>In addition, because the transaction <em>t[1], t[2], …, t[n] </em>submitted to the chain does not contain the nonce or signature, the data on the chain will become smaller (in the above example, only 11 bytes for each transaction will be on the chain).</p><p>At this time, the relayer cannot modify the user’s transaction due to the limitation of the zkSNARK proof. However, a malicious relayer can still refuse to serve a transactor without collecting the transactor’s transaction. In order to prevent this kind of behavior, the contract must support on-chain withdrawal; in other words, any transactor can take its token away from the chain.</p><h3><strong>Current Application</strong></h3><p>At present, a typical ZK Rollup application scenario is a decentralized exchange, represented by <a href="https://github.com/Loopring/protocols/blob/master/packages/loopring_v3/DESIGN.md">Loopring DEX Protocol (v3)</a>.</p><p>In addition, the open-source ZK rollup framework includes:</p><ul><li><a href="https://github.com/barryWhiteHat/roll_up">barryWhiteHat/roll_up</a> -C++</li><li><a href="https://github.com/matter-labs/rollup">matter-labs/rollup</a> — rust</li></ul><h3><strong>Summary</strong></h3><p>ZK Rollup is a new type of layer 2 scaling scheme. The core idea of this technology is:</p><ol><li>Take the main chain as the storage medium instead of the consensus engine</li><li>Compress the transaction and reach a state consensus off-chain;</li><li>Prove the security of the state consensus under the chain with zero knowledge proof.</li></ol><p>At present, the most typical application scenario with ZK Rollup is a decentralized exchange. <a href="https://medium.com/ppio">PPIO</a> is also actively exploring ZK Rollup technology and are trying to apply it to the field of decentralized bandwidth and storage.</p><h3><strong>References</strong></h3><ul><li><a href="https://pandax-statics.oss-cn-shenzhen.aliyuncs.com/statics/1221233526992813.pdf">ZK Rollup: scaling with zero-knowledge proofs</a></li><li><a href="https://medium.com/@trenton.v/transcript-scalable-blockchains-as-data-layers-vitalik-buterin-11aa18b37e07">Transcript: Scalable blockchains as data layers | Vitalik Buterin</a></li><li><a href="https://vitalik.ca/general/2019/08/28/hybrid_layer_2.html">The Dawn of Hybrid Layer 2 Protocols</a></li><li><a href="https://docs.google.com/presentation/d/1EVjrZhoxw-ikzelFGGv7czxuJsIIWfl5I-CPIlnjsME/edit#slide=id.g5274d763f8_0_24">Scalable blockchains as data layers</a></li><li><a href="https://www.youtube.com/watch?v=QyM9qdFKsEA">ZK Rollup: Ethereum Scalability with ZKPs</a></li><li><a href="https://ethresear.ch/t/on-chain-scaling-to-potentially-500-tx-sec-through-mass-tx-validation/3477">On-chain scaling to potentially ~500 tx/sec through mass tx validation</a></li><li><a href="https://github.com/Loopring/protocols/blob/master/packages/loopring_v3/DESIGN.md">loopring 3</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7308b695d929" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ppio/zk-rollup-making-scalable-blockchains-possible-7308b695d929">ZK Rollup: Making Scalable Blockchains Possible</a> was originally published in <a href="https://medium.com/ppio">ppio</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Ring Signatures: Privacy Protection So You Can Hide In A Crowd]]></title>
            <link>https://medium.com/ppio/ring-signatures-privacy-protection-so-you-can-hide-in-a-crowd-40180a732bce?source=rss-43af36c6ceea------2</link>
            <guid isPermaLink="false">https://medium.com/p/40180a732bce</guid>
            <category><![CDATA[ring-signature]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Xin Jiang]]></dc:creator>
            <pubDate>Thu, 24 Oct 2019 06:53:09 GMT</pubDate>
            <atom:updated>2019-10-24T07:10:46.458Z</atom:updated>
            <content:encoded><![CDATA[<p>An examination of an essential privacy algorithm so you can maximize your privacy and ensure anonymous transactions on the blockchain.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*4iF7VjIOdU2DFXuy.jpeg" /></figure><p>Privacy is one of the most concerning issues in the 21st century and the subject of a lot of internal research and discussion at PPIO. Given the importance of this issue, there are many technologies related to privacy protection in the blockchain world. Our previous article, <a href="https://medium.com/@ppio/zksnarks-zero-knowledge-proof-feb76bf49e1a">The A-to-Z on zkSnarks</a> discussed why a zero-knowledge proof is ideal for authentication so no one else knows what you’re communicating. Today we will analyze another technology related to privacy: Ring Signatures.</p><p>To recap a zero-knowledge proof means that the prover must convince the verifier that an assertion is correct without revealing any useful information to the verifier. In other words, I need to prove to you that I know a secret, however, I can’t let you know what that secret is. Ring signatures, on the other hand, is where you hear a secret, however, you don’t know which person in a group has said it to you. A ring signature achieves the purpose of protecting the identity of the signer by hiding his public key into a set of public keys.</p><p>Ring signatures were first proposed in 2001 by the three cryptographers: <a href="https://translate.google.com/translate?hl=en&amp;prev=_t&amp;sl=zh-CN&amp;tl=en&amp;u=https://link.springer.com/content/pdf/10.1007%252F3-540-45682-1_32.pdf">Rivest, Shamir, and Tauman</a>. A ring signature, also known as CryptoNote, originally evolved from group signatures. Group signatures are a method for verification by using a group public key and a group signature. The verifier can verify the correctness of the group signature by using the group public key, but cannot determine the formal signer in the group. However, the problem with this method is that the group administrator can revoke the signature and expose the real signer of the group signature.</p><p>Using a ring signature removes the group administrator and does not require cooperation between ring members. The signer can sign independently by using his private key and the public key of the other members in the group. The other members of the group may not know that they are included in it. The advantage of this is that besides the unconditional anonymity of the signer, other members of the ring cannot forge the true signer’s signature. An external attacker also cannot forge a signature even if it is based on a valid ring signature.</p><h3>Application Scenario</h3><p>Currently, several projects that use ring signatures include Monero, Boolberry, StealthCoin, XCurrency, and others. The Ethereum platform also adds a CryptoNote-like ring signature.</p><p><strong>Monero</strong>: Monero is a typical representative of the application of ring signatures. The ring signature technology makes Monero a public-private, <strong>untraceable cryptocurrency</strong>. The ring signature helps Monero realize the privacy of transactions as <strong>unrelated nodes on the </strong>blockchain cannot trace the sender of the transaction. When other nodes verify the transaction, they can only determine that the signature is one of many public keys, they cannot locate which public key is the specific sender.</p><p><strong>One-Vote Veto Scenarios</strong>: For example, a chairman of an association proposes a motion, however, if someone in the association raises an objection, then the bill must be canceled. If in this case, the member who voted against it does not want to reveal his identity, he can use ring signature technology to sign his negative vote with his private key and the public key of the other members of the association. After signing, all members of the association can see that some of the members of the association opposed the bill, however, they do not know who exactly opposed it.</p><p>So how does ring signature do all this? In the next section, we will use elliptic curves to illustrate the key points and principles of a ring signature.</p><p><strong>Interested in understanding elliptic curves? As part of our Code Talks series, we made a presentation on elliptic curves that even a beginner can understand. </strong><a href="https://github.com/PPIO/ppio-blockchain-code-talks/tree/master/ecc"><strong>Click the link</strong></a><strong> to see how they work.</strong></p><h3>How Is A Ring Signature Generated?</h3><p>Suppose the signer has a private key sk and a public key <strong>pk</strong>. Where:</p><pre><strong>pk </strong>= sk·<strong>g</strong></pre><ul><li><strong>g </strong>is the base point on the elliptic curve; also known as a generator</li><li>“·” is scalar multiplication</li><li>sk·<strong>g </strong>means that sk <strong>g </strong>points are added on the elliptic curve</li><li>For convenience, everything <strong>bolded </strong>is represented by points on the elliptic curve</li></ul><h3>Steps To Generate A Ring Signature:</h3><p>● First, the hash function must be defined. The hash function input is a point on the message m to be signed and point <strong>A</strong> on an elliptic curve, i.e., Hash (m, <strong>A</strong>). This hash function, like the elliptic curve, is a prerequisite for the signature and verification system.</p><p><em>A reference implementation of the hash function is that the byte data of M and A are spliced together, then the values obtained by using the traditional hash function (such as keccak256) are modular to N (where N is the order of a finite group on an elliptic curve).</em></p><p>● Next, the signing party wants to sign a message <em>m</em>, but does not want to let others know their identity while signing. The signing party then hides in a group by means of a ring signature. The signing party finds the public keys of <em>n-1 </em>people (keys which have appeared and been used in the system before, otherwise the signer can be easily identified by hiding amongst a group of new people). The signer numbers these keys, and randomly inserts his own public keys into a collection of <em>n</em> public keys. Let’s assume that the <em>n</em> public keys are:</p><pre><strong>pk[0], pk[1], pk[2], …, pk[i-1], pk[i], pk[i+1], …, pk[n-1]</strong></pre><p>Where<em> </em><strong><em>pk[i]</em> </strong>is the public key of the signing party.</p><p>● The signer randomly generates <em>n-1</em> random numbers <em>s[0], s[1], …, s[i-1] , s[i+1], …, s[n-1</em>] respectively. They correspond to <em>n-1</em> public keys except for <strong><em>pk[i]</em></strong><em>.</em></p><p><strong><em>Note: This step does not need to generate s[i] randomly, because s[i] will be calculated later.</em></strong></p><p>● Next, the signer randomly generates <em>k </em>and calculates<em> k·</em><strong><em>g</em></strong>. We can assume:</p><pre><strong><em>Equation 1：</em></strong><em>k·</em><strong><em>g</em></strong><em> = s[i]·</em><strong><em>g</em></strong><em> + c[i]·</em><strong><em>pk[i]</em></strong></pre><p>According to Equation 1, we can determine that if we have the private key <em>sk[i]</em>of<strong> <em>pk[i] </em></strong><em>and if c[i] and k</em> are known, we can find s[i]<strong> </strong>in reverse.</p><p><strong><em>Note: c[i] here is the hash value calculated from the previous public key pk[i-1] and message m</em></strong></p><p>● Next is the introduction of the second formula,</p><pre><strong>Equation 2: </strong>c[x]<strong> </strong>= Hash(m, s[x-1]·<strong>g </strong>+ c[x-1]·<strong>pk[x-1]</strong>)</pre><p><strong>Equation 2 </strong>is a <strong>recursive</strong> formula, and the second parameter form of Hash function is the same as the right side of Equation 1. This recursive formula means that when the <em>s[x-1]</em> and hash value <em>c[x-1]</em> corresponding to the <em>x-1</em> public key are known, the hash value <em>c[x]</em> corresponding to the next public key will be calculated. Note that when <em>x = 0</em>, the previous <em>x</em> is actually <em>n-1</em>, because the subscript also takes a module for n.</p><p>● For equation 1, we define <em>k · </em><strong><em>g </em></strong><em>= s[i]</em><strong><em> </em></strong><em>· </em><strong><em>g </em></strong><em>+ c[i]</em><strong><em> </em></strong><em>· </em><strong><em>pk[i]</em></strong>, therefore <em>c[i +1]</em> can be obtained directly from the calculation:</p><pre>c[i+1]<strong> </strong>= Hash(m, s[i]·<strong>g </strong>+ c[i]·<strong>pk[i]</strong>) = Hash(m, k·<strong>g</strong>)</pre><p><strong><em>Note: At this time</em></strong>, <strong><em>we do not yet know s[i] and c[i] when calculating </em>c[i+1]<em>. Once </em>c[i] is <em>calculated, we can find </em>s[i]<em>.</em></strong></p><p>Next we can sequentially calculate <em>c[i+2] , … , c[n-1] , c[0] , …, c[i-1], c[i]</em>: (Figure 1)</p><pre>c[i+2]= Hash(m, s[i+1]·<strong>g </strong>+c[i+1]·<strong>pk[i+1]</strong>)<br>…<br>c[n-1]<strong> </strong>= Hash(m, s[n-2]·<strong>g </strong>+c[n-2]·<strong>pk[n-2]</strong>)<br>c[0]= Hash(m, s[n-1]·<strong>g </strong>+c[n-1]·<strong>pk[n-1]</strong>)<br>c[1]= Hash(m, s[0]·<strong>g </strong>+c[0]·<strong>pk[0]</strong>)<br>…<br>c[i]= Hash(m, s[i-1]·<strong>g </strong>+c[i-1]·<strong>pk[i-1]</strong>)</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*WMkv4p7kBfKZcucc" /></figure><p><strong>Figure 1: Computational c[i+1], … , c[n-1], c[0], …, c[i-1], c[i] Process</strong></p><p>● Now that c[i] is solved, we can look back at <strong>Equation 1</strong>. As we know that the private key of <strong>pk[i] </strong>is:</p><p><strong>pk</strong>[i] = sk[i] · <strong>g</strong></p><p>Thus <strong>Equation 1 </strong>can be written as</p><pre>k·<strong>g </strong>= s[i]·<strong>g </strong>+c[i]*sk[i]·<strong>g</strong></pre><p>We can then remove <strong>g </strong>on both sides</p><p><em>k = s[i]</em><strong><em> </em></strong><em>+ c[i]</em><strong><em> </em></strong><em>*sk[i]</em></p><p>Thus <em>k, c[i]</em><strong><em> </em></strong><em>, sk[i]</em><strong><em> </em></strong>can be obtained <em>s[i]</em><strong> </strong>(Fig 2), i.e.,</p><p><em>s[i] = k - c[i] *sk[i]</em></p><p><strong><em>Note: The private key </em>sk[i]<em> plays a role here. If there is no sk[i]</em>,<em> then s[i] cannot be found.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ohRSNz3HjuCmeT9D" /></figure><p><strong>Figure 2 solves the s[i] process based on the private key sk[i] , k, c[i]</strong></p><p>● Once s[i] is calculated by <em>k, c[i] and</em><strong><em> </em></strong><em>sk[i]</em>, the “ring” is established; we can then drop <em>k</em>, because it is not needed anymore.</p><p>In other words, because we have the private key <em>sk[i]</em>, we can find <em>s[i]</em> with the randomly generated <em>s[0] , s[1] , …, s[i-1] , s[i+1] , …, s[n-1]</em>, which makes the following formulas true:</p><pre>c[0]<strong> </strong>= Hash(m, s[n-1]·<strong>g </strong>+c[n-1]·<strong>pk[n-1]</strong>)<br>c[1]<strong> </strong>= Hash(m, s[0]·<strong>g </strong>+c[0]·<strong>pk[0]</strong>)<br>…<br>c[n-1]<strong> </strong>= Hash(m, s[n-2]·<strong>g </strong>+c[n-2]·<strong>pk[n-2]</strong>)</pre><p>On the other hand, if the signer doesn’t have any private keys of the <em>n</em> public keys, he cannot calculate s[i] which makes<em> {c[0], </em><strong><em>pk[0]</em></strong><em>, …. </em><strong><em>pk[n-1]</em></strong><em>, s[0], …., s[n-1]}</em> and is needed to form a ring.</p><p>Therefore, if the above n equations are true, it also means that the person who generates the n equations has at least one private key of the n public keys.</p><p>● The ring signature data of the last message m is:</p><p>Signature = {<em>c[0], </em><strong><em>pk[0]</em></strong><em>, …. </em><strong><em>pk[n-1]</em></strong><em>, s[0], …., s[n-1]</em>}</p><h3>Signature Verification Process</h3><p>The verifier obtains <em>c[0], </em><strong><em>pk[0]</em></strong><em>, …. </em><strong><em>pk[n-1]</em></strong><em>, s[0], …., s[n-1]</em>, message m, and <strong>Equation 2, </strong>then<strong> </strong>finds <em>c[1] , c[2] , …., c[n-1]</em><strong>.</strong> Finally, <em>c[0]’</em><strong> </strong>is calculated according to <em>c[n-1]</em><strong> </strong>and judged</p><pre>c[0]<strong> </strong>?= <em>c[0]’</em></pre><p>If they are equal, the signature is valid; if not, the signature is invalid.</p><h3>In Summary</h3><p>Looking back at the entire process of generating a ring signature, if you know the private key <em>sk[i]</em>, then you can deduce s[i] so that <em>c[1]</em><strong><em> </em></strong><em>, c[2]</em><strong><em> </em></strong><em>, …., c[n-1]</em><strong> </strong>forms a ring. Another way of thinking about it is if you want to loop a wire. The mathematics guarantees that only the person with the private key can connect the two ends of the wire to form a loop. Moreover, once it becomes a loop, there is no trace at the joint, which makes it impossible for someone to judge where the wire was connected.</p><p>Although the ring signature can be used to achieve a certain degree of anonymity, the real signer will still be exposed in the ring. In the current public chain market, the zero-knowledge proof is still one of the best means to stay anonymous. That is not to say that ring signatures do not have their place or are not helpful — they are. If privacy requirements are not so high, or the signing party’s computing power is weak, a ring signature is an excellent choice.</p><h3>Want more? Join the <a href="http://buff.ly/2J36IoK">PPIO community on Discord</a> or follow us on <a href="https://twitter.com/pplabs_ppio">Twitter</a>.</h3><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=40180a732bce" width="1" height="1" alt=""><hr><p><a href="https://medium.com/ppio/ring-signatures-privacy-protection-so-you-can-hide-in-a-crowd-40180a732bce">Ring Signatures: Privacy Protection So You Can Hide In A Crowd</a> was originally published in <a href="https://medium.com/ppio">ppio</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>