Announcing Halo: Recursive Proof Composition without a Trusted Setup

#1

This is big for both Zcash and the emerging decentralized internet. The full details are available on our blog: https://electriccoin.co/blog/halo-recursive-proof-composition-without-a-trusted-setup/

20 Likes
#2

Amazing work, @ebfull, @str4d & @daira!

I thought it was interesting to see one of the code examples is a recursive proof of Bitcoin’s proof of work. It isn’t mentioned explicitly in the paper, but presumably this can be used as a succinct proof of proof of work (useful for SPV)? In which case, it would also be interesting to understand the complexity of deployment within existing smart contract systems such as Ethereum’s EVM, and whether or not the gas cost would be prohibitively expensive to verify a proof.

5 Likes
#3

Yeah, we’re working on a PoC for that example right now. I think at the very least it seems like an interesting alternative to checkpoints (in Bitcoin) when you don’t trust most of your peers to be feeding you the correct blockchain. Unfortunately the verification costs involve at least two large multi-exponentiations so I’m not sure that our existing protocol will be ideal for Ethereum. Maybe future, improved protocols based on our ideas will though.

6 Likes
#4

What are the benefits of ZCASH and how are they planned to be put into practice?

#5

No trusted set up and scalability! Boom :boom:

source

3 Likes
#6

tenor

#7

Any idea how long it will take to integrate it into Zcash? It might help us determine funding levels for the next 4 years.

1 Like
#8

(It is cool but I kinda liked the trusted setup, dont @ me)

2 Likes
#9

cool work. follow it !

#10

So if I’ve understood this correctly, a new wallet wont need the blockchain, just a proof for its initial state.

No heavy download, fits on a phone, good to go almost immediatly. Holy cow!!

Edit: Hoping we get a ‘muggle version’ of the paper at some point, even if its just a list of ‘things it can enable’.

2 Likes
#11

Could you please link me what youre reading? I am no cryptography expert but I do have a batchelors in math and a masters in cs I might be able to handle it…

#12

Here y’go, you’ll know what an aneurysm feels like when you’re half way through - its heavy stuff.

2 Likes
#13

Thank you very much I probably wont be able to handle it since I havent been working in my field after finishing uni and that was like a little over 10 years ago, but Im optimistic by nature.

1 Like
#14

Can someone explain the difference between Spartan and Halo please? Im not too sure.

https://eprint.iacr.org/2019/550

Okay, I am a bit better informed now. I thought this was separate work. from spartan, which I guess it kind of is. but it builds upon it. nice work.

nope read more. confused again. oh well.

#15

Spartan is an example of a SNARK (in theory) though it has large constants so I’m unsure if it will work well in the recursive context. Halo is an attempt to take proving systems (Sonic built over the inner product argument, for example) that aren’t necessarily succinct but still achieve recursive proof composition with them.

7 Likes
#16

I’am not that euphoric yet until there is some audit and/or it’s clear how security plays out with HALO…

…
In other words, the miners will be responsible for both the proof generation and verification of the final ZK-SNARK. This resembles the case where one plays the roles of both the player and judge in the field simultaneously. It is also not clear how the subsequent protocol (if there is any) built on Halo would attempt to resolve this issue. Neither the Coda team nor any existing academic work provides any security argument to justify this action. Bitcoin can legitimately claim its blockchain resists 51% attack. What’s the security level of the recursive proof framework when most of the miner computing power are dedicated to proof generation instead of verification? 1%? 0.1%? One cannot simply just trust the protocol developer without the support of any formal argument. I thought the whole point of blockchain is “in math we trust”?
…

#17

This post appears to misunderstand both the application of recursive validation, and the Coda blog post it is referencing. If the miners are the ones creating recursive chain proofs, then it should be obvious those proofs aren’t solely going to be verified by themselves:

  • If the recursive proofs are part of the consensus rules (forcing miners to create them), then they will be verified by other full nodes as well (necessarily, otherwise the chain they have can’t be valid).
  • If the recursive proofs are not part of the consensus rules (e.g. if they were only used for light client bandwidth improvements with an SPV-style security model), then there’s no difference between a miner generating these proofs, and some other entity (e.g. a wallet provider) doing so. And depending on what the recursive circuit covers, you could in fact have stronger security properties than SPV (because the proofs could themselves bundle in proofs that the block contents are valid).
4 Likes