Re: [bitcoin-dev] Statechain implementations
Good morning Ruben, > Hey Christian, > > Thanks for chiming in :) > > >It might be worth adopting the late fee binding we have in eltoo > > That is where my thinking originally went as well, but then I remembered that > this alters the txid, causing the settlement tx to become invalid. What I am > suggesting should be functionally the same (albeit less space-efficient): a > secondary output that can be spent by anyone, which can be used to fee bump > the kickoff tx with CPFP. I believe this same idea was considered for > Lightning as well at some point. Do you happen to recall if there was some > kind of non-standardness issue with it? Any standardness issue can be fixed by embedding it in a P2WSH / P2SH, you can use an `OP_TRUE` `redeemScript`, for instance. Using an `OP_TRUE` `redeemScript` would allow any third party to make you cry by opportunistically spending such an output. For example your Bitcoin-network peer could notice you broadcasting such a transaction with an `OP_TRUE` output, see you spend that output with a CPFP-RBF-ed child transaction, then instead of further broadcasting the child transaction, instead broadcast a non-RBF child transaction with tiny fee, so that it and its parent transaction will be accepted into mempools but would not be replaceable with a higher-feerate child transaction (because not RBF-flagged). Thus, some portion of mempools will contain this poisoned low-fee child transaction and prevent the parent from being confirmed (because the parent+child fees are not enough to justify being put in a block). Which I suppose is an argument for Full RBF aka ignore-the-RBF-flag-and-always-RBF. The solution that I remember being proposed for this in Lightning was to give each participant its own attach-your-fees output that only that participant can spend, which works for Lightning because the set of participants in a channel is permanently fixed, but probably not for statechains. -- The broadcasting of the kickoff simply means that the first stage cannot be easily changed, and you might still be able to make further updates by updating only the later stages, until the last stage is confirmable, so the kickoff being broadcast simply creates a "dead man walking" statechain. However, the implementation complexity would probably increase tremendously. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Statechain implementations
Hey Christian, Thanks for chiming in :) >It might be worth adopting the late fee binding we have in eltoo That is where my thinking originally went as well, but then I remembered that this alters the txid, causing the settlement tx to become invalid. What I am suggesting should be functionally the same (albeit less space-efficient): a secondary output that can be spent by anyone, which can be used to fee bump the kickoff tx with CPFP. I believe this same idea was considered for Lightning as well at some point. Do you happen to recall if there was some kind of non-standardness issue with it? >Wouldn't that result in a changing pubkey at each update, and thus require an onchain move to be committed? I have yet to take a closer look at the math, but my understanding is that the same key (x) gets redistributed. First x = s1 + o1 and after the transfer x = s2 + o2 (not the actual math, but it demonstrates how the transitory key can change from o1 to o2). Assuming s1 is then thrown away (trust assumption), o1 becomes harmless information. Cheers, Ruben On Thu, Mar 26, 2020 at 6:17 PM Greg Sanders wrote: > > Wouldn't that result in a changing pubkey at each update, and thus > require an onchain move to be committed? > > Suggestion was in line with original proposal where no keys are changing > ever, just not presupposing existence of MuSig. > > On Thu, Mar 26, 2020 at 1:15 PM Christian Decker via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Ruben Somsen via bitcoin-dev >> writes: >> > Regarding modification 1, I agree with ZmnSCPxj that >> > Decker-Wattenhofer is your next best option, given that eltoo is not >> > yet available. But if you are going to use a kickoff transaction, keep >> > in mind that every previous owner will have a copy of it. Because of >> > this, you can't include a fee, and will instead need to have a second >> > output for CPFP. This way a previous owner will at least have to pay >> > the fee if they want to publish it. Note that it's still an >> > improvement, because even if the kickoff transaction gets posted, it >> > basically becomes no different than what it would have been, had you >> > not used a kickoff transaction at all. >> >> It might be worth adopting the late fee binding we have in eltoo by >> having the kickoff transaction input spending the funding tx signed with >> sighash_single. This works because we only have 1 input and 1 output >> that we really care about, and can allow others to attach fees at >> will. That'd at least remove the need to guess the feerate days or >> months in advance and thus having to overestimate. >> >> > Regarding modification 2, I like it a lot conceptually. It hadn't >> > occurred to me before, and it's a clear security improvement. The only >> > question is something Greg Sanders mentioned: whether it's enough to >> > justify the added complexity of using 2P ECDSA. The alternative would >> > be to simply use a regular 2-of-2 multisig (until Schnorr arrives, >> > possibly). >> >> Wouldn't that result in a changing pubkey at each update, and thus >> require an onchain move to be committed? >> >> > I'm looking forward to seeing statechains become a reality. >> >> That'd indeed be great :-) >> >> Cheers, >> Christian >> ___ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Statechain implementations
> Wouldn't that result in a changing pubkey at each update, and thus require an onchain move to be committed? Suggestion was in line with original proposal where no keys are changing ever, just not presupposing existence of MuSig. On Thu, Mar 26, 2020 at 1:15 PM Christian Decker via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Ruben Somsen via bitcoin-dev > writes: > > Regarding modification 1, I agree with ZmnSCPxj that > > Decker-Wattenhofer is your next best option, given that eltoo is not > > yet available. But if you are going to use a kickoff transaction, keep > > in mind that every previous owner will have a copy of it. Because of > > this, you can't include a fee, and will instead need to have a second > > output for CPFP. This way a previous owner will at least have to pay > > the fee if they want to publish it. Note that it's still an > > improvement, because even if the kickoff transaction gets posted, it > > basically becomes no different than what it would have been, had you > > not used a kickoff transaction at all. > > It might be worth adopting the late fee binding we have in eltoo by > having the kickoff transaction input spending the funding tx signed with > sighash_single. This works because we only have 1 input and 1 output > that we really care about, and can allow others to attach fees at > will. That'd at least remove the need to guess the feerate days or > months in advance and thus having to overestimate. > > > Regarding modification 2, I like it a lot conceptually. It hadn't > > occurred to me before, and it's a clear security improvement. The only > > question is something Greg Sanders mentioned: whether it's enough to > > justify the added complexity of using 2P ECDSA. The alternative would > > be to simply use a regular 2-of-2 multisig (until Schnorr arrives, > > possibly). > > Wouldn't that result in a changing pubkey at each update, and thus > require an onchain move to be committed? > > > I'm looking forward to seeing statechains become a reality. > > That'd indeed be great :-) > > Cheers, > Christian > ___ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Statechain implementations
Ruben Somsen via bitcoin-dev writes: > Regarding modification 1, I agree with ZmnSCPxj that > Decker-Wattenhofer is your next best option, given that eltoo is not > yet available. But if you are going to use a kickoff transaction, keep > in mind that every previous owner will have a copy of it. Because of > this, you can't include a fee, and will instead need to have a second > output for CPFP. This way a previous owner will at least have to pay > the fee if they want to publish it. Note that it's still an > improvement, because even if the kickoff transaction gets posted, it > basically becomes no different than what it would have been, had you > not used a kickoff transaction at all. It might be worth adopting the late fee binding we have in eltoo by having the kickoff transaction input spending the funding tx signed with sighash_single. This works because we only have 1 input and 1 output that we really care about, and can allow others to attach fees at will. That'd at least remove the need to guess the feerate days or months in advance and thus having to overestimate. > Regarding modification 2, I like it a lot conceptually. It hadn't > occurred to me before, and it's a clear security improvement. The only > question is something Greg Sanders mentioned: whether it's enough to > justify the added complexity of using 2P ECDSA. The alternative would > be to simply use a regular 2-of-2 multisig (until Schnorr arrives, > possibly). Wouldn't that result in a changing pubkey at each update, and thus require an onchain move to be committed? > I'm looking forward to seeing statechains become a reality. That'd indeed be great :-) Cheers, Christian ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Statechain implementations
Very good point, but I think this is easy to fix. It's not actually necessary that the quantity in (b) involve the SE's secret key s1. It can be purely the blinding factor. This quantity gets relayed through the SE anyway, after a round trip through owner 2, where the SE removes the blinding nonce. The SE needs to determine the ratio of the two private keys o1*o2_inv. There's no reason for the SE to send anything about s1 other than the public keys S1=s1.G and S2=s2.G, keeping the secret keys s1 and s2 hidden behind ECDLP and not sharing quantities involving them in Z_p. Thus: b. (SE) x -> (2) c. (2) o2_inv*x -> (1) d. (1) o1*(o2_inv*x) -> (SE) e. (SE) s2 = x_inv*(o1*o2_inv*x)*s1 = o1*o2_inv*s1 s2.G -> (2) f. (2) o2.s2.G = o1.s1.G = P Now we could have had a different problem, in step (e) if the SE sends owner 2 the quantity o1*o2_inv*s1, a self-sending owner can determine a similar quantity to what you described (x1+x2)*s1: (o1*o2_inv + o2*o3_inv)*s1 and we're back to an Irwin-Hall distribution. It's not necessary to send a quantity involving s1 in steps (b-e). Owner 2 already has his private key o2 and the SE has his new private key s2=o1*o2_inv*s1. Since P=o1.s1.G=o2.s2.G we're set up for o2 to transfer the funds, but it's necessary to prove to (2) that his o2 does in fact control the UTXO. This can be done by sending (2) the public key S2=s2.G which he can multiply by o2 to get P=o2.s2.G and verify that the SE does have the correct private key corresponding to his o2 for the public key P recorded on-chain. Thus in the self-send situation, the owner no longer has any algebraic relations he can use as you describe. Algebraic relations remain in step (d) that a self-sending owner could use, but they all involve his own private keys, which he knows anyway. He has only one relation from the previous owner and all subsequent relations do not involve that owner. However if a pair of entities send funds back and forth, each owner could collect a sum as you describe, if the counterparty (2) re-uses keys: o2_inv*(x1 + x2) The SE has similar relations in step (e) if there's key reuse. Therefore it's important that on each transfer, you generate a new key and do not re-use keys. A responsible SE could detect a key-reuse situation by e.g. recording old pubkeys P1, P2 even though he deleted s1 and s2, and inform the user of the key-reuse error and abort. Do you think that works? P.S. SGX is not "trust minimization", it's "trust transfer" -- specifically to the keys managing the SGX. If we thought processor manufacturers were better at key management than the rest of us, we should just hand them the task. I don't think that's the case, and I don't think anyone else does either. An SGX attestation as an optional add-on I think is a worthwhile enhancement, as long as it's not on the critical path of the protocol. Albert via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wrote: > Hi, > > Great to see some work in this direction, here's some thoughts on your keygen > scheme: > > In the scenario where Owner1=Owner2, that is, one of the owners sends some > coins to itself, that owner would get to know both x1*s1 and x2*s2= > x2*s1*o2_inv*o1, and, because he already knows o1 and o2, that implies > knowledge of both x1*s1 and x2*s1 where x1 and x2 are random numbers sampled > from an uniform distribution. Once the owner has these two numbers, he can > just > sum these together to obtain s1*(x1+x2). > Now, because of the central limit theorem, the distribution of x1+x2 should > approximate a normal one, concretely an Irwin–Hall distribution, with that > approximation getting better when more numbers are collected through > iterations > of the protocol. Once you've collected enough numbers to approximate a normal > well enough (looking at Irwin Hall distribution graphs^[1] you can observe > that > with less than 10 samples the distribution is already pretty similar to a > normal one), it should be possible to drastically reduce the search space and > apply brute force to guess the value of \sum x and, consequently, s1. > > Practically, it's possible that the search space is still too large for > brute-force to be fruitful, so this attack might not work, but it shows that > there is information leakage in every protocol iteration. > > On another note, if you are not already aware of, something which might be > worth looking into is the possibility of further trust-minimising the SE role > by forcing it's code to be run inside an AWS oracle or a hardware isolated > processor such as SGX. > > Albert > > [1] https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution > > On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin-dev wrote: > > Hi all, > > We are starting to work on an implementation of the statechains concept ( > https://medium.com/@RubenSomsen/ > statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39), with > particular interest in using
Re: [bitcoin-dev] Statechain implementations
Hi Tom, Nice to see you working on this. Regarding modification 1, I agree with ZmnSCPxj that Decker-Wattenhofer is your next best option, given that eltoo is not yet available. But if you are going to use a kickoff transaction, keep in mind that every previous owner will have a copy of it. Because of this, you can't include a fee, and will instead need to have a second output for CPFP. This way a previous owner will at least have to pay the fee if they want to publish it. Note that it's still an improvement, because even if the kickoff transaction gets posted, it basically becomes no different than what it would have been, had you not used a kickoff transaction at all. Regarding modification 2, I like it a lot conceptually. It hadn't occurred to me before, and it's a clear security improvement. The only question is something Greg Sanders mentioned: whether it's enough to justify the added complexity of using 2P ECDSA. The alternative would be to simply use a regular 2-of-2 multisig (until Schnorr arrives, possibly). I'm looking forward to seeing statechains become a reality. Cheers, Ruben On Thu, Mar 26, 2020 at 5:20 AM Albert via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi, > > Great to see some work in this direction, here's some thoughts on your > keygen scheme: > > In the scenario where Owner1=Owner2, that is, one of the owners sends some > coins to itself, that owner would get to know both x1*s1 and > x2*s2=x2*s1*o2_inv*o1, and, because he already knows o1 and o2, that > implies knowledge of both x1*s1 and x2*s1 where x1 and x2 are random > numbers sampled from an uniform distribution. Once the owner has these two > numbers, he can just sum these together to obtain s1*(x1+x2). > Now, because of the central limit theorem, the distribution of x1+x2 > should approximate a normal one, concretely an Irwin–Hall distribution, > with that approximation getting better when more numbers are collected > through iterations of the protocol. Once you've collected enough numbers to > approximate a normal well enough (looking at Irwin Hall distribution > graphs^[1] you can observe that with less than 10 samples the distribution > is already pretty similar to a normal one), it should be possible to > drastically reduce the search space and apply brute force to guess the > value of \sum x and, consequently, s1. > > Practically, it's possible that the search space is still too large for > brute-force to be fruitful, so this attack might not work, but it shows > that there is information leakage in every protocol iteration. > > On another note, if you are not already aware of, something which might be > worth looking into is the possibility of further trust-minimising the SE > role by forcing it's code to be run inside an AWS oracle or a hardware > isolated processor such as SGX. > > Albert > > [1] https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution > > On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin-dev wrote: > > Hi all, > > We are starting to work on an implementation of the statechains concept ( > https://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39), > with particular interest in using the protocol enable the change of > ownership (novation) of an individual position in an active discreet log > contract (DLC) without an on-chain transaction, and without needing the > cooperation of the counterparty. The protocol as outlined by Ruben requires > features not currently available in Bitcoin (like SIGHASH_NOINPUT), and it > is uncertain when (or even if) this will be added. So we are looking at > variants that would work with current Bitcoin functionality, and it would > be good to get some feedback on them. > > There are two main modifications we are looking at: > 1. Instead of an eltoo-based backup/refund transaction (enabling the > current owner to claim the UTXO in case the statechain entity disappears) > we propose using a decrementing nLocktime for backup transactions as the > output changes hands. Here, the first owner gets a backup transaction with > an nLocktime at some future height (h0), then the next owner gets a backup > transaction with nLocktime (h0-c) where c is a confirmation window. This > approach has the downside of limiting the lifetime of the UTXO, but it also > doesn't require the current owner to be always online. > > 2. Replacing the 2-of-2 multisig output (paying to statechain entity SE > key and transitory key) with a single P2(W)PKH output where the public key > shared between the SE and the current owner. The SE and the current owner > can then sign with a 2-of-2 ECDSA MPC. This enables each owner to generate > their own private key share, and the SE changes their key share at each > change of ownership (with the shared public key remaining the same). This > works as follows (.G is EC point multiplication, * is scalar > multiplication): > > KeyGen: > > a. Owner 1 generates private key share o1
