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.pdfThe 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.