zkSNARKS - không thể hiểu cách sử dụng đa thức để xác minh một số điều kiện

Từ Blogpost của Vitalik Buterin - Giới thiệu gần đúng về cách có thể có zk-SNARK

Từ chủ đề con "So sánh đa thức với chính nó", tôi đã hiểu cho đến đây

Nói cách khác, bất kỳ đa thức nào bằng 0 trên một số tập hợp là một (đa thức) bội số của đa thức đơn giản nhất (bậc thấp nhất) mà bằng 0 trên cùng tập hợp đó.

Tuy nhiên, tôi không thể tìm ra cách anh ta sử dụng điều đó để xác minh một số điều kiện.

Đây là phần tôi không hiểu

nếu chúng ta có một đa thức mã hóa các số Fibonacci (vì vậy trên $F(x+2) = F(x) + F(x+1)$ băng qua $x = $ { $0, 1, ..., 98$}), thì tôi có thể thuyết phục bạn rằng $F$ thực sự thỏa mãn điều kiện này bằng cách chứng minh rằng đa thức $P(x) = F(x+2) - F(x+1) - F(x)$ bằng 0 trên phạm vi đó, bằng cách cho bạn thương số $H(x) = \frac {F(x+2) - F(x+1) - F(x)}{Z(x)}$ ở đâu $Z(x) = (x - 0) * (x - 1) ... (x - 98)$

Trước hết, tôi không hiểu ý của anh ấy khi "cung cấp cho bạn thương số" - chính xác thì anh ấy sẽ cung cấp cho người xác minh cái gì & người xác minh sẽ xác minh điều đó như thế nào?

Nếu một đa thức $P(x)$ (nghĩ về nó như một chức năng chấp nhận đầu vào $x$ và trả về kết quả đánh giá) đánh giá bằng 0 đối với các giá trị đầu vào nhất định cho $x$ (một ví dụ rất đơn giản có thể là $x=x_1, x_2, x_3$), thì như đã nêu trong đoạn văn được trích dẫn đầu tiên trong câu hỏi, $P(x)$ sẽ là bội số của đa thức bậc thấp nhất $Z(x)$ đó là số không trên các giá trị đầu vào cho $x$ (ở đây nó sẽ là $Z(x)=(x-x_1)(x-x_2)(x-x_3)$). Điều này có nghĩa là nếu $P(x)$ được chia cho $Z(x)$, thương (gọi là $H(x)$) vẫn là một đa thức. Người tục ngữ tính toán $H(x)$ bằng cách thực sự thực hiện phân chia, cụ thể là $P(x)/Z(x)$, và điều này $H(x)$ được gửi từ Người chứng minh đến Người xác minh dưới dạng âBằng chứngâ. Sau đó, Chuyên gia Xác minh xác nhận rằng sản phẩm của $H(x)$ và $Z(x)$ thực sự bằng $P(x)$, và nếu vậy Người xác minh chấp nhận bằng chứng. Chuyên gia Xác minh cũng cần xác nhận rằng $H(x)$ thực sự là một đa thức chứ không phải một loại hàm nào khác (ví dụ: nó không phải là một hàm hữu tỷ, là một phân số không tầm thường với tử số và mẫu số của đa thức). Trên thực tế, điều này được xác nhận khá nhiều theo mặc định do cách Prover giao tiếp hoặc tính toán $H(x)$. Ví dụ: nếu giao thức yêu cầu Prover gửi các hệ số của $H(x)$, thì hiển nhiên nó là một đa thức. Hoặc, nếu giao thức yêu cầu Prover tính toán $H(r)$ cho một giá trị bí mật $r$ (điều đó có nghĩa là $H(x)$ được đánh giá tại $x=r$), sau đó sẽ có âChuỗi tham chiếu chungâ được cung cấp cho Trình xác minh bao gồm mã hóa (ví dụ: theo số mũ của trình tạo nhóm trong nhóm thân thiện ghép đôi) lũy thừa của $r$ lên đến công suất cao nhất (ví dụ: ${g^{r}, g^{r^2}, g^{r^3}, g^{r^4}, g^{r^5}}$), vì vậy Prover buộc phải chỉ đề xuất một đa thức $H(x)$ (đánh giá tại $x=r$) với bậc lên tới lũy thừa cao nhất đó (trong ví dụ đơn giản này là 5).