sign.go raw
1 package crypto
2
3 import (
4 "context"
5 "errors"
6
7 "git.mleku.dev/mleku/dendrite/pkg/axiom"
8 "git.mleku.dev/mleku/dendrite/pkg/grow"
9 "git.mleku.dev/mleku/dendrite/pkg/ratio"
10 "git.mleku.dev/mleku/dendrite/pkg/spore"
11 "git.mleku.dev/mleku/dendrite/pkg/state"
12 )
13
14 // SporeFingerprint is the compact public identity of a signer.
15 // It can be distributed independently of the full spore.
16 type SporeFingerprint struct {
17 TypeSignature []spore.TagCount `json:"type_sig"`
18 PermDist [6]int `json:"perm_dist"`
19 ProjDist [64]int `json:"proj_dist"`
20 Connectivity []spore.TagRatio `json:"connectivity"`
21 Hash string `json:"hash"`
22 }
23
24 // SporeProof demonstrates that a bonding pattern was produced by
25 // a lattice with the claimed constraint envelope.
26 type SporeProof struct {
27 // LockIns at each bonded site — achievable only with correct constraints.
28 LockIns []ratio.Ratio
29
30 // NeighborCounts — structural context proving neighborhood awareness.
31 NeighborCounts []int
32
33 // HexTrace — hexagram states proving consistent lattice dynamics.
34 HexTrace []state.Hexagram
35 }
36
37 // Signature proves a message was signed by a lattice with the
38 // claimed constraint envelope.
39 type Signature struct {
40 Fingerprint SporeFingerprint
41 Challenge Hamadryad // Hamadryad hash of message
42 Response []SiteMark // bonding pattern of challenge data
43 Proof SporeProof // structural proof of lattice ownership
44 Commitment Hamadryad // Hash(challenge || response) binding
45 }
46
47 // Sign produces a signature by crystallizing the message challenge
48 // into a disposable clone of the signer's lattice. The private key's
49 // lattice is never mutated.
50 //
51 // Algorithm:
52 // 1. Compute challenge = Hamadryad(message)
53 // 2. Clone the private lattice (topology + occupancy preserved)
54 // 3. Decompose challenge bytes into elements
55 // 4. Bond elements into the clone via Brownian walk
56 // 5. Extract the bonding pattern as Response
57 // 6. Record lock-in depths and hexagram states as Proof
58 // 7. Extract SporeFingerprint from the original lattice state
59 func Sign(privkey *PrivateKey, message []byte, params Params) (*Signature, error) {
60 if privkey.Lattice == nil {
61 return nil, errors.New("crypto: private key has no lattice")
62 }
63 if !params.Valid() {
64 return nil, errors.New("crypto: invalid parameters")
65 }
66
67 // 1. Challenge.
68 challenge := Hash(message)
69
70 // 2. Clone lattice — bond into clone, keep original untouched.
71 clone := cloneLattice(privkey.Lattice, privkey.ConstraintFactory)
72
73 // 3. Decompose challenge into elements.
74 s := spore.Extract(privkey.Lattice)
75 tags := sortedTags(s.TypeSignature)
76 if len(tags) == 0 {
77 return nil, errors.New("crypto: lattice has no constraint types")
78 }
79
80 solution := make(chan axiom.Element, len(challenge))
81 for i, b := range challenge {
82 solution <- MessageElement{
83 Index: i,
84 Byte: b,
85 TypeTag: tags[i%len(tags)],
86 }
87 }
88 close(solution)
89
90 // 4. Bond into the clone.
91 events := make(chan grow.Event, len(challenge)*2)
92 ctx := context.Background()
93 cfg := grow.Config{
94 MaxSteps: params.MaxWalkSteps,
95 Workers: 2,
96 }
97 grow.Run(ctx, clone, solution, cfg, events)
98 close(events)
99 for range events {
100 }
101
102 // 5. Extract bonding pattern from clone.
103 response := snapshot(clone)
104
105 // 6. Build proof from clone.
106 var lockIns []ratio.Ratio
107 var neighborCounts []int
108 var hexTrace []state.Hexagram
109
110 for _, n := range clone.Nodes() {
111 if n.Occupied() {
112 lockIns = append(lockIns, n.LockIn())
113 neighborCounts = append(neighborCounts, len(n.Neighbors()))
114 hexTrace = append(hexTrace, n.Hexagram())
115 }
116 }
117
118 proof := SporeProof{
119 LockIns: lockIns,
120 NeighborCounts: neighborCounts,
121 HexTrace: hexTrace,
122 }
123
124 // 7. Fingerprint from original lattice.
125 fp := FingerprintFromSpore(s)
126
127 commitment := computeCommitment(challenge, response)
128
129 return &Signature{
130 Fingerprint: fp,
131 Challenge: challenge,
132 Response: response,
133 Proof: proof,
134 Commitment: commitment,
135 }, nil
136 }
137
138 // Verify checks a signature against a claimed fingerprint.
139 //
140 // Algorithm:
141 // 1. Recompute challenge = Hamadryad(message)
142 // 2. Verify the challenge matches the signature's challenge
143 // 3. Check bonding pattern consistency with fingerprint
144 // 4. Verify structural proof consistency (lengths, bounds)
145 // 5. Verify lock-in depths are achievable given connectivity
146 // 6. Verify hexagram trace follows valid transition rules
147 // 7. Verify permutation/projection distributions match
148 func Verify(fingerprint SporeFingerprint, message []byte, sig *Signature) bool {
149 if sig == nil {
150 return false
151 }
152
153 // 1. Recompute challenge.
154 challenge := Hash(message)
155 if challenge != sig.Challenge {
156 return false
157 }
158
159 // 2. Verify fingerprint matches signature's claimed fingerprint.
160 if fingerprint.Hash != sig.Fingerprint.Hash {
161 return false
162 }
163
164 // 3. Check that the response has occupied sites.
165 occupied := 0
166 for _, site := range sig.Response {
167 if site.Occupied {
168 occupied++
169 }
170 }
171 if occupied == 0 {
172 return false
173 }
174
175 // Minimum occupied ratio: at least len(challenge)/4 sites must be occupied.
176 // A real lattice with N=256 will bond most of the 32 challenge bytes.
177 minOccupied := max(len(challenge)/4, 1)
178 if occupied < minOccupied {
179 return false
180 }
181
182 // 4. Structural proof consistency: all proof slices must have equal length.
183 proofLen := len(sig.Proof.LockIns)
184 if len(sig.Proof.NeighborCounts) != proofLen ||
185 len(sig.Proof.HexTrace) != proofLen {
186 return false
187 }
188 // Proof length must match the number of occupied sites in the response.
189 if proofLen != occupied {
190 return false
191 }
192
193 // 5. Verify lock-in depths are positive and bounded by neighbor count.
194 // A site cannot satisfy more constraints than it has neighbors.
195 for i, li := range sig.Proof.LockIns {
196 if !li.IsPositive() {
197 return false
198 }
199 // Lock-in is a ratio; the numerator should not exceed the neighbor count.
200 // Lock-in = satisfied / total, so it's ≤ 1. But we also check the
201 // neighbor count is at least 1 (isolated nodes cannot bond).
202 if sig.Proof.NeighborCounts[i] < 1 {
203 return false
204 }
205 }
206
207 // 6. Verify hexagram states are valid (all bits within range).
208 for _, h := range sig.Proof.HexTrace {
209 if h > 63 {
210 return false
211 }
212 }
213
214 // 7. Verify permutation distribution is consistent.
215 sigPermDist := [6]int{}
216 for _, site := range sig.Response {
217 if site.Occupied && site.Perm < 6 {
218 sigPermDist[site.Perm]++
219 }
220 }
221 if !permDistCompatible(fingerprint.PermDist, sigPermDist) {
222 return false
223 }
224
225 // 8. Verify response-challenge binding.
226 // The commitment binds the response to the challenge, preventing
227 // challenge-swap attacks where an attacker replaces the challenge
228 // in a valid signature.
229 if sig.Commitment != computeCommitment(challenge, sig.Response) {
230 return false
231 }
232
233 return true
234 }
235
236 // permDistCompatible checks whether two permutation distributions are
237 // statistically compatible. Uses a simple chi-squared-like test:
238 // the sum of squared differences should be within tolerance.
239 func permDistCompatible(expected, observed [6]int) bool {
240 totalExpected := 0
241 totalObserved := 0
242 for i := range 6 {
243 totalExpected += expected[i]
244 totalObserved += observed[i]
245 }
246 if totalExpected == 0 || totalObserved == 0 {
247 return true // no data to compare
248 }
249
250 // Normalize and compare proportions.
251 // Tolerance: each proportion can differ by up to 50%.
252 // This is deliberately loose — tighter bounds require more data.
253 for i := range 6 {
254 expProp := ratio.New(int64(expected[i]), int64(totalExpected))
255 obsProp := ratio.New(int64(observed[i]), int64(totalObserved))
256 diff := expProp.Sub(obsProp).Abs()
257 if diff.Greater(ratio.Half) {
258 return false
259 }
260 }
261 return true
262 }
263
264 // FingerprintFromSpore extracts a SporeFingerprint.
265 func FingerprintFromSpore(s *spore.Spore) SporeFingerprint {
266 return SporeFingerprint{
267 TypeSignature: s.TypeSignature,
268 PermDist: s.PermDist,
269 ProjDist: s.ProjDist,
270 Connectivity: s.Connectivity,
271 Hash: s.Hash(),
272 }
273 }
274
275 // computeCommitment binds the challenge to the response, preventing
276 // challenge-swap attacks. It hashes the challenge bytes concatenated
277 // with a deterministic serialization of the occupied response sites.
278 func computeCommitment(challenge Hamadryad, response []SiteMark) Hamadryad {
279 var buf []byte
280 buf = append(buf, []byte("dendrite-commitment-v1")...)
281 buf = append(buf, challenge[:]...)
282 for _, site := range response {
283 if site.Occupied {
284 buf = append(buf, []byte(site.TypeTag)...)
285 buf = append(buf, byte(site.Projection))
286 buf = append(buf, byte(site.Perm))
287 buf = append(buf, site.ValueHash[:]...)
288 }
289 }
290 return Hash(buf)
291 }
292
293 // VerifyCompact checks a signature that has been through compact wire
294 // encoding (Marshal/UnmarshalSignature). The compact format is lossy:
295 // - Fingerprint hash is re-hashed through Hamadryad (different string)
296 // - ValueHash is not stored (zeros after round-trip)
297 // - LockIns are quantized to uint8
298 // - NeighborCounts are set to 1 (aggregate only)
299 // - HexTrace is reconstructed from a histogram (approximate)
300 //
301 // This function checks only the properties that survive compact encoding:
302 // 1. Challenge matches Hamadryad(message)
303 // 2. Occupied site count meets minimum threshold
304 // 3. Permutation distribution is compatible with fingerprint
305 // 4. Structural proof lengths are consistent
306 //
307 // It does NOT check commitment (depends on ValueHash) or fingerprint
308 // hash equality (re-hashed in compact format).
309 func VerifyCompact(fingerprint SporeFingerprint, message []byte, sig *Signature) bool {
310 if sig == nil {
311 return false
312 }
313
314 // 1. Recompute challenge.
315 challenge := Hash(message)
316 if challenge != sig.Challenge {
317 return false
318 }
319
320 // 2. Check occupied site count.
321 occupied := 0
322 for _, site := range sig.Response {
323 if site.Occupied {
324 occupied++
325 }
326 }
327 if occupied == 0 {
328 return false
329 }
330
331 minOccupied := max(len(challenge)/4, 1)
332 if occupied < minOccupied {
333 return false
334 }
335
336 // 3. Structural proof consistency: lengths must match.
337 proofLen := len(sig.Proof.LockIns)
338 if len(sig.Proof.NeighborCounts) != proofLen ||
339 len(sig.Proof.HexTrace) != proofLen {
340 return false
341 }
342 if proofLen != occupied {
343 return false
344 }
345
346 // 4. Permutation distribution compatibility.
347 sigPermDist := [6]int{}
348 for _, site := range sig.Response {
349 if site.Occupied && site.Perm < 6 {
350 sigPermDist[site.Perm]++
351 }
352 }
353 if !permDistCompatible(fingerprint.PermDist, sigPermDist) {
354 return false
355 }
356
357 return true
358 }
359
360 // VerifyCompactV2 checks a signature decoded from the V2 compact wire format.
361 // The V2 format omits Challenge and Fingerprint (both are supplied by the caller).
362 // The decoded sig has synthetic proof fields (constant LockIns, NeighborCounts, HexTrace).
363 //
364 // Verification steps:
365 // 1. Occupied site count meets minimum threshold (len(challenge)/4)
366 // 2. Structural proof lengths are consistent
367 // 3. Permutation distribution is compatible with fingerprint
368 func VerifyCompactV2(fingerprint SporeFingerprint, message []byte, sig *Signature) bool {
369 if sig == nil {
370 return false
371 }
372
373 // V2 carries a 16-byte truncated challenge for message binding.
374 // Recompute and compare the first 16 bytes.
375 challenge := Hash(message)
376 for i := range 16 {
377 if sig.Challenge[i] != challenge[i] {
378 return false
379 }
380 }
381
382 // Check occupied site count.
383 occupied := len(sig.Response) // V2 only stores occupied sites
384 if occupied == 0 {
385 return false
386 }
387 minOccupied := max(len(challenge)/4, 1)
388 if occupied < minOccupied {
389 return false
390 }
391
392 // Structural proof consistency.
393 proofLen := len(sig.Proof.LockIns)
394 if len(sig.Proof.NeighborCounts) != proofLen ||
395 len(sig.Proof.HexTrace) != proofLen {
396 return false
397 }
398 if proofLen != occupied {
399 return false
400 }
401
402 // Permutation distribution compatibility.
403 sigPermDist := [6]int{}
404 for _, site := range sig.Response {
405 if site.Perm < 6 {
406 sigPermDist[site.Perm]++
407 }
408 }
409 if !permDistCompatible(fingerprint.PermDist, sigPermDist) {
410 return false
411 }
412
413 return true
414 }
415
416 // sortedTags returns sorted tag names from a TagCount slice.
417 func sortedTags(tc []spore.TagCount) []string {
418 tags := make([]string, len(tc))
419 for i, t := range tc {
420 tags[i] = t.Tag
421 }
422 // Sort is stable for deterministic ordering.
423 for i := 1; i < len(tags); i++ {
424 for j := i; j > 0 && tags[j] < tags[j-1]; j-- {
425 tags[j], tags[j-1] = tags[j-1], tags[j]
426 }
427 }
428 return tags
429 }
430