lox/src/proto/level_up.rs

/*! A module for the protocol for the user to increase their trust level
(from a level at least 1; use the trust promotion protocol to go from
untrusted (level 0) to minimally trusted (level 1).

They are allowed to do this as long as some amount of time (depending on
their current level) has elapsed since their last level change, and they
have a Bucket Reachability credential for their current bucket and
today's date.  (Such credentials are placed daily in the encrypted
bridge table.)

The user presents their current Lox credential:
- id: revealed
- bucket: blinded
- trust_level: revealed, and must be at least 1
- level_since: blinded, but proved in ZK that it's at least the
  appropriate number of days ago
- invites_remaining: blinded
- invites_issued: blinded

and a Bucket Reachability credential:
- date: revealed to be today
- bucket: blinded, but proved in ZK that it's the same as in the Lox
  credential above

and a new Lox credential to be issued:

- id: jointly chosen by the user and BA
- bucket: blinded, but proved in ZK that it's the same as in the Lox
  credential above
- trust_level: revealed to be one more than the trust level above
- level_since: today
- invites_remaining: blinded, but proved in ZK that it's the same as in
  the Lox credential above, _plus_ a per-level constant
- invites_issued: blinded, but proved in ZK that it's the same as in the
  Lox credential above

*/

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::super::cred;
use super::super::dup_filter::SeenType;
use super::super::{pt_dbl, scalar_dbl, scalar_u32};
use super::super::{BridgeAuth, IssuerPubKey};
use super::super::{CMZ_A, CMZ_A_TABLE, CMZ_B, CMZ_B_TABLE};

/// LEVEL_INTERVAL\[i\] for i >= 1 is the minimum number of days a user
/// must be at trust level i before advancing to level i+1.  The large
/// last entry makes it impossible to advance past the top level.  Note
/// that the LEVEL_INTERVAL\[0\] entry is a dummy; the trust_promotion
/// protocol is used instead of this one to move from level 0 to level
/// 1.
pub const LEVEL_INTERVAL: [u32; 5] = [0, 14, 28, 56, u32::MAX];

/// LEVEL_INVITATIONS\[i\] for i >= 1 is the number of additional
/// invitations a user will be eligible to issue upon advancing from
/// level i to level i+1.  Again the LEVEL_INVITATIONS\[0\] entry is a
/// dummy, as for LEVEL_INTERVAL.  Also the last entry is 0 because
/// users cannot advance above the highest level.
pub const LEVEL_INVITATIONS: [u32; 5] = [0, 2, 4, 6, 0];

pub struct Request {
    // Fields for blind showing the Lox credential
    P: RistrettoPoint,
    id: Scalar,
    CBucket: RistrettoPoint,
    level: Scalar,
    CSince: RistrettoPoint,
    CInvRemain: RistrettoPoint,
    CInvIssued: RistrettoPoint,
    CQ: RistrettoPoint,

    // Fields for blind showing the Bucket Reachability credential
    P_reach: RistrettoPoint,
    CBucket_reach: RistrettoPoint,
    CQ_reach: RistrettoPoint,

    // Fields for the inequality proof (level_since +
    // LEVEL_INTERVAL[level] <= today)
    CG1: RistrettoPoint,
    CG2: RistrettoPoint,
    CG3: RistrettoPoint,
    CG4: RistrettoPoint,
    CG5: RistrettoPoint,
    CG6: RistrettoPoint,
    CG7: RistrettoPoint,
    CG8: RistrettoPoint,
    CG0sq: RistrettoPoint,
    CG1sq: RistrettoPoint,
    CG2sq: RistrettoPoint,
    CG3sq: RistrettoPoint,
    CG4sq: RistrettoPoint,
    CG5sq: RistrettoPoint,
    CG6sq: RistrettoPoint,
    CG7sq: RistrettoPoint,
    CG8sq: RistrettoPoint,

    // Fields for user blinding of the Lox credential to be issued
    D: RistrettoPoint,
    EncIdClient: (RistrettoPoint, RistrettoPoint),
    EncBucket: (RistrettoPoint, RistrettoPoint),
    EncInvRemain: (RistrettoPoint, RistrettoPoint),
    EncInvIssued: (RistrettoPoint, RistrettoPoint),

    // The combined ZKP
    piUser: CompactProof,
}

#[derive(Debug)]
pub struct State {
    d: Scalar,
    D: RistrettoPoint,
    EncIdClient: (RistrettoPoint, RistrettoPoint),
    EncBucket: (RistrettoPoint, RistrettoPoint),
    EncInvRemain: (RistrettoPoint, RistrettoPoint),
    EncInvIssued: (RistrettoPoint, RistrettoPoint),
    id_client: Scalar,
    bucket: Scalar,
    level: Scalar,
    invremain: Scalar,
    invissued: Scalar,
}

pub struct Response {
    // The fields for the new Lox credential; the new trust level is one
    // more than the old trust level, so we don't have to include it
    // here explicitly
    P: RistrettoPoint,
    EncQ: (RistrettoPoint, RistrettoPoint),
    id_server: Scalar,
    level_since: Scalar,
    TId: RistrettoPoint,
    TBucket: RistrettoPoint,
    TInvRemain: RistrettoPoint,
    TInvIssued: RistrettoPoint,

    // The fields for the implicit noop migration ("nm") credential
    P_nm: RistrettoPoint,
    EncQ_nm: (RistrettoPoint, RistrettoPoint),
    TId_nm: RistrettoPoint,
    TBucket_nm: RistrettoPoint,

    // The ZKP
    piBlindIssue: CompactProof,
}

define_proof! {
    requestproof,
    "Level Upgrade Request",
    (bucket, since, invremain, invissued, zbucket, zsince, zinvremain,
     zinvissued, negzQ,
     zbucket_reach, negzQ_reach,
     d, eid_client, ebucket, einvremain, einvissued, id_client,
     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, CInvRemain, CInvIssued, V, Xbucket, Xsince,
     Xinvremain, Xinvissued,
     P_reach, CBucket_reach, V_reach, Xbucket_reach,
     D, EncIdClient0, EncIdClient1, EncBucket0, EncBucket1,
     EncInvRemain0, EncInvRemain1_minus_LEVELINV_B,
     EncInvIssued0, EncInvIssued1,
     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),
    CInvRemain = (invremain*P + zinvremain*A),
    CInvIssued = (invissued*P + zinvissued*A),
    // Blind showing of the Bucket Reachability credential; note the
    // same bucket is used in the proof
    CBucket_reach = (bucket*P_reach + zbucket_reach*A),
    // User blinding of the Lox credential to be issued
    D = (d*B),
    EncIdClient0 = (eid_client*B),
    EncIdClient1 = (id_client*B + eid_client*D),
    EncBucket0 = (ebucket*B),
    EncBucket1 = (bucket*B + ebucket*D),
    EncInvRemain0 = (einvremain*B),
    EncInvRemain1_minus_LEVELINV_B = (invremain*B + einvremain*D),
    EncInvIssued0 = (einvissued*B),
    EncInvIssued1 = (invissued*B + einvissued*D),
    // Prove CSince encodes a value at least LEVEL_INTERVAL
    // days ago (at technically at most LEVEL_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 + LEVEL_INTERVAL*P + CG0 + 2*CG1
    // + 4*CG2 + 8*CG3 + ... + 256*CG8 = today*P by having the verifier
    // plug in today*P - (CSince + LEVEL_INTERVAL*P + 2*CG1 + 4*CG2
    // + ... + 256*CG8) as its value of CG0.
}

pub fn request(
    lox_cred: &cred::Lox,
    reach_cred: &cred::BucketReachability,
    lox_pub: &IssuerPubKey,
    reach_pub: &IssuerPubKey,
    today: u32,
) -> 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 + LEVEL_INTERVAL[level] <= today.
    let level_since: u32 = match scalar_u32(&lox_cred.level_since) {
        Some(v) => v,
        None => return Err(ProofError::VerificationFailure),
    };
    // The trust level has to be at least 1
    let trust_level: u32 = match scalar_u32(&lox_cred.trust_level) {
        Some(v) => v,
        None => return Err(ProofError::VerificationFailure),
    };
    if trust_level < 1 {
        return Err(ProofError::VerificationFailure);
    }
    // The trust level has to be no higher than the highest level
    let level_interval: u32 = match LEVEL_INTERVAL.get(trust_level as usize) {
        Some(&v) => v,
        None => return Err(ProofError::VerificationFailure),
    };
    if level_since + level_interval > today {
        return Err(ProofError::VerificationFailure);
    }
    // The credential can't be _too_ old
    let diffdays = today - (level_since + level_interval);
    if diffdays > 511 {
        return Err(ProofError::VerificationFailure);
    }
    // The buckets in the Lox and Bucket Reachability credentials have
    // to match
    if lox_cred.bucket != reach_cred.bucket {
        return Err(ProofError::VerificationFailure);
    }
    // The Bucket Reachability credential has to be dated today
    let reach_date: u32 = match scalar_u32(&reach_cred.date) {
        Some(v) => v,
        None => return Err(ProofError::VerificationFailure),
    };
    if reach_date != today {
        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 zinvremain = Scalar::random(&mut rng);
    let zinvissued = Scalar::random(&mut rng);
    let CBucket = lox_cred.bucket * P + &zbucket * Atable;
    let CSince = lox_cred.level_since * P + &zsince * Atable;
    let CInvRemain = lox_cred.invites_remaining * P + &zinvremain * Atable;
    let CInvIssued = lox_cred.invites_issued * P + &zinvissued * 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]
        + zinvremain * lox_pub.X[5]
        + zinvissued * lox_pub.X[6]
        + &negzQ * Atable;

    // Blind showing the Bucket Reachability credential

    // Reblind P and Q
    let t_reach = Scalar::random(&mut rng);
    let P_reach = t_reach * reach_cred.P;
    let Q_reach = t_reach * reach_cred.Q;

    // Form Pedersen commitments to the blinded attributes
    let zbucket_reach = Scalar::random(&mut rng);
    let CBucket_reach = reach_cred.bucket * P_reach + &zbucket_reach * 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_reach = Scalar::random(&mut rng);
    let CQ_reach = Q_reach - &negzQ_reach * Atable;

    // Compute the "error factor"
    let V_reach = zbucket_reach * reach_pub.X[2] + &negzQ_reach * Atable;

    // User blinding for the Lox certificate to be issued

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

    // Pick a random client component of the id
    let id_client = Scalar::random(&mut rng);

    // Encrypt it (times the basepoint B) to the ElGamal public key D we
    // just created
    let eid_client = Scalar::random(&mut rng);
    let EncIdClient = (&eid_client * Btable, &id_client * Btable + eid_client * D);

    // Encrypt the other blinded fields (times B) to D as well
    let ebucket = Scalar::random(&mut rng);
    let EncBucket = (&ebucket * Btable, &lox_cred.bucket * Btable + ebucket * D);
    let newinvites: Scalar = LEVEL_INVITATIONS[trust_level as usize].into();
    let einvremain = Scalar::random(&mut rng);
    let EncInvRemain = (
        &einvremain * Btable,
        &(lox_cred.invites_remaining + newinvites) * Btable + einvremain * D,
    );
    let einvissued = Scalar::random(&mut rng);
    let EncInvIssued = (
        &einvissued * Btable,
        &lox_cred.invites_issued * Btable + einvissued * 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;

    let CG0sq = g0 * P + &yg0 * Atable;
    let CG1sq = g1 * P + &yg1 * Atable;
    let CG2sq = g2 * P + &yg2 * Atable;
    let CG3sq = g3 * P + &yg3 * Atable;
    let CG4sq = g4 * P + &yg4 * Atable;
    let CG5sq = g5 * P + &yg5 * Atable;
    let CG6sq = g6 * P + &yg6 * Atable;
    let CG7sq = g7 * P + &yg7 * Atable;
    let CG8sq = g8 * P + &yg8 * Atable;

    // Construct the proof
    let mut transcript = Transcript::new(b"level upgrade request");
    let piUser = requestproof::prove_compact(
        &mut transcript,
        requestproof::ProveAssignments {
            A: &A,
            B: &B,
            P: &P,
            CBucket: &CBucket,
            CSince: &CSince,
            CInvRemain: &CInvRemain,
            CInvIssued: &CInvIssued,
            V: &V,
            Xbucket: &lox_pub.X[2],
            Xsince: &lox_pub.X[4],
            Xinvremain: &lox_pub.X[5],
            Xinvissued: &lox_pub.X[6],
            P_reach: &P_reach,
            CBucket_reach: &CBucket_reach,
            V_reach: &V_reach,
            Xbucket_reach: &reach_pub.X[2],
            D: &D,
            EncIdClient0: &EncIdClient.0,
            EncIdClient1: &EncIdClient.1,
            EncBucket0: &EncBucket.0,
            EncBucket1: &EncBucket.1,
            EncInvRemain0: &EncInvRemain.0,
            EncInvRemain1_minus_LEVELINV_B: &(EncInvRemain.1 - &newinvites * Btable),
            EncInvIssued0: &EncInvIssued.0,
            EncInvIssued1: &EncInvIssued.1,
            CG0: &CG0,
            CG1: &CG1,
            CG2: &CG2,
            CG3: &CG3,
            CG4: &CG4,
            CG5: &CG5,
            CG6: &CG6,
            CG7: &CG7,
            CG8: &CG8,
            CG0sq: &CG0sq,
            CG1sq: &CG1sq,
            CG2sq: &CG2sq,
            CG3sq: &CG3sq,
            CG4sq: &CG4sq,
            CG5sq: &CG5sq,
            CG6sq: &CG6sq,
            CG7sq: &CG7sq,
            CG8sq: &CG8sq,
            bucket: &lox_cred.bucket,
            since: &lox_cred.level_since,
            invremain: &lox_cred.invites_remaining,
            invissued: &lox_cred.invites_issued,
            zbucket: &zbucket,
            zsince: &zsince,
            zinvremain: &zinvremain,
            zinvissued: &zinvissued,
            negzQ: &negzQ,
            zbucket_reach: &zbucket_reach,
            negzQ_reach: &negzQ_reach,
            d: &d,
            eid_client: &eid_client,
            ebucket: &ebucket,
            einvremain: &einvremain,
            einvissued: &einvissued,
            id_client: &id_client,
            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,
            level: lox_cred.trust_level,
            CSince,
            CInvRemain,
            CInvIssued,
            CQ,
            P_reach,
            CBucket_reach,
            CQ_reach,
            D,
            EncIdClient,
            EncBucket,
            EncInvRemain,
            EncInvIssued,
            CG1,
            CG2,
            CG3,
            CG4,
            CG5,
            CG6,
            CG7,
            CG8,
            CG0sq,
            CG1sq,
            CG2sq,
            CG3sq,
            CG4sq,
            CG5sq,
            CG6sq,
            CG7sq,
            CG8sq,
            piUser,
        },
        State {
            d,
            D,
            EncIdClient,
            EncBucket,
            EncInvRemain,
            EncInvIssued,
            id_client,
            bucket: lox_cred.bucket,
            level: lox_cred.trust_level + Scalar::one(),
            invremain: lox_cred.invites_remaining + newinvites,
            invissued: lox_cred.invites_issued,
        },
    ))
}