zero-knowledge

ゼロ知識証明 と SNARKsのリンク メモ

More than 1 year has passed since last update.

ゼロ知識証明とは?

わかりやすい順にリンクを並べてみました。

リンク集

以下の書いてあったものをそのままメモ代わりに

引用元: [Cryptography] blockchain and trustworthy computing

Here are some links in that direction:
https://github.com/scipr-lab/libsnark
https://github.com/Zerocash/libzerocash
https://github.com/pepper-project/tinyram
http://people.xiph.org/~greg/simple_verifyable_execution.txt
http://www.pepper-project.org/

typed presentations on the topic:
http://diyhpl.us/wiki/transcripts/simons-institute/a-wishlist-for-verifiable-computation/
.. last one has good video, https://www.youtube.com/watch?v=Z4jzA6ts2j4
http://diyhpl.us/wiki/transcripts/simons-institute/snarks-and-their-practical-applications/
http://diyhpl.us/wiki/transcripts/mit-bitcoin-expo-2015/zerocash-and-zero-knowledge-succint-arguments-of-knowledge-libsnark/
http://diyhpl.us/wiki/transcripts/scalingbitcoin/snarks/

some history of probabilistically checkable proof (PCP) stuff:
http://diyhpl.us/~bryan/papers2/bitcoin/snarks/pcp/pcp-history.pdf
http://diyhpl.us/wiki/transcripts/simons-institute/zero-knowledge-probabilistic-proof-systems/

quadratic arithmetic/span programs (non-interactive zero knowledge
proofs without probabilistically checkable proofs (PCPs)) (GGPR):
https://eprint.iacr.org/2012/215.pdf

Recently I gave a presentation with a very high level and general
overview of ways to (ab)use SNARKs for bitcoin scalability reasons:
(start at page 43) http://diyhpl.us/~bryan/irc/bitcoin/scalingbitcoin-review.pdf

SNARKs

NIZK: Non-interactive zero-knowledge proof

NP: Non-deterministic Polynomial time(非決定性多項式時間)

SNARKS for C

PDF: Verifying Program Executions Succinctly and in Zero Knowledge
https://eprint.iacr.org/2013/507.pdf

Zerocash

How zerocash works | Zerocash

1985: The Knowledge Complexity of Interactive proof Systems

https://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf

  • Completeness:
  • Soundness:
  • Zero-knowledge:

CoinDesk Article

Hawk

Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts
https://eprint.iacr.org/2015/675.pdf

関連用語

  • 知識の署名 (SPK: Signature based on a Proof of Knowledge)
  • ZKIP: Zero Knowledge Interactive Proof
  • zk-snarks: zero-knowledge Succinct Non-interactive ARgument of Knowledge
  • Bitcoin
  • zero-knowledge proofs
  • Zerocoin, Monero
  • 神託機械, 預言機械, oracle machine