Lagrange Polynomial
Polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset. Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data.
Definition
The Lagrange interpolating polynomial for nodes is the linear combination:
Where is Langrange basis (polynomial):
As mentioned above the interpolating polynomial is unique 1. This characteristic allows uses in cryptography such as: Shamir's secret sharing scheme and KZG polynomial 2 commitments (Kate commitment) [https://en.m.wikipedia.org/wiki/Lagrange_polynomial] 1 *[https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf] 2
Uses
Vector commitment and Verkle Tries
A commitment scheme allows one to commit to a chosen value (or statement) while keeping it hidden to others, with the ability to reveal the committed value later [https://en.m.wikipedia.org/wiki/Commitment_scheme].
A vector commitment allows to commit to an ordered sequences of values in such a way that is later possible to open the commitment only with the reference to a specific position. [https://eprint.iacr.org/2011/495.pdf], (Catalano, Fiore).
In Verkle Tree 3,4, the commitment method is called vector commitment. In practice, it is used a more poweful, efficient and simplest method than a vector commitment, called polynomial commitment. Polynomial commitments let you hash and evaluate in any point the hashed polynomial (the polynomial can be found-defined with Lagrange interpolation). The two polynomial commitment schemes easiest to be used are: KZG and bulletprof-style commitments [https://vitalik.ca/general/2021/06/18/verkle.html] 3, [https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf] 4.
KZG commitments
The Kate commitment scheme is designed as a polynomial commitment, where it also allows a vector commitment. A vector commitment commits to a vector and lets you prove that you committed to for some . This could be reproduced using the Kate commitment scheme, which is a polynomial where for all , . This polynomial could be computed using Lagrange interpolation. [https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html].
Pedersen vector commitment
"It is shown how to distribute a secret to n persons such that each person can verify that he has received correct information about the secret without talking with other persons. Any of these persons can later find the secret , whereas fewer than persons get no information about the secret." [https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf]. (Torben Pryds Pedersen)
Here you will find, that all verification of shares and the scheme are based in Lagrange Polynomial (section 4).