Why Nostr? What is Njump?
2024-08-07 12:22:37

LearnBN on Nostr: 11. Calculations ...

11. Calculations

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

การแข่งขันระหว่าง chain สุจริตกับ chain ของผู้โจมตี สามารถอธิบายได้ด้วยแบบจำลองการเดินสุ่มทวินาม (Binomial Random Walk) โดยเหตุการณ์ที่สำเร็จ หมายถึง chain ที่สุจริตถูกขยายออกไปอีกหนึ่งบล็อก เพิ่มความยาวนำหน้าไป +1 และเหตุการณ์ที่ล้มเหลว หมายถึง chain ของผู้โจมตีถูกขยายออกไปหนึ่งบล็อก ลดช่องว่างลง -1

ความน่าจะเป็นที่ผู้โจมตีจะไล่ตามทันจากช่องว่างที่กำหนด สามารถเปรียบเทียบด้วย Gambler's Ruin problem โดยสมมติว่านักพนันที่มีเครดิตไม่จำกัด เริ่มต้นด้วยการขาดทุน และเล่นพนันไปเรื่อย ๆ เพื่อให้ถึงจุดคุ้มทุน เราสามารถคำนวณความน่าจะเป็นที่เขาจะกลับมาถึงจุดคุ้มทุนได้ หรือความน่าจะเป็นที่ผู้โจมตีจะไล่ทัน chain ที่สุจริตได้ ดังนี้ [8]:

p = ความน่าจะเป็นที่ Node ที่สุจริตจะพบบล็อกถัดไป
q = ความน่าจะเป็นที่ผู้โจมตีจะพบบล็อกถัดไป
qz = ความน่าจะเป็นที่ผู้โจมตีจะไล่ทัน จากที่ตามหลังอยู่ z บล็อก



จากสมมติฐานที่ว่า p > q ความน่าจะเป็นจะลดลงแบบเอกซ์โพเนนเชียล เมื่อจำนวนบล็อกที่ผู้โจมตีต้องไล่ตามทันเพิ่มขึ้น หากเขาไม่สามารถพุ่งขึ้นนำได้อย่างรวดเร็วตั้งแต่แรก โอกาสของเขาก็จะลดลงจนน้อยมาก ๆ เมื่อเขาตามหลังมากขึ้นเรื่อย ๆ

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

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

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



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



จัดเรียงใหม่เพื่อหลีกเลี่ยง infinite tail ของการแจกแจง



แปลงมันให้เป็น C code

#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}

เมื่อรันผลลัพธ์บางส่วน เราจะเห็นว่าความน่าจะเป็นลดลงแบบเอกซ์โพเนนเชียลเมื่อ z เพิ่มขึ้น

q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006

การแก้หาค่า P ที่น้อยกว่า 0.1%...

P < 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340

#siamstr
Author Public Key
npub10yqgu7q6mmrk0nywywd4x0kukx029cnqly5p4yf9ay6zthavjw2syrhcl3