mdoc_witness.h

// Copyright 2025 Google LLC.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#ifndef PRIVACY_PROOFS_ZK_LIB_CIRCUITS_MDOC_MDOC_WITNESS_H_
#define PRIVACY_PROOFS_ZK_LIB_CIRCUITS_MDOC_MDOC_WITNESS_H_
 
#include <stddef.h>
#include <string.h>
 
#include <array>
#include <cstdint>
#include <iterator>
#include <vector>
 
#include "arrays/dense.h"
#include "cbor/host_decoder.h"
#include "circuits/ecdsa/verify_witness.h"
#include "circuits/logic/bit_plucker_encoder.h"
#include "circuits/mac/mac_witness.h"
#include "circuits/mdoc/mdoc_attribute_ids.h"
#include "circuits/mdoc/mdoc_constants.h"
#include "circuits/mdoc/mdoc_hash.h"
#include "circuits/mdoc/mdoc_zk.h"
#include "circuits/sha/flatsha256_witness.h"
#include "gf2k/gf2_128.h"
#include "util/crypto.h"
#include "util/log.h"
#include "util/panic.h"
 
namespace proofs {
 
struct CborIndex {
  size_t k, v, ndx;
  size_t pos, len; /* optional fields for string/byte values */
};
 
struct AttrShift {
  size_t offset, len;
};
 
// This class represents an attribute that is parsed out of the deviceResponse
// data structure. It includes offsets into the original mdoc which can be used
// to construct SHA witnesses for disclosing the value of an attribute.
struct FullAttribute {
  // Offset and length of the attribute identifier and attribute value.
  size_t id_ind;
  size_t id_len;
  size_t val_ind;
  size_t val_len;
 
  const uint8_t* mdl_ns;  // mdl namespace for the attribute
 
  // Index for this attribute among all attributes in the mdoc hash list.
  size_t digest_id;
  CborIndex mso;
 
  // Offset and length of the attribute tag.
  size_t tag_ind;
  size_t tag_len;
 
  // The original mdoc into which all offsets point.
  const uint8_t* doc;
 
  bool operator==(const RequestedAttribute& y) const {
    return y.id_len == id_len && memcmp(y.id, &doc[id_ind], id_len) == 0;
  }
 
  size_t witness_length(const RequestedAttribute& attr) {
    return id_len + val_len + 1 + 12;
  }
};
 
class ParsedMdoc {
 public:
  // Various cbor indices/witnesses for intermediate structures.
  CborIndex t_mso_, sig_, dksig_;
  CborIndex valid_, valid_from_, valid_until_;
  CborIndex dev_key_info_, dev_key_, dev_key_pkx_, dev_key_pky_;
  CborIndex value_digests_, org_;
  std::vector<FullAttribute> attributes_;
  std::vector<uint8_t> doc_type_;
 
  // These are the exact bytes which produce the hash that is signed.
  std::vector<uint8_t> tagged_mso_bytes_;
 
  /*
    Parses a byte representation of the "DeviceResponse" string from a phone.
    This contains all of the information needed to respond to an mdoc verifier.
    This method attempts to construct a witness from this.
 
    8.3.2.1.2.2: first field is "version", 2nd optional field is "documents"
    [documents][0][issuerSigned][issuerAuth]{2} --> tagged mso
    [documents][0][issuerSigned][issuerAuth]{3} --> issuer sig
    [documents][0][issuerSigned][nameSpaces][ns][index-of-attr] --> enc attr
    [documents][0][deviceSigned][deviceAuth][deviceSignature][3] --> sig
 
    This method produces indices into doc as state.
  */
  bool parse_device_response(size_t len, const uint8_t resp[/* len */]) {
    size_t np = 0;
    // When this object falls out of scope, all parsing objects will be
    // garbage collected.
    CborDoc root;
    bool ok = root.decode(resp, len, np, 0);
    if (!ok) {
      log(ERROR, "Failed to decode root");
      return false;
    }
 
    size_t di;
    auto docs = root.lookup(resp, 9, (uint8_t*)"documents", di);
    if (docs == nullptr) return false;
    // Fields of Document are "docType", "issuerSigned", "deviceSigned", ?errors
 
    auto docs0 = docs[1].index(0);
    if (docs0 == nullptr) return false;
 
    auto dt = docs0[0].lookup(resp, 7, (uint8_t*)"docType", di);
    if (dt == nullptr) return false;
    doc_type_.insert(doc_type_.begin(), resp + dt[1].u_.string.pos,
                     resp + dt[1].u_.string.pos + dt[1].u_.string.len);
 
    // The returned docs0 is the map, so index at [0].
    auto is = docs0[0].lookup(resp, 12, (uint8_t*)"issuerSigned", di);
    if (is == nullptr) return false;
 
    auto ia = is[1].lookup(resp, 10, (uint8_t*)"issuerAuth", di);
    if (ia == nullptr) return false;
 
    auto tmso = ia[1].index(2);
    if (tmso == nullptr) return false;
    copy_header(t_mso_, tmso);
    auto nsig = ia[1].index(3);
    if (nsig == nullptr) return false;
    copy_header(sig_, nsig);
 
    auto ns = is[1].lookup(resp, 10, (uint8_t*)"nameSpaces", di);
    if (ns == nullptr) return false;
 
    // Find the attribute witness we need from here.
    for (const char* sn : kSupportedNamespaces) {
      auto mldns = ns[1].lookup(resp, strlen(sn), (const uint8_t*)sn, di);
      if (mldns == nullptr) continue;
      size_t ai = 0;
      auto tattr = mldns[1].index(ai++);
      while (tattr != nullptr) {
        CborDoc er;
        // Decode the map in this tagged attribute.
        size_t pos = tattr->children_[0].u_.string.pos;
        size_t end = pos + tattr->children_[0].u_.string.len;
        if (!er.decode(resp, end, pos, 0)) {
          return false;
        }
 
        auto ei = er.lookup(resp, 17, (uint8_t*)"elementIdentifier", di);
        if (ei == nullptr) return false;
        auto ev = er.lookup(resp, 12, (uint8_t*)"elementValue", di);
        if (ev == nullptr) return false;
        auto digid = er.lookup(resp, 8, (uint8_t*)"digestID", di);
        if (digid == nullptr) return false;
 
        attributes_.push_back((FullAttribute){
            ei[1].position(),
            ei[1].length(),
            ev[1].position(),
            ev[1].length(),
            (const uint8_t*)sn,
            static_cast<size_t>(digid[1].u_.u64), /* digest_id */
            {0, 0, 0},                            /* default mso_ind */
            tattr->header_pos_,                   /* tag_ind */
            tattr->children_[0].u_.string.len +
                4, /* +4 for the D8 18 58 <> prefix */
            resp});
 
        tattr = mldns[1].index(ai++);
      }
    }
 
    auto ds = docs0[0].lookup(resp, 12, (uint8_t*)"deviceSigned", di);
    if (ds == nullptr) return false;
    auto da = ds[1].lookup(resp, 10, (uint8_t*)"deviceAuth", di);
    if (da == nullptr) return false;
    auto dsi = da[1].lookup(resp, 15, (uint8_t*)"deviceSignature", di);
    if (dsi == nullptr) return false;
    auto ndksig = dsi[1].index(3);
    if (ndksig == nullptr) return false;
    copy_header(dksig_, ndksig);
 
    // Then parse tagged mso. Skip 5 bytes to skip the D8 18 59 <len2>.
    const uint8_t* pmso = resp + tmso->u_.string.pos + 5;
    size_t pos = 0;
    CborDoc mso;
    if (!mso.decode(pmso, tmso->u_.string.len - 5, pos, 0)) return false;
    auto nv = mso.lookup(pmso, kValidityInfoLen, kValidityInfoID, valid_.ndx);
    if (nv == nullptr) return false;
    copy_kv_header(valid_, nv);
 
    auto nvf = nv[1].lookup(pmso, kValidFromLen, kValidFromID, valid_from_.ndx);
    if (nvf == nullptr) return false;
    copy_kv_header(valid_from_, nvf);
 
    auto nvu =
        nv[1].lookup(pmso, kValidUntilLen, kValidUntilID, valid_until_.ndx);
    if (nvu == nullptr) return false;
    copy_kv_header(valid_until_, nvu);
 
    auto ndki = mso.lookup(pmso, kDeviceKeyInfoLen, kDeviceKeyInfoID,
                           dev_key_info_.ndx);
    if (ndki == nullptr) return false;
    copy_kv_header(dev_key_info_, ndki);
 
    auto ndk = ndki[1].lookup(pmso, kDeviceKeyLen, kDeviceKeyID, dev_key_.ndx);
    if (ndk == nullptr) return false;
    copy_kv_header(dev_key_, ndk);
 
    auto npkx = ndk[1].lookup_negative(-1, dev_key_pkx_.ndx);
    if (npkx == nullptr) return false;
    copy_kv_header(dev_key_pkx_, npkx);
 
    auto npky = ndk[1].lookup_negative(-2, dev_key_pky_.ndx);
    if (npky == nullptr) return false;
    copy_kv_header(dev_key_pky_, npky);
 
    auto nvd =
        mso.lookup(pmso, kValueDigestsLen, kValueDigestsID, value_digests_.ndx);
    if (nvd == nullptr) return false;
    copy_kv_header(value_digests_, nvd);
 
    // For backwards compatibility with 1f circuits, copy the hard-coded org_ if
    // it is present. TODO(shelat): Remove this once all 1f circuits have
    // been updated.
    auto norg = nvd[1].lookup(pmso, kOrgLen, kOrgID, org_.ndx);
    if (norg != nullptr) {
      copy_kv_header(org_, norg);
    }
 
    for (auto& attr : attributes_) {
      size_t index;
      auto nss = nvd[1].lookup(pmso, strlen((const char*)attr.mdl_ns),
                               attr.mdl_ns, index);
      if (nss == nullptr) return false;
      uint64_t hi = (uint64_t)attr.digest_id;
      auto hattr = nss[1].lookup_unsigned(hi, attr.mso.ndx);
      if (hattr == nullptr) return false;
      copy_kv_header(attr.mso, hattr);
    }
 
    tagged_mso_bytes_.assign(std::begin(kCose1Prefix), std::end(kCose1Prefix));
    // Add 2-byte length
    tagged_mso_bytes_.push_back((t_mso_.len >> 8) & 0xff);
    tagged_mso_bytes_.push_back(t_mso_.len & 0xff);
    for (size_t i = 0; i < t_mso_.len; ++i) {
      tagged_mso_bytes_.push_back(resp[t_mso_.pos + i]);
    }
 
    return true;
  }
 
 private:
  // Used to copy the results of a map lookup.
  static void copy_kv_header(CborIndex& ind, const CborDoc* n) {
    ind.k = n[0].header_pos_;
    ind.v = n[1].header_pos_;
 
    if (n[1].t_ == TEXT || n[1].t_ == BYTES) {
      ind.pos = n[1].u_.string.pos;
      ind.len = n[1].u_.string.len;
    }
  }
 
  // Used to copy the results of an index lookup.
  static void copy_header(CborIndex& ind, const CborDoc* n) {
    ind.k = n->header_pos_;
    ind.pos = n->u_.string.pos;
    ind.len = n->u_.string.len;
  }
};
 
// Transform from u8 be (i.e., be[31] is the most significant byte) into
// nat form, which requires first converting to le byte order.
template <class Nat>
Nat nat_from_be(const uint8_t be[/* Nat::kBytes */]) {
  uint8_t tmp[Nat::kBytes];
  // Transform into byte-wise le representation.
  for (size_t i = 0; i < Nat::kBytes; ++i) {
    tmp[i] = be[Nat::kBytes - i - 1];
  }
  return Nat::of_bytes(tmp);
}
 
// Transform from u32 be (i.e., be[0] is the most significant nibble)
// into nat form, which requires first converting to le byte order.
template <class Nat>
Nat nat_from_u32(const uint32_t be[]) {
  uint8_t tmp[Nat::kBytes];
  const size_t top = Nat::kBytes / 4;
  for (size_t i = 0; i < Nat::kBytes; ++i) {
    tmp[i] = (be[top - i / 4 - 1] >> ((i % 4) * 8)) & 0xff;
  }
  return Nat::of_bytes(tmp);
}
 
template <typename Nat>
Nat nat_from_hash(const uint8_t data[], size_t len) {
  uint8_t hash[kSHA256DigestSize];
  SHA256 sha;
  sha.Update(data, len);
  sha.DigestData(hash);
  Nat ne = nat_from_be<Nat>(hash);
  return ne;
}
 
// Append the cbor encoding of the length of a bytestring to buf.
// This method handles bytestrings that are up to 255 bytes long.
static inline void append_bytes_len(std::vector<uint8_t>& buf, size_t len) {
  check(len < 65536, "Bytestring length too large");
  if (len < 24) {
    buf.push_back(0x40 + len);
  } else if (len < 256) {
    uint8_t ll[] = {0x58, static_cast<uint8_t>(len & 0xff)};
    buf.insert(buf.end(), ll, ll + 2);
  } else {
    uint8_t ll[] = {0x59, (uint8_t)((len >> 8) & 0xff), (uint8_t)(len & 0xff)};
    buf.insert(buf.end(), ll, ll + 3);
  }
}
 
// Append the cbor encoding of the length of a text string to buf.
// This method handles text strings that are up to 255 bytes long.
static inline void append_text_len(std::vector<uint8_t>& buf, size_t len) {
  check(len < 256, "Text length too large");
  if (len < 24) {
    buf.push_back(0x60 + len);
  } else if (len < 256) {
    buf.push_back(0x78);
    buf.push_back(len);
  }
}
 
// Form the COSE1 encoding of the DeviceAuthenticationBytes,
// then compute its SHA-256 hash, and cast into a Nat.
// The original form follows S9.1.3.4 of the mdoc spec and
// assumed that the transcript was a simple string.
// The Jan'2024 demo requires using the "AndroidHandover" version
// of the DeviceAuthenticationBytes formatting, which is not
// specified in the spec. As a result, this function is a hack
// that mimics the bytes produced by the Android com.android.identity.wallet
// library.
template <class Nat>
static Nat compute_transcript_hash(
    const uint8_t transcript[], size_t len,
    const std::vector<uint8_t>* docType = nullptr) {
  // The DeviceAuthenticationBytes is defined in 9.1.3.4 as:
  // DeviceAuthentication = [
  //    "DeviceAuthentication",
  //    SessionTranscript,
  //    DocType, ; Same as in mdoc response
  //    DeviceNameSpacesBytes ; Same as in mdoc response
  // ]
  std::vector<uint8_t> deviceAuthentication = {
      0x84, 0x74, 'D', 'e', 'v', 'i', 'c', 'e', 'A', 'u', 't',
      'h',  'e',  'n', 't', 'i', 'c', 'a', 't', 'i', 'o', 'n',
  };
  std::vector<uint8_t> docTypeBytes = {
      0x75, 'o', 'r', 'g', '.', 'i', 's', 'o', '.', '1', '8',
      '0',  '1', '3', '.', '5', '.', '1', '.', 'm', 'D', 'L',
  };
  std::vector<uint8_t> deviceNameSpacesBytes = {0xD8, 0x18, 0x41, 0xA0};
 
  if (docType != nullptr && docType->size() < 256) {
    docTypeBytes.clear();
    append_text_len(docTypeBytes, docType->size());
    docTypeBytes.insert(docTypeBytes.end(), docType->begin(), docType->end());
  }
 
  // Provide the DeviceAuthentication bytes
  std::vector<uint8_t> da(deviceAuthentication);
  da.insert(da.end(), transcript, transcript + len);
  da.insert(da.end(), docTypeBytes.begin(), docTypeBytes.end());
  da.insert(da.end(), deviceNameSpacesBytes.begin(),
            deviceNameSpacesBytes.end());
 
  // Form the COSE1 encoding of the DeviceAuthenticationBytes.
  std::vector<uint8_t> cose1{0x84, 0x6A, 0x53, 0x69, 0x67, 0x6E,
                             0x61, 0x74, 0x75, 0x72, 0x65, 0x31,
                             0x43, 0xA1, 0x01, 0x26, 0x40};
  uint8_t tag[] = {0xD8, 0x18};
 
  size_t l1 = da.size();
  size_t l2 = l1 + (l1 < 256 ? 4 : 5); /* Tagged array length. */
  append_bytes_len(cose1, l2);
  cose1.insert(cose1.end(), tag, tag + 2);
  append_bytes_len(cose1, l1);
  cose1.insert(cose1.end(), da.begin(), da.end());
 
  return nat_from_hash<Nat>(cose1.data(), cose1.size());
}
 
// Interpret input s as an len*8-bit string, and use it to fill max*8 bits
// in the dense filler.
// Pad the input with the Field value 2 to indicate the positions
// that are not part of the string.
template <class Field>
void fill_bit_string(DenseFiller<Field>& filler, const uint8_t s[/*len*/],
                     size_t len, size_t max, const Field& Fs) {
  std::vector<typename Field::Elt> v(max * 8, Fs.of_scalar(2));
  for (size_t i = 0; i < max && i < len; ++i) {
    fill_byte(v, s[i], i, Fs);
  }
  filler.push_back(v);
}
 
template <class Field>
void fill_byte(std::vector<typename Field::Elt>& v, uint8_t b, size_t i,
               const Field& F) {
  for (size_t j = 0; j < 8; ++j) {
    v[i * 8 + j] = (b >> j & 0x1) ? F.one() : F.zero();
  }
}
 
template <class Field>
bool fill_attribute(DenseFiller<Field>& filler, const RequestedAttribute& attr,
                    const Field& F, size_t version) {
  // In version 3, the attribute is encoded as the raw cbor string that
  // included <name of identifier> <elementValue> <attributeValue>.
  // In version 4, the attribute is encoded as
  // <len(identifier)> <name of identifier> <elementValue> <attributeValue>.
  // This extra length field distinguishes the two attributes:
  //   "aamva/domestic_driving_privileges" from "iso/driving_privileges." No
  // other valid attribute name is a proper suffix of another.  See the
  // mdoc_attribute_ids.h file for the full list of attribute names and our
  // restrictions.
 
  std::vector<uint8_t> vbuf;
  std::vector<typename Field::Elt> v(96 * 8, F.zero());
 
  if (version >= 4) {
    // Append the length of the elementIdentifier.
    append_text_len(vbuf, attr.id_len);
  }
  vbuf.insert(vbuf.end(), attr.id, attr.id + attr.id_len);
  append_text_len(vbuf, 12);  // len of "elementValue"
  const char* ev = "elementValue";
  vbuf.insert(vbuf.end(), ev, ev + 12);
 
  vbuf.insert(vbuf.end(), attr.cbor_value,
              attr.cbor_value + attr.cbor_value_len);
 
  if (vbuf.size() > 96) {
    log(ERROR, "Attribute %s is too long: %zu", attr.id, vbuf.size());
    return false;
  }
  size_t len = 0;
  for (size_t j = 0; j < vbuf.size() && len < 96; ++j, ++len) {
    fill_byte(v, vbuf[j], len, F);
  }
  filler.push_back(v);
  if (version >= 4) {
    // In version 4, add the OpenedAttribute.len field.
    filler.push_back(len, 8, F);
  }
  return true;
}
 
template <class EC, class ScalarField>
class MdocSignatureWitness {
  using Field = typename EC::Field;
  using Elt = typename Field::Elt;
  using Nat = typename Field::N;
  using EcdsaWitness = VerifyWitness3<EC, ScalarField>;
  using MacWitnessF = MacWitness<Field>;
  using f_128 = GF2_128<>;
  const EC& ec_;
  const f_128& gf_;
 
 public:
  Elt e_, e2_;      /* Issuer signature values. */
  Elt dpkx_, dpky_; /* device key */
  EcdsaWitness ew_, dkw_;
  MacWitnessF macs_[3]; /* macs for e_, dpkx_, dpky_ */
 
  explicit MdocSignatureWitness(const EC& ec, const ScalarField& Fn,
                                const f_128& gf)
      : ec_(ec),
        gf_(gf),
        ew_(Fn, ec),
        dkw_(Fn, ec),
        macs_{MacWitnessF(ec.f_, gf_), MacWitnessF(ec.f_, gf_),
              MacWitnessF(ec.f_, gf_)} {}
 
  void fill_witness(DenseFiller<Field>& filler) const {
    filler.push_back(e_);
    filler.push_back(dpkx_);
    filler.push_back(dpky_);
 
    ew_.fill_witness(filler);
    dkw_.fill_witness(filler);
    for (auto& mac : macs_) {
      mac.fill_witness(filler);
    }
  }
 
  bool compute_witness(Elt pkX, Elt pkY, const uint8_t mdoc[/* len */],
                       size_t len, const uint8_t transcript[/* tlen */],
                       size_t tlen) {
    ParsedMdoc pm;
 
    if (!pm.parse_device_response(len, mdoc)) {
      return false;
    }
 
    Nat ne = nat_from_hash<Nat>(pm.tagged_mso_bytes_.data(),
                                pm.tagged_mso_bytes_.size());
    e_ = ec_.f_.to_montgomery(ne);
 
    // Parse (r,s).
    const size_t l = pm.sig_.len;
    Nat nr = nat_from_be<Nat>(&mdoc[pm.sig_.pos]);
    Nat ns = nat_from_be<Nat>(&mdoc[pm.sig_.pos + l / 2]);
    ew_.compute_witness(pkX, pkY, ne, nr, ns);
 
    Nat ne2 = compute_transcript_hash<Nat>(transcript, tlen, &pm.doc_type_);
    const size_t l2 = pm.dksig_.len;
    Nat nr2 = nat_from_be<Nat>(&mdoc[pm.dksig_.pos]);
    Nat ns2 = nat_from_be<Nat>(&mdoc[pm.dksig_.pos + l2 / 2]);
    size_t pmso = pm.t_mso_.pos + 5; /* skip the tag */
    dpkx_ = ec_.f_.to_montgomery(
        nat_from_be<Nat>(&mdoc[pmso + pm.dev_key_pkx_.pos]));
    dpky_ = ec_.f_.to_montgomery(
        nat_from_be<Nat>(&mdoc[pmso + pm.dev_key_pky_.pos]));
    e2_ = ec_.f_.to_montgomery(ne2);
    dkw_.compute_witness(dpkx_, dpky_, ne2, nr2, ns2);
    return true;
  }
};
 
// EC: implements the elliptic curve for the mdoc
// Field: implements the field used to define the sumcheck circuit, which can
//        be smaller than the EC field
template <typename EC, typename Field>
class MdocHashWitness {
  using ECField = typename EC::Field;
  using ECElt = typename ECField::Elt;
  using ECNat = typename ECField::N;
  using Elt = typename Field::Elt;
  using vindex = std::array<Elt, kCborIndexBits>;
 
  const EC& ec_;
  const Field& fn_;
 
 public:
  ECElt e_;           /* Issuer signature values. */
  ECElt dpkx_, dpky_; /* device key */
  uint8_t signed_bytes_[kMaxSHABlocks * 64];
  uint8_t numb_; /* Number of the correct sha block. */
 
  size_t num_attr_;
  std::vector<std::vector<uint8_t>> attr_bytes_;
  std::vector<std::vector<FlatSHA256Witness::BlockWitness>> atw_;
 
  std::vector<uint8_t> attr_n_; /* All attributes currently require 2 SHA. */
  std::vector<CborIndex> attr_mso_; /* The cbor indices of the attributes. */
  std::vector<AttrShift> attr_ei_;
  std::vector<AttrShift> attr_ev_;
 
  FlatSHA256Witness::BlockWitness bw_[kMaxSHABlocks];
 
  ParsedMdoc pm_;
 
  uint8_t now_[20]; /* CBOR-formatted time used for expiry comparison. */
 
  explicit MdocHashWitness(size_t num_attr, const EC& ec, const Field& Fn)
      : ec_(ec), fn_(Fn), num_attr_(num_attr) {}
 
  void fill_cbor_index(DenseFiller<Field>& df, const CborIndex& ind) const {
    df.push_back(ind.k, kCborIndexBits, fn_);
  }
 
  void fill_attr_shift(DenseFiller<Field>& df, const AttrShift& attr) const {
    df.push_back(attr.offset, kCborIndexBits, fn_);
    df.push_back(attr.len, kCborIndexBits, fn_);
  }
 
  void fill_sha(DenseFiller<Field>& filler,
                const FlatSHA256Witness::BlockWitness& bw) const {
    BitPluckerEncoder<Field, kSHAPluckerBits> BPENC(fn_);
    for (size_t k = 0; k < 48; ++k) {
      filler.push_back(BPENC.mkpacked_v32(bw.outw[k]));
    }
    for (size_t k = 0; k < 64; ++k) {
      filler.push_back(BPENC.mkpacked_v32(bw.oute[k]));
      filler.push_back(BPENC.mkpacked_v32(bw.outa[k]));
    }
    for (size_t k = 0; k < 8; ++k) {
      filler.push_back(BPENC.mkpacked_v32(bw.h1[k]));
    }
  }
 
  void fill_witness(DenseFiller<Field>& filler) const {
    // Fill sha of main mso.
    filler.push_back(numb_, 8, fn_);
    // Don't push the prefix.
    for (size_t i = kCose1PrefixLen; i < kMaxSHABlocks * 64; ++i) {
      filler.push_back(signed_bytes_[i], 8, fn_);
    }
    for (size_t j = 0; j < kMaxSHABlocks; j++) {
      fill_sha(filler, bw_[j]);
    }
    // === done with sha
 
    fill_cbor_index(filler, pm_.valid_from_);
    fill_cbor_index(filler, pm_.valid_until_);
    fill_cbor_index(filler, pm_.dev_key_info_);
    fill_cbor_index(filler, pm_.value_digests_);
 
    // Fill all attribute witnesses.
    for (size_t ai = 0; ai < num_attr_; ++ai) {
      for (size_t i = 0; i < 2 * 64; ++i) {
        filler.push_back(attr_bytes_[ai][i], 8, fn_);
      }
      for (size_t j = 0; j < 2; j++) {
        fill_sha(filler, atw_[ai][j]);
      }
 
      // In the case of attribute mso, push the value to avoid having to
      // deal with 1- or 2- byte key length.
      filler.push_back(attr_mso_[ai].v, kCborIndexBits, fn_);
      fill_attr_shift(filler, attr_ei_[ai]);
      fill_attr_shift(filler, attr_ev_[ai]);
    }
  }
 
  bool compute_witness(const uint8_t mdoc[/* len */], size_t len,
                       const uint8_t transcript[/* tlen */], size_t tlen,
                       const RequestedAttribute attrs[], size_t attrs_len,
                       const uint8_t tnow[/*20*/], size_t version) {
    if (!pm_.parse_device_response(len, mdoc)) {
      log(ERROR, "Failed to parse device response");
      return false;
    }
 
    std::vector<uint8_t> buf;
    if (pm_.t_mso_.len >= kMaxSHABlocks * 64 - 9 - kCose1PrefixLen) {
      log(ERROR, "tagged mso is too big: %zu", pm_.t_mso_.len);
      return false;
    }
 
    buf.assign(std::begin(kCose1Prefix), std::end(kCose1Prefix));
    // Add 2-byte length
    buf.push_back((pm_.t_mso_.len >> 8) & 0xff);
    buf.push_back(pm_.t_mso_.len & 0xff);
    for (size_t i = 0; i < pm_.t_mso_.len; ++i) {
      buf.push_back(mdoc[pm_.t_mso_.pos + i]);
    }
 
    FlatSHA256Witness::transform_and_witness_message(
        buf.size(), buf.data(), kMaxSHABlocks, numb_, signed_bytes_, bw_);
 
    ECNat ne = nat_from_u32<ECNat>(bw_[numb_ - 1].h1);
    e_ = ec_.f_.to_montgomery(ne);
 
    memcpy(now_, tnow, 20);
 
    size_t pmso = pm_.t_mso_.pos + 5; /* +5 to skip the tag */
    dpkx_ = ec_.f_.to_montgomery(
        nat_from_be<ECNat>(&mdoc[pmso + pm_.dev_key_pkx_.pos]));
    dpky_ = ec_.f_.to_montgomery(
        nat_from_be<ECNat>(&mdoc[pmso + pm_.dev_key_pky_.pos]));
 
    // initialize variables
    attr_n_.resize(attrs_len);
    attr_mso_.resize(attrs_len);
    attr_ev_.resize(attrs_len);
    attr_ei_.resize(attrs_len);
    attr_bytes_.resize(attrs_len);
    atw_.resize(attrs_len);
 
    // Match the attributes with the witnesses from the deviceResponse.
    for (size_t i = 0; i < attrs_len; ++i) {
      attr_bytes_[i].resize(128);
      atw_[i].resize(2);
      bool found = false;
      for (auto fa : pm_.attributes_) {
        if (fa == attrs[i]) {
          FlatSHA256Witness::transform_and_witness_message(
              fa.tag_len, &fa.doc[fa.tag_ind], 2, attr_n_[i],
              &attr_bytes_[i][0], &atw_[i][0]);
          attr_mso_[i] = fa.mso;
          attr_ei_[i].offset = fa.id_ind - fa.tag_ind;
          if (version >= 4) {
            // In version 4, the attribute id is encoded as the length of the
            // id followed by the id.  The witness starts at the id, so we
            // subtract 1 or 2 to get the offset, depending on the id length.
            attr_ei_[i].offset -= 1;
            if (fa.id_len > 23) {
              attr_ei_[i].offset -= 1;
            }
          }
          attr_ei_[i].len = fa.witness_length(attrs[i]);
          attr_ev_[i].offset = fa.val_ind - fa.tag_ind;
          attr_ev_[i].len = fa.val_len;
          found = true;
          break;
        }
      }
      if (!found) {
        log(ERROR, "Could not find attribute %.*s", attrs[i].id_len,
            attrs[i].id);
        return false;
      }
    }
    return true;
  }
};
}  // namespace proofs
 
#endif  // PRIVACY_PROOFS_ZK_LIB_CIRCUITS_MDOC_MDOC_WITNESS_H_