Supragya Raj

@sraj

computer "science" admirer who expresses it via engineering

Joined on Jul 30, 2020

  • Lately I have found myself reading the paper on Poseidon hash function available here. In essence, this came from the need to understand why this particular hash function is used so widely in the domain of zero-knowledge - what makes it special, and why others just don't cut it (or maybe they do)? What happened to all the well known hashing algorithms such as MD5, SHA256, Keccak256 (the ethereum one)? Somewhere I also heard of something called MiMC. What really is that? The text here is basically my findings while I was struggling with the above question. And if you are trying to find some info on the same, maybe just read on. PSA: While attempts will be made to understand "WHY" such constructions are used, they are not investigated via any deep cryptographic analysis. I am not a cryptographer, nor do I want to sound like one. What really is a hash function? A cryptographic hash function is a mathematical algorithm that takes an input "message" (of variable length possibly) and produces a fixed-size string of characters, which is typically a sequence of numbers and letters. The output, often referred to as the hash value or hash code, is unique to the input data. Even a small change in the input data should result in a significantly different hash value.
     Like  Bookmark
  • Recently, I have been following the awesome tutorial describing the internal details of zkSNARK system PLONK called PLONK by hand by Joshua Fitzgerald (Metastate team). The rust implementation that closely follows this is given by Adrià Massanet in PLONK by fingers. For brevity, for rest of this document, PLONK by hand and PLONK by fingers will be abbreviated as PBH and PBF respectively. While PBF is a bigger implementation of the zkSNARK protocol described in PBH, what we concentrate on in this document is how in rust implementation of elliptic curves go. The purpose of this document remains me describing as a non-cryptography expert the interpretations I draw from what I see. Things might be hand-wavy and could be wrong, but the point remains for this to be a good entry point for others who like to venture into similar territories, which may be slightly wrong at first. May this be a quick disclaimer for readers :P . What are elliptic curves and how do they feature here Elliptic curves are an important cryptographic primitive in modern times. What makes them valuable in where they are used are generally two properties (one optional, but used in PLONK). Discrete Log Problem: Points on elliptic curves form a group $G$. Further, this group has property of being finite and cyclic. What that entails is that there exists some element $g \in G$ (the generator) that all other elements in $G$ can be constructed by raising $g$ to some power $x$ as $g^x$. However once you have $g$ and $g^x$, there exists no efficient "classical computer" algorithm that could deduce $x$.
     Like  Bookmark