Re: [Lightning-dev] Selling timestamps (via payment points and scalars + Pedersen commitments ) [try2]
This is a nice scheme. Pedersen commitments + pay to point seems to be the most practical way to do it but you can generalise this paying for a decommitment idea to any commitment scheme. For example, you could do this in a payment channel with hashes if we had something like OP_CAT. e.g HTLC unlocks based on whether you can provide an r such that H(r || x) == C. > Unfortunately that zkp already proves that C was generated based on x, so you get your timestamp for free. Ooops. :( I haven't studied zkp for circuits in general but I guess the non-interactive proofs are fiat-shamir transformations of an interactive protocol. Maybe you could just use the interactive zero knowledge protocol which doesn't have the side effect of the verifier with a proof they can give to others. LL On Thu, Sep 26, 2019 at 5:30 AM Anthony Towns wrote: > On Wed, Sep 25, 2019 at 01:30:39PM +, ZmnSCPxj wrote: > > > Since it's off chain, you could also provide R and C and a zero > knowledge > > > proof that you know an r such that: > > > R = SHA256( r ) > > > C = SHA256( x || r ) > > > > in which case you could do it with lightning as it exists today. > > I can insist on paying only if the server reveals an `r` that matches > some known `R` such that `R = SHA256(r)`, as currently in Lightning network. > > However, how would I prove, knowing only `R` and `x`, and that there > exists some `r` such that `R = SHA256(r)`, that `C = SHA256(x || r)`? > > If you know x and r, you can generate C and R and a zero knowledge proof > of the relationship between x,C,R that doesn't reveal r (eg, I think > you could do that with bulletproofs). Unfortunately that zkp already > proves that C was generated based on x, so you get your timestamp for > free. Ooops. :( > > Cheers, > aj > > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Selling timestamps (via payment points and scalars + Pedersen commitments ) [try2]
Good morning aj, > On Wed, Sep 25, 2019 at 01:30:39PM +, ZmnSCPxj wrote: > > > > Since it's off chain, you could also provide R and C and a zero knowledge > > > proof that you know an r such that: > > > R = SHA256( r ) > > > C = SHA256( x || r ) > > > > in which case you could do it with lightning as it exists today. > > > I can insist on paying only if the server reveals an `r` that matches > > > some known `R` such that `R = SHA256(r)`, as currently in Lightning > > > network. > > > However, how would I prove, knowing only `R` and `x`, and that there > > > exists some `r` such that `R = SHA256(r)`, that `C = SHA256(x || r)`? > > If you know x and r, you can generate C and R and a zero knowledge proof > of the relationship between x,C,R that doesn't reveal r (eg, I think > you could do that with bulletproofs). Ah, yes, a generic zkp should work indeed. > Unfortunately that zkp already > proves that C was generated based on x, so you get your timestamp for > free. Ooops. :( Yes, the "existence-proof-of-a-proof-of-X is a proof-of-X". Perhaps relevant? http://stevengoldfeder.com/papers/ZKCSP.pdf Lightning payments are essentially zero-knowledge contingent payments already. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Selling timestamps (via payment points and scalars + Pedersen commitments ) [try2]
On Wed, Sep 25, 2019 at 01:30:39PM +, ZmnSCPxj wrote: > > Since it's off chain, you could also provide R and C and a zero knowledge > > proof that you know an r such that: > > R = SHA256( r ) > > C = SHA256( x || r ) > > in which case you could do it with lightning as it exists today. > I can insist on paying only if the server reveals an `r` that matches some > known `R` such that `R = SHA256(r)`, as currently in Lightning network. > However, how would I prove, knowing only `R` and `x`, and that there exists > some `r` such that `R = SHA256(r)`, that `C = SHA256(x || r)`? If you know x and r, you can generate C and R and a zero knowledge proof of the relationship between x,C,R that doesn't reveal r (eg, I think you could do that with bulletproofs). Unfortunately that zkp already proves that C was generated based on x, so you get your timestamp for free. Ooops. :( Cheers, aj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Selling timestamps (via payment points and scalars + Pedersen commitments ) [try2]
Good morning aj, and list, > > Solution: buy a place in a merkle tree "risk-free" > > > > 1. send hash x of my message (or the merkle root of another tree) to the > > timstamping server > > > > 2. server calculates Pedersen commit: C = xH + rG, hashes it, builds merkle > > tree with other commits in it and publishes a valid transaction > > containing the > > merkle root to the Bitcoin blockchain > > > > 3. after a certain number of block confirmations and with the given proof > > I can > > confirm that the commitment C is indeed part of the Bitcoin blockchain > > > > 4. I now have to send a lightning payment with C - xH = rG as the payment > > point to the timestamping server and as a proof of payment the > > server must > > reveal r to receive the money. > > > > Nice. I agree. This is quite correct for its needs, and kudos to Konstantin for deriving this. Do note that Lightning today does not yet support payment points / scalars, only payment hashes / preimages. In particular the client might induce the server to "waste" a slot on committing some information onchain, but the client will still not be able to get a commitment "for free" as it cannot know the blinding key for the commitment. That is, the client can DoS the server and have it make commitments without getting paid, wasting the server capacity, but the client would not be able to prove the commitment does commit to its message without paying. This can be avoided with aj suggestion of "floating" and "subscriber" clients. I would have personally used sign-to-contract onchain directly myself for such "rare" operations, but aggregation certainly has its efficiency benefits and this is still useful. So far it seems, we can use EC magic (payment point / scalar) to: * Prevent route correlation especially for multipath payments. * Allow pay-for-signature. * Allow pay-for-pedersen-commitment (this thread). * Support multiple parallel payments ("stuckless"). * Support noncustodial Lightning escrow. * Probably some other things I have forgotten. > > Since it's off chain, you could also provide R and C and a zero knowledge > proof that you know an r such that: > > R = SHA256( r ) > C = SHA256( x || r ) > > in which case you could do it with lightning as it exists today. I can insist on paying only if the server reveals an `r` that matches some known `R` such that `R = SHA256(r)`, as currently in Lightning network. However, how would I prove, knowing only `R` and `x`, and that there exists some `r` such that `R = SHA256(r)`, that `C = SHA256(x || r)`? I am curious about this operation, as this is beyond what little I know of cryptography. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Selling timestamps (via payment points and scalars + Pedersen commitments ) [try2]
On Wed, Sep 25, 2019 at 11:01:28AM +0200, Konstantin Ketterer wrote: > Motivation: If I had to timestamp multiple messages I could simply aggregate > them in a merkle tree and pay relatively low fees per message. However, if I > only need to timestamp something once in a while I need to rely on free > services or pay high fees. Maybe model the timestamping service as having fixed and floating users, in which case the fixed users pay a subscription fee that covers the costs and get placed relatively high in the merkle tree, while the floating users are placed low in the merkle tree and are basically free money? Your merkle tree might then have 2**N-1 fixed slots, all at height N, then 2**K floating slots, all at height N+K, but you don't need to charge the floating slots anything up front, because your fixed costs are all paid for by subscription income from the fixed slots. You might still want to charge some up front fee to prevent people spamming you with things to timestamp that they're never going to pay for though. > Solution: buy a place in a merkle tree "risk-free" > 1. send hash x of my message (or the merkle root of another tree) to the > timstamping server > 2. server calculates Pedersen commit: C = x*H + r*G, hashes it, builds merkle > tree with other commits in it and publishes a valid transaction containing the > merkle root to the Bitcoin blockchain > 3. after a certain number of block confirmations and with the given proof I > can > confirm that the commitment C is indeed part of the Bitcoin blockchain > 4. I now have to send a lightning payment with C - x*H = r*G as the payment > point to the timestamping server and as a proof of payment the server must > reveal r to receive the money. Nice. Since it's off chain, you could also provide R and C and a zero knowledge proof that you know an r such that: R = SHA256( r ) C = SHA256( x || r ) in which case you could do it with lightning as it exists today. Cheers, aj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
[Lightning-dev] Selling timestamps (via payment points and scalars + Pedersen commitments ) [try2]
*Disclaimer*: I have just finished Highschool and I'm only learning a bit in my free time.This may be fundamentally broken ;) *Motivation*: If I had to timestamp multiple messages I could simply aggregate them in a merkle tree and pay relatively low fees per message. However, if I only need to timestamp something once in a while I need to rely on free services or pay high fees. *Solution*: buy a place in a merkle tree "risk-free" 1. send hash x of my message (or the merkle root of another tree) to the timstamping server 2. server calculates Pedersen commit: C = x*H + r*G, hashes it, builds merkle tree with other commits in it and publishes a valid transaction containing the merkle root to the Bitcoin blockchain 3. after a certain number of block confirmations and with the given proof I can confirm that the commitment C is indeed part of the Bitcoin blockchain 4. I now have to send a lightning payment with C - x*H = r*G as the payment point to the timestamping server and as a proof of payment the server must reveal r to receive the money. --> With both r and x I have a valid Pedersen commitment. This introduces an additional security assumption to Bitcoin timestamps but if the discrete logarithm is broken Bitcoin has bigger problems than broken timestamps. *Conclusion* This scheme essentially shifts the risk of a timestamping service from the buyer to the seller who now has to pay the onchain transaction fee upfront. Hence, the seller will most likely charge a small fee upfront just like some submarineswap providers do. Regards Konstantin Ketterer ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev