Home

tl;dr: A quadratic arithmetic program (QAP), a Rank-1 Constraint System (R1CS), and an NP relation are equivalent ways of representing a hard problem (or computation) whose solution can be verified in polynomial-time. In particular, R1CS is just a reformulation of QAPs as linear equations and, these days, it is used widely when formalizing compu...

tl;dr: A zero-knowledge proof (ZKP) system for an NP relation $R$ allows a prover, who has a statement $\mathbf{x}$ and a witness $\mathbf{w}$ to convince a verifier, who only has the statement $\mathbf{x}$, that $R(\mathbf{x}; \mathbf{w}) = 1$. Importantly, the proof leaks nothing about the secret witness $\mathbf{w}$. (e.g., a ZKP can be used...

tl;dr: An NP relation $R(\mathbf{x}; \mathbf{w})$ is a formalization of an algorithm $R$ that verifies a solution $\mathbf{w}$ to a problem $\mathbf{x}$ (in time $\poly(|\mathbf{x}|+|\mathbf{w}|)$. For example, $\mathsf{Sudoku}(\mathbf{x}; \mathbf{w})$ verifies if $\mathbf{w}$ is a valid solution to the Sudoku puzzle $\mathbf{x}$. NP relations a...

tl;dr: We cover a few basic linear algebra concepts: vectors, matrices, matrix-vector products, vector dot products, Haddamard products, etc.

tl;dr: Do you want to sign (committed) field elements without relying on random oracles? Do you want to efficiently prove (in zero-knowledge) relations over your signed messages? BBS+ is here to help you! The BBS+ signature scheme is a transformation[^ASM08e] of the the Boneh-Boyen-Shacham (BBS) group signature scheme[^BBS04] into a standalone...

tl;dr: We spoke about how a blockchain should keep a secret at the Next-Generation Secure Distributed Computing seminar at Schloss Dagstuhl. We sketched an approach based on trusted execution environments (TEEs) that could be practical, yet could still present interesting research challenges.

$ \def\prove{\mathsf{Prove}} \def\ver{\mathsf{Ver}} \def\A{\mathbf{A}} \def\B{\mathbf{B}} \def\bb{\mathbf{b}} $ tl;dr: This is a post-mortem write-up on how I failed to use the Bulletproofs IPA to convince a verifier that a multi-exponentiation $\A^\bb = \prod_i (A_i)^{b_i}$ was done correctly. The problem is that the Bulletproof verifier has t...

tl;dr: What is a keyless blockchain account? Put simply, “Your blockchain account = Your Google account”. In other words, this keyless approach allows you to derive a blockchain account from any of your existing OpenID Connect (OIDC) account (e.g., Google, Apple), rather than from a traditional secret key or mnemonic. There are no long-term se...