Alternative Zero Proof Approach


#1

Hello guys,
I have a question about the zero knowledge proof.
I have understood that Indy’s/Sovrins ZKP relies on Idemix. I have also read that the proof has been a little bit over-engineered. I wonder why the ZKF has been made so complex.

I have an alternative (at least a logical approach).
Suppose Alice has to proof: salary > $ 2000 (for applying a loan at the Thrift bank).
Her wallet has a valid credential (I prefer the word claim) “Job-certificate” with salary = $ 2400, signed by Acme, her current employer.

Alice’s Indy app could satisfy a proof request of the Thrift bank as follows:

  • Load the json structure of Alice’s Job-certificate as a (UML) object
  • Inspect the predicate “salary > 2000”, looking up the “fact” “salary” in the job-certificate object
  • Substitute “salary” in the predicate by 2400
  • Evaluate the expression “2400 > 2000”, which is true
  • Send the proof result to Thrift bank
    Assumptions:
    • The published Job-certificate scheme on the ledger (published by who?) could be considered as a xml scheme.
    • The content should be formalized and standarized, like for instance XBRL for financial reporting
    • The published Acme-Job-certificate definition on the ledger (published by Acme) could be considered as an instance of the Job-certificate scheme.
    • The Thrift bank must be able to lookup schemes on the ledger to compose their required proofs.
    • The Job-certificate scheme contains meta-data like datatype, kind of salary, month or year salary, gross or net salary, currency and so on.
    • Predicates (I prefer assertions) are regular expressions of conditions , that evaluate to true or false
    • The predicates in a proof request must refer to a published scheme (not to a definition as denoted in the getting started guide!)

Why is such a kind of a ZKF not secure enough?

Kind regards
Frank Alleman


#2

Frank:

ZKPs are a simple concept, and I think they’re accessible enough for most coders to understand at a high level. However, assurances of trustability and standards for extremely careful management of privacy have a way of complicating their implementation.

It is true that ZKPs in Indy/Sovrin are related to Idemix, but this is not a build or run-time dependency; rather, there is a commonality in the math. Indy/Sovrin builds on the math that Idemix first described.

I’m not sure who told you that ZKPs in are over-engineered. There are some smart people in the identity space who do believe that, but by no means is this an accepted consensus. Typically, people who offer this critique don’t buy into Sovrin’s stance on privacy, and they advocate a very simplistic form of selective disclosure that shares signatures, hashes, credential identifiers, or other pieces of data that provide perfect hooks for correlation. This is a philosophical difference, not really an architectural disagreement.

In your proposed algorithm, I don’t understand the magic that happens between steps 4 and 5. Observing that 2400 > 2000 is fine–but how do I prove to a verifier that I have done an evaluation that satisfies their criteria, without also revealing the number that I used as input? What math would you suggest using in the proof presentation?


#3

Hello Daniel, thanks for your comment, I appreciate that very much.

There is hopefully no magic between steps 4 and 5. Probably I miss something. Let me explain my humble logical (not math) approach a little bit more.

Alice has a claim Acme-Job-certificate in het possession. The one way SHA hash over the json structure has been signed by the issuer, Acme Corporation. This means that it is hard to modify the content of the claim from outside.

The expression 2400 > 2000 results in “true” and that result is send back to the verifier (Thrift bank). Important here is that the the Indy software of Alice’s agent evaluates the expression, not Alice herself. That software looks up “salary” in het credential/claim “Acme-Job-certificate” (*1), substitues “salary” by 2400 and evaluates the expression. So the software tries to perform the proof automatically (= automagically?).

*) The proof request contains the restriction that a credential/claim “Job-certificate” must be used. The Indy software only looks up the value of “salary” in credentials/claims that meet this restriction. Therefore Acme-Job-certicate must be a subtype of Job-certificate.

I hope you can find a shortcoming in my theory.
Frank


#4

Hello there, my issue still hasn’t been solved, who can help me out?!
I have looked at simple ZKP concepts like the Ali Baba cave, which illustrates an interactive (and expensive?) ZKP concept, possibly implemented by using the discrete logarithm of a given value (refering to Wiki).
I assume a non-interactive ZKP is much more desirable. I have done a lot of desk research, but I didn’t find a useable abstract and simplified concept (like the Ali baba cave). I need such concepts to explain ZKP to my students (and to promote Sovrin and Indy !).


#5

Frank:

The magic between steps 4 and 5 is tied up with the question, “Who is doing the evaluation?” If Alice’s software does the evaluation, and the verifier is Thrift Bank, then how does Thrift bank trust an assertion from Alice’s side that an expression evaluated to true, without knowing the two operands in the expression? Although it is difficult to change the JSON of the proof, due to a hash/signature, I don’t see anything in your approach that associates the evaluation with the credential’s JSON in a tamper-proof way. I was assuming that you knew some magic that would make that happen.

Regarding interactivity: the Ali Baba example on wikipedia describes the proving as an interactive approach with multiple samples/trials. However, that is not the way ZKPs in Indy work. A verifier in Sovrin does not ask the prover to prove something, over and over again, generating numerous round trips of challenge/response. Rather, the math allows the verifier and prover to construct a single test that has a 1-in-2-to-the-N chance of being fakeable–where N is a very large number–in a single round trip. At one point I could explain the mathematical operation that makes this so, but its details are escaping me now. Perhaps a crypto expert can chime in.


#6

Fallemen,

Indy credentials use CL signatures to sign the attributes. Non-Interactive Proofs can be created using the CL signature by creating another signature and using the existing Issuer signature as a witness. CL Signatures allow proofs to hide the number of attributes signed, but Sovrin defines that number in the schemas. CL Signatures also allow any of those attributes to be hidden and revealed. Predicates like 2400 > 2000 send the hidden value of the attribute and also include a proof about the evaluated result of 2400 > 2000. So its like telling the Relying Party, There is a hidden value in this credential that was signed by an Issuer that I haven’t modified and here is a proof that that same value is > 2000. The Relying Party can have confidence that the Prover did not modify the value. I hope this answers your question.


#7

Hello Daniel,
Thanks for your explanation. When I am honest, I still don’t get your point. Let me explain why.
When Thrift bank sends a proof request, including a reference to a schema and a nonce, and Alice’s (or her agent) software evaluates the proof expression to true, and you only send back the result “true” plus the signed nonce, then WHY you have to associate the evaluation result “true” with the credentials’s JSON (Acme Job certificate) explicitly in a tamper-proof way?
Within the context of my question I assume that Thrift has build up a secure 1:1 channel with Alice and I assume that you (and Thrift) can trust Alice’s Indy software. When that software should be compromised (by ransomeware or whatever), you couldn’t trust the communication channel and her wallet as well, or am I wrong?

And Daniel, thanks for inviting a crypto expert. Mike has answered my question about a non-interactive proof concept in a clear way.


#8

Hello Mike, Thanks a lot for your answer.
For me the “functional” sentence “So its like telling the Relying Party, There is a hidden value in this credential that was signed by an Issuer that I haven’t modified and here is a proof that that same value is > 2000” is important for basic understanding.
I am going to study CL signatures a little bit more. For me it is hard to understand how to work with blinded master secrets, encoded blinded signatures etc, it’s a little bit like using pointers to pointers to pointers in C.


#9

Frank: I think Thrift can mostly trust its own software (because Thrift installed it from a reputable location), but I don’t think it’s a safe assumption that it can trust Alice’s software. It doesn’t know what software Alice is using. Trust in the Sovrin ecosystem isn’t based on confidence that a remote party has good intentions; it’s based on cryptographic proof that the remote party can’t fake, no matter how malicious their software is.


#10

Ok Daniel, now I understand your (and Sovrins) point of view. Thanks for making it clear to me.