บทความนี้ผมจะอธิบายคร่าวๆ เกี่ยวกับคอนเซปของ BLS signature ซึ่งมีคุณสมบัติที่น่าสนใจเรียกว่า Aggregation
หมายความว่าไง? หมายความว่าถ้าปกติเรามี 10 signature เราต้องทำการ verify ทั้ง 10 อันแยกกัน ในบล็อกเชนการที่ Validator จะโหวตให้บล็อกบล็อกนึง Validator จะต้องส่ง Signature บอก Validator คนอื่นๆ ว่าเขาได้โหวตให้กับบล็อกนี้ แต่ถ้าหากมี Validator เป็นแสนคนหละ? แปลว่าต้องมีการส่ง Signature จำนวนมากไปมาหากัน หรือแม้กระทั้งต้องเก็บมันไว้ในบล็อกด้วย เยอะจัด!
ลองใช้ Zero knowledge proof (ZKP) ช่วยดูไหม? การที่จะสร้าง Circuit สำหรับ ZKP ที่ใช้ Verify ความถูกต้องของหลายๆ Signature พร้อมกันก็สามารถทำได้ โดยการสร้าง Proof มานั้นอันเดียวที่สามารถ Verify ได้ว่าทุก Signature นั้นถูกต้อง แต่ความยากก็ยังมีอยู่ ก็คือเวลาเราสร้าง Circuit ขึ้นมาความซับซ้อนหรือขนาดของมันก็จะใหญ่ตามจำนวน Signature ที่จะ Verify ด้วย วิธีแก้ง่ายๆ ก็อาจจะเป็นการแตก Signatures เป็น Subset ย่อยๆ แล้วทำการสร้าง Proof ของแต่ละ Subset พวกนี้แบบ Parallel จากนั้นค่อยใช้ Recursive Proof เพื่อรวบหลายๆ Proof มัดรวมเป็น Proof เดียวก็ได้ แต่มันก็ยังจำเป็นที่จะต้องใช้ทรัพยากรณ์เยอะอยู่ดี (เช่น มี 100 Signatures: ใช้คอมเครื่องแรกสร้าง Proof สำหรับ 1-10 Signatures แรก ใช้คอมเครื่องที่ 2 เพื่อสร้าง Proof สำหรับ Signature ที่ 11-20 … จากนั้นเข้าเอา Proof ทั้งหมดมามัดรวมกันเป็น Proof เดียวโดยใช้ Recursive ZKP)
เอาหละเข้าประเด็น แล้วมันมีวิธีไหนไหมหละ ที่สามารถรวม Signature พวกนี้ไว้เป็น Signature อันเดียว และสามารถ Verify Signature เพียงอันเดียวเนี่ย ก็เท่ากับ Verify ทุก Signature ได้เลย ซึ่งถ้ามีก็คงช่วยประหยัดพื้นที่และลดความซับซ้อนลงได้เยอะเลย
และแน่นอนว่ามีและถูกใช้ใน Eth 2.0 และเหมือนว่าจะมี Idea ที่จะหยิบมาใช้ใน Cosmos ด้วยมันคือ BLS Signature ครับ! [1]
เริ่มจาก Math Basic กันก่อน PAIRING!
Math ALERT!
เริ่มจาก Group Theory แบบง่ายๆ Group คือเซตที่มาพร้อมกับ Operation ขอเรียกว่า “” ซึ่งเซตกับ Operation จะเป็น Group ก็ต่อเมื่อมันมีคุณสมบัติต่อไปนี้
Closure (ปิด): ให้ กับ เป็นสมาชิกของ Group แล้วผลลัพธ์ของ จะยังเป็นสมาชิกของ Group
Associativity (เปลี่ยนกลุ่ม): ให้ , และ แล้ว
Identity Element: มีสมาชิกที่เรียกว่า ที่ทำให้ เมื่อ คือสมาชิกใดๆ ใน Group
Inverses: เมื่อ คือสมาชิกใดๆ ใน Group แล้วจะมี ที่ทำให้
Cyclic Group ที่มี Order เท่ากับ หมายถึง Group นั้นจะประกอบด้วยสมาชิกจำนวน ตัวและมี generator โดยที่สมาชิกทุกตัวใน สามารถเขียนได้อยู่ในรูป เมื่อ หลังจากนี้เราจะพูดถึงแต่ Cyclic Group ซึ่งจากคุณสมบัติด้านบนแปลว่า Group มีสมาชิกเป็น
หมายเหตุว่า ผมใช้ Multiplicative notation “” ซึ่งหมายความว่า Operation ผมจะนิยามให้มีหน้าตาเป็นการคูณ แล้ว โดยที่ กับ สามารถเขียนอยู่ในรูปของ generator ได้เป็น และ ดังนั้น
บางที่อาจจะใช้ Additive notation “”
Pairing คือฟังก์ชัน ที่ Map สมาชิกจาก 2 Group กับ ที่มี Order เดียวกันไปยัง Group ใหม่ที่เรียกว่า Target Group สามารถเขียนได้เป็น ใน Crypyography นั้น Pairing ที่ใช้กันจะมีคุณสมบัติสองอย่าง
Bilinearity: เมื่อ และ .
Non-degeneracy: เมื่อ คือ Identity ของ
สำหรับผม ผมมองว่า Bilinear Pairing เป็นสิ่งที่ช่วยเราให้สามารถคูณ Scalar สองตัวที่ถูกซ่อนอยู่ภายใน Group Element ได้ โดยไม่จำเป็นต้องรู้ค่าที่แท้จริงของมัน
“ให้สามารถคูณ Scalar สองตัวที่ถูกซ่อนอยู่” หมายถึง: ถ้าเรามี เราจะรู้ค่าสุดท้ายของมันแต่ไม่รู้ค่า เนื่องจาก Discrete Log Problem ดังนั้นถ้าเรามี กับ เรารู้ว่ามันเป็นสมาชิกของ กับ แต่ไม่รู้ค่า กับ
ให้ เราสามารถบวก กับ เข้าด้วยกันได้โดยใช้ Group Operator ถึงแม้ว่าเราจะไม่รู้ค่า กับ ก็ตาม โดยให้ และ โดยที่ คือ Generator ของ โดยใช้ Group Operation กับ และ เราจะได้ว่า แต่เราไม่สามารถหาค่า ได้ถ้าเราไม่รู้ค่า หรือ ตรงนี้แหละที่ Pairing มาช่วยได้
คุณสมบัติที่เราจะใช้จริงๆ ใน BLS คือ Bilinearity ครับ
จาก Bilinearity เรารู้ว่า ให้ เราจะได้ จำคุณสมบติพวกนี้เอาไว้ เดี๋ยวจะเอาไปใช้ต่อ
เราเริ่มจากการ Setup ก่อน เริ่มโดยหยิบ private key ขอเรียกว่า มาหนึ่งตัวจาก เมื่อ คือ Group Order ของ และ เราสามารถหา Public Key ได้จาก
ตรงนี้รู้ Public Key ไปก็ไม่สามารถย้อนกลับไปหา ได้ เพราะ Discrete Log
ถ้าเราต้องการจะ Sign ข้อความ เนื่องจากมันมีขนาดยาวเท่าไหร่ก็ได้ เราเริ่มโดยการ Hash มันก่อนเพื่อให้มีขนาดคงที่ เราจะเรียกผลลัพธ์ว่า แต่ Hash นี้ต้องไม่ใช้ Hash แบบปกติแต่ต้องเป็น Hash ที่ให้ผลลัพธ์คือเป็นสมาชิกของ Group โดยสามารถทำได้โดยการมองผลลัพธ์ Hash เป็นตัวเลขและมองมันเป็นจถดบนแกน x ของ Elliptic Curve (Elliptic Curve มันฟอร์มตัวเป็น Group) แต่เนื่องจาก x หนึ่งค่าสามารถมีค่า y ได้สองค่าใน Elliptic Curve เราสามารถเลือกค่า y ที่น้อยที่สุดได้ สามารถอ่านเพิ่มเติมแบบละเอียดได้ลิงค์นี้
Signature ของข้อความ ที่ Sign ด้วย Private Key จะมีค่าเท่ากับ
เวลาจะ Verify ว่า Signature ถูกต้องก็สามารถทำได้ดังนี้
เนื่องจากคนอื่นรู้ Public Key ของคนที่ Sign , Signature และ Hash ของข้อความ
เขาสามารถ Verify ได้โดยใช้ Pairing
ถ้าค่าที่คำนวณ มีค่าเท่ากับ แปลว่า Signature ถูกต้อง
เอาหลังจุด Climax ละ การทำ Signature Aggregation
สมมติว่าเรามีคนเซ็น คนและมี Private Key เท่ากับ และทุกคนต้องการ Sign ข้อความ
ให้ Signature ของแต่ละคนมีค่าเป็น เราสามารถคำนวณหา Aggregated Signature ได้ดังนี้
Public Key ก็เช่นกัน
Now, any verifier can verify that the aggregated signature is valid and corresponds with the aggregated public key by checking:
จากนั้นคนที่ต้องการจะเช็คก็สามารถเช็คได้เลยว่าคนเซ็นหรือ Signer คนนั้นได้ Sign ข้อความ จริงๆ โดยใช้คุณสมบัติเหมือน Signature เดียวเลยคือ ลองตรวจว่า
เป็นจริง โอเคเรามาลองตรวจดูว่าจริงไหม
เรียบร้อย! ถูกต้องเดะ เนี่ยแหละงับ BLS Signature
รอบหน้าผมจะมาอธิบาย Lagrange Interpolation ที่จะพาเราไปสู่ BLS Threshold Signature
[1]