PSBT / Mining & Nonce / SHA-256 📦🎲#️⃣

อธิบายโดย : chatGPT 💬

👤 : PSBT คืออะไร และอยู่ในกระบวนการไหนของโครงสร้างการทำงานของ bitcoin

และรูปแบบของ raw transaction มีอะไรบ้าง

อยากเห็นขั้นตอนในการทำธุรกรรมปกติ และ ลำดับขั้นตอนการที่ miner ขุดเจอ block แล้วประกาศเข้า network

💬 : สรุปภาพรวม

Partially Signed Bitcoin Transaction (PSBT) คือฟอร์แมตมาตรฐานสำหรับเก็บและแลกเปลี่ยนข้อมูลของ Bitcoin transaction ที่ยังไม่เต็มรูป (unsigned หรือ partial-signed) เพื่อให้หลายอุปกรณ์หรือหลายฝ่ายสามารถร่วมเซ็นต์เดียวกันได้อย่างปลอดภัยและมีประสิทธิภาพ . PSBT ถูกนำมาใช้ในงาน multisig, CoinJoin, ช่องทาง Lightning และฮาร์ดแวร์วอลเล็ต โดยอยู่ระหว่างขั้นตอนการสร้าง transaction กับขั้นตอนสุดท้ายก่อน broadcast . ส่วน raw transaction คือโครงสร้างไบต์ที่ Bitcoin ใช้แลกเปลี่ยนบนเครือข่าย มีรูปแบบสำคัญ เช่น Legacy, SegWit และ Taproot ซึ่งประกอบด้วยฟิลด์หลักๆ ได้แก่ version, inputs, outputs, witness (ถ้ามี) และ locktime . ขั้นตอนทั่วไปของผู้ใช้คือ เลือก UTXO → สร้างและเซ็นต์ transaction → broadcast → อยู่ใน mempool แล้วรอให้ miner ดึงเข้า block . เมื่อ miner พบ nonce ที่ถูกต้อง จะประกาศ block ใหม่ด้วยข้อความ inv → ฝั่งรับส่ง getdata → ส่งข้อมูลบล็อก → ตรวจสอบและเพิ่มลง chain ก่อนจะประกาศต่อไปยังโหนดอื่น ๆ .

PSBT คืออะไร

คำนิยามทั่วไป

• PSBT ย่อมาจาก Partially Signed Bitcoin Transaction เป็นมาตรฐานที่ระบุวิธีจัดเก็บ transaction ที่ยังไม่เซ็นต์ครบถ้วน พร้อม metadata ช่วยให้หลายเครื่องมือหรืออุปกรณ์สามารถส่งต่อกันไปเซ็นต์ได้โดยไม่ต้องเปิดเผยคีย์ส่วนตัว .

• PSBT ถูกกำหนดใน BIP-174 ซึ่งอธิบายโครงสร้างเป็นชุดของ key-value maps แบ่งเป็น global, input, และ output maps เพื่อเก็บข้อมูลที่จำเป็นสำหรับการเซ็นต์และตรวจสอบต่อไป .

ข้อดีและการใช้งาน

• Interoperability: ช่วยให้วอลเล็ตหลายค่ายและซอฟต์แวร์ต่างๆ สามารถร่วมกันสร้างและเซ็นต์ transaction ได้อย่างราบรื่น .

• Multi-signature & CoinJoin: จำเป็นสำหรับ multi-sig, CoinJoin, CoinSwap และ PayJoin เนื่องจากต้องใช้ลายเซ็นต์จากหลายฝ่าย .

• Offline Signing: เอื้อให้ฮาร์ดแวร์วอลเล็ตหรืออุปกรณ์แยกออฟไลน์เซ็นต์ transaction ได้ปลอดภัย โดยวอลเล็ตออนไลน์สร้าง PSBT ส่งต่อให้อุปกรณ์เซ็นต์ แล้วจึงรวมลายเซ็นต์กลับมา .

PSBT ในโครงสร้างการทำงานของ Bitcoin

1. Wallet / Creator: สร้าง unsigned transaction แบบ raw แล้วแปลงเป็น PSBT พร้อม metadata เช่น UTXO details, scriptPubKey, sighash type .

2. Signer(s): PSBT ถูกส่งให้แต่ละ signer (เช่น ฮาร์ดแวร์วอลเล็ต หรือ ผู้ถือ multi-sig keys) เพิ่ม partial signature ลงใน input maps .

3. Combiner / Finalizer: เมื่อได้ลายเซ็นต์ครบทุกฝ่าย ก็รวม PSBT แต่ละฉบับเข้าด้วยกัน, ตรวจสอบ และแปลงกลับเป็น fully signed raw transaction พร้อม broadcast ได้ .

4. Node / Broadcaster: รับ raw transaction ที่เซ็นต์เรียบร้อยแล้วจาก PSBT แล้วกระจายไปยังเครือข่าย Bitcoin เพื่อเข้าสู่ mempool .

รูปแบบของ Raw Transaction

โครงสร้างไบนารี

ตามนิยามของ Bitcoin Core, raw transaction คือไบต์ซีรีส์ที่เครื่องขุดและโหนดส่งต่อกัน ประกอบด้วย :

4 bytes version

[optional 2 bytes] flag (0001 หมายถึงมี witness data)

VarInt จำนวน inputs (vin)

... inputs แต่ละ input: prev_txid (32B), vout (4B), scriptSig length + scriptSig, sequence (4B)

VarInt จำนวน outputs (vout)

... outputs แต่ละ output: value (8B), scriptPubKey length + scriptPubKey

[optional witnesses]

4 bytes locktime

ประเภทของ Transaction Scripts

1. P2PKH (Legacy): OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG

2. P2SH: OP_HASH160 <scriptHash> OP_EQUAL

3. P2WPKH (SegWit v0): witness version 0 + program 20-byte pubKeyHash

4. P2WSH (SegWit v0): witness version 0 + program 32-byte scriptHash

5. P2TR (Taproot, SegWit v1): witness version 1 + 32-byte public key

ขั้นตอนในการทำธุรกรรมปกติ

1. สร้างและเซ็นต์ Transaction

• ผู้ใช้ในวอลเล็ตเลือก UTXO และกำหนดที่อยู่ปลายทาง พร้อมคำนวณค่าธรรมเนียม → สร้าง raw transaction แล้วเซ็นต์ทุกรายการ input ด้วย private key → (ถ้าใช้ PSBT ก็แปลงเป็น PSBT ก่อนและส่งต่อให้ signer อื่น) .

2. Broadcast และกระจายสู่ Mempool

• วอลเล็ตส่ง raw transaction ไปยังโหนดใกล้เคียง → โหนดตรวจสอบเงื่อนไขเบื้องต้น (เช่น รูปแบบ script, ค่าธรรมเนียม, UTXO ยังไม่ถูกใช้) → ถ้า valid ให้เพิ่มเข้า mempool แล้ว relay ไปยังเพื่อนบ้าน .

3. อยู่ใน Mempool รอการเลือก

• แต่ละโหนดมี mempool ของตัวเอง เก็บ transaction รอให้ miner ดึงไปจัดกลุ่ม .

ลำดับขั้นตอนเมื่อ Miner ขุดเจอบล็อกใหม่

1. รวบรวม Transaction และสร้าง Candidate Block

• Miner รันโหนด เตรียม candidate block header: เวอร์ชัน, prev_block_hash, merkle_root (คำนวณจาก tx ที่เลือก), timestamp, target bits, nonce (ยังไม่รู้ค่า) .

2. Proof-of-Work

• Miner เปลี่ยนค่า nonce อย่างต่อเนื่องและ hash header ด้วย SHA256(SHA256(header)) จนได้ค่า hash ต่ำกว่า target .

3. ประกาศบล็อกใหม่ (Block Propagation)

1. inv: Miner ส่งข้อความ inv ไปยังเพื่อนบ้าน เพื่อแจ้งว่ามีบล็อกใหม่ (hash ของ block header) .

2. getdata: โหนดที่รับ inv แต่ยังไม่มีบล็อกนี้ จะส่ง getdata กลับมาเพื่อขอบล็อกฉบับเต็ม .

3. block: Miner หรือโหนดอื่นที่มีบล็อก ส่งข้อความ block พร้อมข้อมูลบล็อกทั้งหมดให้เพื่อนบ้าน .

4. Verify & Validate: แต่ละโหนดตรวจสอบความถูกต้องของ block และแต่ละ transaction ภายใน (consensus rules) ถ้าผ่าน ก็เพิ่มบล็อกเข้า chain และลบ tx ที่ถูกใช้แล้วออกจาก mempool .

5. Relay ต่อเนื่อง: โหนดเหล่านั้น relay inv/getdata/block ต่อไปจนทั่วเครือข่าย .

อ้างอิงเพิ่มเติม

1. BIP-174 (PSBT) Spec — GitHub

2. Bitcoin Developer Guide: Transactions & P2P Networking

3. Bitcoin Wiki: Transaction Structure

4. River.com: PSBT Overview

5. Bitcoin Optech: PSBT Topics

6. Cointelegraph: Bitcoin Mempool

7. Leather.io: Bitcoin Transaction & Mining

8. OSL: Bitcoin Mempool Fundamentals

9. Research PDF: Block Propagation

10. Bitcoin StackExchange: PSBT Definition

👤 : ขั้นตอนนี้ : Miner เปลี่ยนค่า nonce อย่างต่อเนื่องและ hash header ด้วย SHA256(SHA256(header)) จนได้ค่า hash ต่ำกว่า target , หมายถึง ถ้าเราทำ solo mining แล้ว mining node ของเราก็จะ hash ตามจำนวนกำลังประมวลผลที่ ASIC farm เรามีใช่ไหม หมายถึง ณ เวลานั้น เอาค่าทุกอย่างใน mempool มา random nonce และ hash ได้ใกล้ target ระบบก็จะปลดล็อคเข้าสู่ mining node ของเราที่ผูกกับ address ไว้ใช่ไหม / และเรื่องนี้จะไปต่อสู่เรื่อง mining pool ได้ใช่ไหม

- inv ย่อมาจากอะไร

💬 : สรุปภาพรวม

เมื่อเราทำ solo mining ระบบจะใช้พลังประมวลผลจาก ASIC farm ของเรา “ขุด” โดยรับบล็อกเท็มเพลตจาก bitcoind (ผ่าน RPC เช่น getblocktemplate) ที่ดึงรายการธุรกรรมจาก mempool มาสร้างเป็น candidate block header ขนาด 80 ไบต์ พร้อม target difficulty จากนั้นฮาร์ดแวร์จะปรับเปลี่ยนค่า nonce (และ extra nonce ใน coinbase) ซ้ำไปมาเพื่อหา hash ที่ต่ำกว่า target เมื่อพบ ระบบจะส่ง header กลับมาให้ซอฟต์แวร์เติมข้อมูลบล็อกเต็มส่งเข้าเครือข่าย ซึ่งกระบวนการเดียวกันนี้ก็ถูกใช้ใน mining pool แต่เปลี่ยน target ให้ต่ำลงเพื่อส่ง “shares” กลับไปจ่ายค่าตอบแทนตามส่วนแบ่งพลังงาน และในโพรโทคอล P2P ของ Bitcoin เมื่อใดมีบล็อกหรือ transaction ใหม่ก็จะประกาศด้วยข้อความ inv (ย่อมาจาก inventory) เพื่อให้โหนดอื่นขอข้อมูล (getdata) ต่อไป

1. Solo Mining ทำงานอย่างไร

1.1 เตรียมบล็อกเท็มเพลต

1. ดึงเท็มเพลต: ซอฟต์แวร์ขุด (เช่น BFGMiner, CGMiner) เรียก RPC getblocktemplate จาก bitcoind เพื่อรับข้อมูลบล็อกเท็มเพลต ซึ่งประกอบด้วย

• รายการธุรกรรมจาก mempool

• public key สำหรับสร้าง coinbase ที่จะจ่ายรางวัลให้กับที่อยู่ของเรา

• ข้อมูล header อื่นๆ ได้แก่ เวอร์ชันบล็อก, hash ของบล็อกก่อนหน้า, bits (target difficulty)

1. สร้าง Merkle root: ซอฟต์แวร์คำนวณ Merkle root จากรายการธุรกรรม และฝัง extra nonce ในฟิลด์ coinbase เพื่อให้สามารถเปลี่ยน Merkle root ได้มากกว่าด้วย nonce เดียวกัน

1.2 การขุดด้วย ASIC

• ส่ง header ให้ ASIC: ซอฟต์แวร์ขุดส่ง header 80 ไบต์ (เวอร์ชัน, prev_hash, Merkle root, timestamp, bits, nonce) พร้อม target threshold ให้ฮาร์ดแวร์ ASIC

• วน nonce: ASIC ปรับค่า nonce และ (приจำเป็น) coinbase extra nonce ไม่หยุดจนกว่าจะได้ hash < target ซึ่งขึ้นกับ hash rate ของฟาร์ม (เช่น ฮาร์ดแวร์ 400 TH/s จะลองได้ 400 ล้านล้าน hash ต่อวินาที)

• พบค่า valid: เมื่อหา nonce ที่ได้ hash ถูกต้อง ฮาร์ดแวร์ส่ง header กลับมา ซอฟต์แวร์รวม header กับรายการธุรกรรมเป็นบล็อกเต็ม แล้วเรียก RPC submitblock หรือส่งผ่าน P2P เพื่อกระจายบล็อกไปยังเครือข่าย

2. Mining Pool vs Solo Mining

2.1 หลักการของ Mining Pool

• เท็มเพลตของพูล: Pooled mining คล้าย solo แต่พูลเซิร์ฟเวอร์จะตั้ง target threshold ของ shares ให้ต่ำกว่า network target หลายระดับ (เช่น 2⁸⁰×)

• ส่ง shares: Miner ส่ง header กับ nonce ที่ได้ hash < pool target กลับไปยังพูล เพื่อยืนยันปริมาณงานที่ทำ (“share”)

• จ่ายรางวัล: เมื่อพูลเจอบล็อกจริง (share ที่ < network target) พูลจะส่งบล็อกขึ้นเครือข่าย แล้วกระจายรางวัลให้สมาชิกตามจำนวน shares ที่แต่ละคนทำได้

2.2 ข้อดี–ข้อเสีย

แบบขุด	ข้อดี	ข้อเสีย
Solo Mining	ได้รางวัลเต็มถ้าเจอบล็อก	ความผันผวนสูง, อาจขุดนานมากกว่าจะเจอ
Pool Mining	รางวัลสม่ำเสมอ, ความผันผวนต่ำ	ได้ส่วนแบ่ง, ค่าธรรมเนียมพูลบ้าง

3. ข้อความ inv ใน P2P Protocol

• inv ย่อมาจาก “inventory” ใช้ในการประกาศรายการ objects (transaction หรือ block) ที่โหนดนั้นรู้จัก เพื่อให้เพื่อนบ้านตรวจสอบว่ามีหรือยัง แล้วจะขอข้อมูลต่อด้วย getdata

• โครงสร้างของ inv: ประกอบด้วยจำนวนรายการ (compactSize) ตามด้วย pairs ของ (type, hash) สูงสุด 50,000 รายการต่อข้อความ

• การใช้งานทั่วไป:

1. ประกาศบล็อกใหม่: เมื่อ miner ขุดเจอบล็อก พวกเขาส่ง inv type=MSG_BLOCK, hash=block_hash → เพื่อนบ้านขอด้วย getdata → ส่งบล็อกจริงด้วย block

2. เผยแพร่ transaction: wallet หรือ node ที่ได้รับ tx ใหม่ ส่ง inv type=MSG_TX, hash=txid → เพื่อนบ้านขอ tx ด้วย getdata → ส่งด้วย tx

สรุป:

• ใน solo mining ระบบจะสุ่มค่า nonce (+ extra nonce) บน header ที่สร้างจาก mempool transactions จนพบ hash < network target โดยใช้พลัง ASIC farm ของเรา

• เมื่อพบ ค่าส่ง block header กลับมาให้ซอฟต์แวร์รวมและ broadcast ทั้งนี้แนวคิดเดียวกันใช้กับ mining pool แต่เปลี่ยน target สำหรับ shares เพื่อแจกจ่ายรางวัลตามสัดส่วน

• เมื่อต้องการประกาศบล็อกหรือ transaction ใหม่ จะใช้ข้อความ P2P inv (inventory) เพื่อบอกเพื่อนบ้านให้ขอข้อมูลต่อด้วย getdata

👤 : - จากขั้นตอนนี้ : พบค่า valid: เมื่อหา nonce ที่ได้ hash ถูกต้อง ฮาร์ดแวร์ส่ง header กลับมา ซอฟต์แวร์รวม header กับรายการธุรกรรมเป็นบล็อกเต็ม แล้วเรียก RPC submitblock หรือส่งผ่าน P2P เพื่อกระจายบล็อกไปยังเครือข่าย , นั้น ระบบรู้ได้อย่างไรว่า valid ภายใน 10 นาที เราทำการ brute force nonce หรือ random nonce ?

💬 : สรุปภาพรวม

ในกระบวนการขุดบิตคอยน์ Miner จะ “เดาทาง” ค่า nonce ด้วยการลองค่าแบบ brute‐force (โดยทั่วไปคือเริ่มที่ 0, ตามด้วย 1, 2, 3… หรือบางกรณีอาจใช้ extra nonce และค่าอื่นผสม) แล้วคำนวณ SHA256(SHA256(header)) ทุกครั้งเพื่อตรวจว่าค่า hash ที่ได้ “ต่ำกว่า target” หรือไม่ ถ้าต่ำกว่าถือว่า valid และ block นั้นจะถูกส่งเข้าเครือข่ายต่อไปทันที การที่ระบบตั้งเป้าให้เจอบล็อก “เฉลี่ยทุก 10 นาที” มาจากการปรับ difficulty ทุก 2,016 บล็อก เพื่อให้เวลาระหว่างบล็อกเฉลี่ยใกล้เคียง 10 นาทีเสมอ

วิธีค้นหา nonce: Brute-force vs Random

Brute-force แบบ Sequential

• Miner มักเริ่มที่ nonce = 0 แล้วเพิ่มขึ้นทีละหนึ่ง ตรวจสอบ hash จนกว่าจะเจอค่าที่ SHA256(SHA256(header)) < target .

• เนื่องจากผลลัพธ์ของ SHA-256 ไม่สามารถคาดเดาได้จากค่าก่อนหน้า การเพิ่มทีละหนึ่งจึงเทียบเท่ากับการสุ่มทางสถิติ (pseudo-random) .

การใช้ Extra Nonce และ Randomization

• เมื่อ nonce (32-bit) หมดช่วง Miner จะปรับค่า extra nonce ในฟิลด์ coinbase เพื่อเปลี่ยน Merkle root แล้ววน nonce ใหม่อีกครั้ง .

• บาง implementation อาจใช้การสุ่ม (random) แทนการนับเพิ่ม แต่หลักการเหมือนกันคือ brute-force ค่าจนกว่าจะถูกต้อง .

การตรวจสอบความถูกต้อง (Validity)

• ทุกครั้งที่ได้ hash ใหม่ Miner จะเปรียบเทียบตัวเลขที่ได้กับ target difficulty ซึ่งเป็นค่าที่ต้องต่ำกว่าเพื่อให้บล็อกนั้น valid .

• เมื่อพบ hash < target Miner รวม header กับรายการธุรกรรมเป็นบล็อกเต็ม และเรียก RPC submitblock หรือส่งผ่าน P2P เพื่อเผยแพร่ block นั้นต่อไป .

ทำไมจึงเฉลี่ยที่ 10 นาที

• Bitcoin protocol ปรับ difficulty ทุก 2,016 บล็อก (ประมาณ 2 สัปดาห์) เพื่อรักษาเวลาการขุดเฉลี่ยที่ ~10 นาทีต่อบล็อก .

• เวลาเฉลี่ย 10 นาทีถูกเลือกเพื่อบาลานซ์ระหว่างความล่าช้าในการส่งบล็อกใหม่ และการเสียแรงงาน (wasted work) เมื่อเกิด chain split .

• อันที่จริง “10 นาที” เป็นค่าเฉลี่ยทางสถิติ (negative exponential distribution) ไม่ใช่เวลาบังคับ บล็อกอาจถูกขุดเร็วกว่าหรือนานกว่า 10 นาทีได้ .

สรุป

1. Miner ใช้วิธี brute-force (ส่วนใหญ่คือ sequential nonce) ผสมกับการปรับ extra nonce เพื่อค้นหา hash ที่ < target

2. ระบบรู้ว่า valid เมื่อ hash ที่ได้ SHA256(SHA256(header)) ต่ำกว่า target difficulty ซึ่ง node อื่นตรวจสอบได้ทันทีด้วยการ hash ซ้ำ

3. เป้าเฉลี่ย “10 นาที” มาจากการปรับ difficulty ทุก 2,016 บล็อก เพื่อรักษาอัตราการขุดเฉลี่ยและลด waste work

👤 : ช่วยแสดงตัวอย่างจริงของค่าที่ miner hash ได้ < target และค่า nonce ของ block นั้น ให้เห็นภาพออกหน่อยได้ไหม

ยังไม่ค่อยเข้าใจความหมายของคำว่าตำกว่า target ถ้างั้นทำไมไม่สุ่มค่าที่ต่ำๆไว้ก่อนเลยล่ะ

💬 : ตัวอย่างจริง (Block #500 000)

พิจารณาบล็อกหมายเลข 500 000 ซึ่งข้อมูลจาก Bitaps Explorer แสดงว่า :

• Block Hash:

00000000000000000024fb37364cbf81fd49cc2d51c09c75c35433c3a1945d04

• Nonce:

0x5cfc9955 (1556615829 decimal)

• nBits (compact target encoding):

0x18009645

การเปรียบเทียบ Hash กับ Target

1. ขั้นแรก แปลง nBits เป็น Target เต็มรูปแบบตามสูตร target = coefficient × 256^(exponent − 3)

2. • coefficient = 0x009645

   • exponent = 0x18 จึงได้ค่า

0x00964500000000000000000000000000000000000000000000000000

1. หรือเทียบเป็นตัวเลขขนาดใหญ่ (decimal)

2. เมื่อเปรียบเทียบ Hash ของบล็อก:

0x00000000000000000024fb37364cbf81fd49cc2d51c09c75c35433c3a1945d04

• Target:

0x0000000000000000009645000000000000000000000000000000000000000000

จะเห็นว่า

hash_value < target_value

จึงถือว่า Proof-of-Work ผ่านเงื่อนไขและบล็อกนี้จึงถูกยอมรับ

ทำไมไม่ “สุ่ม” ค่า Nonce ต่ำๆ ไว้ก่อน

1. SHA-256 ให้ผลลัพธ์แบบกระจายสม่ำเสมอ (Uniform Random) การเปลี่ยนค่า nonce เพียง 1 บิต จะทำให้ผลลัพธ์ของ SHA-256 เปลี่ยนไปในทางที่ดูสุ่มสิ้นเชิง ไม่มีความสัมพันธ์กันระหว่างค่า nonce และความใกล้เคียงของ hash กับ target

2. ไม่มีแนวโน้มว่าค่า nonce ต่ำจะให้ hash ต่ำกว่า target ทุกครั้งที่ลอง hash ด้วย nonce ใดๆ โอกาสในการสำเร็จเท่ากันหมด ไม่ว่าจะเป็น nonce = 0 หรือ nonce = 4 294 967 295 (2³²−1)

3. จึงต้อง “ลองทุกค่า” (Brute-force) หรือ “นับขึ้นทีละหนึ่ง” การนับเพิ่มแบบ sequential (0,1,2,…) เป็นวิธีที่ง่ายและเร็วที่สุดในการเปลี่ยน nonce และคำนวณค่า hash ใหม่ทุกครั้งจนเจอค่า valid

โครงสร้าง Block Header ที่เกี่ยวข้อง

บล็อกเฮดเดอร์มีความยาว 80 ไบต์ ประกอบด้วย :

4 bytes version

32 bytes prev_block_hash

32 bytes merkle_root

4 bytes timestamp

4 bytes nBits

4 bytes nonce ← ตัวเลขที่ miners ปรับเปลี่ยนเพื่อค้นหา hash ที่ < target

สรุป

• สำหรับบล็อกจริง (#500 000) ค่า nonce ที่ miners เจอคือ 0x5cfc9955 จึงให้ hash ที่ต่ำกว่า target ซึ่งถูกแสดงผ่าน nBits = 0x18009645

• ไม่มีประโยชน์ในการสุ่มค่า nonce ต่ำๆ ไว้ก่อน เพราะ SHA-256 ให้ผลลัพธ์ที่ดูสุ่มและกระจายสม่ำเสมอ “nonce ต่ำ” ไม่ได้เพิ่มโอกาสสำเร็จกว่าค่าอื่นๆ จึงต้อง brute-force ทุกค่า หรือใช้อัลกอริธึม sequential increment

👤 : ทำไม SHA-256 ให้ผลลัพธ์ที่ดูสุ่มและกระจายสม่ำเสมอ

💬 : สรุปภาพรวม

SHA-256 ถูกออกแบบให้ทำหน้าที่เป็น pseudo-random function และมี avalanche effect สูงสุด เพื่อให้ผลลัพธ์เปลี่ยนแปลงแบบสุ่ม สม่ำเสมอ และไม่ดูมีรูปแบบใด ๆ การออกแบบนี้อาศัยโครงสร้าง Merkle–Damgård ร่วมกับ Davies–Meyer compression function ซึ่งทำให้บิตเอาต์พุตแต่ละบิตขึ้นกับทุกบิตอินพุต บิตใดบิตหนึ่งเปลี่ยนก็สลับสถานะบิตเอาต์พุตถึง 50% โดยเฉลี่ย (avalanche) .

1. Avalanche Effect: “ทุกบิตขึ้นต่อทุกบิต”

1.1 ความหมายของ Avalanche Effect

• Avalanche effect คือคุณสมบัติของอัลกอริทึมเข้ารหัสหรือแฮชที่เมื่อเปลี่ยนอินพุตเพียงเล็กน้อย (เช่น พลิกบิตเดียว) เอาต์พุตจะเปลี่ยนแปลงอย่างมาก (ประมาณครึ่งหนึ่งของบิตทั้งหมด) .

• หากไม่มีคุณสมบัตินี้ นักวิเคราะห์สามารถคาดเดาความสัมพันธ์ระหว่างอินพุตกับเอาต์พุตได้ง่ายซึ่งเป็นช่องทางโจมตี เช่น collision attack, length extension attack หรือ preimage attack .

1.2 Strict Avalanche Criterion (SAC)

• SAC เป็นเงื่อนไขที่ระบุว่า “เมื่อเปลี่ยนบิตเดียวในอินพุต บิตเอาต์พุตแต่ละบิตควรเปลี่ยนสถานะด้วยความน่าจะเป็น 50%” .

• SHA-256 อาศัยการผสมผสานของ bitwise operations, modular addition, และ rotations ภายใน compression function เพื่อให้ผ่าน SAC ในทุกรอบของการคอมเพรสชั่น .

2. SHA-256 ในฐานะ Pseudorandom Function

2.1 Random Oracle Model

• ในการวิเคราะห์เชิงทฤษฎี SHA-256 มักถูกสมมติให้เป็น random oracle กล่าวคือฟังก์ชันสุ่มเต็มรูปแบบ ที่แจกแจงค่าเอาต์พุตอย่างเท่าเทียมกันในช่วง 0 ถึง 2²⁵⁶−1 .

• โมเดลนี้ช่วยให้พิสูจน์ความปลอดภัยของโปรโตคอลหลายชนิด รวมถึง HMAC, digital signatures และ zero-knowledge proofs .

2.2 HMAC-SHA256 เป็น PRF

• HMAC-SHA256 ได้รับการพิสูจน์ (หรือ conjectured) ว่าเป็น pseudo-random function family เมื่อใช้คีย์ลับ รักษาความลับของคีย์ได้ดีและผลลัพธ์มีการแจกแจงใกล้เคียงสุ่ม .

3. การออกแบบเชิงโครงสร้างของ SHA-256

3.1 Merkle–Damgård & Davies–Meyer

• SHA-256 ใช้ Merkle–Damgård construction และ Davies–Meyer compression function ที่ผสมค่าก่อนหน้า (chaining value) กับบล็อกข้อความโดยใช้ XOR และ modular addition .

• การวนรอบ (round) จำนวน 64 ครั้ง พร้อม constant แต่ละรอบ ทำให้เกิด diffusion สูง และป้องกันโจมตีทางคณิตศาสตร์ได้ดี .

3.2 Uniform Output Distribution

• เพราะโครงสร้างภายในให้เอฟเฟกต์ “butterfly” (Bitwise complex mixing) บิตเอาต์พุตจึงกระจายทั่วทั้งเวกเตอร์ 256 บิตแบบสมดุล ไม่มีโซนใดที่มีโอกาสเกิดน้อยหรือมากเป็นพิเศษ .

• ผล empiric พบว่า เมื่อพลิกอินพุต 1 บิต จะมีการเปลี่ยนสถานะเอาต์พุตเฉลี่ย ~128 บิต (50%) และการแจกแจงจำนวนบิตที่เปลี่ยนตามทฤษฎีเป็นแบบ Binomial, เข้าใกล้ Normal distribution เมื่อ n ใหญ่ขึ้น .

4. ทำไมจึงดูเหมือน “สุ่มเต็มที่”

1. Cryptographic Mixing

• bitwise XOR, modular addition, rotations ทำให้ความสัมพันธ์เชิงเส้นถูกทำลายทุกขั้นตอน .

1. Entropy Preservation

• ถ้าอินพุตมี entropy เพียงพอ (เช่น 256 บิตสุ่ม) เอาต์พุตก็จะมี entropy เกือบเท่ากับอินพุต เพราะ SHA-256 พยายาม “กระจาย” entropy ออกไปให้ทั่ว .

1. No Predictable Bias

• ไม่มีหลักฐานว่าพารามิเตอร์ compression function หรือ constant ต่างๆ ก่อ bias ในการแจกแจงของเอาต์พุต จึงเทียบเท่ากับการสุ่ม $U(0,2^{256}-1)$ .

อ้างอิง

1. Avalanche effect – Wikipedia

2. Cryptographic hash function – Wikipedia

3. SHA-2 family design – Wikipedia

4. Why hash functions produce random-looking output – Crypto.SE

5. Entropy preservation in hash functions – Crypto.SE

6. Impact of hash on PRNG randomness – Crypto.SE

7. Uniform distribution & truncated hash – Crypto.SE

8. Bit-flip statistics in SHA-256 – Crypto.SE

9. HMAC-SHA256 as PRF – Crypto.SE

10. Wide-pipe & diffusion in hash design – Wikipedia Merkle–Damgård