Lagrange Interpolation을 통한 n개 데이터 포인트의 단일 다항식 변환 및 ZK Proof 응용

Context

기존의 System of Equations 방식은 데이터 포인트 증가에 따라 계산 복잡도가 선형적으로 증가하는 한계 존재. n개의 포인트를 만족하는 다항식을 찾기 위해 반복적인 연립 방정식 풀이가 필요하여 연산 효율성이 저하되는 문제 발생.

Technical Solution

• 각 데이터 포인트 $x_i$에 대해 해당 지점에서만 1이고 나머지 모든 지점에서 0이 되는 Basis Polynomials 설계
• 특정 $x$값에서 0을 만들기 위해 $(x - x_j)$ 항들의 곱으로 구성된 분자 설계
• 해당 $x_i$ 지점에서의 결과값을 1로 정규화하기 위한 분모 값의 나누기 연산 적용
• 각 Basis Polynomial에 실제 $y$값을 가중치로 곱한 뒤 모두 합산하는 Weighted Sum 구조 채택
• 연립 방정식 풀이 과정 없이 주어진 포인트들을 직접 다항식으로 변환하는 Direct Mapping 로직 구현
• 데이터 포인트의 미세한 변경이 전체 다항식에 영향을 주는 고감도 특성을 활용하여 Computation Encoding 구현