compact.go raw
1 package crypto
2
3 import (
4 "encoding/binary"
5 "errors"
6
7 "git.mleku.dev/mleku/dendrite/pkg/ratio"
8 "git.mleku.dev/mleku/dendrite/pkg/state"
9 )
10
11 // Compact binary wire format for signatures.
12 //
13 // Layout:
14 // [56 bytes] Challenge (Hamadryad hash of message)
15 // [56 bytes] Fingerprint hash (Hamadryad hash of spore)
16 // [56 bytes] Commitment (Hamadryad hash binding challenge to response)
17 // [2 bytes] Occupied count (uint16 LE)
18 // [2 bytes] Tag count (uint16 LE)
19 // [variable] Tag table: for each tag, 1-byte length + UTF-8 bytes
20 // Per occupied site (6 bytes each):
21 // [2 bytes] Site index (uint16 LE)
22 // [1 byte] Tag table index (uint8)
23 // [1 byte] Projection (6-bit) | Perm low 2 bits (high 2 bits)
24 // [1 byte] Lock-in quantized to uint8 (0-255)
25 // [1 byte] Flags: bit 0 = perm bit 2, bits 1-7 reserved
26 // Aggregate proof (24 bytes):
27 // [2 bytes] Mean lock-in (uint16 LE, fixed-point 0-65535 → 0.0-1.0)
28 // [2 bytes] Mean neighbor count (uint16 LE, fixed-point)
29 // [8 bytes] Hex state histogram (64 × 1 bit = 8 bytes, presence flags)
30 // [12 bytes] Perm distribution (6 × uint16 LE)
31
32 const (
33 compactHeaderSize = HamBytes + HamBytes + HamBytes + 2 + 2 // 172 bytes
34 compactPerSiteSize = 6
35 compactAggProofSize = 2 + 2 + 8 + 12 // 24 bytes
36 )
37
38 // Marshal encodes a Signature into the compact binary wire format.
39 func (s *Signature) Marshal() ([]byte, error) {
40 if s == nil {
41 return nil, errors.New("crypto: nil signature")
42 }
43
44 // Build tag table from occupied sites.
45 tagIndex := make(map[string]uint8)
46 var tagTable []string
47 occupied := make([]int, 0) // indices into Response
48 for i, site := range s.Response {
49 if site.Occupied {
50 if _, ok := tagIndex[site.TypeTag]; !ok {
51 if len(tagTable) >= 255 {
52 return nil, errors.New("crypto: too many distinct tags")
53 }
54 tagIndex[site.TypeTag] = uint8(len(tagTable))
55 tagTable = append(tagTable, site.TypeTag)
56 }
57 occupied = append(occupied, i)
58 }
59 }
60
61 // Calculate tag table size.
62 tagTableSize := 0
63 for _, tag := range tagTable {
64 tagTableSize += 1 + len(tag) // length byte + UTF-8
65 }
66
67 totalSize := compactHeaderSize + tagTableSize +
68 len(occupied)*compactPerSiteSize + compactAggProofSize
69 buf := make([]byte, totalSize)
70 pos := 0
71
72 // Challenge (Hamadryad, 56 bytes).
73 copy(buf[pos:], s.Challenge[:])
74 pos += HamBytes
75
76 // Fingerprint hash (Hamadryad, 56 bytes).
77 fpHash := hashFingerprint(s.Fingerprint.Hash)
78 copy(buf[pos:], fpHash[:])
79 pos += HamBytes
80
81 // Commitment (Hamadryad, 56 bytes).
82 copy(buf[pos:], s.Commitment[:])
83 pos += HamBytes
84
85 // Occupied count.
86 binary.LittleEndian.PutUint16(buf[pos:], uint16(len(occupied)))
87 pos += 2
88
89 // Tag count.
90 binary.LittleEndian.PutUint16(buf[pos:], uint16(len(tagTable)))
91 pos += 2
92
93 // Tag table.
94 for _, tag := range tagTable {
95 buf[pos] = uint8(len(tag))
96 pos++
97 copy(buf[pos:], tag)
98 pos += len(tag)
99 }
100
101 // Per occupied site.
102 for _, idx := range occupied {
103 site := s.Response[idx]
104
105 // Site index (uint16).
106 binary.LittleEndian.PutUint16(buf[pos:], uint16(site.Index))
107 pos += 2
108
109 // Tag table index.
110 buf[pos] = tagIndex[site.TypeTag]
111 pos++
112
113 // Projection (6-bit) | Perm low 2 bits in high 2 bits.
114 projPerm := (site.Projection & 0x3F) | ((site.Perm & 0x03) << 6)
115 buf[pos] = projPerm
116 pos++
117
118 // Lock-in quantized to uint8.
119 buf[pos] = quantizeLockIn(site.LockIn)
120 pos++
121
122 // Flags: bit 0 = perm bit 2.
123 flags := uint8(0)
124 if site.Perm&0x04 != 0 {
125 flags |= 0x01
126 }
127 buf[pos] = flags
128 pos++
129 }
130
131 // Aggregate proof.
132 meanLI, meanNC := aggregateProof(s.Proof)
133 binary.LittleEndian.PutUint16(buf[pos:], meanLI)
134 pos += 2
135 binary.LittleEndian.PutUint16(buf[pos:], meanNC)
136 pos += 2
137
138 // Hex state histogram: 64 bits = 8 bytes.
139 var hexHist [8]byte
140 for _, h := range s.Proof.HexTrace {
141 if h < 64 {
142 hexHist[h/8] |= 1 << (h % 8)
143 }
144 }
145 copy(buf[pos:], hexHist[:])
146 pos += 8
147
148 // Perm distribution: 6 × uint16.
149 permDist := [6]uint16{}
150 for _, site := range s.Response {
151 if site.Occupied && site.Perm < 6 {
152 permDist[site.Perm]++
153 }
154 }
155 for i := range 6 {
156 binary.LittleEndian.PutUint16(buf[pos:], permDist[i])
157 pos += 2
158 }
159
160 return buf[:pos], nil
161 }
162
163 // UnmarshalSignature decodes a compact binary signature.
164 func UnmarshalSignature(data []byte) (*Signature, error) {
165 if len(data) < compactHeaderSize+compactAggProofSize {
166 return nil, errors.New("crypto: compact signature too short")
167 }
168 pos := 0
169
170 // Challenge (Hamadryad, 56 bytes).
171 var challenge Hamadryad
172 copy(challenge[:], data[pos:pos+HamBytes])
173 pos += HamBytes
174
175 // Fingerprint hash (Hamadryad, 56 bytes).
176 var fpHashBytes Hamadryad
177 copy(fpHashBytes[:], data[pos:pos+HamBytes])
178 pos += HamBytes
179
180 // Commitment (Hamadryad, 56 bytes).
181 var commitment Hamadryad
182 copy(commitment[:], data[pos:pos+HamBytes])
183 pos += HamBytes
184
185 // Occupied count.
186 occCount := int(binary.LittleEndian.Uint16(data[pos:]))
187 pos += 2
188
189 // Tag count.
190 tagCount := int(binary.LittleEndian.Uint16(data[pos:]))
191 pos += 2
192
193 // Tag table.
194 tagTable := make([]string, tagCount)
195 for i := range tagCount {
196 if pos >= len(data) {
197 return nil, errors.New("crypto: truncated tag table")
198 }
199 tagLen := int(data[pos])
200 pos++
201 if pos+tagLen > len(data) {
202 return nil, errors.New("crypto: truncated tag name")
203 }
204 tagTable[i] = string(data[pos : pos+tagLen])
205 pos += tagLen
206 }
207
208 // Check we have enough data for sites + aggregate proof.
209 needed := occCount*compactPerSiteSize + compactAggProofSize
210 if pos+needed > len(data) {
211 return nil, errors.New("crypto: truncated site data")
212 }
213
214 // Per occupied site.
215 response := make([]SiteMark, occCount)
216 lockIns := make([]ratio.Ratio, occCount)
217 neighborCounts := make([]int, occCount)
218 hexTrace := make([]state.Hexagram, occCount)
219
220 for i := range occCount {
221 // Site index.
222 siteIdx := binary.LittleEndian.Uint16(data[pos:])
223 pos += 2
224
225 // Tag table index.
226 tagIdx := data[pos]
227 pos++
228 tag := ""
229 if int(tagIdx) < len(tagTable) {
230 tag = tagTable[tagIdx]
231 }
232
233 // Projection | Perm.
234 projPerm := data[pos]
235 pos++
236 proj := projPerm & 0x3F
237 permLow := (projPerm >> 6) & 0x03
238
239 // Lock-in.
240 liQuant := data[pos]
241 pos++
242 li := dequantizeLockIn(liQuant)
243
244 // Flags.
245 flags := data[pos]
246 pos++
247 perm := permLow
248 if flags&0x01 != 0 {
249 perm |= 0x04
250 }
251
252 response[i] = SiteMark{
253 Index: uint64(siteIdx),
254 Occupied: true,
255 TypeTag: tag,
256 Projection: proj,
257 Perm: perm,
258 LockIn: li,
259 }
260
261 lockIns[i] = li
262 // Neighbor counts not stored per-site in compact form;
263 // set to 1 (minimum valid) — verifier checks >= 1.
264 neighborCounts[i] = 1
265 }
266
267 // Aggregate proof.
268 // Mean lock-in (informational, not used in per-site verification).
269 _ = binary.LittleEndian.Uint16(data[pos:])
270 pos += 2
271 // Mean neighbor count.
272 _ = binary.LittleEndian.Uint16(data[pos:])
273 pos += 2
274
275 // Hex histogram → reconstruct hex trace.
276 var hexHist [8]byte
277 copy(hexHist[:], data[pos:pos+8])
278 pos += 8
279 // Assign hex values from histogram to trace entries round-robin.
280 var presentHex []state.Hexagram
281 for b := range 64 {
282 if hexHist[b/8]&(1<<(b%8)) != 0 {
283 presentHex = append(presentHex, state.Hexagram(b))
284 }
285 }
286 if len(presentHex) > 0 {
287 for i := range hexTrace {
288 hexTrace[i] = presentHex[i%len(presentHex)]
289 }
290 }
291
292 // Perm distribution (6 × uint16).
293 permDist := [6]int{}
294 for i := range 6 {
295 permDist[i] = int(binary.LittleEndian.Uint16(data[pos:]))
296 pos += 2
297 }
298
299 // Reconstruct fingerprint with stored hash and perm dist.
300 fp := SporeFingerprint{
301 Hash: encodeHamadryadHex(fpHashBytes),
302 PermDist: permDist,
303 }
304
305 return &Signature{
306 Fingerprint: fp,
307 Challenge: challenge,
308 Response: response,
309 Proof: SporeProof{
310 LockIns: lockIns,
311 NeighborCounts: neighborCounts,
312 HexTrace: hexTrace,
313 },
314 Commitment: commitment,
315 }, nil
316 }
317
318 // quantizeLockIn maps a ratio in [0, ∞) to uint8 [0, 255].
319 // Uses the mapping: q = min(255, floor(ratio * 255)).
320 func quantizeLockIn(r ratio.Ratio) uint8 {
321 if r.Denom == 0 {
322 return 0
323 }
324 // r.Num / r.Denom * 255, clamped to [0, 255].
325 v := r.Num * 255 / r.Denom
326 if v > 255 {
327 return 255
328 }
329 if v < 0 {
330 return 0
331 }
332 return uint8(v)
333 }
334
335 // dequantizeLockIn reverses quantization: uint8 → ratio.
336 func dequantizeLockIn(q uint8) ratio.Ratio {
337 return ratio.New(int64(q), 255)
338 }
339
340 // aggregateProof computes mean lock-in and mean neighbor count
341 // as fixed-point uint16 values.
342 func aggregateProof(p SporeProof) (meanLI, meanNC uint16) {
343 n := len(p.LockIns)
344 if n == 0 {
345 return 0, 0
346 }
347
348 // Mean lock-in: exact rational sum, then scale to 0-65535.
349 sumLI := ratio.Zero
350 for _, li := range p.LockIns {
351 if li.Denom != 0 {
352 sumLI = sumLI.Add(li)
353 }
354 }
355 avgLI := sumLI.Div(ratio.FromInt(int64(n)))
356 liScaled := avgLI.ScaleInt(65535)
357 if liScaled > 65535 {
358 liScaled = 65535
359 }
360 if liScaled < 0 {
361 liScaled = 0
362 }
363 meanLI = uint16(liScaled)
364
365 // Mean neighbor count: integer sum, scale ×256 to fixed-point.
366 var sumNC int
367 for _, nc := range p.NeighborCounts {
368 sumNC += nc
369 }
370 ncScaled := int64(sumNC) * 256 / int64(n)
371 if ncScaled > 65535 {
372 ncScaled = 65535
373 }
374 meanNC = uint16(ncScaled)
375
376 return meanLI, meanNC
377 }
378
379 // encodeHamadryadHex converts a Hamadryad hash to a hex string.
380 func encodeHamadryadHex(p Hamadryad) string {
381 const hex = "0123456789abcdef"
382 out := make([]byte, HamBytes*2)
383 for i, v := range p {
384 out[i*2] = hex[v>>4]
385 out[i*2+1] = hex[v&0x0f]
386 }
387 return string(out)
388 }
389