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

คำนำ: หากนักเข้ารหัสไม่พบความเชื่อมโยงระหว่างผลิตภัณฑ์ Tensor และค่าโพลิโนเมียล ก็จะยากที่โปรโตคอลการผูกมัดพหุนาม Brakedown จะปรากฏขึ้น และจะเป็นไปไม่ได้ที่จะสร้างสิ่งใหม่ เช่น Orion และ FOAKS ที่ใช้เบรกดาวน์ อัลกอริทึมที่รวดเร็ว

ในระบบพิสูจน์ความรู้เป็นศูนย์จำนวนมากที่อาศัยการผูกมัดแบบพหุนาม จะใช้โปรโตคอลการผูกมัดที่แตกต่างกัน จากการประเมินของ Justin Thaler จาก a16z ในบทความ "การวัดประสิทธิภาพ SNARK: ส่วนหน้า ส่วนหลัง และอนาคต" ในเดือนสิงหาคม 2022 แม้ว่า Brakedown จะมีขนาด Proof ที่ใหญ่กว่า แต่ก็เป็นโปรโตคอลความมุ่งมั่นแบบพหุนามที่เร็วที่สุดอย่างไม่ต้องสงสัยในปัจจุบัน

FRI, KZG, Bulletproof เป็นโปรโตคอลความมุ่งมั่นแบบพหุนามที่พบได้บ่อยกว่า แต่ความเร็วคือคอขวด อัลกอริทึมต่างๆ เช่น Plonky ที่ใช้โดย zkSync, Plonky 2 ที่ใช้โดย Polygon zkEVM และ Ultra-Plonk ที่ใช้โดย Scroll ล้วนเป็นความมุ่งมั่นแบบพหุนามตาม KZG Prover เกี่ยวข้องกับการคำนวณ FFT จำนวนมากและการดำเนินการของ MSM ที่สร้างพหุนามและภาระผูกพัน ซึ่งทั้งสองอย่างนี้ทำให้เกิดภาระในการคำนวณจำนวนมาก แม้ว่า MSM มีศักยภาพในการเรียกใช้การเร่งความเร็วแบบมัลติเธรด แต่ก็ต้องใช้หน่วยความจำจำนวนมากและช้าแม้ภายใต้การทำงานแบบคู่ขนานสูง ในขณะที่ FFT ขนาดใหญ่ต้องอาศัยการสับเปลี่ยนข้อมูลบ่อยครั้งอย่างมากเมื่ออัลกอริทึมทำงาน ทำให้ยากต่อการโหลด ข้ามคลัสเตอร์การคำนวณผ่านการเร่งความเร็วแบบกระจาย

เป็นเพราะโปรโตคอลการผูกมัดพหุนามที่เร็วกว่า Brakedown ทำให้ความซับซ้อนของการดำเนินการดังกล่าวลดลงอย่างมาก

FOAKS หรือ Fast Objective Argument of Knowledges เป็นเฟรมเวิร์กระบบพิสูจน์ความรู้ที่ไม่มีความรู้ตามเบรกดาวน์ซึ่งเสนอโดย Fox Tech FOAKS ลดการทำงานของ FFT บนพื้นฐานของ Orion และเป้าหมายคือกำจัด FFT ในที่สุด นอกจากนี้ FOAKS ยังออกแบบวิธีการเรียกซ้ำการพิสูจน์ใหม่ที่สวยงามมากเพื่อลดขนาดการพิสูจน์ ข้อได้เปรียบของเฟรมเวิร์ก FAKS คือมีขนาดการพิสูจน์ที่เล็กโดยยึดตามเวลาการพิสูจน์เชิงเส้นจริง ซึ่งเหมาะมากสำหรับสถานการณ์ zkRollup

ด้านล่างนี้ เราจะแนะนำโปรโตคอลข้อผูกมัดแบบพหุนามที่ Brakedown ใช้โดย FOAKS โดยละเอียด

ในการเข้ารหัส โปรโตคอลข้อผูกมัด (Commitment) ประกอบด้วยผู้พิสูจน์ (Prover) ที่กระทำกับค่าความลับบางอย่าง สร้างมูลค่าความมุ่งมั่นสาธารณะซึ่งมีผลผูกพันและซ่อน (ซ่อน) จากนั้นส่ง ผู้ตรวจสอบจำเป็นต้องเปิดสัญญานี้และส่ง ข้อความไปยังผู้ตรวจสอบเพื่อตรวจสอบความสอดคล้องระหว่างสัญญาและข้อความ สิ่งนี้ทำให้โปรโตคอลการผูกมัดและฟังก์ชันแฮชมีหลายอย่างที่เหมือนกัน แต่โปรโตคอลการผูกมัดมักจะอาศัยโครงสร้างทางคณิตศาสตร์ในด้านการเข้ารหัสคีย์สาธารณะ พหุนามพันธสัญญา (Polynomial Commitment) คือรูปแบบพันธะพหุนามประเภทหนึ่ง กล่าวคือ ค่าสัญญาเป็นพหุนาม ในเวลาเดียวกัน โปรโตคอลการผูกมัดพหุนามยังรวมถึงอัลกอริทึมเพื่อรับค่า ณ จุดที่กำหนดและให้การพิสูจน์ ซึ่งทำให้โปรโตคอลการผูกมัดพหุนามเป็นชั้นสำคัญของโปรโตคอลการเข้ารหัสและเป็นส่วนสำคัญของระบบพิสูจน์ความรู้ที่ไม่มีความรู้จำนวนมาก .

ในการวิจัยล่าสุดในด้านการเข้ารหัส เนื่องจากการค้นพบการเชื่อมต่อระหว่างผลิตภัณฑ์เทนเซอร์ (ผลิตภัณฑ์เทนเซอร์) และค่าของพหุนาม ทำให้เกิดชุดของโปรโตคอลความมุ่งมั่นพหุนามที่เกี่ยวข้อง และเบรกดาวน์เป็นหนึ่งในโปรโตคอลตัวแทน . .

ก่อนที่จะแนะนำรายละเอียดของโปรโตคอล Brakedown โดยละเอียด จำเป็นต้องเข้าใจพื้นฐานบางอย่างก่อน เราจำเป็นต้องเข้าใจการทำงานของ Linear Code, Anti-collision Hash Function, Merkle Tree, Tensor Product และ tensor product ที่แสดงค่าพหุนาม

แบบแรกคือรหัสเชิงเส้น (Linear Code) รหัสเชิงเส้นที่มีความยาวข้อความ k และความยาวของคำรหัส n คือพื้นที่ย่อยเชิงเส้น

C ∈ Fn เพื่อให้มีการแทรกจากข้อความไปยังโค้ดเวิร์ด เรียกว่า การเข้ารหัส ซึ่งแสดงเป็น EC: Fk→C การรวมกันเชิงเส้นของ codewords ยังคงเป็น codeword ระยะห่างระหว่างโค้ดเวิร์ด 2 ตัว u และ v คือระยะแฮมมิง ซึ่งแสดงเป็น △(u, v)

ระยะทางที่สั้นที่สุดคือ d=minu, v△(u, v) รหัสดังกล่าวแสดงเป็นรหัสเชิงเส้น [n, k, d] และ d /n แทนระยะทางสัมพัทธ์ของรหัส

ตามด้วยฟังก์ชันป้องกันการชนกันของแฮช (Hash Function) และ Merkle tree (เมิร์กเคิลทรี)

ใช้ H: { 0, 1 } 2 λ → { 0, 1 } λ เพื่อแสดงฟังก์ชันแฮช Merkle tree เป็นโครงสร้างข้อมูลพิเศษที่สามารถรับสัญญาของข้อความ 2 d สร้างค่าแฮช h และต้องการค่าแฮช d+ 1 เมื่อเปิดข้อความใดๆ

ต้นไม้ Merkle สามารถแสดงเป็นต้นไม้ไบนารีที่มีความลึก d โดยที่องค์ประกอบข้อความ L m1 , m2 ,..., ml สอดคล้องกับใบของต้นไม้ตามลำดับ แต่ละโหนดภายในของทรีถูกแฮชจากโหนดย่อยสองโหนด เมื่อเปิดข้อความ mi เส้นทางจาก mi ไปยังรูทโหนดจะต้องถูกเปิดเผย

คำอธิบายภาพ

1. h←Merkle.Commit(m1 ,..., ml)

2. (mi,πi)←Merkle.Open(m, i)

3. { 0, 1 }←Merkle.Verify(πi, mi, h)

รูปที่ 1: Merkle Tree

คำอธิบายภาพ

รูปที่ 2: การทำงานของผลิตภัณฑ์เทนเซอร์ของเวกเตอร์และเมทริกซ์

ต่อไป เราจำเป็นต้องทราบผลคูณเทนเซอร์ของค่าพหุนาม

ตามที่กล่าวไว้ใน [GLS+] ค่าของพหุนามสามารถแสดงในรูปของผลิตภัณฑ์เทนเซอร์ ที่นี่เราพิจารณาความมุ่งมั่นของพหุนามพหุนาม

โดยเฉพาะอย่างยิ่ง เมื่อให้พหุนาม ค่าของมันในเวกเตอร์ x0 , x1 ,..., xlogN-1 สามารถเขียนเป็น:

ตามนิยามของพหุเชิง ระดับของตัวแปรแต่ละตัวคือ 0 หรือ 1 ดังนั้นจึงมี N monomials และสัมประสิทธิ์ และ logN ตัวแปร ทำ

โดยที่ i0 i1 ...ilogN-1 เป็นตัวแทนเลขฐานสองของ i ให้ w แทนค่าสัมประสิทธิ์พหุนาม

ในทำนองเดียวกันให้กำหนด

ทำ

. ดังนั้น X=r0 ⊗r1

ดังนั้น ค่าพหุนามสามารถแสดงในรูปของผลิตภัณฑ์เทนเซอร์ได้: ϕ(x0 , x1 ,..., xlogN-1 )=。

สุดท้าย มาดูกระบวนการเบรกดาวน์ที่ใช้ใน FOAKS และ Orion [XZS 22 ]

ขั้นแรก PC.Commit แบ่งค่าสัมประสิทธิ์พหุนาม w ในรูปแบบเมทริกซ์ k×k และเข้ารหัส (อ้างอิงถึงรหัสเชิงเส้นใน "ความรู้เบื้องต้น") ซึ่งแสดงเป็น C2 จากนั้นให้สัญญากับแต่ละคอลัมน์ C2 [:, i] ของ C2 เพื่อสร้างต้นไม้ Merkle จากนั้นสร้างต้นไม้ Merkle อีกต้นสำหรับรากของต้นไม้ Merkle ที่เกิดจากแต่ละคอลัมน์เป็นข้อผูกมัดสุดท้าย

ในการคำนวณการพิสูจน์ค่า จำเป็นต้องพิสูจน์สองจุด จุดหนึ่งคือความใกล้เคียง (Proximity) และอีกจุดคือความสม่ำเสมอ (Consistency) การประมาณช่วยให้มั่นใจว่าเมทริกซ์ที่กระทำนั้นใกล้เคียงกับโค้ดเวิร์ดที่เข้ารหัสจริงๆ รับประกันความสม่ำเสมอ y=。

การทดสอบความใกล้เคียง: การทดสอบความใกล้เคียงประกอบด้วยสองขั้นตอน ขั้นแรก ผู้ตรวจสอบจะส่งเวกเตอร์แบบสุ่ม 0 ไปยังผู้พิสูจน์ และผู้พิสูจน์จะคำนวณผลคูณภายในของ Y0 และ C1 นั่นคือ คำนวณผลรวมเชิงเส้นของแถวของ C1 โดยมีส่วนประกอบของ Y0 เป็นค่าสัมประสิทธิ์ เนื่องจากคุณสมบัติของรหัสเชิงเส้น Cy 0 จึงเป็นโค้ดเวิร์ดของ Yy 0 หลังจากนั้น ผู้พิสูจน์จะพิสูจน์ว่า Cy 0 คำนวณจากโค้ดเวิร์ดที่กำหนด ในการพิสูจน์สิ่งนี้ ผู้ตรวจสอบจะสุ่มเลือกคอลัมน์ t และผู้พิสูจน์จะเปิดคอลัมน์ที่เกี่ยวข้องและแสดงหลักฐานต้นไม้ Merkle ตัวตรวจสอบจะตรวจสอบว่าผลคูณภายในของคอลัมน์เหล่านี้และ Y0 เท่ากับตำแหน่งที่สอดคล้องกันใน Cy 0 [BCG 20] พิสูจน์ว่าหากโค้ดเชิงเส้นที่ใช้มีระยะทางสัมพัทธ์คงที่ แสดงว่าเมทริกซ์ที่กระทำนั้นใกล้เคียงกับโค้ดเวิร์ดที่มีความน่าจะเป็นอย่างท่วมท้น (ความน่าจะเป็นอย่างท่วมท้นหมายถึงความน่าจะเป็นที่ประพจน์เชิงลบของประพจน์นั้นเป็นจริง ละเว้น) .

การตรวจสอบความสอดคล้อง: กระบวนการของการตรวจสอบความสอดคล้องและการตรวจสอบความใกล้เคียงนั้นคล้ายคลึงกันอย่างสิ้นเชิง ข้อแตกต่างคือไม่ได้ใช้เวกเตอร์สุ่ม Y0 แต่ใช้ r0 โดยตรงเพื่อทำให้ส่วนผลรวมเชิงเส้นสมบูรณ์ ในทำนองเดียวกัน c1 ยังเป็นรหัสเชิงเส้นสำหรับข้อความ y1 และมี

ϕ(x)=. มันแสดงให้เห็นใน [BCG 20 ] ว่าโดยการตรวจสอบความสอดคล้อง y=ϕ(x) มีความเป็นไปได้สูงหากเมทริกซ์ที่กระทำนั้นใกล้เคียงกับโค้ดเวิร์ด

ในรูปแบบ pseudocode เราให้โฟลว์ของโปรโตคอล Brakedown:

Public input：The evaluation point X，parsed as a tensor product X=r0 ⊗r1 ;

Private input：The polynomial ϕ ，the coefficient of is denoted by w.

Let C be the [n, k, d]-limear code，EC：FkFn be the encoding function，N=k×k. If N is not a perfect square，we can pad it to the next perfect square. We use a python style notationmat[:, i] to select the i-th column of a matrix mat。

1. function PC. Commit(ϕ)：

2. Parse w as a k×k matrix. The prover locally computes the tensor code encoding C1 ，C2  ，C1 is a k×n matrix，C2 is a n×n matrix.

3. for i∈ [n] do

4. Compute the Merkle tree root Roott=Merkle.Commit(C2 [:, i])

5. Compute a Merkle tree root R=Merkle.Commit([Root0 ,......Rootn-1 ]), and output R as the commitment.

6. function PC. Prover(ϕ, X, R)

7. The prover receives a random vector Y0 ∈Fk from the verifier

8. Proximity 

   

9. Consistency  

   

10. Prover sends C1 , y1 , C0 , y0  to the verifier.

11. Verifier randomly samples t[n] as an array Î and send it to prover

12. for idx∈Î do

13. Prover sends C1  [:, idx] and the Merkle tree proof of Rootidx for C2  [:, idx] under R to verifier

14. function PC. VERIFY_EVAL(πX, X, y=ϕ(X), R)

15. Proximity: ∀idx∈Î, CY 0 [idx]==and EC(Yy 0 )==CY 0 

16. Consistency:∀idx∈Î, C1 [idx]==and EC(Y1 )==C1 

17. y==

18. ∀idx∈Î, EC(C1 [:, idx]) is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.

19. Output accept if all conditions above holds. Otherwise output reject.

อ้างอิง

อ้างอิง

1. [GLS+]:Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for r 1 cs. Cryptology ePrint Archive. https://ia.cr/2021/1043.

2. [XZS 22 ]:Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]//Advances in Cryptology–CRYPTO 2022: 42 nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15 – 18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022: 299-328.https://eprint.iacr.org/2022/1010 

3. [BCG 20 ]:Bootle, Jonathan, Alessandro Chiesa, and Jens Groth. "Linear-time arguments with sublinear verification from tensor codes." Theory of Cryptography: 18 th International Conference, TCC 2020, Durham, NC, USA, November 16 – 19, 2020, Proceedings, Part II 18. Springer International Publishing, 2020.

4. Justin Thaler from A16z crypto, Measuring SNARK performance: Frontends, backends, and the future https://a16z crypto.com/measuring-snark-performance-frontends-backends-and-the-future/

5. ข้อมูลเบื้องต้นเกี่ยวกับผลิตภัณฑ์เทนเซอร์: https://blog.csdn.net/chenxy_bwave/article/details/127288938