compact_v2.go raw
1 package crypto
2
3 import (
4 "errors"
5 "math/big"
6 "sort"
7
8 "git.mleku.dev/mleku/dendrite/pkg/ratio"
9 "git.mleku.dev/mleku/dendrite/pkg/state"
10 )
11
12 // Compact V2 binary wire format for signatures.
13 //
14 // Eliminates redundant fields (full Challenge recomputed by verifier,
15 // Fingerprint known to verifier, aggregate proof recomputed from per-site
16 // data). Uses combinatorial number system for occupancy encoding and
17 // bitpacking for per-site data.
18 //
19 // A 16-byte truncated challenge hash is included for message binding:
20 // without it the signature would be message-independent and trivially
21 // replayable against different messages.
22 //
23 // Layout:
24 // [1 byte] Magic (0xD2)
25 // [1 byte] Flags: security_level[2] | tag_bits[1] | reserved[5]
26 // [1 byte] Occupied count K
27 // [1 byte] Tag count T
28 // [variable] Tag table: per tag, 1-byte length + UTF-8 string
29 // [16 bytes] Truncated challenge: first 16 bytes of Hamadryad(message)
30 // [variable] Occupancy set: combinatorial encoding of K-subset of [0,N)
31 // [variable] Per-site data: K × (tag_bits + 8 + 3) bits, padded
32 //
33 // Target size: ~144 bytes for N=256, K=56, 3 tags.
34
35 const compactV2Magic = 0xD2
36
37 // securityN maps security level bits to lattice dimension.
38 func securityN(level uint8) int {
39 switch level {
40 case 1:
41 return 384
42 case 2:
43 return 512
44 default:
45 return 256
46 }
47 }
48
49 // securityLevel returns the 2-bit security level for a given N.
50 func securityLevel(n int) uint8 {
51 switch {
52 case n >= 512:
53 return 2
54 case n >= 384:
55 return 1
56 default:
57 return 0
58 }
59 }
60
61 // --- Combinatorial number system ---
62 //
63 // Encodes a K-element subset of [0,N) as an integer in [0, C(N,K)).
64 // Rank of sorted indices {c_0 < c_1 < ... < c_{K-1}} = sum of C(c_i, i+1).
65 // This is the most compact possible encoding for a fixed-size subset.
66
67 // bigBinom computes C(n, k) as a *big.Int.
68 func bigBinom(n, k int) *big.Int {
69 if k < 0 || k > n {
70 return big.NewInt(0)
71 }
72 // Use the smaller of k and n-k for efficiency.
73 if k > n-k {
74 k = n - k
75 }
76 result := big.NewInt(1)
77 for i := 0; i < k; i++ {
78 result.Mul(result, big.NewInt(int64(n-i)))
79 result.Div(result, big.NewInt(int64(i+1)))
80 }
81 return result
82 }
83
84 // subsetBytes returns the number of bytes needed to encode a K-subset of [0,N).
85 func subsetBytes(n, k int) int {
86 b := bigBinom(n, k)
87 bits := b.BitLen()
88 if bits == 0 {
89 return 1
90 }
91 return (bits + 7) / 8
92 }
93
94 // encodeSubset encodes sorted indices into a combinatorial rank (little-endian bytes).
95 func encodeSubset(indices []int, n int) []byte {
96 k := len(indices)
97 rank := new(big.Int)
98 for i, c := range indices {
99 rank.Add(rank, bigBinom(c, i+1))
100 }
101 nbytes := subsetBytes(n, k)
102 buf := make([]byte, nbytes)
103 rankBytes := rank.Bytes() // big-endian
104 // Reverse to little-endian and copy into fixed-size buf.
105 for i, j := 0, len(rankBytes)-1; i < len(rankBytes) && j >= 0; i, j = i+1, j-1 {
106 buf[i] = rankBytes[j]
107 }
108 return buf
109 }
110
111 // decodeSubset decodes a combinatorial rank (little-endian bytes) back to sorted indices.
112 func decodeSubset(data []byte, n, k int) []int {
113 // Convert little-endian to big.Int.
114 reversed := make([]byte, len(data))
115 for i, j := 0, len(data)-1; j >= 0; i, j = i+1, j-1 {
116 reversed[i] = data[j]
117 }
118 rank := new(big.Int).SetBytes(reversed)
119
120 indices := make([]int, k)
121 // Greedy decode: from the highest index position downward.
122 for i := k - 1; i >= 0; i-- {
123 // Find the largest c such that C(c, i+1) <= rank.
124 c := i // minimum possible value for position i
125 for c+1 < n {
126 b := bigBinom(c+1, i+1)
127 if b.Cmp(rank) > 0 {
128 break
129 }
130 c++
131 }
132 indices[i] = c
133 rank.Sub(rank, bigBinom(c, i+1))
134 }
135 return indices
136 }
137
138 // --- Bitpacking ---
139
140 type bitWriter struct {
141 buf []byte
142 bitPos int
143 }
144
145 func newBitWriter(capacity int) *bitWriter {
146 return &bitWriter{buf: make([]byte, 0, capacity)}
147 }
148
149 func (w *bitWriter) writeBits(val uint32, nbits int) {
150 for i := 0; i < nbits; i++ {
151 byteIdx := w.bitPos / 8
152 bitIdx := uint(w.bitPos % 8)
153 for byteIdx >= len(w.buf) {
154 w.buf = append(w.buf, 0)
155 }
156 if val&(1<<uint(i)) != 0 {
157 w.buf[byteIdx] |= 1 << bitIdx
158 }
159 w.bitPos++
160 }
161 }
162
163 func (w *bitWriter) bytes() []byte {
164 // Ensure final partial byte is included.
165 totalBytes := (w.bitPos + 7) / 8
166 for len(w.buf) < totalBytes {
167 w.buf = append(w.buf, 0)
168 }
169 return w.buf[:totalBytes]
170 }
171
172 type bitReader struct {
173 buf []byte
174 bitPos int
175 }
176
177 func newBitReader(data []byte) *bitReader {
178 return &bitReader{buf: data}
179 }
180
181 func (r *bitReader) readBits(nbits int) (uint32, error) {
182 var val uint32
183 for i := 0; i < nbits; i++ {
184 byteIdx := r.bitPos / 8
185 bitIdx := uint(r.bitPos % 8)
186 if byteIdx >= len(r.buf) {
187 return 0, errors.New("crypto: bitstream truncated")
188 }
189 if r.buf[byteIdx]&(1<<bitIdx) != 0 {
190 val |= 1 << uint(i)
191 }
192 r.bitPos++
193 }
194 return val, nil
195 }
196
197 // --- MarshalV2 / UnmarshalSignatureV2 ---
198
199 // MarshalV2 encodes a Signature into the compact V2 binary wire format.
200 // The caller must supply the lattice dimension N (from Params).
201 func (s *Signature) MarshalV2(n int) ([]byte, error) {
202 if s == nil {
203 return nil, errors.New("crypto: nil signature")
204 }
205
206 // Collect occupied sites in index order.
207 type siteData struct {
208 index int
209 tag string
210 proj uint8
211 perm uint8
212 }
213 var sites []siteData
214 for _, site := range s.Response {
215 if site.Occupied {
216 sites = append(sites, siteData{
217 index: int(site.Index),
218 tag: site.TypeTag,
219 proj: site.Projection,
220 perm: site.Perm,
221 })
222 }
223 }
224 sort.Slice(sites, func(i, j int) bool { return sites[i].index < sites[j].index })
225
226 k := len(sites)
227 if k == 0 {
228 return nil, errors.New("crypto: no occupied sites")
229 }
230 if k > 255 {
231 return nil, errors.New("crypto: too many occupied sites for V2")
232 }
233
234 // Build tag table.
235 tagIndex := make(map[string]uint8)
236 var tagTable []string
237 for _, sd := range sites {
238 if _, ok := tagIndex[sd.tag]; !ok {
239 if len(tagTable) >= 8 {
240 return nil, errors.New("crypto: too many distinct tags for V2")
241 }
242 tagIndex[sd.tag] = uint8(len(tagTable))
243 tagTable = append(tagTable, sd.tag)
244 }
245 }
246
247 tagCount := len(tagTable)
248 tagBitsFlag := uint8(0) // 2-bit tags
249 tagBits := 2
250 if tagCount > 4 {
251 tagBitsFlag = 1 // 3-bit tags
252 tagBits = 3
253 }
254
255 // Header: magic + flags + K + tagcount + tag table.
256 flags := securityLevel(n) | (tagBitsFlag << 2)
257 var header []byte
258 header = append(header, compactV2Magic)
259 header = append(header, flags)
260 header = append(header, uint8(k))
261 header = append(header, uint8(tagCount))
262 for _, tag := range tagTable {
263 if len(tag) > 255 {
264 return nil, errors.New("crypto: tag name too long")
265 }
266 header = append(header, uint8(len(tag)))
267 header = append(header, []byte(tag)...)
268 }
269
270 // Truncated challenge: first 16 bytes of Hamadryad(message).
271 // Provides 128-bit message binding.
272 header = append(header, s.Challenge[:16]...)
273
274 // Combinatorial occupancy encoding.
275 indices := make([]int, k)
276 for i, sd := range sites {
277 indices[i] = sd.index
278 }
279 occBytes := encodeSubset(indices, n)
280 nbytes := subsetBytes(n, k)
281 // Prefix with 1-byte length so decoder knows how many bytes to read.
282 var occSection []byte
283 occSection = append(occSection, uint8(nbytes))
284 occSection = append(occSection, occBytes...)
285
286 // Bitpacked per-site data.
287 bitsPerSite := tagBits + 8 + 3
288 bw := newBitWriter((k*bitsPerSite + 7) / 8)
289 for _, sd := range sites {
290 bw.writeBits(uint32(tagIndex[sd.tag]), tagBits)
291 bw.writeBits(uint32(sd.proj), 8)
292 bw.writeBits(uint32(sd.perm), 3)
293 }
294 siteBytes := bw.bytes()
295
296 // Assemble.
297 total := len(header) + len(occSection) + len(siteBytes)
298 buf := make([]byte, 0, total)
299 buf = append(buf, header...)
300 buf = append(buf, occSection...)
301 buf = append(buf, siteBytes...)
302
303 return buf, nil
304 }
305
306 // UnmarshalSignatureV2 decodes a compact V2 binary signature.
307 // Returns the reconstructed Signature with synthetic proof fields.
308 func UnmarshalSignatureV2(data []byte) (*Signature, int, error) {
309 if len(data) < 4 {
310 return nil, 0, errors.New("crypto: V2 signature too short")
311 }
312 pos := 0
313
314 // Magic.
315 if data[pos] != compactV2Magic {
316 return nil, 0, errors.New("crypto: bad V2 magic")
317 }
318 pos++
319
320 // Flags.
321 flags := data[pos]
322 pos++
323 level := flags & 0x03
324 tagBitsFlag := (flags >> 2) & 0x01
325 n := securityN(level)
326
327 tagBits := 2
328 if tagBitsFlag == 1 {
329 tagBits = 3
330 }
331
332 // Occupied count.
333 k := int(data[pos])
334 pos++
335 if k == 0 {
336 return nil, 0, errors.New("crypto: zero occupied sites")
337 }
338
339 // Tag count.
340 if pos >= len(data) {
341 return nil, 0, errors.New("crypto: truncated header")
342 }
343 tagCount := int(data[pos])
344 pos++
345
346 // Tag table.
347 tagTable := make([]string, tagCount)
348 for i := range tagCount {
349 if pos >= len(data) {
350 return nil, 0, errors.New("crypto: truncated tag table")
351 }
352 tLen := int(data[pos])
353 pos++
354 if pos+tLen > len(data) {
355 return nil, 0, errors.New("crypto: truncated tag name")
356 }
357 tagTable[i] = string(data[pos : pos+tLen])
358 pos += tLen
359 }
360
361 // Truncated challenge (16 bytes).
362 const challengeTruncLen = 16
363 if pos+challengeTruncLen > len(data) {
364 return nil, 0, errors.New("crypto: truncated challenge")
365 }
366 var challengeTrunc [challengeTruncLen]byte
367 copy(challengeTrunc[:], data[pos:pos+challengeTruncLen])
368 pos += challengeTruncLen
369
370 // Occupancy set.
371 if pos >= len(data) {
372 return nil, 0, errors.New("crypto: truncated occupancy")
373 }
374 occLen := int(data[pos])
375 pos++
376 if pos+occLen > len(data) {
377 return nil, 0, errors.New("crypto: truncated occupancy data")
378 }
379 indices := decodeSubset(data[pos:pos+occLen], n, k)
380 pos += occLen
381
382 // Per-site bitpacked data.
383 bitsPerSite := tagBits + 8 + 3
384 totalBits := k * bitsPerSite
385 siteDataBytes := (totalBits + 7) / 8
386 if pos+siteDataBytes > len(data) {
387 return nil, 0, errors.New("crypto: truncated site data")
388 }
389
390 br := newBitReader(data[pos : pos+siteDataBytes])
391 response := make([]SiteMark, k)
392 lockIns := make([]ratio.Ratio, k)
393 neighborCounts := make([]int, k)
394 hexTrace := make([]state.Hexagram, k)
395
396 for i := range k {
397 tagIdx, err := br.readBits(tagBits)
398 if err != nil {
399 return nil, 0, err
400 }
401 proj, err := br.readBits(8)
402 if err != nil {
403 return nil, 0, err
404 }
405 perm, err := br.readBits(3)
406 if err != nil {
407 return nil, 0, err
408 }
409
410 tag := ""
411 if int(tagIdx) < len(tagTable) {
412 tag = tagTable[tagIdx]
413 }
414
415 response[i] = SiteMark{
416 Index: uint64(indices[i]),
417 Occupied: true,
418 TypeTag: tag,
419 Projection: uint8(proj),
420 Perm: uint8(perm),
421 LockIn: ratio.New(1, 1),
422 }
423 lockIns[i] = ratio.New(1, 1)
424 neighborCounts[i] = 1
425 hexTrace[i] = 0
426 }
427 pos += siteDataBytes
428
429 // Reconstruct permutation distribution for fingerprint.
430 permDist := [6]int{}
431 for _, site := range response {
432 if site.Perm < 6 {
433 permDist[site.Perm]++
434 }
435 }
436
437 // Store truncated challenge in the Challenge field (first 16 bytes).
438 var challenge Hamadryad
439 copy(challenge[:], challengeTrunc[:])
440
441 sig := &Signature{
442 Fingerprint: SporeFingerprint{
443 PermDist: permDist,
444 },
445 Challenge: challenge,
446 Response: response,
447 Proof: SporeProof{
448 LockIns: lockIns,
449 NeighborCounts: neighborCounts,
450 HexTrace: hexTrace,
451 },
452 }
453
454 return sig, pos, nil
455 }
456
457 // V2Size returns the wire size of a V2 encoding without performing the full marshal.
458 func (s *Signature) V2Size(n int) int {
459 if s == nil {
460 return 0
461 }
462
463 var k int
464 tags := make(map[string]bool)
465 for _, site := range s.Response {
466 if site.Occupied {
467 k++
468 tags[site.TypeTag] = true
469 }
470 }
471
472 tagCount := len(tags)
473 tagBits := 2
474 if tagCount > 4 {
475 tagBits = 3
476 }
477
478 // Header: magic(1) + flags(1) + K(1) + tagcount(1) = 4
479 headerSize := 4
480 tagTableSize := 0
481 for tag := range tags {
482 tagTableSize += 1 + len(tag)
483 }
484
485 // Occupancy: 1-byte length prefix + combinatorial bytes.
486 occSize := 1 + subsetBytes(n, k)
487
488 // Per-site data.
489 bitsPerSite := tagBits + 8 + 3
490 siteDataSize := (k*bitsPerSite + 7) / 8
491
492 // 16-byte truncated challenge.
493 challengeSize := 16
494
495 return headerSize + tagTableSize + challengeSize + occSize + siteDataSize
496 }
497
498