Elias Extractor Lab | Learning Chontit

ทำความรู้จัก Elias Extractor

Elias Extractor หรือ "ตาชั่งซื่อสัตย์" คืออัลกอริทึมที่ทำหน้าที่สกัดความสุ่มที่บริสุทธิ์ 100% (Uniform) จากอุปกรณ์ที่มีความลำเอียง (Biased) อย่างเช่น เต๋าที่ถ่วงน้ำหนัก หรือเหรียญที่บิ่น โดยอาศัยหลักการทางคณิตศาสตร์เรื่อง "การเรียงสับเปลี่ยนตำแหน่ง (Permutations)" แทนที่จะสนใจว่าหน้าใดออกมากกว่ากัน

The Bias Problem (ปัญหาความลำเอียง)

ลองปรับความลำเอียง และทดสอบทอยเหรียญดูสิ!

สาธิต: เมื่อเหรียญของคุณไม่สมมาตร

โอกาสออกหัว (Heads): 70% โอกาสออกก้อย (Tails): 30%

หัว (Heads)

ก้อย (Tails)

ทำไมถึงต้องใช้ Elias?

สังเกตผลลัพธ์จากการทอย 100 ครั้งด้านบน หากเราใช้ ผลลัพธ์ดิบๆ จากอุปกรณ์ที่ลำเอียง ความสุ่มที่ได้จะเอียงไปฝั่งใดฝั่งหนึ่งอย่างชัดเจน (เดาง่าย ไม่ปลอดภัย) แต่ Elias ไม่สนใจว่าฝั่งไหนออกมากกว่ากัน มันสนใจเพียงแค่ว่า ในกลุ่มผลลัพธ์แบบเดียวกัน มันถูกสลับที่หรือ "เรียงตัว" อย่างไร ซึ่งกระบวนการนี้ยุติธรรม 100% เสมอ!

1. จำแนก Type และคำนวณขอบเขตทั้งหมด (M)

แนวคิดหลัก (Key Concept)

ผลลัพธ์จากการทอยเต๋าคือ "ลำดับของตัวอักษรหรือตัวเลข" (Sequence) สิ่งแรกที่อัลกอริทึมทำคือ นับความถี่ ว่าแต่ละหน้าออกกี่ครั้ง เพื่อจัดหมวดหมู่ให้เป็น Type (ชุดคุณลักษณะ)

จากนั้นจึงคำนวณหาค่า M (Total Permutations) หรือ จำนวนวิธีที่สามารถนำตัวเลขชุดนี้มาสลับที่กันได้ทั้งหมด

ป้อนลำดับการทอย (รับเฉพาะ 0-9 และ A-F):

ความถี่ของแต่ละหน้า (Frequency) และค่า M

จำนวนวิธีเรียงสับเปลี่ยนทั้งหมดที่เป็นไปได้สำหรับ Type นี้ (M):

Multinomial Coefficient (สัมประสิทธิ์พหุนาม)

ทำไมถึงต้องใช้สูตรนี้? เวลาเราทอยเต๋าหรือเหรียญ เราจะได้ลำดับที่มี "หน้าซ้ำกัน" สูตรนี้ช่วยให้เราหาจำนวนรูปแบบทั้งหมดที่สลับตำแหน่งกันได้ โดยไม่นับรูปแบบที่ซ้ำซ้อน

M = k! / (c₁! * c₂! * ... * cₙ!)

k! (แฟกทอเรียลของความยาวทั้งหมด): คือจำนวนวิธีเรียงสับเปลี่ยนทั้งหมด สมมติว่าของทุกชิ้นหน้าตาไม่เหมือนกันเลย

c₁!, c₂! (แฟกทอเรียลความถี่): เนื่องจากอักษรที่เหมือนกัน (เช่น ได้ 'A' 3 ครั้ง) เวลาสลับที่กันเอง ลำดับก็ยังดูหน้าตาเหมือนเดิม! เราจึงต้อง หารออก ด้วยวิธีที่ตัวซ้ำมันสลับกันเอง

2. ค้นหาอันดับพจนานุกรม (Dictionary Rank)

ความมหัศจรรย์ของอันดับ (Rank)

เมื่อเราได้ค่า M (รูปแบบที่เป็นไปได้ทั้งหมด) จากขั้นตอนที่แล้ว ทฤษฎีความน่าจะเป็นพิสูจน์แล้วว่า "ทุกๆ รูปแบบใน M มีโอกาสเกิดเท่ากันเป๊ะ 100%!" ไม่ว่าเต๋าของคุณจะลำเอียงแค่ไหนก็ตาม

ดังนั้น สิ่งที่เราต้องทำคือ หาว่าลำดับของเรา เป็นอันดับที่เท่าไหร่ (Rank)? หากเรียงรูปแบบทั้งหมดตามพจนานุกรม ตัวเลข "อันดับ" นี้แหละคือความสุ่มที่บริสุทธิ์!

ลำดับที่เราทอยได้:

พร้อมคำนวณอันดับ (Rank เริ่มต้น = 0)
คลิกปุ่มด้านบนเพื่อเริ่มตรวจสอบตัวอักษรตำแหน่งแรก...

ที่มาของตัวเลข "การนับข้ามกลุ่ม"

สมมติลำดับที่เราป้อนคือ A3A71FA23B และกำลังดูที่ตำแหน่ง 'A' เนื่องจาก 'A' ไม่ใช่ตัวแรกตามพจนานุกรม เราจึงต้อง นับข้าม รูปแบบที่ขึ้นต้นด้วย 1, 2, 3, 7

วิธีคิด (ใช้สูตร M เดิมกับอักษรที่เหลือ):

ข้ามกลุ่มที่นำด้วย '1': เหลือที่ว่าง 9 ตำแหน่ง (มี '3' ซ้ำ 2, 'A' ซ้ำ 3) ➡️ M = 9! / (2!×3!) = 30,240
ข้ามกลุ่มที่นำด้วย '3': เหลือที่ว่าง 9 ตำแหน่ง (ตอนนี้มีแค่ 'A' ซ้ำ 3) ➡️ M = 9! / 3! = 60,480

เราจะนำจำนวนเหล่านี้มาบวกสะสมเป็น Rank ไปเรื่อย ๆ จนจบ Sequence

3. ปรากฏการณ์ Avalanche และการสกัดบิต

ปรากฏการณ์ลูกโซ่ (The Avalanche Effect)

ในระบบ Hash Function ทั่วไป (เช่น SHA-256) การเปลี่ยนหรือเพิ่มตัวอักษร 1 ตัว คือการ "Scramble" หรือสุ่มมั่วผลลัพธ์ใหม่ทั้งหมด แต่ในโลกของ Elias Extractor มันลึกซึ้งกว่านั้น:

การเพิ่มข้อมูลเพียง 1 ตัวอักษร ไม่ใช่แค่การเอาบิตไปต่อท้าย แต่มันคือ การขยายขนาดของจักรวาล (M) ให้ใหญ่ขึ้นแบบทวีคูณ และบังคับให้เราต้องเอาทุกอย่างมาจัดเรียงอันดับ (Rank) ใหม่ทั้งหมดตั้งแต่ต้น!

ทดลองเพิ่มข้อมูลลงในลำดับ (คลิกปุ่มเพื่อเพิ่มทีละตัว จะเห็นว่า M โตขึ้น):

การสกัดบิตให้ยุติธรรม (Uniform Bit Extraction)

เรามีอันดับ (Rank) ที่ยุติธรรมแล้ว แต่คอมพิวเตอร์ต้องการข้อมูลเป็น "บิต (0 และ 1)" ซึ่งบิตที่ดีต้องมีโอกาสออก 0 และ 1 อย่างละ 50% เท่ากัน

ทำไมต้องหาเพดาน 2^a ?

สมมติว่าค่า M = 6 (เรารับ Rank ได้ตั้งแต่ 0 ถึง 5)
จำนวนรูปแบบที่เป็นเลขยกกำลังของ 2 (Power of 2) คือ 2, 4, 8, 16...
ก้อน (Block) ที่ใหญ่ที่สุดที่ไม่เกิน 6 คือ 4 (มาจาก 2² ซึ่งหมายถึงเราจะสกัดได้ 2 บิต)
เราจะจับคู่ Rank เข้ากับบิตดังนี้:
Rank 0 = 00
Rank 1 = 01
Rank 2 = 10
Rank 3 = 11
ปัญหาคือ: ถ้าเราทอยได้ Rank 4 หรือ 5 ล่ะ? เราไม่สามารถแปลงเป็นบิต 00, 01, 10, 11 ได้อีกแล้ว เพราะจะทำให้บิตตัวนั้นๆ ออกบ่อยเกินไป (เสียสมดุล 50/50)
ทางแก้: เราต้องยอม "ปัดทิ้ง" (Dropped) Rank 4 และ 5 ไปเลย (เหมือนทอยเต๋าใหม่) เพื่อรักษาความสุ่มให้บริสุทธิ์ 100% นั่นเอง!

สังเกตในตาราง: ถ้าเติมตัวอักษร "ใหม่" ค่า M จะโตขึ้นมาก ทำให้เราได้จำนวนบิต (a) มากขึ้น! แต่ถ้าเติมตัว "ซ้ำ" M จะโตช้า ข้อมูลที่ซ้ำซากจึงให้ค่าความสุ่ม (Entropy) ต่ำกว่านั่นเองครับ

4. สกัดบิตบริสุทธิ์แบบ Real-time (Elias Engine)

ลองพิมพ์เพื่อให้ Engine ทำงาน

ทดลองป้อนสัญลักษณ์ HEX ไปเรื่อย ๆ ด้านล่าง เพื่อดูการคำนวณ M, r และการคายบิตออกมาแบบสดๆ (เป้าหมายคือสะสมให้ครบ 256 Bits)

ป้อนลำดับการทอย (ทอยเพิ่มไปเรื่อยๆ):

ความยาวปัจจุบัน: 0 ทอย

ขอบเขต (M)

อันดับ (Rank)

บิตบริสุทธิ์ที่สกัดได้: 0 / 256 Bits

Extracted Bits (Output)

Binary (ฐาน 2):

HEX (ฐาน 16) Output เพื่อเทียบกับ Input ด้านบน:

5. บทสรุปสู่ BIP-39 Seed Phrase

นำ Entropy มาใช้งานจริง

เมื่อเราได้ Pure Entropy ครบ 256 บิตจากขั้นตอนที่แล้ว เราจะนำมันมาเข้าสู่กระบวนการมาตรฐาน BIP-39 เพื่อแปลงเลขฐานสองที่จำยาก ให้กลายเป็นกลุ่มคำภาษาอังกฤษ 24 คำ (Mnemonic) เพื่อใช้สำหรับกู้คืนกระเป๋าเงิน (Wallet) ของคุณ

ป้อนค่า Entropy เริ่มต้น (HEX 64 ตัวอักษร = 256 Bits):

คำเตือนเพื่อความปลอดภัย (For Education Only)

ห้ามนำ 24 คำที่ปรากฏในหน้านี้ไปใช้สร้างกระเป๋าเก็บเงินจริงเด็ดขาด! ข้อมูลนี้เกิดจากการจำลองบนเบราว์เซอร์เพื่อการเรียนรู้เท่านั้น