<?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[Xord - Medium]]></title>
        <description><![CDATA[Making our contribution to the inevitability that is decentralization, by building powerful products, nurturing ideas and launching them as ventures into the expanse, and providing incubation to organizations with similar vision for the world. - Medium]]></description>
        <link>https://medium.com/xord?source=rss----a7974b2f8a92---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Xord - Medium</title>
            <link>https://medium.com/xord?source=rss----a7974b2f8a92---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 05:41:50 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/xord" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[An Organization is only as good as the Individuals Running it]]></title>
            <link>https://medium.com/xord/an-organization-is-only-as-good-as-the-individuals-running-it-9613999cdc4f?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/9613999cdc4f</guid>
            <category><![CDATA[culture]]></category>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[unique-company-culture]]></category>
            <category><![CDATA[the-xordian-way]]></category>
            <category><![CDATA[xord]]></category>
            <dc:creator><![CDATA[Kanza]]></dc:creator>
            <pubDate>Thu, 02 Mar 2023 07:11:40 GMT</pubDate>
            <atom:updated>2023-03-02T09:41:54.676Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*JIdaox2l-b3y5x5JwO8f9g.png" /><figcaption>By Kanza Nadeem</figcaption></figure><p>Ever heard the story about a Zappos employee ordering a bouquet for a customer who, they learned, had a medical condition affecting her feet? Or when a flight attendant on Southwest Airlines when learned that a passenger was flying to attend the funeral of a loved one, wrote a heartfelt note on a napkin and gave it to the passenger to offer condolences?</p><p>These stories highlight the impact a company’s culture can have on employee behaviour and how it goes beyond just material perks or benefits.</p><p>Although cool offices, free swag, and extravagant perks are not inherently negative, a truly exceptional company culture extends beyond those superficial elements. Rather, it is a way of life that establishes a framework for our actions, shaping the way we think, act, and interact with others.</p><p>Culture is who you are, as well as what you stand for. Every organization has its unique style of working which often contributes to its culture. The beliefs, ideologies, principles and values of an organization form its culture. Xord has a distinct and forward-thinking work culture.</p><p><strong><em>But what makes the company culture at Xord so special?</em></strong></p><p>Let’s take a closer look at Life at Xord.</p><p>Xord is a rapidly growing Web3 technology company known for its unique and innovative approach to company culture. At Xord, our people are our greatest asset, and we strive to create a work environment that is both challenging and supportive.</p><h3>There isn’t a Traditional Company Culture at Xord</h3><p>Xord operates in a non-traditional manner, with policies and practices that are unique to the organization and its culture and are not based on standard industry practices. This is reflective of the company’s values and mission.</p><p>This is the reason we have O<strong><em>pen Leaves Policy</em></strong> and a <strong><em>Flexible Vacation Policy</em></strong> at Xord. We believe in working from anywhere that does not conform to traditional schedules or office environments.</p><p>It allows for greater flexibility and adaptability as Xordian can work in ways that suit them best. It can also foster innovation and creativity as there isn’t a rigid set of rules to adhere to.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n674LVsJ_-QpWrvPOtdhiA.jpeg" /><figcaption>Xord Quarterly Roundup</figcaption></figure><p><strong><em>Transparency</em></strong></p><p>Another example of this is our emphasis on transparency. We believe in a culture that is transparent to all. To make sure of this, our CEO conducts AMA every quarter and answers every question people have.</p><h3>Working at Xord is Fun</h3><p>Working at Xord is a truly enjoyable experience. The company culture is built on a foundation of collaboration, innovation, and fun. The team is made up of talented and passionate individuals who are always eager to lend a helping hand or share their expertise. The work environment is dynamic and fast-paced, which keeps things exciting and challenging.</p><p>In addition to the great work culture, Xord also recognizes the importance of work-life balance and strives to create a comfortable and enjoyable environment for its team members. We have different activities from gaming rooms, foosball tables, and table tennis sets to other games for Xordians to unwind. Our company trips and gaming competitions throughout the year create a strong sense of camaraderie among the Xordians.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mEYY6vLzBtmcs0YFvHbmkg.jpeg" /><figcaption>Trips and Gaming Competitions</figcaption></figure><p>Xord hosted an event <a href="https://www.linkedin.com/company/web3disruptio/">Web3 Disrupt</a> which was centred on bringing the Web3 ecosystem to Pakistan in hopes of spreading awareness and indulging more people in the new era of the web and aims to bridge the gap between Web3 enthusiasts of Pakistan and the industry experts working in Web3.</p><p>Making events like <a href="https://www.linkedin.com/company/web3disruptio/">Web3 Disrupt</a> a huge success are examples of collaboration and teamwork among Xordians.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0Di34BRTqpin-JAIdIVdlA.jpeg" /><figcaption>Glimpse from Web3 Disrupt</figcaption></figure><p>All in all, working at Xord is a fulfilling and rewarding experience that is both fun and fulfilling.</p><h3>Creativity and Innovation</h3><p>At Xord, creativity and innovation are the driving forces behind success in today’s fast-paced world. We recognise that entrepreneurial spirit is a valuable asset to any organization and that’s why we encourage and support our people in pursuing their startup ideas. Through mentorship, access to funding, and networking opportunities, we provide our Xordians with the resources they need to turn their startup ideas into successful businesses. Example of this is <a href="https://www.linkedin.com/company/expeditedesign/">Expedite Design</a>, <a href="https://www.linkedin.com/company/unipilotio/">Unipilot</a> and <a href="https://www.linkedin.com/company/blockapex/">BlockApex</a> achieving the milestone.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*om7UOyA19JtjB9KdTGk68g.jpeg" /></figure><h3>We Believe in Freedom with Responsibility</h3><p>Freedom with responsibility serves as a core value for Xord. Our core values are the principles to guide decisions and inspire people throughout the organization over a long period of time.</p><p>At Xord, the company culture is built on the principle of freedom with responsibility. The company trusts its people and gives them the autonomy to work in their style and pace. There are no strict rules or micromanagement, which allows the Xordians to be more creative and productive in their work. Xord believes that when people are given the freedom to work in a way that suits them best, they are more likely to produce high-quality work and feel more satisfied in their roles.</p><p>However, with this freedom, Xord also expects its people to take responsibility for their work and actions. The company values accountability, and team members are expected to take ownership of their roles. This creates a culture of mutual trust and respect, where Xordians feel empowered to take charge of their work and deliver results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DgZQf8Sf0-gHhCyDDyoOaA.jpeg" /></figure><p>As a longtime Xordian, I can attest to the fact that this company truly cares about its people. From the flexible work arrangements to the emphasis on personal growth, Xord has always supported us in both our professional and personal lives.</p><p>Overall, life at Xord is fast-paced, challenging, and rewarding. From innovative projects to a supportive culture, there are many reasons why Xord is one of a kind!</p><p>As we say <strong>“<em>For, in the end, it is impossible to have a great life unless it is a meaningful life. And it is very difficult to have a meaningful life without meaningful work”.</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9613999cdc4f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/an-organization-is-only-as-good-as-the-individuals-running-it-9613999cdc4f">An Organization is only as good as the Individuals Running it</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[2D Reed Solomon Encoded Merkle Tree Construction]]></title>
            <link>https://medium.com/xord/2d-reed-solomon-encoded-merkle-tree-construction-dea349aea555?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/dea349aea555</guid>
            <category><![CDATA[celestia]]></category>
            <category><![CDATA[bloackchain]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Maham Imtiaz]]></dc:creator>
            <pubDate>Tue, 29 Nov 2022 08:17:38 GMT</pubDate>
            <atom:updated>2022-11-29T08:17:38.086Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3ujkLYAEAjdCuqxRiaWVLQ.png" /></figure><h3>Introduction:</h3><p>In our previous article Merkle Tree construction we had briefly discussed the formation of the Merkle Tree using the <em>Reed Solomon Code</em>. In this article we will look into the depth of how a 2k by 2k matrix is constructed in light clients.</p><h3>Reed Solomon Erasure Coding:</h3><p>In order to form a merkle tree using the reed solomon coding we first decide the size of our Galois Field that is 16 bit. The size plays an important role in coding it helps us to form the generator function which then results in the parity added data. For a detailed description about Reed Solomon code you can read our article <a href="https://xord.com/research/reed-solomon-codes-a-classical-explanation/">here</a>.</p><h3>2D Reed Solomon Encoded Merkle Tree:</h3><p>The roots of Namespace Merkle Tree is divided in the four quadrant where Q0 has the original data Q1 has parity data of rows of Q0 and Q2 has the parity data for column of Q0 so the question that arises in our mind is how are we forming it in 2k by 2k dimension there is no explanation for it yet. So the answer is a simple trick of maths. Let’s discuss it below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rFQDoeBAmLGeEiHJdhhyig.png" /></figure><p>In the Q0 quadrant we have our data divided into shares that are associated with namespace ID, whose data will be erasure-coded and committed to NameSpace Merkel Tree. A shares raw data is interpreted in different ways depending upon your namespace ID which has the following raw data.</p><ul><li>The first part of the share is the namespace ID</li><li>Next we have a share reserved byte that is represented as * which represents the canonically serialised first request that starts in the share or 0 if there is none as the 1 byte big endian unsigned integer.</li><li>Remaining we have the requested data in which we have done some zero padding i.e adding zero at the end of the data to achieve the desired length of the byte to complete the size of 256 byte which can be shown below.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*3Lel-GfGc3qehXBq" /></figure><h3>Erasure Coding of Original data:</h3><p>First of all, the data in Q0 is carefully divided in the equal shares and is made sure that all shares lie in the set of 16 bit Galois fields (which is the length of field we decide to perform Reed Solomon coding) which gives us the matrix as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*J_XbLxrvryFmAOJN" /></figure><p>Where txs are the transaction data and msg1 and msg2 stands for the messages which is the interaction between the block producer and transaction sender which is signed by the transaction sender. And then broken into the parts so that it can be laid out in the matrix</p><p>For the above matrix we decide on a generator polynomial that has alpha as the primitive roots and can also be written in the form of a matrix. The generator matrix helps us to add parity to the original data and also it helps to recover the loss from the parity. Generator matrix looks like below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*IOP_jhKfELoQle9s" /></figure><p>Which is obtained by obtaining a primitive polynomial. Now let us suppose that we have our following matrix as the original data in the GF(2⁸) modulo 0x11D</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*WpcB2ZRvSg39gxqi" /></figure><p>Now we create a matrix that can encode any matrix of size 4xn here we have n = 8 therefore we create a matrix of size 8x4 which can form polynomial of size n and has n-1 roots hence our parity encoded matrix is as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*847r3w1lFz37bxGU" /></figure><p>Since we now know that Vandermonde matrix is an alternative approach to lagrange interpolation method it can interpolate the polynomials by expressing them in matrix form.</p><p>Also we know that polynomials are unique and therefore it is easy to generate polynomials using the determinant of the matrix or second approach is to form a generator matrix by taking the upper four rows since we have four rows in original data therefore we are considering only four rows. Which helps us yield the following matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*_hZAwV-iMfrUrQK3" /></figure><p>Since we have obtained our extended matrix we will now multiply our original data and we will have the following result</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*IUk6ibfZzDgtiYov" /></figure><h3>Recovering the lost data:</h3><p>Now let us assume that we have lost our data, let say row 0 and 4 from the extended matrix. Hence our encoding matrix and original matrix becomes as follows</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*SAXEmo9IVEHESOYF" /><figcaption>Encoded Matrix</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*lJ7glklw1FmBoA7b" /><figcaption>Original matrix</figcaption></figure><p>Since we know that A*(A)^(-1) = I. Therefore we invert the encoded submatrix and multiply the inverse with encoded matrix to check that our answer is correct so we get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*KOmVQwBCtFUk9uIh" /></figure><p>As we have obtained an identity matrix therefore we are safe to say that we have a correct inverse matrix. Now in order to obtain our lost data we will multiply our inverse matrix with the extended data which will result in the restoration of the original matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*oRzM2RY3YM-vq_UD" /></figure><p>In actual process what we do is that we only multiply the extended data with the sub inverse row of the generator matrix as shown below</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*yU-q3rB36ffJPURZ" /></figure><p>Once we have constructed the data matrix row we will also generate parity in the same way</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*S7xIDXcRbzjvdAhc" /></figure><p>Now it comes in mind that how are we extending our data horizontally so it’s not that of moon maths it’s basically we take another vandermonde matrix and apply the transpose of the matrix this how we get our generator function. Once we have our generator matrix we then continue to the same work that is explained above.</p><p>The advantage of Reed Solomon code is that the probability of an error remaining in the decoded data is much lower than the probability of an error if Reed Solomon is not used. But the approach of encoding a data in matrix form is not efficient since the Vandermonde matrix fails on the data of large size therefore in order to have a data more secure I believe lagrange interpolation would be a better approach to the problem</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dea349aea555" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/2d-reed-solomon-encoded-merkle-tree-construction-dea349aea555">2D Reed Solomon Encoded Merkle Tree Construction</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reed Solomon Codes: A Classical Explanation]]></title>
            <link>https://medium.com/xord/reed-solomon-codes-a-classical-explanation-fb6f195b52e0?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/fb6f195b52e0</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[erasure-code]]></category>
            <category><![CDATA[reed-solomon]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Rabia Fatima]]></dc:creator>
            <pubDate>Tue, 29 Nov 2022 08:17:17 GMT</pubDate>
            <atom:updated>2022-11-29T08:17:17.863Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Kxz5KdmKgkAS1c9zzxxYOQ.png" /></figure><p>Ever wondered how satellite communication works when there is so much noise in the environment? Or how can we still play our games on a CD which might have lost some data by little scratches over them? It’s all possible because of the efforts of two scientists Irving S. Reed and Gustave Solomon. In 1960, they introduced the world with an algebraic concept of erasure codes most commonly known as “Reed-Solomon codes”.</p><p>Reed- Solomon code is the subclass of <a href="https://ieeexplore.ieee.org/document/1054109/">Non-Binary BCH codes.</a> The non-binary BCH codes are different from the binary codes in a way that they can operate on multiple bits error rather than individual bits. These codes are based on Galois fields, where arithmetic operations on field elements have a result within the field. These arithmetic operations are handled by an encoder and decoder, which require special purpose hardware or software. These codes help us to recover the corrupted messages over a noisy network. There are two main components of the Reed-Solomon codes and they are:</p><ol><li>Encoding</li><li>Decoding</li></ol><p>The encoder receives the data and before transferring it to the network it adds some parity in the original data(How to add parity we will see that later). On the other hand the decoder detects the corrupted message and recovers the original data.</p><p>This concept of recovering data is very important in the blockchain world. Want to know why?</p><h3>Why is Data Recovery Important in Blockchain?</h3><p>When you heard about Layer-2 solutions, the most essential part of these solutions are data. The base layer is compelled to provide the guarantee for data availability. We have two possible solutions available to ensure that data is indeed available.</p><ol><li>Nodes on L1 download the whole data → This solution comes with a cost of high bandwidth and large hardware requirements. We don’t want to burdanise the nodes for downloading unnecessary data.</li><li>The other solution is Data Availability Sampling where the sequencer samples the data into chunks and each node at L1 can download the samples and verify that indeed the data is available.</li></ol><p>With the later approach of Data Availability Sampling the main problem arises is how can we make sure that not even a 1% of data is withheld by the sequencer? Because if that is the case then we can’t fully reconstruct the data to validate the state. So here comes the Reed-Solomon in the picture.</p><p>The Reed-Solomon allows us to recover our data by using the parity. How do they work? To begin with, let’s first get to know the construction and some basic facts about Reed solomon codes.</p><h3>Reed Solomon Codes</h3><p>Reed Solomon codes also refer to error-correcting code that acts on a block of <em>k</em> bits of input data to produce <em>n</em> bits of output data (n,k). RS codes are a family of block codes used for error detection and correction. So in simple words when a sequencer transmits a large data using RS codes, he first extends the data by using some parity and then break the data into some fixed size pieces. Each such piece is called a message and the procedure given by the Reed solomon algorithm encodes each message individually into a codeword.</p><p>We have different encoding procedures available for Reed Solomon codes, but we particularly here will be focusing on the BCH view of Reed Solomon Codes.</p><h3>RSCodes Parameters</h3><p>Error codes is an <a href="https://en.wikipedia.org/wiki/Injective_function">injective</a> mapping of:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/83/0*9J13ZFjKgX2C7CnH.png" /></figure><p>What’s the meaning of these parameters involved in this equation?</p><h3>1- Σ -The Alphabet</h3><p>The data needs to be encoded is modeled as a string over Alphabet <strong>Σ</strong> The size of this alphabet is denoted as <em>“q”</em>. If this size value is 2 then the codes are binary codes. Otherwise they are non-binary. In many applications it is useful to consider <em>q</em> to be a prime power, and to identify <strong>Σ</strong> as a finite field.</p><h3>Galois Finite Field Arithmetic</h3><p>A <a href="https://en.wikipedia.org/wiki/Finite_field">finite field</a> performs arithmetic operations such as (+, -, / , *) on field elements in a way that the result always lies in the field. That is the reason we need a special purpose hardware or software encoder and decoder which helps to carry out these operations.</p><h3>2- The Message Length k</h3><p>Messages are elements “<em>m</em>” of data stream</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/20/0*EJZWCPtszsbaxYPs.png" /></figure><p>which have a string length <em>k </em>is called message length or dimension of block.</p><h3>3- The Block Length n</h3><p>The coded message elements “c” of</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/19/0*KpSAsgadjPIF7Wen.png" /></figure><p>are of length n which will be received by the receiver. Hence they are also called received words. If <em>c=C(m) </em>for some message <em>m</em>, then <em>c</em> is called the codeword of <em>m</em>.</p><h3>BCH view of Reed Solomon Codes</h3><p>Every codeword of the Reed–Solomon code is a sequence of function values of a polynomial of degree less than k. In order to obtain a codeword of the Reed–Solomon code the message symbols (each within the q-sized alphabet) are treated as the coefficients of a polynomial <strong><em>p</em></strong> of degree less than <strong><em>k</em></strong>, over the finite field <strong><em>F</em></strong> with <strong><em>q</em></strong> elements. Formally, the set of codewords <strong><em>C</em></strong> of the Reed–Solomon code is defined as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/763/0*bINJLr_4sHfARUvV" /></figure><h3>Encoding Procedure using systematic way</h3><p>There are multiple methods to encode the message using Reed solomon such as Discrete Fourier transform, data mapping to polynomial but we here for the sake of data availability problem are considering <a href="https://en.wikipedia.org/wiki/Systematic_code">systematic encoding</a> as the best approach due to the below reason.</p><p><em>Systematic encoding can simply append parity to the source block and receivers do not need to recover the original source message if received correctly. This is useful for example if error-correction coding is combined with a hash function for quickly determining the correctness of the received source code.</em></p><p>We perform mapping of messages x to a polynomial p(x) of degree less than <em>k</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/304/0*KiWS7IrR5mnSMyHr" /></figure><p>To compute the polynomial p(x) from x, we use <a href="https://en.wikipedia.org/wiki/Lagrange_polynomial">lagrange interpolation</a>. Once it has found, this polynomial will be evaluated at positions a1, a2, . . . an of the field. The <strong><em>a</em></strong> is called the <a href="https://en.wikipedia.org/wiki/Primitive_element_(finite_field)">Primitive element </a>of field F. These points are generated by a generator polynomial.</p><h3>Generator Polynomial</h3><p>The generator polynomial G(x) is defined as the polynomial whose roots are sequential powers of the Galois field primitive .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/675/0*r6iLQgtq5ufm8Ckr" /></figure><p>The generator function is generated using a special polynomial. In these codes all the valid codewords are exactly divisible by this <a href="https://en.wikipedia.org/wiki/Polynomial_code">generator polynomial</a>.</p><p>To learn the generation process of g(x), you may refer to this <a href="https://www.sciencedirect.com/topics/computer-science/generator-polynomial">link</a>.</p><p>The generator matrix G, can always be written as G=[Ix][P], where Ix is the identity matrix of size k.</p><p>Now remember our G matrix is equal to the identity matrix multiplied by a polynomial matrix.</p><p>G=[Ix][P]</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/715/0*BwXc-Kw3AxrphDOq" /></figure><p>Now the codeword C contains the message m as a prefix, and simply appends error correcting symbols as suffixes. Here instead of sending s(x)=p(x)g(x) , the encoder constructs the transmitting polynomial s(x) such that;</p><p>1- The coefficients of <strong><em>k</em></strong> largest monomials<em>(e.g 1,2, . . . k) </em>are equal to the corresponding coefficients of p(x).</p><p>2- The lower order coefficients(<em>e.g k, k+1, . . . n)</em> of s(x) are chosen in a way that the polynomial s(x) is completely divisible by generator polynomial g(x).</p><p>We construct a message polynomial p(x) by interpreting the message as the coefficients of a polynomial. Next we multiply the message polynomial p(x) by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/27/0*DeI20jBmpR7mWee2.png" /></figure><p>to perform check of t=n-k. Now divide this product with g(x) to find the remainder.</p><p>For example I have a message polynomial of degree 3,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/0*RZKL8iWL_xJN7H0Y.png" /></figure><p>Now I want to extend it with some parity and make an encoding polynomial s(x) of degree 6. For this i must generate a generator polynomial g(x) of degree 6 which might be</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/383/0*5pqa0h3uTxd-ioq_.png" /></figure><p>Now the largest monomials of the polynomial s(x) such as x6, x5, x4 will have the same coefficients as p(x). On the other hand the lower order must have the coefficients in a way that the whole s(x) can be divisible by g(x).</p><p>In this case the s(x) must be equal to</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/383/0*OyMGnHv8MMzZkDZ0.png" /></figure><p>Now there might be a case that we don’t get the exact 0 remainder. Hence for that After finding the remainder polynomial S_r(x) we can subtract it to itself till we get the 0 remainder.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/471/0*VIcE0PpKZT5OTgk2" /></figure><h3>BCH View Decoding</h3><p>The decoder views the codeword as a sequence of coefficients. They use a fixed generator polynomial which is known to both sender and receiver.</p><h3>Formulation For Decoding</h3><p>The transmitted message (c0, c1, , , ,cn) is viewed as the coefficients of a polynomial s(x).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/186/0*22u-czeQRKXuWWas" /></figure><p>As a result of the Reed-Solomon encoding procedure, s(x) is divisible by the generator polynomial g(x):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/186/0*OMlpNyV0rz0AY-UL" /></figure><p>Since s(x) is a multiple of generator polynomial and inherits all of its roots then we could say:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/186/0*-3PHa-kvC5UisRK5" /></figure><p>Since s(x) is a multiple of generator polynomial and inherits all of its roots then we could say:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/350/0*XHP_m6XwOEctPUo5" /></figure><p>Therefore;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/383/0*dRIGP4U8-Fm_CphG.png" /></figure><p>The transmitted polynomial that has been received by the receiver has error in it which could be defined as:</p><p>r(x)=s(x)+e(x) where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/163/0*Jc88c99W221KI_rV" /></figure><p>The coefficients of the ei will be zero if the received polynomial does not contain any error at the corresponding power of x, otherwise the value will be non-zero.</p><p>Potentially there could be v error at the ik distinct positions of x, which could be mathematically define as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/163/0*kE2h7jpHvWQEb_iG" /></figure><p>Now we want to design a decoder which could find the number of error v, the positions of error ik and the error values at those positions eik so we can get the original message s(x) by subtracting the error from the received polynomial.</p><p>r(x)-e(x)=s(x)</p><h3>Syndrome Decoding</h3><p>The decoder starts by evaluating the polynomial as received at points <strong>α</strong>1, . . <strong>α</strong>k . The evaluations at these primitive points are called “ syndrome” (Sj).</p><p>Syndromes can be defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/0*ACzTNZPe5WdDmN5_.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/163/0*HxQJpjND8_9qPIbm" /></figure><p>The Sj is 0 because s(x) has roots at <strong>α</strong>j as we have discussed above.</p><p><em>“The advantage of looking at the syndromes is that the message polynomial drops out. In other words, the syndromes only relate to the error, and are unaffected by the actual contents of the message being transmitted. If the syndromes are all zero, the algorithm stops here and reports that the message was not corrupted in transit.”</em></p><h3>Error Locators and Error Values</h3><p>We define locators as X_k and values as Y_k.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/159/0*_H3R_RdvbDSxJKkk" /></figure><p>Hence we can write the syndromes as;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/159/0*HfDG4VLV5EBz67tm" /></figure><p>I can map my above equation into a matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/363/0*FmJw47tUe4YeC8yi.png" /></figure><p>Let’s solve the leftmost side of the matrix first. In matrix form we can easily solve this equation. As the main problem is finding X_k because then we have the leftmost matrix and we can simply multiply both sides of the equation by its inverse yielding Y_k. The k values are column numbers while the j values are rows.</p><p>So let head to our journey of finding error locator X_k using a linear system of equations.We define our Error locator polynomial as A(x).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/441/0*lEmOnD7pAXXmDplW" /></figure><p>The zero’s of A(x) are the reciprocal of</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/40/0*PNZy6NhnEdHtjEQC.png" /></figure><p>since x=</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/40/0*3PKajE7FEoU5ThuW.png" /></figure><p>then the overall equation will become</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/201/1*NhwGbw5aFnHXNzbj6DRgRw.png" /></figure><p>So we could say that by evaluation A(x) at</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/40/0*wkwLT-mqzLtxIO_i.png" /></figure><p>we are making the whole polynomial 0.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/110/0*cgj1rnRFPpRhRyVe" /></figure><p>Now even if we multiply both sides of the equation with Y_k*X_j+v where j is an integer 1&lt;j&lt;v . After multiplication the equation will still remain at 0.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/566/0*XzrW3k13RMT6BdU0" /></figure><p>Now for sum k=1 to v and it will still be zero.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/518/0*Y0aHvx6-_mxza92S" /></figure><p>Separate each term to its own sum.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/685/0*6tE3kDaIblZ4SaoP" /></figure><p>We here can separate the unaffected values of A.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/685/0*5yWhllNfZad3wioN" /></figure><p>These summations are now equivalent to syndromes values, which are already known. Hence we can substitute in the syndrome values.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/0*z7Rb3yx-nFlHMCGZ" /></figure><p>Subtracting sj+v from both sides yields.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/0*VOLsBA4PkXhaQAh3" /></figure><p>Recall that j was chosen to be any integer between 1 and v inclusive, and this equivalence is true for any and all such values. Therefore, we have v linear equations, not just one. This system of linear equations can therefore be solved for the coefficients Λ_i of the error location polynomial:</p><p>Now we have our knowns at both sides of the equation so we can easily find the values of A_i. For an example reference of how this is working practically you may see this <a href="https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#:~:text=with%20errors%20corrected.-,example">link</a>.</p><p>After solving for Ai(error locators) , I can simply put the values of A_i matrix to the equation where with using syndrome values i can get the error values Y_i.</p><p>This is how you can understand the general mathematical overview of Reed-Solomon erasure codes.</p><p>To read on <a href="https://xord.com/research/fraud-proofs-for-data-availability/">Data Sampling and Fraud Proofs</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fb6f195b52e0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/reed-solomon-codes-a-classical-explanation-fb6f195b52e0">Reed Solomon Codes: A Classical Explanation</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Fraud and Data Availability Proofs]]></title>
            <link>https://medium.com/xord/fraud-and-data-availability-proofs-901f2afee3af?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/901f2afee3af</guid>
            <category><![CDATA[rollup]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[l2]]></category>
            <dc:creator><![CDATA[Rabia Fatima]]></dc:creator>
            <pubDate>Mon, 14 Nov 2022 12:45:00 GMT</pubDate>
            <atom:updated>2022-11-14T12:45:00.578Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FD7_J3T7nsHHmllgZfVE-A.jpeg" /></figure><p>In recent times, we on twitter are witnessing a frequent discussion about the Data Availability Problem and its importance. There is no doubt in how L2 solutions are empowering ethereum’s vision to be a global super computer. However, we can’t deny the fact that even with L2s we can’t achieve what we have envisioned due to number of limitations. Out of them the first and the most important one is “The Data Availability Problem(DA)”. So in this series we are going to take a deeper look in what DA is and how can we solve its challenges with Data sampling and Fraud proofs.</p><p>Let’s briefly discuss what this series is about? And what are the topics that we are gonna cover to fully understand the concept of DA Proofs.</p><ul><li>Fraud and Data Availability proofs</li><li>Reed Solomon codes in the context of DA</li><li>2D Reed Solomon codes for Merkle Tree Construction</li><li>Fraud Proofs for incorrectly generated extended data</li></ul><p><strong><em>In this particular post we are gonna talk about what is Data Availability, why it matters to us and what are the potential schemes to solve this problem. We will also discuss how a node can submit a fraud proof in case of detecting a malicious transaction at L2.</em></strong></p><p>We already know that the cryptocurrency platforms are gaining traction on daily bases. This massive adoption comes with the scalability limitations for existing blockchains. One possible solution for this problem is to simply increase the on-chain throughput by improving the hardware specifications. However, if we tend to do this, this would hurt the decentralization as very few nodes will be able to participate due to large hardware requirements. As a result most of the nodes will run the light clients and rely on the full nodes to verify the blockchain state. This reliance guarantees weak assurance in a case where the majority of nodes are dishonest. This is the main reason why L1s are considering off-chain solutions as the best alternative to achieve scalability.</p><blockquote><em>When we talk about off-chain solutions such as Rollups, we often tend to ignore the fact that even with rollups we can’t achieve unlimited throughput. Ever wondered Why?</em></blockquote><p>This is because the rollups are an off-chain computing solution which performs the state calculation off-chain. However, in order to finalize the block they do need to publish the state and callData to the base layer such as Ethereum. So even if we make the sequencer, a supercomputer to produce infinite blocks we can’t finalize them because of the network and storage limitations at the base layer.</p><p>So now when we have acknowledged that rollup itself can not achieve an unlimited throughput, we have another problem which is what if the centralized sequencer itself is dishonest? And he has computed a false state? How can L1 reject those transactions? Well in that case we have full nodes on the base layer. These nodes are watching the state and on detecting a faulty transaction they can submit the fraud proof to mark the block invalid.</p><p>Does that mean all the L1 nodes responsible for watching the rollup activity, need to download the whole sequencer data?? Well, yes that is exactly the case. This implies that even by proposing off-chain solutions we are still demanding full nodes to increase their hardware requirements. That’s bizarre right?</p><p>On top of this, if somehow you manage to run a powerful node to watch over the transactions, this still doesn’t guarantee that the sequencer is not trying to cheat by withholding the data. Because even if 1% of data is unavailable then no node can reconstruct the state and hence nobody can submit the fraud proofs within the defined time making the block valid. This is what we define as the “<strong><em>Data Availability Problem</em></strong>”.</p><p>Heww!!! That’s a lot to grasp right?But bear with me. We have some very fun things to discover. And to be honest there is no need to panic as Ethereum has proposed another smart solution to tackle this problem which is “Data Availability Sampling”. So what is Data Availability Sampling? well it allows us to ensure data availability without requiring nodes to download the entire data. This is a massive breakthrough to achieve scalability.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/0*PxJg1L4OSM3qLnJ5" /></figure><p>So we have two notions:</p><p>1- The sequencer is trying to cheat with a faulty transaction but does not hold any data.</p><p>2- The sequencer is trying to cheat with faulty transaction and has also withhold some percentage of data so that nodes may not able to reconstruct the block for providing fraud proofs.</p><p>To explain our purpose of writing we want to prove that the light nodes will not accept blocks with invalid transactions under the influence of dishonest majority in consensus nodes.</p><p>As an example for the first notion, we are assuming a scenario where a malicious sequencer is trying to cheat by including a faulty transaction in a block but without holding any data.</p><p>In case of optimistic rollups, to prove that some block is invalid the nodes need to reconstruct a block and submit a fraud proof for it. Now lets discuss a few things which are must for a sequencer to publish on L1 in order to verify l2 state.</p><h3>The Rollup Block Structure</h3><p>The block structure is very important when it comes to support the generation and validity of fraud proofs. To describe this we have a block header h_i at height<em> i contains</em> the following information.</p><ol><li>Previous Blockhash hash(prevHash_i)</li><li>Merkle Root of the data involved the block transactions(dataRoot_i)</li><li>The number of leaves represented in a merkle tree(dataLength_i)</li><li>The merkle tree of the state of rollup(stateRoot_i)</li><li>Additional arbitrary data that may be required by the network(additionalData_i)</li></ol><p>In an account based model such as Ethereum the key value pair are account address and balance. The state needs to keep track of all the data, for example the total fees paid to the block producer.</p><p>Now to begin with, we define a transition function which performs transition without requiring the whole state tree, but only with state root and Merkle proofs of parts of the state tree that the transaction reads or writes, which is most commonly called “<strong><em>State Witness</em></strong>”. These merkle proofs are effectively expressed as a subtree of the same state tree with a common root. The function could be defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/390/0*0v0goZJRZckPvBIw.png" /></figure><p>t→ Rollup Transactions</p><p>w→ Merkle proof of transaction tree</p><p>The witness <em>w </em>consists of a set of value — pairs and their associated Merkle proofs in the state tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/718/0*apLqsGDiCxb0_sli.png" /></figure><p>After executing all the transactions<em> t </em>on parts of the state given by <em>w </em>if the transactions modifies any state then, the new resulting NewstateRoot can be generated by computing the new root of the new sub-tree with the modified leafs.</p><p><em>If </em><strong><em>w</em></strong><em> is not the correct witness and does not contain all the part of the leaves required by the transactions during the execution then it will throw an exception error </em><strong><em>err</em></strong><em>.</em></p><p>For the rest of this series we will have a few notations which i am concluding here:</p><h3>Notations:</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/711/0*Sik19SCcfQ0Fc4b9.png" /></figure><h3>What is the innerRoot?</h3><p>The innerRoot is the representation of intermediate roots within a block after applying a certain number of transactions.</p><p>When we talk about rollup state validation, data is the most important thing. Data helps us to reconstruct the state and verify either the state published by the rollup is valid or not. That’s why its very important to communicate the DataRoot to the light clients. So lets first understand why and how we can construct the DataRoot.</p><h3>What is DataRoot?</h3><p><strong><em>dataRoot_i</em></strong> is a fixed size of transaction data chunk in bytes known as<strong><em> “shares”.</em></strong> The share will not contain all the transactions rather a fixed part of transactions. We reserve the first byte in each share to be the starting position of the first transaction. This allows the protocol message parser to establish the message boundaries without requiring every transaction in the block.</p><p>Given a list of shares (sh0, sh1, . . . shn) we define a function parseShares which parses these shares and output a list of messages (m0, m1, . . .mt) which are either transactions or intermediate state roots. For example, parseShares on some shares in the middle of some block <em>i </em>may return (trace1i, t4i , t5i , t6i ,trace2i).</p><p>We can not include state roots after every transaction so we can define a period, for example after<em> p</em> transactions of <em>g</em> gas we can include an intermediate state root within a block.Thus we have a function parsePeriod which parses a list of messages and returns a pre-state intermediate roots tracexi and post-state intermediate root tracex+1i and a list of transaction (tig, tig+1, . . .tig+h) such that when we apply these transactions on tracexi , it must give us tracex+1i . If the transactions do not follow the condition then the function must return an err.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/587/0*LTVGXYA8-NaPhdjL.png" /></figure><h3>How to Verify the Invalid State Transition?</h3><p>What if a malicious sequencer has provided us with an incorrect stateRoot? We can check the invalidity of the stateRoot by a function “<strong><em>VerifyTransitionFraudProof</em></strong>”. This function takes the fraud proof submitted by full nodes and verifies it.</p><h3>What is a Fraud Proof?</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*slFuSLXXWHO4c5M-.jpg" /></figure><p>A fraud proof consists of the following things:</p><ol><li>Relevant shares in the block that contain a bad state transition.</li><li>Merkle Proofs for those shares.</li><li>State witness for the transactions in the shares.</li></ol><p>The VerifyTransitionFraudProof function applies the transactions of a particular challenged period to the pre-state intermediate which must result in intermediate post-state root.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/574/0*Z1uFNLt67VK2w4Rj.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/694/0*0NeNBVWjTXSeEupd" /></figure><p>The function VerifyTransitionFraudProof returns true if all the given conditions are true otherwise, false will be returned.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/663/0*ctFtfoRi40VPjOsH" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/668/0*tkuYjoThJHX8Ak_6.png" /></figure><p>Now that we are aware of both DA and fraud Proofs we are now moving with a second notion as we have discussed which is what if the sequencer has computed an invalid transaction and I as a light client detects it. Now I need to compute a fraud proof for it. However, the sequencer has not published the entire data through which I can reconstruct the state to verify. For this problem Rollups like Optimism has proposed a solution which is to enforce the sequencer to publish the data. But how exactly? I am leaving this for another post. Till then <strong><em>adiós</em></strong>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=901f2afee3af" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/fraud-and-data-availability-proofs-901f2afee3af">Fraud and Data Availability Proofs</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Why is Resource Pricing a Big Deal in Blockchain?]]></title>
            <link>https://medium.com/xord/why-is-resource-pricing-a-big-deal-in-blockchain-f9ad2916769f?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/f9ad2916769f</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[bitcoin]]></category>
            <dc:creator><![CDATA[Rabia Fatima]]></dc:creator>
            <pubDate>Sat, 10 Sep 2022 11:11:40 GMT</pubDate>
            <atom:updated>2022-09-10T11:11:40.410Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RtgPxAa-NVQmGxDfFlBlqg.jpeg" /></figure><p>TLDR; <em>In this article, we are gonna discuss what resource pricing is and how we can limit and price the submission of transactions that get included in the chain. We will also discuss the trade-offs between different approaches that can help us to understand and improve the status quo of resource pricing. Excited? Let’s quickly jump into this.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/278/0*a9LooImgXEp6LrLV" /></figure><p>In the blockchain ecosystem, scalability trilemma is one of the most talked about problems. However, when we folks talk about scalability, we tend to confuse it with the throughput of the blockchain. The common mis-conception is that the more the throughput, the more the scalable the blockchain is. But, that is not true, throughput is transactions per second, whereas, scalability is the transactions per second / cost to validate all transactions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/432/0*fOPYlFWuTASh9X70" /></figure><p>This introduces the resource factor in our scalability problem. Why should resources cost less? Because, If the validator machine is so costly that a normal person cannot set and run it, then the system is not scalable because not everyone can spin up a costly machine.</p><p>In blockchain we need to measure these resources in units or in any sort of weighing scheme. So if a block is taking a million years to validate because of slow resources you can’t abandon it. You have to limit your resources to prevent denial of service factors. Once we have metered these resources we have to put a bound on resource consumption for each block.</p><h3>Understanding Social Cost from First Principle Method</h3><h4>How do you define a blockchain from the first principle?</h4><p>Well, a blockchain is a replicated state machine where a bunch of nodes perform independent transaction execution to arrive at some state of a virtual machine. You can imagine the state machine as a mathematical abstraction used to reach a new state after a transitioning function. Now remember all these activities take resources.</p><p>We already know that every transaction confers some personal benefit to its sender, but transactions also induce social cost to the network as every node has to process it independently. This was the model presented by Satoshi. In such cases, the general economic theory dictates that the incentives of performing these state transition activities have to be more than the social cost that was consumed by each transaction in the network.</p><p>The social cost of running a state machine can be broken down into five fundamental types of resource expenditure.</p><ol><li><em>Network Bandwidth:</em> It is the cost of downloading the transactional data in order to reach a new state.</li><li><em>History Storage:</em> It refers to the cost of storing each transaction data.</li><li><em>Computation:</em> The cost of a node to verify a transaction.</li><li><em>Memory Bandwidth and Capacity:</em> Refers to the memory read and write functionality for data. Let’s understand this concept with the help of an example. Suppose you want to copy a few kilobytes of data from one location to another in a VM. You would definitely not do it for free as it takes some amount of memory to read and write. Since the memory has finite capacity and bandwidth hence we have a social cost associated with it.</li><li><em>Random-access Disk Bandwidth and Capacity:</em> This refers to storage read and write of data.We need to perform random access read and write into storage. This is different from history, where we just append the data.</li></ol><p>Before diving into these five fundamentals, here’s a subtle reminder; In the blockchain world, we have two transaction models, one is the UTXO model, used in bitcoin, and the other one is the account-based model, used in Ethereum.</p><p>In Bitcoin, the block has to download approximately 1–4 MB of data every 10 mins, while Ethereum has a less frequency of about 5–10KB of data which takes around 12–15sec.</p><h3>Resource Metering in Bitcoin:</h3><h3>Pre-SegWit</h3><p>Earlier before segWit, Bitcoin used ”vByte” as a measurement unit which is equal to 4 weight units.</p><p>1Gas = 1vByte = 4 Weight Units</p><p>Transactions prior to segWit are called Legacy transactions. The block was about 1Mb and 4million weight units. For more about segWit read <a href="https://www.investopedia.com/terms/s/segwit-segregated-witness.asp">this</a>.</p><h3>Post-SegWit</h3><p>The main purpose of SegWit is to improve transaction throughput on a blockchain network.</p><p>SegWit is basically a typical transaction that takes an UTXO ID and provides a witness that we authorize this UTXO with the account. Now with SegWit, this signature does not provide the effect of transactions such as whether the UTXO is created or burned? It simply authorizes the transaction. So SegWit removes this signature from the transaction tree but keeps it in the block.</p><p>With SegWit transactions are not smaller, they are exactly the same size as were before. WHY? Because SegWit hasn’t deleted the data, rather it has just moved it from one place to another.</p><p>4gas(weight units) per non-witness byte</p><p>1gas(weight units) per witness byte</p><p>So a block has a limit of 40 million weight units which means Either the block can be filled with 4MB of non-witness data or 1MB of witness data. Now there is a catch here.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/504/0*wThRu53T5sdP12BM" /></figure><p>With the increased block size we have quadrupled the network bandwidth and history storage for full nodes.</p><p><em>However, are we really getting a quadrupled throughput by this? Let’s figure it out.</em></p><p>Consider we have an equally distributed data of both witness and non-witness data type which is 2MB for both.</p><p>Now, Non-witness data = 2MB(data) * 4gas = 8MB gas*4 = 3,200,00 Weight units.</p><p>Witness data = 2MB*1 = 2MB gas = 800,00 Weight units.</p><p>With the above calculation, we can conclude that removing the witness data from the transaction storage tree has given us only a 25% increase in throughput. This means that the throughput was not the bottleneck for bitcoin.</p><p>“So what exactly led to SegWit?”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/498/0*ZlOsDthuqF4a3O6N" /></figure><p><em>Is it Network bandwidth?</em> No, as we are downloading more data i.e 4MB.</p><p><em>Is it Disk Capacity?</em> No, as the state is growing quadruple.</p><p><em>Is it computation?</em> No, as we have quadrupled the amount of signatures we can verify.</p><p><em>Then is it Memory bandwidth and capacity?</em><strong> </strong>As the size of blocks has increased the nodes fetching the data from memory has also increased. This means segWit did not provide any advantage for memory bandwidth.</p><p>This exact reason why bitcoin has opted for SegWit is <strong>Random access and disk capacity!</strong> SegWit helps to bound the rate at which state grows by removing witnessed data from the transaction tree.</p><p>This concludes that If we increase the load on bottlenecks then we are hurting decentralization and the cost of running a full node.</p><h3>Additional Cost</h3><p>Bitcoin uses a proof of work consensus mechanism, which inherently infers some uncertain electricity cost. Though this cost is not the subject of matter here, I would like to mention that there is a marginal cost associated with it, such as expensive ASICs or mining rigs that every miner must endure.</p><h3>Resource Metering in Ethereum:</h3><p><em>Now let’s discuss how Ethereum meters its resources.</em></p><p>Ethereum uses the accounts plus storage data model while for execution it uses a turing complete machine. Ethereum’s execution model is without predicates unlike bitcoin, however, it discards the infinite loops by limiting gas consumption.</p><p><strong>Ethereum Gas Cost Structure Before EIP-1559</strong></p><ol><li>Fixed Base cost</li><li>16 gas per byte for a data in transaction</li><li>Variable gas per opcode or instruction executed</li></ol><h3>Why Do We Need Base Cost?</h3><p>Ethereum has restricted its block size to be in the range of 0 to 30Mgas. So even if we remove our base cost you will still not be able to create an infinite-sized block with infinite transactions. You will still have a cap on block size limits in bytes. So why then is the base cost important? It helps at the mempool level to avoid the denial of service attack. Imagine an account is trying to send 0 Eth to some random address. This is a completely valid transaction. This means bots can flood the mempool with random transactions, creating overhead. So the base cost is essential for the validity of mempool. The base cost is adjusted based on the network activity after every new block.</p><p><strong>Again the same question arises. Why the 30M gas limit?</strong></p><p>There are two possible reasons that we have found for Ethereum to select 30M gas limit are:</p><ol><li><strong>Validation</strong> →Ethereum nodes can validate 50–100 Mega gas per second on a laptop. so when you do full sync you can catch into a reasonable time. However, if we increase the block limit or decrease the block time we will be hurting the validation rate, which means that the full sync will take longer and longer.</li><li><strong>State Growth</strong>→Ethereum gas is decent for metering operations except for state growth. Ethereum wants to bound the state growth rate which is 90G bytes at the time of writing. This means the larger the state the longer time will take to sync.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/273/0*UoDPmNNkJIDl5XFE" /></figure><p>The block size here has been increased by a factor of 2 approx. This means that the resources will also double. However, our main point of discussion was to reduce the resources and decrease the burden on validators.</p><p>So what are solutions that are brought up by the Ethereum community to tackle the resource pricing problem? There are plenty but let’s discuss some of them.<br><strong>State Expiry → </strong>The older history of Ethereum will be removed from the chain. If any smart contracts wants to re-execute the older transactions they can query it from protocols like <a href="https://thegraph.com/en/">The Graph</a> and The Protocol Network.</p><p><strong>Statelessness → </strong>By using Verkle trees and Kate commitments technology, nodes can be able to validate the block without syncing to the full blockchain data.</p><p><strong>Make Storage Operations More Expensive → </strong>Ethereum could simply increase the gas cost for storage Opcodes.</p><p><strong>Make data more cheap→ </strong>Some technology or alternate solution such as Data Availability which can replace the requirement of data dumping from Ethereum to some other chain such as Celestia.</p><p>In the end, I would like to present my opinion about why I feel that DA layers are the better choice for Ethereum regardless of all the others. The DA layers will not only help the monolithic blockchains such as Ethereum to lower the price of their storage but also they will help in the sustainability of Rollups too. We know that in rollups we have a supernode which can process infinite transactions; however, even that supernode is restricted to limit the transactions inside a block. This is because Go-ethereum hasn’t changed so it will still validate 50–100M gas/sec on the laptop. In DA layers we don’t have to download each byte to validate a transaction. We can simply perform data availability sampling which has a subliner cost.You might argue that, we can achieve the same with Ethereum’s data shards too. Maybe, but in my opinion running a validator node in data shards is not equal to a DA layer node as you have to run a heavy EVM too which has some hefty changes in gas costs.</p><p>Yeah, so this is it for now but, in the next post we will definitely discuss how these resources can be capped efficiently. Till then, au revoir!!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f9ad2916769f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/why-is-resource-pricing-a-big-deal-in-blockchain-f9ad2916769f">Why is Resource Pricing a Big Deal in Blockchain?</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Xord From First Principles; Make Web3 Usable for 1 Billion People]]></title>
            <link>https://medium.com/xord/xord-from-first-principles-make-web3-usable-for-1-billion-people-781fedb9ef0?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/781fedb9ef0</guid>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[about-xord]]></category>
            <category><![CDATA[vision]]></category>
            <category><![CDATA[xord]]></category>
            <dc:creator><![CDATA[Abdul Sami Khawaja]]></dc:creator>
            <pubDate>Thu, 02 Jun 2022 10:12:59 GMT</pubDate>
            <atom:updated>2022-06-02T10:12:58.414Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/0*o4m9uJPoxWLa_SEf.png" /></figure><h3>Background</h3><p><a href="https://xord.com/">Xord</a> is a Web3 R&amp;D and Investment Company helping to contribute to the development of technology and funding new ventures. We are a mission-driven company, and being mission-driven means existing for a purpose.</p><p>In just over three years that we have existed, we have reinvented ourselves many times. We have tried many new things and seen failures, but we have kept going. At the start of this year, we started asking ourselves again the reason for the existence of Xord.</p><p>We sat down and tried to imagine the world from First Principles where the promise of crypto and Web3 was fulfilled. We came up with 16 axioms that form the foundation of our thinking and our company today. For the first time in the history of Xord, we have a solid foundation to build on.</p><p>Those axioms are as follows:</p><ol><li>The value would be given to the users and builders instead of a few shareholders.</li><li>People want equity and access to open financial and economic systems.</li><li>People want global reach and accessibility for exchanging data and money.</li><li>People care about privacy/decentralization only if they are better than centralized systems. They want convenience and ease of use.</li><li>People have and will always want faster and low-cost transactions.</li><li>New forms of value will be created in the form of money, data, and composability.</li><li>New forms of value will be monetized such as social capital and cultural capital.</li><li>The new internet will derive the vast majority of its value through protocol and data composability.</li><li>Consumers will be the new marketers.</li><li>The world would be better off if intellectual properties were open source.</li><li>Identity and privacy will be human rights.</li><li>Network economies will be designed in a way that acting in the interest of the public would be more profitable than acting selfishly.</li><li>Token would be the new form of ownership. An internet orchestrated with tokens.</li><li>Collaboration will win over competition in most cases.</li><li>The role of investors will be more long-term and geared towards acting in the interest of the community.</li><li>Digital democratic organizations will be formed that exist entirely on the trust layer of the internet (blockchains).</li></ol><p>These axioms might seem obvious to many people, but for the first time, we were able to articulate what had always existed in our minds. These axioms will change and improve in the future as we close the knowledge gap. We want to provide each citizen of the world the ability to be truly free. For the first time in the history of humanity, we have the technology to do it. We intend to create a legacy that advances the cause of humanity.</p><p>The design of the internet had a fundamental flaw: the absence of a trust layer to allow strangers to transact. This is why we have always relied on big technology companies to mediate our interactions on the internet. Today we have the technology that allows us to democratize institutions. We can now build institutions and communities that do not take the sovereignty of the individual for granted and allow anyone to take part in it. We see digital organizations called DAOs based entirely on the internet doing massive public good.</p><h3>Redefining Our Vision</h3><p>We redefined ourselves once again, this time to focus the next 10 years of our company’s efforts to give freedom to the people through the use of decentralized technologies. This is the reason we have now stated our 10-year goal as:</p><p><strong><em>“Make Web3 products usable for 1 billion people”</em></strong></p><p>“Usable” is a key term here. The current technology cannot support billions of users transacting every second. We aspire to make that possible.</p><p>Web3 is more than just a set of technologies. It’s a movement to decentralize the internet. This transformation has to happen. It’s just about when.</p><p>Today the Web3 ecosystem is clumsy and suffers from bad user experience. If we truly want to accelerate the world’s transition to decentralized technologies, we have to make them usable for the average person. The user experience of the next generation of the internet needs to be as good if not better than what we have today.</p><p>We now know our purpose:</p><p><strong><em>“Xord exists to accelerate the world’s transition to Web3”</em></strong></p><p>The world is shifting more towards collaboration. In 2021, more than 34k developers contributed code to open-source crypto projects.</p><p>The DeFi sector has grown from 0 to more than $100B in less than 2 years . This growth is bound to extend in the coming years as better applications are developed. As more and more people understand the value and accessibility that blockchain-based protocols and products provide, the adoption of Web3 is going to increase manyfold.</p><p>Xord’s vision to onboard 1 billion users on Web3 can be imagined as our contribution to making the world decentralized, transparent, and honest. The dawn of the 4th industrial revolution is inevitable, and we are positive that through the initiatives taken by Xord, this transition can be accelerated.</p><h3>References</h3><ol><li><a href="https://medium.com/@laurashin/how-many-new-developers-joined-web3-in-2021-more-than-34-000-1017f157ce20">How Many New Developers Joined Web3 in 2021? </a>— Laura Shin (Jan 7 2022)</li><li><a href="https://a16zcrypto.com/state-of-crypto-report-a16z-2022/">Introducing the 2022 State of Crypto Report</a> — Darren Matsuoka, Eddie Lazzarin, Chris Dixon, Robert Hackett (May 17 2022)</li></ol><p><em>Originally published at </em><a href="https://xord.com/news/xord-from-first-principles-make-web3-usable-for-1-billion-people/"><em>https://xord.com</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=781fedb9ef0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/xord-from-first-principles-make-web3-usable-for-1-billion-people-781fedb9ef0">Xord From First Principles; Make Web3 Usable for 1 Billion People</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Advent Of STARKs With IOPs]]></title>
            <link>https://medium.com/xord/the-advent-of-starks-with-iops-4bd4f17bcf2f?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/4bd4f17bcf2f</guid>
            <category><![CDATA[zkp]]></category>
            <category><![CDATA[interactive]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[xord]]></category>
            <category><![CDATA[starkware]]></category>
            <dc:creator><![CDATA[Zainab Hasan]]></dc:creator>
            <pubDate>Fri, 29 Apr 2022 08:57:10 GMT</pubDate>
            <atom:updated>2022-04-29T08:57:10.444Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*SGf6VEB9ZnAcpoPBPMXaHA.png" /></figure><p>STARKs revolves around the idea of computational integrity, which essentially means that the output of a specific computation is correct.</p><p>In traditional financing, where banks are involved, trusted third parties such as auditors, accountants, etc ensure their integrity. Whereas in the crypto world, the integrity of computed data is verified by reading the whole proof. This proves to be a naive action.</p><p>Furthermore, if you were to prove to someone that you are over 18, you are most likely to provide your ID card, which means sharing more information than required. This is not ideal and <a href="https://xord.com/research/zero-knowledge-proofs-a-general-understanding/">zero-knowledge proofs</a> can take care of it.</p><p>Initially, Zero-knowledge system constructions were based on PCPs or probabilistically checkable proofs.</p><p><strong>Prover:</strong> An algorithm that receives an input x and calculates pi for that x.</p><p><strong>Verifier:</strong> A polytime deterministic algorithm that receives an input x and proof pi, then accepts or rejects that pi.</p><h4>Learn More on PCPs, IOPs, and STARKs at <a href="https://xord.com/research/the-advent-of-starks-with-iops/">https://xord.com/research/the-advent-of-starks-with-iops/</a></h4><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4bd4f17bcf2f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/the-advent-of-starks-with-iops-4bd4f17bcf2f">The Advent Of STARKs With IOPs</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Trusted Setup of ZK-SNARK]]></title>
            <link>https://medium.com/xord/the-trusted-setup-of-zk-snark-4a9a71b5fc05?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/4a9a71b5fc05</guid>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[xord]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <dc:creator><![CDATA[Rabia Fatima]]></dc:creator>
            <pubDate>Fri, 29 Apr 2022 08:56:15 GMT</pubDate>
            <atom:updated>2022-04-29T08:56:16.302Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*IcLEOMmCBPII74ne2-HwlA.png" /></figure><p>Zero-knowledge proofs are cryptographically advanced proofs which are being used by many blockchain protocols to attain privacy and scalability. Though the more these proofs look sophisticated, the more complexity is inherent within them. In the second series of our publication, we are going to discuss the pre-processing of ZK-SNARK and how a multi-trusted computation setup really works.</p><p>Previously, in our series of ZK- SNARK<a href="https://xord.com/research/the-low-level-working-of-zk-snarks/"> articles</a> I have explained how a basic ZK protocol works and we have also discussed some scenarios where a prover can cheat and forge the proofs.</p><p>However, we have not discussed the origination point of the proving polynomial P(x) and why it is important. To begin with, we know that zero-knowledge proofs mainly depend on three algorithms.</p><ol><li>The keys to interact.</li><li>Generation of proof for a statement.</li><li>Verification of the proof.</li></ol><p>In this article, I will discuss the importance of keys and why trusted setup is a better trade-off for security. We will also see the initial mathematical structure of Multi-trusted party computation.</p><p>To read about more in detail please visit to this <a href="https://xord.com/research/the-trusted-setup-of-zk-snark/">link</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4a9a71b5fc05" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/the-trusted-setup-of-zk-snark-4a9a71b5fc05">The Trusted Setup of ZK-SNARK</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Cryptographic algorithms as interactive and non-interactive proofs]]></title>
            <link>https://medium.com/xord/cryptographic-algorithms-as-interactive-and-non-interactive-proofs-263183d87e25?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/263183d87e25</guid>
            <category><![CDATA[proof-of-stake]]></category>
            <category><![CDATA[difference]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[xord]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Filza]]></dc:creator>
            <pubDate>Fri, 18 Mar 2022 10:44:32 GMT</pubDate>
            <atom:updated>2022-03-18T10:44:32.119Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*3bAuJDIeJt48OVqRzsZ3Fw.png" /></figure><p>This article aims to reach a conclusion and spread awareness about the interactive cryptographic systems and non-interactive cryptographic systems and the common difference that differentiate the two. The algorithms to be discussed in this article are Diffie Hellman (DH), Rivest Shamir Adleman (RSA), Schnorr Signature Scheme, Schnorr Identification Scheme, Digital Signature Algorithm (DSA), and FIAT Shamir.</p><h3>Introduction</h3><p>The debate remains whether the interactive cryptosystem or non-interactive cryptosystem is better. In this article, we will minimize the discussion by stating some facts and clarity based on these two systems. Let’s first go through some of the basic overviews:</p><p>In the symmetric cryptographic system, the sender and receiver use one key, or it is better to say they exchange one secret key to encrypt and decrypt at both sides. In an asymmetric cryptographic system, the sender and receiver use two separate keys at both ends. The sender uses the receiver’s public key to encrypt the message, and only the receiver can decrypt it using their private key. Let’s further read how these systems differentiate and what is more to the cryptographic system than just message passing.</p><h3>Trusted system</h3><p>A trusted system is a communication channel through which information is sent from source to destination but without opening it to the channel. In a cryptographic system, a trusted system has a broad meaning, but the root cause is the protection and security of keys from theft.</p><h3>Interactive proof system</h3><p>It is an abstract system with two parties; a prover and a verifier. The communication between these two parties is in terms of computation, known as an interactive system. In the interactive proof system communication, it is deduced that the prover has unlimited resources but cannot be trusted, whereas the verifier has fewer resources but is always honest. Therefore, an interactive proof system is based on trust and honesty.</p><p>Messages are exchanged between the verifier and prover, and the way it works is when the prover states something, the verifier verifies it until has itself convinced that the statement is correct and the prover is telling the truth.</p><p>Most of the interactive proof systems depend upon the verifier’s random choices ability. The verifier sends an unexpected challenge, and the prover utilizing the random set has to create proof. The verifier then verifies. The verifier can inquire repeatedly. It is the reason that this system is called an interactive proof system.</p><p>The interactive proof system has two main properties:</p><ol><li><strong><em>Completeness: </em></strong>Completeness means that the prover can prove anything that is right.</li></ol><p><strong><em>2. Soundness: </em></strong>Soundness is when the prover cannot prove anything that is wrong.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/652/0*-aUpktmPX-ar9hdd" /><figcaption>Image source: <a href="https://blog.cs.ut.ee/2020/08/13/karim-baghery-reducing-trust-and-improving-security-in-zk-snarks-and-commitments/">https://blog.cs.ut.ee/2020/08/13/karim-baghery-reducing-trust-and-improving-security-in-zk-snarks-and-commitments/</a></figcaption></figure><h3>Non-interactive proof system</h3><p>To make the communication one-way and deterministic, non-interactive proof systems emerged. The non-interactive systems have no direct interaction between the prover and verifier. It is done to make a trust-less system.</p><p>Unlike the interactive proof system, The verifier does not send a random set, but the system relies on an oracle model as a way to prove and verify. This Random Oracle Model (ROM) is called a theoretical black box that responds to a query with a random response. Both the prover and the verifier look up the model for their reference strings. In this case, the verifier does not inquire the same message repeatedly from the prover. This approach of a non-interactive proof system is called deterministic.</p><p>The interactive proof system has two main properties:</p><ol><li><strong><em>Completeness: </em></strong>Completeness means that the verifier, without a doubt, will be convinced of the fact.</li></ol><p><strong><em>2. Soundness: </em></strong>Soundness is that the prover without cheating can convince the verifier that the statement is true.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/652/0*AzlqPWKVnM2LvhUY" /><figcaption>Image source: <a href="https://blog.cs.ut.ee/2020/08/13/karim-baghery-reducing-trust-and-improving-security-in-zk-snarks-and-commitments/">https://blog.cs.ut.ee/2020/08/13/karim-baghery-reducing-trust-and-improving-security-in-zk-snarks-and-commitments/</a></figcaption></figure><h3>Why do we need proof systems:</h3><p>When people use services or products, they require proof that the working behind it or the product made is authentic, its documents, and the process has been validated or not. These queries are best tackled using proof systems. Proofs and verifications are made without sharing any additional or personal information to satisfy such questions. They are stated over interactive and non-interactive proof systems.</p><h3>Algorithms implementation based on the difference between the two systems</h3><p>We will start looking at the algorithms based on the differences based on the interactive and non-interactive approaches.</p><h3>Diffie Hellman:</h3><p>Diffie Hellman is a secure key-exchanging protocol. This method is based on Non-Interactive Key Exchange (NIKE). NIKE is a cryptographic procedure that allows the two parties who know each others’ public keys to settle on a shared symmetric variable that does not require any interaction and is available to both. Its properties are listed below:</p><ul><li>The algorithm does not share any random number to any side of the communicators.</li><li>No challenges are presented to be validated.</li><li>It does not authenticate any side of the party.</li><li>It provides Encryption.</li><li>It includes the identification of the two parties.</li><li>There is a key generation process involved in DH.</li><li>No signatures are created or validated based on the DH algorithm.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*YmyBQsm0GfRwslXo" /><figcaption>Image source: <a href="https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange">https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange</a></figcaption></figure><h3>Rivest Shamir Adleman:</h3><p>The RSA algorithm is the all-rounder algorithm that can be used for data encryption, key exchange, and signature. It is an asymmetric algorithm it uses a pair of keys. RSA algorithm is widely used for a non-interactive approach for cryptography.</p><p>The public key is shared publicly while the private key is not shared, and know that the public key available to the verifier and used for Encryption does not yield a private key. Below are the properties discussed of RSA:</p><ul><li>The algorithm does not share any random number to any side of the communicators.</li><li>No challenges are presented to be validated.</li><li>It authenticates the two parties associated with the communication.</li><li>It provides Encryption.</li><li>It includes the identification of the two parties.</li><li>It also includes signature generation.</li><li>There is a key generation process involved in RSA.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/685/0*-7uAZ7o4xId8cl-Y" /><figcaption>Image source: <a href="https://www.c-sharpcorner.com/UploadFile/75a48f/rsa-algorithm-with-C-Sharp2/">https://www.c-sharpcorner.com/UploadFile/75a48f/rsa-algorithm-with-C-Sharp2/</a></figcaption></figure><h3>Digital Signature Algorithm:</h3><p>Digital Signature Algorithm (DSA) has two operations; Signature generation and signature verification. It is an asymmetric signature generation algorithm. It is a non-interactive system. The signer takes a random value for each signature, and the verifier verifies it using multi-exponentiation. The verifier uses the signed message, signer’s public key, and signature to verify. But no challenge is given to the prover by the verifier.</p><ul><li>It does not perform Encryption</li><li>It can identify the two parties communicating.</li><li>It can authenticate the prover and verifier.</li><li>It is used for signature generation and verification.</li><li>It does a key exchange between the prover and verifier.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/782/0*5q3o51yPS1APCst3" /><figcaption>Image source: <a href="https://www.simplilearn.com/tutorials/cryptography-tutorial/digital-signature-algorithm">https://www.simplilearn.com/tutorials/cryptography-tutorial/digital-signature-algorithm</a></figcaption></figure><h3>Schnorr Signature Scheme:</h3><p>Schnorr signature scheme is the most efficient and secure scheme, more than RSA and DSA. It has non-interactive proof of the system. The challenge in the Schnorr Identification scheme is replaced by randomness. The random integer is added in the signature while generating a signature for each message. This scheme is more or less a version of FIAT Shamir. Schnorr signature scheme is also used for multiple signatures generation and verification. Some properties of the Schnorr Signature Scheme are listed as:</p><ul><li>It can be used for Encryption</li><li>It can be used for the identification of two parties</li><li>It can help authenticate.</li><li>It is used for signature generation and verification.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/680/0*SUFSrwfZ_HtKNiak" /><figcaption>Image source: <a href="https://slideplayer.com/slide/11001593/">https://slideplayer.com/slide/11001593/</a></figcaption></figure><h3>Schnorr Identification Scheme:</h3><p>Schnorr identification scheme is a type of exchange protocol with a prover and a verifier. The prover has the public and secret keys. In comparison, the verifier keeps the prover’s public key copy. This scheme works in an interactive system where the verifier challenges the prover. The prover sends back the response, and the verifier verifies.</p><p>It has the same properties as the Schnorr Signature Scheme. However, it is being modified, and there might be an upgrade added to Schnorr that ECDSA (Elliptic Curve Digital Signature Algorithm) lacks.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/283/0*-RSHOdPRqf3IsE-a" /><figcaption>Image source: <a href="https://www.researchgate.net/figure/An-interactive-Proof-Protocol-Source-modified-from-Gol02_fig1_221947500">https://www.researchgate.net/figure/An-interactive-Proof-Protocol-Source-modified-from-Gol02_fig1_221947500</a></figcaption></figure><h3>FIAT Shamir</h3><p>FIAT Shamir is a type of non-interactive schnorr signature scheme. Both methods provide the solution to identification problems. However, in FIAT Shamir, the significant computation is done by the prover, whereas in the Schnorr signature scheme, the main calculation is done by both the prover and the verifier.</p><p>A few of the FIAT Shamir properties are listed below:</p><ul><li>It is not used for Encryption.</li><li>It is used for signature generation and verification.</li><li>It is used for identification problem-solving.</li><li>It can not be used for authentication.</li><li>It does not generate keys or exchanges in the protocol.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/593/0*ydunjH9LESCx6R7F" /><figcaption>Image source: <a href="https://slideplayer.com/slide/11001593/">https://slideplayer.com/slide/11001593/</a></figcaption></figure><h3>Analysis</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/974/0*N65ls0KVlEfhRANU" /></figure><h3>Conclusion</h3><p>To quickly overview all algorithms, use some Parameters, Public keys, Private keys as inputs, some exchange the keys for Encryption, some algorithms exchange the keys for proving and verification of the data. All the algorithms do not differ much, except for using the direct channel of communication or indirect.</p><p>The interactive and non-interactive systems can be distinguished using a single entity in between. The distinction strictly depends on whoever generates the critical number, making it interactive and non-interactive.</p><p>In the interactive trusted systems, the prover commits a statement, and the verifier sends the challenge to inquire if the prover has integrated a reasonable solution in response to that commitment. The prover using that challenge sends a reply (Result) to the verifier. The verifier verifies if the prover has sent the correct solution and has used the given challenge or not.</p><p>In the non-interactive trusted system, the verifier and the prover do not interact directly. Instead, an entity like a storage box is used in the middle, which has the resources available required by both the prover and verifier. This middle entity is known as Random Oracle Model (ROM). You can read more about ROM <a href="https://en.wikipedia.org/wiki/Random_oracle">here</a>.</p><p>Also check out this article related to Mina Blockchain: <a href="https://xord.solutions/mina-lightest-blockchain/">https://xord.solutions/mina-lightest-blockchain/</a></p><h3>References</h3><ul><li>Trusted System (2022), Wikipedia <a href="https://en.wikipedia.org/wiki/Trusted_system">https://en.wikipedia.org/wiki/Trusted_system</a></li><li>What Are the Security Considerations When Choosing A Root of Trust Solution?,(2020),Prof. Yehuda Lindell <a href="https://www.unboundsecurity.com/blog/the-basic-root-of-trust-in-cryptographic-infrastructure/">https://www.unboundsecurity.com/blog/the-basic-root-of-trust-in-cryptographic-infrastructure/</a></li><li>Interactive proof system, (2022), Wikipedia <a href="https://en.wikipedia.org/wiki/Interactive_proof_system">https://en.wikipedia.org/wiki/Interactive_proof_system</a></li><li>What is the difference between Completeness and Soundness in first-order logic?, (2012), Mathexchange.com https://math.stackexchange.com/questions/105575/what-is-the-difference-between-completeness-and-soundness-in-first-order-logic</li><li>Interactive and Non-Interactive Proofs of Knowledge, (2012), Olivier Blazy <a href="https://tel.archives-ouvertes.fr/tel-00768787/file/thesis.pdf">https://tel.archives-ouvertes.fr/tel-00768787/file/thesis.pdf</a></li><li>Comparison: Fiat-Shamir, GQ, and Schnorr <a href="https://ebrary.net/134584/computer_science/comparison_fiat_shamir_schnorr">https://ebrary.net/134584/computer_science/comparison_fiat_shamir_schnorr</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=263183d87e25" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/cryptographic-algorithms-as-interactive-and-non-interactive-proofs-263183d87e25">Cryptographic algorithms as interactive and non-interactive proofs</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Explaining Quadratic Arithmetic programs]]></title>
            <link>https://medium.com/xord/explaining-quadratic-arithmetic-programs-837c6437702d?source=rss----a7974b2f8a92---4</link>
            <guid isPermaLink="false">https://medium.com/p/837c6437702d</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[xord]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Rabia Fatima]]></dc:creator>
            <pubDate>Thu, 17 Mar 2022 12:09:01 GMT</pubDate>
            <atom:updated>2022-03-17T12:09:01.307Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*aii5s3Z8CGH-f5stDMHlPw.png" /></figure><p>This article is greatly inspired by Vitalik explanation on Quadratic arithmetic programs(<a href="https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649">QAPs)</a>. In this article we are going to take a direct approach to understand the complex step in making snarks or you may say that the first step of representing the massive state data into a low degree polynomial. If you are not familiar with the basics of polynomials and what benefits do they really offer? you may refer to this <a href="https://xord.com/research/polynomial-commitments-for-stateless-clients/">article</a>.</p><p>To begin with, we must know that ZK-snarks are not applicable to any computational problem. There are few NP problems(such as boolean satisfiability) which are computationally infeasible to verify.</p><p>When we say that every NP problem has zero-knowledge proof, what we mean is that any NP problem instance can be proven to be true in ZK. This is what Goldreich, Micali and Wigderson explained in their <a href="https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Proofs_That_Yield_Nothing_But_Their_Validity_or_All_Languages_in_NP_Have_Zero-Knowledge_Proof_Systems.pdf">paper</a> . So to operate the problem we first have to convert the problem into a right form. This form is termed as Quadratic Arithmetic Program. This step is separate and will run in parallel alongside the zero-knowledge proof creation and its verification. The flow of QAP is <strong>program→circuit→R1CS→QAP.<br></strong>To learn about more read upon this <a href="https://xord.com/research/explaining-quadratic-arithmetic-programs/">link</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=837c6437702d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/xord/explaining-quadratic-arithmetic-programs-837c6437702d">Explaining Quadratic Arithmetic programs</a> was originally published in <a href="https://medium.com/xord">Xord</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>