Subject: Re: [bitcoin-dev] Statechain implementations

From: Tom Trevethan <[email-masked]>
Date: Sun, 5 Apr 2020 22:25:51 +0100

Hi Bob and Nadav,

There seems to be no way to prevent a malicious SE from stealing an
output from the current owner by either colluding with (or being) a
previous owner. But with a proof-of-publication (i.e. the statechain) it is
possible for the current owner to have a proof that the SE has stolen from
them. It seems to me that the statechain itself provides two functions: 1.
Proof that an output has only a single owner at any time (preventing the SE
from double-spending) and 2. a way for the current owner to prove their
ownership, and require their permission to change ownership. 1. can just be
a publication by the SE, but 2. requires that the output is transferred to
a public key of the owner, and only via a signature of the previous owner
(in this way the SE cannot re-assign ownership unilaterally). Therefore I
think Nadav is right, and this needs to be a key that the SE can never know
(even if they are malicious), but which can be used to prove ownership, and
in turn prove fraud on the part of the SE.

I don't think that this should be too much of an issue: any wallet will
have to use new keys for each output and transfer anyway. The statechain
key (used for the ownership proof) and the output key share can be on
different hardened HD paths (following on from a path derived from the
outpoint of the UTXO, similar to the method in BIP175).

Tom

On Sun, Apr 5, 2020 at 3:17 PM Bob McElrath <[email-masked]> wrote:

> Note that this attack requires collaboration with the current UTXO owner.
> Generally if there's some form of address/payment request, the current
> holder is
> trying to transfer the UXTO to some other (non-statechain) entity, and he
> knows
> the target of the transfer, and participates in the protocol to authorize
> it.
> The current holder must obtain the target pubkey for the transfer
> out-of-band
> with respect to the SE, or the SE can MITM that.
>
> It's a stated security assumption that the sender or receiver do not
> collude
> with the SE. If either do, then your attack is generally possible and all
> bets
> are off. So what you've described is simply the SE colluding with the
> receiver.
> The receiver will *already* receive the UTXO, so the receiver here is
> assisting
> the SE in stealing his (the receiver's) funds, or the SE has done a MITM
> on the
> transfer.  Various improvements including blind signing, a SE-federation,
> etc
> are valuable to consider to mitigate this. But the SE must be prevented,
> one way
> or another, from "buying the UTXO". The SE cannot be allowed to be both
> operator
> of the SE and a customer of it, as this clearly violates the no-receiver
> collusion principle.
>
> "Adding a new user key" doesn't change the situation. There's already a
> user key
> involved, and the user has already acquiesced to the transfer. Acquiescing
> with
> two keys doesn't change anything.
>
> As far as proving and tracing the fraud, this is where "single use seals"
> come
> in. Each SE transfer can involve an "opening" of a seal, followed by a
> "close"
> when it is transferred, creating a linear history of ownership. If the SE
> obtains the full private key x, one way or another, the spend of that UTXO
> will
> fall outside this seal-based history, and proof of fraud will be evident.
> It
> won't be possible to determine *which* of the old owners collaborated with
> the
> SE, but it gives clear proof that the SE is not to be trusted. A customer
> might
> demand that a seal-based system be in use as an independent entity from
> the SE,
> to audit the honesty of the SE. The seal system does not require any of
> the keys
> required for transfer. See https://mainstay.xyz as a potential
> implementation.
> There are lots of reasons this might required as an AML solution for some
> businesses anyway.
>
> Nadav Kohen via bitcoin-dev [[email-masked]] wrote:
> > Hey all,
> >
> > So my main concern with the proposal as written is that the Statechain
> Entity
> > (SE) can untraceably scam its users with the following attack:
> >
> > 1) Buy the utxo (have it transferred to a key it knows), this first step
> can be
> > skipped if the utxo was created by the SE.
> > 2) Transfer the UTXO to someone else, let it be for however long
> > 3) When it wishes to steal the UTXO, the SE now knows its own shard s_n
> and it
> > knows the full private key, x, from when it owned the UTXO (and had both
> > shards), and so it can compute x/s_n = the current users shard. It can
> then
> > sign for the current user, and forge a state transition to a key it owns
> before
> > spending the UTXO on chain.
> >
> > The main problem here is that the user who had their funds stolen cannot
> prove
> > to anyone that this has happened since the attack compromises their key.
> > That said, I think this problem is easily fixed by adding a new user key
> to the
> > protocol with which they must sign in order for the transfer to be
> considered
> > valid on the state chain. This way, if the SE wishes to steal the funds
> (which
> > they still can), at least it is traceable/provable that this SE is not
> > trustworthy as there is no evidence of a valid transfer for the funds
> that have
> > been stolen.
> >
> > Best,
> > Nadav
> >
> > On Thu, Apr 2, 2020 at 7:22 PM Tom Trevethan via bitcoin-dev <
> > [email-masked]> wrote:
> >
> >     Thanks for all of the input and comments - I do now think that the
> >     decrementing nSequence relative locktime backup system with kick-off
> >     transaction is the way to go, including a fee penalty via CPFP to
> >     disincentivise DoS, as suggested.
> >     I have started a more detailed document specifying the proposed
> protocol in
> >     more detail: https://github.com/commerceblock/mercury/blob/master/
> >     statechains.md which includes improvements to the transfer mechanism
> (and
> >     an explanation of how this can be used to transfer/novate positions
> in
> >     DLCs). Always happy to get more feedback or PRs.
> >
> >     Tom
> >
> >     On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <
> [email-masked]>
> >     wrote:
> >
> >         Hi David,
> >
> >         Just for clarity, I left nChain over 2 years ago (having worked
> there
> >         since 2016). While there, I (along with other researchers) were
> given
> >         free rein to work on any ideas we wanted to. I had been
> interested in
> >         the scaling of Bitcoin off-chain, and this was one of several
> things I
> >         spent time on (including things like sidechains, pegs and
> threshold
> >         signatures). This patent application came out of an idea I had to
> >         transfer ownership of UTXOs off-chain that has some similarities
> to the
> >         statechains proposal, which has shown there is interest and
> demand for
> >         this type of system.
> >
> >         Although I think the existence of this application is something
> to be
> >         mindful of, there are several important things to note:
> >
> >         1. Although there are similarities, the current ideas are
> significantly
> >         different to those in the application.
> >         2. The key transfer protocol as described in the application is
> not
> >         secure (for several reasons, including as discussed above, by
> Albert
> >         and Bob etc.) - and a different mechanism is required.
> >         3. Decrementing timelocks (as suggested in the application) are
> prior
> >         art (Decker-Wattenhofer 2015), and in any case any
> implementation will
> >         most likely use an 'invalidation tree' relative locktime backup
> >         mechanism for open-ended UTXOs.
> >         4. The patent application has not been granted (it was made in
> May
> >         2017) and the international search report rejected it on the
> grounds of
> >         prior art.
> >
> >         Tom
> >
> >         On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <[email-masked]
> >
> >         wrote:
> >
> >             On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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),
> >             >
> >             > [...]
> >             > There are two main modifications we are looking at:
> >             > [...]
> >             >
> >             > 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.
> >
> >             Dr. Trevethan,
> >
> >             Would you be able to explain how your proposal to use
> statechains
> >             with
> >             2P-ECDSA relates to your patent assigned to nChain Holdings
> for
> >             "Secure
> >             off-chain blockchain transactions"?[1]
> >
> >                 [1] https://patents.google.com/patent/US20200074464A1
> >
> >             Here are some excerpts from the application that caught my
> >             attention in
> >             the context of statechains in general and your proposal to
> this
> >             list in
> >             particular:
> >
> >             > an exchange platform that is trusted to implement and
> operate the
> >             > transaction protocol, without requiring an on-chain
> transaction.
> >             The
> >             > off-chain transactions enable one computer system to
> generate
> >             multiple
> >             > transactions that are recordable to a blockchain in
> different
> >             > circumstances
> >             >
> >             > [...]
> >             >
> >             > at least some of the off-chain transactions are valid for
> >             recording on
> >             > the blockchain even in the event of a catastrophic failure
> of the
> >             > exchange (e.g., exchange going permanently off-line or
> loosing
> >             key
> >             > shares).
> >             >
> >             > [...]
> >             >
> >             > there may be provided a computer readable storage medium
> >             including a
> >             > two-party elliptic curve digital signature algorithm
> (two-party
> >             ECDSA)
> >             > script comprising computer executable instructions which,
> when
> >             > executed, configure a processor to perform functions of a
> >             two-party
> >             > elliptic curve digital signature algorithm described
> herein.
> >             >
> >             > [...]
> >             >
> >             > In this instance the malicious actor would then also have
> to
> >             collude
> >             > with a previous owner of the funds to recreate the full
> key.
> >             Because
> >             > an attack requires either the simultaneous theft of both
> exchange
> >             and
> >             > depositor keys or collusion with previous legitimate
> owners of
> >             funds,
> >             > the opportunities for a malicious attacker to compromise
> the
> >             exchange
> >             > platform are limited.
> >
> >             Thank you,
> >
> >             -Dave
> >
> >     _______________________________________________
> >     bitcoin-dev mailing list
> >     [email-masked]
> >     https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > !DSPAM:5e87670a231323960034969!
>
> > _______________________________________________
> > bitcoin-dev mailing list
> > [email-masked]
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> >
> > !DSPAM:5e87670a231323960034969!
>
> --
> Cheers, Bob McElrath
>
> "For every complex problem, there is a solution that is simple, neat, and
> wrong."
>     -- H. L. Mencken
>
>