public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Tier Nolan <tier.nolan@gmail.com>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] [BIP] Normalized Transaction IDs
Date: Wed, 13 May 2015 19:11:30 +0100	[thread overview]
Message-ID: <CAE-z3OV1WEDEV+X7gNVx+qBMt4jpSHFKXm3dxUrUyBEJrCNDSQ@mail.gmail.com> (raw)
In-Reply-To: <CAPg+sBggj382me1ATDx4SS9KHVfvX5KH7ZhLHN6B+2_a+Emw1Q@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 4483 bytes --]

On Wed, May 13, 2015 at 6:14 PM, Pieter Wuille <pieter.wuille@gmail.com>
wrote:

> Normalized transaction ids are only effectively non-malleable when all
> inputs they refer to are also non-malleable (or you can have malleability
> in 2nd level dependencies), so I do not believe it makes sense to allow
> mixed usage of the txids at all.
>

The txid or txid-norm is signed, so can't be changed after signing.

The hard fork is to allow transactions to refer to their inputs by txid or
txid-norm.  You pick one before signing.

> They do not provide the actual benefit of guaranteed non-malleability
> before it becomes disallowed to use the old mechanism.
>
A signed transaction cannot have its txid changed.  It is true that users
of the system would have to use txid-norm.

The basic refund transaction is as follows.

 A creates TX1: "Pay w BTC to <B's public key> if signed by A & B"

 A creates TX2: "Pay w BTC from TX1-norm to <A's public key>, locked 48
hours in the future, signed by A"

 A sends TX2 to B

 B signs TX2 and returns to A

A broadcasts TX1.  It is mutated before entering the chain to become
TX1-mutated.

A can still submit TX2 to the blockchain, since TX1 and TX1-mutated have
the same txid-norm.

>
> That, together with the +- resource doubling needed for the UTXO set (as
> earlier mentioned) and the fact that an alternative which is only a
> softfork are available, makes this a bad idea IMHO.
>
> Unsure to what extent this has been presented on the mailinglist, but the
> softfork idea is this:
> * Transactions get 2 txids, one used to reference them (computed as
> before), and one used in an (extended) sighash.
> * The txins keep using the normal txid, so not structural changes to
> Bitcoin.
> * The ntxid is computed by replacing the scriptSigs in inputs by the empty
> string, and by replacing the txids in txins by their corresponding ntxids.
> * A new checksig operator is softforked in, which uses the ntxids in its
> sighashes rather than the full txid.
> * To support efficiently computing ntxids, every tx in the utxo set
> (currently around 6M) stores the ntxid, but only supports lookup bu txid
> still.
>
> This does result in a system where a changed dependency indeed invalidates
> the spending transaction, but the fix is trivial and can be done without
> access to the private key.
>
The problem with this is that 2 level malleability is not protected against.

C spends B which spends A.

A is mutated before it hits the chain.  The only change in A is in the
scriptSig.

B can be converted to B-new without breaking the signature.  This is
because the only change to A was in the sciptSig, which is dropped when
computing the txid-norm.

B-new spends A-mutated.  B-new is different from B in a different place.
The txid it uses to refer to the previous output is changed.

The signed transaction C cannot be converted to a valid C-new.  The txid of
the input points to B.  It is updated to point at B-new.  B-new and B don't
have the same txid-norm, since the change is outside the scriptSig.  This
means that the signature for C is invalid.

The txid replacements should be done recursively.  All input txids should
be replaced by txid-norms when computing the txid-norm for the
transaction.  I think this repairs the problem with only allowing one level?

Computing txid-norm:

- replace all txids in inputs with txid-norms of those transactions
- replace all input scriptSigs with empty scripts
- transaction hash is txid-norm for that transaction

The same situation as above is not fatal now.

C spends B which spends A.

A is mutated before it hits the chain.  The only change in A is in the
scriptSig.

B can be converted to B-new without breaking the signature.  This is
because the only change to A was in the sciptSig, which is dropped when
computing the txid-norm (as before).

B-new spends A mutated.  B-new is different from B in for the previous
inputs.

The input for B-new points to A-mutated.  When computing the txid-norm,
that would be replaced with the txid-norm for A.

Similarly, the input for B points to A and that would have been replaced
with the txid-norm for A.

This means that B and B-new have the same txid-norm.

The signed transaction C can be converted to a valid C-new.  The txid of
the input points to B.  It is updated to point at B-new.  B-new and B now
have have the same txid-norm and so C is valid.

I think this reasoning is valid, but probably needs writing out actual
serializations.

[-- Attachment #2: Type: text/html, Size: 5728 bytes --]

  parent reply	other threads:[~2015-05-13 18:11 UTC|newest]

Thread overview: 27+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-05-13 12:48 [Bitcoin-development] [BIP] Normalized Transaction IDs Christian Decker
2015-05-13 13:12 ` Tier Nolan
2015-05-13 13:41   ` Gavin Andresen
2015-05-13 15:24     ` Christian Decker
2015-05-13 16:18       ` Tier Nolan
2015-05-13 16:34 ` Luke Dashjr
2015-05-13 17:14 ` Pieter Wuille
2015-05-13 18:04   ` Christian Decker
2015-05-13 18:40     ` Pieter Wuille
2015-05-13 19:14       ` Christian Decker
2015-05-13 19:40         ` Pieter Wuille
2015-05-13 18:11   ` Tier Nolan [this message]
2015-05-13 20:27     ` Tier Nolan
2015-05-13 20:31       ` Pieter Wuille
2015-05-13 20:32         ` Tier Nolan
2015-05-14  0:37           ` Pieter Wuille
2015-05-14 11:01             ` Christian Decker
2015-05-14 11:26               ` Christian Decker
2015-05-15  9:54 ` s7r
2015-05-15 10:45   ` Tier Nolan
2015-05-15 16:31   ` Luke Dashjr
2015-05-16  3:58   ` Stephen
2015-05-16 10:52     ` Tier Nolan
2015-05-19  8:28     ` Christian Decker
2015-05-19  9:13       ` Tier Nolan
2015-05-19 10:43         ` Christian Decker
2015-05-19 12:48           ` Stephen Morse

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAE-z3OV1WEDEV+X7gNVx+qBMt4jpSHFKXm3dxUrUyBEJrCNDSQ@mail.gmail.com \
    --to=tier.nolan@gmail.com \
    --cc=bitcoin-development@lists.sourceforge.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox