lox_library/proto/
trust_promotion.rs

1/*! A module for the protocol for the user to get promoted from
2untrusted (trust level 0) to trusted (trust level 1).
3
4They are allowed to do this as long as UNTRUSTED_INTERVAL days have
5passed since they obtained their level 0 Lox credential, and their
6bridge (level 0 users get put in a one-bridge bucket) has not been
7blocked.  (Blocked bridges in one-bridge buckets will have their entries
8removed from the bridge authority's migration table.)
9
10The user presents their current Lox credential:
11- id: revealed
12- bucket: blinded
13- trust_level: revealed to be 0
14- level_since: blinded, but proved in ZK that it's at least
15  UNTRUSTED_INTERVAL days ago
16- invites_remaining: revealed to be 0
17- blockages: revealed to be 0
18
19They will receive in return the encrypted MAC (Pk, EncQk) for their
20implicit Migration Key credential with attributes id and bucket,
21along with a HashMap of encrypted Migration credentials.  For each
22(from_i, to_i) in the BA's migration list, there will be an entry in
23the HashMap with key H1(id, from_attr_i, Qk_i) and value
24Enc_{H2(id, from_attr_i, Qk_i)}(to_attr_i, P_i, Q_i).  Here H1 and H2
25are the first 16 bytes and the second 16 bytes respectively of the
26SHA256 hash of the input, P_i and Q_i are a MAC on the Migration
27credential with attributes id, from_attr_i, and to_attr_i. Qk_i is the
28value EncQk would decrypt to if bucket were equal to from_attr_i. */
29
30use curve25519_dalek::ristretto::RistrettoBasepointTable;
31use curve25519_dalek::ristretto::RistrettoPoint;
32use curve25519_dalek::scalar::Scalar;
33use curve25519_dalek::traits::IsIdentity;
34
35use lox_zkp::CompactProof;
36use lox_zkp::ProofError;
37use lox_zkp::Transcript;
38
39use serde::{Deserialize, Serialize};
40use serde_with::serde_as;
41
42use std::collections::HashMap;
43
44use super::super::cred;
45#[cfg(feature = "bridgeauth")]
46use super::super::dup_filter::SeenType;
47use super::super::migration_table;
48#[cfg(feature = "bridgeauth")]
49use super::super::pt_dbl;
50#[cfg(feature = "bridgeauth")]
51use super::super::BridgeAuth;
52use super::super::IssuerPubKey;
53use super::super::{scalar_dbl, scalar_u32};
54use super::super::{CMZ_A, CMZ_A_TABLE, CMZ_B, CMZ_B_TABLE};
55
56use super::errors::CredentialError;
57
58/// The minimum number of days a user has to be at trust level 0
59/// (untrusted) with their (single) bridge unblocked before they can
60/// move to level 1.
61///
62/// The implementation also puts an upper bound of UNTRUSTED_INTERVAL +
63/// 511 days, which is not unreasonable; we want users to be engaging
64/// with the system in order to move up trust levels.
65pub const UNTRUSTED_INTERVAL: u32 = 30;
66
67#[derive(Serialize, Deserialize)]
68pub struct Request {
69    // Fields for blind showing the Lox credential
70    // We don't need to include trust_level, invites_remaining, or
71    // blockages, since they must be 0
72    P: RistrettoPoint,
73    id: Scalar,
74    CBucket: RistrettoPoint,
75    CSince: RistrettoPoint,
76    CQ: RistrettoPoint,
77
78    // Fields for user blinding of the Migration Key credential
79    D: RistrettoPoint,
80    EncBucket: (RistrettoPoint, RistrettoPoint),
81
82    // Fields for the inequality proof (level_since +
83    // UNTRUSTED_INTERVAL <= today)
84    CG1: RistrettoPoint,
85    CG2: RistrettoPoint,
86    CG3: RistrettoPoint,
87    CG4: RistrettoPoint,
88    CG5: RistrettoPoint,
89    CG6: RistrettoPoint,
90    CG7: RistrettoPoint,
91    CG8: RistrettoPoint,
92    CG0sq: RistrettoPoint,
93    CG1sq: RistrettoPoint,
94    CG2sq: RistrettoPoint,
95    CG3sq: RistrettoPoint,
96    CG4sq: RistrettoPoint,
97    CG5sq: RistrettoPoint,
98    CG6sq: RistrettoPoint,
99    CG7sq: RistrettoPoint,
100    CG8sq: RistrettoPoint,
101
102    // The combined ZKP
103    piUser: CompactProof,
104}
105
106#[derive(Debug, Serialize, Deserialize)]
107pub struct State {
108    d: Scalar,
109    D: RistrettoPoint,
110    EncBucket: (RistrettoPoint, RistrettoPoint),
111    id: Scalar,
112    bucket: Scalar,
113}
114
115#[serde_as]
116#[derive(Serialize, Deserialize, Debug)]
117pub struct Response {
118    // The encrypted MAC for the Migration Key credential
119    Pk: RistrettoPoint,
120    EncQk: (RistrettoPoint, RistrettoPoint),
121
122    // A table of encrypted Migration credentials; the encryption keys
123    // are formed from the possible values of Qk (the decrypted form of
124    // EncQk)
125    #[serde_as(as = "Vec<(_,[_; migration_table::ENC_MIGRATION_BYTES])>")]
126    enc_migration_table: HashMap<[u8; 16], [u8; migration_table::ENC_MIGRATION_BYTES]>,
127}
128
129define_proof! {
130    requestproof,
131    "Trust Promotion Request",
132    (bucket, since, zbucket, zsince, negzQ,
133     d, ebucket,
134     g0, g1, g2, g3, g4, g5, g6, g7, g8,
135     zg0, zg1, zg2, zg3, zg4, zg5, zg6, zg7, zg8,
136     wg0, wg1, wg2, wg3, wg4, wg5, wg6, wg7, wg8,
137     yg0, yg1, yg2, yg3, yg4, yg5, yg6, yg7, yg8),
138    (P, CBucket, CSince, V, Xbucket, Xsince,
139     D, EncBucket0, EncBucket1,
140     CG0, CG1, CG2, CG3, CG4, CG5, CG6, CG7, CG8,
141     CG0sq, CG1sq, CG2sq, CG3sq, CG4sq, CG5sq, CG6sq, CG7sq, CG8sq),
142    (A, B):
143    // Blind showing of the Lox credential
144    CBucket = (bucket*P + zbucket*A),
145    CSince = (since*P + zsince*A),
146    V = (zbucket*Xbucket + zsince*Xsince + negzQ*A),
147    // User blinding of the Migration Key credential
148    D = (d*B),
149    EncBucket0 = (ebucket*B),
150    EncBucket1 = (bucket*B + ebucket*D),
151    // Prove CSince encodes a value at least UNTRUSTED_INTERVAL
152    // days ago (and technically at most UNTRUSTED_INTERVAL+511 days
153    // ago): first prove each of g0, ..., g8 is a bit by proving that
154    // gi = gi^2
155    CG0 = (g0*P + zg0*A), CG0sq = (g0*CG0 + wg0*A), CG0sq = (g0*P + yg0*A),
156    CG1 = (g1*P + zg1*A), CG1sq = (g1*CG1 + wg1*A), CG1sq = (g1*P + yg1*A),
157    CG2 = (g2*P + zg2*A), CG2sq = (g2*CG2 + wg2*A), CG2sq = (g2*P + yg2*A),
158    CG3 = (g3*P + zg3*A), CG3sq = (g3*CG3 + wg3*A), CG3sq = (g3*P + yg3*A),
159    CG4 = (g4*P + zg4*A), CG4sq = (g4*CG4 + wg4*A), CG4sq = (g4*P + yg4*A),
160    CG5 = (g5*P + zg5*A), CG5sq = (g5*CG5 + wg5*A), CG5sq = (g5*P + yg5*A),
161    CG6 = (g6*P + zg6*A), CG6sq = (g6*CG6 + wg6*A), CG6sq = (g6*P + yg6*A),
162    CG7 = (g7*P + zg7*A), CG7sq = (g7*CG7 + wg7*A), CG7sq = (g7*P + yg7*A),
163    CG8 = (g8*P + zg8*A), CG8sq = (g8*CG8 + wg8*A), CG8sq = (g8*P + yg8*A)
164    // Then we'll check that CSince + UNTRUSTED_INTERVAL*P + CG0 + 2*CG1
165    // + 4*CG2 + 8*CG3 + ... + 256*CG8 = today*P by having the verifier
166    // plug in today*P - (CSince + UNTRUSTED_INTERVAL*P + 2*CG1 + 4*CG2
167    // + ... + 256*CG8) as its value of CG0.
168}
169
170pub fn request(
171    lox_cred: &cred::Lox,
172    lox_pub: &IssuerPubKey,
173    today: u32,
174) -> Result<(Request, State), CredentialError> {
175    let A: &RistrettoPoint = &CMZ_A;
176    let B: &RistrettoPoint = &CMZ_B;
177    let Atable: &RistrettoBasepointTable = &CMZ_A_TABLE;
178    let Btable: &RistrettoBasepointTable = &CMZ_B_TABLE;
179
180    // Ensure the credential can be correctly shown: it must be the case
181    // that level_since + UNTRUSTED_INTERVAL <= today.
182    let level_since: u32 = match scalar_u32(&lox_cred.level_since) {
183        Some(v) => v,
184        None => {
185            return Err(CredentialError::InvalidField(
186                String::from("level_since"),
187                String::from("could not be converted to u32"),
188            ))
189        }
190    };
191    if level_since + UNTRUSTED_INTERVAL > today {
192        return Err(CredentialError::TimeThresholdNotMet(
193            level_since + UNTRUSTED_INTERVAL - today,
194        ));
195    }
196    let diffdays = today - (level_since + UNTRUSTED_INTERVAL);
197    if diffdays > 511 {
198        return Err(CredentialError::CredentialExpired);
199    }
200
201    // Blind showing the Lox credential
202
203    // Reblind P and Q
204    let mut rng = rand::thread_rng();
205    let t = Scalar::random(&mut rng);
206    let P = t * lox_cred.P;
207    let Q = t * lox_cred.Q;
208
209    // Form Pedersen commitments to the blinded attributes
210    let zbucket = Scalar::random(&mut rng);
211    let zsince = Scalar::random(&mut rng);
212    let CBucket = lox_cred.bucket * P + &zbucket * Atable;
213    let CSince = lox_cred.level_since * P + &zsince * Atable;
214
215    // Form a Pedersen commitment to the MAC Q
216    // We flip the sign of zQ from that of the Hyphae paper so that
217    // the ZKP has a "+" instead of a "-", as that's what the zkp
218    // macro supports.
219    let negzQ = Scalar::random(&mut rng);
220    let CQ = Q - &negzQ * Atable;
221
222    // Compute the "error factor"
223    let V = zbucket * lox_pub.X[2] + zsince * lox_pub.X[4] + &negzQ * Atable;
224
225    // User blinding the Migration Key credential
226
227    // Pick an ElGamal keypair
228    let d = Scalar::random(&mut rng);
229    let D = &d * Btable;
230
231    // Encrypt the attributes to be blinded (each times the
232    // basepoint B) to the public key we just created
233    let ebucket = Scalar::random(&mut rng);
234    let EncBucket = (&ebucket * Btable, &lox_cred.bucket * Btable + ebucket * D);
235
236    // The range proof that 0 <= diffdays <= 511
237
238    // Extract the 9 bits from diffdays
239    let g0: Scalar = (diffdays & 1).into();
240    let g1: Scalar = ((diffdays >> 1) & 1).into();
241    let g2: Scalar = ((diffdays >> 2) & 1).into();
242    let g3: Scalar = ((diffdays >> 3) & 1).into();
243    let g4: Scalar = ((diffdays >> 4) & 1).into();
244    let g5: Scalar = ((diffdays >> 5) & 1).into();
245    let g6: Scalar = ((diffdays >> 6) & 1).into();
246    let g7: Scalar = ((diffdays >> 7) & 1).into();
247    let g8: Scalar = ((diffdays >> 8) & 1).into();
248
249    // Pick random factors for the Pedersen commitments
250    let wg0 = Scalar::random(&mut rng);
251    let zg1 = Scalar::random(&mut rng);
252    let wg1 = Scalar::random(&mut rng);
253    let zg2 = Scalar::random(&mut rng);
254    let wg2 = Scalar::random(&mut rng);
255    let zg3 = Scalar::random(&mut rng);
256    let wg3 = Scalar::random(&mut rng);
257    let zg4 = Scalar::random(&mut rng);
258    let wg4 = Scalar::random(&mut rng);
259    let zg5 = Scalar::random(&mut rng);
260    let wg5 = Scalar::random(&mut rng);
261    let zg6 = Scalar::random(&mut rng);
262    let wg6 = Scalar::random(&mut rng);
263    let zg7 = Scalar::random(&mut rng);
264    let wg7 = Scalar::random(&mut rng);
265    let zg8 = Scalar::random(&mut rng);
266    let wg8 = Scalar::random(&mut rng);
267
268    // Compute zg0 to cancel things out as
269    // zg0 = -(zsince + 2*zg1 + 4*zg2 + 8*zg3 + 16*zg4 + 32*zg5 + 64*zg6 + 128*zg7 + 256*zg8)
270    // but use Horner's method
271    let zg0 = -(scalar_dbl(
272        &(scalar_dbl(
273            &(scalar_dbl(
274                &(scalar_dbl(
275                    &(scalar_dbl(
276                        &(scalar_dbl(&(scalar_dbl(&(scalar_dbl(&zg8) + zg7)) + zg6)) + zg5),
277                    ) + zg4),
278                ) + zg3),
279            ) + zg2),
280        ) + zg1),
281    ) + zsince);
282
283    let yg0 = wg0 + g0 * zg0;
284    let yg1 = wg1 + g1 * zg1;
285    let yg2 = wg2 + g2 * zg2;
286    let yg3 = wg3 + g3 * zg3;
287    let yg4 = wg4 + g4 * zg4;
288    let yg5 = wg5 + g5 * zg5;
289    let yg6 = wg6 + g6 * zg6;
290    let yg7 = wg7 + g7 * zg7;
291    let yg8 = wg8 + g8 * zg8;
292
293    let CG0 = g0 * P + &zg0 * Atable;
294    let CG1 = g1 * P + &zg1 * Atable;
295    let CG2 = g2 * P + &zg2 * Atable;
296    let CG3 = g3 * P + &zg3 * Atable;
297    let CG4 = g4 * P + &zg4 * Atable;
298    let CG5 = g5 * P + &zg5 * Atable;
299    let CG6 = g6 * P + &zg6 * Atable;
300    let CG7 = g7 * P + &zg7 * Atable;
301    let CG8 = g8 * P + &zg8 * Atable;
302
303    let CG0sq = g0 * P + &yg0 * Atable;
304    let CG1sq = g1 * P + &yg1 * Atable;
305    let CG2sq = g2 * P + &yg2 * Atable;
306    let CG3sq = g3 * P + &yg3 * Atable;
307    let CG4sq = g4 * P + &yg4 * Atable;
308    let CG5sq = g5 * P + &yg5 * Atable;
309    let CG6sq = g6 * P + &yg6 * Atable;
310    let CG7sq = g7 * P + &yg7 * Atable;
311    let CG8sq = g8 * P + &yg8 * Atable;
312
313    // Construct the proof
314    let mut transcript = Transcript::new(b"trust promotion request");
315    let piUser = requestproof::prove_compact(
316        &mut transcript,
317        requestproof::ProveAssignments {
318            A,
319            B,
320            P: &P,
321            CBucket: &CBucket,
322            CSince: &CSince,
323            V: &V,
324            Xbucket: &lox_pub.X[2],
325            Xsince: &lox_pub.X[4],
326            D: &D,
327            EncBucket0: &EncBucket.0,
328            EncBucket1: &EncBucket.1,
329            CG0: &CG0,
330            CG1: &CG1,
331            CG2: &CG2,
332            CG3: &CG3,
333            CG4: &CG4,
334            CG5: &CG5,
335            CG6: &CG6,
336            CG7: &CG7,
337            CG8: &CG8,
338            CG0sq: &CG0sq,
339            CG1sq: &CG1sq,
340            CG2sq: &CG2sq,
341            CG3sq: &CG3sq,
342            CG4sq: &CG4sq,
343            CG5sq: &CG5sq,
344            CG6sq: &CG6sq,
345            CG7sq: &CG7sq,
346            CG8sq: &CG8sq,
347            bucket: &lox_cred.bucket,
348            since: &lox_cred.level_since,
349            zbucket: &zbucket,
350            zsince: &zsince,
351            negzQ: &negzQ,
352            d: &d,
353            ebucket: &ebucket,
354            g0: &g0,
355            g1: &g1,
356            g2: &g2,
357            g3: &g3,
358            g4: &g4,
359            g5: &g5,
360            g6: &g6,
361            g7: &g7,
362            g8: &g8,
363            zg0: &zg0,
364            zg1: &zg1,
365            zg2: &zg2,
366            zg3: &zg3,
367            zg4: &zg4,
368            zg5: &zg5,
369            zg6: &zg6,
370            zg7: &zg7,
371            zg8: &zg8,
372            wg0: &wg0,
373            wg1: &wg1,
374            wg2: &wg2,
375            wg3: &wg3,
376            wg4: &wg4,
377            wg5: &wg5,
378            wg6: &wg6,
379            wg7: &wg7,
380            wg8: &wg8,
381            yg0: &yg0,
382            yg1: &yg1,
383            yg2: &yg2,
384            yg3: &yg3,
385            yg4: &yg4,
386            yg5: &yg5,
387            yg6: &yg6,
388            yg7: &yg7,
389            yg8: &yg8,
390        },
391    )
392    .0;
393
394    Ok((
395        Request {
396            P,
397            id: lox_cred.id,
398            CBucket,
399            CSince,
400            CQ,
401            D,
402            EncBucket,
403            CG1,
404            CG2,
405            CG3,
406            CG4,
407            CG5,
408            CG6,
409            CG7,
410            CG8,
411            CG0sq,
412            CG1sq,
413            CG2sq,
414            CG3sq,
415            CG4sq,
416            CG5sq,
417            CG6sq,
418            CG7sq,
419            CG8sq,
420            piUser,
421        },
422        State {
423            d,
424            D,
425            EncBucket,
426            id: lox_cred.id,
427            bucket: lox_cred.bucket,
428        },
429    ))
430}
431
432#[cfg(feature = "bridgeauth")]
433impl BridgeAuth {
434    /// Receive a trust promotion request
435    pub fn handle_trust_promotion(&mut self, req: Request) -> Result<Response, ProofError> {
436        let A: &RistrettoPoint = &CMZ_A;
437        let B: &RistrettoPoint = &CMZ_B;
438        let Btable: &RistrettoBasepointTable = &CMZ_B_TABLE;
439
440        if req.P.is_identity() {
441            return Err(ProofError::VerificationFailure);
442        }
443
444        // Recompute the "error factor" using knowledge of our own
445        // (the issuer's) private key instead of knowledge of the
446        // hidden attributes
447        let Vprime = (self.lox_priv.x[0] + self.lox_priv.x[1] * req.id) * req.P
448            + self.lox_priv.x[2] * req.CBucket
449            + self.lox_priv.x[4] * req.CSince
450            - req.CQ;
451
452        // Recompute CG0 using Horner's method
453        let today: Scalar = self.today().into();
454        let unt: Scalar = UNTRUSTED_INTERVAL.into();
455        let CG0prime = (today - unt) * req.P
456            - req.CSince
457            - pt_dbl(
458                &(pt_dbl(
459                    &(pt_dbl(
460                        &(pt_dbl(
461                            &(pt_dbl(
462                                &(pt_dbl(&(pt_dbl(&(pt_dbl(&req.CG8) + req.CG7)) + req.CG6))
463                                    + req.CG5),
464                            ) + req.CG4),
465                        ) + req.CG3),
466                    ) + req.CG2),
467                ) + req.CG1),
468            );
469
470        // Verify the ZKP
471        let mut transcript = Transcript::new(b"trust promotion request");
472        requestproof::verify_compact(
473            &req.piUser,
474            &mut transcript,
475            requestproof::VerifyAssignments {
476                A: &A.compress(),
477                B: &B.compress(),
478                P: &req.P.compress(),
479                CBucket: &req.CBucket.compress(),
480                CSince: &req.CSince.compress(),
481                V: &Vprime.compress(),
482                Xbucket: &self.lox_pub.X[2].compress(),
483                Xsince: &self.lox_pub.X[4].compress(),
484                D: &req.D.compress(),
485                EncBucket0: &req.EncBucket.0.compress(),
486                EncBucket1: &req.EncBucket.1.compress(),
487                CG0: &CG0prime.compress(),
488                CG1: &req.CG1.compress(),
489                CG2: &req.CG2.compress(),
490                CG3: &req.CG3.compress(),
491                CG4: &req.CG4.compress(),
492                CG5: &req.CG5.compress(),
493                CG6: &req.CG6.compress(),
494                CG7: &req.CG7.compress(),
495                CG8: &req.CG8.compress(),
496                CG0sq: &req.CG0sq.compress(),
497                CG1sq: &req.CG1sq.compress(),
498                CG2sq: &req.CG2sq.compress(),
499                CG3sq: &req.CG3sq.compress(),
500                CG4sq: &req.CG4sq.compress(),
501                CG5sq: &req.CG5sq.compress(),
502                CG6sq: &req.CG6sq.compress(),
503                CG7sq: &req.CG7sq.compress(),
504                CG8sq: &req.CG8sq.compress(),
505            },
506        )?;
507
508        // Ensure the id has not been seen before, either in the general
509        // id filter, or the filter specifically for trust promotion.
510        // Add the id to the latter, but not the former.
511        if self.id_filter.check(&req.id) == SeenType::Seen
512            || self.trust_promotion_filter.filter(&req.id) == SeenType::Seen
513        {
514            return Err(ProofError::VerificationFailure);
515        }
516
517        // Compute the encrypted MAC (Pk, EncQk) for the Migration Key
518        // credential.
519
520        // Compute the MAC on the visible attributes
521        let mut rng = rand::thread_rng();
522        let b = Scalar::random(&mut rng);
523        let Pk = &b * Btable;
524        let Pktable = RistrettoBasepointTable::create(&Pk);
525        let Qid = &(self.migrationkey_priv.x[0] + self.migrationkey_priv.x[1] * req.id) * &Pktable;
526
527        // El Gamal encrypt it to the public key req.D
528        let s = Scalar::random(&mut rng);
529        let EncQkid = (&s * Btable, Qid + s * req.D);
530
531        // Homomorphically compute the part of the MAC corresponding to
532        // the blinded attributes
533        let tbucket = self.migrationkey_priv.x[2] * b;
534        let EncQkBucket = (tbucket * req.EncBucket.0, tbucket * req.EncBucket.1);
535
536        let EncQk = (EncQkid.0 + EncQkBucket.0, EncQkid.1 + EncQkBucket.1);
537
538        Ok(Response {
539            Pk,
540            EncQk,
541            enc_migration_table: self.trustup_migration_table.encrypt_table(
542                &req.id,
543                &self.bridge_table,
544                &Pktable,
545                &self.migration_priv,
546                &self.migrationkey_priv,
547            ),
548        })
549    }
550}
551
552/// Handle the response to the request, producing a Migration credential
553/// if successful.
554///
555/// The Migration credential can then be used in the migration protocol
556/// to actually upgrade to trust level 1.
557pub fn handle_response(state: State, resp: Response) -> Result<cred::Migration, ProofError> {
558    if resp.Pk.is_identity() {
559        return Err(ProofError::VerificationFailure);
560    }
561
562    // Decrypt the MAC on the Migration Key credential
563    let Qk = resp.EncQk.1 - (state.d * resp.EncQk.0);
564
565    // Use Qk to locate and decrypt the Migration credential
566    match migration_table::decrypt_cred(
567        &Qk,
568        &state.id,
569        &state.bucket,
570        migration_table::MigrationType::TrustUpgrade,
571        &resp.enc_migration_table,
572    ) {
573        Some(m) => Ok(m),
574        None => Err(ProofError::VerificationFailure),
575    }
576}
lox_library/proto/trust_promotion.rs

lox_library/proto/
trust_promotion.rs
