Motivation
ก่อนอื่นเลยเรามาทำความเข้าใจกันก่อนว่าทำไมถึงต้องทำการสุ่ม โดยมีการถ่วงน้ำหนักกันครับ
การสุ่มแบบถ่วงน้ำหนักถือเป็นปัญหานึงที่มีการใช้งานบ่อยๆในการเขียนโปรแกรมปกติ หรือในสถาณการณ์ปกติในชีวิตประจำวันของเรา
สมมติว่าเรามีลูกบอลอยู่ 4 สี แล้วต้องการที่จะสุ่มหยิบออกมาซักลูกนึง จะสามารถเขียนโปรแกรมได้อย่างไร?
หรือถ้าจะยกตัวอย่างที่ใกล้เคียงกันกับโลก Smart Contract มากขึ้น ทุกวันนี้อาจจะนึกถึงการสุ่ม NFTs ได้ครับ
สมมติว่าเรามี Platform NFT ที่สามารถ mint เมฆออกมาได้ โดยเมฆที่เรา mint ได้จะมีความ rare อยู่ 3 ลำดับ คือ Normal, Rare, Epic โดยแต่ละคลาสมี % การ gen ได้เป็นน้ำหนัก %
แล้วเราจะเขียนโปรแกรมสุ่มยังไงกันนะ ?
How do we do?
วิธีง่ายสุดเลยก็คือเราก็แค่สร้าง Array ขึ้นมาซักอัน แล้วเราก็ push สมาชิกในแต่ละคลาสเข้าไป
สมมติว่าเราอยากให้แต่ละ class มีสัดส่วนการสุ่มได้เท่าไรเราก็ใส่ไปเป็นสัดส่วนเท่านั้นๆ เช่นอยากให้ น้ำเงิน:แดง:เหลือง มีสัดส่วน 3:2:1 ก็ push ลูกบอลเข้าไปเป็นสัดส่วนเท่านั้นๆ
ถ้าเราอยากสุ่มเราก็แค่สุ่มเลขในช่วง 0..จำนวนลูกบอล จากนั้นก็ค่อยไปเทียบเอาว่าเราจะได้ลูกบอลสีอะไรมา
แต่.. ? วิธีการแบบนี้จะมี Big O เป็น O(N) ตอนที่เราเพิ่ม เพราะจำเป็นที่จะต้องเพิ่มไปทีละชิ้นๆ ซึ่งเปลือง action และเปลือง storage มากๆ เพราะฉะนั้นมันจึงไม่ใช่วิธีที่ feasible เลยถ้าหากจะเอาไปไว้บน smart contract เพราะมันจะเปลือง gas มากๆ
วิธีที่ผมจะแนะนำในวันนี้คือการใช้ Sum Tree ครับ (ข้อมูลอ้างอิงจาก https://www.fcodelabs.com/2019/03/18/Sum-Tree-Introduction/)
ตอนนี้ผมขอยกตัวอย่าง ให้บอลสี แดง:เหลือง:น้ำเงิน:เขียว มีสัดส่วนเป็น 5:7:5:13
เราสามารถที่จะเอามาวาด Sum Tree ได้ดังนี้ แล้วเราก็สุ่มเลขในช่วงระหว่าง 0–29 จากนั้นค่อยมาดูว่าเลขที่เราสุ่มได้อยู่ในใบไหน
Sum Tree เป็นหนึ่งใน Data Structure รูปแบบ Tree ซึ่งผมจะขอไม่เล่าในบทความนี้เนื่องจากจะเกินขอบเขตของบทความนี้เกินไปหน่อยครับ แต่ถ้าใครสนใจอยากศึกษาสามารถได้จาก GeekForGeeks ได้ครับ
ในที่นี้ผมจะขออธิบายรูปแบบคร่าวๆของ Sum Tree ครับ ให้ลองสังเกตตรง leaf node แต่ละอัน จะมีผลรวมเท่ากับ parent node เช่น โหนดสีแดงกับสีเหลือง 5 กับ 7 รวมกันเป็น 12
ซึ่งการเรียง Tree ในลักษณะนี้จะสามารถทำให้เรา Traverse มาหาโหนดที่มี index นั้นๆได้โดยใช้ Big O ค่า O(n log n)
แต่ถ้าหากสังเกตดูจะเห็นว่าเราไม่จำเป็นที่จะต้อง store ค่าเยอะเหมือนวิธีแรก แต่ store ลงน้อยมาก เพราะมี structure เป็น tree ซึ่งจะช่วยลดค่า gas เราไปได้เยอะมากๆ
Implementation
ในที่นี้เราจะไม่ได้เขียน Sum Tree ด้วยตัวเองครับ เนื่องจากมีความซับซ้อนในการ implement มาก เราจะไปยืมโค้ดที่มีคนเขียนมาก่อนแล้วมาใช้กันครับ
ผมเอามาเขียนโค้ดได้ตามนี้ครับ
บรรทัดที่ 4–6 ผม setup ระบบ SortitionSumTreeFactory
บรรทัดที่ 10 ใน contructor ผมสร้าง Sum Tree อันใหม่
บรรทัดที่ 13 ผมสร้างฟังค์ชัน mock() ขึ้นมาเพื่อที่จะ mock ค่าให้ระบบสุ่มของเรา สังเกตการใช้งานฟังค์ชันsortitionSumTrees.set( SUM_TREE_KEY, 80, bytes32(0) );
ตรงนี้เป็นจุดที่เรา set node ใหม่เข้าไปใน Tree ของเรา parameters แรกที่ใส่เป็น id ของ Tree ที่เราต้องการใช้ เลขที่ใส่ไปใน parameters ที่ 2 คือน้ำหนักที่ต้องการ ส่วน parameters ที่ 3 เอาไว้เก็บชื่อ หรือ identifier ของ node นั้น
บรรทัดที่ 33 ถ้าหากเราต้องการที่จะ access node ของแต่ละ index ก็จะเรียกใช้ฟังค์ชัน indexOf ที่ผมประกาศไว้ตรงนี้
แต่ตอนนี้เรายังไม่มีระบบสุ่มอยู่ข้างในครับ
https://gist.github.com/nonkung51/7556c5c569de72b596f6355f8dbc0cc9
บรรทัดที่ 37 ผมเพิ่มฟังค์ชัน random เข้าไปเพื่อให้เราสามารถ random สุ่มได้ (ในที่นี้เพื่อไม่ให้ซับซ้อนเกินไป ผมเลือกใช้การสุ่มแบบ Pseudo Random ง่ายๆไปก่อนครับ)
ลองกด deploy contract แล้วสุ่มเล่นดู ก็จะได้ผลลัพท์ออกมาตามที่เราต้องการครับ
(หลังจาก deploy อย่าลืมกด mock เพื่อ mock ฟังค์ชันเข้าไปด้วยครับ)
เขียนมาจนจบอาจจะมีคนสงสัยว่าทำไมเราต้องทำให้มันซับซ้อนถึงขนาดนี้ด้วย ทั้งๆที่ใส่ if-else เข้าไปก็ได้แล้ว
เหตุผลก็คือ ถ้าหากเราแค่ใส่ if-else เพื่อสุ่ม จะทำให้มันไม่มีความ dynamic ครับ บางครั้งเราอาจจะต้องการมาปรับลด เพิ่ม % หรือมาเพิ่ม class ที่จะให้สุ่ม ซึ่งถ้าหากใช้งาน if-else หลังจาก deploy contract แล้ว จะไม่สามารถมาเพิ่มได้ง่ายๆครับ
สำหรับบทความนี้ก็ขอจบลงเท่านี้ ถ้าใครมีข้อสงสัย ติชมอะไรสามารถ comment ได้ข้างล่างเลยครับ ขอบคุณมากครับ 😊😊