ZK-gossip for lightning channel announcements

Hi @halseth thanks for the impressive work you’ve been putting on this zk prover.

One major advantage I can think of using this approach, is that it works out-of-the-box with extremely lightweight nodes like floresta and utreexod, since the utreexo state is all context you need to verify the proof. This would be beneficial for resource-constrained lightning nodes, as they may not have full access to the UTXO set.

Just out of curiosity: have you benchmarked this using an algebraic hash function? rustreexo now (since October last year to be precise) lets you choose your custom hash function, and algebraic hashes are waaaayyy lighter when running inside a prover. I wonder how much proving time is due to utreexo proofs.

I see you’re using my bridge node for proof generation, it supports Poseidon 2 as hash function and puts everything in a nice json format intended for provers (this was developed for the folks at starkware for their bitcoin zk prover), just need to toggle the shinigami feature (it won’t build the API tho).

1 Like

Aha, I get what you are saying. Using a different UTXO than the channel output as the “anti-spam cost”.

However, I’m not sure if it give us anything (in a non-ZK scenario it obviously could):

  • Since channel counterparties have to create a multisig output in order to open a channel between them, you already have a utxo available for this purpose. (if we wanted to allow channels not backed by a real utxo this would not be the case of course…)
  • Channels are often created between non-trusted parties. Who would put up a utxo in that scenario? If both had to that would be less scalable of course.

Thanks!

I have not tried the algebraic functions, but it is on my list of optimizations to try!

Great to hear that rustreexo has it available already, that will make it a lot easier to test out :smile:

I had been working with a mental model based on what I read a long time ago here (Rusty’s gossip v2 proposal, I think the original one? Hard to keep track).

To crib from there:

  1. Nodes send out weekly node_announcement_v2, proving they own some UTXOs.
  2. This entitles them to broadcast channels, using channel_update_v2; a channel_update_v2 from both peers means the channel exists.
  3. This uses UTXOs for anti-spam, but doesn’t tie them to channels directly.
  4. Future ZKP proofs are could be added.

He also has a concept of claiming the channel on open at the end of that post. Obviously in that model, my perspective should make a lot more sense.

But it seems pretty clear you’re looking at it differently (as per the OP, v1.75 but with zkp added in). Responding more directly to your Q, though, I think you could make this argument: single funder provides zkp, dual funders have the starting channel balance reflect the asymmetric cost of one funder making a single proof; but as you can see this is fudgy, and maybe I’m wrong. I personally find Rusty’s model makes a lot more logical sense, taking anti-DOS as far away as possible from the blockchain and making capacity claims vague).

I think that model makes a lot of sense in the non-ZKP scenario, since you have to reveal some utxo but allow it to be a different one from the channel.

In the ZKP setting I think it is less efficient, as using the actual channel utxo as stake doesn’t reveal it.

Also, as you mention, this proposal doesn’t change the trust model as much; each channel is still backed by a single UTXO, you just don’t reveal which one.

From profiling looks like most of the proving time comes from key aggregation (to verify the Musig signature), while utreexo verification and SHA-256 play a much smaller part.

Oh, nvm then. Def not worth it.

It actually makes sense, once ECC enters the game, everything else becomes irrelevant performance-wise. (It’s good to know my code isn’t the bottleneck tho :joy: ).

I did work on a new approach where we do the signature verification on a blinded key, such that we can move the heavy EC operations outside the ZK environment (see the discussion here: (EDITED) following README example - slower proving time? · Issue #10 · halseth/output-zero · GitHub).

This results in the SHA-512 hashing in verifying the utreexo proof dominating the runtime:

@Davidson How easy is it to either

  1. Switch to using the poseidon2 hash function for this, OR
  2. use the Risc0 precompile for SHA-512 (it looks like rustreexo is using the bitcoin_hashes::Sha512 implementation).

I see that this is made possible in the latest rustreexo release :+1:

Changing the utreexo hash function to using SHA-256 (which has a Risc0 precompile) reduces proving time to 22s using this approach:

Now again the two EC multiplications (blinding the key and creating the taproot output key) dominates (in addition to ZKVM serde).

1 Like

The way the ZK-proof was created in the original post here, is very non-intrusive and simple to apply to existing LN implementations. You simply take the gossip message, and do the verification of it in zero-knowledge, hiding all the inputs that would leak your privacy (namely the bitcoin_key fields).

However, this requires to to the full Musig2 key aggregation and signature verification in the ZK environment, which can be expensive and slow. On my machine proving time was about 80 seconds.

To speed this up, I created a variant of this that does less work in ZK, by blinding the channel output key with a tweak before funding it. The tradeoff is that the LN implementation must be aware of this tweak.

It works by the channel counterparties creating a Musig2 aggregate key P as before, but then agreeing on a secret blinding value r, and beta = hash(r || P). The output key will then be P_out = P + beta * G (optionally this key can then be given a taptweak if needed).

Now channel operation can work as before, but the parties must tweak the key with beta before signing.

When creating the gossip message, everything will be done as before, and the verifier will validate the channel announcement according to the gossip 1.75 proposal. The only difference is that the output tapkey is not found on-chain (since it has been tweaked) and hence we must attach a ZK proof to prove that the tweaked version is actually in the UTXO set.

An implementation of this approach is here: GitHub - halseth/output-zero at blinded-tap-key

This reduces proving time to 16-22 sec on my laptop since we are left with only 2 EC multiplications (see above pprof flamegraph).