1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
use crate::bintrie_types::{Hash, Pubkey};
// State proof type constants (matching C implementation in tn_state_proof.h)
pub const TN_STATE_PROOF_TYPE_EXISTING: u64 = 0x0;
pub const TN_STATE_PROOF_TYPE_UPDATING: u64 = 0x1;
pub const TN_STATE_PROOF_TYPE_CREATION: u64 = 0x2;
/// Proof structure for existence/non-existence proofs
#[derive(Debug, Clone)]
pub struct Proof {
pub proof_indices: Vec<u8>,
pub sibling_hashes: Vec<Hash>,
pub existing_leaf_hash: Option<Hash>,
}
impl Proof {
pub fn new() -> Self {
Self {
proof_indices: Vec::new(),
sibling_hashes: Vec::new(),
existing_leaf_hash: None,
}
}
pub fn to_wire(&self, slot: u64) -> Vec<u8> {
// Convert proof indices to path bitset (matching C tn_state_proof_idx_list_to_path_bitset)
let mut path_bitset = [0u8; 32];
for &idx in &self.proof_indices {
let bit_idx = (idx % 64) as usize;
let word_idx = (idx / 64) as usize;
if word_idx < 4 {
// Convert to little-endian u64 array like C implementation
let start = word_idx * 8;
let mut word_bytes = [0u8; 8];
word_bytes.copy_from_slice(&path_bitset[start..start + 8]);
let mut word = u64::from_le_bytes(word_bytes);
word |= 1u64 << bit_idx;
path_bitset[start..start + 8].copy_from_slice(&word.to_le_bytes());
}
}
// Create header: type_slot (8 bytes) + path_bitset (32 bytes)
let mut result = Vec::with_capacity(40 + 64 + self.sibling_hashes.len() * 32);
// Encode type_slot: slot in low 62 bits, type (EXISTING=0) in high 2 bits
let type_slot = slot
| (if self.existing_leaf_hash.is_some() {
TN_STATE_PROOF_TYPE_UPDATING
} else {
TN_STATE_PROOF_TYPE_EXISTING
} << 62);
result.extend_from_slice(&type_slot.to_le_bytes());
// Add path bitset
result.extend_from_slice(&path_bitset);
if let Some(existing_leaf_hash) = self.existing_leaf_hash {
result.extend_from_slice(existing_leaf_hash.as_bytes());
}
for sibling_hash in &self.sibling_hashes {
result.extend_from_slice(sibling_hash.as_bytes());
}
result
}
}
/// Result of a non-existence proof
#[derive(Debug, Clone)]
pub struct NonExistenceProof {
pub proof: Proof,
pub existing_pubkey: Pubkey,
pub existing_hash: Hash,
}
impl NonExistenceProof {
/// Convert the non-existence proof to wire format compatible with C tn_state_proof_t
/// This creates a CREATION type state proof with the proof data
///
/// Wire format layout:
/// - Header (40 bytes):
/// - type_slot (8 bytes): slot in low 62 bits, proof type (2=CREATION) in high 2 bits
/// - path_bitset (32 bytes): bitset indicating which proof indices are used
/// - Body (variable length):
/// - existing_leaf_pubkey (32 bytes): pubkey of the existing leaf found
/// - existing_leaf_hash (32 bytes): hash of the existing leaf value
/// - sibling_hashes (32 * n bytes): sibling hashes for the proof path
///
/// # Arguments
/// * `slot` - The slot number to encode in the proof header
///
/// # Returns
/// A Vec<u8> containing the binary representation compatible with C tn_state_proof_t
///
/// # Example
/// ```
/// use thru_base::bintrie::BinTrie;
/// use thru_base::bintrie_types::{Pubkey, Hash};
///
/// let mut trie = BinTrie::new();
/// let existing_key = Pubkey::new([1u8; 32]);
/// let existing_value = Hash::new([2u8; 32]);
/// trie.insert(existing_key, existing_value).unwrap();
///
/// let missing_key = Pubkey::new([3u8; 32]);
/// let proof = trie.prove_non_existence(&missing_key).unwrap();
///
/// let wire_data = proof.to_wire(12345);
/// assert!(wire_data.len() >= 104); // At least header + existing pubkey + hash
/// ```
pub fn to_wire(&self, slot: u64) -> Vec<u8> {
// Convert proof indices to path bitset (matching C tn_state_proof_idx_list_to_path_bitset)
let mut path_bitset = [0u8; 32];
for &idx in &self.proof.proof_indices {
let bit_idx = (idx % 64) as usize;
let word_idx = (idx / 64) as usize;
if word_idx < 4 {
// Convert to little-endian u64 array like C implementation
let start = word_idx * 8;
let mut word_bytes = [0u8; 8];
word_bytes.copy_from_slice(&path_bitset[start..start + 8]);
let mut word = u64::from_le_bytes(word_bytes);
word |= 1u64 << bit_idx;
path_bitset[start..start + 8].copy_from_slice(&word.to_le_bytes());
}
}
// Create header: type_slot (8 bytes) + path_bitset (32 bytes)
let mut result = Vec::with_capacity(40 + 64 + self.proof.sibling_hashes.len() * 32);
// Encode type_slot: slot in low 62 bits, type (CREATION=2) in high 2 bits
let type_slot = slot | (TN_STATE_PROOF_TYPE_CREATION << 62);
result.extend_from_slice(&type_slot.to_le_bytes());
// Add path bitset
result.extend_from_slice(&path_bitset);
// Add body for CREATION type:
// 1. existing_leaf_pubkey (32 bytes)
// 2. existing_leaf_hash (32 bytes)
// 3. sibling_hashes (32 bytes each)
result.extend_from_slice(self.existing_pubkey.as_bytes());
result.extend_from_slice(self.existing_hash.as_bytes());
for sibling_hash in &self.proof.sibling_hashes {
result.extend_from_slice(sibling_hash.as_bytes());
}
result
}
}