smart contract แจก stake reward เขียนแบบไหนได้บ้างนะ ? (Part 2)
โอเค part นี้ เรามาดู algorithm standard ที่ใช้กันบ่อยในการทำ staking กัน (synthetix staking, pancake swap staking)
โอเค จาก part ที่แล้ว เราลองใช้สูตรด้านล่างในการคำนวณ staking reward กัน
แต่ปัญหาคือ สูตรนี้มี complexity เท่ากับ O(n) ซึ่งทำให้เสียค่า gas เยอะ
แล้วเราพัฒนายังไงได้บ้าง ?
โอเค มาลองดู scenario เทียบกับสูตรกัน
จากภาพข้อมูลที่แสดงคือ
- จำนวนที่นาย smile และนาย bear stake ในแต่ละช่วงเวลา
- ค่า totalStake ในแต่ละช่วงเวลา
แต่ถ้าเรามองแค่ส่วนของนาย smile ละ ?
เราจะพบว่าจริงๆแล้ว จำนวน stake ของนาย smile … ถ้าไม่มีการ stake เพิ่ม ก็นับเป็นค่าคงที่นี่นา
ดังนั้นเราสามารถแทนค่าคงที่ไปในสูตรได้
ซึ่งพอเป็นค่าคงที่แล้ว ก็จะดึงออกมาจากการ sum ได้ เช่น ในรูป เราดึง k ออกมาจาก sum
โอเค จะสรุปเป็นสูตรได้ดังนี้
ซึ่งสูตรนี้ยังเป็น O(n) อยู่ดี
มา optimize ต่อกัน
ตรงค่า sum จาก a ถึง b เนี่ย เราสามารถแปลงสมการได้เป็น ค่า sum จาก 0 ถึง b — ค่า sum จาก 0 ถึง a-1 ดังรูป
ดังนั้น จะได้สูตรคือ
เมื่อนำทั้ง 2 สูตรมารวมกัน จะได้สูตรสุดท้ายเป็น
แล้วสูตรนี้มี complexity ดีขึ้นยังไง ?
โอเค คงต้องกลับมาที่คำถาม สูตรนี้แปลว่าอะไรก่อน
มาเริ่มจากก้อนนี้กัน
โดยเราจะคูณ R เข้าไป จะได้
โอเค มาดูแต่ละตัวแปรกัน
เริ่มจากการยกตัวอย่างดีกว่า เช่น
เราต้องการคำนวณ reward ตั้งแต่วินาทีที่ 7–18
จะได้
b = 18
R = reward ที่ contract ให้ต่อวินาที
L(t) = totalStake ณ เวลานั้นๆ
โดยค่า R/L(t) เนี่ย จะคงที่ในช่วงที่ L(t) ไม่เปลี่ยน
เช่นจากภาพ
วินาทีที่ 7–9 L(t) จะไม่เปลี่ยน
วินาทีที่ 9–14 L(t) จะไม่เปลี่ยน
เป็นต้น
ดังนั้น ถ้าเราจะคิดค่า sum ตามสูตร
เราก็ต้องแบ่งการคิดเป็นช่วงๆ
เช่น ถ้าเราจะคิดค่า sum ตั้งแต่ช่วง 0–18 วินาที
ช่วง วินาทีที่ 0–7 ยังไม่มีการ stake จึงมีค่าเป็น 0
ช่วง วินาทีที่ 7–9 … ตอนที่ วินาทีที่ 7 นาย smile ยังเพิ่งมา stake จึงยังไม่มี reward … แต่ตอนวินาทีที่ 9 นาย Bear มา stake ณ จุดนี้เราจะคำนวณตามสูตรได้เป็น R/100 + R/100 (ที่วินาทีที่ 8 ทีนึง ที่วินาทีที่ 9 ทีนึง)
ช่วง วินาทีที่ 9–14 … ตอนที่ วินาทีที่ 14 นาย smile unstake ซึ่งเราจะคำนวณ sum ของ R / L(t) ได้เป็น R/200 + R/200 + R/200 + R/200 + R/200 (เนื่องจากระหว่าง 9–14 มี 5 วินาที)
และคิดค่าแบบเดิมในช่วงวินาทีที่ 14–18
โดยเมื่อบวกค่า sum ของทุกช่วงเข้าด้วยกัน จะได้ค่า sum ของช่วง 0–18 นั่นเอง
โอเค โดยสามารถวาดการคำนวณออกมาเป็นตารางได้ดังนี้
โอเค ก้อนหน้าเคลียร์ไปแล้ว มาดูก้อนหลังกันต่อ
โดยเมื่อคูณ R เข้าไป เราจะได้สูตรคล้ายๆกับข้อแรก ต่างกันที่เปลี่ยน b เป็น a-1
a คืออะไรแล้วนะ ?
มายกตัวอย่างกัน
ถ้าเราต้องการหา stake reward ของนาย bear ตั้งแต่วินาทีที่ 7–18 ด้วยสูตร
อย่างแรกเลยคือ ค่า k (จำนวน stake ของนาย bear) คงที่แค่ช่วงวินาทีที่ 9–18 (เพราะนาย bear เพิ่ง stake เข้ามาที่วินาทีที่ 9 ดังรูป)
ดังนั้น เราก็ต้องคำนวณแต่วินาทีที่ 9 -18 นั่นเอง
โดย a = 9 และ b = 18
โอเค ได้ค่า a มาแล้ว
จากสูตร พอเราคูณ R เข้าไป เราจะต้องหา R/L(t) ตั้งแต่วินาทีที่ 0 — (a-1) หรือก็คือ 0–8
แต่ประเด็นคือตอนเราคำนวณ sum b ด้านบน เราก็เก็บค่า sum วินาทีที่ 0–7 ไว้แล้ว … และวินาทีที่ 8 ก็ไม่มีใครมา interact อะไร
ดังนั้น sum R/L(t) วินาทีที่ 0–8 เท่ากับ sum R/L(t) วินาทีที่ 0–7
หรือแปลงเป็นคำพูดได้ว่า
ถ้านาย bear เข้ามา stake ที่วินาทีที่ 9
ก็ให้คำนวณก้อนหลัง โดยเอาค่า sum b ก่อนที่นาย bear จะเข้ามา stake (ค่า sum b ของวินาทีที่ 0–7) มาใช้ได้เลย
ดังนั้น ก้อนหลังไม่ต้องคำนวณใหม่ แต่ให้เอาค่า sum b ก่อนหน้ามาใช้
แต่เนื่องจาก user จะมีช่วงที่ต้องคิด reward ไม่เหมือนกัน เพราะ stake ไม่พร้อมกัน
ดังนั้น แต่ละ user จะคำนวณค่าก้อนหลังของตังเอง เก็บแยกกันไปนั่นเอง ตามรูป
โอเค มาลองดูตัวอย่างกัน
ถ้าจะหา reward ของ นาย bear ตั้งแต่วินาทีที่ 0–18 ด้วยสูตร
ตัวก้อนหน้า เราสามารถคำนวณโดยใช้ตารางแบบที่อธิบายไปแล้วได้เลย ตามรูป
ส่วนก้อนหลัง (ตัว p[bob]) เราก็สามารถหาได้จากค่าของก้อนหน้า ในตอนก่อนที่ นาย bear (หรือนาย bob) จะเข้ามา stake นั่นเอง โดยจะได้ค่า s ของวินาทีที่ 9 ไป ตามรูป
โอเค สูตรนี้สามารถ implement logic ได้ประมาณนี้
แต่ประเด็นคือ เรายังไม่ได้คิดใน case ที่ค่า stake ไม่คงที่ เช่นตามรูป นาย smile ทำการ stake เข้ามา 2 รอบ
เช่นเราต้องการคำนวณ reward ของนาย smile ตั้งแต่วินาทีที่ 7–14
ในเคสนี้เราต้องคำนวณ reward 2 รอบ
โดยให้ทำเสมือนว่านาย smile unstake 100 token ไปที่วินาทีที่ 9
แล้วทำการ stake 200 token เข้ามาในวินาทีที่ 9 เช่นกัน
โดยจะคำนวณได้ดังนี้
เริ่มจากคำนวณ reward ก่อนที่นาย smile จะมาเติม stake ก่อน โดยนาย smile จะ unstake เพื่อ claim reward จากนั้นจะนำไปเก็บไว้ (จากภาพจะได้ 3.5 R)
จากนั้น ทำเหมือนว่านาย smile เติม stake ทันทีหลังจาก unstake
ดังนั้นค่า p ของนาย smile จะเท่ากับ 2R/100 + 3R/200 ทันที (แม้ว่าจากเลข ในก้อนนี้จะ เหมือนมีส่วนของนาย smile อยู่ แต่เนื่องจาก claim ไปแล้ว ดังนั้นเราจะจึงจะไม่นำมาคิดใหม่ หรือก็คือ ทำเหมือนเป็นของคนอื่นไปเลย)
และค่า s ในช่วง 12–14 นั้น การถอนออก 200 ถอนเข้า 200 ในวินาทีเดียวกัน sจะไม่กระทบกับ L(t) อยู่แล้ว ดังนั้นเราจึงไม่ต้องคำนวณ s ใหม่ในตอน stake
โดยเราจะได้ reward ของนาย smile = 3.5 + 1.33 R นั่นเอง
โอเค part นี้ math กับ logic ล้วนๆเลย …
แต่เราจะเห็นแล้วว่า ใน logic นี้ เราไม่ต้องวนลูปเลย มีแค่การคำนวณเป็นครั้งๆ เวลา stake unstake เท่านั้น
part หน้าเราเอา logic นี้ไปลองเขียน code กัน โดย code ที่ได้ก็จะไม่มีลูปเช่นกัน!
