One application that I like: sending ads with a proof proving they were
generated by some algorithm that is known not to have access to personal
data.
And I like that notation Andrew -- there is a sort of extension to it
(which is basically the idea of snarky) which involves not having to
declare all your witnesses up front. The main advantage over
the Camenisch-Stadler notation to my mind is modularity/abstraction. (For
example, you can factor out the idea of opening a commitment).
This is a bit of a contrived example but to get the idea across,
"sumCommitmentsIsZero" proves that you know openings to a bunch of
commitments such that the openings sum to 0, say.
def openCommitment(c):
(value, nonce) = *exists* OpenCommitment(c);
*assert* SHA256(value, nonce) = c;
return value
def sumCommitmentsIsZero(cs):
*assert* sum(map cs (fun c -> openCommitment(c))) = 0
(sometimes I call exists "request" instead.)
If this sort of notation was widely used, people would probably know what
you meant when you wrote openCommitment as a function, and so you could
just write the second definition in communicating. There are a bunch of
other reusable abstractions that arise in zk-proof programming that we
could build up a shared vocabulary for as well to make communicating this
stuff easier.
On Sat, Mar 24, 2018 at 4:05 PM, Andrew Miller via zapps-wg <
zapps...@lists.z.cash.foundation> wrote:
> Lucas's post reminded me of something I wanted to post about:
> If there's one thing I'd like to take up the torch for and advocate as a
> standard, it's to use a conventional pseudocode for describing snark
> application ideas. What I have in mind is Camenisch-Stadler proof
> notation. It looks like this:
>
> ZkPoK{ (witness): Predicate(statement, witness) }
>
> The idea is that "witness" is the private witness, "statement" is
> public information that the verifier provides, and you replace
> "Predicate" with whatever pseudocode you want to check.
> Here are some examples:
>
> 1. Pay-to-Sudoku:
> ZkPoK{ (solution, nonce):
> SHA2(nonce || solution) == H,
> CheckSudokuSolution(puzzleBoard, solution) == 1 }
>
> 2. Show two hashes have related preimages:
>
> ZkPoK{ (R1, R2): H1 = sha256(R1) and H2 = sha256(R2) and R1 = R2 ^ X }
>
> https://github.com/ebfull/lightning_circuit/blob/master/README.md
>
> This notation is a starting point, it can be extended to say a
> Signature-of-Knowledge, like in BabyZoe (a simplified form of ZSL,
> where the only shielded operation is to withdraw 1.0 coin from the
> shielded pool):
>
> 3. SoK[tx]{ (secretkey, Com, merkleProof):
> // Com is included in the commitment tree
> MerkleVerify(coinTree, merkleProof, Com),
> Com is a commitment to (secretkey, Nullifier)
> }
>
> Notes on BabyZoe:
> https://github.com/zcash-hackworks/babyzoe/blob/master/
> talks/2016-07-27-IC3---SNARKs-for-Ethereum.pdf
>
> To take a stab at translating the snark-based password authentication
> idea into this pseudocode, I think it could look like this:
>
> 4. SoK[signedMessage]{ (derivedkey):
> username = SHA256(addrContract, derivedkey)
> }
>
> The user would then use standard PBKDF2 from something like:
> derivedKey := Argon2(addrContract, password)
>
> so the snark circuit itself doesn't even have to have the expensive
> hash. The smart contract would use the final password hash as the
> username.
>
> On Sat, Mar 24, 2018 at 4:47 PM, Andrew Miller <soc1...@illinois.edu>
> wrote:
> > That's awesome Lucas, thanks for this input, these are pretty cool
> > application scenarios. They're all quite relevant to a standards effort
> > because they seem to involve interfacing between zkSNARKs and other
> > standardized primitives (password hash functions, anonymous credentials,
> > extensions to ZSL).
> >
> > On Sat, Mar 24, 2018 at 4:42 PM, Lucas Vogelsang via zapps-wg
> > <zapps...@lists.z.cash.foundation> wrote:
> >>
> >> I've put some thoughts into possible use cases, here are some that we
> have
> >> been thinking about in the context of decentralized business
> applications.
> >> Some of these concepts are things we are actually working on, others
> just
> >> ideas
> >>
> >> - blind auctions (including double dutch auctions)
> >> - page-rank style algorithms on top of anonymous credentials or
> >> reputations
> >> - build a password-based authentication out of any password hash
> >> - give out "referral capabilities" that automatically assign a
> commission
> >> to whoever introduced a subscriber who signs up (this would be part of a
> >> privacy-preserving subscription service, that could be built on top of a
> >> zcash-like (ZSL protocol) cryptocurrency)
> >> - consumer credit scores: create a registry of "bad debtors". use
> zkproofs
> >> both to "register" a bad debt/bad action and allow individuals to
> provide a
> >> proof revealing your score without actual transaction details (not sure
> how
> >> exactly this could work)
> >>
> >> Curious to hear what other people have thought of!
> >>
> >>
> >> On Fri, Mar 23, 2018 at 11:11 AM, Andrew Miller via zapps-wg
> >> <zapps...@lists.z.cash.foundation> wrote:
> >>>
> >>> Dear Zapps, I just wanted to let you know that there will be a
> standards
> >>> workshop organized by several academics / industry participants in May.
> >>> https://zkproof.org
> >>> I want to make sure that the workshop includes input from all the
> groups
> >>> involved in this open source community that are developing tools and
> >>> applications and even making initial standardization efforts around
> >>> portability between different libraries.
> >>>
> >>> I'm especially interested in collecting application ideas to include
> as
> >>> case studies to help make the conversation more concrete. So far I
> don't
> >>> have many ideas. So far I have:
> >>> - anonymous credentials
> >>> - zcash
> >>> - voting
> >>> - sudoku solutions / contingent payments
> >>> - compressing blockchain verification
> >>> - a log of photo edits
> >>> - checking that a cloud compute task was done correctly (this is
> arguably
> >>> not specific enough).
> >>>
> >>> Suggestions of what I'm missing?
> >>
> >>
> >
> >
> >
> > --
> > Andrew Miller
> > University of Illinois at Urbana-Champaign
>
>
>
> --
> Andrew Miller
> University of Illinois at Urbana-Champaign
>
