Use batched DLEQ proofs for Trust Token.

Before:
Did 867 TrustToken-Exp1-Batch1 generate_key operations in 1029740us (842.0 ops/sec)
Did 1441 TrustToken-Exp1-Batch1 begin_issuance operations in 1021088us (1411.2 ops/sec)
Did 200 TrustToken-Exp1-Batch1 issue operations in 1003145us (199.4 ops/sec)
Did 154 TrustToken-Exp1-Batch1 finish_issuance operations in 1053858us (146.1 ops/sec)
Did 5128000 TrustToken-Exp1-Batch1 begin_redemption operations in 1000076us (5127610.3 ops/sec)
Did 517 TrustToken-Exp1-Batch1 redeem operations in 1031054us (501.4 ops/sec)
Did 15000 TrustToken-Exp1-Batch1 finish_redemption operations in 1041906us (14396.7 ops/sec)
Did 870 TrustToken-Exp1-Batch10 generate_key operations in 1020929us (852.2 ops/sec)
Did 154 TrustToken-Exp1-Batch10 begin_issuance operations in 1085963us (141.8 ops/sec)
Did 20 TrustToken-Exp1-Batch10 issue operations in 1040995us (19.2 ops/sec)
Did 14 TrustToken-Exp1-Batch10 finish_issuance operations in 1009041us (13.9 ops/sec)
Did 5138000 TrustToken-Exp1-Batch10 begin_redemption operations in 1000114us (5137414.3 ops/sec)
Did 528 TrustToken-Exp1-Batch10 redeem operations in 1026978us (514.1 ops/sec)
Did 15000 TrustToken-Exp1-Batch10 finish_redemption operations in 1016920us (14750.4 ops/sec)

After:
Did 900 TrustToken-Exp1-Batch1 generate_key operations in 1032678us (871.5 ops/sec) [+3.5%]
Did 1410 TrustToken-Exp1-Batch1 begin_issuance operations in 1004439us (1403.8 ops/sec) [-0.5%]
Did 154 TrustToken-Exp1-Batch1 issue operations in 1068370us (144.1 ops/sec) [-27.7%]
Did 121 TrustToken-Exp1-Batch1 finish_issuance operations in 1048767us (115.4 ops/sec) [-21.0%]
Did 5179000 TrustToken-Exp1-Batch1 begin_redemption operations in 1000159us (5178176.7 ops/sec) [+1.0%]
Did 572 TrustToken-Exp1-Batch1 redeem operations in 1093354us (523.2 ops/sec) [+4.3%]
Did 15000 TrustToken-Exp1-Batch1 finish_redemption operations in 1001506us (14977.4 ops/sec) [+4.0%]
Did 913 TrustToken-Exp1-Batch10 generate_key operations in 1027546us (888.5 ops/sec) [+4.3%]
Did 154 TrustToken-Exp1-Batch10 begin_issuance operations in 1051530us (146.5 ops/sec) [+3.3%]
Did 26 TrustToken-Exp1-Batch10 issue operations in 1027599us (25.3 ops/sec) [+31.7%]
Did 24 TrustToken-Exp1-Batch10 finish_issuance operations in 1055615us (22.7 ops/sec) [+63.9%]
Did 5100000 TrustToken-Exp1-Batch10 begin_redemption operations in 1000201us (5098975.1 ops/sec) [-0.7%]
Did 561 TrustToken-Exp1-Batch10 redeem operations in 1072683us (523.0 ops/sec) [+1.7%]
Did 15000 TrustToken-Exp1-Batch10 finish_redemption operations in 1006697us (14900.2 ops/sec) [+1.0%]

Change-Id: Ibdc08f9d63e62dda14a2cd9e9d8be27c8723675b
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/40865
Commit-Queue: Steven Valdez <svaldez@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/trust_token/internal.h b/crypto/trust_token/internal.h
index db9d0cf..d65057f 100644
--- a/crypto/trust_token/internal.h
+++ b/crypto/trust_token/internal.h
@@ -197,6 +197,10 @@
   // use_token_hash determines whether to include the token hash in the SRR and
   // private metadata encryption.
   int use_token_hash : 1;
+
+  // batched_proof determines whether PMBToken uses a batched DLEQOR proof when
+  // signing tokens.
+  int batched_proof : 1;
 };
 
 // Structure representing a single Trust Token public key with the specified ID.
diff --git a/crypto/trust_token/pmbtoken.c b/crypto/trust_token/pmbtoken.c
index 7eca5bb..258cd40 100644
--- a/crypto/trust_token/pmbtoken.c
+++ b/crypto/trust_token/pmbtoken.c
@@ -52,6 +52,9 @@
   // hash_c implements the H_c operation in PMBTokens. It returns one on success
   // and zero on error.
   hash_c_func_t hash_c;
+  // batched_proof determines whether PMBToken uses a batched DLEQOR proof when
+  // signing tokens.
+  int batched_proof : 1;
 } PMBTOKEN_METHOD;
 
 static const uint8_t kDefaultAdditionalData[32] = {0};
@@ -59,7 +62,7 @@
 static int pmbtoken_init_method(PMBTOKEN_METHOD *method, int curve_nid,
                                 const uint8_t *h_bytes, size_t h_len,
                                 hash_t_func_t hash_t, hash_s_func_t hash_s,
-                                hash_c_func_t hash_c) {
+                                hash_c_func_t hash_c, int batched_proof) {
   method->group = EC_GROUP_new_by_curve_name(curve_nid);
   if (method->group == NULL) {
     return 0;
@@ -68,6 +71,7 @@
   method->hash_t = hash_t;
   method->hash_s = hash_s;
   method->hash_c = hash_c;
+  method->batched_proof = batched_proof;
 
   EC_AFFINE h;
   if (!ec_point_from_uncompressed(method->group, &h, h_bytes, h_len)) {
@@ -384,6 +388,38 @@
   return ok;
 }
 
+static int hash_c_batch(const PMBTOKEN_METHOD *method, EC_SCALAR *out,
+                        const CBB *points, size_t index) {
+  static const uint8_t kDLEQBatchLabel[] = "DLEQ BATCH";
+  if (index > 0xffff) {
+    // The protocol supports only two-byte batches.
+    OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
+    return 0;
+  }
+
+  int ok = 0;
+  CBB cbb;
+  CBB_zero(&cbb);
+  uint8_t *buf = NULL;
+  size_t len;
+  if (!CBB_init(&cbb, 0) ||
+      !CBB_add_bytes(&cbb, kDLEQBatchLabel, sizeof(kDLEQBatchLabel)) ||
+      !CBB_add_bytes(&cbb, CBB_data(points), CBB_len(points)) ||
+      !CBB_add_u16(&cbb, (uint16_t)index) ||
+      !CBB_finish(&cbb, &buf, &len) ||
+      !method->hash_c(method->group, out, buf, len)) {
+    OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
+    goto err;
+  }
+
+  ok = 1;
+
+err:
+  CBB_cleanup(&cbb);
+  OPENSSL_free(buf);
+  return ok;
+}
+
 // The DLEQ2 and DLEQOR2 constructions are described in appendix B of
 // https://eprint.iacr.org/2020/072/20200324:214215. DLEQ2 is an instance of
 // DLEQOR2 with only one value (n=1).
@@ -681,12 +717,41 @@
     return 0;
   }
 
+  int ret = 0;
+  EC_RAW_POINT *Tps = NULL;
+  EC_RAW_POINT *Sps = NULL;
+  EC_RAW_POINT *Wps = NULL;
+  EC_RAW_POINT *Wsps = NULL;
+  CBB batch_cbb;
+  CBB_zero(&batch_cbb);
+  if (method->batched_proof) {
+    if (num_to_issue > ((size_t)-1) / sizeof(EC_RAW_POINT)) {
+      OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
+      goto err;
+    }
+    Tps = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
+    Sps = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
+    Wps = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
+    Wsps = OPENSSL_malloc(num_to_issue * sizeof(EC_RAW_POINT));
+    if (!Tps ||
+        !Sps ||
+        !Wps ||
+        !Wsps ||
+        !CBB_init(&batch_cbb, 0) ||
+        !point_to_cbb(&batch_cbb, method->group, &key->pubs) ||
+        !point_to_cbb(&batch_cbb, method->group, &key->pub0) ||
+        !point_to_cbb(&batch_cbb, method->group, &key->pub1)) {
+      OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
+      goto err;
+    }
+  }
+
   for (size_t i = 0; i < num_to_issue; i++) {
     EC_AFFINE Tp_affine;
     EC_RAW_POINT Tp;
     if (!cbs_get_prefixed_point(cbs, group, &Tp_affine)) {
       OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
-      return 0;
+      goto err;
     }
     ec_affine_to_jacobian(group, &Tp, &Tp_affine);
 
@@ -697,35 +762,89 @@
 
     uint8_t s[PMBTOKEN_NONCE_SIZE];
     RAND_bytes(s, PMBTOKEN_NONCE_SIZE);
-    EC_RAW_POINT Sp, W[2];
-    EC_AFFINE W_affine[2];
+    // The |jacobians| and |affines| contain Sp, Wp, and Wsp.
+    EC_RAW_POINT jacobians[3];
+    EC_AFFINE affines[3];
     CBB child;
-    if (!method->hash_s(group, &Sp, &Tp_affine, s) ||
-        !ec_point_mul_scalar_batch(group, &W[0], &Tp, &xb, &Sp, &yb, NULL,
-                                   NULL) ||
-        !ec_point_mul_scalar_batch(group, &W[1], &Tp, &key->xs, &Sp, &key->ys,
-                                   NULL, NULL) ||
-        // This call to |ec_jacobian_to_affine_batch| could be merged with the
-        // one in |dleq_generate|, but we expect to implement the batched DLEQOR
-        // proofs (see figure 15 of the PMBTokens paper), which would require a
-        // different interface.
-        //
-        // We similarly pass inputs to |dleq_generate| in Jacobian form, even
-        // though the affine values have already been computed. In the batched
-        // version, these inputs are the result of a multiplication.
-        !ec_jacobian_to_affine_batch(group, W_affine, W, 2) ||
+    if (!method->hash_s(group, &jacobians[0], &Tp_affine, s) ||
+        !ec_point_mul_scalar_batch(group, &jacobians[1], &Tp, &xb,
+                                   &jacobians[0], &yb, NULL, NULL) ||
+        !ec_point_mul_scalar_batch(group, &jacobians[2], &Tp, &key->xs,
+                                   &jacobians[0], &key->ys, NULL, NULL) ||
+        !ec_jacobian_to_affine_batch(group, affines, jacobians, 3) ||
         !CBB_add_bytes(cbb, s, PMBTOKEN_NONCE_SIZE) ||
         // TODO(https://crbug.com/boringssl/331): When updating the key format,
         // remove the redundant length prefixes.
         !CBB_add_u16_length_prefixed(cbb, &child) ||
-        !point_to_cbb(&child, group, &W_affine[0]) ||
+        !point_to_cbb(&child, group, &affines[1]) ||
         !CBB_add_u16_length_prefixed(cbb, &child) ||
-        !point_to_cbb(&child, group, &W_affine[1]) ||
-        !CBB_add_u16_length_prefixed(cbb, &child) ||
-        !dleq_generate(method, &child, key, &Tp, &Sp, &W[0], &W[1],
-                       private_metadata) ||
+        !point_to_cbb(&child, group, &affines[2])) {
+      goto err;
+    }
+
+    if (!method->batched_proof) {
+      if (!CBB_add_u16_length_prefixed(cbb, &child) ||
+          !dleq_generate(method, &child, key, &Tp, &jacobians[0], &jacobians[1],
+                         &jacobians[2], private_metadata)) {
+        goto err;
+      }
+    } else {
+      if (!point_to_cbb(&batch_cbb, group, &Tp_affine) ||
+          !point_to_cbb(&batch_cbb, group, &affines[0]) ||
+          !point_to_cbb(&batch_cbb, group, &affines[1]) ||
+          !point_to_cbb(&batch_cbb, group, &affines[2])) {
+        OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
+        goto err;
+      }
+      Tps[i] = Tp;
+      Sps[i] = jacobians[0];
+      Wps[i] = jacobians[1];
+      Wsps[i] = jacobians[2];
+    }
+
+    if (!CBB_flush(cbb)) {
+      goto err;
+    }
+  }
+
+  // The DLEQ batching construction is described in appendix B of
+  // https://eprint.iacr.org/2020/072/20200324:214215.
+  if (method->batched_proof) {
+    EC_RAW_POINT Tp_batch, Sp_batch, Wp_batch, Wsp_batch;
+    for (size_t i = 0; i < num_to_issue; i++) {
+      EC_SCALAR e;
+      if (!hash_c_batch(method, &e, &batch_cbb, i)) {
+        goto err;
+      }
+
+      EC_RAW_POINT Tp_e, Sp_e, Wp_e, Wsp_e;
+      if (!ec_point_mul_scalar(group, &Tp_e, &Tps[i], &e) ||
+          !ec_point_mul_scalar(group, &Sp_e, &Sps[i], &e) ||
+          !ec_point_mul_scalar(group, &Wp_e, &Wps[i], &e) ||
+          !ec_point_mul_scalar(group, &Wsp_e, &Wsps[i], &e)) {
+        goto err;
+      }
+
+      // TODO: Switch this to a multi-scalar multiplication.
+      if (i == 0) {
+        Tp_batch = Tp_e;
+        Sp_batch = Sp_e;
+        Wp_batch = Wp_e;
+        Wsp_batch = Wsp_e;
+      } else {
+        group->meth->add(group, &Tp_batch, &Tp_batch, &Tp_e);
+        group->meth->add(group, &Sp_batch, &Sp_batch, &Sp_e);
+        group->meth->add(group, &Wp_batch, &Wp_batch, &Wp_e);
+        group->meth->add(group, &Wsp_batch, &Wsp_batch, &Wsp_e);
+      }
+    }
+
+    CBB proof;
+    if (!CBB_add_u16_length_prefixed(cbb, &proof) ||
+        !dleq_generate(method, &proof, key, &Tp_batch, &Sp_batch, &Wp_batch,
+                       &Wsp_batch, private_metadata) ||
         !CBB_flush(cbb)) {
-      return 0;
+      goto err;
     }
   }
 
@@ -733,10 +852,18 @@
   size_t point_len = 1 + 2 * BN_num_bytes(&group->field);
   if (!CBS_skip(cbs, (2 + point_len) * (num_requested - num_to_issue))) {
     OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
-    return 0;
+    goto err;
   }
 
-  return 1;
+  ret = 1;
+
+err:
+  OPENSSL_free(Tps);
+  OPENSSL_free(Sps);
+  OPENSSL_free(Wps);
+  OPENSSL_free(Wsps);
+  CBB_cleanup(&batch_cbb);
+  return ret;
 }
 
 static STACK_OF(TRUST_TOKEN) *
@@ -750,12 +877,41 @@
     return NULL;
   }
 
+  int ok = 0;
   STACK_OF(TRUST_TOKEN) *ret = sk_TRUST_TOKEN_new_null();
   if (ret == NULL) {
     OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
     return NULL;
   }
 
+  EC_RAW_POINT *Tps = NULL;
+  EC_RAW_POINT *Sps = NULL;
+  EC_RAW_POINT *Wps = NULL;
+  EC_RAW_POINT *Wsps = NULL;
+  CBB batch_cbb;
+  CBB_zero(&batch_cbb);
+  if (method->batched_proof) {
+    if (count > ((size_t)-1) / sizeof(EC_RAW_POINT)) {
+      OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_OVERFLOW);
+      goto err;
+    }
+    Tps = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
+    Sps = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
+    Wps = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
+    Wsps = OPENSSL_malloc(count * sizeof(EC_RAW_POINT));
+    if (!Tps ||
+        !Sps ||
+        !Wps ||
+        !Wsps ||
+        !CBB_init(&batch_cbb, 0) ||
+        !point_to_cbb(&batch_cbb, method->group, &key->pubs) ||
+        !point_to_cbb(&batch_cbb, method->group, &key->pub0) ||
+        !point_to_cbb(&batch_cbb, method->group, &key->pub1)) {
+      OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
+      goto err;
+    }
+  }
+
   for (size_t i = 0; i < count; i++) {
     const PMBTOKEN_PRETOKEN *pretoken =
         sk_PMBTOKEN_PRETOKEN_value(pretokens, i);
@@ -765,27 +921,47 @@
     CBS proof;
     if (!CBS_copy_bytes(cbs, s, PMBTOKEN_NONCE_SIZE) ||
         !cbs_get_prefixed_point(cbs, group, &Wp_affine) ||
-        !cbs_get_prefixed_point(cbs, group, &Wsp_affine) ||
-        !CBS_get_u16_length_prefixed(cbs, &proof)) {
+        !cbs_get_prefixed_point(cbs, group, &Wsp_affine)) {
       OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
       goto err;
     }
 
-    // We pass |Tp| in Jacobian form to |dleq_verify| although the affine form
-    // is already available. This is in anticipation of supporting batched DLEQ
-    // proofs, where the input would be the result of a multiplication.
     EC_RAW_POINT Tp, Wp, Wsp, Sp;
     ec_affine_to_jacobian(group, &Tp, &pretoken->Tp);
     ec_affine_to_jacobian(group, &Wp, &Wp_affine);
     ec_affine_to_jacobian(group, &Wsp, &Wsp_affine);
-    if (!method->hash_s(group, &Sp, &pretoken->Tp, s) ||
-        !dleq_verify(method, &proof, key, &Tp, &Sp, &Wp, &Wsp)) {
+    if (!method->hash_s(group, &Sp, &pretoken->Tp, s)) {
       goto err;
     }
 
-    if (CBS_len(&proof) != 0) {
-      OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
-      goto err;
+    if (!method->batched_proof) {
+      if(!CBS_get_u16_length_prefixed(cbs, &proof)) {
+        OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
+        goto err;
+      }
+
+      if (!dleq_verify(method, &proof, key, &Tp, &Sp, &Wp, &Wsp)) {
+        goto err;
+      }
+
+      if (CBS_len(&proof) != 0) {
+        OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_DECODE_FAILURE);
+        goto err;
+      }
+    } else {
+      EC_AFFINE Sp_affine;
+      if (!point_to_cbb(&batch_cbb, group, &pretoken->Tp) ||
+          !ec_jacobian_to_affine(group, &Sp_affine, &Sp) ||
+          !point_to_cbb(&batch_cbb, group, &Sp_affine) ||
+          !point_to_cbb(&batch_cbb, group, &Wp_affine) ||
+          !point_to_cbb(&batch_cbb, group, &Wsp_affine)) {
+        OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE);
+        goto err;
+      }
+      Tps[i] = Tp;
+      Sps[i] = Sp;
+      Wps[i] = Wp;
+      Wsps[i] = Wsp;
     }
 
     // Unblind the token.
@@ -829,11 +1005,60 @@
     }
   }
 
-  return ret;
+  // The DLEQ batching construction is described in appendix B of
+  // https://eprint.iacr.org/2020/072/20200324:214215.
+  if (method->batched_proof) {
+    EC_RAW_POINT Tp_batch, Sp_batch, Wp_batch, Wsp_batch;
+    for (size_t i = 0; i < count; i++) {
+      EC_SCALAR e;
+      if (!hash_c_batch(method, &e, &batch_cbb, i)) {
+        goto err;
+      }
+
+      EC_RAW_POINT Tp_e, Sp_e, Wp_e, Wsp_e;
+      if (!ec_point_mul_scalar(group, &Tp_e, &Tps[i], &e) ||
+          !ec_point_mul_scalar(group, &Sp_e, &Sps[i], &e) ||
+          !ec_point_mul_scalar(group, &Wp_e, &Wps[i], &e) ||
+          !ec_point_mul_scalar(group, &Wsp_e, &Wsps[i], &e)) {
+        goto err;
+      }
+
+      // TODO: Switch this to a multi-scalar multiplication.
+      if (i == 0) {
+        Tp_batch = Tp_e;
+        Sp_batch = Sp_e;
+        Wp_batch = Wp_e;
+        Wsp_batch = Wsp_e;
+      } else {
+        group->meth->add(group, &Tp_batch, &Tp_batch, &Tp_e);
+        group->meth->add(group, &Sp_batch, &Sp_batch, &Sp_e);
+        group->meth->add(group, &Wp_batch, &Wp_batch, &Wp_e);
+        group->meth->add(group, &Wsp_batch, &Wsp_batch, &Wsp_e);
+      }
+    }
+
+    CBS proof;
+    if (!CBS_get_u16_length_prefixed(cbs, &proof) ||
+        !dleq_verify(method, &proof, key, &Tp_batch, &Sp_batch, &Wp_batch,
+                     &Wsp_batch) ||
+        CBS_len(&proof) != 0) {
+      goto err;
+    }
+  }
+
+  ok = 1;
 
 err:
-  sk_TRUST_TOKEN_pop_free(ret, TRUST_TOKEN_free);
-  return NULL;
+  OPENSSL_free(Tps);
+  OPENSSL_free(Sps);
+  OPENSSL_free(Wps);
+  OPENSSL_free(Wsps);
+  CBB_cleanup(&batch_cbb);
+  if (!ok) {
+    sk_TRUST_TOKEN_pop_free(ret, TRUST_TOKEN_free);
+    ret = NULL;
+  }
+  return ret;
 }
 
 static int pmbtoken_read(const PMBTOKEN_METHOD *method,
@@ -1018,9 +1243,10 @@
       0xcd,
   };
 
-  pmbtoken_exp0_ok = pmbtoken_init_method(
-      &pmbtoken_exp0_method, NID_secp521r1, kH, sizeof(kH),
-      pmbtoken_exp0_hash_t, pmbtoken_exp0_hash_s, pmbtoken_exp0_hash_c);
+  pmbtoken_exp0_ok =
+      pmbtoken_init_method(&pmbtoken_exp0_method, NID_secp521r1, kH, sizeof(kH),
+                           pmbtoken_exp0_hash_t, pmbtoken_exp0_hash_s,
+                           pmbtoken_exp0_hash_c, /*batched_proof=*/0);
 }
 
 static int pmbtoken_exp0_init_method(void) {
@@ -1157,9 +1383,10 @@
       0x87, 0xc3, 0x95, 0xd0, 0x13, 0xb7, 0x0b, 0x5c, 0xc7,
   };
 
-  pmbtoken_exp1_ok = pmbtoken_init_method(
-      &pmbtoken_exp1_method, NID_secp384r1, kH, sizeof(kH),
-      pmbtoken_exp1_hash_t, pmbtoken_exp1_hash_s, pmbtoken_exp1_hash_c);
+  pmbtoken_exp1_ok =
+      pmbtoken_init_method(&pmbtoken_exp1_method, NID_secp384r1, kH, sizeof(kH),
+                           pmbtoken_exp1_hash_t, pmbtoken_exp1_hash_s,
+                           pmbtoken_exp1_hash_c, /*batched_proof=*/1);
 }
 
 static int pmbtoken_exp1_init_method(void) {
diff --git a/crypto/trust_token/trust_token.c b/crypto/trust_token/trust_token.c
index f4c4fa1..448def8 100644
--- a/crypto/trust_token/trust_token.c
+++ b/crypto/trust_token/trust_token.c
@@ -37,6 +37,7 @@
       pmbtoken_exp0_unblind,
       pmbtoken_exp0_read,
       0 /* don't use token hash */,
+      0 /* don't use batched proof */,
   };
   return &kMethod;
 }
@@ -51,6 +52,7 @@
       pmbtoken_exp1_unblind,
       pmbtoken_exp1_read,
       1 /* use token hash */,
+      1 /* use batched proof */,
   };
   return &kMethod;
 }
diff --git a/crypto/trust_token/trust_token_test.cc b/crypto/trust_token/trust_token_test.cc
index a326122..bbb7a8a 100644
--- a/crypto/trust_token/trust_token_test.cc
+++ b/crypto/trust_token/trust_token_test.cc
@@ -607,10 +607,22 @@
     ASSERT_TRUE(CBB_add_u16(bad_response.get(), CBS_len(&tmp)));
     ASSERT_TRUE(
         CBB_add_bytes(bad_response.get(), CBS_data(&tmp), CBS_len(&tmp)));
+    if (!method()->batched_proof) {
+      ASSERT_TRUE(CBS_get_u16_length_prefixed(&real_response, &tmp));
+      CBB dleq;
+      ASSERT_TRUE(CBB_add_u16_length_prefixed(bad_response.get(), &dleq));
+      ASSERT_TRUE(CBB_add_bytes(&dleq, CBS_data(&tmp), CBS_len(&tmp) - 2));
+      ASSERT_TRUE(CBB_flush(bad_response.get()));
+    }
+  }
+
+  if (method()->batched_proof) {
+    CBS tmp;
     ASSERT_TRUE(CBS_get_u16_length_prefixed(&real_response, &tmp));
-    ASSERT_TRUE(CBB_add_u16(bad_response.get(), CBS_len(&tmp) - 2));
-    ASSERT_TRUE(
-        CBB_add_bytes(bad_response.get(), CBS_data(&tmp), CBS_len(&tmp) - 2));
+    CBB dleq;
+    ASSERT_TRUE(CBB_add_u16_length_prefixed(bad_response.get(), &dleq));
+    ASSERT_TRUE(CBB_add_bytes(&dleq, CBS_data(&tmp), CBS_len(&tmp) - 2));
+    ASSERT_TRUE(CBB_flush(bad_response.get()));
   }
 
   uint8_t *bad_buf;
@@ -663,11 +675,24 @@
     ASSERT_TRUE(CBB_add_u16(bad_response.get(), CBS_len(&tmp)));
     ASSERT_TRUE(
         CBB_add_bytes(bad_response.get(), CBS_data(&tmp), CBS_len(&tmp)));
+    if (!method()->batched_proof) {
+      ASSERT_TRUE(CBS_get_u16_length_prefixed(&real_response, &tmp));
+      CBB dleq;
+      ASSERT_TRUE(CBB_add_u16_length_prefixed(bad_response.get(), &dleq));
+      ASSERT_TRUE(CBB_add_bytes(&dleq, CBS_data(&tmp), CBS_len(&tmp)));
+      ASSERT_TRUE(CBB_add_u16(&dleq, 42));
+      ASSERT_TRUE(CBB_flush(bad_response.get()));
+    }
+  }
+
+  if (method()->batched_proof) {
+    CBS tmp;
     ASSERT_TRUE(CBS_get_u16_length_prefixed(&real_response, &tmp));
-    ASSERT_TRUE(CBB_add_u16(bad_response.get(), CBS_len(&tmp) + 2));
-    ASSERT_TRUE(
-        CBB_add_bytes(bad_response.get(), CBS_data(&tmp), CBS_len(&tmp)));
-    ASSERT_TRUE(CBB_add_u16(bad_response.get(), 42));
+    CBB dleq;
+    ASSERT_TRUE(CBB_add_u16_length_prefixed(bad_response.get(), &dleq));
+    ASSERT_TRUE(CBB_add_bytes(&dleq, CBS_data(&tmp), CBS_len(&tmp)));
+    ASSERT_TRUE(CBB_add_u16(&dleq, 42));
+    ASSERT_TRUE(CBB_flush(bad_response.get()));
   }
 
   uint8_t *bad_buf;