Wall of Text #5: Internet Scale List Comprehension

ในทีมผมมีคนแนะนำ Codewars มา ผมก็เลยเอาไปปล่อยต่อให้น้องเค้าเล่น ซึ่งมันสนุกมาก

เวลาทำโจทย์ใน Codewars ผ่าน มันจะให้ดูว่าคนอื่นแก้โจทย์นี้อย่างไร ซึ่งถ้าเป็น Python เรามักจะเห็นเฉลยระดับบรรทัดเดียวออก เช่น

def find_it(seq):
    return [i for i in seq if seq.count(i) % 2 != 0]

โค้ดนี้เรียกว่า List Comprehension ซึ่งสำหรับมือใหม่อาจจะดูซับซ้อน ผมเองก็เขียน Python มาประมาณ 3-4 ปีก่อนที่จะเริ่มใช้เป็น

List Comprehension ประกอบด้วยคอนเซปต์จาก Functional Programming 2 ตัว คือ Map และ Filter

Map

Map คือการเปลี่ยนทุกสมาชิกของ List ให้เป็นค่าใหม่ โดยเรียกฟังค์ชั่นที่กำหนดไว้กับสมาชิกทุกตัว แล้วเอาคำตอบที่ได้แทนค่าเดิม ดังนั้นผลลัพท์ของ Map จะมีจำนวนสมาชิกเท่ากับค่าตั้งต้นเสมอ

ยกตัวอย่างเช่น ถ้ากำหนดฟังค์ชั่นคือ ยกกำลังสอง แล้ว Map function นี้ลงบน [1, 2, 3, 4] ผลลัพท์ที่ได้คือ [1, 4, 9, 16]

Filter

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

ยกตัวอย่างเช่น ถ้ากำหนดฟังค์ชั่นคือ ทดสอบว่าเป็นเลขคู่ แล้ว Map ลงบน [1, 2, 3, 4, 5] ผลลัพท์ที่เหลืออยู่คือ [2, 4]

ในหลายๆ ภาษา กระบวนการ Map กับ Filter นี้จะแยกกันเป็นสองคำสั่ง เช่นในภาษา JavaScript [1,2,3].map((x) => x*2).filter((x) => x<5) แต่ใน Python เราสามารถรวบเป็น List Comprehension ครั้งเดียวได้เพื่อความสะดวก

Reduce

โดยปกติแล้วฟังค์ชั่นตระกูลนี้นอกจาก Map – Filter แล้วยังมักจะมี Reduce ด้วย (ซึ่ง List Comprehension ทำไม่ได้)

Reduce คือการนำสมาชิก 2 ตัวเข้ามารวมกันเหลือค่าเดียว เช่น ถ้าหากต้องการหาผลรวมของ [1, 2, 5] เราสามารถใช้ reduce function คือ x+y แล้วระบบจะรันฟังค์ชั่นนี้จนครบทุกสมาชิกให้เอง คือ

  • x=1, y = 2; 1+2 = 3
  • x=3, y = 5; 3+5 = 8
  • คำตอบสุดท้ายคือ 8

คำสั่ง Reduce ใน Python 2 คือ reduce() และ Python 3 ถูกย้ายไปไว้ใน functools.reduce() ด้วยเหตุผลว่าเราสามารถใช้ For loop แทนกันได้และอ่านเข้าใจง่ายกว่า

MapReduce

กระบวนการ Map – Reduce – Filter นี้ทรงพลังมาก ขนาด Google ที่มีข้อมูลมหาศาลก็ยังใช้กระบวนการนี้ประมวลผลข้อมูลบางอย่างอยู่

สาเหตุที่มันทรงพลังมาก ก็เพราะมันทำให้ปัญหานี้สามารถกระจายงานไปหลายๆ เครื่องพร้อมกันได้

ยกตัวอย่างเช่น ถ้าหากเราต้องการทำโปรแกรมนับคะแนนจากภาพบัตรเลือกตั้ง วิธีก็คือ

  1. Map – แปลงภาพบัตรเลือกตั้งเป็นพรรคที่เลือก
  2. Filter – กรองบัตรเสียออก
  3. Reduce – รวมคะแนนเลือกตั้งจาก Map

วิธีนี้จะสังเกตว่าในขั้นตอน Map-Filter ไม่มีใครต้องรอใคร ทำให้เรากระจายงานได้ง่ายมาก

ทั้งนี้ MapReduce ที่ใช้ในงาน BigData จะแตกต่างกับ Map-Filter-Reduce อยู่เล็กน้อยเพราะ Map จะมีหน้าที่ของ Filter ไปด้วย โดยในแต่ละ Input Map อาจจะคืนค่ามากกว่า 1 ก็ได้ หรือไม่คืนค่าเลยก็ได้ (แปลว่า filter ทิ้ง) มันจึงจะหน้าตาประมาณนี้

def map_ballot(ballot_img):
    result = ocr(ballot_img)
    if result is not None:
        emit({result: 1})

จากโค้ดด้านบน เราสามารถเรียก emit หลายๆ ครั้งได้ถ้าหากต้องการ output หลายๆ ค่า หรือถ้า result เป็น None จะไม่มีการเรียก emit ก็คือ input นี้จะถูก filter ทิ้งนั่นเอง

Implementing libsodium Sealed Box

พอดีมี project ที่จะใช้ Sealed Box เลยได้นั่ง implement ให้กับภาษาที่ใช้งานอยู่ เลยอยากเอามาเล่าให้ฟังครับ

อะไรคือ libsodium

ถ้าเคยเขียนโปรแกรมที่ต้องใช้การเข้ารหัสข้อมูล น่าจะรู้จักกับ OpenSSL ครับ หรือถ้าใช้ PHP อาจจะเคยผ่านตากับ mcrypt ซึ่งสองตัวนี้เป็น library ที่รวบรวม algorithm เข้ารหัสไว้มากมายให้เราเลือกใช้

ปัญหาคือทางเลือกไม่ใช่เรื่องดีครับ เพราะกลายเป็นว่าโปรแกรมเมอร์จะต้องศึกษาดูก่อนว่า Algorithm ตัวไหนปลอดภัยบ้าง และแถมบางที library ก็ไม่ตรงปกซะเอง

นักวิทยาการรหัสลับ นำโดยคุณ Daniel J. Bernstein (djb) ผู้คิดค้น algorithm Ed25519/Poly1305/Salsa20 ที่กำลังมาแรงในช่วงนี้ ก็เลยคิดพัฒนาไลบรารีใหม่เข้ามาที่จะทำให้เข้ารหัสเป็นเรื่องง่าย และเร็ว มีชื่อว่า NaCl (อ่านว่า salt) ย่อมาจาก Networking and Cryptography Library (อ่านที่มาได้ใน Paper นี้ ครับ ไม่มีแมทอะไรมากอ่านสนุกดี)

นอกจากนี้เค้ายังพัฒนา TweetNaCl ซึ่งเป็นไลบรารีที่ใช้งานได้เหมือน NaCl แต่ขนาดเล็กเพียง 140 ตัว * 100 tweets เท่านั้น ทำให้สามารถอ่านโค้ดทั้งหมดเพื่อตรวจสอบได้ง่าย (ปัจจุบันมีการ port ไปหลายๆ ภาษาอีกด้วย เช่น Python, JavaScript) ทั้งนี้ความแตกต่างคือ TweetNaCl อาจจะทำงานช้ากว่า

ปัญหาคือ NaCl นั้นลงยากพอสมควร ทาง OpenDNS ก็เลยเอา NaCl ไปจัดระเบียบใหม่ให้นำไปใช้ได้ง่ายขึ้นอีก โดยเรียกไลบรารีใหม่นี้ว่า Sodium

สำหรับการใช้งานของ NaCl/Sodium นั้นจะเปลี่ยนคำถามใหม่จาก “ต้องการเข้ารหัสด้วย algorithm อะไร” เป็น “ต้องการความปลอดภัยแบบไหน” ตัวอย่างเช่น

  1. ถ้า Alice ต้องการส่งข้อความลับให้เฉพาะ Bob ก็ใช้ Box (authenticated encryption) ซึ่งเมื่อได้รับข้อความแล้ว Bob ยังสามารถยึนยันได้อีกด้วยว่า Alice เป็นผู้เขียนข้อความนี้จริง และข้อความไม่ถูกแก้ไขระหว่างทาง
  2. ถ้าต้องการส่งข้อความที่เข้ารหัสโดยใช้ password ก็ใช้ Secret box (authenticated encryption)
  3. ถ้าไม่ต้องการเข้ารหัสแต่ต้องการยึนยันว่าข้อความนี้เราเขียนจริง โดยใช้ระบบกุญแจสาธารณะ ก็ใช้ Sign (public-key signature)

จะเห็่นว่าเราไม่จำเป็นต้องทราบว่าด้านหลังมันทำงานยังไง ใช้ algorithm อะไรเลยด้วยซ้ำ อ่านรายละเอียดแต่ละ abstraction แล้วถ้าตรงกับโจทย์ก็เลือกใช้ได้ทันที

อะไรคือ Sealed Box

ทีนี้สิ่งที่ผมสนใจคือ Sealed box ครับ ซึ่งเป็นหนึ่งใน Security model ที่มีใน libsodium แต่มันพิเศษคือเป็นตัวที่ libsodium สร้างขึ้นมาเอง ไม่มีใน NaCl ปกติ

Sealed box จะเหมือนข้อ 1 ด้านบน คือใช้ส่งข้อความลับหาผู้รับที่เจาะจงและรู้ public key ของเค้า (เช่นส่งหาคุณ Bob) แต่ต่างกันคือเราไม่ต้องการยึนยันตัวผู้ส่งด้วย (ในตัวอย่างด้านบนคือ Alice ไม่ต้องการให้รู้) ซึ่งเราใช้ Box ปกติทำไม่ได้เพราะ Box จะต้องระบุ public key + secret key ของผู้รับและผู้ส่ง

ปัญหาคือพอมันเป็นสิ่งที่มีใน libsodium แล้ว ไลบรารีที่เอา NaCl ไปใช้ก็จะไม่ค่อยมี sealed box ให้ใช้ ซึ่งในหลายๆ ไลบรารีก็จะมี feature request เรื่องนี้อยู่

แกะ Sealed Box

วิธีแก้ปัญหาก็ไม่ยากครับ ไม่มีก็เขียนใช้เองซะสิ! แต่เราคงต้องแกะซอร์สซะก่อน

ซอร์ส libsodium จัดไว้ค่อนข้างง่ายครับ หาเจอไม่ยาก ไฟล์ที่เราต้องการคือ libsodium/src/libsodium/crypto_box/crypto_box_seal.c

พออ่านโค้ดใน crypto_box_seal แล้วก็จะพบว่าจริงๆ แล้ว Sealed box ก็คือ box ประเภทหนึ่งครับ ซึ่งจะสร้าง public และ private ของผู้ส่งขึ้นมาใหม่ทุกครั้ง แล้วก็ใช้ Box ปกติเข้ารหัสได้เลย จากนั้นเวลาส่งข้อมูลก็ให้ส่ง public key นำไปก่อน แล้วตามด้วย Box

ที่น่าสนใจคือ Nonce ครับ ใน docs ของ Box จะบอกว่าการส่งข้อความจะต้องมี Nonce ทุกครั้ง (ถ้าใครอ่านตำรา crypto มา อาจจะรู้จักกับ IV เจ้า Nonce นี่ก็คือ IV ล่ะครับ แต่ต่างกันคือ NaCl อนุญาตให้ใช้ string ใดๆ เป็น Nonce ได้ ขอแค่ห้ามใช้ซ้ำกัน ต่างกับ IV ตรงที่ IV จะต้องคาดเดาไม่ได้ด้วย) แต่การสร้าง Nonce ของ Sealed box น่าสนใจมากครับ คือแทนที่จะสุ่ม Nonce มา เราก็พบว่า Public key เราสุ่มใหม่ทุกรอบอยู่แล้ว ก็เลยเอา public key นั้น ต่อกับ public key ผู้รับ เข้า Hash function ก็จะได้ Nonce เลยที่ไม่ซ้ำแน่นอน และไม่จำเป็นต้องส่งไปด้วยเพราะผู้รับก็ทราบ public key ทั้งหมดอยู่แล้ว

อีกจุดนึงของ Nonce generation ที่น่าสนใจคือมันใช้ Hash function ใหม่ล่าสุดอย่าง BLAKE2 ครับ ข้อดีของเค้าคือสามารถกำหนดความยาวของแฮชเองได้ ไม่เหมือน SHA-256/512 ที่กำหนดความยาวไว้ชัดเจน แน่นอนว่าในเคสนี้เราก็กำหนดให้ยาวเท่ากับ Nonce ที่ Box ต้องการได้เลย

สุดท้ายแล้วผมก็พบว่าไม่ต้องอ่านโค้ดก็ได้ ใน docs เค้าก็เขียนไว้ชัดเจนแล้วว่ามันคือ ephemeral_pk ‖ box(m, recipient_pk, ephemeral_sk, nonce=blake2b(ephemeral_pk ‖ recipient_pk)) *facepalm* (‖ แปลว่าต่อ string)

Implement ใน JavaScript

ทีนี้ก็ได้เวลา implement ครับ ใน project ที่ผมจะทำ client side จะเข้ารหัสข้อความไปให้ server ซึ่งก็แน่นอนว่าฝั่ง client เราจะต้องใช้ JavaScript

ใน JavaScript ก็มีหลาย library ที่ใช้ libsodium ครับ แม้แต่ libsodium เองก็ยังมี official release ที่ใช้ Emscripten compile เป็น JavaScript ให้เลย แต่ปัญหาคือมันจะใหญ่มากและเปลือง memory ก็เลยตัดสินใจใช้ pure JavaScript implementation อย่าง TweetNaCl.js ซึ่งตัวนี้โดน Security audit มาแล้วด้วยซ้ำ และผลการ Audit คือ “ยอดเยี่ยม ไม่เจออะไรไม่ดีเลย” เป็นเรื่องที่หายากมากๆ

เวลาเขียนตัวนี้ก็ไม่ยากครับ JavaScript ยุคใหม่มี Fixed size array อย่าง Uint8Array แล้ว ก็ map จาก C ลงไปได้เลย แต่เขียนไปสักพักก็จะเจอปัญหาว่าไม่มี BLAKE2!

คือ NaCl ของแท้ๆ เนี่ยครับ hash function ที่เค้าเลือกใช้จะเป็น SHA-512 แต่ใน NaCl จะเปลี่ยนเป็น BLAKE2 ฉะนั้นก็ไม่มีทางเลือก เราต้องลง library ที่ทำ BLAKE2 ได้

ก็ปรากฏว่า BLAKE2 มีสองแบบครับ คือ BLAKE2s ที่มี library BLAKE2s.js และ BLAKE2b ที่มี library BLAKE.js ทำไว้ ตอนแรกก็เลือกผิดตัวไป เสียเวลาเขียนใหม่เล็กน้อย

(สำหรับความแตกต่างคือ BLAKE2s จะ optimize สำหรับ 32 bit ครับ และ BLAKE2b optimize สำหรับ 64 bit ผลลัพท์ไม่เหมือนกันใช้สลับกันไม่ได้นะครับ)

สุดท้ายก็ได้ Library ออกมาครับอย่าง tweetnacl-sealed-box ไปจิ้มจาก npm ได้เลย

Implement ใน Python

สำหรับฝั่ง server ผมใช้ Django ซึ่งสำหรับภาษา Python นั้นก็มี libsodium binding หลายตัวครับ เดิมทีผมใช้ PyNaCl อยู่ แต่อยากจะย้ายเป็นตัวอื่นที่มี wheel จะได้ build ไวๆ (มันเป็น Docker ครับ build นานเสียเวลา)

ตัวที่เลือกใช้ก็คือ libnacl ซึ่งเลือกจากว่ามันใช้ใน Salt ที่เป็น Server automation tool เจ้าดังตัวนึง (แต่เอาเข้าจริงเหมือนเค้าจะไม่ค่อย maintain libnacl เท่าไรนะ)

สำหรับ Implementation อันนี้ไม่ยากครับ เพราะ libnacl นั้นจะไปเรียก sodium.so ของแท้ๆ อยู่แล้ว เราก็แค่เขียน ctypes definition ให้มัน ก็จบ แต่ครั้นจะส่งแพทช์ไปแบบนี้เลยก็คงจะไม่ดีเท่าไร เลยต้องเขียน Abstraction ให้เค้าด้วย และ documentation ซึ่งก็ไม่รู้จะเขียนอะไรดี เลยก๊อปอีกหน้านึงมาแก้ซะเลย 555

สรุป

Sealed box เป็น design ที่น่าสนใจครับ คือเค้าพยายาม design ของใหม่ โดยใช้ของเดิมที่มีอยู่แล้ว เนื่องจากว่าของเดิมถูกพัฒนาโดยนักวิทยาการรหัสลับจึงมั่นใจได้ว่าปลอดภัย พอเป็นแบบนี้แล้วการจะ port ไปให้ภาษาอื่นๆ เลยค่อนข้างง่าย แต่ถ้า port ไป TweetNaCl ก็จะยุ่งยากนิดนึง

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