blyss_rs/
proof.rs

1use crate::{
2    api::{http_get_string, ApiClient},
3    error::Error,
4};
5use ruint::aliases::U256;
6use serde::{Deserialize, Serialize};
7
8/// A configuration for performing Merkle proof lookups using Blyss.
9///
10/// Typically loaded with `from_url` or `from_json`.
11#[derive(Debug, Clone, Serialize, Deserialize)]
12pub struct LookupCfg {
13    /// The URL of the Blyss bucket containing the subtrees and leaf nodes.
14    pub bucket_url: String,
15    /// The API key to optionally use when accessing the bucket. Can be empty.
16    pub api_key: String,
17    /// The URL of the JSON file containing the cap of the Merkle tree.
18    pub cap_url: String,
19    /// The height of the subtrees stored in the bucket.
20    pub subtree_height: usize,
21    /// The height of the cap of the Merkle tree.
22    pub cap_height: usize,
23    /// The height of the full Merkle tree.
24    pub tree_height: usize,
25}
26
27impl LookupCfg {
28    /// Fetch a `LookupCfg` from the given URL to a JSON object.
29    pub async fn from_url(url: &str) -> Result<LookupCfg, Error> {
30        let val = http_get_string(url, "").await?;
31        let cfg: LookupCfg = serde_json::from_str(&val)?;
32        Ok(cfg)
33    }
34
35    /// Parse a `LookupCfg` from given JSON string.
36    pub async fn from_json(json: &str) -> Result<LookupCfg, Error> {
37        let cfg: LookupCfg = serde_json::from_str(&json)?;
38        Ok(cfg)
39    }
40}
41
42/// A step in a Merkle proof.
43#[derive(Debug, Clone, Serialize, Deserialize)]
44pub struct ProofStep {
45    /// The value of the sibiling node at this step.
46    pub value: String,
47    /// The position of the sibiling node at this step.
48    /// `0` is on the left, and `1` is on the right.
49    pub pos: usize,
50}
51
52impl ProofStep {
53    /// Convert the string value for the sibiling node in this step to a `U256`.
54    pub fn u256(&self) -> U256 {
55        to_u256(&self.value)
56    }
57}
58
59/// Convert the given BE hex string to a `U256`.
60fn to_u256(value: &str) -> U256 {
61    U256::from_be_bytes::<32>(hex::decode(&value[2..]).unwrap().try_into().unwrap())
62}
63
64/// Get the indices of the subtrees needed to construct a Merkle proof for the given identity index.
65fn get_subtree_indices(lookup_cfg: &LookupCfg, identity_idx: usize) -> Vec<String> {
66    let mut keys_to_fetch = Vec::new();
67    let mut cur_level = lookup_cfg.tree_height - lookup_cfg.subtree_height;
68    while cur_level >= lookup_cfg.cap_height - 1 {
69        let idx_within_level = identity_idx >> (lookup_cfg.tree_height - 1 - cur_level);
70        let key = format!("{}-{}", cur_level, idx_within_level);
71        keys_to_fetch.push(key);
72
73        if cur_level >= lookup_cfg.subtree_height {
74            cur_level -= lookup_cfg.subtree_height - 1;
75        } else {
76            break;
77        }
78    }
79
80    keys_to_fetch
81}
82
83/// Get the Merkle proof for the given index in the given tree.
84fn get_subproof(tree: &[String], tree_height: usize, idx: usize) -> Vec<ProofStep> {
85    let mut out = Vec::new();
86    for level in 1..tree_height {
87        let mut idx_within_level = idx >> (tree_height - 1 - level);
88        idx_within_level ^= 1; // flip low bit to get sibiling
89
90        let tree_idx = (1 << level) - 1 + idx_within_level;
91        out.push(ProofStep {
92            value: tree[tree_idx].clone(),
93            pos: idx_within_level & 1,
94        });
95    }
96    out.reverse();
97    return out;
98}
99
100/// Construct a complete Merkle proof for the given identity index, given the appropriate subtrees.
101fn construct_merkle_proof(
102    lookup_cfg: &LookupCfg,
103    identity_idx: usize,
104    subtrees: &[Vec<String>],
105) -> Vec<ProofStep> {
106    let mut cur_level = lookup_cfg.tree_height - lookup_cfg.subtree_height;
107    let mut outer_idx = 0;
108
109    let mut proof = Vec::new();
110    while cur_level >= lookup_cfg.cap_height - 1 {
111        let subtree = &subtrees[outer_idx];
112        outer_idx += 1;
113        let idx_within_level = identity_idx >> (lookup_cfg.tree_height - 1 - cur_level);
114        let idx_within_subtree = (identity_idx
115            >> (lookup_cfg.tree_height - 1 - (cur_level + lookup_cfg.subtree_height - 1)))
116            - idx_within_level * (1 << (lookup_cfg.subtree_height - 1));
117
118        let proof_part = get_subproof(subtree, lookup_cfg.subtree_height, idx_within_subtree);
119        proof.extend(proof_part.into_iter());
120
121        if cur_level >= lookup_cfg.subtree_height {
122            cur_level -= lookup_cfg.subtree_height - 1;
123        } else {
124            break;
125        }
126    }
127
128    proof
129}
130
131/// Fetch the cap of the Merkle tree.
132async fn get_cap(url: &str) -> Result<Vec<String>, Error> {
133    let val = http_get_string(url, "").await?;
134    let cap: Vec<String> = serde_json::from_str(&val)?;
135    Ok(cap)
136}
137
138/// Get the index of the given identity within the cap.
139fn get_idx_within_cap(identity_idx: usize, tree_height: usize, cap_height: usize) -> usize {
140    let idx_within_level = identity_idx >> ((tree_height - 1) - (cap_height - 1));
141    idx_within_level
142}
143
144/// Fetch the Merkle proof for the given identity index using Blyss.
145async fn fetch_merkle_proof_at_idx(
146    client: &mut ApiClient,
147    lookup_cfg: &LookupCfg,
148    identity_idx: usize,
149) -> Result<Vec<ProofStep>, Error> {
150    let cap = get_cap(&lookup_cfg.cap_url).await?;
151    let subtrees_to_query = get_subtree_indices(lookup_cfg, identity_idx);
152    let subtrees = client.private_read(&subtrees_to_query).await?;
153    let mut subtrees_as_strs = Vec::new();
154    for s in subtrees {
155        let s: Vec<String> = serde_json::from_slice(&s)?;
156        subtrees_as_strs.push(s);
157    }
158    let mut proof = construct_merkle_proof(lookup_cfg, identity_idx, &subtrees_as_strs);
159    let cap_proof_part = get_subproof(
160        &cap,
161        lookup_cfg.cap_height,
162        get_idx_within_cap(identity_idx, lookup_cfg.tree_height, lookup_cfg.cap_height),
163    );
164    proof.extend(cap_proof_part.into_iter());
165
166    Ok(proof)
167}
168
169/// Get the index for the given identity commitment.
170async fn fetch_idx_for_identity(
171    client: &mut ApiClient,
172    identity_commitment: &str,
173) -> Result<usize, Error> {
174    let result = client
175        .private_read(&[identity_commitment.to_owned()])
176        .await?;
177    let index: usize = serde_json::from_slice(&result[0])?;
178
179    Ok(index)
180}
181
182/// Fetch the Merkle proof for the given identity commitment using Blyss, with the given lookup configuration.
183async fn private_fetch_merkle_proof_with_cfg(
184    identity_commitment: &str,
185    lookup_cfg: &LookupCfg,
186) -> Result<Vec<ProofStep>, Error> {
187    let mut owned_ic = identity_commitment.to_owned();
188    if !owned_ic.starts_with("0x") {
189        owned_ic = format!("0x{}", identity_commitment);
190    }
191    owned_ic = owned_ic.to_lowercase();
192
193    let mut client = ApiClient::new(&lookup_cfg.bucket_url, &lookup_cfg.api_key).await?;
194    client.setup().await?;
195
196    let index = fetch_idx_for_identity(&mut client, &owned_ic).await?;
197    let proof = fetch_merkle_proof_at_idx(&mut client, lookup_cfg, index).await?;
198    Ok(proof)
199}
200
201/// Privately fetch the Merkle proof for the given identity commitment using Blyss.
202///
203/// # Arguments
204/// - `lookup_cfg_url` - A URL pointing to the JSON lookup configuration (see `LookupCfg`).
205/// - `identity_commitment` - The identity commitment (as a big-endian hex string) to fetch the Merkle proof for.
206pub async fn private_fetch_merkle_proof(
207    identity_commitment: &str,
208    lookup_cfg_url: &str,
209) -> Result<Vec<ProofStep>, Error> {
210    let lookup_cfg = LookupCfg::from_url(lookup_cfg_url).await?;
211    private_fetch_merkle_proof_with_cfg(identity_commitment, &lookup_cfg).await
212}
213
214#[cfg(test)]
215mod tests {
216    use super::*;
217
218    use semaphore::poseidon;
219
220    fn to_str(value: &U256) -> String {
221        format!("0x{}", hex::encode(value.to_be_bytes::<32>()))
222    }
223
224    fn verify_proof(input: &str, proof: &[ProofStep], root: &str) {
225        let mut cur_hash = to_u256(&input);
226        for step in proof.iter() {
227            let step_hash = step.u256();
228
229            let new_hash = if step.pos == 0 {
230                poseidon::hash2(step_hash, cur_hash)
231            } else {
232                poseidon::hash2(cur_hash, step_hash)
233            };
234
235            cur_hash = new_hash;
236        }
237        assert_eq!(to_str(&cur_hash), root);
238    }
239
240    #[test]
241    fn proof_works() {
242        let sample_proof = vec![
243            ProofStep {
244                value: "0x0000000000000000000000000000000000000000000000000000000000000000"
245                    .to_string(),
246                pos: 1,
247            },
248            ProofStep {
249                value: "0x1df013c70209502f348ea55e649fd86687163959177e3c64eb81101982d46e05"
250                    .to_string(),
251                pos: 1,
252            },
253            ProofStep {
254                value: "0x1f4a2f66f412222c3b1d6c5ade414a3d8e4b2ebcd4b7500f88ee8284914d3aa3"
255                    .to_string(),
256                pos: 1,
257            },
258            ProofStep {
259                value: "0x16fc91b5ffdf1e4be6b6c8ba467017e605aaa4edf68c5a0419876fb12f558fc4"
260                    .to_string(),
261                pos: 1,
262            },
263            ProofStep {
264                value: "0x04650054c0e366b4fd06d65b5fe0b96f3e7e9169f50c176fa25dd50e7c52852f"
265                    .to_string(),
266                pos: 1,
267            },
268            ProofStep {
269                value: "0x1cebe7a720c3454e5f2e9780f9da6f46bc82db4345bea44f2a816f6d988a6d7e"
270                    .to_string(),
271                pos: 1,
272            },
273            ProofStep {
274                value: "0x101af632d69b4d1a993b04a53775cf7f12d65cc751355c3bb5bb540548c8de47"
275                    .to_string(),
276                pos: 1,
277            },
278            ProofStep {
279                value: "0x2187d3e9d93033adb4f250a6a33da9b24223f27c3dd2962082b62cd04c01a6e2"
280                    .to_string(),
281                pos: 1,
282            },
283            ProofStep {
284                value: "0x1c1a0b78b55b21366a680c8f1c412fbe93864a286195de2ae069e229b4f35874"
285                    .to_string(),
286                pos: 1,
287            },
288            ProofStep {
289                value: "0x19346ce3cc2e5d46c37aa750f1fbd2363d8546b27ceec21903a7b3dc180cabbf"
290                    .to_string(),
291                pos: 1,
292            },
293            ProofStep {
294                value: "0x0ffb8ffc70abd907f6548d7043654334dcac5675450b79a9a949b6d68482ce53"
295                    .to_string(),
296                pos: 1,
297            },
298            ProofStep {
299                value: "0x133028e8db184a9ec1d21cf5617909b6ccf2002ea95bf1f5b70532fc9f217d12"
300                    .to_string(),
301                pos: 1,
302            },
303            ProofStep {
304                value: "0x21e5840d5e45d43dac5b39ca1620979655c31732be490ae3180baa9d94603ef3"
305                    .to_string(),
306                pos: 1,
307            },
308            ProofStep {
309                value: "0x2d63fd584ac6c7ecc9fde3eab063f40f789ddae1336b256487b4f0f42403250a"
310                    .to_string(),
311                pos: 1,
312            },
313            ProofStep {
314                value: "0x23285ed2421e0cd54cf7722ba0478e5386bfba97054f2c00b7ee8ff1e5ae0224"
315                    .to_string(),
316                pos: 1,
317            },
318            ProofStep {
319                value: "0x21fc8d14983eab9b40668e78f816a785568973e2f7c5c70a921398abb804377b"
320                    .to_string(),
321                pos: 1,
322            },
323            ProofStep {
324                value: "0x11117446426ca7b68db951a0e90b75fa3895dfdb1e18d76dc009e1446be9bddb"
325                    .to_string(),
326                pos: 1,
327            },
328            ProofStep {
329                value: "0x10a801cdd8b09b93c1c4763547416bf3a6a1b501af87f2e222e00689c82d3a6d"
330                    .to_string(),
331                pos: 1,
332            },
333            ProofStep {
334                value: "0x0ea484bbc862f222255634d1859c1c3e3602571e958b0e3acf29f1634f3b45a9"
335                    .to_string(),
336                pos: 1,
337            },
338            ProofStep {
339                value: "0x1a8c640e78d2e23c36fca18cb69d1ed36ccfa691a26674f34c4077080cbbb16f"
340                    .to_string(),
341                pos: 1,
342            },
343        ];
344
345        let root = "0x205aff5d8fc468b111f6fba374f5ba3bdaf02b37a741fd675fac334350f19880";
346        verify_proof(
347            "0x0000000000000000000000000000000000000000000000000000000000000000",
348            &sample_proof,
349            root,
350        );
351    }
352}
blyss_rs/proof.rs

blyss_rs/
proof.rs
