BIP 140: Normalized transaction ID #224

cdecker commented at 1:31 PM on October 19, 2015: contributor

This is the amended Normalized Transaction ID BIP previously discussed on the mailing list. Since the discussion on the mailing list there have been some major changes, for one the BIP changed from requiring a hard-fork to a much easier soft-fork (thanks sipa for helping me figure out how).

The normalized transaction IDs are computed on a stripped version of the transaction, in which all the malleable parts, i.e., the signatures, where removed. This solves malleability in a simple and clean way.

Unlike the original proposal, this version does not use the normalized transaction IDs on a network level, instead they are used solely when signing and checking signatures. Normalized transactions are swapped in on-demand when using a new opcode OP_CHECKSIGEX and are tracked in the UTXO, no longer requiring lookups by normalized transaction ID.

In order to give clear semantics when to track the normalized transaction IDs and anchoring them without recursively computing the IDs of previous transactions down to the coinbases, the version is bumped to 2. Version 2 outputs may be referenced using the normalized transaction IDs, while nothing changes for version 1 transactions.

There is a working implementation of this BIP in my normtx branch.

Draft of the normalized transaction ID BIP 46d25f8629

cdecker renamed this:
~~Draft of the normalized transaction ID BIP~~
Normalized transaction ID BIP
on Oct 19, 2015

sipa commented at 2:03 PM on October 19, 2015: member

I think you should include that to compute a normalized txid, you should replace the prevout hashes in inputs by their respective normalized txid as well, otherwise you only accomplish malleability protection when spending inputs from already unmalleable transactions (=sufficiently confirmed ones).

sipa commented at 2:10 PM on October 19, 2015: member

You cannot mimick OP_CHECKSIG in a softfork, as it has an effect on the stack. You can only create something similar to OP_CHECKVERIFY.

cdecker commented at 2:11 PM on October 19, 2015: contributor

Agreed, sorry for the oversight. If we leave the malleable transaction IDs in there we only achieve a non-malleability of 1 level beyond what is confirmed in the blockchain.

However that means that in order to compute the normalized transaction ID we do need to have the previous outputs in our UTXO so that we can retrieve. Not a huge problem if we discard orphaned transactions anyway, just a minor drawback as I see it. I'll see if I can fix it in my implementation branch :-)

As for mimicking OP_CHECKSIG, isn't it sufficient to leave one non-null item on the top of the stack for old nodes to accept the script?

sipa commented at 2:14 PM on October 19, 2015: member

If we're going to take the effort of:

Introducing a new checksig operator
Increasing the UTXO set size by 20%
Doing a softfork

... we might as well try to fix the problem entirely, and define normalized txids recursively.

cdecker commented at 2:19 PM on October 19, 2015: contributor

By define recursively you mean to recompute all transaction IDs from the coinbase transaction to their current outputs instead of bumping to v2 and anchoring the normalized transaction ID there?

The advantage of not computing them down to the coinbase is that it is trivial for clients to start tracking newly incoming normalized transaction IDs, but it might be very hard to do so on the entire blockchain. For one it is computationally intensive to go through 60+ million transactions, some nodes no longer have all the data (purged blockchain) and I am not clear on what the advantage would be to track additional IDs for historic transactions.

Bumping v2 gives an easy way for future transactions to opt-into being tracked by normalized transaction ID as well.

in bip-00nn.mediawiki:None in 46d25f8629 outdated

  29 | + - Changes to the UTXO tracking to enable normalized transaction ID lookup
  30 | +
  31 | +=== Normalized Transaction ID computation ===
  32 | +
  33 | +In order to calculate the normalized transaction ID, the signature script is stripped from each input of the transaction of non-coinbase transactions. Stripping the signature script is achieved by setting the script's length to 0 and removing the <code>uchar[]</code> array from the <code>TxIn</code>.<ref>[[https://en.bitcoin.it/wiki/Protocol_Specification#tx|Protocol Specification: TX]]</ref>
  34 | +The normalized transaction ID is then computed as the <code>SHA 256</code> hash of the stripped transaction matching the existing transaction ID computation. The normalized transaction ID remains unchanged even if the signatures of the transaction are replaced/malleated and describe a class of semantically identical transactions. In the following we use ''transaction instance ID'' to refer to the transaction ID computed on the transaction including signatures. Normalized transaction IDs for coinbase transactions are computed with the signature script in the coinbase input, in order to avoid hash collisions.

btcdrak commented at 2:21 PM on October 19, 2015:

The normalized transaction ID is then computed as the <code>SHA 256</code> hash

This should be double hash, as per the implementation https://github.com/bitcoin/bitcoin/commit/5f4bd6e22cb7e8ba073207316a83d2ef7ca4bd71#diff-02ae369ce5b03ca498fdf66921b00e0bR76

cdecker commented at 2:54 PM on October 19, 2015:

Right you are, it's a sad day when you can't read your own code anymore :-)

Although, would it maybe be better to change the implementation, to keep the ID computation in sync with how it is currently done for legacy transaction IDs?

btcdrak commented at 4:10 PM on October 19, 2015:

Everything is double sha256()

sipa commented at 2:26 PM on October 19, 2015: member

Sure, you can use transactions versions and state that transactions with v1 have ntxid==txid, to simplify computation. But it doesn't solve the problem: anyone who upgrades to a post-this-BIP codebase will need to be able to know compute ntxids of transactions that spend v2 outputs. If they have pruned those by the time they upgrade, there is no solution.

In my opinion, the cost of permanently increasing the UTXO set size by 20% has a far larger impact and needs much more reconsideration than the one-off reindexing that would be needed to upgrade.

sipa commented at 2:34 PM on October 19, 2015: member

@cdecker For adding new opcodes as a softfork, your opcode may have no affect at all on the stack. It can't even pop the signature it processes. If it makes any changes at all, anyone can create a script that inspects the top stack item after the opcode and fail if it isn't the opcode's expected result. By changing the stack, such a script would go from invalid to valid, which is a hard fork.

cdecker commented at 2:37 PM on October 19, 2015: contributor

I don't think I follow: since we use normalized transaction IDs in the signing and checking phase, and legacy transaction IDs at network level, we will always have to keep around both versions of the transaction ID (until all outputs are spent at which point both can be dropped along with the remainder of CCoins). Computing the normalized transaction IDs for existing outputs therefore would just increase the number of normalized transaction IDs we have to track.

The fact that people upgrading after the first v2 transactions appear have to rescan part of the blockchain is bad, but it only affects people that did not upgrade in time, which hopefully will be a minority, unlike forcing a rescan on everybody.

sipa commented at 2:41 PM on October 19, 2015: member

@cdecker Sure, so use versioning to prevent the separate ntxid for old transactions. It complicates the logic a bit more, but you prevent the instant 20% blowup and requirement for reindexing when upgrading before this BIP takes effect (though if a miner lets in a v2 transaction beforehand, we're all screwed...).

By "define normalized txids recursively" I just mean ultimately using prevout's ntxids in the computation of spending ntxids, not whether this would be done for all of history too.

cdecker commented at 2:51 PM on October 19, 2015: contributor

Ah ok, sure I agree that when computing a transaction's normalized transaction ID we should also replace any prevout hash in the inputs with the normalized version, I will amend the draft to include this and update my implementation to reflect this. I did not specify a way to activate the soft-fork on purpose so we can deploy this in parallel with other changes, but hopefully we can avoid having v2 transactions being confirmed until we have locked in the changes.

So mimicking OP_CHECKSIG or OP_CHECKMULTISIG is not an option, meaning that the last value pushed on the stack (the flags for OP_CHECKSIGEX) is on the top of the stack. Will non-updated clients interpret this as success, even though it has more than one element on the stack? If so we can simply make the SCRIPT_CHECKSIG_VERIFY flag mandatory in order to avoid having OP_0/false on top of the stack.

sipa commented at 2:57 PM on October 19, 2015: member

If the top element on the stack is nonzero at the end of execution, it is succesful.

A scriptSig of "[pubkey] OP_CHECKSIGVERIFY_NORMALIZED" with scriptPubKey "[sig]" would result in a stack of:

Pre-fork with valid sig: "[sig] [pubkey]" (success)
Pre-fork with invalid sig: "[sig] [pubkey]" (success)
Post-fork with valid sig: "[sig] [pubkey]" (success)
Post-fork with invalid sig: fails at execution of the VERIFY, and doesn't reach the end (failure)

So that's exactly the semantics you'd want.

cdecker commented at 3:04 PM on October 19, 2015: contributor

Great, thanks for the clarification, so I think making the SCRIPT_CHECKSIGEX_VERIFY flag mandatory is what we'd want in this case.

Would you prefer to re-use two NOPs and implement the normalized singlesig and the multisig as separate opcodes or is the parameterized version to be preferred? My main motivation was that I don't want to use 4 opcodes (verify/non-verify & singlesig/multisig), but if we lose the flexibility of deciding whether we are doing a multisig based on the flags anyway it could be done using two opcodes.

I still have a preference for the flags since it allows us to introduce more flags in the future and NOPs are pretty rare, so keeping as many as possible free for the future might be better.

gavinandresen commented at 3:29 PM on October 19, 2015: contributor

Single-sig could be done as just 1-of-1 multisig (at the cost of two extra bytes).

And if we're worried about extra bytes, then we should just skip to Schnorr signatures with normalized txids (which I think Elements Alpha already has....)

cdecker commented at 3:39 PM on October 19, 2015: contributor

Agreed, reducing singlesig to 1-of-1 is a possibility, just wanted to keep the change as small and uncontroversial as possible. Same goes for Schnorr, which would be nice to implement, but I don't trust my crypto skills to implement it :-)

That being said, Schnorr would be one of the things that can be added as a flag to OP_CHECKSIGEX, so this might be a point to keep the parameterized opcode over having a special opcode for every checksig operation.

in bip-00nn.mediawiki:None in 46d25f8629 outdated

  94 | +
  95 | +The only occurence in which transactions can still be modified unilaterally is in the case <code>SIGHASH_NONE</code>, <code>SIGHASH_SINGLE</code> or <code>SIGHASH_ANYONECANPAY</code> is used. This however is not problematic since in these cases the creator of the transaction explicitly allows modification.
  96 | +
  97 | +In case of a transaction becoming invalid due to one of the inputs being malleated it is necessary to modify the spending transaction to reference the modified transaction ID. However, the signatures, which only use the normalized IDs, remain valid as long as the semantics of the funding transaction remain unchanged. An observer in the network may fix the transaction and reinject a corrected version.
  98 | +
  99 | +Using version 2 for transactions is an explicit optin to the normalized ID tracking and a simple upgrade for existing clients. It avoids having to reprocess the entire blockchain and computing the normalized transaction IDs for existing outputs in the UTXO. This would be further complicated by having to recursively compute normalized transaction IDs down to the coinbase transactions which created the coins.

schildbach commented at 4:29 PM on October 19, 2015:

optin -> opt-in

in bip-00nn.mediawiki:None in 46d25f8629 outdated

  72 | +
  73 | +    <num sigs> <pubkeys> <numpubkeys> OP_6 OP_CHECKSIGEX
  74 | +
  75 | +The first is the equivalent of the pay-to-pubkeyhash script with normalization (<code>OP_4 = SCRIPT_CHECKSIGEX_NORMALIZE</code>), while the second is the equivalent of the pay-to-multisig also with normalization (<code>OP_6 = SCRIPT_CHECKSIGEX_NORMALIZE | SCRIPT_CHECKSIGEX_MULTI</code>). The format of the <code>scriptSig</code> corresponds to the original version, with exception of omitting the dummy <code>OP_0</code> in the multisig case.
  76 | +
  77 | +=== Tracking Normalized Transaction IDs ===

schildbach commented at 4:33 PM on October 19, 2015:

What's the impact on bloom filters? Will version 3 txns still match existing filters?

cdecker commented at 6:31 PM on October 19, 2015:

There is no change for bloomfilters in that we maintain the existing semantics: if a bloomfilter matches a transaction that is modified in flight it might not match the modified transaction and it may miss future transactions building on it. We could add the normalized outpoint to the bloomfilter as well to ensure that we start forwarding modified transactions and transactions dependent on modified transactions as well, but that might be better suited to a separate spec.

schildbach commented at 7:32 PM on October 19, 2015:

I was also thinking about the nFlags feature, which auto-adds to the filter as matches are detected. I think BLOOM_UPDATE_NONE and BLOOM_UPDATE_ALL are still pretty clearly defined in the context of this BIP, but BLOOM_UPDATE_P2PUBKEY_ONLY could probably need some update or companion.

in bip-00nn.mediawiki:None in 46d25f8629 outdated

  85 | +Normalized transaction IDs are provably non-malleable since no data is included in the signaturehash whose integrity is not also proven in the signature, thus any modification causing the hash to change will also invalidate the signature.
  86 | +Normalized transactions are secure as they still use cryptographic hashes over all the semantic information of the transaction, i.e., the inputs, outputs and metadata, thus it is still computationally infeasible to cause a hash collision between transactions.
  87 | +
  88 | +There are a number of advantages to using normalized transaction IDs:
  89 | +
  90 | +* Like BIP 62 and BIP 66 it solves the problem of third-parties picking transactions out of the network, modifying them and reinjecting them, as was allegedly done to defraud MtGox<ref>[[http://www.tik.ee.ethz.ch/file/7e4a7f3f2991784786037285f4876f5c/malleability.pdf|Bitcoin Transaction Malleability and MtGox]]</ref>.

schildbach commented at 4:35 PM on October 19, 2015:

I think isn't no good to mention MtGox here. It's entirely unclear how the coins were stolen, and who knows maybe they were never stolen?

sipa commented at 4:38 PM on October 19, 2015:

Agree. There are plenty of better reasons for normalizations ignoring that.

cdecker commented at 4:39 PM on October 19, 2015:

Will be removed :-)

btcdrak commented at 4:55 PM on October 19, 2015: contributor

@gavinandresen +1 for Schnorr signatures @cdecker The code for Schnorr signatures is done in Element's Alpha (which also has normalised txids)

luke-jr added the label New BIP on Oct 21, 2015

cdecker commented at 8:42 AM on October 22, 2015: contributor

+1 for Schnorr signatures +1 for singlesig = 1-of-1 multisig

The bitcoin/secp256k1 repo, which is vendorized into bitcoin, contains all the necessary code to enable creating and checking Schnorr signatures. I quite like the idea of enabling this signature scheme since we are touching a lot of signing code already with this PR and it would simply be swapping in the signing and checking code.

Merging singlesig and multisig, so that singlesig is simply a 1-of-1, is also nice since it reduces the number of separate cases we have to treat. In addition Schnorr trivially allows m-of-m by summing up the public keys, resulting in a combined pubkey, and summing up the signatures into a comined sig, then the combined sig is a valid signature for the combined pubkey. So we can manage and combine m-of-m externally to bitcoin-core.

m-of-n could continue using a list of pubkeys and signatures (with the addition of a bitmap for which pubkeys were used when signing), until a better scheme is implemented.

Since we now handle a lot fewer cases (verify is mandatory, singlesig = multisig) it seems natural to drop the flags argument and replace it with a simple version integer. This way we still group all future signature checking opcodes by replacing a single OP_NOP, but the semantics are clearer: if the version is higher than what I support I just treat the checksig op as an OP_NOP, reestablishing the current softfork semantics. Version 1 would use Schnorr signatures and normalization.

luke-jr added the label Needs number assignment on Oct 23, 2015

luke-jr assigned gmaxwell on Oct 23, 2015

cdecker force-pushed on Nov 3, 2015

cdecker commented at 4:46 PM on November 3, 2015: contributor

I just fixed a few minor things and applied the changes we discussed:

Using a simple version flag that indicates what ruleset to use: allows us to group future signature checking opcodes without using a nop, and it is way simpler than having flags, this way we treat unknown versions as nops and maintain softfork semantics.
The first ruleset (version=1) uses normalized transaction IDs and Schnorr signatures.
Adding new standard multisig format for both m-of-n and 1-of-1 as proposed by Gavin, it's not a huge overhead and simplifies things. I'd like to defer more complex scenarios to future BIPs and keep this one simple.

Since there have been no deal-breaking comments and most of the people commenting seem to agree that this proposal is useful I'd like to join @luke-jr in asking @gmaxwell to assign a BIP number :-)

Open questions:

Maybe we could lead the m-of-n sigscript with a bitmap indicating which keys were used? Currently we have to check combinations if I'm not mistaken.
Is the grouping of future signature checking opcodes with a version desired at all, or should I simply redefine OP_NOP4 as Schnorr + normalized without the option to do future versions? I quite like the grouping but I'm open for suggestions.

I gave merging secp256k1 into my dev branch a shot, but it broke far too much for me to feel comfortable fixing it and not introduce bugs, I'll therefore keep ECDSA in my experimental implementation for now, and let @sipa do the merging, he knows best :-)

Replaced binary flags with version, added migration to Schnorr, specified recursive computation and fixed a few minor things. 893a4ff584

cdecker force-pushed on Nov 3, 2015

luke-jr commented at 5:42 PM on November 3, 2015: member

FWIW, I consider the issues I pointed out on the mailing list to be "deal-breaking" in terms of cost/benefit. (Not that you can't still be assigned a BIP number for this despite that.)

gmaxwell commented at 6:22 PM on November 3, 2015: contributor

Checking combinations is not good as it makes batch validation impossible. No signature should be allowed to fail. My recommendation is that for multiple pubkey inputs there must be the same number of signature inputs, but signatures should be required to be empty (and so only take one byte) if not being used, or otherwise pass verification.

I don't understand why luke's alternative proposal that avoids increasing the UTXO set size by 20%+ doesn't seem to have been given consideration. As it stands I would oppose this proposal in Bitcoin Core and in the Bitcoin network due to the apparently avoidable irreversibly increase in the UTXO set size.

This can use BIP130.

luke-jr unassigned gmaxwell on Nov 3, 2015

luke-jr removed the label Needs number assignment on Nov 3, 2015

luke-jr renamed this:
~~Normalized transaction ID BIP~~
BIP 130: Normalized transaction ID BIP
on Nov 3, 2015

luke-jr renamed this:
~~BIP 130: Normalized transaction ID BIP~~
BIP 130: Normalized transaction ID
on Nov 3, 2015

cdecker commented at 7:01 PM on November 3, 2015: contributor

Yep, checking combinations is awful and we can avoid it either by having empty sigs signalling that we should skip this check or by having a bitmap telling us which pubkeys from the script pubkey to use.

I quite like the alternative proposal, which would void any need to do normalization in the first place and basically implement segregated witnesses, however as you also pointed out on the mailing list there is simply no clean way to relaying the witnesses without breaking old clients. I have been discussing this with a few more people and simply couldn't come up with a good way to implement it. The reason it is not in this proposal is that the proposal is implemented and does work, while with the alternative proposal I'm not even sure there is a good solution that does not break everything.

For those who don't want to wade through the mailing list: the alternative proposal by @luke-jr and @gmaxwell would define the opcode in such a way that a transaction is accompanied with an external script (segregated witness) that is not part of the transaction itself. The checksig opcode would require the scriptsig to be empty, hence the transaction would already be normalized. Then we would execute the external script, the scriptsig (which is empty) and the script pubkey so that we get normal execution semantics. The problem is that it is difficult to tell not-upgraded clients that they should now also relay the external script along with the transactions itself.

If there is a workable solution I'm more than happy to amend this proposal and include it.

luke-jr commented at 8:07 PM on November 3, 2015: member

IMO, at the very least, something this expensive should completely fix malleability, which this BIP does not do. Furthermore, this BIP does not disclose its shortcomings.

In any case, these discussions belong on the mailing list, not on this pull request, which only needs the finishing touch of filling in the assigned BIP number to be merged.

cdecker commented at 8:38 PM on November 3, 2015: contributor

Agreed, moving the discussion back to the mailing list. I'd be thrilled if we can get the relaying of segregated witnesses working, that would solve all my problems and be a great improvement to the protocol.

luke-jr commented at 6:26 AM on November 7, 2015: member

uhh... just merged #221 and realised that also has BIP 130 assigned. ping @gmaxwell :/

luke-jr renamed this:
~~BIP 130: Normalized transaction ID~~
BIP 130?: Normalized transaction ID
on Nov 7, 2015

luke-jr added the label Needs number assignment on Nov 7, 2015

luke-jr assigned gmaxwell on Nov 7, 2015

afk11 commented at 4:25 PM on January 8, 2016: contributor

@luke-jr ping, the PR title still mentions bip 130

afk11 unassigned gmaxwell on Jan 8, 2016

afk11 commented at 4:26 PM on January 8, 2016: contributor

Did I just un-assign gmaxwell? How did that happen?

luke-jr renamed this:
~~BIP 130?: Normalized transaction ID~~
New BIP: Normalized transaction ID
on Jan 8, 2016

luke-jr commented at 4:29 PM on January 8, 2016: member

@afk11 Probably internal to GitHub, since gmaxwell is no longer a valid option for assignments.

luke-jr assigned luke-jr on Jan 8, 2016

luke-jr renamed this:
~~New BIP: Normalized transaction ID~~
BIP 140: Normalized transaction ID
on Jan 8, 2016

luke-jr removed the label Needs number assignment on Jan 8, 2016

luke-jr merged this on Jan 8, 2016

luke-jr closed this on Jan 8, 2016