<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Dhruv on Medium]]></title>
        <description><![CDATA[Stories by Dhruv on Medium]]></description>
        <link>https://medium.com/@druvsssm123?source=rss-2d988263beba------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*Iu1ZTnHiSTcWoR2X</url>
            <title>Stories by Dhruv on Medium</title>
            <link>https://medium.com/@druvsssm123?source=rss-2d988263beba------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 02:07:21 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@druvsssm123/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Campus Fora — Authorization (assignment 3)]]></title>
            <link>https://medium.com/@druvsssm123/campus-fora-authorization-assignment-3-7349b777371b?source=rss-2d988263beba------2</link>
            <guid isPermaLink="false">https://medium.com/p/7349b777371b</guid>
            <dc:creator><![CDATA[Dhruv]]></dc:creator>
            <pubDate>Fri, 16 Jun 2023 19:06:02 GMT</pubDate>
            <atom:updated>2023-06-16T19:06:02.376Z</atom:updated>
            <content:encoded><![CDATA[<h3>Campus Fora — Authorization (assignment 3)</h3><p>To begin with this backend assignment you must get familiar with some concepts —</p><ol><li>Asymmetric Encryption</li><li><a href="https://jwt.io/introduction">JWT</a> Tokens</li><li>R<a href="https://www.geeksforgeeks.org/jwt-authentication-with-refresh-tokens/">efresh token</a>s</li></ol><blockquote>Endpoints —</blockquote><p>/api/auth/register</p><p>/api/auth/verifyemail/:code</p><p>/api/auth/login</p><p>/api/auth/logout</p><p>/api/auth/refresh</p><p>/api/getAll &gt;&gt; No authentication needed</p><p>/api/user/getMyText/:id &gt;&gt; Only I should be able to see my asked questions.</p><p>/api/user/createText/:id &gt;&gt; Post Question</p><p>For used id, you may generate it or just use the cc username (Email without the @iitk.ac.in)</p><p>First — For the assignment, prefer GORM to interact with Postgres. Also, if you haven’t already, install <a href="https://www.docker.com/get-started/">Docker</a> on your system and run a Postgres container.</p><p>File structure —</p><blockquote><strong>Campus_Fora_Assign3</strong></blockquote><blockquote>— models</blockquote><blockquote>— —User.go</blockquote><p>— utils</p><p>— — security.go</p><p>— — token.go</p><p>— migrate</p><p>— — migrate.go</p><p>—controllers</p><p>— — authController.go</p><p>— routes</p><p>— userRoutes.go</p><p>— authRoutes.go</p><p>— middleware</p><p>— — authorize.go</p><p>main.go</p><p>User.go will have the following structs —</p><ol><li>User struct — {ID, Name, Email, Password, Role, Branch, CreatedAt, UpdatedAt}.</li><li>Register struct —{ Name, Email, Password, Role, Branch}. For this assignment, the user is deciding his role for himself, but later this will be changed to IITK-user by default, as only the admin has role-issuing privilege.</li><li>Login struct — {Email, Password}</li><li>Response struct</li></ol><p>In the migrate.go, use <a href="https://gorm.io/docs/migration.html">AutoMigrate</a> provided by GORM to migrate the User schema to the database.</p><p>Password Security —</p><p>In security.go make two functions-</p><p>One to hash a given string, as we will only store a hashed pswd,</p><p>And another to compare the hashed pswd and a candidate string.</p><p>Use <a href="http://golang.org/x/crypto/bcrypt">brcypt</a> package for your hashing algorithm.</p><p>Token Generation —</p><p>Next in token.go file you’ll be creating two functions, one to create and sign a token, and another to validate it.</p><pre>func CreateToken(t time.Duration, payload interface{}, privateKey string) (string, error)<br>func ValidateToken(token string, publicKey string) (interface{}, error)</pre><p>So, you have two tokens, access and refresh that you’ll be signing, so we need two pairs of public-private keys. You may generate them yourself in Go, using <a href="https://www.systutorials.com/how-to-generate-rsa-private-and-public-key-pair-in-go-lang/">crypto/rsa</a>, or use an online generator.</p><p>Encode these four keys in base64 encoding using &quot;encoding/base64&quot; and store them in .env, something like —</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/649/1*meXMgJ8XkjXy3-ck2U_POw.png" /></figure><p>You’ll be using “github.com/golang-jwt/jwt” package.</p><p>In CreateToken —</p><p>This function takes the duration specified in the .env, user.ID interface in payload and a privateKey in .env and returns a token with any error.</p><p>First, decode back the base64 key using DecodeString of base64 package then pass this decoded string to jwt.ParseRSAPrivateKeyFromPEM to get the required key.</p><p>Then to generate a token with jwt.NewWithClaims, refer to <a href="https://www.oreilly.com/library/view/building-restful-web/9781788294287/06645ecf-8853-4bfe-bda8-fce46c5b310f.xhtml">this</a>.</p><p>The signing method will be ‘RS256’,</p><p>MapClaims will contain</p><p>— “sub”: payload, &gt;&gt; user <br> — “exp”: time.Now().Add(t).Unix(), &gt;&gt; token expiry time<br> — “iat”: time.Now().Unix() &gt;&gt; token issue time</p><p>ValidateToken — -</p><p>Will take a candidate token and a publicKey.</p><p>Repeat the same procedure of decoding and parsing as you did for private key.</p><p>Implement jwt.parse function which returns a parsedToken, then use parsedToken.Claims.(jwt.MapClaims) to extract the claims we defined previously. return claims[“sub”] which contained the payload (in our case user ID).</p><blockquote>Now you need to implement the controllers and middlewares — -</blockquote><p>In authController.go implement the functions for-</p><p>Registering User — response will be- {ID, Name, Role}</p><p>Similarily Login, which first queries db if the mail exists, then validates the provided password against the hashed one. Then generate the Access and Refresh tokens which get sent to the client as HTTPOnly cookies, use SetCookie of gin.</p><p>AcessTokenRefresh — Here you will validate the refresh token from the cookie and set the cookie with new created access token.</p><p>Logout — Just send an expired cookie set with null tokens and -1 for cookie life.</p><p>In userController.go — define a function to return the currently logged in user.</p><p>Middleware —</p><p>authorize.go — Extract access token either from the cookie or header, validate the token and check if the user exists.</p><p>Now define the all the routes using RouterGroup of gin, evoke all the routes in main.go, make sure you have install the CORS package for the gin server.</p><p>This assignment is meant to be done in stages</p><p>1 — Use only JWT, without refresh tokens and return the information user provided during registration in register/login response.</p><p>2 — Add refresh tokens too.</p><p>3 — Add mail verification with help of a SMTP provider.</p><p>4 — Secure your CRUD app from backend assignment 1.</p><p>5 — Implement reset pswd service.</p><p>6 — Frontend integeration</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7349b777371b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Bloom filters]]></title>
            <link>https://medium.com/programming-club-iit-kanpur/bloom-filters-7e51abf48007?source=rss-2d988263beba------2</link>
            <guid isPermaLink="false">https://medium.com/p/7e51abf48007</guid>
            <dc:creator><![CDATA[Dhruv]]></dc:creator>
            <pubDate>Thu, 22 Dec 2022 16:58:45 GMT</pubDate>
            <atom:updated>2022-12-26T07:01:22.509Z</atom:updated>
            <content:encoded><![CDATA[<p>Let us begin by imagining a situation — - This blog becomes really popular! So popular that thousands of users at a time send a query to fetch it. Now, this may give latency issues due to a centralised server. That&#39;s where proxy servers come into the picture.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*T7Xpn7ZzfUdTwU2hbwAwFQ.png" /></figure><p>Proxies act as a gateway between the user and the source server, storing (or caching) the server’s resources. When the user files a query to access a resource, the proxy checks to see if it has a cached recent copy of the resource and immediately delivers it to the user. If not, the resource is retrieved from the provider of web content and if the proxy gets many requests for the same resource, it’ll simultaneously cache it.</p><p>This blog isn’t about proxy servers.</p><p>How the proxy that caches millions of queries knows if the client query is not present in the cache to further send it to the isp, that too in O(1) time as space efficient as possible?</p><p>To solve this, a special data structure — Bloom filters are used, with their primary use case being, to test whether an element (query) belongs to a set (millions of cached queries).</p><p>Sounds like something that can be easily done by <em>Hashmaps, BSTs or even Tries </em>if we are concerned with strings!</p><p>Let’s take a look at some use cases where bloom filters can be put to use to get a clear understanding of our requirements: —</p><ol><li><strong>Weak password Detection:</strong>: A list of weak passwords can be maintained and the user can be warned while creating/updating his password, in case of a match to prevent cyber attacks like <a href="https://medium.com/@arianehorbach/the-basics-of-the-basic-dictionary-attack-2234b72a4fee">dictionary attacks</a>. A password not belonging to the list won’t be at least weak.</li><li><strong>Safe Browsing::</strong> Browsers maintain a very long list of malicious URLs, everytime we try to fetch a new URL, it needs to be verified it doesn’t belong to the list.</li><li><strong>Duplicate Usernames::</strong> While creating a new account on social media, many times we need to pick a different username as the previous one is already taken.</li><li><strong>Databases:: </strong>The disk lookups for non-existent rows or columns need to be reduced to avoid costly disk lookups, doing so considerably increases the performance of a database query operation.</li><li><strong>Tracking User Traffic::</strong> If a visiting user has ever visited before. (is it a new or existing user?)</li><li><strong>Proxy caching::</strong> There are multiple proxies in a network. When a user accesses a website, proxies interpret the request and respond to it on the behalf of the original server. All proxies cache resources of some websites but all don’t necessarily cache the same resources. A Proxy hashes all URLs of its cached resources and maintains a record of them. Then all proxies share their URL record among themselves, basically telling ‘<em>I have cached these websites</em>’. <br>Consider requesting ‘A.com’. The GET request will go to the nearest proxy P1. It will check its cache record, if that<em> proxy doesn’t have the cache</em>, it’ll find a proxy in the network with the desired cache of ‘A.com’. If <em>no proxy has the cache</em>, the request will be sent to ISP. This scales well when there are millions of the same requests. The catch is, <em>cached internet history is large,</em> and we like our search to be <strong>quick</strong>.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Lqb1Ou5G-LeprBBhKEiuzg.png" /></figure><p>Noticing a general pattern in the above, we are given a large pool of data, which can be a list of billions of users or passwords and we are only concerned with if <strong><em>some element exists within that pool or not</em></strong>.</p><p>Hashmaps offer lookups in a really convenient O(1) time complexity but are less space efficient and a strong hash function is needed to minimise collisions, it won’t scale well practically when data is immense.</p><p>Let’s see how bloom filters overcome this.</p><p>Working of a Bloom Filter:: —</p><p>Start by considering an array of <em>m </em>bits, all set to 0. We have <em>k</em> hash functions (all generate a uniform random distribution), each of which hashes an element to one of the indexes of the above array (i.e 0 to m-1).</p><p>To <em>add</em> an element, we feed it to each of the <em>k</em> hash functions to get <em>k</em> array positions. Set the bits at all these positions to 1.</p><p>To <em>query</em> for an element (test whether it is in the set), we feed it to each of the <em>k</em> hash functions to get <em>k</em> array positions. If <em>any</em> of the bits at these positions is 0, the element is definitely not in the set; if it were, then all the bits would have been set to 1 when it was inserted.</p><p>For eg, we have 3 hashfunctions, they’ll map each element in set {x,y,z} to three indexes each. When we query for ‘w’ we get one position for w which is not set, hence ‘w’ is definitely not present.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*_VvrBt37zOT-bhZF9tVwqw.png" /></figure><p>Consider querying for ‘u’, which is not in our set but has all its bits set. The query will give a ‘<strong><em>false positive</em></strong>’ for this case.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*tgCDdij1_PGzH821BhHi7g.png" /></figure><p>The above example clears one thing, in a simple bloom filter: —</p><ol><li>If a query response is negative, then the element is definitely not in the set.</li><li>In the case of positive, we can’t be sure. It may result in a false positive.</li></ol><p>That’s why bloom filters are known as <strong><em>probabilistic data structures.</em></strong></p><p>Now coming to why bloom filters are prefered over hashtables in certain tasks:: —</p><p>Our primary needs are to verify if something <em>does not exist</em> in a very large pool of data, <strong>quickly and space efficiently.</strong></p><ol><li><strong>Space utilization: </strong>Hashtables store the element in the bucket array, whereas bloom filters utilize a bit array, only store whether the elements exist or not (it is just an array of 0 and 1s). They fit well for tasks concerning with only verifying the absence of an element. The number of bit boxes in a filter can be decided by us.</li><li><strong>Collision handling</strong>: We have to minimize collisions in hash tables so must choose multiple hashes or a strong hash or solve it with probing. A bloom filter uses many hash functions. There is no need to handle collisions, which can make it computationally lighter.</li><li>A simple implementation of Bloom filters in python —</li></ol><pre>import mmh3<br><br>class Bloom_filter(set):<br><br>    def __init__(self, m, k): #initialises a bit array of &#39;m&#39; size and<br>                              #specifies the number of hash-functions,&#39;k&#39;<br>        self.m=m<br>        self.k=k<br>        self.bit_array = [0]*m<br>    def add(self, item):<br>        for i in range(self.k):<br>            index = mmh3.hash(item, i) % self.m<br>            self.bit_array[index] = 1<br>    def query(self, item):<br>        for i in range(self.k):<br>            index = mmh3.hash(item, i) % self.m<br>            if self.bit_array[index] == 0:<br>                return False<br>        return True<br>if __name__ == &#39;__main__&#39;:<br>    bloom = Bloom_filter(100, 10)<br>    data = [&#39;java&#39;,&#39;cpp&#39;,&#39;javascript&#39;,&#39;kotlin&#39;,&#39;swift&#39;,&#39;rust&#39;,&#39;ruby&#39;,<br>            &#39;agile&#39;,&#39;algorithm&#39;,&#39;application&#39;,&#39;adaptive&#39;,&#39;bootstrap&#39;,&#39;backend&#39;,<br>            &#39;github&#39;,&#39;http&#39;,&#39;jQuery&#39;,&#39;python&#39;,&#39;ssl&#39;,&#39;version&#39;]<br>    for word in data:<br>        bloom.add(word)<br>    test_data=[&#39;swift&#39;,&#39;version&#39;,&#39;emaad&#39;,&#39;scala&#39;]<br>    for word in test_data:<br>        if bloom.query(word):<br>            if word in data:<br>                print(&#39;{} is in bloom filter as expected.&#39;.format(word))<br>            else:<br>                print(&#39;{} is not present in the entered data. Bloom filter says ohterwise, False Positive!&#39;.format(word))<br>        else:<br>            if word not in data:<br>                print(&#39;{} is present neither in the entered data nor the bloom filter as desired.&#39;.format(word))</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b3kt59e-DYGpdifiB6RiUw.png" /></figure><blockquote>Probability of false positives: —</blockquote><p>To improve our filter, we want to reduce the false positives.</p><p>Some intuition first:: —</p><ol><li>If ‘m’ is really large, the set bits will be spread out enough such that hashes of a non-existing element will have less chance to have all its bits set. Hence, decreasing false positives.</li><li>Similarly, consider if we have only one bucket, all elements, are hashed to that one bucket and the chances of error become 100%.</li><li>Having too many hash functions with limited ‘m’ will increase the number of bits set per element, increasing the risk of false positives. Whereas, a single hash function will lead to too many collisions, especially while querying because a false positive will be triggered only if <em>all</em> of the bit positions you inspect are set, and the number of bit positions you inspect is equal to the number of hash functions.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/314/1*lRTr3kpwu409poKlKjF33Q.png" /><figcaption>False positive probability formula</figcaption></figure><p>You may refer to this<a href="https://youtu.be/vc7TQ8g2XlQ"> video</a> for the derivation.</p><p>Making m=1, gives the false positive probability of 1, whereas making it tend to infinity, gives the probability of 0.</p><p>To optimise k, we need to minimise the above expression. By differentiating it wrt k, we find the expression for optimal k: —</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/178/1*ERH7BQVexjyxHPXcx3lZbw.png" /></figure><p>’n’ is the number of elements in our set.</p><p>Now, that we got the relation for the number hash functions we should use, how to decide on ‘m’ for our filter? There’s a general convention that we want to keep at most 70–80 per cent bits set. By choosing our desired false positives probability we can find ‘m’.</p><p>One major issue that we have not addressed in this blog is, simple bloom filters lack<strong><em> delete</em></strong> operation! It concerns our example 4) of proxy caching, as caches are frequently updated and not frequently accessed data should be deleted but we can’t delete by simply reversing a bit as it may also be a hash of some other element. To solve this,<a href="https://en.wikipedia.org/wiki/Counting_Bloom_filter"> Counting Bloom filters</a> are used.</p><p>In conclusion, the most significant advantage of Bloom filters over other data structures such as self-balancing trees, tries and HashMaps is in terms of <strong>space utilization</strong>. Others store <strong>each element in its entirety</strong>. The storage requirement in this case can range from a few bits to several bytes. Hence they are used to <strong>effectively speed up answers in a key-value storage system</strong>. If this blog got recommended to you by Medium itself, it’ll make use of bloom filters to make sure you don’t get the same blog you’ve read recommended again.</p><p><strong><em>References:</em></strong></p><blockquote>Wikipedia<br>https://www.youtube.com/watch?v=bgzUdBVr5tE</blockquote><p><em>Authors: Dhruva Singh Sachan<br>Editor: Parinay Chauhan</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7e51abf48007" width="1" height="1" alt=""><hr><p><a href="https://medium.com/programming-club-iit-kanpur/bloom-filters-7e51abf48007">Bloom filters</a> was originally published in <a href="https://medium.com/programming-club-iit-kanpur">Programming Club, IIT Kanpur</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>