Math & Engineering

Hyrax commitments are introduced in WTS⁺17. They are a polynomial commitment scheme designed for multi-linear extenstions (MLEs). Given a finite multi-variate basis B=B 1 ​ ×B 2 ​ ×⋯×B n ​ with B i ​ ⊂F and a sum of the form b∈B ∑ ​ g(b)⋅ k∈[n] ∏ ​ e k ​ (b k ​ ) where g:F n →F and e k ​ :F→F are arbitrary and b k ​ denotes the k-th component of b. Given any binary partitioning [n]=A∪B we can rewrite this as a∈B A ​ ∑ ​ b∈B B ​ ∑ ​ g(a,b)⋅( k∈A ∏ ​ e k ​ (a k ​ ))⋅( k∈B ∏ ​ e k ​ (b k ​ )) Observe that the products only depend on a and b respectively. Since B A ​ and B B ​ are finite we can enumerate their values as {a i ​ }=B A ​ and {b j ​ }=B B ​ and define g ij ​ ​ =g(a i ​ ,b j ​ ) ​ u i ​ ​ = k∈A ∏ ​ e k ​ ((a i ​ ) k ​ ) ​ v j ​ ​ = k∈B ∏ ​ e k ​ ((b j ​ ) k ​ ) ​ we can then rewrite the sum as a vector-matrix-vector product, also known as a rank-2 tensor contraction i∈[∣B A ​ ∣] ∑

Hyrax Commitments \gdef\p#1{\left({#1}\right)} \gdef\vec#1{\mathbf{#1}} \gdef\eq{\mathrm{eq}} \gdef\setn#1{\mathcal #1} Hyrax commitments are introduced in WTS⁺17 . They are a polynomial commitment scheme designed for multi-linear extenstions (MLEs). Certain Multivariate Sums as Tensor Contractions Given a finite multi-variate basis \setn B = \setn B_1 × \setn B_2 × ⋯ × \setn B_n with \setn B_i ⊂ 𝔽 and a sum of the form \sum_{\vec b ∈ \setn B} g(\vec b) ⋅ \prod_{k ∈ [n]} e_k(b_k) where g : 𝔽^n → 𝔽 and e_k: 𝔽 → 𝔽 are arbitrary and b_k denotes the k -th component of \vec b . Given any binar

related reading

• The Polynomial Commitment - notes.0xparc.orgnotes.0xparc.org
• Binius: highly efficient proofs over binary fieldsvitalik.eth.limo
• Commitment scheme - Wikipediaen.wikipedia.org
• Inner Product Arguments · Dankrad Feistdankradfeist.de
• KZG polynomial commitments · Dankrad Feistdankradfeist.de
• Pedersen Commitments, Divide-and-Conquer, and the Inner Product Argument - notes.0xparc.orgnotes.0xparc.org
• Applied Crypto #2: Polynomial Commitments | ZK Learning Resourceslearn.0xparc.org
• Explaining Halo 2 - Electric Coin Companyelectriccoin.co
• The Spartan zkSNARK framework - Alin Tomescualinush.github.io
• ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
• Pearl Whitepaperpearlresearch.ai
• 17 misconceptions about SNARKs - a16z cryptoa16zcrypto.com