Raju Krishnamoorthy

@notnotraju

Joined on Jun 9, 2023

  • Thanks to Yi Sun and Jonathan Wang for the Axiom open source program and for substantial help with halo2 and halo2-lib, and to M.S. Krishnamoorthy for many helpful discussions about polynomial commitment schemes in general and IPA in particular. This document was written as part of the Axiom open source program. It contains a detailed explanation/description of a particular polynomial commitment scheme, the "Inner Product Argument", as well as notes on the implementation of a "circuit" (in the sense of Plonkish arithmetization) to verify batch IPA proofs. Motivation As part of the Axiom open source program, I planned to write a circuit to verify membership proofs in a Verkle trie. Verkle tries are a data structure to commit to a dictionary (i.e., a store of key-value pairs), and they have been proposed as a replacement to Merkle Patricia tries for storing state in Ethereum (BF21, But21a, Fei21a). The basic model, a Verkle tree, was invented by J. Kuszmaul in 2018. Verkle trees require an underlying vector commitment scheme. For reasons we indicate below, inner product arguments (IPA) have been proposed as the vector commitment scheme for the Verkle trie to store state. One of these reasons is that IPA, like other linear vector commitment schemes, permits batch proofs. IPA has found several other uses: they are being used currently in zcash and in the backend of the Halo2 proving system. With this in mind, my first goal was to write a circuit that verified a batch IPA proof.
     Like 1 Bookmark