Điểm mấu chốt là họ đang sử dụng một mạch phổ quát ở đó:
Khi chúng tôi xây dựng một SNARK cho mạch SAT, chúng tôi sử dụng một QSP cho một phổ mạch, có kích thước $O(|C| \log |C|)$ ở đâu $|C|$ là kích thước tối đa của các mạch trong bài toán thỏa mãn.
Một mạch phổ quát là một mạch có thể tính toán bất kỳ mạch nào khác. Sự khái quát hóa này chính là nơi mà yếu tố logarit bổ sung xuất hiện. Điều này được giải thích ở phần đầu của phần 3:
Để so sánh trực tiếp với Groth, chúng ta có thể xử lý $u$ là một mạch được chọn thích ứng bằng cách xây dựng $R$ [(một quan hệ)] từ một
mạch vạn năng. Trong trường hợp này, kích thước của tính toán mạch $R$ có thể lớn hơn
hơn $|u|$ bởi một hệ số logarit, tương ứng làm tăng kích thước CRS và tính toán tục ngữ lên $\tilde{O}(|u|)$. Nếu $u$ ... có thể được chọn không thích ứng, sơ đồ của chúng tôi trở nên hiệu quả hơn.
Các $\tilde{O}$ ký hiệu ẩn thừa số logarit. Cuối cùng, họ đề cập rằng biết mạch cụ thể $u$ sẽ hiệu quả hơn - đây là những gì bạn có trong tâm trí. Lý do cho tính đúng đắn thích ứng là vì điều này mô hình hóa chính xác hơn cách giao thức có thể sẽ được sử dụng trong các tình huống thực tế - thường thì bạn sẽ mong đợi người chứng minh xem CRS trước khi bắt đầu bằng chứng của họ, vì vậy họ có thể chọn tuyên bố của họ (có lẽ sai) cố gắng chứng minh dựa trên CRS (thích nghi).
Tờ giấy này giải thích cách xây dựng mạch phổ thông hiệu quả và đưa ra giải thích về cách thức hoạt động của các mạch như vậy trong phần sơ bộ (ví dụ: xem trang 4-7). Theo trực giác, hệ số logarit được đưa ra bởi vì các mạch này có xu hướng được xây dựng theo cách đệ quy, với mỗi bài toán con có kích thước gần bằng một nửa, vì vậy chúng ta có hệ số logarit thông thường khi xử lý cây nhị phân. Để giải thích rõ hơn, tôi nghĩ rằng bản thân bài báo là thứ tốt nhất để đọc.
