Efficient Inner-Product Argument from Compressed $$\Sigma $$-Protocols and Applications

The Inner-Product Argument (IPA) is a subroutine of well-known zero-knowledge proof systems, such as Bulletproofs and Halo. These proof systems are then applied in large cryptographc protocols for anonymous and private transactions in the public blockchain. Despite its trustless nature and logarithmic communication efficiency, IPA suffers from low computational efficiency. While not specifically aimed at optimizing the IPA, Attema et al. propose the compressed Sigma-protocol theory. Their intuition is simple: the prover provides an argument for a single committed vector to the verifier, whose commitment satisfies an arbitrary linear relation. We follow this intuition, but instead we provide an argument for two vectors committed under a single compact commitment, satisfying a linear form that is the inner-product relation. Hence, we propose the compressed Sigma-protocol version of the original IPA, namely the compressed Sigma-Inner-Product Argument (Sigma-IPA). To this end, we prove security and provide a Sigma-IPA that is complete and has soundness in standard DLOG setting. Finally, we conduct an efficiency analysis showing that our IPA reduces the computational complexity of prover and verifier algorithms by a factor of 2 compared to the original IPA.