Extending Existing Json Web Algorithms to Support Some ZKPs

[boumba100]

As we already know, the existing set of Json Web Algorithms (JWA) only really support proof of authenticity (I.e., that a message was signed by a certain key, and that it was not modified). I propose extending some of the existing JWAs, enabling them to support more extensive proof types such as selective-disclosure, compound proofs, and predicate proofs.

I believe this could be achieved with the following approach.

Generating a digital signature.

1. Create a vector Pedersen commitment on the messages (m1...mi).
   • COMMITMENT = g₁^m1 * g₂^m2 * g_i^mi * g_n^nonce .
2. Sign the commitment using an existing digital signature algorithm (e.g., ECDSA).
   • SIGNING_INPUT = HASH (COMMITMENT)
   • SIGNATURE = GENERATE_SIGNATURE (SIGNING_INPUT)

Generating a proof.

1. Generate the required message proofs (MESSAGE_PROOFS), e.g., selective-disclosure/proof-of-knowledge
2. PROOF = (COMMITMENT, MESSAGE_PROOFS, SIGNATURE)

Verifying a proof.

1. VERIFICATION_INPUT = HASH (COMMITMENT)
2. VERIFY_SIGNATURE (VERIFICATION_INPUT, SIGNATURE)
3. VERIFY_MESSAGE_PROOFS (MESSAGE_PROOFS, COMMITMENT)

The homomorphic encryption property of a Pedersen Commitment would enable a prover to create a larger set of proof types on hidden messages. In fact, this is how the Ursa BBS+ and PS signatures implementations support it.

Some Pros and Cons of this approach

Pros:

• A small component to implement on top of existing digital signature libraries
• Allows for multiple messages to be signed instead of one
• Could enable predicate proofs
• Could enable compound proofs, even between unlinkable proof algorithms such as BBS+ (needs some investigating)

Cons:

• Proofs are still linkable

Jpa Identifier

A JPA identifier for ES256 plus the described approach could be ES256+C, where C stands for commitment.

Pedersen Commitment Building Block

Another aspect to take into consideration is that the Pedersen Commitment is a building block for many of the ZKP proof algorithms. With this into consideration, I am wondering if we should create a section in the JPA draft spec to document the different proof algorithms that could be applied to Pedersen Commitments. JPAs can then refer to those algorithms.

Useful Links

• https://asecuritysite.com/encryption/ped
• Vector Pedersen Commitment Proof of Knowledge URSA RFC (this is how selective disclosure is done for BBS+ and PS Signatures)

Noah

[quartzjer]

I really like this approach, I'd love to help develop it further as well!

There's very high level similarities to the "Single Use" JPA that is starting to get documented in the latest draft.

Would you want to contribute this as PR for a new section in the JPA draft, or develop it on its own further?

[boumba100]

Sounds good!

I'll start documenting this approach in the JPA draft.

[quartzjer]

Hi @boumba100, just bumping this thread as we now have two JPAs documented and curious if you think this can be developed into a third?

[boumba100]

The following link points to the draft I've been working on:
https://github.com/boumba100/json-web-proofs/blob/jpa-draft-ec%2BC/draft-jmiller-json-proof-algorithms.md

Please feel free to make any suggestions.

Thanks,
Noah

[OR13]

You may also like: https://vitalik.ca/general/2021/06/18/verkle.html

[quartzjer]

@boumba100 Impressive!

IMO what you've written up so far is easily substantial enough to be its own standalone work. Would you be interested in creating it as a draft in your own name? It can still be a PR to this repo, would just separate the work into an algorithm specific draft.

Would you be free 30 minutes before the upcoming JWP sync call next Tuesday to walk me (and anyone else interested) through it all?

Also just to be sure I'm processing this correctly so far, this algorithm will support selective disclosure and predicate proofs but it will not support unlinkability since the S from the issuer is also provided as-is to the verifier, correct?

[boumba100]

Hi @quartzjer,

That proposition interests me.

Count me in for a chat before the next call.

Regarding proof linkability, you are correct.

A commitment that is signed using a traditional ECDSA algorithm is linkable because the value of s will not change. That said, the vector-commitment building block could be combined with a ZKP signature/proof algorithm (e.g., BBS+, PS Signatures, blind signatures) to support unlinkable proofs.

[dwaite]

FWIW, @OR13 's verkle reference is on a server which does not appear to currently be running, see instead https://web.archive.org/web/20231115115627/https://vitalik.ca/general/2021/06/18/verkle.html

[dwaite]

This is a bit of a call-out to see if there is still interest in this family of algorithms.