lox/src/trust_promotion.rs

/*! A module for the protocol for the user to get promoted from
untrusted (trust level 0) to trusted (trust level 1).

They are allowed to do this as long as UNTRUSTED_INTERVAL days have
passed since they obtained their level 0 Lox credential, and their
bridge (level 0 users get put in a one-bridge bucket) has not been
blocked.  (Blocked bridges in one-bridge buckets will have their entries
removed from the bridge authority's migration table.)

The user presents their current Lox credential:
- id: revealed
- bucket: blinded
- trust_level: revealed to be 0
- level_since: blinded, but proved in ZK that it's at least
  UNTRUSTED_INTERVAL days ago
- invites_remaining: revealed to be 0
- invites_issued: revealed to be 0

They will receive in return the encrypted MAC (Pk, EncQk) for their
implicit Migration Key credential with attributes id and bucket,
along with a HashMap of encrypted Migration credentials.  For each
(from_i, to_i) in the BA's migration list, there will be an entry in
the HashMap with key H1(id, from_attr_i, Qk_i) and value
Enc_{H2(id, from_attr_i, Qk_i)}(to_attr_i, P_i, Q_i).  Here H1 and H2
are the first 16 bytes and the second 16 bytes respectively of the
SHA256 hash of the input, P_i and Q_i are a MAC on the Migration
credential with attributes id, from_attr_i, and to_attr_i. Qk_i is the
value EncQk would decrypt to if bucket were equal to from_attr_i. */

use curve25519_dalek::ristretto::RistrettoBasepointTable;
use curve25519_dalek::ristretto::RistrettoPoint;
use curve25519_dalek::scalar::Scalar;
use curve25519_dalek::traits::IsIdentity;

use zkp::CompactProof;
use zkp::ProofError;
use zkp::Transcript;

use super::cred;
use super::IssuerPubKey;
use super::{scalar_dbl, scalar_u64};
use super::{CMZ_A, CMZ_A_TABLE, CMZ_B, CMZ_B_TABLE};

/// The minimum number of days a user has to be at trust level 0
/// (untrusted) with their (single) bridge unblocked before they can
/// move to level 1.
///
/// The implementation also puts an upper bound of UNTRUSTED_INTERVAL +
/// 511 days, which is not unreasonable; we want users to be engaging
/// with the system in order to move up trust levels.
pub const UNTRUSTED_INTERVAL: u64 = 30;

pub struct Request {
    // Fields for blind showing the Lox credential
    // We don't need to include trust_level, invites_remaining, or
    // invites_issued, since they must be 0
    P: RistrettoPoint,
    id: Scalar,
    CBucket: RistrettoPoint,
    CSince: RistrettoPoint,
    CQ: RistrettoPoint,

    // Fields for user blinding of the Migration Key credential
    D: RistrettoPoint,
    EncBucket: (RistrettoPoint, RistrettoPoint),

    // Fields for the inequality proof (level_since +
    // UNTRUSTED_INTERVAL <= today)
    CG1: RistrettoPoint,
    CG2: RistrettoPoint,
    CG3: RistrettoPoint,
    CG4: RistrettoPoint,
    CG5: RistrettoPoint,
    CG6: RistrettoPoint,
    CG7: RistrettoPoint,
    CG8: RistrettoPoint,

    // The combined ZKP
    piUser: CompactProof,
}

#[derive(Debug)]
pub struct State {
    d: Scalar,
    D: RistrettoPoint,
    EncBucket: (RistrettoPoint, RistrettoPoint),
    id: Scalar,
    bucket: Scalar,
}

define_proof! {
    requestproof,
    "Trust Promotion Request",
    (bucket, since, zbucket, zsince, negzQ,
     d, ebucket,
     g0, g1, g2, g3, g4, g5, g6, g7, g8,
     zg0, zg1, zg2, zg3, zg4, zg5, zg6, zg7, zg8,
     wg0, wg1, wg2, wg3, wg4, wg5, wg6, wg7, wg8,
     yg0, yg1, yg2, yg3, yg4, yg5, yg6, yg7, yg8),
    (P, CBucket, CSince, V, Xbucket, Xsince,
     EncBucket0, EncBucket1, D,
     CG0, CG1, CG2, CG3, CG4, CG5, CG6, CG7, CG8,
     CG0sq, CG1sq, CG2sq, CG3sq, CG4sq, CG5sq, CG6sq, CG7sq, CG8sq),
    (A, B):
    // Blind showing of the Lox credential
    CBucket = (bucket*P + zbucket*A),
    CSince = (since*P + zsince*A),
    V = (zbucket*Xbucket + zsince*Xsince + negzQ*A),
    // User blinding of the Migration Key credential
    EncBucket0 = (ebucket*B),
    EncBucket1 = (bucket*B + ebucket*D),
    D = (d*B),
    // Prove CSince encodes a value at least UNTRUSTED_INTERVAL
    // days ago (at technically at most UNTRUSTED_INTERVAL+511 days
    // ago): first prove each of g0, ..., g8 is a bit by proving that
    // gi = gi^2
    CG0 = (g0*P + zg0*A), CG0sq = (g0*CG0 + wg0*A), CG0sq = (g0*P + yg0*A),
    CG1 = (g1*P + zg1*A), CG1sq = (g1*CG1 + wg1*A), CG1sq = (g1*P + yg1*A),
    CG2 = (g2*P + zg2*A), CG2sq = (g2*CG2 + wg2*A), CG2sq = (g2*P + yg2*A),
    CG3 = (g3*P + zg3*A), CG3sq = (g3*CG3 + wg3*A), CG3sq = (g3*P + yg3*A),
    CG4 = (g4*P + zg4*A), CG4sq = (g4*CG4 + wg4*A), CG4sq = (g4*P + yg4*A),
    CG5 = (g5*P + zg5*A), CG5sq = (g5*CG5 + wg5*A), CG5sq = (g5*P + yg5*A),
    CG6 = (g6*P + zg6*A), CG6sq = (g6*CG6 + wg6*A), CG6sq = (g6*P + yg6*A),
    CG7 = (g7*P + zg7*A), CG7sq = (g7*CG7 + wg7*A), CG7sq = (g7*P + yg7*A),
    CG8 = (g8*P + zg8*A), CG8sq = (g8*CG8 + wg8*A), CG8sq = (g8*P + yg8*A)
    // Then we'll check that CSince + UNTRUSTED_INTERVAL*P + CG0 + 2*CG1
    // + 4*CG2 + 8*CG3 + ... + 256*CG8 = today*P by having the verifier
    // plug in today*P - (CSince + UNTRUSTED_INTERVAL*P + 2*CG1 + 4*CG2
    // + ... + 256*CG8) as its value of CG0.
}

pub fn request(
    lox_cred: &cred::Lox,
    lox_pub: &IssuerPubKey,
    today: u64,
) -> Result<(Request, State), ProofError> {
    let A: &RistrettoPoint = &CMZ_A;
    let B: &RistrettoPoint = &CMZ_B;
    let Atable: &RistrettoBasepointTable = &CMZ_A_TABLE;
    let Btable: &RistrettoBasepointTable = &CMZ_B_TABLE;

    // Ensure the credential can be correctly shown: it must be the case
    // that level_since + UNTRUSTED_INTERVAL <= today.
    let level_since: u64 = match scalar_u64(&lox_cred.level_since) {
        Some(v) => v,
        None => return Err(ProofError::VerificationFailure),
    };
    if level_since + UNTRUSTED_INTERVAL > today {
        return Err(ProofError::VerificationFailure);
    }
    let diffdays = today - (level_since + UNTRUSTED_INTERVAL);
    if diffdays > 511 {
        return Err(ProofError::VerificationFailure);
    }

    // Blind showing the Lox credential

    // Reblind P and Q
    let mut rng = rand::thread_rng();
    let t = Scalar::random(&mut rng);
    let P = t * lox_cred.P;
    let Q = t * lox_cred.Q;

    // Form Pedersen commitments to the blinded attributes
    let zbucket = Scalar::random(&mut rng);
    let zsince = Scalar::random(&mut rng);
    let CBucket = lox_cred.bucket * P + &zbucket * Atable;
    let CSince = lox_cred.level_since * P + &zsince * Atable;

    // Form a Pedersen commitment to the MAC Q
    // We flip the sign of zQ from that of the Hyphae paper so that
    // the ZKP has a "+" instead of a "-", as that's what the zkp
    // macro supports.
    let negzQ = Scalar::random(&mut rng);
    let CQ = Q - &negzQ * Atable;

    // Compute the "error factor"
    let V = zbucket * lox_pub.X[2] + zsince * lox_pub.X[4] + &negzQ * Atable;

    // User blinding the Migration Key credential

    // Pick an ElGamal keypair
    let d = Scalar::random(&mut rng);
    let D = &d * Btable;

    // Encrypt the attributes to be blinded (each times the
    // basepoint B) to the public key we just created
    let ebucket = Scalar::random(&mut rng);
    let EncBucket = (&ebucket * Btable, &lox_cred.bucket * Btable + ebucket * D);

    // The range proof that 0 <= diffdays <= 511

    // Extract the 9 bits from diffdays
    let g0: Scalar = (diffdays & 1).into();
    let g1: Scalar = ((diffdays >> 1) & 1).into();
    let g2: Scalar = ((diffdays >> 2) & 1).into();
    let g3: Scalar = ((diffdays >> 3) & 1).into();
    let g4: Scalar = ((diffdays >> 4) & 1).into();
    let g5: Scalar = ((diffdays >> 5) & 1).into();
    let g6: Scalar = ((diffdays >> 6) & 1).into();
    let g7: Scalar = ((diffdays >> 7) & 1).into();
    let g8: Scalar = ((diffdays >> 8) & 1).into();

    // Pick random factors for the Pedersen commitments
    let wg0 = Scalar::random(&mut rng);
    let zg1 = Scalar::random(&mut rng);
    let wg1 = Scalar::random(&mut rng);
    let zg2 = Scalar::random(&mut rng);
    let wg2 = Scalar::random(&mut rng);
    let zg3 = Scalar::random(&mut rng);
    let wg3 = Scalar::random(&mut rng);
    let zg4 = Scalar::random(&mut rng);
    let wg4 = Scalar::random(&mut rng);
    let zg5 = Scalar::random(&mut rng);
    let wg5 = Scalar::random(&mut rng);
    let zg6 = Scalar::random(&mut rng);
    let wg6 = Scalar::random(&mut rng);
    let zg7 = Scalar::random(&mut rng);
    let wg7 = Scalar::random(&mut rng);
    let zg8 = Scalar::random(&mut rng);
    let wg8 = Scalar::random(&mut rng);

    // Compute zg0 to cancel things out as
    // zg0 = -(zsince + 2*zg1 + 4*zg2 + 8*zg3 + 16*zg4 + 32*zg5 + 64*zg6 + 128*zg7 + 256*zg8)
    // but use Horner's method
    let zg0 = -scalar_dbl(
        &(scalar_dbl(
            &(scalar_dbl(
                &(scalar_dbl(
                    &(scalar_dbl(
                        &(scalar_dbl(&(scalar_dbl(&(scalar_dbl(&zg8) + zg7)) + zg6)) + zg5),
                    ) + zg4),
                ) + zg3),
            ) + zg2),
        ) + zg1),
    ) + zsince;

    let yg0 = wg0 + g0 * zg0;
    let yg1 = wg1 + g1 * zg1;
    let yg2 = wg2 + g2 * zg2;
    let yg3 = wg3 + g3 * zg3;
    let yg4 = wg4 + g4 * zg4;
    let yg5 = wg5 + g5 * zg5;
    let yg6 = wg6 + g6 * zg6;
    let yg7 = wg7 + g7 * zg7;
    let yg8 = wg8 + g8 * zg8;

    let CG0 = g0 * P + &zg0 * Atable;
    let CG1 = g1 * P + &zg1 * Atable;
    let CG2 = g2 * P + &zg2 * Atable;
    let CG3 = g3 * P + &zg3 * Atable;
    let CG4 = g4 * P + &zg4 * Atable;
    let CG5 = g5 * P + &zg5 * Atable;
    let CG6 = g6 * P + &zg6 * Atable;
    let CG7 = g7 * P + &zg7 * Atable;
    let CG8 = g8 * P + &zg8 * Atable;

    // Construct the proof
    let mut transcript = Transcript::new(b"trust promotion request");
    let piUser = requestproof::prove_compact(
        &mut transcript,
        requestproof::ProveAssignments {
            A: &A,
            B: &B,
            P: &P,
            CBucket: &CBucket,
            CSince: &CSince,
            V: &V,
            Xbucket: &lox_pub.X[2],
            Xsince: &lox_pub.X[4],
            EncBucket0: &EncBucket.0,
            EncBucket1: &EncBucket.1,
            D: &D,
            CG0: &CG0,
            CG1: &CG1,
            CG2: &CG2,
            CG3: &CG3,
            CG4: &CG4,
            CG5: &CG5,
            CG6: &CG6,
            CG7: &CG7,
            CG8: &CG8,
            CG0sq: &(g0 * P + &yg0 * Atable),
            CG1sq: &(g1 * P + &yg1 * Atable),
            CG2sq: &(g2 * P + &yg2 * Atable),
            CG3sq: &(g3 * P + &yg3 * Atable),
            CG4sq: &(g4 * P + &yg4 * Atable),
            CG5sq: &(g5 * P + &yg5 * Atable),
            CG6sq: &(g6 * P + &yg6 * Atable),
            CG7sq: &(g7 * P + &yg7 * Atable),
            CG8sq: &(g8 * P + &yg8 * Atable),
            bucket: &lox_cred.bucket,
            since: &lox_cred.level_since,
            zbucket: &zbucket,
            zsince: &zsince,
            negzQ: &negzQ,
            d: &d,
            ebucket: &ebucket,
            g0: &g0,
            g1: &g1,
            g2: &g2,
            g3: &g3,
            g4: &g4,
            g5: &g5,
            g6: &g6,
            g7: &g7,
            g8: &g8,
            zg0: &zg0,
            zg1: &zg1,
            zg2: &zg2,
            zg3: &zg3,
            zg4: &zg4,
            zg5: &zg5,
            zg6: &zg6,
            zg7: &zg7,
            zg8: &zg8,
            wg0: &wg0,
            wg1: &wg1,
            wg2: &wg2,
            wg3: &wg3,
            wg4: &wg4,
            wg5: &wg5,
            wg6: &wg6,
            wg7: &wg7,
            wg8: &wg8,
            yg0: &yg0,
            yg1: &yg1,
            yg2: &yg2,
            yg3: &yg3,
            yg4: &yg4,
            yg5: &yg5,
            yg6: &yg6,
            yg7: &yg7,
            yg8: &yg8,
        },
    )
    .0;

    Ok((
        Request {
            P,
            id: lox_cred.id,
            CBucket,
            CSince,
            CQ,
            D,
            EncBucket,
            CG1,
            CG2,
            CG3,
            CG4,
            CG5,
            CG6,
            CG7,
            CG8,
            piUser,
        },
        State {
            d,
            D,
            EncBucket,
            id: lox_cred.id,
            bucket: lox_cred.bucket,
        },
    ))
}