พิสูจน์การทำงาน HashWX

HashWX คือโปรโตคอล challenge เริ่มต้นของ Cap แทนที่จะใช้ฟังก์ชันแฮชตายตัวอย่าง SHA-256 challenge ทุกข้อจะสร้างฟังก์ชันทางเดียว ตัวใหม่ ขึ้นมาจาก seed โดยประกอบจากการดำเนินการกับจำนวนเต็มและการแตกกิ่ง ซึ่งเลือกมาให้ GPU รันได้ไม่เร็วกว่า CPU มากนัก

ผู้ออกแบบคือ tevador คนเดียวกับที่เขียน RandomX และ HashX ส่วน Cap ก็รวมบิลด์ WebAssembly ฉบับอ้างอิงมาให้ในตัว

TIP

HashWX เป็นค่าเริ่มต้นของคีย์ Standalone ที่สร้างใหม่ ส่วนใน cap-core ต้องเลือกเปิดเองผ่าน API แบบ format 2 และที่นั่น proof of work แบบ SHA-256 ยังเป็นค่าเริ่มต้นอยู่ ดู challenge แบบ HashWX

ทำไมต้อง HashWX

ปัญหาของ proof of work แบบ SHA-256 คือปริมาณงานต่อวินาที GPU รันฟังก์ชันตายตัวตัวเดียวกันพร้อมกันนับพันเลนอย่างสอดประสาน จึงแก้ challenge ได้ต่อวินาทีมากกว่า CPU อยู่มาก และนั่นคือตัวเลขที่สำคัญจริง ๆ สำหรับการกันบอท: ผู้โจมตีไม่สนว่า challenge ข้อเดียวใช้เวลานานแค่ไหน สนแค่ว่าเคลียร์ได้กี่ข้อต่อชั่วโมง

ก่อนหน้านี้ Cap ใช้ปริศนา time-lock แบบ RSW เพื่อการนี้ RSW ชนะในแง่ เวลาแฝง เพราะการยกกำลังสองตามลำดับภายในปริศนาข้อเดียวทำขนานไม่ได้ แต่แพ้ขาดในแง่ ปริมาณงานต่อวินาที เพราะ GPU รันปริศนาที่เป็นอิสระต่อกันพร้อมกันได้เป็นพันข้อ เมื่อวัดเทียบกับ GPU ระดับผู้ใช้ทั่วไป:

อัลกอริทึม	CPU, Ryzen 3700X, 16 เธรด	GPU, RTX 5060 Ti	GPU ได้เปรียบ
SHA-256	41 MH/s	6150 MH/s	~150x
RSW	26 H/s	4400 H/s	~170x
HashWX	2.8 MH/s	5.8 MH/s	~2x

ตัวเลขชุดนี้เป็นของ tevador ที่ใช้โค้ด CUDA ของเขาเองซึ่งไม่ได้เปิดเผย เราวัดแถว RSW ซ้ำเองแยกต่างหาก: M3 วัดได้ 2.112 H/s ต่อเธรด ซึ่งคิดเป็น 26 H/s สำหรับ 16 เธรดของ Ryzen

RSW ถูกเลิกใช้แล้ว มันยังเลือกใช้ได้รายคีย์และคีย์เดิมยังทำงานต่อได้ แต่ไม่ควรใช้กับระบบที่ติดตั้งใหม่

โปรโตคอลทำงานอย่างไร

การสร้าง challenge

เซิร์ฟเวอร์สุ่ม 32 ไบต์มาเป็น challenge C แล้วกำหนดความยาก d ตรงนี้ไม่มีสาระกุญแจและไม่มีการคำนวณล่วงหน้า การสร้าง challenge จึงเป็นแค่การอ่านค่าสุ่มหนึ่งครั้งกับการเซ็น JWT หนึ่งครั้ง

ไคลเอนต์จะได้รับ C, d และ n ซึ่งคือจำนวน nonce ที่ฟังก์ชันแต่ละตัวที่สร้างขึ้นครอบคลุม

การแก้ฝั่งไคลเอนต์

ไคลเอนต์ต้องหา nonce ขนาด 64 บิต N ที่ทำให้

H(N) <= (2^64 - 1) / d      where H = hashwx_make(sha256(C || u64le(N / n)))

nonce ที่ต่อเนื่องกัน n ตัวในหนึ่งบล็อกจะใช้ฟังก์ชันแฮชที่สร้างขึ้นร่วมกันหนึ่งตัว ไคลเอนต์สร้างฟังก์ชันนั้น รันมันทั้งบล็อก แล้วขยับไปบล็อกถัดไปถ้าไม่มีค่าไหนตกลงไปต่ำกว่าเป้าหมาย งานที่คาดหวังคือการแฮช d ครั้ง

Cap ใช้ n = 65536 ส่วนโปรโตคอลอ้างอิงใช้ 463 สำหรับไคลเอนต์เนทีฟ แต่ในเบราว์เซอร์ต้อง JIT คอมไพล์ฟังก์ชันผ่าน WebAssembly.Module ใหม่ทุกบล็อก บล็อกที่ใหญ่ขึ้นจึงช่วยเฉลี่ยต้นทุนส่วนนั้น tevador ระบุข้อแลกเปลี่ยนนี้ไว้ชัดเจน: ยิ่ง nonce ต่อฟังก์ชันมากขึ้น โปรโตคอลก็ยิ่งเสี่ยงต่อเคอร์เนล GPU ที่ JIT คอมไพล์มากขึ้น และสิ่งที่ยังคงความต้านทาน GPU ไว้ที่ค่านี้คือการแตกกิ่งที่แยกทางกัน ตัวเลข ~2x ข้างบนวัดที่ 65536 จึงรวมผลข้อนี้ไว้แล้ว

อะไรทำให้ต้านทาน GPU

สี่คุณสมบัติ ทั้งหมดมาจากเอกสารการออกแบบ:

แต่ละอินสแตนซ์คือโปรแกรม 32 ตัว แต่ละตัวเป็นลูปที่กระโดดกลับไปยังจุดเริ่มต้นของตัวเองด้วยความน่าจะเป็น 1/2 ซึ่งคิดออกมาได้พอดี 256 การแตกกิ่งต่อการแฮชหนึ่งครั้ง บน CPU นั่นคือการทำนายผิดไม่กี่ครั้ง แต่บน GPU มันทำให้ warp แตกออกเป็นเส้นทางที่แยกจากกัน และต้องรันทีละเส้นทาง

มี scratchpad ขนาด 16 KB และการอ่านจากมันถูกจงใจให้ไม่จัดแนว CPU เก็บมันไว้ใน L1 แล้วซ่อนเวลาแฝง 3 ถึง 4 รอบสัญญาณนาฬิกาด้วยการจัดลำดับคำสั่งใหม่ ส่วน GPU ต้องเก็บไว้ใน local memory ที่หนุนด้วย L2 ซึ่งใช้ราว 100 รอบ แล้วสถาปัตยกรรม GPU ส่วนใหญ่ยังต้องจำลองการอ่านแบบไม่จัดแนวด้วยการรวมการอ่านสองครั้งที่อยู่ติดกัน

รีจิสเตอร์ต้นทางถูกเลือกจากรายการ "ตื้น" และ "ลึก" ที่สลับกันอยู่ CPU จึงเจอการอ่านที่ขึ้นต่อกันเฉลี่ย 2.75 ครั้ง ส่วนตัวแปลคำสั่งบน GPU ต้องปรับให้เข้ากับรายการลึก เพราะราว 95% ของกรณีจะมีอย่างน้อยหนึ่งเธรดใน warp ที่รันโปรแกรมแบบลึก มันจึงต้องรับโซ่การอ่านที่ขึ้นต่อกันครบ 6 ชั้นทุกครั้ง

ชุดคำสั่งถูกจำกัดไว้เท่าที่ WebAssembly 1.0 มีให้: การคูณ บวก ลบ XOR OR หมุนบิต และเลื่อนบิตขนาด 64 บิต พร้อมค่าคงที่ 6 บิต นี่แหละคือสิ่งที่ทำให้อัลกอริทึมเดียวกันรันในเบราว์เซอร์ได้

การตรวจสอบฝั่งเซิร์ฟเวอร์

เซิร์ฟเวอร์คำนวณ seed ใหม่จาก C และดัชนีบล็อกที่ได้จาก nonce ที่ส่งมา สร้างฟังก์ชันแฮชตัวนั้นขึ้นมาหนึ่งตัว รันหนึ่งครั้ง แล้วเทียบกับเป้าหมาย การสร้างโปรแกรมถูกกว่า HashX ราว 5 เท่า นั่นคือเหตุผลที่การตรวจสอบอยู่ในระดับหลักสิบไมโครวินาที

ต้นทุน

ต้นทุนฝั่งเซิร์ฟเวอร์ต่อ challenge หนึ่งข้อ วัดบนคอร์เดียวของ Apple M3 เป็นค่ามัธยฐานจากการสร้าง 200 ครั้งและการตรวจสอบ 40 ครั้งผ่าน validateChallenge:

โปรโตคอล	การสร้าง	การตรวจสอบ	รวม
HashWX, 1 challenge	14 µs	40 µs	54 µs
HashWX, 4 challenge ย่อย (ค่าเริ่มต้น)	20 µs	129 µs	149 µs
SHA-256 (50 challenge, ความยาก 4)	4 µs	83 µs	87 µs
RSW (t = 75,000)	1522 µs	14 µs	1536 µs

challenge ของ HashWX แบบเดียวมีต้นทุนไป-กลับถูกที่สุดในสามตัวนี้ ค่าเริ่มต้นที่แบ่งเป็นสี่ challenge ย่อยใช้ราว 150 µs มากกว่า SHA-256 แต่เป็นหนึ่งในสิบของ RSW ซึ่งต้องจ่ายค่ายกกำลังมอดุลาร์จริงสี่ครั้งทุกครั้งที่สร้าง ความยากไม่มีผลกับตัวเลขเหล่านี้ เพราะการตรวจสอบคือการแฮชหนึ่งครั้งต่อหนึ่ง challenge ย่อย ไม่ว่าจะหามายากแค่ไหน

ต้นทุนฝั่งไคลเอนต์คืออีกด้านของการแลกเปลี่ยนนี้ challenge เดียวมีเวลาแก้ที่กระจายแบบเอกซ์โพเนนเชียล จึงเหมือนการจับสลาก ความยากเท่ากันอาจใช้ 30 มิลลิวินาทีสำหรับผู้เยี่ยมชมคนหนึ่ง และสามวินาทีสำหรับคนถัดไป Cap จึงแบ่งความยากออกเป็นสี่ challenge ย่อยเป็นค่าเริ่มต้น เพื่อให้เวลาแก้สม่ำเสมอขึ้น วัดผ่านวิดเจ็ตใน Chrome รุ่นเสถียรบน M3 8 คอร์ ชุดละ 72 ครั้ง โดยปรับความยากทั้งสองแบบให้มีค่ามัธยฐานใกล้เคียงกัน:

	1 challenge, d = 1,330,000	4 challenge ย่อย, d = 1,000,000
ค่ามัธยฐาน	536 ms	490 ms
p90	1447 ms	778 ms
ช้าที่สุดใน 72 ครั้ง	2378 ms	1490 ms

คอลัมน์ขวาคือค่าเริ่มต้น เมื่อวัดกับคีย์ของ Standalone ได้ค่ามัธยฐาน 578 มิลลิวินาที และ p90 0.9 วินาที

สำหรับความยากที่กำหนด การแบ่งไม่ได้เปลี่ยนสิ่งที่ผู้โจมตีต้องจ่าย เพราะงานที่คาดหวังยังคงเป็น d แฮชไม่ว่าจะแบ่งอย่างไร สิ่งที่เปลี่ยนคือรูปร่างของการกระจาย ค่ามัธยฐานของ challenge เดียวอยู่ที่ 0.69 เท่าของค่าเฉลี่ย ส่วนสี่ challenge ย่อยจะดันค่ามัธยฐานไปอยู่ราว 0.92 เท่าของค่าเฉลี่ยและทำให้หางสั้นลง ดังนั้นที่ความยากเท่ากัน การแบ่งทำให้การแก้ทั่วไปช้าลงราวหนึ่งในสาม และลด p90 ลงราวหนึ่งในสี่ ตารางด้านบนตรึงค่ามัธยฐานไว้แทน ซึ่งทำให้แบบแบ่งใช้ความยากน้อยลง 25% และผู้โจมตีต้องทำงานน้อยลง 25% ต่อการแก้หนึ่งครั้ง overhead ของวิดเจ็ตเองมีน้อย worker จะตรวจทุก 16 มิลลิวินาทีว่าต้องหยุดหรือไม่ ซึ่งเป็นตัวกำหนดว่าการส่งต่องานระหว่าง challenge ย่อยจะนานได้สูงสุดเท่าใด

เอนจินของเบราว์เซอร์

บิลด์ wasm ทำงานได้ราว 60% ของความเร็วเนทีฟ บน worker เดียวเอนจินหลักทั้งสามเร็วใกล้เคียงกัน แต่เมื่อใช้ทุกคอร์ Safari จะตามหลัง วัดบน M3 เครื่องเดียวกันในรอบเดียวกัน โดยเบราว์เซอร์แต่ละตัวรันแบบ headless หรืออยู่หน้าสุด:

เอนจิน	1 worker	8 worker	การถอยไปใช้โหมดตีความ
Chrome 153	440 KH/s	2050 KH/s	94 KH/s
Firefox 156	420 KH/s	1850 KH/s	105 KH/s
Safari 27.2	410 KH/s	1480 KH/s	105 KH/s

บน worker เดียว ทั้งสามต่างกันไม่เกิน 5% บนแปด worker Safari ทำได้ราว 70% ของอัตราของ Chrome ดังนั้นให้ตั้งความยากโดยอิง Safari ที่ d = 1,000,000 เวลาเฉลี่ยจะอยู่ราว 0.5 วินาทีบน Chrome และ 0.7 วินาทีบน Safari

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

โทรศัพท์มือถือ

ค่าเริ่มต้นบนโทรศัพท์จริงผ่าน BrowserStack เครื่องละ 15 ครั้ง และ 30 ครั้งสำหรับ Vivo ทุกรอบเริ่มจากหน้าที่เพิ่งโหลดใหม่ เหมือนผู้เยี่ยมชมที่เพิ่งเข้ามา หลังจากหน้าเว็บรัน HashWX ไปแล้วหนึ่งนาที Pixel 6 ใช้เวลาต่อการแก้หนึ่งครั้งน้อยลง 24% และ Vivo น้อยลง 29% ดังนั้นการวัดที่วอร์มอัปก่อนจะได้ตัวเลขดีกว่าในตารางนี้

อุปกรณ์	ระบบ	ทุกคอร์	ค่ามัธยฐาน	ช้าที่สุด
Galaxy S24	Android 14	1238 KH/s	1.1 วินาที	1.8 วินาที
Pixel 9	Android 15	837 KH/s	1.4 วินาที	2.0 วินาที
Pixel 6	Android 12	746 KH/s	1.9 วินาที	2.4 วินาที
iPhone 15	iOS 17	ไม่ได้วัด	1.9 วินาที	4.3 วินาที
iPhone 12	iOS 17	620 KH/s	2.0 วินาที	3.3 วินาที
iPhone 13	iOS 15	678 KH/s	2.2 วินาที	4.1 วินาที
iPhone SE 2022	iOS 15	588 KH/s	2.4 วินาที	4.0 วินาที
Redmi Note 11	Android 11	456 KH/s	2.4 วินาที	4.8 วินาที
Galaxy M32	Android 11	444 KH/s	2.8 วินาที	6.1 วินาที
Vivo Y21	Android 11	316 KH/s	5.9 วินาที	11.0 วินาที

การแก้แต่ละครั้งรวมการรับส่งข้อมูลไป-กลับกับเซิร์ฟเวอร์ทดสอบสองครั้ง โดยค่ามัธยฐานของแต่ละเครื่องอยู่ที่ 80 ถึง 190 มิลลิวินาที Vivo ซึ่งเป็น Android ราคาประหยัดใช้เวลาราวสิบเท่าของเดสก์ท็อป M3 ถ้าทราฟฟิกส่วนใหญ่ของคุณมาจากมือถือ ให้ลดความยากลง เวลาแก้แปรผันตรงกับความยาก ดังนั้น 500,000 จะทำให้ส่วนที่ใช้คำนวณของตัวเลขทุกตัวในตารางนี้ลดลงราวครึ่งหนึ่ง

ไคลเอนต์ที่ไม่มี WebAssembly แก้ HashWX ไม่ได้เลยและจะได้รับข้อผิดพลาด ถ้าคุณต้องรองรับพวกเขา ให้ใช้ proof of work แบบ SHA-256 ซึ่งมีทางถอยเป็น JS ล้วน บน iPhone วิดเจ็ตต้องใช้ iOS 15 ขึ้นไป

สิ่งที่ HashWX ไม่ได้ป้องกัน

เหมือนกับที่ RSW ป้องกันไม่ได้: ชิปเฉพาะทาง FPGA หรือ ASIC ที่สร้างมาเพื่อสิ่งนี้ยังเอาชนะ CPU ได้อยู่ดี ในเชิงเศรษฐศาสตร์มันไม่คุ้มกับการทำฟาร์ม CAPTCHA เพราะ ASIC มีต้นทุนออกแบบหลายล้าน แต่นี่ก็ไม่ใช่การรับประกันเชิงการเข้ารหัสลับ

และมันก็หยุดฟาร์มที่ใช้คนแก้ไม่ได้ ทั้งตอนนี้และตลอดไป proof of work ทำได้แค่ดันต้นทุนต่อคำขอให้สูงขึ้น ใช้มันคู่กับ challenge แบบ instrumentation เพื่อให้ต้องมีสภาพแวดล้อมเบราว์เซอร์จริงด้วย

ลองใช้งาน

API ของ cap-core มีเอกสารอยู่ที่ challenge แบบ HashWX ตัววิดเจ็ตตรวจจับการตอบกลับแบบ format 2 ได้เอง แค่อัปเกรดเซิร์ฟเวอร์ก็พอ

บน Cap Standalone HashWX เป็นค่าเริ่มต้นของคีย์ที่สร้างใหม่ และสลับได้รายคีย์ในแดชบอร์ด