Wall of Text #7: ทหารล้อมเมือง

เวลาเครียดๆ ขอแนะนำให้อ่านปัญหา Computer Science แก้เครียด

ปัญหาวันนี้มีอยู่ว่า พม่ายกทัพมาปิดล้อมกรุงศรีไว้ แบ่งเป็นสองกองทัพอยู่คนละฝั่งของเมือง

ทีนี้แม่ทัพพม่าต้องการให้บุกเข้าตีเมืองพร้อมกันทั้งสองด้าน เพราะถ้าบุกอยู่ข้างเดียวกรุงศรีอาจจะตั้งรับได้ แล้วทั้งสองกองทัพจะนัดเวลาเข้าตีกันอย่างไรดี?

วิธีการง่ายๆ ก็คือแม่ทัพที่อยู่ฝั่งซ้ายให้ทหารขี่ม้าถือสาส์นไปหากองทัพฝั่งขวา บอกว่าเวลาสองยามคืนนี้ให้บุกเข้าตี

ปรากฏว่ามันไม่ได้ง่ายอย่างนั้น เพราะทหารขี่ม้าไปก็อาจจะถูกข้าศึกจับระหว่างทางก็เป็นได้ ฝั่งขวาก็จะไม่ได้รับสาส์น ฝั่งซ้ายก็บุกอยู่ฝั่งเดียว

เพื่อความชัวร์ เราก็อาจจะกำหนดว่าถ้าได้รับสาส์นแล้วให้ทหารขี่ม้ากลับมาบอกด้วยว่าได้รับแล้ว วิธีนี้กลับยิ่งสร้างปัญหาใหม่อีก นั่นคือถ้าทหารขี่ม้าขากลับถูกจับ กลายเป็นว่าฝั่งขวาบุกเข้าตีอยู่ฝั่งเดียวแทน

แล้วเราจะแก้ปัญหานี้ให้แม่ทัพอย่างไรดี?


ปัญหานี้ใน Computer Science เรียกว่า Two Generals’ Problem ซึ่งเมื่อเราพิสูจน์ออกมาแล้วก็จะพบว่าเป็นไปไม่ได้ที่ทั้งสองกองทัพจะตกลงกันได้ เพราะไม่ว่าส่งสาส์นไปเท่าไรก็มีโอกาสจะถูกจับทั้งสิ้น

วิธีหนึ่งที่เราจะพอจัดการกับปัญหานี้ได้คือออกแบบระบบโดยคำนึงถึงความไม่แน่นอนเอาไว้ด้วย เช่น ถ้าคิดว่าไม่มีทางที่ทหารจะถูกจับไม่เหลือรอดเลยสักคน เราก็อาจจะส่งทหารแยกกันไปหลายๆ คน (ยังไงก็น่าจะถึงผู้รับสักคน) แล้วไม่ว่าจะได้รับคำตอบหรือไม่ก็จะบุกตามเวลาที่นัดหมายไว้

อีกวิธีหนึ่งคือเพิ่มขั้นตอนการยึนยันเข้าไปอีก นั่นคือเมื่อฝั่งขวารับสาส์นแล้วให้ส่งทหารกลับไปฝั่งซ้ายยึนยันว่าได้รับแล้ว ฝั่งซ้ายก็จะต้องส่งสาส์นกลับไปอีกทีหนึ่งว่าได้รับคำยึนยันแล้ว แล้วก็อาจจะตกลงกันไว้ก่อน เช่น ยึนยันครบ 4 ครั้งจึงจะบุก

วิธีนี้ก็พอช่วยได้เช่นกัน แต่ก็ไม่ได้ถูกต้อง 100% เช่น ถ้าสาส์นยึนยันครั้งสุดท้ายหายไป ฝั่งหนึ่งจะยึนยันแค่ 3 ครั้ง แม่ทัพก็ต้องเสี่ยงดวงอยู่ดีว่าจะบุกหรือไม่


ปัญหาบุกล้อมเมืองนี้ยังไม่จบ เพราะเรายังมีภาคต่อ

ภาคนี้บอกว่า กองทัพเมือง Byzantine ยกกองทัพปิดล้อมเมืองข้าศึกไว้ แต่คราวนี้ยกมาถึง 9 กองทัพ นายพลของแต่ละกองทัพก็ได้ตั้งทัพไว้ตามที่ต่างๆ นอกเมือง

คำถามยังคล้ายเดิมคือ นายพล 9 คนนี้จะต้องตกลงกันว่าจะบุกเข้าตีหรือจะถอย

ข้อจำกัดคือตามเงื่อนไขเดิม การส่งสาส์นระหว่างกองทัพ ผู้นำสาส์นอาจถูกจับและทำให้ไม่ได้รับสาส์นก็ได้

แล้วปรากฏว่า นายพลทั้ง 9 คนนั้นกลับมีบางคนเป็นไส้ศึก ซึ่งเราก็ไม่อาจรู้ได้ว่าใครอยู่พวกใด คนที่เป็นไส้ศึกนั้นอาจจะลงคะแนนเสียงขัดแย้งกับความเป็นจริงก็ได้ เช่น ถ้าข้าศึกมีกำลังมากกว่า ไส้ศึกก็จะบอกให้บุกเข้าไปตายกันหมด

แล้วนายพลทั้ง 9 จะตกลงกันอย่างไรดี?


ปัญหานี้มีชื่อตามเนื้อเรื่องคือเรียกว่า Byzantine generals’ problem ซึ่งวิธีแก้ที่ง่ายที่สุดก็คือกำหนดให้ 1 คนเป็นหัวหน้าแล้วนายพลที่เหลือต้องทำตามคำสั่งของหัวหน้าเสมอ แต่ถ้าบังเอิญดันได้ไส้ศึกมาเป็นหัวหน้า กองทัพก็วินาศ

ถ้าเราอยากได้ระบบที่ไม่ต้องพึ่งผู้นำที่เชื่อถือได้ วิธีที่เหมาะสมก็คงเป็นประชาธิปไตย คือนายพลทุกคนส่งสาส์นหากันหมด เพื่อลงคะแนนเสียงของตัวเอง ถ้าหากไส้ศึกมีไม่ถึงครึ่งหนึ่งก็ยังสามารถเชื่อตามเสียงส่วนมากได้ กรณีที่ผู้นำสาส์นถูกจับ ก็กำหนดให้ถือว่าไม่ได้ลงคะแนน แล้วเตี๊ยมกันล่วงหน้าว่าเสียงส่วนใหญ่ไม่ได้ลงคะแนนจะบุกหรือจะถอย

ปัญหา Byzantine นี้เป็นปัญหาที่พบเจอได้ทั่วไป เช่นบนเครื่องบินมักจะมีระบบอ่านค่าหลายชุดเพื่อป้องกันกรณีอุปกรณ์ล้มเหลว ถ้าหากระบบควบคุมแต่ละระบบอ่านค่าได้ไม่ตรงกัน ก็จะต้องมีการกำหนดวิธีแก้ไขสถานการณ์

หรือ Bitcoin เองก็เป็นปัญหาแบบนี้เช่นกัน โดยเปรียบผู้ใช้แต่ละคนเป็นนายพล ซึ่งบางคนก็ตั้งใจจะโกงเงินที่มีในระบบ จึงต้องมีระบบการขุด Bitcoin ใครขุดได้ก่อนและเสียงส่วนมากของระบบยอมรับผลนั้น ผู้นั้นก็จะได้กำหนดการทำธุรกรรมบนระบบ

อะไรคือ Bitcoin Mining

เห็นโพสต์ดีๆ เลยมาแปลให้อ่านกันครับ เป็นโพสต์อธิบาย Bitcoin Mining เป็นภาษาแบบบ้านๆ

ก่อนอื่นต้องเริ่มที่คำศัพท์ที่ต้องรู้จักกันก่อนครับ ดังต่อไปนี้

Hash

คำว่าแฮช คือคำตอบจากสมการคณิตศาสตร์ที่ซับซ้อน ซึ่งสามารถแก้ได้โดยง่าย แต่ไม่สามารถทำย้อนกลับได้ และไม่สามารถคาดการณ์คำตอบได้ ยกตัวอย่างเช่น ถ้าผมบอกว่าผมมีเลขสองตัวรวมกันได้ 14,862 คงตอบไม่ได้ว่าเลขสองตัวนั้นเป็นเลขตัวไหนบ้าง แต่ถ้าผมบอกว่ามันเกิดจาก 3,608 + 11,254 เราสามารถพิสูจน์ได้ง่ายนิดเดียว แฮชก็มีลักษณะแบบนี้ แต่ใช้สูตรที่ซับซ้อนมาก

Block

ธุรกรรมต่างๆ ใน Bitcoin จะจัดรวมกลุ่มกันเป็นกล่องที่เรียกว่า block ซึ่งแต่ละ block จะเชื่อมหากันในลักษณะที่ว่า block อันใหม่ จะช่วยยึนยันว่า block อันก่อนถูกต้อง

ถ้าใครเคยใช้ Bitcoin อาจจะเคยเห็นข้อความทำนองว่า “12 confirmations” หมายความว่า บล็อคที่เก็บธุรกรรมของเรานั้นอยู่ห่างจากบล็อคล่าสุด 12 บล็อค ยิ่งห่างมากเท่าไร ก็ยิ่งยากต่อการถูกเปลี่ยนแปลงจากแฮคเกอร์

Difficulty

คำนี้แปลตรงตัวว่าความยาก ค่าความยากเป็นตัวเลขที่ระบุว่าแฮชที่ “ชนะ” นั้นหายากแค่ไหน (จะอธิบายต่อไป) ตอนนี้ขอให้เข้าใจว่า ค่าความยากเป็นค่าที่ระบบ Bitcoin ปรับตัวเองเพื่อให้เหมาะสมกับพลังประมวลผลของเครื่องที่ต่อกับระบบอยู่ โดยแต่ละบล็อคนั้นควรจะใช้เวลาสร้างประมาณ 6 บล็อคต่อชั่วโมง และการปรับค่าความยากนี้จะช่วยให้ Bitcoin ยากพอที่จะใช้เครื่องประมวลผลทั้งหมดสร้าง Block ได้ในเวลาประมาณ 10 นาที

การ mine Bitcoin ก็มาจากการที่แต่ละ Block นั้น นอกจากข้อมูลธุรกรรมแล้วยังมีข้อมูลมั่วๆ อยู่ค่านึง โปรแกรมขุด Bitcoin จะลองสุ่มข้อมูลมั่วๆ นี้มาแล้วหาค่าแฮชของ Block นั้น (ซึ่งอย่างที่บอก เราไม่สามารถคาดเดาคำตอบแฮชได้ ฉะนั้นไม่สามารถที่จะคาดคะเนข้อมูลสุ่มได้) พอมีคนโชคดีที่บังเอิญค่าแฮชมีค่าน้อยกว่าค่านึงที่กำหนดมาจากค่าความยากของระบบ ก็จะส่งค่านี้และแฮชออกไปในเครือข่าย Bitcoin จากนั้นเครือข่ายจะยึนยันว่าคำตอบนี้ถูกต้องแน่นอนแล้ว ผู้ที่เจอก็จะได้รับรางวัลเป็น Bitcoin จำนวนหนึ่ง

จำนวน Bitcoin ที่ได้รับนี้จะมาจากหลายๆ ปัจจุบัน โดยจะมีค่าตั้งต้นไว้ก่อนเพื่อส่งเสริมการ mining ในระหว่างที่ Bitcoin กำลังตั้งตัว ซึ่งตอนนี้ค่านี้คือ 50 BTC แต่เมื่อเวลาผ่านไป ค่านี้จะหารครึ่งไปเรื่อยๆ จนถึงศูนย์ นอกจากนี้ ธุรกรรมบางรายการยังมีการหักค่าธรรมเนียม (แล้วแต่จะให้ แต่ถ้าไม่ให้ miner อาจจะไม่ยอมใส่ธุรกรรมใน block ทำให้ธุรกรรมไม่มีผล) ซึ่งธุรกรรมนี้ผู้พบก็จะได้ไปเช่นเดียวกัน ในอนาคตค่าธรรมเนียมจะเป็นรายได้เดียวจากการ mining

ในสมัยแรก จำนวน miner ของระบบมีน้อยมาก และอุปกรณ์ก็ด้อยประสิทธิภาพ คือคอมทั่วๆ ไป แต่พวกนี้วันนึงได้หลายร้อย BTC แต่ในปัจจุบันมี miner จำนวนมาก และอุปกรณ์ก็เทพด้วย แต่ถึงจะใช้อุปกรณ์ราคาหลายหมื่นก็ต้องใช้เวลากว่า 2-3 เดือนกว่าจะได้ Block มาสักอัน

ก็มีผู้คิดแก้ไขปัญหานี้ โดยการสร้าง Mining pool ขึ้นมา ซึ่งหลักการคือให้ miner รวมกลุ่มกันสร้าง block ขึ้นมา และเมื่อสร้าง block สำเร็จแล้วก็จะแบ่งรายได้กันด้วยวิธีต่างๆ ที่ยุติธรรม (มีหลายวิธี แต่จะไม่กล่าวถึงในบทความนี้)

ข้างต้นนี้เป็นหลักการพื้นฐานของ Bitcoin Mining ต่อไปจะเป็นข้อสังเกตที่ควรทราบ

  • ระบบแฮชไม่ได้ทำไว้ให้ miner ไม่สะดวกอย่างเดียว แต่ยังทำให้แฮคเกอร์แก้ไขเนื้อหา block ได้ยากอีกด้วย เพราะจะต้องหาค่าแฮชใหม่ที่เป็นไปตามกฎเดิม แถมการจะเขียนทับข้อมูลเก่านั้น ไม่ใช่แค่หาแฮชได้อย่างเดียว จะต้องหาให้เร็วกว่า miner ทั่วไป ซึ่งแน่นอนว่าต้องใช้พลังประมวลผลจำนวนมหาศาล แต่ได้ประโยชน์น้อย ฉะนั้น ยิ่งมี miner มาก ค่าความยากก็ยิ่งยาก และยิ่งความยากมากขึ้น ก็ทำให้การฉ้อโกงในลักษณะนี้เป็นไปได้ยาก (ซึ่งในปัจจุบันนี้ค่าความยากมีค่ามากจนอาจจะต้องใช้อุปกรณ์หลายพันล้านเหรียญเพื่อจะเขียนทับธุรกรรมรายการเดียว)
  • ข้างบนจะบอกไว้ว่ารางวัลจากการหา block นั้นเริ่มที่ 50 แล้วหักครึ่งไปเรื่อยๆ จนเหลือ 0 ฉะนั้นถึงจุดนึงจะไม่มี bitcoin เกิดใหม่อีกแล้ว ในระบบจะมีมากที่สุดแค่ประมาณ 21 ล้าน BTC
  • นอกจากที่บอกว่าจำนวน miner ปัจจุบันมีมากและอุปกรณ์ก็ความเร็วสูงแล้ว ยังมีนวัตกรรมใหม่มาอีกด้วย คือในสมัยแรกคนใช้ CPU ธรรมดาประมวลผล แต่วันดีคืนดีมีคนคิดว่า เออ การ์ดจอที่เราไว้เล่นเกมเนี่ยมันคิดเลขแบบเดียวกันนี้เร็วกว่าเป็นร้อยเท่า ฉะนั้นโลกก็เปลี่ยนน่ะสิครับ แถมในปัจจุบันมันยังมีบริษัทที่คิดมากไปกว่านั้น พัฒนาอุปกรณ์เฉพาะทางกันไปเลย เรียกได้ว่าเร็วแรงกว่าการ์ดจอเสียอีก พวกนี้คือความเสี่ยงของการลงทุน Bitcoin miner เพราะสักวันอาจจะโดนเทคโนโลยีใหม่แซงหน้าไปไม่เห็นฝุ่นได้
  • การขุด Bitcoin ไม่ใช่การได้เงินฟรีๆ มันต้องลงทุนอุปกรณ์ (โอเค หรืออาจจะเอาที่ใช้อยู่แล้วก็ได้ถ้ามันเร็ว) และยังกินไฟฟ้า ฉะนั้นถ้าคุณต้องจ่ายค่าไฟเอง การจะได้กำไรไม่ใช่เรื่องง่าย​ (ผู้แปล: ผมเคยคำนวณจากค่าไฟของ กฟน.​ และการใช้ไฟฟ้าของ MacBook Pro แล้วไม่คุ้มครับ)
  • ทุกอย่างใน Bitcoin ไม่มีองค์กรกลาง การขุดก็เช่นเดียวกัน ทุกคนในระบบยอมรับกฎเดียวกัน ฉะนั้น ที่ผมเขียนไปว่า “Bitcoin มันทำแบบนี้” ถ้าพูดให้ถูกคือ “กฎเขียนไว้ว่าอย่างนี้” และทุกคนในระบบยอมรับและควบคุมรักษากฎ
  • สุดท้าย ปัจจัยต่างๆ ที่บอกในนี้ไม่ได้เกี่ยวข้องกับอัตราแลกเปลี่ยน ฉะนั้นถ้าอยู่ดีๆ มูลค่า Bitcoin เปลี่ยน มันอาจจะทำให้การขุดเกิดหรือตายได้เลย แต่อย่าลืมว่าถ้าขุดแล้วเจ๊ง ก็จะมีคนเลิก ความยากของระบบก็จะปรับลง แต่ก็ต้องใช้เวลา

มีคนสรุปกระบวนการ Mining ไว้แบบนี้ (จาก comment ในโพสต์ต้นฉบับ) “แฮชเปรียบเสมือน barcode อันนึง และการหา block ก็เหมือนการหาบาร์โค้ดที่มีจำนวนน้อยที่สุดในมหานครเมืองนึง”