<?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 Grayblock on Medium]]></title>
        <description><![CDATA[Stories by Grayblock on Medium]]></description>
        <link>https://medium.com/@grayblock?source=rss-b87d8eb3b46c------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*22i9k8CGAHMabu_ikHSOSg.png</url>
            <title>Stories by Grayblock on Medium</title>
            <link>https://medium.com/@grayblock?source=rss-b87d8eb3b46c------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 00:20:05 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@grayblock/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[Mimblewimble in IoT]]></title>
            <link>https://medium.com/coinmonks/mimblewimble-in-iot-72cdec6bedec?source=rss-b87d8eb3b46c------2</link>
            <guid isPermaLink="false">https://medium.com/p/72cdec6bedec</guid>
            <category><![CDATA[mimblewimble]]></category>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[anonymity]]></category>
            <dc:creator><![CDATA[Grayblock]]></dc:creator>
            <pubDate>Thu, 30 May 2019 13:11:00 GMT</pubDate>
            <atom:updated>2021-11-04T18:23:35.430Z</atom:updated>
            <content:encoded><![CDATA[<h3>Mimblewimbling Through Privacy</h3><h4>Implementing privacy and anonymity with fancy math</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OffvILlw7Ec69pC60aqvew.png" /></figure><p>The years of 2017 and ’18 were years focused on the topic of scaling. Coins forked and projects were hyped with this word as their sole mantra. What this debate brought us were solutions and showed us that where we are right now satisfies the current need when paired with a plan for the future. What will be the focus of years to come will be anonymity and fungibility in mass adoption.</p><p>In the quickly evolving world of connected data, privacy is becoming a topic of immediate importance. As it stands, we trust our privacy to centralized corporations where safety is ensured by the strength of your passwords and how much effort an attacker dedicates to getting breaking them. As we grow into the new age of the Internet, where all things are connected, trustless and cryptographic privacy must be at the base of all that it rests upon. In this future, what is at risk is not just photographs and credit card numbers, it is everything you interact with and the data it collects.</p><p>If the goal is to do this in a decentralized and trustless network, the challenge will be finding solutions that have a range of applicability that equal the diversity of the ecosystem with the ability to match the scales predicted.</p><h3>Mimblewimble</h3><p>Mimblewimble is a fairly new and novel implementation of the same elements of Elliptic-Curve Cryptography that serves as the basis of most cryptocurrencies.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_oruUUJLV5_fe8RH5tNpbA.png" /></figure><p>In bitcoin-wizards IRC channel in August 2016, an anonymous user posted a Tor link to a whitepaper claiming “an idea for improving privacy in bitcoin.” What followed was a blockchain proposal that uses a transaction construction radically different than anything seen today creating one of the most elegant uses of elliptic curve cryptography seen to date.</p><p>While the whitepaper posted was enough to lay out the ideas and reasoning to support the theory, it contained no explicit mathematics or security analysis. Andrew Poelstra, a mathematician and the Director of Research at Blockstream, immediately began analyzing its merits and over the next two months, created a detailed whitepaper [poel16] outlining the cryptography, fundamental theorems, and protocol involved in creating a standalone blockchain.</p><p>What it sets out to do as a protocol is to wholly conceal the values in transactions and eliminate the need for addresses while simultaneously solving the scaling issue.</p><h4>Confidential Transactions</h4><p>Let’s say you want to hide the amount that you are sending. One great way to hide information that is well known and quick: hashing! Hashing allows you to deterministically produce a random string of constant length regardless of the size of the input, that is impossible to reverse. We could then hash the amount and send that in the transaction.</p><p>X = SHA256(amount)</p><p>or</p><pre>4A44DC15364204A80FE80E9039455CC1608281820FE2B24F1E5233ADE6AF1DD5 = SHA256(10)</pre><p>But since hashing is deterministic, all someone would have to do would be to catalog all the hashes for all possible amounts and the whole purpose for doing so in the first place would be nullified. So instead of just hashing the amount, lets first multiply this amount by a private <strong><em>blinding factor</em></strong><em>. </em>If kept private, there is no way of knowing the amount inside the hash.</p><pre>X = SHA256(blinding factor * amount)</pre><p>This is called a <strong><em>commitment</em></strong>, you are committing to a value without revealing it and in a way that it cannot be changed without changing the resultant value of the commitment.</p><p>But how then would a node validate a transaction using this commitment scheme? In the very least, we need to prove that you satisfy two conditions; one, you have enough coins, and two, you are not creating coins in the process. The way most protocols validate this is by consuming a previous input transaction (or multiple) and in the process, creating an output that does not exceed the sum of the inputs. If we hash the values and have no way validate this condition, one could create coins out of thin air.</p><pre>input(commit(bf,10), Alice) -&gt; output(commit(bf,9), BOB), outputchange(commit(bf,5), Alice)</pre><pre>Or</pre><pre>input(4A44DC15364204A80FE80E9039455CC1608281820FE2B24F1E5233ADE6AF1DD5, Alice) -&gt;</pre><pre>output(19581E27DE7CED00FF1CE50B2047E7A567C76B1CBAEBABE5EF03F7C3017BB5B7, Bob)</pre><pre>output(EF2D127DE37B942BAAD06145E54B0C619A1F22327B2EBBCFBEC78F5564AFE39D, Alice)</pre><p>As shown above, the later hashed values look just as valid as anything else and result in Alice creating 4 coins and receiving them as change in her transaction. <strong>In any transaction, the sum of the inputs must equal the sum of the outputs.</strong>We need some way of doing mathematics on these hashed values to be able to prove:</p><pre>commit(bf1,x) = commit(bf2,y1) + commit(bf3,y2)</pre><p>which, if it is a valid transaction would be:</p><pre>commit(bf1,x) - commit(bf2+bf3,y1+y2) = commit(bf1-(bf2+bf3),0)</pre><p>Or just a commit of the leftover blinding factors.</p><p>By the virtue of hashing algorithms, this isn’t possible. To verify this we would have to make all blinding factors and amounts public. But in doing so, nothing is private. How then can we make a value <em>public</em>that is made with a <em>private</em>value in such a way that you cannot reverse engineer the private value and still validate it satisfies some condition? Sounds a bit like public and private key cryptography…</p><p>What we learned in <a href="https://medium.com/coinmonks/elliptic-curve-cryptography-6de8fc748b8b">our primer on Elliptic-Curve Cryptography</a>was that by using an elliptic curve to define our number space, we can use a point on the curve, <strong>G</strong>, and multiply it by any number, <em>x</em>, and what you get is another valid point, <strong>P</strong>, on the same curve. This calculation is quick but in taking the resultant point and the publically known generator point <strong>G</strong>, it is practically impossible to figure out what multiplier was used. This way we can use the point <strong>P</strong>as the public key and the number <em>x</em>as the private key. Interestingly, they also have the curious property of being additive and communicative.</p><p>If you take point <strong>P</strong>which is <em>x</em>• <strong>G</strong>and add point <strong>Q</strong>to it which is <em>y</em>• <strong>G</strong>, its resulting point, <strong>W </strong>= <strong>P</strong>+ <strong>Q</strong>, is equal to creating a new point with the combined numbers <em>x</em>+<em>y</em>. So:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Wj-FGFX7ClNqec3VLUSTOQ.png" /></figure><p>This property, <em>homomorphism, </em>allows us to do math with numbers we do not know.</p><p>So if instead of using the raw amount and blinding factor in our commit, we use them each multiplied by a known generator point on an elliptic curve. Our commit can now be defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*w7qqJ2wX4p_deQD9ewqIWQ.png" /></figure><p>This is called a <strong>Pedersen Commitment </strong>and serves as the core of all <strong>Confidential Transactions</strong>.</p><p>Let’s call the blinding factors <em>r, </em>and the amounts <em>v,</em>and use <strong>H</strong>and <strong>G</strong>as generator points on the same elliptic curve (without going deep into Schnorr signatures, we will just accept that we have to use two different points for the blinding factor and value commits for validation purposes**). Applying this to our previous commitments:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9hq3CJoVJRbdTTDD87ipiA.png" /></figure><p>and using the communicative properties:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*p0aKYDLE4qGm_wGQcqqqFg.png" /></figure><p>which for a valid transaction, this would equal:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KJYoC6XaTz_PMqY5yWhbKg.png" /><figcaption>with <em>ri, vi</em>being the values for the input, <em>ro,vo</em>being the values for the output and <em>rco, vco</em>being the values for the change output.</figcaption></figure><p>This resultant difference is just a commit to the excess blinding factor, also called a <em>commitment-to-zero:</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pi3AvBstt4L5dK432hQh_g.png" /></figure><p>You can see that in any case where the blinding factors were selected randomly, the commit-to-zero will be non-zero and in fact, is still a valid point on the elliptic curve with<strong><em>public key,</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wKSa6BZUYCjPP75dA5f6Hg.png" /></figure><p>And <strong><em>private key</em></strong>being the difference of the blinding factors.</p><p>So, if the sum of the inputs minus the sum of the outputs produces a valid public key on the curve, you know that the values have balanced to zero and no coins were created. If the resultant difference is not of the form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EMVaYGRDhekOK3FhySUynQ.png" /></figure><p>for some excess blinding factor, it would not be a valid public key on the curve, and we would know that it is not a balanced transaction. To prove this, the transaction is then signed with this public key to prove the transaction is balanced and that all blinding factors are known, and in the process, no information about the transaction have been revealed (the by step details of the signature process can be read in [Arvan19]).</p><p>All the above work assumed the numbers were positive. One could create just as valid of a balanced transaction with negative numbers, allowing users to create new coins with every transaction. Called <strong>Range Proofs, </strong>each transaction must be accompanied by a zero-knowledge argument of knowledge to prove that a private committed value lies within a predetermined range of values. Mimblewimble, as well as Monero, use <strong>BulletProofs</strong>which is a new way of calculating the proof which cuts down the size of the transaction by 80–90%.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/848/1*ak65ZluWs-ccxw9Cfu3lqg.png" /><figcaption>*Average sizes of transactions seen in current networks or by assuming 2 input 2.5 output average tx size for MW.</figcaption></figure><p>Up to this point, the protocol described is more-or-less identical between Mimblewimble and Monero. The point of deviation is how transactions are signed.</p><p>In <strong>Monero</strong>, there are two sets of keys/addresses, the spend keys, and the view keys. The spend key is used to generate and sign transactions, while the view key is used to “receive” transactions. Transactions are signed with what is called a <strong>Ring Signature </strong>which is derived from the output being spent, proving that one key out of the group of keys possesses the spend key. This is done by creating a combined Schnorr signature with your private key and a mix of decoy signers from the public keys of previous transactions. These decoy signers are all mathematically equally valid which results in an inability to determine which one is the real signer. Being that Monero uses Pedersen Commitments shown above, the addresses are never publically visible but are just used for the claiming, signing of transactions and generating blinding factors.</p><p><strong><em>Mimblewimble, on the other hand, does not use addresses of any type. </em></strong>Yes. That’s right, no addresses. This is the true brilliance of the protocol. What Jedusor proved was that the blinding factors within the Pedersen commits and the commit-to-zero can be used as single-use public/private key pairs to create and sign transactions.</p><p>All address based protocols using elliptic-curve cryptography generate public-private key pairs in essentially the same way. By multiplying a very large random number (<em>k_priv</em>) by a point (<strong>G</strong>) on an elliptic curve, the result (<strong>K</strong>_pub) is another valid point on the same curve.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/906/1*IpVPZjjWzQvvFlUktoB0qQ.png" /></figure><p>This serves as the core of all address generation. Does that look familiar?</p><p>Remember this commit from above:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ddi0nvprdBTo8WxbVsDeOw.png" /></figure><p>Each blinding factor multiplied by generator point <strong>G </strong>(in red) is exactly that! <em>r</em>•G is the public key with private key <em>r</em>! So instead of using addresses, we can use these blinding factors as proof we own the inputs and outputs by using these values to build the signature.</p><p>This seemingly minor change removes the linkability of addresses and the need for a scriptSig process to check for signature validity, which greatly simplifies the structure and size of Confidential Transactions. Of course, this means (at this time) that the transaction process requires interaction between parties to create signatures.</p><h4>CoinJoin</h4><p>Even though all addresses and amounts are now hidden, there is still some information that can be gathered from the transactions. In the above transaction format, it is still clear which outputs are consumed and what comes out of the transaction. This “transaction graph” can reveal information about the owners of the blinding factors and build a picture of the user based on seen transaction activity. In order to further hide and condense information, Mimblewimble implements an idea from Greg Maxwell called CoinJoin [Max13] which was originally developed for use in Bitcoin. CoinJoin is a trustless method for combining multiple inputs and outputs from multiple transactions, joining them into a single transaction. What this does is mask which sender paid which recipient. To accomplish this in Bitcoin, users or wallets must interact to join transactions of like amounts so you cannot distinguish one from the other. If you were able to combine signatures without sharing private keys, you could create a combined signature for many transactions (like ring signatures) and not be bound by needing like amounts.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3lt-lFBosFUPjuZTEO-AtA.png" /><figcaption>In this CoinJoin tx, 3 addresses have 4 outputs with no way of correlating who sent what</figcaption></figure><p>In Mimblewimble, doing the balance calculation for one transaction or many transactions still works out to a valid commit-to-zero. All we would need to do is to create a combined signature for the combined transaction. Mimblewimble is innately enabled to construct these combined signatures with the commit with Schnorr challenge transaction construction. Using “one-way aggregate signatures” (OWAS), nodes can combine transactions, while creating the block, into a single transaction with one aggregate signature. <strong>Using this,Mimblewimble joins all transactions at the block level, effectively creating each block as one big transaction of all inputs consumed and all outputs created. </strong>This simultaneously blurs the transaction graph and has the power to remove in-between transactions that were spent during the block, cutting down the total size of blocks and the size of the blockchain.</p><h4>Cut-through</h4><p>We can take this one step further. To validate this fully “joined” block, the node would sum all of the output commitments together, then subtract all the input commitments and validate that the result is a valid commit-to-zero. What is stopping us from only joining the transactions within a block? We could theoretically combine two blocks, removing any transactions that are created and spent in those blocks, and the result again is a valid transaction of just unspent commitments and nothing else. We could then do this all the way back to the genesis block, reducing the whole blockchain to just a state of unspent commitments. This is called <strong>Cut-through. </strong>When doing this, we don’t have any need to retain the range proofs of spent outputs, they have been verified and can be discarded. This lends itself to a massive reduction in blockchain growth, reducing growth from <strong><em>O</em></strong><em>(number of txs)</em>to <strong><em>O</em></strong><em>(number of unspent outputs)</em>.</p><p>To illustrate the impact of this, let’s imagine if Mimblewimble was implemented in the Bitcoin network from the beginning, with the network at block 576,000, the blockchain is about 210 GB with 413,675,000 total transactions and 55,400,000 total unspent outputs. In Mimblewimble, <em>transaction outputs</em>are about 5 kB (including range proof ~5 kB and Pedersen commit ~33 bytes), <em>transaction inputs </em>are about 32 bytes and <em>transactionproofs</em>are about 105 bytes (commit-to-zero and signature), block headers are about 250 bytes (Merkle proof and PoW) and non-confidential transactions are negligible. This sums up to to a staggering 5.3 TB for a full sync blockchain of all information, with “only” 279 GB of that being the UTXOs. When we cut-through, we don’t want to lose all the history of transactions, so we retain the proofs for all transactions as well as the UTXO set and all block headers. This reduces the blockchain to 322 GB, a 94% reduction in size. The result is basically a total consensus state of only that which has not been spent with a full proof history, greatly reducing the amount of sync time for new nodes.</p><p>If Bulletproofs are implemented, the range proof is reduced from over 5kB to less than 1 kB, dropping the UTXO set in the above example from 279 GB to 57 GB.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/902/1*yPhXIIoLUMjtzPTmr1djcA.png" /><figcaption>*Based on the assumptions and calculations above.</figcaption></figure><p>There is also an interesting implication in PoS blockchains with explicit finality. Once finality has been obtained, or at some arbitrary blockchain depth beyond it, there is no longer the need to retain range proofs. Those transactions have been validated, the consensus state has been built upon it and they make up the vast majority of the blockchain size. If we say in this example that finality happens at 100 blocks deep, and assume that 10% of the UTXO set is pre-finality, this would reduce the blockchain size by another 250 GB, resulting in a full sync weight of 73 GB, a 98.6% reduction (even down 65% from its current state). <em>Imagine this.</em>A 73 GB blockchain for 10 years of fully anonymous Bitcoin transactions, and one third the current blockchain size.</p><p>It’s important to note that cut-through has no impact on privacy or security. Each node may choose whether or not to store the entire chain without performing any cut-through with the only cost being increased disk storage requirements. Cut-through is purely a scalability feature resulting in Mimblewimble based blockchains being on average three times smaller than Bitcoin and fifteen times smaller than Monero (even with the recent implementation of Bulletproofs).</p><h3>What does this mean?</h3><p>Mimblewimble’s revolutionary use of elliptic-curve cryptography brings us a privacy protocol using <strong>Pedersen commitments </strong>for fully <strong>confidential transactions </strong>and in the process, removes the dependence on addresses and private keys in the way we are used to them. This transaction framework combined with <strong>Bulletproofs </strong>brings lightweight privacy and anonymity on par with Monero, in a blockchain that is 15 times smaller, utilizing full <strong>cut-through</strong>. This provides the solution to private transactions that fit the scalability requirements of the INT network.</p><p>The Mimblewimble protocol has been implemented in two different live networks, Grin and Beam. Both are purely transactional networks, focused on the private and anonymous transfer of value. Grin has taken a Bitcoin-like approach with community-funded development, no pre-mine or founders reward while Beam has the mindset of a startup, with VC funding and a large emphasis on a user-friendly experience.</p><h4>Where it falls short</h4><p><em>What makes this protocol revolutionary is the same thing that limits it. </em>Almost all protocols, like Bitcoin, Ethereum, etc., use a basic scripting language with a function call out in the actual transaction data that tells the verifier what script to use to validate it. In the simplest case, the data provided with the input calls “scriptSig” and provides two pieces of data, the signature that matches the transaction and the public key that proves you own the private key that created it. The output scripts use this provided data with the logic passed with it, to show the validator how to prove they are allowed to spend it. Using the public key provided, the validator then hashes it, checks that it matches the hashed public key in the output, if it does, it then checks to make sure the signature provided matches the input signature.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dTwQminjdrSeMH1UU8x5kQ.png" /></figure><p>This verification protocol allows some limited scripting ability in being able to tell validators what to do with the data provided. The Bitcoin network can be updated with new functions allowing it to adapt to new processes or data. Using this, Bitcoin protocol can verify multiple signatures, lock transactions for a defined timespan and do more complex things like lock bitcoin in an account until some outside action is taken.</p><p>In order to achieve more widely applicable public smart contracts like those in Ethereum, they need to be provided data in a non-shielded way or create shielded proofs that prove you satisfy the smart contract conditions.</p><p>In Mimblewimble, as a consequence of using the blinding factors as the key pairs, greatly simplifying the signature verification process, there are no normal scripting opportunities in the base protocol. What is recorded on the blockchain is just:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Eqlaa4w4GdO2j9Y4k-dyEg.png" /></figure><ul><li>Inputs used — which are old commits consumed</li><li>New outputs — which are new commits to publish</li><li>Transaction kernel — which contains the signature for the transaction with excess blinding factor, transaction fee, and lock_height.</li></ul><p>And none of these items can be related to one another and contain no useful data to drive action.</p><p>There are some proposals for creative solutions to this problem by doing so-called scriptless-scripts†. By utilizing the properties of the Schnorr signatures used, you can achieve multisig transactions and more complex condition-based transactions like atomic cross-chain swaps and maybe even lightning network type state channels. Still, this is not enough complexity to fulfill all the needs of IoT smart contracts.</p><p><em>And on top of it all, implementing cut-through would remove transactions that might be smart contracts or rely on them.</em></p><p>So you can see in this design we can successfully hide values and ownership but only for a single dimensional data point, quantity. Doing anything more complex than transferring ownership of coin is beyond its capabilities. But the proof of ownership and commit-to-zero is really just a specific type of Zero-knowledge (ZK) proof. So, what if, instead of blinding a value we blind a proof?</p><blockquote>Part 2 of this series will cover implementing private smart contracts with zkSNARKs.</blockquote><h3>References and Notes</h3><p><a href="https://github.com/ignopeverell/grin/blob/master/doc/intro.md">https://github.com/ignopeverell/grin/blob/master/doc/intro.md</a></p><p><a href="https://github.com/mimblewimble/grin/blob/master/doc/pow/pow.md">https://github.com/mimblewimble/grin/blob/master/doc/pow/pow.md</a></p><p><a href="https://github.com/mimblewimble/grin/wiki/Grin-and-MimbleWimble-vs-ZCash">https://github.com/mimblewimble/grin/wiki/Grin-and-MimbleWimble-vs-ZCash</a></p><p>*<a href="https://bitcointalk.org/index.php?topic=305791.0">https://bitcointalk.org/index.php?topic=305791.0</a></p><p>[poel16] <a href="http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble-andytoshi-INCOMPLETE-DRAFT-2016-10-06-001.pdf">http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble-andytoshi-INCOMPLETE-DRAFT-2016-10-06-001.pdf</a></p><p>** <em>In order to prove that v=0 and therefore the commit to zero, in fact, has no </em><strong><em>H </em></strong><em>component without revealing r, we must use Schnorr protocol:</em></p><ul><li><em>prover generates random integer n, computes and sends point 𝑇←n𝐻</em></li><li><em>verifier generates and sends random integer 𝑖</em></li><li><em>prover computes and sends integer 𝑠←𝑖𝑏+n modq, where q is the (public) order of the curve</em></li><li><em>verifier knowing point r𝐻 computes point 𝑖(r𝐻), then point 𝑖(r𝐻)+𝑇; computes point 𝑠𝐻; and ensures 𝑖(r𝐻)+𝑇=𝑠𝐻.</em></li></ul><p>[Arvan19] <a href="https://medium.com/@brandonarvanaghi/grin-transactions-explained-step-by-step-fdceb905a853">https://medium.com/@brandonarvanaghi/grin-transactions-explained-step-by-step-fdceb905a853</a></p><p>[Bulletproofs] <a href="https://eprint.iacr.org/2017/1066.pdf">https://eprint.iacr.org/2017/1066.pdf</a></p><p>[Max13] <a href="https://bitcointalk.org/?topic=279249">https://bitcointalk.org/?topic=279249</a></p><p>[MaxCT]<a href="https://people.xiph.org/~greg/confidential_values.txt">https://people.xiph.org/~greg/confidential_values.txt</a></p><p>[Back13]<a href="https://bitcointalk.org/index.php?topic=305791.0">https://bitcointalk.org/index.php?topic=305791.0</a></p><p>† <a href="http://diyhpl.us/wiki/transcripts/grincon/2019/scriptless-scripts-with-mimblewimble/">http://diyhpl.us/wiki/transcripts/grincon/2019/scriptless-scripts-with-mimblewimble/</a></p><p>† <a href="https://tlu.tarilabs.com/cryptography/scriptless-scripts/introduction-to-scriptless-scripts.html#list-of-scriptless-scripts">https://tlu.tarilabs.com/cryptography/scriptless-scripts/introduction-to-scriptless-scripts.html#list-of-scriptless-scripts</a></p><iframe src="https://drive.google.com/viewerng/viewer?url=https%3A//diyhpl.us/%7Ebryan/papers2/bitcoin/2017-03-mit-bitcoin-expo-andytoshi-mimblewmble-scriptless-scripts.pdf&amp;embedded=true" width="600" height="780" frameborder="0" scrolling="no"><a href="https://medium.com/media/b5b61e653ab260737eafc0f60a4d30f9/href">https://medium.com/media/b5b61e653ab260737eafc0f60a4d30f9/href</a></iframe><blockquote><a href="https://coincodecap.com/?utm_source=coinmonks">Get Best Software Deals Directly In Your Inbox</a></blockquote><figure><a href="https://coincodecap.com/?utm_source=coinmonks"><img alt="" src="https://cdn-images-1.medium.com/max/584/0*OJ-qb5G6i863msBB.png" /></a></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=72cdec6bedec" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/mimblewimble-in-iot-72cdec6bedec">Mimblewimble in IoT</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[PoS Blockchain Scaling]]></title>
            <link>https://medium.com/coinmonks/pos-blockchain-scaling-8f9c0c485c0d?source=rss-b87d8eb3b46c------2</link>
            <guid isPermaLink="false">https://medium.com/p/8f9c0c485c0d</guid>
            <category><![CDATA[pos]]></category>
            <category><![CDATA[blockchain-scalability]]></category>
            <category><![CDATA[finality]]></category>
            <category><![CDATA[int]]></category>
            <category><![CDATA[internet-of-things]]></category>
            <dc:creator><![CDATA[Grayblock]]></dc:creator>
            <pubDate>Sat, 23 Mar 2019 21:15:36 GMT</pubDate>
            <atom:updated>2021-11-04T18:47:04.799Z</atom:updated>
            <content:encoded><![CDATA[<h3>Blockchain Scaling in PoS</h3><h4>Scaling as a function of finality</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*weZ1soYXQy_IIzZDftlOTg.png" /></figure><blockquote>As long as every node independently verifies the entirety of all transactions in the network, the network can only process as many transactions as one node is capable of.</blockquote><p>In <a href="https://medium.com/coinmonks/blockchain-finality-in-iot-79e466406133">Part 1</a> of this series, we discussed PoW finality and the consequence of the consensus mechanism which allows there to always be a chance the chain will be overtaken by another competing chain, thereby reverting transactions. So transaction finality is never a guarantee. Because of this, all nodes in the network verify all blocks and all transactions. Therefore, the network can only process as many transactions as one node can independently process.</p><p>In <a href="https://medium.com/coinmonks/blockchain-scaling-30c9e1b7db1b">Part 2</a>, we looked into ways of improving this by increasing block size and decreasing block frequency but ultimately those changes are limited by how fast transactions and blocks can propagate the network. So again, while the throughput can be increased (slightly, still less than 100 TPS) by these methods, it doesn’t change the constraint of the single node bottleneck. Scaling globally will require the network state validation responsibility to be divided between the nodes. This now becomes an issue of finality.</p><p>If there is no probability of transactions beyond a certain age to be reverted, we wouldn’t need to store or verify against the entire history of transactions, only the ones which the current state is dependent on.</p><h4>History behind Proof-of-Stake</h4><p>The beginnings of PoS come from a long history of research in distributed agreement in replicated state machines. Going back to the 1970s, many people were working on the issues around making reliable communications from unreliable parts in commercial airlines. A fault in a communication 30,000 feet and with 150 passengers has real consequence so being able to figure out data validity is a life and death problem. From this field of work came the classical Byzantine General’s problem that birthed Byzantine Fault Tolerance (BFT). Up until 1999 (when Practical BFT was invented), the Byzantine General’s problem was mostly an academic one which no one had yet solved. Major computing systems around the world had no practical use for it as banking, stocks, communications, and internet were all centrally hosted and controlled.</p><p>It wasn’t until 2008 when Satoshi Nakamoto brought a practical solution to the Byzantine General’s problem into a globally scaled distributed network. This quickly proved to be a stable and secure system to achieve fault-tolerant consensus, causing research in applying these previously academic ideas into real-world applications to explode.</p><p>Stated simply, Proof-of-Work is really just a way to verify that what the block creator has compiled as a history of what occurred since the last block is valid and allowable. The crux of this consensus protocol is to do this without having to trust the honesty of the block creator and make the process open and available to all (with also dynamically maintaining a 10-minute block frequency despite changes to the overall computing power in the network, <em>details… details)</em>. The penalty here is that if you act improperly, the block is provably invalid and you do not get awarded for the computational effort you expended. This computational effort has proven to grow in direct relation to the value of the asset. Over the past couple of years, this has brought some concern. As it currently stands, bitcoin at $4,013, each transaction uses 511 KWh or enough energy to power 17.27 US households producing 242.73 kg of CO2.</p><p>So if this can be done by some other means while maintaining the same security, lack of trust and distributed nature of a PoW network without the need to expend physical resources, that would be a more efficient method of achieving BFT consensus and unarguably better for everyone.</p><p>The concept of Proof-of-Stake was born <a href="https://bitcointalk.org/index.php?topic=27787.0">rather brilliantly</a>from user <em>QuantumMechanic </em>on Bitcointalk forum in 2011. In this discussion, they pitched the idea that instead of distributed computing “voting” on the valid history, distributed ownership votes on the to-be-accepted valid history. This discussion began the 7-year battle to implement this idea with the same security and scale as Bitcoin.</p><p>Initial implementations of this technology were incompletely implemented as the multitude of issues solved by the Bitcoin implementation of PoW were not completely understood. Some would argue that even today, many of the more nuanced issues have yet to be solved.</p><h4>Breaking Down PoS</h4><p>There are several ways a block producer can be selected in PoS, whether it be by votes (Delegated PoS, e.g. EOS) or stake (PoS), randomly selected (e.g. Nxt) or by coin age (e.g. Peercoin), but the core concept remains the same, the network is not secured by the physically scarce resource of computing power as in PoW but by the digitally scarce resource of the network currency/asset.</p><p>In staking PoS, the users who wish to participate in the block creation process must “stake” their coins by locking them in a wallet. Just like PoW, where the user’s probability for creating a block is proportional to the amount of computing power they have in relation to the network, a staked user in a PoS network will be selected to create the block with a probability proportional to the amount of stake they have in relation to the total amount of staked coins in the network.</p><p>This requires the user’s wallet with the staked funds to remain online and available for this process, a requirement that leads to less than desired participation. This architecture has proved to be just about as efficient as PoW implementations with limiting factors in throughput being dependent on block propagation and ultimately single node throughput. Once 2/3 of the nodes in the network* approve the proposed block, the block becomes a finalized addition to the blockchain. You can see that finalization in these networks is highly dependent on the number of staked wallets (therefore, nodes) currently part of the active selection process. Pulling the math from Part 1 of this series, on finality, assuming we have a PoS network with a 5 second block time (fast-ish) so <em>ω = 1/5, </em>and 10,000validators (highly decentralized). That gives us a finality of 10,000/(1/5) or 10,000 x 5 or 50,000 seconds (~14 hours). That isn’t practical for the transaction of anything that requires verifiable proof of validity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VnOPXg03bDe6W9agoD4wjA.png" /><figcaption>From Part 1 on finality. In PoS networks, time to finality, <em>f</em>, is defined as the above where <em>n</em>is the number of validator nodes in the network needed for consensus and ω is the protocol overhead.</figcaption></figure><h4>Issues with PoS</h4><p>The main issue with pure PoS implementations is something called the <strong>Nothing-at-Stake problem</strong>. In these networks, there is no punishment for voting on competing blocks. Users could therefore selectively vote on blocks that create a competing fork which does not include a particular unwanted history. Because these blockchains operate on the same longest-chain principle, overtaking the main chain is much cheaper than a similar attack in a PoW network. The solution to this is to create a framework for determining malicious behavior and punishing it. Very much easier said than done.</p><p>This issue goes hand in hand with <strong>long-range attacks</strong>, even if there is punishment for voting on competing blocks, there is nothing stopping an attacker building up a fork from a long range without fear of penalty.If this is done, and users are free to immediately unstake, the incentive not to vote on a long-range fork from some block height ago is removed. If 2/3 of the validators do this and vote for the contentious fork which is longer than the main chain, the history would be overwritten. One solution to this problem is to have unstaked coin have a cooling period before having the ability to revote. This gives the main chain time to grow past the time where the validators are present on both chains, thereby nullifying the risk. The only problem to this is the cool off time for this to effectively work could be on the order of weeks to months. Another solution is to implement explicit finality. If you consider a block at a certain height, <em>(current height)-X,</em>as final and unable to be overwritten, then this would invalidate any long-range fork. This is also solved in DPoS by considering a block with 2/3 of the delegates signatures as final.</p><p>Votes and delegates being determined by the number of tokens users own brings in an inherent centralization risk by <strong>cartel creation or “whale” manipulation</strong>. Now, this issue is not secluded to PoS consensus as mining power is just as much at risk of centralization, PoS just makes this a social issue and opens the door to a much broader topic for another day: distributed governance. No in-protocol solution has been presented to prevent rich-getting-richer or censorship resistance at this time. The hope here is that the social space will inevitably notice cartels forming, create conversation around it, and in the interest of protecting the group interest, vote to reorganize the blockchain.</p><h4>Scaling in PoS networks</h4><p>By not making the consensus process a computational competition to create a block but one of probabilistic election nullifies† the orphan block issue caused by speeding up block frequency in PoW consensus. This gives immediate throughput gains by being able to push the network faster than before. But you are still limited to the time it takes for the block to propagate the network and 2/3 of the node pool to sign the block.</p><p>The issues with finality, low actual participation in securing the network and the difficulty in applying a solution to the Nothing-at-Stake problem really can be solved by limiting the number of block producing nodes in the network. Finality is reduced linearly with respect to the number of nodes, and tracking and punishing real-time Byzantine behavior is much easier over 100 or even 10 nodes than 10,000.</p><p>So this is the PoS version of the PoW ceiling defined as: <em>“the network can only process as many transactions as one node is able to”</em>. In classical, single chain PoS, your ceiling is defined as: <em>“the network can only process as many transactions as the node pool is able to”</em>. But how can this be done without making it a rich-get-richer ecosystem with no accountability to the users in the network while maintaining “decentralization”? This is where Delegated PoS, or DPoS, has proved to be a much more stable implementation with a tremendous technical advantage over the most accepted PoW networks.</p><p>In DPoS, instead of having a staked user be the probabilistic block producer, the pool of candidates is reduced to a static number and block producing status of the node is based on votes from stakeholders. While this reduces the decentralized distribution of wealth within the network, block producers are usually required (or socially pressured) to give value back to the voters or network as a whole in the form of profit sharing or other technological/social increases of value e.g. 3rd party software or social action.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/386/1*bl_YlABslQSvEABZ4lGj0w.jpeg" /><figcaption>Fig. 1 From Vlad Zamfir’s paper on Ethereum Casper Protocol</figcaption></figure><p>Reducing the number of nodes allows the architects to push the bounds of block size and block frequency to the limits of bandwidth and latency within the network. The distinct variables of the network, e.g. block frequency, size, and node quantity, are based on the accepted trade-offs for finality latency, decentralization and overhead [Fig. 1]. For DPoS mechanisms, since every node must send a message signing the block before the next block can be made, the number of messages per block is one to (block proposal) and one from (block signature) each node per block time, <em>B</em>, or: <em>ω = 2n/B. </em>For example, assuming we have a DPoS network with a 0.5 second block time and 21 validators (EOS), we have a <em>ω = 42/0.5 or 84</em>. That gives us a finality of 21/84 or 0.25 seconds. That is from the moment you send a transaction and it is accepted into a block to it being 100% finalized is at max 1.25 seconds (<em>depending on your local latency)</em>.</p><p>As a grand consequence of PoS variants with explicit finality, we can approach the problem of scaling from a different angle. Because there is no possibility for earlier transactions to be reverted, there is no need to carry a whole history or blockchain of transactions, only a snapshot at a time prior to the last finalized block. We are then free to explore how little each validating node has to do in the network to security and provable validity. Traditional scaling solutions looked at it as a problem of getting more transactions through nodes or a pool of nodes (vertical scaling) but this allows us to look at scaling as a problem of splitting the network into multiple pools of nodes handling cells of the network, thereby multiplying the the number of transactions able to be processed by the number of pools available (horizontal scaling).</p><h4>Finality Enabled Horizontal Scaling</h4><p>Horizontal scaling has been used in databases for many years. In a common table of data, this is represented by splitting up rows of data and storing them in separate tables, e.g. addresses of people with last names starting with A-M in one table stored on one server and addresses of people with last names starting with N-Z in a second table stored on a second server. This effectively shares the load of the data between two servers, doubling the network capacity and requiring the network to communicate between servers in order to compile network-wide queries. This is <strong>database sharding</strong>.</p><p>A blockchain at its very core is just a database recording events in time-based on a set of rules, so we could apply this theory to blockchain networks. This can be done by splitting up the validator nodes into groups which maintain subsets of addresses, e.g. 0x0 addresses in one group, 0x1 addresses in another group, etc. Those nodes maintain a blockchain for only those addresses and coordinate transactions to other address groups by interacting with the other node groups. In simple terms, that’s exactly what Ethereum’s implementation of sharding proposes to do. This increases the throughput from what one node can process to what one node can process, times the number of shards in the network.</p><p>These shards don’t just have to be copies of each other with the same rule set governing them. They can have different assets, block sizes, frequency, consensus mechanism, anonymity, contracts, fees, etc. For all intents and purposes, each shard is a standalone blockchain. The nodes governing that shard maintain consensus within it while also rolling their shard state into the global state of the network. That ties each shard state to each other, combining the state and therefore security of all shards. A consequence of this architecture is everything that happens within shards is usable and intractable with what occurs in other shards. In a single asset sharded network, this would be you being able to send tokens from an 0x0 address to an 0x1 address with the network operating imperceptibly different from a single chain blockchain. But in a sharded network where shards have different rules and functions, this opens the doors to endless complex interoperability.</p><p>This is where Ethereum, the second largest cryptocurrency, is headed. And it goes farther than that. Scaling a sharded network is as easy as adding nodes to support the additional shard. Let’s say you have a 10 shard network and every shard can handle 200 TPS, for total network throughput of 2,000 TPS. If you begin to run out of capacity and transactions begin to pile up, you can redefine shard boundaries, add a shard and assign nodes to it to increase throughput to 2,200 TPS. In essence, this architecture allows for endless scalability (THEORETICALLY).</p><h4>Notes</h4><p>*<em>2/3 of the nodes for fault-tolerant consensus is derived from the Byzantine’s General problem. Suppose we have a traitorous general A, and two commanders, B and C. When A tells B to retreat and C to attack, and B and C compare their messages, neither B or C can figure out who is the traitor since it is not necessarily A generating the traitorous message. It can be shown in general that if n is the number of generals in total and t is the number of traitors, then there can be verifiable consensus only when n &gt; 3t.</em></p><p>†<em>Not really. But for the sake of the argument, let’s just assume all the details that go into making that a correct assumption, are baseline.</em></p><p><a href="https://www.semanticscholar.org/paper/The-Quest-for-Scalable-Blockchain-Fabric%3A-vs.-BFT-Vukolic/efb1a85cf540fd4f901a78100a2e450d484aebac">https://www.semanticscholar.org/paper/The-Quest-for-Scalable-Blockchain-Fabric%3A-vs.-BFT-Vukolic/efb1a85cf540fd4f901a78100a2e450d484aebac</a></p><p><a href="http://www.gsd.inesc-id.pt/~ler/docencia/rcs1314/papers/P2P2013_041.pdf">http://www.gsd.inesc-id.pt/~ler/docencia/rcs1314/papers/P2P2013_041.pdf</a></p><p><a href="https://bitcoin.stackexchange.com/questions/32628/redeeming-a-raw-transaction-step-by-step-example-required">https://bitcoin.stackexchange.com/questions/32628/redeeming-a-raw-transaction-step-by-step-example-required</a></p><p><a href="https://medium.com/@jonchoi/ethereum-casper-101-7a851a4f1eb0">https://medium.com/@jonchoi/ethereum-casper-101-7a851a4f1eb0</a></p><p><a href="https://github.com/ethereum/wiki/wiki/Sharding-FAQ">https://github.com/ethereum/wiki/wiki/Sharding-FAQ</a></p><p><a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002417.html">[Bitcoin-development] Anti DoS for tx replacement</a></p><blockquote><a href="https://coincodecap.com/?utm_source=coinmonks">Get Best Software Deals Directly In Your Inbox</a></blockquote><figure><a href="https://coincodecap.com/?utm_source=coinmonks"><img alt="" src="https://cdn-images-1.medium.com/max/584/0*OJ-qb5G6i863msBB.png" /></a></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8f9c0c485c0d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/pos-blockchain-scaling-8f9c0c485c0d">PoS Blockchain Scaling</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Zero-Knowledge Proofs]]></title>
            <link>https://medium.com/coinmonks/zero-knowledge-proofs-1f4bd8f20d8d?source=rss-b87d8eb3b46c------2</link>
            <guid isPermaLink="false">https://medium.com/p/1f4bd8f20d8d</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zcash]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[bitcoin]]></category>
            <dc:creator><![CDATA[Grayblock]]></dc:creator>
            <pubDate>Mon, 26 Nov 2018 19:01:41 GMT</pubDate>
            <atom:updated>2021-11-04T18:27:30.639Z</atom:updated>
            <content:encoded><![CDATA[<h4>How to prove you know (or have) something without giving up any information about what it is you know</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wmqM2Gx5rOxGd3WRZCrK5Q.png" /></figure><p>In open blockchains like Bitcoin, Ethereum and many others, the transaction is public and open to all, showing who is sending it, who is receiving it and how much is changing hands. You can then see into all transactions in an out of those addresses, revealing their whole history. This level of openness makes many uncomfortable. So how can we make things a little more private?</p><p>How do you hide how much you are transacting, the data you are sending or your identity?</p><p>One simple solution could be hashing the entire transaction with the public key of the recipient, making it only readable by them. This is a great solution but this creates a couple issues. That data in the output is used for validating the transaction, populating the wallet with data and serves as the input to future outputs. Hiding that data behind a hash would therefore make it unavailable. Otherwise this is a great solution. Maybe we can solve these issues one by one. First, we have to prove that the data within the encrypted transaction is valid without giving up our privacy.</p><p>This is where zero-knowledge proofs come in. Zero-knowledge proofs refer to a proof construction that allows you to convince someone that you know something without revealing any information about what it is you know in the process. In a simple example, lets say that I, the prover, want to prove to you, the verifier, that I have two different colored billiard balls, but I don’t want you knowing what colors they are. So I blindfold you and put them in your hands. I have you put them behind your back and tell you that you can switch them or not then show them to me. I can then tell you if you switched them. Of course the first time I do this, it’s a 50–50 chance I get it right. But I have you do it over and over again, each time reducing the probability I got it right again by 50%. After several iterations of this you become satisfied that there is some difference between these balls and you hand them back to me and I put them away. I therefore proved to you that I have two different color balls without you knowing anything about them.</p><p>In cryptography this can be used to prove more complex things like given a hash, the prover could convince the verifier that there indeed exists a number, which the verifier knows, that satisfies certain criteria and that hashes to this value without revealing any characteristics of this number. This is what is used in creating confidential transactions where address and transaction balances are hidden on the blockchain behind hashes, or that you own the private key in order to spend a note, therefore hiding your identity.</p><p>Zero-knowledge proofs must satisfy three properties:</p><ul><li><strong>Completeness </strong>— If the statement is true, the honest verifier is completely convinced of the knowledge shown by the prover.</li><li><strong>Soundness </strong>— If the statement is false, no dishonest prover can convince the verifier that the statement is true. In practice, these are often not completely sound but statistically sound.</li><li><strong>Zero-knowledge</strong> — If the statement is true, the verifier cannot gain any knowledge of the statement other than that it is true. No other information about what made the statement true can be gained.</li></ul><h3>Let’s get snarky</h3><p>There are currently three cryptocurrencies (Zcash, Ethereum, INT) who have proposed the use of zero-knowledge proofs (that I know of) and only <strong>one</strong> of those has successfully implemented them. <strong>Zcash</strong>, a hard-fork of Bitcoin, became the pioneer in zero-knowledge proof application in late 2016 with the use of a specific implementation of zero-knowledge proofs called zk-SNARKs, with “zk” referring to <em>“zero-knowledge”</em> and SNARK referring to “<em>Succinct Non-interactive ARgument of Knowledge</em>”. This allows users to send transactions without revealing their address, the receiver’s address, the amount being sent or revealing either of their balances.</p><p>The succinctness of the argument refers to the speed at which the argument can be verified with the whole of the argument reduced down to only a few hundred bytes even for statements about complex programs (in Zcash, the verification only takes a few milliseconds).</p><p>For the argument to be non-interactive, the prover must supply the verifier all that they need in order to verify the proof fully. In interactive zero-knowledge setups, a “conversation” can occur where the verifier can ask questions of the prover and the prover provides answers.</p><h4>In Theory</h4><p>This can be broken down into 4 main steps, which are general to all SNARK implementations.</p><ul><li><strong>Encoding as a polynomial</strong> — The statement that is to be proven is compiled into a quadratic equation of 4 separate polynomials, where the equality, <em>t(x) h(x) = w(x) v(x) within a defined field</em>, must hold in order for the proof to be valid. Polynomials have curious mathematical properties (called homomorphic properties) that allow operations to be shifted around without effecting the result and are very hard to factor to reverse engineer their definition. This property makes them very useful for transporting, concealing and making use of secret values without them being known.</li><li><strong>Succinctness by random sampling</strong> — By giving the verifier the ability to randomly evaluate the polynomials with a secret value, <em>s</em>, it transforms the problem from multiplying polynomials to evaluating them at a specific point for equality, <em>t(s) h(s) = w(s) v(s), </em>thereby significantly reducing the work needing to be done to verify. By randomly sampling them at a given point, the chance of the functions being all equal at that point without satisfying the requirements of proof entirely are very small, ensuring completeness.</li><li><strong>Homomorphic encryption of the secret value</strong> — If the secret value, s, was known, the prover could construct a proof that worked only for that <em>s</em>, therefore convincing the verifier that they have satisfied all conditions.* In order to hide the secret value so the prover doesn’t know where their proof will be evaluated, the value is embedded into a semi-homomorphic† function to allow the use of the value in the provers polynomials without revealing the value itself, ensuring soundness. This function, <em>E(s)</em>, is then used by the prover to evaluate their quadratic proof at given point, <em>s,</em> by, <em>t(E(s)) h(E(s)) = w(E(s)) v(E(s)), </em>which because of the homomorphic properties is the same as<em> E(t(s)) E(h(s)) = E(w(s)) E(v(s)) </em>and also<em> E(t(s) h(s)) = E(w(s) v(s))</em></li><li><strong>Zero-knowledge — </strong>The problem with passing on <em>t(E(s)), h(E(s)), w(E(s)) </em>and<em> v(E(s)) </em>is that with the verifier knowing <em>E(s),</em> this would reveal some information about what the functions <em>t(s), h(s), w(s), v(s) </em>are. Therefore, in an effort to pass zero information on, the prover multiplies the function by a random number <em>k</em>, so the verifier can still make sure the “shape” of the result is the same just not where it is on the axis. Essentially, the idea is that <em>t(s) h(s) = w(s) v(s) </em>is identical to<em> (t(s) h(s)) k = (w(s) v(s)) k </em>for secret number<em> k. </em>And if all the verifier receives is numbers, there is no way to determine <em>k</em> and therefore the details of the functions, effectively proving the statement without allowing the discovery of any information that formulated the proof.</li></ul><p>Now, I conveniently and gracefully slid right over the most difficult part of this whole process, encoding the statement into a “quadratic arithmetic program” (QAP). This is not something that will be covered here but will probably be done in a separate post and will not be for the feint of heart. This step is the reason why zk-SNARKs is not a trivial thing to implement which lead to Zcash having to encode some of their consensus rules into zk-SNARKs and Ethereum to downsize the set of available smart contracts in order to make this work. Even then, for a simple transaction in Zcash, it still takes 40ish seconds to construct the proof. Ethereum, on the other hand, cannot possibly enable global use of these proofs in their smart contract environment because of gas constraints so <a href="https://github.com/ethereum/EIPs/pull/213">they have proposed a small subset of precompiled smart contracts that would work with zk-SNARKs</a>.</p><p><em>*Special note: In these setups, the secret value s could be used to generate falsely verifiable proofs and therefore giving the power to create coins in the network. It is therefore imperative that great lengths are taken to make sure this value is highly protected. In Zcash, a </em><a href="https://blog.z.cash/generating-zcash-parameters/"><em>multi-party ceremony was held</em></a><em> where each member of a group of third party actors created a part of the final value with an air-gapped computer which was then destroyed.</em></p><p>†<em>Homomorphic means that you can change the order of mathematical operations without changing the result. In cryptography this becomes useful because you can do mathematical operations on encrypted data and the result is the same as if you did the operations before encrypting. In specific, the product of the encryption of two messages is equal to the encryption of the product of the message. Finding complete homomorphic function pairs is in practice very difficult and the subject of intense research. In these applications we settle for “semi”.</em></p><h4>In Practice — Private Token Transfer</h4><p>In a UTXO (Unspent Transaction Output) based framework (like Bitcoin, which is the basis of Zcash), the sum of the inputs must be equal to the sum of the outputs:</p><pre>output1[toAddress1] + output2[toAddress2] = input1[fromAddress] + input2[fromAddress] + ...</pre><p>where output2[toAddress2] is the change leftover from sending the entire balance (sum of all the inputs) of the address to a separate “change wallet”. This creates a constant chain of transactions for each Bitcoin from their genesis to their current holder. This doesn’t allow the users any privacy besides the pseudo-anonymous relationship between person and address. To fix this, Zcash effectively moved the burden of proving the satisfying of conditions for a valid transaction from the verifier to the prover, allowing the introduction of zero-knowledge proofs between the prover and verifier to shield the details of the transaction.</p><p>In order for the transaction to be valid, the above must return true as well as proving that you have the private key to spend the inputs, input1, input2 and so on. These can all be constructed as zk-SNARK proofs, proving that you hold the private key to spend the inputs and that the outputs sum up equal to the sum of the inputs.</p><p>But now that you have successfully hidden and proven those details for valid transaction, the details of the outputs (the “to” field and the amount), are still visible. So instead of storing the output on the blockchain like what Bitcoin does, Zcash stores an encrypted hashed version of the output as a “Note” on the blockchain. The note would be encrypted with the “transmission key” (think public key) who’s private key counterpart, the “view key” would be used to decrypt the incoming transaction, populating your wallet with the input. This makes it so other users cannot see the amount that is being transferred, nor can they associate the encrypted transaction to the transmission key owner.</p><p>Transactions are now completely opaque on the blockchain and the traditional framework of being able to see who sends what, where they go and who has how much is now solved. Your traditional transaction of two outputs is now a transaction of one zero-knowledge proof for verification and two encrypted outputs. [Fig. 1]</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*TPdFihWIyDveYjcaKgWRkw.png" /><figcaption>Fig. 1 The structure of a Zcash transaction</figcaption></figure><p>So how then do addresses spend these notes and the blockchain keep track of that so no double spending or unauthorized creation of coin occurs?</p><p>The note includes a nullifier value that, when published, signifies that the original note has been spent. The nullifier is hashed with the recipient’s transmission key and made publicly known.</p><p>Spending a note (shielded output) would then entail publishing the nullifiers of the notes you are using to construct your new notes as the inputs of your transaction, basically destroying the old note and creating a new note, nullifier pair. You can see here again the importance of keeping that <em>s</em> hidden.</p><p>This transforms the blockchain from being UTXO to UNN (Un-Nullified Note) based.</p><h4>In Practice — Private Smart Contracts</h4><p>Transactions like described above are really just simple smart contracts. Verify these x criteria and token ownership is transferred. Therefore, applying zero-knowledge proofs to more generalized contracts should, in theory, be about being able to define the problem into a QAP that can define all of the verification criteria of that smart contract. While Ethereum has incorporated zk-SNARK compatibility into their base code, client support has not yet been rolled out. First lets look at a basic transaction to understand the fundamental differences between it and Zcash.</p><p>In an account based transaction framework (like Ethereum), there exists a mapping between addresses and balances and when sending a transaction of amount value , the following must be satisfied:</p><pre>balances[fromAddress] &gt;= value</pre><p>and is done to make sure that the address has enough token to send the transaction amount.</p><p>The transaction is also sent with a nonce. Unlike the nonce used in mining (which is just a random number added to the hash in order to make it fit a pattern) this nonce is used to assure that the transactions are maintained in the order they are to be processed. If the nonce is not one or more than the nonce of the previous transaction, the transaction will be rejected.</p><p>These two validating criteria, along with proving you have the private key to sign transactions for that address, can be represented as zero-knowledge proofs fairly easily.</p><p>But what about interacting with a contract? Contracts not only require the above but also require some amount of input that is dependent on the contract itself. Implementing zk-SNARKs for a contract would entail enabling the contract to verify zero-knowledge proofs and transforming function calls or satisfying the conditions of the contract to deal with encrypted information. This adds a whole layer to existing contracts which drives gas cost for the transactions. This limits the usage of zk-SNARKs significantly in Ethereum because even for simple contracts, the gas used in order to verify the proof consume half of a block’s worth of gas.</p><p>This has driven a down-selecting of viable smart contracts for zk-SNARKs to ones that can operate with the current block gas limit and with the current efficiencies of this implementation of zk-SNARKs. These precompiled smart contracts have the ability to do simple transactions and elliptic curve operations.</p><p>Zcash is also working with Ethereum in a project called <em>Project Alchemy</em> or <em>Zcash on Ethereum</em> (<em>ZoE</em>). This project is looking to bridge the two blockchains to make use of the programmability of one and the privacy of the other to open up another realm of applicability. This integration would open up the creation of custom anonymous tokens that could be used in dAPPs just as current Ethereum tokens are, enabling real world use of important and sensitive contracts, e.g. voting, identity authentication or other sensitive applications.</p><p>This bridge would be constructed much like what BTCrelay has done with Bitcoin and Ethereum, as is what INT is looking to ease the enabling of with their heterogeneous multi-chain framework. For more on blockchain interoperability,<a href="https://medium.com/@graytrain/interoperability-the-holy-grail-of-blockchain-eac8e689d50d"> read this post</a>.</p><h4>The Future</h4><p>Zero-knowledge proofs find a balance of complete and ensured privacy with the selectability for wide application use. The current drawbacks associated with the resource intensiveness of proof generation is the topic of intense academic research, the latest improvements of which you can <a href="https://eprint.iacr.org/2017/1132">read here</a>.</p><p>With the growing interest in privacy and applicability of blockchains, more effort will be put into developing sound and compete systems for privacy protection and some sort of zk-SNARK implementation will certainly be at the center of it.</p><p><strong>Further reading, which was used as inspiration and material for the article.</strong></p><p><a href="https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/">https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/</a></p><p><em>More about QAPs:</em></p><p><a href="https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649">https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649</a></p><p><em>How Zcash’s parameters were created:</em></p><p><a href="https://blog.z.cash/generating-zcash-parameters/">https://blog.z.cash/generating-zcash-parameters/</a></p><p><a href="https://ipfs.io/ipfs/QmXoypizjW3WknFiJnKLwHCnL72vedxjQkDDP1mXWo6uco/wiki/Zero-knowledge_proof.html">https://ipfs.io/ipfs/QmXoypizjW3WknFiJnKLwHCnL72vedxjQkDDP1mXWo6uco/wiki/Zero-knowledge_proof.html</a></p><p><a href="https://blog.ethereum.org/2017/01/19/update-integrating-zcash-ethereum/">An Update on Integrating Zcash on Ethereum (ZoE)</a></p><blockquote><a href="https://coincodecap.com/?utm_source=coinmonks">Get Best Software Deals Directly In Your Inbox</a></blockquote><figure><a href="https://coincodecap.com/?utm_source=coinmonks"><img alt="" src="https://cdn-images-1.medium.com/max/584/0*OJ-qb5G6i863msBB.png" /></a></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1f4bd8f20d8d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/zero-knowledge-proofs-1f4bd8f20d8d">Zero-Knowledge Proofs</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Blockchain Scaling]]></title>
            <link>https://medium.com/coinmonks/blockchain-scaling-30c9e1b7db1b?source=rss-b87d8eb3b46c------2</link>
            <guid isPermaLink="false">https://medium.com/p/30c9e1b7db1b</guid>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[scaling]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[pow]]></category>
            <dc:creator><![CDATA[Grayblock]]></dc:creator>
            <pubDate>Fri, 31 Aug 2018 20:44:20 GMT</pubDate>
            <atom:updated>2021-11-04T18:33:23.006Z</atom:updated>
            <content:encoded><![CDATA[<h4>Why PoW Networks Can’t Scale</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EqBwuks-8QVt512O6FSkmQ.png" /></figure><p><em>This is only concerned with scaling on layer 1 of the network. Second layer scaling solutions is another topic entirely.</em></p><p><strong>Scaling</strong>, one of the more popular words in the greater blockchain buzzword bingo that has a lot of people demanding it without many understanding the intricacies involved in successfully implementing a lasting solution. Scaling is not as simple as increasing block size and quickening block generation. Transactions have weight, require computation, need to be communicated through all nodes and the blockchains they are included in require storage in their ever growing state. Scalability is therefore heavily dependent on how the specific blockchain handles transactions and node communication.</p><p>In general, one of the core concepts of cryptocurrency, trustless verification, causes the most trouble for scaling. In all blockchain protocols, each node stores all states with account balances, contract code, and entire transaction history, in order to trustlessly verify a transaction’s validity for each transaction in the network. This provides a large amount of security but limits scalability to not being able to process more transactions than any single node in the network can. This is the biggest variable in setting the ceiling for transaction volume at ~3–7 transactions per second for Bitcoin or 7–15 TPS for Ethereum. Visa processes ~2,000 transactions per second and an IoT network with an estimated 50 billion devices could produce several times that. <em>That’s a large gap.</em></p><p>So if we want to expand into the future and create the real world usable networks that we all envision them to be, we have to find other ways to scale. Second layer solutions that stretch each of those transactions to the settlement of larger groups of transactions, like Lightning, are a valid path and one that even Satoshi conceived for Bitcoin.* But more can be done to the first layer to establish it as more able to scale with higher throughput to push out the need for more extreme first or second layer solutions or make them a natural evolution within the network.</p><h3>Defining the Problem</h3><p><em>We are going to talk about the problem in terms of Bitcoin pre-SegWit as this complicates things and turns the discussion from easy to understand block size to less easy, block weight</em></p><p>What prevents a network from processing more transactions? There are two types of constraints: physical resource constraints and software constraints. Data communication is limited by the speed of light, bandwidth determines how much data can be sent in time, CPUs limit how much processing can be accomplished, blockchains grow and after all of that, the network has to remain secure and resilient against attack.</p><p>At the very base of the problem, we have network latency, how long it takes for data to travel. This is dependent on the size of the transaction but in most global networks this is about 2–3 seconds. Currently, transactions are about 500 bytes for Bitcoin and 150 bytes for Ethereum so if we want to compete with Visa the network must be able to communicate at 8 Megabits per second. This is relatively common Internet speeds for today.</p><p>At this theoretical rate of transactions that means the nodes in the network must be able to process 500 bytes x 2,000 tps = 1 MB amount of transactions per second. Processing a transaction involves hashing and <a href="https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm">ECDSA</a> signature verifications. RIPEMD-160 and SHA256 (both hash algorithms) run at about 100 megabytes per second, so 2,000 transactions could be processed in about 10 milliseconds, so fast enough that we don’t need to worry about it.</p><p>A Bitcoin node does do other things above verifying transactions, but this process takes up the majority of the processing power required to run a node.</p><p>Ethereum is a little different in that it doesn’t have a traditional block size but a per block gas limit. Gas is the payment unit used to pay for the computations required to process the transaction. This is a consistently reevaluated value based on the current processing, storage and bandwidth conditions of the network. This is important because not every transaction is just used for transferring an asset but may be used to signal a contract or carry data to it which requires the network to do some level of extra computation.</p><p>The only resource concern then that increasing transaction rate brings is increased requirements for node storage which may lead to a centralization of nodes based on higher cost of equipment. If the rate of transactions increases by way of block size increase or block generation rate, the blockchain would grow at a corresponding rate. Currently, the Bitcoin blockchain grows at a max rate of about 1 GB a week (max rate of about 4 GB for SegWit enabled Bitcoin). If the block size is doubled, that rate would be 2 GB a week, tripled it would be 3 GB a week and so on. (Imagine if Bitcoin Cash, with its 32 MB blocks, were filled. The blockchain would grow at a rate of 4.5 GB per day.) If the block production rate increases, this would have the same effect. This poses a node centralization risk if this is done too early putting the node storage requirements out of financial reach for common people. So while it is something to keep in mind in terms of the implementation timing of certain scaling techniques in relation to technology cost, it is not a base concern.</p><p>As we saw above, all the operations of processing a transaction, from the propagating through the network, to the hashing and verifying, do not pose any real physical resource constraints on transaction throughput in our current networks. What does currently stop us from going faster is the size of the transactions, the size of a block (how many transactions you can fit in the block), how often a block gets added to the chain and the mechanism by which the nodes collaborate to add transactions to the chain.</p><h4>Anatomy of a Transaction</h4><p>Bitcoin and Ethereum transactions are fundamentally different but the data within is relatively similar. In a UTXO framework like Bitcoin, the transaction has two sections, the input data, and the output data. In an account based network like Ethereum, the transaction is not dependent on proving you possess the private key to spend an output but in having enough balance in your wallet for that transaction. This makes Ethereum transactions quite a bit smaller than Bitcoin transactions and fairly consistent in their size. Bitcoin transaction size is heavily dependent on the number of inputs and outputs included in the transaction.</p><p>In the most simplified Bitcoin transaction, pay-to-public-key-hash, where you are sending as an output the entirety of an input with no change address required, there are two main chunks of data, the input and the output. For each of those we will need the signature, the public key, the previous unspent output, the new output public key and the amount (with some little tidbits here or there). This looks like this (though not this nice):</p><pre>&lt;Version&gt;<br>01000000 <br>&lt;Input No.&gt;<br>01<br>&lt;Unspent TX Output&gt;<br>be66e10da854e7aea9338c1f91cd489768d1d6d7189f586d7a3613f2a24d5396<br>&lt;Output Index&gt;<br>00000000</pre><pre>&lt;scriptSig:scriptPubKey&gt; <br>19 76 a9 14 dd6cce9f255a8cc17bda8ba0373df8e861cb866e 88 ac</pre><pre>&lt;Sequence&gt;<br>ffffffff</pre><pre>&lt;Output No.&gt;<br>01<br>&lt;Tx Amount in Little Endian&gt;<br>23ce010000000000<br>&lt;Output Script&gt;<br>19 76 a9 14 a2fd2e039a86dbcf0e1a664729e09e8007f89510 88 ac</pre><pre>&lt;Lock Time&gt;<br>00000000 <br>&lt;Hash Code Type&gt;<br>01000000</pre><p>and without the nice titles and spacing:</p><pre>01000000 01 be66e10da854e7aea9338c1f91cd489768d1d6d7189f586d7a3613f2a24d5396 00000000 19 76 a9 14 dd6cce9f255a8cc17bda8ba0373df8e861cb866e 88 ac ffffffff 01 23ce010000000000 19 76 a9 14 a2fd2e039a86dbcf0e1a664729e09e8007f89510 88 ac 00000000 01000000</pre><p>Once all of that is set, we have to sign the transaction that shows that we own the address of the output included in this transaction. This consists of a DER encoded signature generated with the private key and the corresponding DER encoded public key. We then use this to replace the &lt;scriptSig:scriptPubKey&gt; portion of the input, and completes our transaction for .00128307 BTC:</p><pre>01000000 <br>01 <br>be66e10da854e7aea9338c1f91cd489768d1d6d7189f586d7a3613f2a24d5396 00000000</pre><pre>8c 49 3046022100cf4d7571dd47a4d47f5cb767d54d6702530a3555726b27b6ac56117f5e7808fe0221008cbb42233bb04d7f28a715cf7c938e238afde90207e9d103dd9018e12cb7180e <br>01 41 042daa93315eebbe2cb9b5c3505df4c6fb6caca8b756786098567550d4820c09db988fe9997d049d687292f815ccd6e7fb5c1b1a91137999818d17c73d0f80aef9</pre><pre>ffffffff <br>01 <br>23ce010000000000 <br>19 76 a9 14 a2fd2e039a86dbcf0e1a664729e09e8007f89510 88 ac <br>00000000</pre><p>Or:</p><pre>01000000 01 be66e10da854e7aea9338c1f91cd489768d1d6d7189f586d7a3613f2a24d5396 00000000 8c 49 3046022100cf4d7571dd47a4d47f5cb767d54d6702530a3555726b27b6ac56117f5e7808fe0221008cbb42233bb04d7f28a715cf7c938e238afde90207e9d103dd9018e 2cb7180e 01 41 042daa93315eebbe2cb9b5c3505df4c6fb6caca8b756786098567550d4820c09db988fe9997d049d687292f815ccd6e7fb5c1b1a91137999818d17c73d0f80aef9 ffffffff 01 23ce010000000000 19 76 a9 14 a2fd2e039a86dbcf0e1a664729e09e8007f89510 88 ac 00000000</pre><p>You can see that once the transaction is signed, the signature is about 65% of the transaction data. This would be a good place to work in order to reduce transaction weight. This is in fact what SegWit does, it segregates the witness (signature) from the transaction data, reducing the transaction weight by 65%, by moving it to a new merkle tree in the coinbase transaction. This along with changing how the block size is evaluated, effectively quadrupled the size of the block.</p><p>This transaction format also grows rapidly with the number of inputs and outputs. If the transaction requires two inputs (to cover the amount of BTC sent) and two outputs (one for a change address), as is most common, the transaction size doubles. Larger transactions of larger sums including a large amount of smaller inputs would then become quite heavy. In fact, this is an effective way to attack the network and clog blocks. This was, arguably, what occurred during the scaling debate where Bitcoin Cash tried to overthrow Bitcoin for the top spot. Transactions were sent for relatively small amounts containing many inputs and therefore creating transactions so heavy the number of transactions that could be included in a block was significantly reduced. In several instances, this took the average number of transactions in a block from over 2,000 to <a href="https://www.blockchain.com/btc/block/00000000000000000182aabc399d2daec86b50d510701a5fd098793a4eadead4">under 100</a>. This is currently still an issue but one that has a proposed solution.</p><p>Schnorr signatures is a proposed change to Bitcoin’s current Elliptic Curve Digital Signature Algorithm that essentially allows the combination of keys to provide an aggregate signature for many inputs. This would reduce the need to provide a signature for every input to a combined signature for all inputs, thereby reducing the weight of the transaction and nullifying the attack vector.</p><p>Ethereum transactions are much simpler because of it’s account/balance framework. In Ethereum, you do not have to provide inputs to supply your output, you just have to provide:</p><pre>to: &#39;0xAb5801a7D398351b8bE11C439e05C5B3259aeC9B&#39;,<br>value: &#39;1000000000&#39;,<br>gas: 2000000,<br>gasPrice: &#39;234567897654321&#39;,<br>nonce: 0,<br>chainId: 1</pre><p>Then sign it by using your private key. As you can see, since the nodes maintain a state database of accounts and their balances, transactions are quite a bit lighter and of consistent size, assuming they aren’t passing a significant amount of data for a contract execution.</p><p>So, we are fairly limited to how light we can make transactions. An irreducible amount of data has to be passed and there is only so much compressing of the signature that can be done. We therefore only have two more recourses to increase the throughput of transactions through the network, increasing the size of blocks and how often they are generated.</p><h4>Block Size — Is Bigger, Better?</h4><p>Increasing the block size is the next logical step in increasing the number of transactions through the network. Doing so is straightforward in its implementation but it does have some side effects.</p><p>The most obvious of issues that arise from increasing the block size is the increased storage requirements for maintaining a full node. In the case of Bitcoin Cash, which recently increased their block size to 32 MB, the blockchain will grow at a rate of 4.5 GB per day (assuming all blocks are full, which they are not, they average 50 kB). This could push the costs required to maintain a full node outside that of a dedicated hobbyist, further centralizing a network. Again, this concern is one of timing with the cost of technology and less of a concern in security.</p><p>What is of significant concern is forks caused by block distribution time. In typical PoW frameworks, where computers compete to produce valid blocks, all nodes build upon the latest valid block in the chain. Once the newly formed block is created, it needs to be distributed through the node network and the time it takes for that block to be communicated can become an issue as blocks get bigger.</p><p>The impact of this was investigated by <em>Sompolinsky et al. (2013)</em>. They found that the average block propagation time was 2 seconds plus .08 seconds per kilobyte in the block (this has since been improved to .008 seconds per kilobyte due to transaction propagation improvements) [Fig. 1]. This would mean for a full 32 MB block, it would take 258 seconds (4.3 minutes, nearly half the block time) for that block to propagate to the edge of the network, meaning the nodes nearer the center of the latest block discovery would have a tremendous head start in generating the next block, further centralizing an already less-than-decentralized network.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/919/1*K5h5NqBxFGRbq78QPe9rjw.png" /><figcaption>Fig. 1 Block propagation time versus block size in the left panel shows that at pre-SegWit 1 MB Bitcoin blocks, block propagation takes over 60 seconds to penetrate 50% of the node network. Taken from Sompolinsky et al. 2013 “Secure High-Rate Transaction Processing in Bitcoin”</figcaption></figure><p>They also found as a side effect of this that as the blocks got bigger, and the time it takes new blocks to propagate through the network increases, as does the probability of a node producing a block before it learns of this new block. When this happens, the network forks by having two blocks at the same block height. To the nodes in the network, there is no one chain longer than the other, so they coexist, building transaction histories of their own. The amount of time it takes to rectify this split depends on the amount of computing power dedicated to each fork. The first to become the longest chain (and therefore has the most hash power behind it) becomes the main chain, thereby discarding all blocks that don’t fit into the winning chain’s transaction history. These unaccepted but valid blocks are called several names: stale, orphans or uncles. This may be one block, or it may be many, depending on how long the contentious fork has existed. This also means that any transactions in those blocks and any block rewards for mining them are also rolled back as they no longer exist in the accepted history. You can see why this is a problem. Imagine being transferred bitcoin and watch it get confirmed, only for that transaction to disappear.</p><p>This has a direct impact on the security of the blockchain itself. 51% attacks require the attacker to have more than half the network’s hash power in order to successfully overtake the longest chain and initiate a double spend <em>but</em> this assumes the propagation time of the latest valid block to be negligible compared to block time. If block size becomes too big, the time it takes to propagate more than 50% of the node network becomes comparable to the block time itself, the probability of another alternate chain replacing it becomes higher, thus impacting the finality probability of each confirmation. 6 confirmations will no longer be enough to probabilistically guarantee finality.</p><p>So as the blocks grow in size, so does the propagation time and thus the stale creation rate in the network, creating forks, potentially rolling back transactions and increasing the risk of a double spend attack from increasingly weaker attackers.</p><p>To mitigate these issues, instead of having one large block every 10 minutes, why don’t we speed this up and transmit the same amount of data per time in smaller, more manageable chunks by speeding up the block time?</p><h4>Block Time — What About Faster?</h4><p>It turns out, speeding it up isn’t a simple solution either. As the PoW block generation process is sped up, the time in which these valid blocks are transmitted through the network becomes relevant, even for smaller blocks. The impact is exactly the same as increasing block size.</p><p>Using the same logic from above, each second elapsed before a node in the network learns of the latest block, the chances that node produces a stale block increase proportional to the time elapsed and the block time. For Bitcoin, with its 10 minute (600 second) block time, if it takes your node 5 seconds to learn of the new block then the probability your node would produce a block that is not canonical to that new block during that time increases by 5/600 or 0.8%. A small increase, sure, but it is non-zero. In the current Bitcoin network (post-SegWit), with a full block (~4 MB) it would take roughly 35 seconds for that block to propagate the network, so the probability the nodes on the edge of the network will produce a stale block increases by 35/600 or 5.8%. No longer negligible and in fact, these forks are happening all the time, as shown by Decker and Wattenhofer in their 2013 study in information propagation in the Bitcoin network [Fig. 2].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1hZDd8dZdaDyUwmTxyHDWA.png" /><figcaption>Fig. 2 Observed stale rate under normal conditions in Bitcoin. Taken directly from Decker et al. 2013 “Information Propagation in the Bitcoin Network”</figcaption></figure><p>So making the block time faster is much like making blocks bigger, increasing centralization and decreasing security, impacting finality of transactions and overall reducing the security of the network, opening it up to double spend attacks by increasingly weak attackers.</p><h3>The Core of the Issue</h3><p>So while we might be able to squeeze out a little more throughput by manipulating these variables, this will only ever get us so far, and nowhere near Visa level outputs.</p><p>Ethereum is a good example of this, with it’s 15 second block time and 90 kB (adaptable) max block size. That is about 3.6 MB of blocks every 10 minutes, about the same as current SegWit Bitcoin! And even this only allows for about 15–30 transactions per second.</p><p>Wait wait wait…</p><p>So how then is Ethereum able to get by with it’s 15 second block time? Their stale rate must be through the roof! Well, it is. Using the technique above, 15 second block time with an average block size of 25 kB would mean that you would have a max propagation time of about 3 seconds which would mean that the network has a stale generation rate of about 0.2 stale blocks created per block accepted (about 1200 stale blocks per day! That would be a lot of wasted energy). This is in line with the data we currently see in the network also. Fortunately, they thought about that when designing it and made it a feature to make their blockchain more secure. They implemented a novel technique for dealing with decreased security and centralization risks that come with this block generation speed. “Greedy Heaviest Observed SubTree” (GHOST) was proposed by <em>Sompolinsky et al. (2013)</em> when investigating possible scaling techniques to use in Bitcoin. It changes the definition of the main chain from being that of the longest chain of valid blocks to being the one with the most stale descendants (<em>heaviest</em>) of the block’s ancestor as a way to calculate which blocks have the largest total proof-of-work backing it. This fixes the problems associated with stale generation and forking, rewarding the inclusion of them in the blockchain and not wasting the energy used in creating those stale blocks.</p><p>And here we come to the absolute core of the issue, the single weak point in the whole framework. Throughout this article there has been one main theme. We can manipulate transaction size, block size and block time, but who processes it? The node. At the end of the day, only one node generates any given block. <strong>As long as every node independently verifies the entirety of all transactions in the network, the network can only process as many transactions as one node is capable of.</strong> In a trustless and decentralized network, that number will always fall short of the goal.</p><p>So what now? The only way to scale to this level of transaction throughput is to divide the burden of verifying transactions in the network between nodes. In PoW networks, there is no way to separate the network.† As long as there is some probability that the chain will switch over to another alternate chain, reverting transactions, every node has to verify everything. If there is no chance transactions of a certain age will be reverted, there is no reason to have nodes maintain a complete history, just a state of accounts.</p><h4>Notes</h4><p>*<a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002417.html">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002417.html</a></p><p>†<em>The only way to do this is in PoW networks is to have side chains that utilize the main chain as the settlement layer, turning one main chain transaction into the verification of many transactions. This is what Lightning Network does for Bitcoin. The side chain verifies batches of transactions then sends the pre-verified batch as a single transaction to be included in a block. This limitation is because of the probabilistic nature of finality in PoW networks.</em></p><p><a href="https://en.bitcoin.it/wiki/Scalability">https://en.bitcoin.it/wiki/Scalability</a></p><p><a href="http://www.gsd.inesc-id.pt/~ler/docencia/rcs1314/papers/P2P2013_041.pdf">http://www.gsd.inesc-id.pt/~ler/docencia/rcs1314/papers/P2P2013_041.pdf</a></p><p><a href="https://medium.com/@jonchoi/ethereum-casper-101-7a851a4f1eb0">https://medium.com/@jonchoi/ethereum-casper-101-7a851a4f1eb0</a></p><p><a href="https://github.com/ethereum/wiki/wiki/Sharding-FAQ">https://github.com/ethereum/wiki/wiki/Sharding-FAQ</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=30c9e1b7db1b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/blockchain-scaling-30c9e1b7db1b">Blockchain Scaling</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Blockchain Finality]]></title>
            <link>https://medium.com/coinmonks/blockchain-finality-in-iot-79e466406133?source=rss-b87d8eb3b46c------2</link>
            <guid isPermaLink="false">https://medium.com/p/79e466406133</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[finality]]></category>
            <category><![CDATA[iot]]></category>
            <category><![CDATA[dpos]]></category>
            <category><![CDATA[int]]></category>
            <dc:creator><![CDATA[Grayblock]]></dc:creator>
            <pubDate>Thu, 19 Jul 2018 14:01:01 GMT</pubDate>
            <atom:updated>2021-11-04T18:41:24.798Z</atom:updated>
            <content:encoded><![CDATA[<h4>The Importance of Finality In Cross-Chain Communication</h4><blockquote>“Objective and unambiguous 100% finality is a critical property for all blockchains that wish to support inter-blockchain communication. Absent 100% finality, a reversion on one chain could have irreconcilable ripple effects across all interconnected chains.” — Daniel Larimer</blockquote><p><em>This will be a two part series in the finality and scalability in interconnected networks.</em></p><p><strong>Finality</strong>, <em>the irreversibility in the transferring of ownership</em>, is something that many of us don’t think about in our day-to-day dealings. We trust that when we see our paycheck arrive in our bank account that the money is ours to spend, that when we swipe our card buying groceries that once it says “Approved” we can walk out of the door with what we bought and when we see that bitcoin show up in our wallet, that it is officially ours, but behind all of this is a carefully considered judgment on the probability of the transaction that just occurred being reverted. As is the case with most imperceptible things that are part of the basic fabric of our life, it is essential to the normal operation of every transaction based system.</p><p>Finality is never an absolute. Mistakes can be made, banks can burn down, glitches happen and there are bugs in code. Something can always happen with some degree of probability that can take away what was previously in your possession. In centralized systems of trust, like banks, finality is up to the bank to make sure you have the funds and the permissions in order to transact and no one but them can decide on a valid history. In blockchains however, just because a transfer was made, doesn’t mean the network won’t decide to switch to a different valid chain a moment later which wipes that transaction from history.</p><h3>Why is finality important in interoperable networks</h3><p>If a network is looking to be a network of interoperating chains, where contracts and actions taken inside that network will be dependent on the data and transactions in multiple chains, finality becomes a crucial variable. Transferring anything of value based on information from a secondary chain without the ability to guarantee that the information on that chain will not be reverted is a recipe for an abandoned network.*</p><h3>Finality in blockchains</h3><p>Because of the lack of centralized authority, blockchains rely on distributed agreement on what is a valid history. Because this agreement takes a finite amount of time and is not guaranteed, it is possible that transactions become part of a block or chain that does not become the future accepted chain. This is why transactions normally require a number of “confirmations” from the network before you can use what you received. With each additional block, and therefore, confirmation, the transaction is further verified and the likelihood of that transaction being reversed is reduced.</p><p><em>But why does it matter?</em> Why not just figure out the optimal number of blocks before the chance of it being reverted is significantly small and set-it-and-forget-it? Well this certainly works in asset transactions like Bitcoin, Ethereum and any other cryptocurrency and is what exchanges do when they receive your deposit. They wait till that transaction gets to a certain “depth” in the blockchain before allowing you to trade it.</p><p>But what about in a system that passes data of varying worth or significance, or a network that interoperates with another network? In an IoT network, having your weather sensor send a reading of 70° F and it not being available for use for 10 minutes until it gets “fully” confirmed doesn’t make sense. While on the other hand having a complex contract rely on an asset transfer on a chain that gets reverted after that contract was already verified could have large scale consequence. You can see that depending on the situation, finality becomes much more complex and in a network of interoperating chains, full reliance on the finality of a transaction on a chain is essential to operation.</p><h3>Why the choice of consensus mechanism is important</h3><p>The definition of settlement finality within a blockchain network is wholly dependent on the consensus mechanism, block generation time and node communication. These three variables determine points of failure and time to finality of a certain confidence level.</p><h4>In PoW</h4><p>In PoW networks there is never 100% finality. As the transaction gets deeper in the blockchain, the probability of it not being considered a valid chain decreases but is never eliminated. There is always the risk that miners may switch to a chain that starts from a block that was before the block which your transaction was a part of and doesn’t include that block.</p><p>The PoW consensus mechanism uses the longest chain, which therefore means the chain with the most work done on it and consequently, the most miners, as the accepted main chain in the network. It is therefore possible for there to be many alternate chains at a given moment, each proposing a new timeline of events. If one of these forks continues to have miners working on it by result of a bug in the system or malicious intent, 2 equally valid histories begin to form. <a href="https://bitcoinmagazine.com/articles/bitcoin-network-shaken-by-blockchain-fork-1363144448/">This happened in 2013</a> in the Bitcoin network when there was a bug in one version of the software but not the other that essentially created two competing chains which went on for 6 hours after which the problem resolved itself as one chain conclusively became longer than the other, thereby nullifying the alternate chain and erasing the history of those 6 hours of transactions.</p><p>So how do we determine when we can trust the finality of a transaction in a PoW network? We can define the problem by imagining someone wanted to do this on purpose in the form of a double-spend attack and work through this mathematically. Lets assume they have no more than 25% of the network hashpower at their disposal and we want to be more than 99% sure that the transaction will not be reverted. In this case there is only a 25% chance that this alternate chain will add a block before the main chain does and a 75% chance it will not and therefore lose ground in the race to be a longer chain. This works out mathematically to:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j0-6A2DaBQXEwuM1lB3-DA.png" /></figure><p>Where <em>x</em> is the number of “steps” or blocks that the alternate chain has to make up in order to be longer than the main chain and <em>F</em> is the probability that it will succeed. Finality, <em>f</em>, is therefore defined as <em>1-F.</em></p><p>For 1 block behind, the result is 33%. Meaning that if we only waited one block or confirmation, and there was a malicious actor with 25% network hashpower, they could revert a transaction with 33% success over one block.</p><p>With each step, or block we wait, the probability of the alternate chain taking over goes down exponentially.</p><p>For 2 blocks, it’s 11%; for 3 blocks, it’s 4% and so on. And after 6 blocks it is .1%.</p><p>This is why the general accepted finality for a PoW network is 6 blocks or confirmations. At that point, the probability of your transaction not being reverted by a chain which has it’s origin before that block is about 99.8%.</p><p>And if you would like a higher confidence in that transaction finality, waiting 10 blocks is 99.998% and 15 blocks is 99.999993%. This also shows that the probability never goes to 0, so 100% finality is impossible.</p><p>And this is why centralized control of 51% of the network hashpower is a concern. A concerted effort to create a mass double spend attack becomes a real possibility with high probability of success if the actor has 51% of the network hashpower.</p><p>So how long do we have to wait to get this 99% finality? This is where the block generation time becomes important in the time to finality. In Bitcoin, with it’s 10 minute block time, 6 confirmations is 60 minutes. In Ethereum, with it’s 10 second block time, 6 confirmations is 1 minute.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/580/1*_7qpJrXmOfuJBnr5hwWE5g.png" /></figure><h4>In PoS</h4><p>In PoS networks, finality is not defined using the longest chain but by the number of validators signing a block. If you are not familiar with PoS, validators serve as the miners in the network with their mining “power” or influence being proportional to the amount of coins they own. If you are a validator and own 2% of the total amount of coins in the network, you would validate 2% of the transactions or 2% of the blocks in the network.</p><p>The problem with PoS validators is that it doesn’t inherently protect against alternate chains like PoW mechanisms with their longest chain rule. There is nothing to protect against a portion of the validators voting for one block and then voting for another contentious block as well, creating two chains. This is called the <strong>Byzantine Generals’ Problem </strong>and every PoS system must protect against it in some capacity, even in trusted systems.</p><p>In the Byzantine Generals’ Problem, the actions taken by an army, whether to attack (validate a given block) or retreat (not validate a given block), is made with all of the generals (the validators) of that army coming to a common decision. In order to ensure those generals are acting in the best interest of the army they support, a system has to be formed to make sure malicious actors (the dishonest validators in this case) are nullified or punished for their actions. Solutions to the Byzantine Generals’ Problem are called <strong>Byzantine Fault Tolerance.</strong></p><p>In the simplest case, tolerance to this kind of attack can be achieved if the honest validators have the majority agreement and any dissenting vote is not considered. While this will stop any split in the network, it does not dissuade the validators from being dishonest (the Nothing-At-Stake Problem). In many PoS networks this is done by punishing those that vote against a valid block and the majority.</p><p>The details of how many validators are needed for consensus and the penalties for dishonest validators are dependent on the specific implementation. In general, the standard for Byzantine Fault purposes is 2/3 of the network validators in agreement for total consensus.† This maximizes the amount of validators needed in order to attack the network, thereby preventing network split and validator collusion, while minimizing the amount of validators needed for majority decision.</p><p>Penalizing dishonest validators is a more nuanced argument which leads some networks forfeiting your validator reward for a given time, revoking of your validator privileges like EOS or burning the entirety of your staked coin holdings like the proposed Ethereum Casper PoS Implementation (as Vlad Zamfir put it, imagine a version of proof of work where if you participate in a 51% attack your mining hardware burns down). The point here is to make it economically wise for validators to be honest and act in their own best interest.</p><p>In addition to economic finality, where the cost of colluding for a chain reorganization assures finality, there is also subjective finality where the software itself decides a window of changeability. The clients decide to not overturn finality after a predetermined block depth, thereby making it an iron clad finality no matter what a collection of validators propose to the contrary.</p><p><em>Okay, getting back to finality.</em></p><p>With all that said, in PoS networks, time to finality, <em>f</em>, is defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VnOPXg03bDe6W9agoD4wjA.png" /></figure><p>where <em>n</em> is the number of validator nodes in the network needed for consensus and ω is the protocol overhead (the number of messages per second that validators need to process). This is very similar to the classical physics problem of <em>speed = distance/time</em> where if you want to process <em>n</em> messages (distance) in <em>f </em>time, then the number of messages per second (speed) is <em>ω = n/f</em>. You can see with this three variable problem that you can only chose the best scenario for one variable or have a mix of less than optimal values. Putting this into diagram form:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/386/1*bl_YlABslQSvEABZ4lGj0w.jpeg" /><figcaption>From Vlad Zamfir’s paper on Ethereum Casper Protocol</figcaption></figure><p>So you can only be king in one domain. Do you want high decentralization and low overhead? The finality time will be very long. Do you want high decentralization and low finality time? The nodes will have high demands on performance. Do you want low overhead and low finality time? You will have to limit the network to a small number of nodes. Of course there is an infinite variety of in-betweens that yield a spectrum of compromises.</p><p>The number of messages per second, <em>ω,</em> is dependent on the mechanism chosen. In PBFT or DBFT every node must send their response to block proposal whereas in chain based PoS or DPoS the network selects one validator to validate the block.</p><p>For BFT mechanisms, since every node must send a message signing the block before the next block can be made, the number of messages per block is one to (block proposal) and one from (block signature) each node per block time, <em>B</em>, or: <em>ω = 2n/B. </em>For PoS mechanisms, since there is only one validator per block, there is only one message per block time so <em>ω </em>simplifies down to <em>1/B.</em></p><p>Plugging in the numbers, lets assume we have a PoS network with a 5 second block time (fast-ish) so <em>ω = 1/5, </em>and 10,000<em> </em>validators (highly decentralized). That gives us a finality of 10,000/(1/5) or 10,000 * 5 or 50,000 seconds (~14 hours). If we want to have a network of equally fast block time but a quick finality time we have to sacrifice decentralization to limit the network validators. With 30 validators, this would give us a finality of 30 * 5 = 150 seconds (2.5 minutes). Of course you can take a middle ground and have 1000 validators, require those validators to communicate more at 1 message per second which would yield a finality of 1000 seconds (~17 minutes).</p><p>Because BFT mechanism requires a response from at least 2/3 of the nodes in the network for consensus, they achieve finality much quicker for a given network setup at the expense of overhead proportional to the amount of validators in the network. Taking the examples above, for a DBFT network with 5 second block time and 10,000 validators, the overhead <em>ω = 20,000/5 or 4,000 messages </em><strong><em>PER SECOND</em></strong><em> </em>which gives us a finality of<em> 10,000/4,000 or 2.5 </em>seconds, versus the<em> 50,000 </em>seconds in the equivalent DPoS setup.</p><h3>Notes and References:</h3><p><em>*To further emphasize the importance, imagine a scenario where a smart contract is in place that transfers the ownership of real estate on one blockchain upon the successful transfer of a cryptocurrency. This transfer takes place and the ownership of the real estate is transferred only to have the payment be reverted on the payment chain. This type of event on any scale and of any value is unacceptable.</em></p><p>†<em>2/3 is standard for byzantine-fault-tolerance purposes. If you require 3/4, then 26% can collude to prevent finality, and if you require 51% then with 2% byzantine actors plus a network split you can create a scenario where one half of the network finalizes A and the other half finalizes B. A 2/3 threshold ensures that both of these attacks require 1/3 byzantine to pull off, which has been mathematically proven to be as safe as you can get. — Vitalik Buterin</em></p><p>From: <a href="https://ethereum.stackexchange.com/questions/1347/in-casper-pos-what-is-a-finalised-block">https://ethereum.stackexchange.com/questions/1347/in-casper-pos-what-is-a-finalised-block</a></p><p>More on Byzantine Fault Tolerance: <a href="http://pmg.csail.mit.edu/papers/osdi99.pdf">http://pmg.csail.mit.edu/papers/osdi99.pdf</a></p><p><a href="https://medium.com/eosio/dpos-bft-pipelined-byzantine-fault-tolerance-8a0634a270ba">https://medium.com/eosio/dpos-bft-pipelined-byzantine-fault-tolerance-8a0634a270ba</a></p><p><a href="https://ethresear.ch/t/in-favor-of-forkfulness/1225">https://ethresear.ch/t/in-favor-of-forkfulness/1225</a></p><p><a href="https://blog.ethereum.org/2016/05/09/on-settlement-finality/">https://blog.ethereum.org/2016/05/09/on-settlement-finality/</a></p><p><a href="https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQs">https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQs</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=79e466406133" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/blockchain-finality-in-iot-79e466406133">Blockchain Finality</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Elliptic-Curve Cryptography]]></title>
            <link>https://medium.com/coinmonks/elliptic-curve-cryptography-6de8fc748b8b?source=rss-b87d8eb3b46c------2</link>
            <guid isPermaLink="false">https://medium.com/p/6de8fc748b8b</guid>
            <category><![CDATA[rsa]]></category>
            <category><![CDATA[elliptic-curve]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Grayblock]]></dc:creator>
            <pubDate>Fri, 29 Jun 2018 17:04:25 GMT</pubDate>
            <atom:updated>2022-06-26T18:42:32.337Z</atom:updated>
            <content:encoded><![CDATA[<h4>The Curves That Keep The Bitcoin Secure</h4><p>This isn’t an easy subject but it is one that has wide ranging applications and is therefore worth putting in the effort to understand. It has enabled a reduction in key generation time and key weight over first generation public key systems like prime factorization cryptography, as well as a 10-fold increase in security and it serves as the basis of much of the public key cryptography in today’s cryptocurrency ecosystem. So let’s break it down so we can trust it.</p><h4>Hey Alice, pass the key.</h4><p>First, let’s rewind. Say you want to send a message to someone and you don’t want anyone to read it but that person. So you “encrypt” it in some way that someone cannot read it unless they know how to “decrypt” it. This can be done with a simple jumbling or shifting of the letters in a known way. One of the oldest encryptions known is the Cesar Cipher, does just that. By shifting the letters some number of places <em>X</em>, the words in your message become unreadable [Fig.1]. Once X is communicated, the jumble of letters can be unshifted to decrypt the message.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NQLhEI5GesrCuZVX0YlC-Q.png" /><figcaption>Fig. 1 A Cesar Cipher where the shift is 3. “E” will then take the place of “B”, “F” for “C” and so on.</figcaption></figure><p>There are two significant issues with this method. First, you have to somehow tell the person that you wish to communicate with, the secret key to break the code and trust them to keep it safe. And second, in this age of computers, this is not very hard to break.</p><p>We could come up with another scheme of encrypting the data like using a specific page in a book as the cipher, but in every case I can think of, we need some safe way to communicate to another person the key. How would this be done if we were far away? Communicate through a digital format or trust a third party to share the secret? We have to find another way.</p><h4>Public-Key Cryptography</h4><p>In comes public key (or asymmetric) cryptography. Pioneered by Whit Diffie and Martin Hellman in the late 1970s, public key cryptography uses pairs of keys; one public, which can be known to all, and one private, which is kept secret. This system enables anyone to encrypt a message using the receiver’s public key and that message can then only be decrypted with the receiver’s private key.</p><blockquote>A public key is a key which can lock the door but cannot unlock it.</blockquote><p>This revolutionary step solved the issue of having to share a secret in order to decrypt the message and also enabled the authentication of messages encrypted by the owner of a public key.</p><p>These key-pairs rely on “Trapdoor Functions” which are easy to compute in one direction but much harder to reverse. Based on mathematics, the strength of these key-pairs rely on the computational effort that would have to be expended in order to derive the private key from the public key.</p><h4>RSA</h4><p>In one of the first widely used public-key crytposystems, RSA (Rivest–Shamir–Adleman), you rely on the fact that multiplying large numbers together is easy and factoring them is hard.</p><p>To create an RSA key-pair (without going into too much detail), you select two large prime numbers, multiply them together to get a maximum value (<em>max or MOD, meaning the number where the clock resets to 0</em>), and select one of the primes to be the public key,<em> pub, </em>and use the other prime number to derive your private key,<em> priv. </em>With these three numbers someone can multiply their message by<em> pub</em>, wrap around any numbers that go above<em> max, </em>and the corresponding jumbled mess of numbers can be multiplied by <em>priv </em>to yield the original data.<em> I know it sounds hand-wavey but it’s true (and if you want to see it done simply, take a look at the links at the bottom of this article). </em>It’s kind of like if I hid the hour hand on the clock and rotated the minute hand around it several times then showed it to you. It may say 45 minutes but you don’t know how many times it went around the clock before it landed there. Only I would know.</p><p>The take away is that using this mathematics, you can find 2 numbers such that when you multiply a number by itself a number of times and get a random-looking number, you can then multiply it by itself again a secret number of times to get the original number back.</p><p>The only problem with this is that factoring is a very popular problem and one that is not that very difficult to do on a bit by bit basis. With the advance of computational speed and increased efficiency in factoring algorithms, the prime numbers in the RSA key-pair generation have to continually grow in order to outpace technology and maintain security. This system has therefore become unsustainable and not applicable in mobile or low power situations. Another, more robust, Trapdoor Function had to be found.</p><h4>Elliptic Curves</h4><p>This real world use case of mathematics invigorated the research into more fringe mathematics in the effort to find something that would further revolutionize cryptography.</p><p>In 1985, cryptography based on elliptic curves was proposed independently by Neal Koblitz and Victor Miller.</p><p>Elliptic curves have some curious characteristics that make them useful. They are defined as a curve that is completely smooth (<em>non-singular</em>) and a line between two points on this curve will always intersect a third point (<em>projective</em>) [Fig. 2]. This allows you to quickly hop around this curve easily (computationally) and procedurally come up with an endpoint that has seemingly no relation to the starting point and is very difficult to reverse the path that led you there.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/409/1*KKdvscN4y-NcGZ8Nnx1ZYQ.png" /><figcaption>Fig. 2 Elliptical curve with points defined as y² = x³ + ax + b</figcaption></figure><p>In the cryptographic usage, the same ideas of finding two unique numbers (points in a two dimensional curve) which are related and a max ceiling to wrap around apply.</p><p>How do we go about getting two numbers that are related but in a way that no one can tell? Well we use the curve’s projective property and draw a line tangent to the starting point <em>P, </em>finding where it intersects<em> </em>the curve at a second point<em> P</em>ʹ. Then flip the axis and draw a line from that new point (<em>2•P</em>) through the starting point and find the new intersection point <em>P</em>ʹʹ. Then flip the axis and draw a line from that new point (3<em>•P</em>) through the starting point and find the new intersection point <em>P</em>ʹʹʹ etc. (this mathematical operation is called point multiplication) [Fig. 3].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*1-AoW3TBVJCSOHjyER-YFg.gif" /><figcaption>Fig. 3 Point multiplication starting with the tangent to point P and ending with point 3<em>•P</em></figcaption></figure><p>We do this <em>n</em> times and end up with a point on the curve, <em>Q</em>, that has no obvious relationship to the starting point and can be defined as <em>Q=n•P</em> where <em>n</em> is the number of iterations of point multiplication done. Mathematically this works out to <em>Q = P + P + P … n</em> times.</p><p>So if you knew the curve we used, the starting point <em>P </em>and the ending point<em> Q, </em>could you determine<em> n? </em>It turns out there is no known algorithm to do this. No short cuts in determining how many times you “dotted” <em>P</em> in order to get to <em>Q</em>. You basically have to just keep adding <em>P</em> to itself and count how many times you have to do it in order to get to <em>Q</em> (or the other way around). This is fairly easy with small <em>n</em>, but what happens when <em>n</em> gets big? and I mean really big…</p><h4>Elliptic Curves in Application</h4><p>The elliptic curve used by Bitcoin, Ethereum and many others is the secp256k1 curve, with a equation of y² = x³+7 and looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*iOWu6hm-BtFHLB_iO7iwfQ.png" /><figcaption>Fig. 4 Elliptic curve secp256k1 over real numbers. Note that the real implementation of the curve is over a defined prime field of positive integers and therefore looks nothing like the above.</figcaption></figure><p>And has a defined starting point used by all key generation,<em> P(x, y)</em>, with<em> x</em> and <em>y</em> coordinates:</p><p><em>x-coordinate: 55066263022277343669578718895168534326250603453777594175500187360389116729240</em></p><p><em>y-coordinate:<br>32670510020758816978083085130507043184471273380659243275938904335757337482424</em></p><p>As you can see with a starting point THAT big, having an ending point larger than the allowed 512-bit key size is very possible. We therefore have to set a maximum value that we wrap around to establish a field of allowed points that fit our key size.</p><p>For this specific curve the maximum (mod) value is defined by a prime number (to yield a prime field) of:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/1*20auxrni0SabUZk3ecb3DA.png" /></figure><p>OR</p><p><em>115792089237316195423570985008687907853269984665640564039457584007908834671663</em></p><p>OR</p><p><strong><em>115 quattuorvigintillion …</em></strong></p><p>OR</p><p><strong><em>.12% of all the atoms in the known universe.</em></strong></p><h3>aka real big.</h3><p>As negative or non-integer values are difficult to use in computation, we only want to use the integer points in the curve with negative values inversed and use the defined maximum value to wrap values back to 0 as to prevent getting values too large. We end up with something that looks less like a curve, but more like a random smattering of dots, although some symmetry can be seen [Fig. 5].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/752/1*NpvuJWl1uVQlkn2rGOcSKA.png" /><figcaption>Fig. 5 secp256k1 over the field ²⁸+1</figcaption></figure><p>So now with this newly defined “curve”, we do the point multiplication from our new starting point, we wrap around our modulo much like the minute hand going around a clock, and after <em>n</em> times we end on point <em>Q</em> [or <em>A•B = C</em> as shown in Fig. 6].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/954/1*TB-tUijsbiCLGuNJ1kNU0g.gif" /><figcaption>Fig. 6 Point multiplication demonstrated in a finite field</figcaption></figure><p>Since the number of available points is linearly related to the field size (<em>number of points = </em><strong><em>Fᵖ </em></strong><em>+1)</em>, and since there is no easy way to find <em>n</em> given <em>P</em> and <em>Q</em>, you just have to go through the whole list, trying 115792089237316195423570985008687907853269984665640564039457584007908834671663<strong>–1</strong> possibilities to find it (with each one being just as possible as another). So it therefore makes sense to make <em>Q</em> the public key and <em>n </em>the private key with everyone using the same curve and starting point, <em>P</em>.</p><blockquote>So in the end, your private key is just a large integer and your public key is a point on the curve corresponding to your private key point multiplied with the starting point.</blockquote><h4>How “Secure” is Secure?</h4><p>Let’s try to visualize just how secure this is. <strong><em>If the selection of n was truly random,</em></strong> how long would it take for you to find a specific <em>n</em>, or just in general, any “collision” with another, in-use, private key? Lets say you could try 250 billion billion possibilities a second, 5 times the current Bitcoin network hash rate, it would still take 1⁰¹⁰ times the age of the universe to find a match. Basically anything else happening is more probable than finding a match.</p><p>There has been <a href="https://eprint.iacr.org/2013/635.pdf">some research</a> done to establish ways of measuring the security of these encryption types. In these scales, ECC in the defined curve and field above is considered “Globally Secure”, meaning the energy a computer, or group of computers, would have to use in order to find a specific <em>n </em>would be enough energy to boil 1,400,000,000 km³ of water, which is just about all the water on the surface of the earth. That’s <em>probably</em> secure enough.</p><h4>How does this apply to the addresses we see today?</h4><p>Obviously the ways we are used to seeing addresses, being large strings of both numbers and letters, are different than a number and points on a curve. That’s because they are hashed in such a way to reduce the size of the string for light weight ease of use. In Bitcoin, the coordinates of <em>Q</em> are combined and put through a cascade of hashing algorithms designed to compress the key and add a validity checksum for address checking [Fig. 7].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jzBDmsUGdGc-ldgu9jgdhQ.png" /><figcaption>Fig. 7 Bitcoin address creation hash flow</figcaption></figure><p>So hopefully after all that you now understand the ideas behind elliptic curve cryptography a bit better and can trust the security of your cryptocurrencies and private communications to the statistics of cosmically large numbers.</p><p>If you wish to see this explanation in more detail with some encryption examples, check out the below links which served as inspiration for this article.</p><ul><li><a href="https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/">A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography</a></li><li><a href="https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3">What is the math behind elliptic curve cryptography? | HackerNoon</a></li></ul><p><a href="https://eprint.iacr.org/2013/635.pdf">https://eprint.iacr.org/2013/635.pdf</a></p><blockquote>Join Coinmonks<a href="https://t.me/coincodecap"> Telegram Channel</a> and<a href="https://www.youtube.com/c/coinmonks/videos"> Youtube Channel</a> get daily <a href="http://coincodecap.com/">Crypto News</a></blockquote><h4>Also, Read</h4><ul><li><a href="https://medium.com/coinmonks/top-10-crypto-copy-trading-platforms-for-beginners-d0c37c7d698c">Copy Trading</a> | <a href="https://medium.com/coinmonks/crypto-tax-software-ed4b4810e338">Crypto Tax Software</a></li><li><a href="https://coincodecap.com/grid-trading">Grid Trading</a> | <a href="https://medium.com/coinmonks/the-best-cryptocurrency-hardware-wallets-of-2020-e28b1c124069">Crypto Hardware Wallet</a></li><li><a href="http://Top 4 Telegram Channels for Crypto Traders">Crypto Telegram Signals</a> | <a href="https://medium.com/coinmonks/crypto-trading-bot-c2ffce8acb2a">Crypto Trading Bot</a></li><li><a href="https://medium.com/coinmonks/crypto-exchange-dd2f9d6f3769">Best Crypto Exchange</a> | <a href="https://medium.com/coinmonks/bitcoin-exchange-in-india-7f1fe79715c9">Best Crypto Exchange in India</a></li><li><a href="https://coincodecap.com/binance-vs-bitstamp">Binance vs Bitstamp</a> |<a href="https://coincodecap.com/bitpanda-coinbase-coinsbit"> Bitpanda vs Coinbase vs Coinsbit</a></li><li><a href="https://coincodecap.com/buy-ripple-india">How to buy Ripple (XRP)</a> |<a href="https://coincodecap.com/crypto-exchange-africa"> Best Crypto Exchanges in Africa</a></li><li><a href="https://coincodecap.com/crypto-exchange-africa">Best Crypto Exchanges in Africa</a> |<a href="https://coincodecap.com/hoo-exchange-review"> Hoo Exchange Review</a></li><li><a href="https://coincodecap.com/etoro-robinhood">eToro vs Robinhood</a> |<a href="https://coincodecap.com/bybit-bityard-moonxbt"> MoonXBT vs Bybit vs Bityard</a></li><li><a href="https://medium.com/coinmonks/best-crypto-apis-for-developers-5efe3a597a9f">Best Crypto APIs</a> for Developers</li><li>Best <a href="https://medium.com/coinmonks/top-5-crypto-lending-platforms-in-2020-that-you-need-to-know-a1b675cec3fa">Crypto Lending Platform</a></li><li><a href="https://medium.com/coinmonks/free-crypto-signals-48b25e61a8da">Free Crypto Signals</a> | <a href="https://medium.com/coinmonks/crypto-trading-bot-c2ffce8acb2a">Crypto Trading Bots</a></li><li>An ultimate guide to <a href="https://medium.com/coinmonks/leveraged-token-3f5257808b22">Leveraged Token</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6de8fc748b8b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/elliptic-curve-cryptography-6de8fc748b8b">Elliptic-Curve Cryptography</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Who we are]]></title>
            <link>https://medium.com/@grayblock/who-we-are-bd67f4678e69?source=rss-b87d8eb3b46c------2</link>
            <guid isPermaLink="false">https://medium.com/p/bd67f4678e69</guid>
            <category><![CDATA[grayblock]]></category>
            <category><![CDATA[iot]]></category>
            <category><![CDATA[node]]></category>
            <category><![CDATA[internet-of-things]]></category>
            <dc:creator><![CDATA[Grayblock]]></dc:creator>
            <pubDate>Thu, 21 Jun 2018 20:06:20 GMT</pubDate>
            <atom:updated>2018-06-22T23:24:51.136Z</atom:updated>
            <content:encoded><![CDATA[<h4><a href="https://grayblock.network/">We are Grayblock…</a></h4><p>We are a diverse group with backgrounds in Research and Technology, Engineering, Server Administration and Supply Chain, with a combined 7 years of experience in node building and maintenance to carry us into the next era of blockchain technology. We are a team that shares one passion in blockchain technology and it’s application in the future.</p><p>The current state is changing fast and we are taking it upon ourselves to be a part of the revolution, by propping up ecosystem with nodes or masternodes, located around the world, serving as data and transaction maintainers and verifiers.</p><p>We also understand that the main hurdle in realizing this future is in people understanding the technology, driving use and community effort in demanding usability and creating a market. Our technology experts are therefore actively involved in the community, eager to share their knowledge and passion with others, making this technology more accessible to every day people.</p><h3>What we do</h3><h4>Node Setup, Hosting and Support</h4><p>Whether it is hosing a masternode, supernode or anything in between, we have 7 years experience building and hosting nodes for a variety of cryptocurrencies to make sure you do it right. We have servers located around the world to fit your needs, whether it is cloud based or bare metal.</p><h4>Consulting</h4><p>If you want to get started but don’t know where to start, we can help! From simple wallet setup to building mining rigs to hosting masternodes, we know it all. Our team has a long history in everything cryptocurrency and can help you get to the destination of your choosing.</p><h4>Teaching</h4><p>We recognize that one of the most important parts to getting people involved and invested is in people understanding the technology and how to use it for their needs. Our team is passionate about sharing our knowledge and making it easy to understand for all. If you would like one of our team members to talk at your event or even one on one, let us know!</p><h4>Writing</h4><p>As an extension of our passion to teach, we have a technical expert on our team that regularly writes articles concerning a wide variety of technology and has a real talent for making the complex, accessible. If you would like an article written for your project or website (whitepapers included!), send us an email.</p><p>As we continue to grow we will be posting here, on Medium, updates to our business, upcoming events, as well as technical articles written by our technical expert.</p><p>Feel free to contact us if you have any questions or comments.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bd67f4678e69" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>