ผู้เขียนข้อความต้นฉบับ: Kang Shuiyue ซีอีโอของ Fox Tech และ Meng Xuanji หัวหน้านักวิทยาศาสตร์ของ Fox Tech

ผู้เขียนข้อความต้นฉบับ: Kang Shuiyue ซีอีโอของ Fox Tech และ Meng Xuanji หัวหน้านักวิทยาศาสตร์ของ Fox Tech

ด้วยการแพร่กระจายของแนวคิดเช่น Bitcoin, blockchain และสัญญาอัจฉริยะ ผู้คนจำนวนมากขึ้นให้ความสนใจกับการพัฒนาที่แข็งแกร่งของฟิลด์ Web3 ในแง่ของเทคโนโลยี นักพัฒนาจำนวนมากยังให้ความสนใจกับโปรโตคอลการเข้ารหัสที่รองรับบล็อกเชนพื้นฐาน ในบรรดาโปรโตคอลเหล่านั้น โปรโตคอลที่พิสูจน์ความรู้เป็นศูนย์นั้นมีลักษณะเฉพาะที่โดดเด่น และมีบทบาทสำคัญในการตระหนักถึงการปกป้องความเป็นส่วนตัวและในโครงการ zkrollup ที่ขยายประสิทธิภาพการทำงานของเลเยอร์ 2

Zero-knowledge Proof เป็นคำทั่วไปสำหรับอัลกอริทึมประเภทหนึ่ง จนถึงตอนนี้ นักวิจัยได้คิดค้นโปรโตคอลมากมาย เช่น Plonk, Groth 16, zkStark, Virgo, Orion, Foaks เป็นต้น โปรโตคอลที่แตกต่างกันเหมาะสำหรับสถานการณ์การคำนวณที่แตกต่างกันและความซับซ้อนและประสิทธิภาพก็แตกต่างกันเช่นกัน ตัวอย่างเช่น Foaks มีข้อได้เปรียบของเวลาในการพิสูจน์เชิงเส้นและความยาวในการพิสูจน์ที่น้อย

โปรโตคอลนี้ยังมีบทบาทสำคัญในระบบพิสูจน์ Foaks ที่ Fox Tech นำมาใช้ โดยเฉพาะอย่างยิ่ง เพื่อพิสูจน์ความถูกต้องของ opcode จะต้องแปลงเป็นวงจรเลขคณิตก่อน แล้วจึงแปลงเป็นเมทริกซ์ และสุดท้ายสร้างพหุนาม ใช้อัลกอริทึมในระบบการพิสูจน์กับพหุนาม และสุดท้ายบีบอัด ส่วนหนึ่งของการพิสูจน์ ในหมู่พวกเขา กระบวนการโต้ตอบระหว่างผู้พิสูจน์ (Prover) และผู้ตรวจสอบ (Verifier) ​​จะถูกแปลงเป็นกระบวนการคำนวณผลรวมที่แน่นอน นั่นคือ กระบวนการของโปรโตคอลการตรวจสอบผลรวม

ชื่อระดับแรก

Sum-check Protocol

ชื่อเรื่องรอง

1. วัตถุประสงค์ของพิธีสาร

เป้าหมายของโปรโตคอลนั้นเรียบง่ายและเข้าใจง่าย

คล้ายกับสถานการณ์ "การคำนวณจากภายนอก" ที่พิจารณาใน zkRollup ในแอปพลิเคชัน จำนวนการคำนวณของสูตรข้างต้นจะสูงมาก เราหวังว่าจะมอบการคำนวณสูตรนี้ให้กับผู้พิสูจน์ (Prover) จากนั้นผู้พิสูจน์จะ รายงานต่อผู้ตรวจสอบ (Verifier) ​​เพื่อพิสูจน์ว่าผลการคำนวณถูกต้อง

ชื่อเรื่องรอง

2. ข้อสันนิษฐานของพิธีสาร

ก่อนอื่น จำเป็นต้องชี้แจงความสามารถของตัวตรวจสอบในโปรโตคอลนี้ เราถือว่าผู้ตรวจสอบมีออราเคิล (Oracle) ที่สามารถคำนวณฟังก์ชัน g นั่นคือ มันง่ายสำหรับผู้ตรวจสอบที่จะคำนวณ g(r 1, ... , rv) หลังจากกำหนดอินพุต r 1, ... , rv แต่การคำนวณผลลัพธ์ทั้งหมด H เป็นเรื่องยาก

ประเด็นที่สอง เกี่ยวกับเป้าหมายของโปรโตคอล ที่จริงแล้ว โปรโตคอลการตรวจสอบผลรวมสามารถคำนวณ bBmg(b) สำหรับชุด B ใดๆ ก็ได้ แต่โดยไม่สูญเสียลักษณะทั่วไป เราถือว่า B={0, 1}

ชื่อเรื่องรอง

3. กระบวนการโปรโตคอล

ข้อตกลงมีทั้งหมด v รอบ หนึ่งตัวแปรในหน่วย g ได้รับการประมวลผลในแต่ละรอบ

รอบที่ 1:

หากผู้พิสูจน์มีความซื่อสัตย์ ควรกำหนด H=g 1( 0)+g 1( 1) ผู้ตรวจสอบจะตรวจสอบและหากผ่าน หมายเลขสุ่ม r 1 จะถูกเลือกและส่งไปยังผู้รับรอง โปรดทราบว่าตามสมมติฐานของโปรโตคอล ผู้พิสูจน์สามารถทำการตรวจสอบข้างต้นให้เสร็จสมบูรณ์ได้

เราใช้ degi(p) เพื่อแสดงระดับของตัวแปร ith ในพหุนามหลายตัวแปร p ดีกรีของ g 1(X 1) คือ deg 1(g) ดังนั้นเราจึงรู้ว่า g 1 สามารถแทนด้วย deg 1(g)+ 1 องค์ประกอบของโดเมน

รอบ j (j>1):

รอบ วี:

คำอธิบายภาพ

• รูปที่ 2: โปรโตคอลการตรวจสอบผลรวมของ Foaks

• ความครบถ้วนสมบูรณ์: หากผู้พิสูจน์มีพยานที่ถูกต้อง ผู้ตรวจสอบจะยอมรับการพิสูจน์ด้วยความน่าจะเป็นไม่ต่ำกว่า (1-negl(n))

• ความถูกต้อง: หากผู้พิสูจน์ไม่มีพยานที่ถูกต้อง ผู้ตรวจสอบจะปฏิเสธการพิสูจน์ที่มีความเป็นไปได้ต่ำกว่า negl(n)

• ความรวบรัด: ขนาดของหลักฐานต้องเล็กกว่าขนาดของพยานมาก

# โดยที่ negl(n) คือฟังก์ชันเล็กน้อยใดๆ

ชื่อเรื่องรอง

4. ความซับซ้อนของโปรโตคอล

ตารางต่อไปนี้แสดงผลลัพธ์ของความซับซ้อนอย่างละเอียด โดยที่ T แสดงถึงโอเวอร์เฮดที่จำเป็นในการเข้าถึงออราเคิล (Oracle) นั่นคือ การประเมิน g หนึ่งครั้ง

รูปที่ 3: ความซับซ้อนของโปรโตคอลการตรวจสอบผลรวม

ชื่อระดับแรก

การประยุกต์ใช้โปรโตคอลการตรวจสอบผลรวม

ในบรรดาอัลกอริธึมการพิสูจน์ความรู้เป็นศูนย์ โปรโตคอลการตรวจสอบผลรวมกำลังมีบทบาทสำคัญ การพิสูจน์ปัญหาต่างๆ อาศัยการแปลงปัญหาเดิมเป็นแบบฟอร์มการตรวจสอบผลรวม จากนั้นจึงดำเนินการตามขั้นตอนที่ตามมาให้เสร็จสิ้น

ตัวอย่างเช่น สามารถใช้โปรโตคอลการตรวจสอบผลรวมเพื่อนับจำนวนสามเหลี่ยมในกราฟที่ไม่มีทิศทาง

อันดับแรก เราใช้เมทริกซ์คำคุณศัพท์ A แทนกราฟที่ไม่มีทิศทาง G ให้ E เป็นเซตขอบของมัน จากนั้น Ai, j= 1(i, j)E กล่าวคือ ถ้ามีขอบระหว่างจุด i, j จากนั้น Ai, j = 1 มิฉะนั้น 0 สำหรับจุด i, j, k เงื่อนไขสำหรับสามจุดในการสร้างรูปสามเหลี่ยมคือ Ai, j= 1, Ai, k= 1, Aj, k= 1

นอกจากนี้ ในระบบพิสูจน์หลายระบบ โปรโตคอลการตรวจสอบผลรวมยังใช้เป็นตรรกะพื้นฐานสำหรับการก่อสร้าง ภาพด้านล่างแสดงระบบการพิสูจน์ที่แตกต่างกันตามการเปลี่ยนแปลงที่แตกต่างกันตามการตรวจสอบผลรวม

รูปที่ 4: การประยุกต์ใช้โปรโตคอล Sum-check ในระบบพิสูจน์อักษร 4 ประเภท

ชื่อระดับแรก

บทส่งท้าย

บทส่งท้าย

ชื่อระดับแรก

อ้างอิง

1. [LFKN 92 ] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39: 859 – 868, October 1992.

2. https://people.cs.georgetown.edu/jthaler/sumcheck.pdf

3. https://zkproof.org/2020/03/16/sum-checkprotocol/

4. https://eprint.iacr.org/2021/333.pdf

5. อ้างอิงhttps://blog.csdn.net/mutourend/article/details/111610754