<div dir="ltr">FWIW, Conner pointed out that the initial ZK Proof for the correctness of the <div>Paillier params (even w/ usage of bulletproofs) has multiple rounds of interaction, </div><div>iirc up to 5+ (with additional pipelining) rounds of interaction.</div><div><br></div><div>-- Laolu</div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, May 7, 2018 at 5:14 PM Olaoluwa Osuntokun <<a href="mailto:laolu32@gmail.com">laolu32@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Actually, just thought about this a bit more and I think it's possible to</div><div>deploy this in unison with (or after) any sort of SS based on schnorr becomes</div><div>possible in Bitcoin. My observation is that since both techniques are based on</div><div>the same underlying technique (revealing a secret value in a signature) and</div><div>they center around leveraging the onion payload to drop off a payment point</div><div>(G*a, or G*a_1*a_2*a_3, etc), then the disclosure within the _links_ can be</div><div>heterogeneous, as the same secret is still revealed in an end-to-end matter.</div><div><br></div><div>As an illustration, consider: A <-> B <-> C. The A <-> B link could use the 2pc</div><div>pailier technique, while the B <-> C link could use the OG SS technique based</div><div>on schnorr. If i'm correct, then this would mean that we can deploy both</div><div>techniques, without worrying about fragmenting the network due to the existence</div><div>of two similar but incompatible e2e payment routing schemes! </div><div><br></div><div>-- Laolu</div></div><div dir="ltr"><div><br></div><br><div class="gmail_quote"><div dir="ltr">On Mon, May 7, 2018 at 4:57 PM Olaoluwa Osuntokun <<a href="mailto:laolu32@gmail.com" target="_blank">laolu32@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>Hi Pedro, </div><div><br></div><div>Very cool stuff! When I originally discovered the Lindell's technique, my</div><div>immediate thought was the we could phase this in as a way to _immediately_ (no</div><div>additional Script upgrades required), replace the regular 2-of-2 mulit-sig with</div><div>a single p2wkh. The immediate advantages of this would: be lower fees for</div><div>opening/closing channels (as the public key script, and witness are smaller),</div><div>openings and cooperative close transactions would blend in with the anonymity</div><div>set of regular p2wkh transactions, and finally the htlc timeout+success</div><div>transactions can be made smaller as we can remove the multi-sig. The second</div><div>benefit is nerfed a bit if the channel are advertised, but non-advertised</div><div>channels would be able to take advantage of this "stealth" feature.</div><div><br></div><div>The upside of the original application I hand in mind is that it wouldn't</div><div>require any end-to-end changes, as it would only be a link level change (diff</div><div>output for the funding transaction). If we wanted to allow these styles of</div><div>channels to be used outside of non-advertised channels, then we would need to</div><div>update the way channels are verified in the gossip layer.</div><div><br></div><div>Applying this to the realm of allowing us to use randomized payment identifiers</div><div>across the route is obviously much, much doper. So then the question would be</div><div>what the process of integrating the scheme into the existing protocol would</div><div>look like. The primary thing we'd need to account for is the additional</div><div>cryptographic overhead this scheme would add if integrated. Re-reviewing the</div><div>paper, there's an initial setup and verification phase (which was omitted from</div><div>y'alls note for brevity) where both parties need to complete before the</div><div>actually signing process can take place. Ideally, we can piggy-back this setup</div><div>on top of the existing accept_channel/open_channel dance both sides need to go</div><div>through in order to advance the channel negotiation process today. </div><div><br></div><div>Conner actually started to implement this when we first discovered the scheme,</div><div>so we have a pretty good feel w.r.t the implementation of the initial set of</div><div>proofs. The three proofs required for the set up phase are:</div><div><br></div><div> 1. A proof that that the Paillier public key is well formed. In the paper</div><div> they only execute this step for the party that wishes to _obtain_ the</div><div> signature. In our case, since we'll need to sign for HTLCs in both</div><div> directions, but parties will need to execute this step.</div><div><br></div><div> 2. A dlog proof for the signing keys themselves. We already do this more or</div><div> less, as if the remote party isn't able to sign with their target key, then</div><div> we won't be able to update the channel, or even create a valid commitment in</div><div> the first place.</div><div><br></div><div> 3. A proof that value encrypted (the Paillier ciphertext) is actually the</div><div> dlog of the public key to be used for signing. (as an aside this is the part</div><div> of the protocol that made me do a double take when first reading it: using one</div><div> cryptosystem to encrypt the private key of another cryptosystem in order to</div><div> construct a 2pc to allow signing in the latter cryptosystem! soo clever!)</div><div><br></div><div>First, we'll examine the initial proof. This only needs to be done once by both</div><div>parties AFAICT. As a result, we may be able to piggyback this onto the initial</div><div>channel funding steps. Reviewing the paper cited on the Lindell paper [1], it</div><div>appears this would take 1 RTT, so this shouldn't result in any additional round</div><div>trips during the funding process. We should be able to use a Paillier modulos</div><div>of 2048 bits, so nothing too crazy. This would just result in a slightly bigger</div><div>opening message.</div><div><br></div><div>Skipping the second proofs as it's pretty standard.</div><div><br></div><div>The third proof as described (Section 6 of the Lindell paper) is interactive.</div><div>It also contains a ZK range proof as a sub-protocol which as described in</div><div>Appendix A is also interactive. However, it was pointed out to us by Omer</div><div>Shlomovits on the lnd slack, that we can actually replace their custom range</div><div>proofs with Bulletproofs. This would make this section non-interactive,</div><div>allowing the proof itself to take 1.5 RTT AFAICT. Additionally, this would only</div><div>need to be done once at the start, as AFIACT, we can re-use the encryption of</div><div>the secp256k1 private key of both parties.</div><div><br></div><div>The current channel opening process requires 2 RTT, so it seems that we'd be</div><div>able to easily piggy back all the opening proofs on top of the existing funding</div><div>protocol. The main cost would be the increased size of these opening messages,</div><div>and also the additional computational cost of operations within the Paillier</div><div>modulus and the new range proof.</div><div><br></div><div>The additional components that would need to be modified are the process of</div><div>adding+settling an HTLC, and also the onion payload that drops off the point</div><div>whose dlog is r_1*alpha. Within the current protocol, adding and settling an</div><div>HTLC are more or less non-interactive, we have a single message for each, which</div><div>is then staged to be committed in new commitments for both parties. With this</div><div>new scheme (if I follow it correctly), adding an HTLC now requires N RTT:</div><div> 1. Alice sends A = G*alpha to Bob. Here alpha is the payment secret.</div><div> 2. Bob sends R_3 = (G*alpha)*r_2 (along w/ a proof of knowledge of r_2 and</div><div> relation to A)</div><div> 3. Alice sends R_3' = (G*alpha)*r_3 (along with a similar proof as above) 4.</div><div> Bob then computes c3 (the encrypted partial sig which when completed will</div><div> reveal a) to Alice.</div><div> 5. Alice decrypts c3 to get the plaintext partial sig (s'), then finalizes</div><div> the set up by sending s'' to Bob.</div><div><br></div><div>This process takes 2.5 RTT, and would require re-working the state machine</div><div>slightly to only actually commit an HTLC after step 5 has been completed. When</div><div>Bob obtains a from the next party in the path, we Alice can then then over the</div><div>signature, from which Alice can extract alpha. So adding HTLCs is now a bit</div><div>more interactive, but settling them is the same a before.</div><div><br></div><div>Finally, the onion payload would need to be re-interpreted in order to encode</div><div>G*alpha which takes 33 bytes. We can shave this down to 32 by selecting the x</div><div>coordinate (at the sender) to always be either even or odd. Currently, we have</div><div>12 unused bytes in the onion payload. The HMAC is currently 32 bytes. One path</div><div>would be to allocate a portion of HMAC space to encoding this point. A 16-byte</div><div>HMAC would probably have been enough in the beginning, so we can drop down to</div><div>that. However, that still leaves 4 bytes somewhere that has to give...one could</div><div>either obtain these extra bytes from the CLTV and Amount fields, or just have</div><div>each hop consume an extra payload. The latter path would mean that the new</div><div>upper hop limit is actually 10. </div><div><br></div><div>However, given that we would need need a new global feature bit in order to</div><div>roll this out, it may make sense to re-work the onion format all together which</div><div>would mean that we wouldn't need to hack the old format a bit to accommodate</div><div>this additional data. One aspect of introducing a new end-to-end contract type</div><div>which I hadn't considered before is that each new type effectively partitions</div><div>the network. This is due to the fact that these HTLCs will now only be able to</div><div>be carried along paths that understand this new feature. As a result, plausible</div><div>path diversity takes as we can no longer utilize all channels on the network</div><div>for routing. This would suggest that introducing new end to end contract types</div><div>(if one wishes to use them widely across arbitrary channels and not for</div><div>specific contract protocols) may be a strong point of synchronization w.r.t</div><div>updates across the network. As a result, we may need to be a bit more</div><div>discerning w.r.t new candidates for e2e contracts given the coordination costs.</div><div><br></div><div>So the takeaways are:</div><div> * we can probably piggy back the extra proofs onto the channel opening</div><div> process</div><div> * one of the subproofs can use bulletproofs to make the proof shorter and</div><div> also non-interactive</div><div> * adding an HTLC would take 2.5 RTT's, but settling is just as quick as</div><div> before</div><div> * the onion payload would either need to be hacked, or extended to support</div><div> packaging the point.</div><div> * the utility of the scheme won't shine until all/most of the network uses it</div><div> * we could start w/ just the introduction of the OG 2PC scheme as a multi-sig</div><div> replacement</div><div><br></div><div><br></div><div>[1]: <a href="https://eprint.iacr.org/2011/494.pdf" target="_blank">https://eprint.iacr.org/2011/494.pdf</a> (section 3.3)</div><div><br></div><div>-- Laolu</div></div><div><br></div><br></div><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Fri, Apr 27, 2018 at 11:42 AM Pedro Moreno Sanchez <<a href="mailto:pmorenos@purdue.edu" target="_blank">pmorenos@purdue.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello guys,<br>
<br>
as some of you already know, I am working on some cryptographic<br>
constructions that might be of interest and useful for the Lightning<br>
Network.<br>
<br>
Recently, I have come up with a scriptless version of the adaptor<br>
signatures and the contract required in the Lighting Network using only<br>
2-party ECDSA signatures. The main advantage is that, instead of waiting<br>
for Schnorr signatures to be deployed in Bitcoin so that Poelstra's<br>
scriptless scripts can be used, I believe that this ECDSA-version of the<br>
scriptless scripts can be directly applied today.<br>
<br>
Details are in the attached PDF. I am looking forward to hearing your<br>
comments and suggestions.<br>
<br>
Cheers,<br>
Pedro.<br>
<br>
_______________________________________________<br>
Lightning-dev mailing list<br>
<a href="mailto:Lightning-dev@lists.linuxfoundation.org" target="_blank">Lightning-dev@lists.linuxfoundation.org</a><br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev</a><br>
</blockquote></div></div></blockquote></div></div></blockquote></div>