Re: Longfellow ZK (google-zk)

Thanks to all for the great information.  It has been extremely helpful at
understanding the model.

In thinking about the practical implications of the approach, I'm wondering
about how many circuits might be needed.  From what I understood, the
circuit defines most of the functionality of a (hopefully broad) set of use
cases:

   - The VC format -- currently mdocs, but flexible (is this at the circuit
   level or in code processing a circuit?)
   - Proof of issuer's signature in an unlinkable way.
   - Holder binding using a proof of the holder's signature across a
   challenge from the verifier in an unlinkable way (no public key needed for
   verification).
   - A maximum size (number of bytes) of the VC (e.g., "2048")
   - The number of attributes to be revealed (e.g., "5")

What I'm not clear on is if:

   - If a circuit is defined as (for example) "mdoc, 2048, 5", can it be
   used by a verifier based on any small enough input mdoc VC to prove any
   arbitrary 5 attributes defined by the verifier/selected by the holder?
   - If a circuit is defined as "mdoc, 2048, 5", can the verifier
   request/the holder disclose *fewer* than 5 attributes, such that the
   presentation is still verifiable?

That latter flexibility would be extremely useful in limiting the number of
circuits that will need to be defined and shared.

A second question is around the other useful/required ZK VC features,
whether they are possible to add, and where they would be implemented -- in
the code to process the circuits, or in the circuits?

   - Pseudonymous identifiers
   - Revocation

It seems to me, these would be like the handling of the signatures -- an
agreed upon (opinionated) mechanisms to accomplish an agreed upon approach.

Thanks

On Mon, Jun 30, 2025 at 7:03 AM <andrea@dyne.org> wrote:

> Thank you Matteo for explanation! We’re indeed busy preparing for our demo
> in Geneva – I’ll make sure Jaromil sees this message, as based on our
> previous discussions, I believe you’re answering to some of the questions
> about the circuits that he has been investigating too.
>
>
>
> To Manu (and everyone else interested): we have integrated Longfellow-zk
> in Zenroom (PoC, still needs a bit of ironing) and we’ll demo an Android
> app (Java) producing a proof and a microservice verifying it at GDC
> (Geneva). Both the repos are close source now as Longefellow-zk is still in
> an invitation only repo.
>
>
>
> We’re happy to share it as soon as we get a green light from Matteo and
> Abhi, and hopefully we can demo it soon to one of the CCG meetings
> (theoretically even on July 8th).
>
>
>
> Cheers,
>
>
>
>   Andrea D'Intino | +45  21 62 79 18 | Project Manager
>
>   https://Dyne.org
> <https://urldefense.com/v3/__https:/Dyne.org__;!!DOxrgLBm!Gg55d-yEU7qY3PAyOjKssWDnIy8ifsyJqSbSA_mujg0N0zoZc8AhvFPweZXchR6MkrZm7zv5SbLDB4HHIGU$> think
> &do tank  | software to empower communities
>
>   ⚷ crypto κρυπτο крипто गुप्त् 加密הצפנה المشفره
>
>
>
> *From:* Matteo Frigo <matteof@google.com>
> *Sent:* Saturday, 28 June 2025 12.43
> *To:* public-credentials@w3.org
> *Subject:* Re: Longfellow ZK (google-zk)
>
>
>
> I guess Jaromil is busy preparing a demo for Geneva, so I take the liberty
> of chiming in.
>
>
>
> > How is the counter-signature (in the mDL transcript) of the
> mobile device verified?
>
>
>
> As you have surmised, the circuit verifies two ECDSA signatures, one from
> the issuer on the hash of the MDOC, and the other from the secure element
> on the transcript of the session between the relying party and the holder
> (basically a nonce provided by the RP and some other stuff).
>
>
>
> > In other words, do you know what the cost of dynamically disclosing a
> set of submessages is in Longfellow ZK, or is that not supported?
>
>
>
> The way things are currently set up is this.  Pick SZ and N in advance,
> say SZ=2048 and N=3.  We generate a circuit that takes a MDOC up to SZ
> bytes long and discloses up to N attributes.  The prover does not reveal
> the actual length of the MDOC or how many attributes/which attributes are
> in the MDOC.  "Disclosing an attribute" today means equality check: for 0
> <= i < N and given key[i], val[i] as public inputs, the circuit proves
> that, for all i, some attribute exists in the mdoc that matches (key[i],
> val[i]).
>
>
>
> Most of the proving cost is in the SZ term, because we have to hash SZ
> bytes.  The N term is smaller, say something like 30ms for each extra
> attribute.
>
>
>
> We do equality-check only because we lack imagination.  If use cases arise
> that require, e.g., less-than comparisons, we can easily add those at
> negligible cost.  I think the fullness-of-time circuit will look like N
> "arithmetic-logic units" that can be configured to compute a few common
> operations, and N giant multiplexers that route the MDOC bytes to the input
> of the ALU.  Today the ALU is just an equality check.
>
>
>
> > ECDSA is not post-quantum.
>
>
>
> Agree.  That's the next thing to work on---how to verify a post-quantum
> signature in a circuit.  This is a hard problem.
>
>
>
> > SD-JWT
>
>
>
> I'll let Jaromil say what he wants to say.  I note that, from the ZKP
> perspective, SD is redundant because it accomplishes the same goal as ZKP
> in a less perfect way.  So it's better for us to start from plain JWT
> rather than having to compute a redundant hash in SD-JWT.  MDOC is SD-only,
> so it is suboptimal from our perspective.
>
>
>
> > Circuit compression.
>
>
>
> As you have surmised, there is a lot of redundancy in the circuit.  There
> are 36 identical instances of SHA256 permutations, 2 identical ECDSA
> verifications, and each SHA256 is itself multiple identical rounds, and
> each round is multiple identical XORs etc.  There is redundancy at all
> levels of abstraction.  Our current strategy is to flatten everything into
> individual gates (the "netlist" as hardware people would call it) and
> ignore the redundancy.
>
>
>
> The redundancy manifests itself in two ways.
>
>
>
> First, the circuit is highly compressible for the practical purpose of
> distributing the circuit to all phones.  Since ZSTD was good enough we
> didn't worry too much about this issue.  I am sure one can do better but
> 300KB is in the noise.
>
>
>
> The second issue is more important.  It is in theory possible to exploit
> the redundancy in sumcheck itself.  For example, we know how to run one
> SHA256 circuit on vectors of 36 elements instead of instantiating the
> SHA256 gates 36 times, and in fact this "vector sumcheck" algorithm would
> be about twice as fast as the other one.  (Both versions are in the code
> but the vector one is disabled.)  If the whole circuit were just repeating
> SHA256 36 times we would be done, but things get much more complicated when
> we have to select the N attributes, where now the attributes are misaligned
> with respect to the SHA256 vector dimension.  This is kind-of analogue to
> AVX programming, where you have a vector unit that performs 8 additions but
> you still need to perform scalar operations.  Any attempts to exploit
> vector operations leads to complexity that we are unwilling to impose to
> the world at this stage.  We would also need some circuit-description
> language and compiler support which we don't currently have.
>
>
>
>
>
>
>


-- 

Stephen Curran
Principal, Cloud Compass Computing, Inc.