From amiller at cs.umd.edu Wed Dec 2 12:40:43 2015 From: amiller at cs.umd.edu (Andrew Miller) Date: Wed, 2 Dec 2015 07:40:43 -0500 Subject: [Lightning-dev] Better privacy with SNARKs In-Reply-To: <20151117211436.GA17583@debian> References: <20151117211436.GA17583@debian> Message-ID: 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 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: