ความหมายของความพึงพอใจของวงจรในบริบทของ zk-SNARK

ทฤษฎีบทมาตรฐานคือความพึงพอใจของวงจรบูลีนคือ NP-complete (แสดงใน ซีแอลอาร์เอส, ตัวอย่างเช่น).

ฉันสนใจว่าข้อความเหล่านี้มีความหมายอย่างเป็นทางการอย่างไร จาก CLRS ฉันสามารถอ้างอิงได้

$$\text{CIRCUIT-SAT} = \{C \mid \text{$C$ เป็นวงจรรวมบูลีนที่น่าพอใจ}\}$$

ใน Bitansky และคณะ, ความพึงพอใจของวงจรบูลีนใช้เพื่อจับข้อความที่จะพิสูจน์ อย่างไรก็ตาม นี่ไม่ใช่ CIRCUIT-SAT: Bitansky และคณะ พิจารณาความพอใจของวงจร $C$ สำหรับ หนึ่ง ป้อนข้อมูล $x$. CIRCUIT-SAT อธิบายถึงความพึงพอใจของวงจรเท่านั้น $C$ สำหรับ ใดๆ ป้อนข้อมูล $x$.

zk-SNARK พิสูจน์ข้อความ $x \ใน L$ สำหรับ $L \ใน NP$. สิ่งที่ทำเพื่อสร้าง zk-SNARK สำหรับความพึงพอใจของวงจรบูลีนคือการลด $L$ ไปยังวงจรบูลีน $C$ ดังนั้น $C$ เป็นที่น่าพอใจ สำหรับการป้อนข้อมูล $x$ ถ้า $x \ใน L$. $C$ โมเดล $L$เพื่อที่จะพูด

ฉันสับสนที่มีคนพูดว่าวงจรบูลีน (หรือเลขคณิต) นั้นสมบูรณ์ NP ตามที่ผมเข้าใจคือ $L$ จำเป็นต้องสร้างแบบจำลองโดยวงจร $C$. แต่ถ้าว่ากันตามนิยามของ CIRCUIT-SAT $x$ จะต้องแปลงเป็นวงจร $C$. CIRCUIT-SAT สำหรับ zk-SNARK ควรมีลักษณะอย่างไร

$$\text{CIRCUIT-SAT} = \{ (C, x) \mid \text{$C$ เป็นวงจรรวมบูลีนที่น่าพอใจสำหรับอินพุต $x$}\}$$

เราอยากได้วงจร ต่อภาษาไม่ใช่ต่ออินพุต

ดังนั้น เมื่อมีคนพูดว่าความน่าพึงพอใจของวงจร R1CS, QSPs หรือ QAPs นั้นเป็น NP-complete ในบริบทของ zk-SNARK พวกเขาหมายถึงคำจำกัดความของฉันเกี่ยวกับ CIRCUIT-SAT และคำที่คล้ายกันหรือไม่

สมมติ $L$ เป็นภาษา NP และอัลกอริธึมการตรวจสอบพยานคือ $R$, ดังนั้น $L = \{ x \กลาง \มีอยู่ w : R(x,w) = 1 \}$.

นี่คือวิธีที่ฉันจะพิสูจน์ให้คุณเห็น $x \ใน L$:

• สร้างวงจร $C$ ดังนั้น $C(w) = R(x,w)$. เราทั้งสองสามารถทำเช่นนี้ได้เพราะ $R$ เป็นอัลกอริธึมสาธารณะและ $x$ เป็นสาธารณะด้วย วงจรนี้ $C$ มีตัวอย่าง $x$ "รหัสตายตัว" ลงไป เพื่อให้ป้อนข้อมูลที่เป็นทางการเท่านั้น $w$.

• ทำให้คุณเชื่อได้ว่าวงจร $C$ เป็นที่พอใจ - นั่นคือมีอินพุต $w$ นั่นเป็นสาเหตุ $C$ ออก 1.

กล่าวอีกนัยหนึ่งฉันแค่ต้องโน้มน้าวใจคุณบ้าง $C$ อยู่ใน CIRCUIT-SAT