(Thai Ver)My Lecture Note 1: BLS Signatures
May 30th, 2024

บทความนี้ผมจะอธิบายคร่าวๆ เกี่ยวกับคอนเซปของ 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 ขอเรียกว่า “\cdot” ซึ่งเซตกับ Operation จะเป็น Group ก็ต่อเมื่อมันมีคุณสมบัติต่อไปนี้

  1. Closure (ปิด): ให้ aa กับ bb เป็นสมาชิกของ Group แล้วผลลัพธ์ของ aba \cdot b จะยังเป็นสมาชิกของ Group

  2. Associativity (เปลี่ยนกลุ่ม): ให้ aa, bb และ cc แล้ว (ab)c=a(bc)(a \cdot b) \cdot c = a \cdot (b \cdot c)

  3. Identity Element: มีสมาชิกที่เรียกว่า ee ที่ทำให้ ea=ae=ae \cdot a = a \cdot e = a เมื่อ aa คือสมาชิกใดๆ ใน Group

  4. Inverses: เมื่อ aa คือสมาชิกใดๆ ใน Group แล้วจะมี a1a^{-1} ที่ทำให้ aa1=a1a=ea \cdot a^{-1} = a^{-1} \cdot a = e

Cyclic Group GG ที่มี Order เท่ากับ pp หมายถึง Group นั้นจะประกอบด้วยสมาชิกจำนวน pp ตัวและมี generator gg โดยที่สมาชิกทุกตัวใน GG สามารถเขียนได้อยู่ในรูป gmg^m เมื่อ m{0,1,...,p1}m \in \{0, 1, ..., p - 1\} หลังจากนี้เราจะพูดถึงแต่ Cyclic Group ซึ่งจากคุณสมบัติด้านบนแปลว่า Group GG มีสมาชิกเป็น {g0,g1,...,gp1}\{g^0, g^1, ..., g^{p-1}\}

หมายเหตุว่า ผมใช้ Multiplicative notation “\cdot” ซึ่งหมายความว่า Operation ผมจะนิยามให้มีหน้าตาเป็นการคูณ u,vGu, v \in G แล้ว uv=wGu \cdot v = w \in G โดยที่ uu กับ vv สามารถเขียนอยู่ในรูปของ generator gg ได้เป็น gxg^x และ gyg^y ดังนั้น uv=gxgy=gx+y=wGu \cdot v = g^x \cdot g^y = g^{x+y} = w \in G

บางที่อาจจะใช้ Additive notation “++

Pairing คือฟังก์ชัน ee ที่ Map สมาชิกจาก 2 Group G1G_1 กับ G2G_2 ที่มี Order เดียวกันไปยัง Group ใหม่ที่เรียกว่า Target Group GTG_T สามารถเขียนได้เป็น e:G1×G2Gte: G_1 × G_2 → G_t ใน Crypyography นั้น Pairing ที่ใช้กันจะมีคุณสมบัติสองอย่าง

  1. Bilinearity: e(ua,vb)=e(u,v)abe(u^a, v^b) = e(u, v)^{ab} เมื่อ uG1u \in G_1 และ vG2v \in G_2.

  2. Non-degeneracy: e(g1,g2)IGte(g_1, g_2) \neq I_{G_t} เมื่อ IGtI_{G_t} คือ Identity ของ GtG_t

สำหรับผม ผมมองว่า Bilinear Pairing เป็นสิ่งที่ช่วยเราให้สามารถคูณ Scalar สองตัวที่ถูกซ่อนอยู่ภายใน Group Element ได้ โดยไม่จำเป็นต้องรู้ค่าที่แท้จริงของมัน e(ua,vb)=e(u,v)abe(u^a, v^b) = e(u, v)^{ab}

  1. “ให้สามารถคูณ Scalar สองตัวที่ถูกซ่อนอยู่” หมายถึง: ถ้าเรามี uau^a เราจะรู้ค่าสุดท้ายของมันแต่ไม่รู้ค่า aa เนื่องจาก Discrete Log Problem ดังนั้นถ้าเรามี uau^a กับ vbv^b เรารู้ว่ามันเป็นสมาชิกของ G1G_1 กับ G2G_2 แต่ไม่รู้ค่า aa กับ bb

  2. ให้ u,vG1u, v \in G_1 เราสามารถบวก xx กับ yy เข้าด้วยกันได้โดยใช้ Group Operator ถึงแม้ว่าเราจะไม่รู้ค่า xx กับ yy ก็ตาม โดยให้ u=gxu = g^x และ v=gyv = g^y โดยที่ gg คือ Generator ของ G1G_1 โดยใช้ Group Operation กับ uu และ vv เราจะได้ว่า uv=gxgy=gx+yu \cdot v = g^x \cdot g^y = g^{x+y} แต่เราไม่สามารถหาค่า gxy=(gx)y=uyg^{xy} = (g^x)^y = u^y ได้ถ้าเราไม่รู้ค่า xx หรือ yy ตรงนี้แหละที่ Pairing มาช่วยได้

คุณสมบัติที่เราจะใช้จริงๆ ใน BLS คือ Bilinearity ครับ

จาก Bilinearity เรารู้ว่า e(ua,vb)=e(u,v)abe(u^a, v^b) = e(u, v)^{ab} ให้ a=1a=1 เราจะได้ e(u,vb)=e(u,v)b=e(ub,v)e(u, v^b) = e(u, v)^b = e(u^b, v) จำคุณสมบติพวกนี้เอาไว้ เดี๋ยวจะเอาไปใช้ต่อ

เราเริ่มจากการ Setup ก่อน เริ่มโดยหยิบ private key ขอเรียกว่า sksk มาหนึ่งตัวจาก {1,...,q1}\{1, ..., q - 1\} เมื่อ qq คือ Group Order ของ G1G_1 และ G2G_2 เราสามารถหา Public Key ได้จาก pk=gskpk = g^{sk}

ตรงนี้รู้ Public Key ไปก็ไม่สามารถย้อนกลับไปหา sksk ได้ เพราะ Discrete Log

ถ้าเราต้องการจะ Sign ข้อความ MM เนื่องจากมันมีขนาดยาวเท่าไหร่ก็ได้ เราเริ่มโดยการ Hash มันก่อนเพื่อให้มีขนาดคงที่ เราจะเรียกผลลัพธ์ว่า H(M)H(M) แต่ Hash นี้ต้องไม่ใช้ Hash แบบปกติแต่ต้องเป็น Hash ที่ให้ผลลัพธ์คือเป็นสมาชิกของ Group G2G_2 โดยสามารถทำได้โดยการมองผลลัพธ์ Hash เป็นตัวเลขและมองมันเป็นจถดบนแกน x ของ Elliptic Curve (Elliptic Curve มันฟอร์มตัวเป็น Group) แต่เนื่องจาก x หนึ่งค่าสามารถมีค่า y ได้สองค่าใน Elliptic Curve เราสามารถเลือกค่า y ที่น้อยที่สุดได้ สามารถอ่านเพิ่มเติมแบบละเอียดได้ลิงค์นี้

Signature ของข้อความ MM ที่ Sign ด้วย Private Key sksk จะมีค่าเท่ากับ S=H(M)skG2S = H(M)^{sk} \in G_2

เวลาจะ Verify ว่า Signature ถูกต้องก็สามารถทำได้ดังนี้

เนื่องจากคนอื่นรู้ Public Key ของคนที่ Sign pkpk, Signature SS และ Hash ของข้อความ H(M)H(M)

เขาสามารถ Verify ได้โดยใช้ Pairing

e(pk,H(M))=e(gsk,H(M))=e(g,H(M)sk)=e(g,S)e(pk, H(M)) = e(g^{sk}, H(M)) = e(g, H(M)^{sk}) = e(g, S)

ถ้าค่าที่คำนวณ e(pk,H(M))e(pk, H(M)) มีค่าเท่ากับ e(g,S)e(g, S) แปลว่า Signature ถูกต้อง

เอาหลังจุด Climax ละ การทำ Signature Aggregation

สมมติว่าเรามีคนเซ็น nn คนและมี Private Key เท่ากับ sk1,sk2,...,sknsk_1, sk_2, ..., sk_nและทุกคนต้องการ Sign ข้อความ MM

ให้ Signature ของแต่ละคนมีค่าเป็น S1,S2,...,SnS_1, S_2, ..., S_n เราสามารถคำนวณหา Aggregated Signature ได้ดังนี้

Sagg=S1S2...Sn=H(M)sk1H(M)sk2...H(M)skn=H(M)sk1+sk2+...+sknS_{agg} = S_1 \cdot S_2 \cdot ... \cdot S_n = H(M)^{sk_1} \cdot H(M)^{sk_2} \cdot ... \cdot H(M)^{sk_n} = H(M)^{sk_1 + sk_2 + ... + sk_n}

Public Key ก็เช่นกัน

pkagg=pk1pk2...pkn=gsk1gsk2...gskn=gsk1+sk2+...+sknpk_{agg} = pk_1 \cdot pk_2 \cdot ... \cdot pk_n = g^{sk_1} \cdot g^{sk_2} \cdot ... \cdot g^{sk_n} = g^{sk_1 + sk_2 + ... + sk_n}

Now, any verifier can verify that the aggregated signature is valid and corresponds with the aggregated public key by checking:

จากนั้นคนที่ต้องการจะเช็คก็สามารถเช็คได้เลยว่าคนเซ็นหรือ Signer nn คนนั้นได้ Sign ข้อความ MM จริงๆ โดยใช้คุณสมบัติเหมือน Signature เดียวเลยคือ ลองตรวจว่า

e(pkagg,H(M))=e(g,Sagg)e(pk_{agg}, H(M)) = e(g, S_{agg})

เป็นจริง โอเคเรามาลองตรวจดูว่าจริงไหม

e(pkagg,H(M))=e(gsk1+sk2+...+skn,H(M))=e(g,H(M)sk1+sk2+...+skn)=e(g,Sagg)e(pk_{agg}, H(M)) = e(g^{sk_1 + sk_2 + ... + sk_n}, H(M)) = e(g, H(M)^{sk_1 + sk_2 + ... + sk_n}) = e(g, S_{agg})

เรียบร้อย! ถูกต้องเดะ เนี่ยแหละงับ BLS Signature

รอบหน้าผมจะมาอธิบาย Lagrange Interpolation ที่จะพาเราไปสู่ BLS Threshold Signature

Ref

[1]

Subscribe to Fieldlnwza007
Receive the latest updates directly to your inbox.
Mint this entry as an NFT to add it to your collection.
Verification
This entry has been permanently stored onchain and signed by its creator.
More from Fieldlnwza007

Skeleton

Skeleton

Skeleton