Andrew Miller [ARCHIVE] on Nostr: đź“… Original date posted:2015-12-02 đź“ť Original message: So, it turns out that a ...
đź“… Original date posted:2015-12-02
đź“ť Original message:
So, it turns out that a SNARK is overkill for the application in this
thread. It was just a one-off experiment. But the performance estimates
seemed pretty far off compared to what’s reported in in the snark science
papers. So, Sean (a Zcash engineer, in his “20% fun time”) replicated the
experiment from the original post, in libsnark (not snarklib).
First, as a recap, this is the specification of the original post’s SNARK,
summarized in Camenisch-Stadler notation:
ZkPoK{ (R1, R2): H1 = sha256(R1) and H2 = sha256(R2) and R1 = R2 xor X }
In other words: given a statement H1, H2, and X, you can prove that you
know a secret witness R1, and R2, such that the predicate holds (i.e., R1
and R2 are preimages of H1,H2 and are related by X)
This is almost a complete specification of the SNARK: all that’s left is to
choose a representation size for R1 and R2…. here these are forced to be
32-byte strings.
Here are the results for a libsnark implementation of this, ordered up to
the above spec:
https://github.com/ebfull/lightning_circuit/
Most relevant benchmarks:
key generation time: 11.6270s
proof generation time: 3.0968s
verification time: 0.0270s
proof size: ~287 bytes
proving key size: ~12.85 megabytes
verifying key size: ~573 bytes
R1CS constraints: 56612 (mostly sha256-related)
The difference in proof time and proving key size (this is ~3x faster to
prove, with ~10x less key size) might be explained by libsnark having a
more efficient SHA256 implementation. The libsnark one is hand-optimized.
But I don’t have any idea why the OP and snarklib reported such large
verification keys or memory consumption during verification. The verifier
should only have to think of about a kilobyte.
On Tue, Nov 17, 2015 at 4:14 PM, Anthony Towns <aj at erisian.com.au> wrote:
> Hi all,
>
> An obvious privacy limitation with lightning is that even with onion
> routing, differents hops can be associated as being part of the same
> transaction due to sharing a common R value. So if you see a HTLC from
> Alice to Bob, paying $5 to Bob on receipt of R where SHA(R)=12345..;
> and you see another HTLC from Carol to Dave, paying $4.95 to Bob on
> receipt of R under the same condition, SHA(R)=12345..., then you know
> it's part of the same transaction.
>
> If you could change R at each step in the route, this would go away,
> improving payment anonymity and making it harder to attack the system in
> general.
>
> That's hard, because as a forwarding node, if you receive a HTLC payable
> on R1, then to send a HTLC payable on R2, you need to be able to
> calculate R1 from R2 or you'll be out of pocket. But you also can't be
> able to calculate R1 *without* R2, or you could just rip off whoever's
> making the payment. And, of course you have to know SHA(R2) to forward the
> payment at all. And if you only know SHA(R1) and SHA(R2) it's hard to
> say anything at all about R1 and R2 because cryptographic hash functions
> are designed to make any structural relationships go away.
>
> BUT! I think the magic of SNARKs [0] lets you do this!
>
> With a SNARK, you can "prove" that you have some secrets (ie, R1 and R2)
> that satisfy some programmable condition (ie, SHA(R1)=H1 and SHA(R2)=H2
> and R1=R2 XOR X), based on public inputs (H1, H2 and X), without revealing
> those secrets.
>
> I think that's pretty safe, because if you receive an HTLC asking for a
> preimage for H1, along with instructions in the onion saying ask Bob for
> a preimage for H2, and here's X and a proof, then either:
>
> - your forwarded HTLC will fail, and everything's fine
>
> - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1)=H1 as
> expected, and everything's fine
>
> - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1) != H1,
> which is only possible if the cryptography behind SNARKs are broken
>
> - you'll receive RX, such that H2=SHA(RX) but RX being too
> long or too short. If SNARKs aren't broken, this means that you know
> R2alt and someone else knows R2 that are different but hash to the
> same value, meaning SHA has been broken.
>
> It seems like there are research-level tools out there that actually
> make this practical to try out. I've had a go at implementing this using
> snarkfront [1]. Using it looks like:
>
> 1) initial setup of proof/verification keys
>
> $ ./test_lightning -m keygen > keygen.txt # global setup
>
> 2) generate a proof, using a 32 byte secret, and XOR key (64 hex digits)
>
> $ SECRET="the quick brown fox jumps lazily"
> $ XOR=$(echo "she sells sea shells" | sha256sum | head -c64)
> $ cat keygen.txt |
> ./test_lightning -m proof -s "$SECRET" -x "$XOR" > proof.txt
> m: proof.
> f: .
> b: .
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> F: 74686520717569636b2062726f776e20666f78206a756d7073206c617a696c79
> B: 221fb676bda3964ad9b6c4e5166a7eba716c2d5ea1c9985b3c18b8d7faece56b
> #F: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
> #B: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
> generate proof
> (6) ..................................................
> (5) ..................................................
> (4) ..................................................
> (3) ..................................................
> (2) ..................................................
> (1) ..................................................
>
> 3) Verify the proof:
>
> $ F=ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
> $ B=166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
> $ cat keygen.txt proof.txt |
> ./test_lightning -m verify -h "$F" -b "$B" -x "$XOR"
> m: verify.
> f: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
> b: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> verify proof (6) (5) (4) (3) (2) (1)
> proof is verified
>
> 4) Verify it doesn't report a valid proof with different inputs:
>
> $ cat keygen.txt proof.txt |
> ./test_lightning -m verify -h "$B" -b "$F" -x "$XOR"
> m: verify.
> f: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
> b: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> verify proof (6) (5) (4) (3) (2)
> proof is rejected
>
> Some results:
>
> * the proof/verification key data take up about 100MB -- in theory
> one set of this data can be used by everyone; the only catch is
> that everyone has to trust that nobody has kept the original random
> numbers used to generate it.
>
> * proof/verification key data takes about a minute to generate,
> and about 650MB of RAM.
>
> * the proof data itself (which would need to be sent to the node that's
> going to switch R's) is just 864 bytes; so it'd use up about 5 hops
> worth of onion routing at 192B per hop -- in a 4096 byte packet eg,
> you could have four hops, changing R each time; or you could have 9
> hops, changing R only three times.
>
> * generating the proof data for a given R1,X pair takes about 10
> seconds, and 260MB of RAM
>
> * verifying the proof is quick-ish -- it takes 0.5s on my laptop,
> and uses about 150MB of RAM.
>
> For comparison, that last point makes a SNARK verification 500+ times
> more expensive than an ECDH operation. If I got my maths right, you
> can translate 3c for a linode CPU-hour into 2.5 satoshi for a linode
> CPU-second (at $338/BTC), so you're probably looking at a minimum fee
> of a few satoshi per SNARK verification, but that's still pretty okay
> for transactions of 500 satoshi or more, ie anything more than about a
> fifth of a US cent.
>
> The 10s proof generation time is probably more of a limitation -- though
> you could generate them in advance easily enough and just store them until
> you need to use them, which would avoid lag being a problem at least. But
> even then it's still essentially adding up to 30c of additional costs to
> your transaction (ie 10s cpu time valued at up to 3c/s), which probably
> isn't worthwhile for transactions smaller than a dollar or two.
>
> A drawback is that you'd either (a) have to do all this on the merchant's
> side (not just sending SHA(R) to whoever wants to pay you, but sending
> SHA(R1), SHA(R2), SHA(R3), SHA(R4), X12, X23, X34, and three proofs,
> which would be pretty painful; or (b) you'd have to generate all the
> R secrets as a consumer, and you wouldn't get to use the fact that you
> know R as evidence that you paid the merchant.
>
> Anyway, it's obviously not ready for prime time today: SNARKs are still
> pretty new as a concept; I'm definitely not familiar enough with SNARK
> theory to be sure I'm not misusing the concept somehow; snarkfront may not
> have implemented the theory fully correctly; and I might not have captured
> everything I needed to in order for my "proof" to actually say what I
> want it to. So not a great idea to use this to protect real money today.
>
> But still, this seems like it's not all /that/ far from being practical,
> and if the crypto's not fundamentally broken, seems like it goes a long
> way to filling in the biggest privacy hole in lightning today [3]...
>
> Code is at https://github.com/ajtowns/snarkfront/ or more directly at:
> https://github.com/ajtowns/snarkfront/blob/lightning-sha/test_lightning.cpp
>
> Cheers,
> aj
>
> [0] https://tahoe-lafs.org/trac/tahoe-lafs/wiki/SNARKs
>
> [1] https://github.com/jancarlsson/snarkfront
>
> [2] This would also improve privacy/anonymity for other applications of
> HTLCs, such as atomic swaps across chains:
>
> 1 bitcoin, payable on R1 + Alice's sig or timeout + Bob's sig
> 100 litecoin, payable on R2 + Robert's sig or timeout + Ally's sig
>
> Alice and Bob communicate privately, agreeing to trade 1 BTC for 100
> litecoin and revealing their aliases Robert and Ally; Alice generates
> R1, R2, and reveals SHA(R1), SHA(R2), R1^R2 and the SNARK proof and
> publishes the litecoin payment. Bob verifies the proof, and publishes
> the bitcoin payment. Alice claims the bitcoin payment, revealing R1;
> Bob calculates R2 and claims the litecoin payment. The swap can take
> place trustlessly because Bob knows the only way Alice can claim his
> bitcoin is by revealing enough info so he can claim the corresponding
> litecoin. But there isn't any on-chain information linking the two
> transactions, because R1 and R2 are independent (and could even be
> using different hash functions as well as different preimages).
> After the funds have been claimed, the private communication is
> also completely deniable, since anyone could generate R1^R2 and a
> corresponding SNARK proof just using the info on the blockchain.
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20151202/97972a83/attachment.html>;
đź“ť Original message:
So, it turns out that a SNARK is overkill for the application in this
thread. It was just a one-off experiment. But the performance estimates
seemed pretty far off compared to what’s reported in in the snark science
papers. So, Sean (a Zcash engineer, in his “20% fun time”) replicated the
experiment from the original post, in libsnark (not snarklib).
First, as a recap, this is the specification of the original post’s SNARK,
summarized in Camenisch-Stadler notation:
ZkPoK{ (R1, R2): H1 = sha256(R1) and H2 = sha256(R2) and R1 = R2 xor X }
In other words: given a statement H1, H2, and X, you can prove that you
know a secret witness R1, and R2, such that the predicate holds (i.e., R1
and R2 are preimages of H1,H2 and are related by X)
This is almost a complete specification of the SNARK: all that’s left is to
choose a representation size for R1 and R2…. here these are forced to be
32-byte strings.
Here are the results for a libsnark implementation of this, ordered up to
the above spec:
https://github.com/ebfull/lightning_circuit/
Most relevant benchmarks:
key generation time: 11.6270s
proof generation time: 3.0968s
verification time: 0.0270s
proof size: ~287 bytes
proving key size: ~12.85 megabytes
verifying key size: ~573 bytes
R1CS constraints: 56612 (mostly sha256-related)
The difference in proof time and proving key size (this is ~3x faster to
prove, with ~10x less key size) might be explained by libsnark having a
more efficient SHA256 implementation. The libsnark one is hand-optimized.
But I don’t have any idea why the OP and snarklib reported such large
verification keys or memory consumption during verification. The verifier
should only have to think of about a kilobyte.
On Tue, Nov 17, 2015 at 4:14 PM, Anthony Towns <aj at erisian.com.au> wrote:
> Hi all,
>
> An obvious privacy limitation with lightning is that even with onion
> routing, differents hops can be associated as being part of the same
> transaction due to sharing a common R value. So if you see a HTLC from
> Alice to Bob, paying $5 to Bob on receipt of R where SHA(R)=12345..;
> and you see another HTLC from Carol to Dave, paying $4.95 to Bob on
> receipt of R under the same condition, SHA(R)=12345..., then you know
> it's part of the same transaction.
>
> If you could change R at each step in the route, this would go away,
> improving payment anonymity and making it harder to attack the system in
> general.
>
> That's hard, because as a forwarding node, if you receive a HTLC payable
> on R1, then to send a HTLC payable on R2, you need to be able to
> calculate R1 from R2 or you'll be out of pocket. But you also can't be
> able to calculate R1 *without* R2, or you could just rip off whoever's
> making the payment. And, of course you have to know SHA(R2) to forward the
> payment at all. And if you only know SHA(R1) and SHA(R2) it's hard to
> say anything at all about R1 and R2 because cryptographic hash functions
> are designed to make any structural relationships go away.
>
> BUT! I think the magic of SNARKs [0] lets you do this!
>
> With a SNARK, you can "prove" that you have some secrets (ie, R1 and R2)
> that satisfy some programmable condition (ie, SHA(R1)=H1 and SHA(R2)=H2
> and R1=R2 XOR X), based on public inputs (H1, H2 and X), without revealing
> those secrets.
>
> I think that's pretty safe, because if you receive an HTLC asking for a
> preimage for H1, along with instructions in the onion saying ask Bob for
> a preimage for H2, and here's X and a proof, then either:
>
> - your forwarded HTLC will fail, and everything's fine
>
> - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1)=H1 as
> expected, and everything's fine
>
> - you'll receive R2, calculate R1=R2 XOR X and see SHA(R1) != H1,
> which is only possible if the cryptography behind SNARKs are broken
>
> - you'll receive RX, such that H2=SHA(RX) but RX being too
> long or too short. If SNARKs aren't broken, this means that you know
> R2alt and someone else knows R2 that are different but hash to the
> same value, meaning SHA has been broken.
>
> It seems like there are research-level tools out there that actually
> make this practical to try out. I've had a go at implementing this using
> snarkfront [1]. Using it looks like:
>
> 1) initial setup of proof/verification keys
>
> $ ./test_lightning -m keygen > keygen.txt # global setup
>
> 2) generate a proof, using a 32 byte secret, and XOR key (64 hex digits)
>
> $ SECRET="the quick brown fox jumps lazily"
> $ XOR=$(echo "she sells sea shells" | sha256sum | head -c64)
> $ cat keygen.txt |
> ./test_lightning -m proof -s "$SECRET" -x "$XOR" > proof.txt
> m: proof.
> f: .
> b: .
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> F: 74686520717569636b2062726f776e20666f78206a756d7073206c617a696c79
> B: 221fb676bda3964ad9b6c4e5166a7eba716c2d5ea1c9985b3c18b8d7faece56b
> #F: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
> #B: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
> generate proof
> (6) ..................................................
> (5) ..................................................
> (4) ..................................................
> (3) ..................................................
> (2) ..................................................
> (1) ..................................................
>
> 3) Verify the proof:
>
> $ F=ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85
> $ B=166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245
> $ cat keygen.txt proof.txt |
> ./test_lightning -m verify -h "$F" -b "$B" -x "$XOR"
> m: verify.
> f: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
> b: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> verify proof (6) (5) (4) (3) (2) (1)
> proof is verified
>
> 4) Verify it doesn't report a valid proof with different inputs:
>
> $ cat keygen.txt proof.txt |
> ./test_lightning -m verify -h "$B" -b "$F" -x "$XOR"
> m: verify.
> f: 166e4f9b8ec5895e870f0f0508327d73ba9ad9af4e9841599bafb1bf55c8a245.
> b: ae4d48f71fdb6f74149fab591e88f2cc07d4e696968def1aa7ca1e07096c5b85.
> x: 5677d356ccd6ff29b296a697791d109a1703557ecbbcf52b4f38d4b680858912.
> verify proof (6) (5) (4) (3) (2)
> proof is rejected
>
> Some results:
>
> * the proof/verification key data take up about 100MB -- in theory
> one set of this data can be used by everyone; the only catch is
> that everyone has to trust that nobody has kept the original random
> numbers used to generate it.
>
> * proof/verification key data takes about a minute to generate,
> and about 650MB of RAM.
>
> * the proof data itself (which would need to be sent to the node that's
> going to switch R's) is just 864 bytes; so it'd use up about 5 hops
> worth of onion routing at 192B per hop -- in a 4096 byte packet eg,
> you could have four hops, changing R each time; or you could have 9
> hops, changing R only three times.
>
> * generating the proof data for a given R1,X pair takes about 10
> seconds, and 260MB of RAM
>
> * verifying the proof is quick-ish -- it takes 0.5s on my laptop,
> and uses about 150MB of RAM.
>
> For comparison, that last point makes a SNARK verification 500+ times
> more expensive than an ECDH operation. If I got my maths right, you
> can translate 3c for a linode CPU-hour into 2.5 satoshi for a linode
> CPU-second (at $338/BTC), so you're probably looking at a minimum fee
> of a few satoshi per SNARK verification, but that's still pretty okay
> for transactions of 500 satoshi or more, ie anything more than about a
> fifth of a US cent.
>
> The 10s proof generation time is probably more of a limitation -- though
> you could generate them in advance easily enough and just store them until
> you need to use them, which would avoid lag being a problem at least. But
> even then it's still essentially adding up to 30c of additional costs to
> your transaction (ie 10s cpu time valued at up to 3c/s), which probably
> isn't worthwhile for transactions smaller than a dollar or two.
>
> A drawback is that you'd either (a) have to do all this on the merchant's
> side (not just sending SHA(R) to whoever wants to pay you, but sending
> SHA(R1), SHA(R2), SHA(R3), SHA(R4), X12, X23, X34, and three proofs,
> which would be pretty painful; or (b) you'd have to generate all the
> R secrets as a consumer, and you wouldn't get to use the fact that you
> know R as evidence that you paid the merchant.
>
> Anyway, it's obviously not ready for prime time today: SNARKs are still
> pretty new as a concept; I'm definitely not familiar enough with SNARK
> theory to be sure I'm not misusing the concept somehow; snarkfront may not
> have implemented the theory fully correctly; and I might not have captured
> everything I needed to in order for my "proof" to actually say what I
> want it to. So not a great idea to use this to protect real money today.
>
> But still, this seems like it's not all /that/ far from being practical,
> and if the crypto's not fundamentally broken, seems like it goes a long
> way to filling in the biggest privacy hole in lightning today [3]...
>
> Code is at https://github.com/ajtowns/snarkfront/ or more directly at:
> https://github.com/ajtowns/snarkfront/blob/lightning-sha/test_lightning.cpp
>
> Cheers,
> aj
>
> [0] https://tahoe-lafs.org/trac/tahoe-lafs/wiki/SNARKs
>
> [1] https://github.com/jancarlsson/snarkfront
>
> [2] This would also improve privacy/anonymity for other applications of
> HTLCs, such as atomic swaps across chains:
>
> 1 bitcoin, payable on R1 + Alice's sig or timeout + Bob's sig
> 100 litecoin, payable on R2 + Robert's sig or timeout + Ally's sig
>
> Alice and Bob communicate privately, agreeing to trade 1 BTC for 100
> litecoin and revealing their aliases Robert and Ally; Alice generates
> R1, R2, and reveals SHA(R1), SHA(R2), R1^R2 and the SNARK proof and
> publishes the litecoin payment. Bob verifies the proof, and publishes
> the bitcoin payment. Alice claims the bitcoin payment, revealing R1;
> Bob calculates R2 and claims the litecoin payment. The swap can take
> place trustlessly because Bob knows the only way Alice can claim his
> bitcoin is by revealing enough info so he can claim the corresponding
> litecoin. But there isn't any on-chain information linking the two
> transactions, because R1 and R2 are independent (and could even be
> using different hash functions as well as different preimages).
> After the funds have been claimed, the private communication is
> also completely deniable, since anyone could generate R1^R2 and a
> corresponding SNARK proof just using the info on the blockchain.
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20151202/97972a83/attachment.html>;