Tham gia Đăng nhập
Điểm:1
avatar Crypto

zkSnark: Chuyển đổi R1CS thành QAP

lá cờ et
user93353

Tôi đang đọc qua trang của Vitalin Buterin trên R1CS & QAP - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Tôi hiểu đến phần mà anh ấy nhận được

$A=\begin{pmatrix} 0&1&0&0&0&0 \ 0&0&0&1&0&0 \ 0&1&0&0&1&0 \ 5&0&0&0&0&1 \ \end{pmatrix}$

$B=\begin{pmatrix} 0&1&0&0&0&0 \ 0&1&0&0&0&0 \ 1&0&0&0&0&0 \ 1&0&0&0&0&0 \ \end{pmatrix}$

$C=\begin{pmatrix} 0&0&0&1&0&0 \ 0&0&0&0&1&0 \ 0&0&0&0&0&1 \ 0&0&1&0&0&0 \ \end{pmatrix}$

Bây giờ, khi anh ấy chuyển đổi R1CS thành QAP, anh ấy viết

Nghĩa là, nếu chúng ta đánh giá các đa thức tại x=1, thì chúng ta sẽ nhận được tập hợp vectơ đầu tiên, nếu chúng ta đánh giá các đa thức tại x=2, thì chúng ta sẽ nhận được tập hợp vectơ thứ hai, v.v.

Các tập hợp ban đầu của vectơ A, B & C hoàn toàn không được tạo bởi bất kỳ x=1, x=2 nào, v.v. Chúng có ánh xạ

$['~one', 'x', '~out', 'sym\_1', 'y', 'sym\_2'] = [ 1, 3, 35, 9, 27, 30]$

tức là chúng được tính toán bằng cách sử dụng $x = 3$ (là nghiệm của đa thức $x^3 + x + 5 = 35$)

Vì vậy, tôi không hiểu làm thế nào anh ấy đánh đồng những thứ đó với việc lấy mẫu tại x=1, x=2, v.v.

Ai đó có thể giải thích?

105
0 + 0
Điểm:1
Ievgeni avatar Crypto
lá cờ cn
Ievgeni

Đầu tiên, điều quan trọng là phải hiểu, có bao nhiêu thông tin trong một đa thức bậc $d$ có thể chứa Nó được đặc trưng bởi $d+1$ hình ảnh (nghĩ đến đa thức Lagrange để hiểu tại sao).

Vì vậy, bây giờ chúng ta phải tập trung vào một câu cụ thể trong liên kết bạn đã viết: "Chúng tôi đi từ bốn nhóm ba vectơ có độ dài sáu đến sáu nhóm ba đa thức bậc 3, trong đó việc đánh giá các đa thức tại mỗi tọa độ x đại diện cho một trong các ràng buộc.".

Nó ngụ ý rằng mỗi nhóm tương ứng với ảnh của các đa thức cho một giá trị cụ thể. (Bởi vì chúng tôi tùy ý quyết định diễn giải nó như thế này) Có vẻ như quy ước là xem xét rằng $i^\text{th}$ nhóm cung cấp cho chúng tôi hình ảnh cho đầu vào $i$.

Ví dụ, nếu tôi muốn tính đa thức đầu tiên $P_{1,1}$ của vectơ đầu tiên. tôi sẽ tính toán $P_{1,1}$ tối đa bằng cấp $3$ như vậy mà $P_{1,1}(1)= x_1, P_{1,1}(2) = x_2, P_{1,1}(3) = x_3, P_{1,1}(4)=x_4$, với $x_i$ tọa độ đầu tiên của vectơ đầu tiên của $i^{\text{th}}$ tập đoàn.

Các phương trình này chỉ xác định một đa thức (tôi không chắc có thể giải thích tốt hơn phương trình trong liên kết của bạn), nhưng nếu bạn muốn có thêm kiến ​​​​thức về điều này, bạn có thể đọc: https://en.wikipedia.org/wiki/Lagrange_polynomial

Tổng quát hơn, chúng ta có thể làm tương tự để tính $j^{\text{th}}$ đa thức $P_{j,k}$ sau đó $k^{\text{th}}$ véc tơ, bằng cách nhìn $k^{\text{th}}$ tọa độ của $j^{\text{th}}$ vectơ của các nhóm.

0 + 0
lá cờ et
user93353
Tôi biết (n+1) điểm xác định & đa thức bậc n. Nội suy Lagrange dùng để tìm đa thức bậc n khi biết n+1 điểm trên đa thức. Tuy nhiên, ở đây chúng ta đã biết đa thức - $x^3 + x -30$ - vì vậy tôi không thể hiểu chính xác tại sao chúng ta lại sử dụng phép nội suy Lagrange?
0
Hồi đáp
lá cờ et
user93353
Tôi biết $L_i(x)= \prod_{j=0}^n \frac {x-x_j} {x_i - x_j}$ & $P_n(x) = \sum_{i=0}^n L_i(x) y_i$. Tuy nhiên, tôi không thể liên kết nó với các ký hiệu bạn sử dụng - $P_{j,k}(1)$ & $P_{j,k}(2)$ - (1) & (2) ở đây là gì - là nó P(x=1) & P(x=2) & $P_{j,k}$ là gì?
0
Hồi đáp
Ievgeni avatar
lá cờ cn
Ievgeni
tọa độ $j^{\text{th}}$ của vectơ $k^{\text{th}}$
0
Hồi đáp
lá cờ et
user93353
Nội suy Lagrange dùng để tìm đa thức bậc n khi biết n+1 điểm trên đa thức. Tuy nhiên, ở đây chúng ta đã biết đa thức - x3+xâ30 - vì vậy tôi không thể hiểu chính xác tại sao chúng ta lại sử dụng phép nội suy Lagrange?
0
Hồi đáp
Ievgeni avatar
lá cờ cn
Ievgeni
Tôi đang nói về đa thức trong câu này ""Chúng ta đi từ bốn nhóm ba vectơ độ dài sáu đến sáu nhóm ba đa thức bậc 3".
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.