|
Title: SNARK-based Crypto-currency Validation Model Post by: MatthewLM on December 11, 2013, 01:12:56 PM This is a continuation from the off topic discussion at https://bitcointalk.org/index.php?topic=359582.100 about using SNARK programs as an alternative crytocurrency validation model. Program execution correctness can be verified with SNARK. See here for more information about SNARKs: http://eprint.iacr.org/2013/507.pdf
The essential idea is that miners do all of the validation and provide proof-of-knowledge about the correct unspent outputs which other nodes can verify without needing to verify transactions themselves. I thought it would be something like inputs: prev_utxo_tree_hash, transaction set for current block output: utxo_tree_hash or F(prev_utxo_tree_hash, transaction set for current block) = utxo_tree_hash Indeed. If even a single hash would increase the complexity too much (would it? I don't know), I suppose you could obtain the unspent outputs from running an ordinary validation program, and then provide the tree hash as an input to a SNARK program which verifies that the unspent outputs match at the end of execution. That way you only need a boolean output for the SNARK program. I did read somewhere that the SNARK programs can have public inputs as well as arbitrary inputs which are unknown to verifiers. Is that right? Some details would be hidden to the verifier, such as the transactions. If this is correct then another node would just need prev_utxo_tree_hash, utxo_tree_hash and the signature of the execution of F to validate that the block was correctly processed. Doesn't even need the transactions. Sorry again if I'm saying something stupid about snark, this is still like magic to me so it's hard to retain what can and cannot be done. This is what I thought. And if you could embed previous proofs into new proofs then blocks could contain a proof that the previous proof was verified. Then you would only need the latest block, because that block would act as proof for all of the previous blocks. That would be ideal. The blocks would need to then also calculate and provide proof for the total work done, so that nodes can simply choose the block with the chain with the highest total proven work. Title: Re: SNARK-based Crypto-currency Validation Model Post by: 2_Thumbs_Up on September 06, 2016, 04:09:56 PM I'm surprised this thread didn't get any attention.
Couldn't this be used to make confidential transactions more efficient as well?. Miners could validate the range proofs of all outputs in their block, and everyone else just verifies the miner's SNARK-proof. This would make the range proof redundant as soon as they get in a block, and they wouldn't contribute to the peak in bandwith usage when a block is found. Also, what's the size of a typical SNARK-proof? Title: Re: SNARK-based Crypto-currency Validation Model Post by: kushti on September 07, 2016, 01:52:21 PM The idea is very attractive in theory, but in practice proving time would be much more than 10 minutes inter-block delays.
Title: Re: SNARK-based Crypto-currency Validation Model Post by: 2_Thumbs_Up on September 09, 2016, 02:01:08 PM The idea is very attractive in theory, but in practice proving time would be much more than 10 minutes inter-block delays. What factors determine the proving time?Can't it be parallelized somehow by proving different parts seperately, and then use these proofs as inputs in another SNARK-proof? Title: Re: SNARK-based Crypto-currency Validation Model Post by: 2112 on September 09, 2016, 02:41:53 PM The whole idea is ambiguous and not well-defined. The problem centers around what it means to "verify zk-SNARK". There are two possible interpretations:
1) evaluate a given zk-SNARK to verify that the input data satisfies the particular condition. 2) verify that the given zk-SNARK actually tests for the condition stated by whoever had given it to you. If you re-read the linked paper paying attention to trust boundaries, you'll find that it doesn't really apply to the trust-less cryptocurrency model. What is missing is a distinction between two processes: 1) generate a zk-SNARK for a particular condition without knowing your resultant zk-SNARK in advance 2) knowing a particular zk-SNARK perform a regeneration of it to verify that it was generated properly and tests for the condition that it was supposed to test, not something else Only if you'll find process (2) that takes substantially less energy than process (1) the "generation of zk-SNARKs" would be anything suitable for trust-less mining. |