IMPL3.md (6223B)
1 # IMPL3: Packet Construction 2 3 **Module**: `Lightning.Protocol.BOLT4.Construct` 4 5 **Dependencies**: IMPL1 (Prim), IMPL2 (Types, Codec) 6 7 **Can run in parallel with**: IMPL4, IMPL5 (after IMPL1 and IMPL2 complete) 8 9 ## Overview 10 11 Implement onion packet construction from the sender's perspective. 12 13 ## Types 14 15 ```haskell 16 -- | Route information for a single hop. 17 data Hop = Hop 18 { hopPubKey :: !Secp256k1.PubKey -- node's public key 19 , hopPayload :: !HopPayload -- routing data for this hop 20 } deriving (Eq, Show) 21 22 -- | Session state accumulated during packet construction. 23 data SessionState = SessionState 24 { ssEphemeralSec :: !Secp256k1.SecKey -- current ephemeral private 25 , ssEphemeralPub :: !Secp256k1.PubKey -- current ephemeral public 26 , ssSharedSecrets :: ![SharedSecret] -- accumulated secrets (reverse) 27 , ssBlindingFactors :: ![BlindingFactor] -- accumulated factors (reverse) 28 } deriving (Eq, Show) 29 ``` 30 31 ## Main Functions 32 33 ### Packet Construction 34 35 ```haskell 36 -- | Construct an onion packet for a payment route. 37 -- 38 -- Takes a session key (32 bytes random), list of hops, and optional 39 -- associated data (typically payment_hash). 40 -- 41 -- Returns the onion packet and list of shared secrets (for error 42 -- attribution). 43 construct 44 :: BS.ByteString -- ^ 32-byte session key (random) 45 -> [Hop] -- ^ route (first hop to final destination) 46 -> BS.ByteString -- ^ associated data 47 -> Either Error (OnionPacket, [SharedSecret]) 48 49 -- | Errors during packet construction. 50 data Error 51 = InvalidSessionKey 52 | EmptyRoute 53 | TooManyHops -- > 20 hops typically 54 | PayloadTooLarge Int -- payload exceeds available space 55 | InvalidHopPubKey Int 56 deriving (Eq, Show) 57 ``` 58 59 ## Internal Functions 60 61 ### Session Initialization 62 63 ```haskell 64 -- | Initialize session state from session key. 65 -- Derives initial ephemeral keypair. 66 initSession 67 :: BS.ByteString -- ^ 32-byte session key 68 -> Maybe SessionState 69 70 -- | Compute shared secrets and blinding factors for entire route. 71 -- Iterates through hops, computing ECDH and blinding at each step. 72 computeSessionData 73 :: SessionState 74 -> [Secp256k1.PubKey] -- ^ hop public keys 75 -> Maybe SessionState -- ^ with all secrets/factors populated 76 ``` 77 78 ### Filler Generation 79 80 ```haskell 81 -- | Generate filler bytes that compensate for per-hop shifts. 82 -- 83 -- As each intermediate node shifts the payload left, the filler 84 -- ensures the packet maintains constant size without leaking 85 -- information about route position. 86 generateFiller 87 :: [SharedSecret] -- ^ shared secrets (excluding final hop) 88 -> [Int] -- ^ payload sizes per hop (excluding final) 89 -> BS.ByteString -- ^ filler bytes 90 ``` 91 92 Algorithm: 93 1. Start with empty filler 94 2. For each hop (forward order, excluding final): 95 - Extend filler by hop's payload size (zeros) 96 - Generate rho stream of length (filler size) 97 - XOR filler with stream 98 3. Result is filler that will "appear" after final hop processes 99 100 ### Payload Wrapping 101 102 ```haskell 103 -- | Wrap a single hop's payload into the onion. 104 -- 105 -- Called in reverse order (final hop first, origin last). 106 wrapHop 107 :: SharedSecret -- ^ shared secret for this hop 108 -> BS.ByteString -- ^ serialized payload (without length prefix) 109 -> BS.ByteString -- ^ current HMAC (32 bytes) 110 -> BS.ByteString -- ^ current hop_payloads (1300 bytes) 111 -> BS.ByteString -- ^ associated data 112 -> (BS.ByteString, BS.ByteString) -- ^ (new hop_payloads, new HMAC) 113 ``` 114 115 Algorithm: 116 1. Compute shift_size = bigsize_len(payload_len) + payload_len + 32 117 2. Right-shift hop_payloads by shift_size (drop rightmost bytes) 118 3. Prepend: bigsize(payload_len) || payload || hmac 119 4. Generate rho stream (1300 bytes) 120 5. XOR entire buffer with stream 121 6. Compute new HMAC = HMAC-SHA256(mu_key, hop_payloads || assoc_data) 122 123 ### Filler Application 124 125 ```haskell 126 -- | Apply filler to the final wrapped packet. 127 -- 128 -- Overwrites the tail of hop_payloads with filler bytes. 129 -- This must be done after wrapping all hops but before 130 -- computing the final HMAC. 131 applyFiller 132 :: BS.ByteString -- ^ hop_payloads (1300 bytes) 133 -> BS.ByteString -- ^ filler 134 -> BS.ByteString -- ^ hop_payloads with filler applied 135 ``` 136 137 ## Construction Algorithm 138 139 Full algorithm as pseudocode: 140 141 ``` 142 construct(session_key, hops, assoc_data): 143 1. session = initSession(session_key) 144 2. session = computeSessionData(session, map hopPubKey hops) 145 146 3. Extract from session: 147 - ephemeral_pub (for first hop) 148 - shared_secrets[0..n-1] 149 150 4. Compute payload sizes for each hop 151 5. filler = generateFiller(shared_secrets[0..n-2], sizes[0..n-2]) 152 153 6. Initialize: 154 - hop_payloads = random 1300 bytes (using pad key from last secret) 155 - hmac = 32 zero bytes (final hop sees zeros) 156 157 7. For i = n-1 down to 0: 158 payload_bytes = encodeHopPayload(hops[i].payload) 159 (hop_payloads, hmac) = wrapHop( 160 shared_secrets[i], payload_bytes, hmac, hop_payloads, assoc_data 161 ) 162 163 if i == n-1: 164 hop_payloads = applyFiller(hop_payloads, filler) 165 hmac = recompute HMAC after filler 166 167 8. packet = OnionPacket { 168 version = 0x00, 169 ephemeral = ephemeral_pub, 170 hop_payloads = hop_payloads, 171 hmac = hmac 172 } 173 174 9. return (packet, shared_secrets) 175 ``` 176 177 ## Implementation Notes 178 179 1. The session key should come from a CSPRNG. This module assumes it's 180 provided externally (no IO). 181 182 2. Shared secrets are returned for error attribution - the sender needs 183 them to unwrap error messages. 184 185 3. Filler generation is subtle. Test against spec vectors carefully. 186 187 4. The "random" initial hop_payloads should be deterministic from the 188 pad key (derived from final hop's shared secret) for reproducibility. 189 190 5. Payload size validation: ensure total doesn't exceed 1300 bytes 191 accounting for all length prefixes and HMACs. 192 193 ## Test Vectors 194 195 From BOLT4 spec with session key 0x4141...41: 196 197 ``` 198 Hop 0: pubkey 02eec7245d6b7d2ccb30380bfbe2a3648cd7a942653f5aa340edcea1f283686619 199 payload (hex): ... 200 201 Final packet ephemeral key: 02... 202 Final packet hop_payloads (hex): ... 203 Final packet HMAC (hex): ... 204 ``` 205 206 Verify intermediate values (shared secrets, blinding factors) and 207 final packet bytes match spec exactly.