YACL Talk | Nov 21 | Harjasleen Malvai, UIUC - Memory Accesses for SNARKs and Constraint-Friendly Map-to-Elliptic-Curve-Group Relations

[Aviv Yaish]

Join our next talk!

• Harjasleen Malvai, UIUC - Memory Accesses for SNARKs and Constraint-Friendly Map-to-Elliptic-Curve-Group Relations
• Nov 21, 11:00am
• Abstract: This talk will be divided into two parts. Part I: Memory Access Solutions for SNARKs. In this part of the talk, I will motivate the unique challenge of RAM for SNARK programming and provide an overview of the different techniques used to address it. This serves to motivate the second part of the talk and introduce all of our audience to the need for a constraint efficient map-to-elliptic-curve primitive.  Part II: Constraint-Friendly Map-to-Elliptic-Curve-Group Relations and Their Applications. Hashing to elliptic curve groups is a fundamental operation used in many cryptographic applications, including multiset hashing and BLS signatures. With the recent rise of zero-knowledge applications, they are increasingly used in constraint programming settings. For example, multiset hashing enables memory consistency checks in zkVMs, while BLS signatures are used in proof of stake protocols. In such cases, it becomes critical for hash-to-elliptic-curve-group constructions to be constraint-friendly such that one can efficiently generate succinct proofs of correctness. However, existing constructions rely on cryptographic hash functions that are expensive to represent in arithmetic constraint systems, resulting in high proving costs. We propose a constraint-efficient alternative: a map-to-elliptic-curve-group relation that bypasses the need for cryptographic hash functions and can serve as a drop-in replacement for hash-to-curve constructions in practical settings, including the aforementioned applications. Our relation naturally supports non-deterministic map-to-curve choices making them more efficient in constraint programming frameworks and enabling efficient integration into zero-knowledge proofs. We formally analyze the security of our approach in the elliptic curve generic group model (EC-GGM). Our implementation in Noir/Barretenberg demonstrates the efficiency of our construction in constraint programming: it achieves over 20x fewer constraints than the best hash-to-elliptic-curve-group alternatives, and enables 50-100x faster proving times at scale.
• Bio: Harjasleen (Jasleen) Malvai is a final-year PhD student at UIUC, working with Prof. Andrew Miller. At the moment, she is visiting Prof. Babis Papamanthou at Yale. Her research develops the cryptographic and systems foundations for verifiable and privacy-preserving identity infrastructure. She designs protocols and proofs that make large-scale transparency and accountability possible without compromising privacy—both drawing on and advancing tools such as authenticated data structures, memory checking, and zero-knowledge proofs. Her approach combines traditional applied cryptography with decentralized systems, using tools such as SNARKs and MPC to design protocols that are both rigorous and deployable.  Her work spans both theory and practice, from lower bounds for authenticated dictionaries to deployed systems such as Parakeet (used by WhatsApp, awarded the IETF Applied Networking Research Prize), and CanDID,whose component DECO protocol was acquired by Chainlink Labs.
• Livestream: https://yale.zoom.us/j/92019907023?pwd=bBhXvpxbOvVW6zUzoPqJclrpFIeFcz.1
• More: For additional details about the talk, see our website: https://yacl.cs.yale.edu