zkSNARKS -> zkSTARKS

General
#1

How do you plan to move Zcash to zkSTARKS? Will it be new coin? fork?

Can you explain details around this issue in more detail?

#2

There was some news about a new proving key and, I think, a fork that would be needed to switch to it. It’s possible that a further advance could remove the need for it or allow that kind of data to be generated without even theoretic possibility of abuse…

I gather this article provides a basis for your question - Zk-Starks? New Take on Zcash Tech Could Power Truly Private Blockchains - CoinDesk Setting aside suspicions of anything to do with Monero, what size proofs / transactions would such a scheme generate? In my opinion, to be worthwhile the proofs would have to be much closer to the Zcash end of the spectrum, ie: roughly 300 bytes, than the Monero end of the spectrum, ie: 2000 bytes.

1 Like
#3

From the article I linked above: "Zk-starks seek to remove this risk, and in the process, take a lot of the heavy machinery associated with zk-snarks with it. Unlike zk-snarks, zk-starks don’t rely on public key cryptography at all.

Actually, all zk-starks need to function is one algorithm similar to that performed by computers when mining the bitcoin blockchain."

This reminds me of ‘Quantumresistant’ [ANN] QRL - Announcing the Quantum Resistant Ledger which seeks to use hashing instead of cryptographic signing - and also seems to generate transactions with large byte sizes.

1 Like
#4

Professor Eli Ben Sasson is a member of the Zcash team and has been working on Starks for some time now. Last I heard they are still working on getting the proof sizes down to make them viable for Zcash. I would bet good money that as soon as Starks are ready for prime time, Zcash will be the first to incorporate them.

Recent progress on one part of the Stark is in this paper: https://eccc.weizmann.ac.il/report/2017/134/

He talks a bit about Starks here: Towards Transparent and Scalable Computational Integrity and Privacy - YouTube

9 Likes
#5

Re PQ, @Voluntary, you want Issues #805, “post-quantum Zcash“, and #2527, “[Sapling] Analyse post-quantum effect of Sapling”.

Not totally off-topic. Last February, @daira in #805 linked the same Youtube video as today’s Coindesk article.

Note well the difference between PQ financial safety, and PQ forward-privacy. Bitcoin already has some measure of PQ financial safety due to use of hashed addresses: IIUC, if you use one-time addresses (as best practice), a quantum attacker who can break the elliptic-curve crypto cannot arbitrarily spend your coins. Bitcoin has no privacy at all, so it loses nothing there; thus I see no reason for a PQ Bitcoin clone based on Lamport signatures, etc. The safety of balances in current one-time addresses, and visibility of the monetary base, together provide a future PQ upgrade path if/when necessary.

Zcash would be financially ruined under those very unlikely/far-future conditions, because a PQ attacker could create unlimited ZEC; but according to Daira in #2527, it “conjectured that Sprout has post-quantum privacy for z-addresses that are kept secret between payer and payee against a quantum adversary, and Sapling should at least preserve that property.” (Emphasis added.) In terms of confidentiality, I think that’s already better than Tor and PGP, captured traffic from which could likely be retrospectively decrypted by a PQ attacker. And it’s definitely better than Bitcoin, which has no useful confidentiality properties at all.

Back to topic, a decent writeup on zk-STARKs at approximately AC2-reader level would be really useful.

2 Likes
#6

My question is - will it be some kind of fork (all coins will migrate ) or it will be new genesis block (starting from scratch)?

1 Like
#7

Really excited for ZK-STARKs this is some interesting stuff for sure!

Yes I too have the same question as @santacruz123 …will it be a new genesis block or fork?

#8

Hm… What if zk-STARKS turn out to be sufficiently competitive in terms of transaction proof size and obviating the need for a large proving key - could Zcash initiate a new chain beginning with a genesis block composed of pre-submitted 1:1 atomic swaps of zk-SNARK Zcash that go to a particular burn-address in exchange for that balance being re-created on the new zk-STARK chain? It’s clunky but that would also serve as a way to prune overgrown blockchains and do significant protocol overhauls…

#9

I don’t have any answer specific to zk-STARKs. That is likely not in the immediate future. But a many other incompatible changes are planned, including the “Sapling” circuit upgrade currently expected for next year (2018). For the general topic of future changes to Zcash, I recommend reading:

If zk-STARKs survive cryptographic review and are developed into a usable technology, I would expect to see them appear in a future circuit upgrade, post-Sapling. SNARKs took about 3 years from initial academic papers (2013) to full implementation (2016). Meanwhile, SNARKs and the algorithms which run on the SNARK are still being improved! I expect that we will see big performance improvement with SNARKs in 2018, and maybe STARKs around 2020.

Note that I am not associated with ZECC, and I do not know their plans on that particular point. I could be totally wrong in my prediction.

4 Likes
#10

An update on zk-STARKS:
Apparently running on a browser from a smartphone!
Next step after Sapling?

5 Likes
#11

A post was merged into an existing topic: Shielded transactions on Ethereum layer 1 now a reality