Olaoluwa Osuntokun [ARCHIVE] on Nostr: 📅 Original date posted:2018-05-08 📝 Original message: FWIW, Conner pointed out ...

📅 Original date posted:2018-05-08
📝 Original message:
FWIW, Conner pointed out that the initial ZK Proof for the correctness of
the
Paillier params (even w/ usage of bulletproofs) has multiple rounds of
interaction,
iirc up to 5+ (with additional pipelining) rounds of interaction.

-- Laolu

On Mon, May 7, 2018 at 5:14 PM Olaoluwa Osuntokun <laolu32 at gmail.com> wrote:

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