Semi-soft-fork to decrease the risk of tx malleability

[jl2012]

tx malleability could cause big trouble. I think all devs agree that we have to fix it some point in the future. However, due to the risk involving soft-fork, this could only be done very slowly. Now we have BIP66 but there are still many forms of malleability to be fixed.

I propose to have to a technique called "semi-soft-fork" as a remedy before a real soft-fork is done. Currently, transactions are divided into standard and non-standard. I propose to divide it into 3 types:

• Standard tx (ST): a valid tx with a strict set of scriptSig and scriptPubKey, with all known malleability issues fixed
• Type 1 non-standard tx (NST1): any mutated standard tx, otherwise valid
• Type 2 non-standard tx (NST2): any other valid tx not in the previous categories

A block with only ST is a standard block (SB). A block with at least 1 NST1 non-standard tx is a Type 1 non-standard block (NSB1). A block with no NST1 but with at least 1 NST2 is a Type 2 non-standard block (NSB2). SB, NSB1 and NSB2 are all valid blocks, just with different level of standardness

Miners joining this semi-soft-fork will still try to mine the longest chain, no matter the blocks in it are SB, NSB1, or NSB2. However, if there are forks with same length, the miner will always switch to the fork with least number of NSB1.

If there are enough miners joining this semi-soft-fork, it will provide incentive for the rest of miners to avoid NST1 and NSB1. Therefore, the risk of tx malleability is reduced. And since this is not a consensus rule change, it is easily reversible if anything goes wrong. It will also allow us to test the anti-malleability code before we migrate to a real soft-fork.

[1713913128]

1713913128

[1713913128]

1713913128

[1713913128]

1713913128

[funkenstein]

I'm still not so sure tx malleability is a real issue.  One can always check that the receiving address received payment from the sending address.  And what else is really so important?  In the recent proposal of payment channels (lighthouse) there is also talk that malleability could cause a problem.  I haven't understood how that is the case yet.  What am I missing? 

[Amph]

wasn't this issued with an update? i remember that was a big excuse used by gox for their loss, and others exchangee has started to take it as an excuse also(minus cryptsy)

[gmaxwell]

we have BIP66 but there are still many forms of malleability to be fixed.

BIP66 is not about malleability, really; BIP62 is.

What you're describing has previously been described as "Block discouragement";  here I think it has all the software complexity of a normal soft-fork plus the additional complexity of the discouragement mechanism.

I do not see how this helps much; the reversibility is a selling point, but at a far from zero cost. We'll be moving on 62 once 66 is actually deployed (one flaw in the the legacy softfork deployment mechanism is that only one change can be in flight at a time)

[jl2012]

we have BIP66 but there are still many forms of malleability to be fixed.

BIP66 is not about malleability, really; BIP62 is.

But in the BIP66 description it says it "has the added benefit of reducing transaction malleability":

every non-compliant signature can trivially be converted into a compliant one, so there is no loss of functionality by this requirement. This proposal has the added benefit of reducing transaction malleability (see BIP 62).

And if a non-compliant signature can trivially be converted into a compliant one (I assume private key is not needed for such conversion?), why isn't it a source of malleability?

What you're describing has previously been described as "Block discouragement";  here I think it has all the software complexity of a normal soft-fork plus the additional complexity of the discouragement mechanism.

Most block discouragement rules should eventually become soft-fork rules. So the code should be pretty much reusable. The code for discouragement mechanism is also reusable in the future.

I do not see how this helps much; the reversibility is a selling point, but at a far from zero cost. We'll be moving on 62 once 66 is actually deployed (one flaw in the the legacy softfork deployment mechanism is that only one change can be in flight at a time)

As mining becomes more professional and competitive, miners will try everything to reduce the stale rate. It's not zero cost but most work done are reusable. And the selling point is low risk, not low cost.

Can we deploy 2 (or more) soft-fork concurrently like this: block version 3 is BIP62 only; block version 4 is BIP66 only; block version 5 is both BIP62 and 66?

[gmaxwell]

But in the BIP66 description it says it "has the added benefit of reducing transaction malleability":

Sure, its a forward move of one of the BIP62 features; but "reducing" doesn't improve anything; it's not like malleability happens by chance.

And if a non-compliant signature can trivially be converted into a compliant one (I assume private key is not needed for such conversion?), why isn't it a source of malleability?

Because only the single canonical form is permitted in the blockchain.

And the selling point is low risk, not low cost.

The amount of code that must be written and confirmed to be correct is the risk, and the risk is the cost.

An ordinary soft-fork is not especially risky so long as the work is done to be confident that its engineered correctly; and virtually all the risk comes from the definition of the restriction itself; there was an inflow of virtually no review or commentary for BIP66.

Can we deploy 2 (or more) soft-fork concurrently like this: block version 3 is BIP62 only; block version 4 is BIP66 only; block version 5 is both BIP62 and 66?

Not with the current definition for the mechanism used in BIP62. Version 5 would enable BIP 62 on existing nodes.

Pieter has a new proposal which makes major improvements: every softfork is signaled by a single bit, the when the bit crossed threshold it 'latches' and
becomes available for reuse again, and there is a deadline by which if it fails to latch its aborted and becomes available for use again.

We wanted to use that for BIP62 but it would have delayed the process.

Keep in mind, that for refund protocols where the potential attacker is a signer of the transaction no "fix" in the form of signature encoding improvements is possible; their problem is not that transactions are malleable but that the malleability matters. BIP66 is about preventing (we hope) third party malleability.

[jl2012]

Pieter has a new proposal which makes major improvements: every softfork is signaled by a single bit, the when the bit crossed threshold it 'latches' and
becomes available for reuse again, and there is a deadline by which if it fails to latch its aborted and becomes available for use again.

But there are only 32 bits in the version. It will be exhausted very soon if it is used in this way, isn't it?

Keep in mind, that for refund protocols where the potential attacker is a signer of the transaction no "fix" in the form of signature encoding improvements is possible; their problem is not that transactions are malleable but that the malleability matters. BIP66 is about preventing (we hope) third party malleability.

By third party malleability do you mean the ability of mutating a tx without private key? I think this is the only type of malleability we may fix. Private key holder will always be able to mutate and double spend a tx before it is confirmed.

I'm not sure if I misunderstand you. In the refund protocol, the potential attacker (i.e. the payee) does not need to sign the payment to the escrow address. It should work like this:

1. Merchant generates a new private key, and send the public key to the customer.
2. Customer creates a 2-of-2 P2SH address with his own public key and merchant's public key
3. Customer creates a tx, sending some bitcoin to the P2SH address from step 2, but not publishing the tx
4. Customer asks the merchant to sign a nlocktime refund tx with the outpoint from step 3.
5. Customer publishes the tx from step 3.
6. After the tx from step 3 is confirmed, customer shows the script to the merchant to prove that the bitcoin is under escrow.

Customer may lose money if tx mutation happens between step 5 and 6. However, if we fixed all known third-party malleability, the customer is the only person having to ability to mutate it but he has absolutely no incentive to do it.

[gmaxwell]

It will be exhausted very soon if it is used in this way, isn't it?

No, because the bit becomes available for use again after the feature latches or passes the deadline without latching;  So up to 31 features in flight at once, and no total limit (though we might reduce it to just 15 of the bits being used in this way).

If the soft-fork rules are consistent even for yet undefined future soft-forks then even a non-upgraded client can tell what the state of the softfork is even without knowing its specifics.

I'm not sure if I misunderstand you. In the refund protocol, the potential attacker (i.e. the payee) does not need to sign the payment to the escrow address. It should work like this:

Depends on what you mean by refund protocol. As soon as your pattern makes multiple transactions-- e.g. the escrow makes change back to the escrow, things are broken again.

[TierNolan]

No, because the bit becomes available for use again after the feature latches or passes the deadline without latching;  So up to 31 features in flight at once, and no total limit (though we might reduce it to just 15 of the bits being used in this way).

So, version becomes non-monotonic?

What about 2 bytes for "count" and 2 bytes for softforks.

If a soft-fork is accepted, the "count" part of the version increases by 1.

If the count is made the top 2 bytes, then the version will increase as each soft fork is accepted.

If the soft-fork rules are consistent even for yet undefined future soft-forks then even a non-upgraded client can tell what the state of the softfork is even without knowing its specifics.

A warning to update has the risk of everyone updating their client at the same time.

If the consensus lib was based on a virtual CPU with bytecode, the new soft rule could potentially be added as part of the process.  That might make it too easy to add soft forks though.

[gmaxwell]

So, version becomes non-monotonic?

Correct. And why shouldn't it be? It's just data. An expectation of monotonicity is not very compatible with decentralization in any case.

What about 2 bytes for "count" and 2 bytes for softforks.
If a soft-fork is accepted, the "count" part of the version increases by 1.
If the count is made the top 2 bytes, then the version will increase as each soft fork is accepted.

What would this gain? You can already count the acceptance from the flags, even if you don't know what they mean.

We'd want to use the remaining bits for extra information that needs to be judged statelessly, without seeing the prior headers. (there are very few cases where this matters, but e.g. additional POW constraints, for soft-forking in an additional POW, would be an example).

A warning to update has the risk of everyone updating their client at the same time.

Not a warning to update-- but notice that the network is imposing rules that your software doesn't understand, meaning that it might accept a fork the overwhelming majority of the hashpower on the chain you're on would not accept.   Such a notice would only happen around the point the new rules went into effect in any case; e.g. once its already widely deployed.

If the consensus lib was based on a virtual CPU with bytecode, the new soft rule could potentially be added as part of the process.  That might make it too easy to add soft forks though.

That could only safely work for rules that didn't lock in, since they could only really safely be applied in the context of a single chain.  Keep in mind, a big reason for the rules a node imposes exist to create a reason for miners to behave honestly; the purpose of it is to constrain their behavior, so giving them control over it doesn't make sense.  A soft-fork isn't a vote; its safe coordination for activation of a change that people already (almost certainly) consent to. The whole reason to have it isn't to decide to do it or not, but to make sure that everyone imposes it at the same time.

[jl2012]

Depends on what you mean by refund protocol. As soon as your pattern makes multiple transactions-- e.g. the escrow makes change back to the escrow, things are broken again.

Then just make it be escrow -> customer -> escrow.

Or to fix it permanently, we may have a hardfork (or a softfork in a creative way) to replace txid with normalized-txid. This will ensure that a safe subset of tx (SIGHASH_ALL and pay-to-key-hash/pay-to-pubkey) will be totally free of malleability.

[TierNolan]

Correct. And why shouldn't it be? It's just data. An expectation of monotonicity is not very compatible with decentralization in any case.

It would make it easier to do the soft fork checks in code. 

Code:

// BIP - XYZ - Soft fork check
If (block.version >> 16 >= 7) {
   // Do check
}

Though probably the easiest is to just hard code the hash for a block after the change and set all blocks before that as automatically valid.

That could only safely work for rules that didn't lock in, since they could only really safely be applied in the context of a single chain.  Keep in mind, a big reason for the rules a node imposes exist to create a reason for miners to behave honestly; the purpose of it is to constrain their behavior, so giving them control over it doesn't make sense.

It would still need 95%+ support for miners.

It would be a way for miners to coordinate more easily though.

The proposal could include some way to actually designate what the new bits actually mean.  For example, the miner could include "magic_number | 0xFF | hash(BIP text)" in the coinbase.  If 10 people have already done that in the last 1000 blocks, then the 10th person can replace 0xFF with the bit index they want to use for the new BIP.  It is like proposing and seconding for consideration.

The rule for the last 1000 blocks could be

< 10%: Bit reverts to unused [*]
> 75%: Activate rule for blocks with the bit set
> 95%: Activate rule for all blocks

[*]: Blocks with multiple bits set could as 1/N blocks per bit (N = number of bits)

A pool (or group) with >10% of the mining power would be able to get a BIP considered, but couldn't lockout all 16.  The division rule could be activated if to many bits were active.

[gmaxwell]

It would make it easier to do the soft fork checks in code. 

It would make it easier to do them wrong.  You're expecting change A, but the network has adopted B.  You're now confused.  That kind of simplistic check is only safe with a centralized process providing a universal order of changes; and to provide that non-safety it has to use up a fair amount of precious space.

Compared to the rest of the complexity of checking headers I don't see keeping 15 counters a list of completed changes to be a major barrier.

It would still need 95%+ support for miners.

It's much easier to get 95% hashrate (not that this isn't 95% people or anything like that) for a very profitable blank check.

[TierNolan]

It would make it easier to do them wrong.  You're expecting change A, but the network has adopted B.

I was thinking implementations after the fork has been accepted for a while.  The threshold could be based on block height to give the same benefit in that case though.

The consensus lib would still need the full set of rules.  There does need to be some way to tie bits to particular BIPs though.  A major re-org could mean that the software can't figure out which rules are in effect.

[Cryddit]

The only problem I see with the per-bit masking of block version is old clients that misinterpret the bits without realizing that the same bit they expect to mean A, now means B.  

One way to avoid this is for the old clients to know at what block height their knowledge of the meaning of the bits was current; then when checking the block chain, if they see more than one on-off cycle during the block chain since that point they are aware that they no longer know the meaning of a bit.

[TierNolan]

One way to avoid this is for the old clients to know at what block height their knowledge of the meaning of the bits was current; then when checking the block chain, if they see more than one on-off cycle during the block chain since that point they are aware that they no longer know the meaning of a bit.

The first objective is to allow old/obsolete clients know that a soft fork has occured.  It doesn't matter what the bits are defined as.  If after the last known block, there is 950 out of the last 1000 blocks with a version bit set, then the soft fork flag can be set.

The second objective is to allow multiple soft forks to run at the same time.  The process followed could be that the reference client is updated with the soft fork rule and then is allowed to run with it being part of the reference client for 6 months.  The bit could be recovered by having a max block height rule.  If the soft fork doesn't activate before a certain block height, then it is permenently disabled.  This prevents the bit accidently activating the rule later.  If the rule is not accepted, then it is removed/amended in the reference client for the next release.

The inherent assumption is that major re-orgs don't happen.  Each new soft-fork acts as a checkpoint. 

[Realpra]

I'm still not so sure tx malleability is a real issue.  One can always check that the receiving address received payment from the sending address.  And what else is really so important?  In the recent proposal of payment channels (lighthouse) there is also talk that malleability could cause a problem.  I haven't understood how that is the case yet.  What am I missing?  

You're correct, TX malleability is only an issue if people use the TX hashes as Ids.

This is because a script saying 1=1 can be changed to saying 1=1=1 and it will still be correct (gross simplification), but the hash of the entire TX changes.

Obviously scripts cannot sign themselves because it would change the script.


"Fixing" malleability would also mean making the script system less flexible which I am against.

It has even been shown that very few of the losses of MtGox could be blamed on TX malleability - it was a total lie.

[jl2012]

I'm still not so sure tx malleability is a real issue.  One can always check that the receiving address received payment from the sending address.  And what else is really so important?  In the recent proposal of payment channels (lighthouse) there is also talk that malleability could cause a problem.  I haven't understood how that is the case yet.  What am I missing? 

You're correct, TX maleability is only an issue if people use the TX hashes as Ids.

You're not correct, things are not that simple.

Malleability has big impact on any anything depending on transaction hash of unconfirmed transactions, e.g:

• Refund protocols: https://bitcointalk.org/index.php?topic=303088.msg11149909
• Spending outputs of unconfirmed transactions. Due to third party malleability, a transaction chain could be broken even if all payers are honest

[Cryddit]

You're correct, TX maleability is only an issue if people use the TX hashes as Ids.

The problem with not using tx hashes as a transaction ID, is that tx hashes are exactly what the block chain itself uses as a tx ID when specifying what transaction's output to use as an input.  If you don't know the transaction hash in advance, you can't make a transaction that spends its output in advance.  And if you can't make transactions that spend outputs before the outputs they spend actually get into the block chain, then a lot of escrow and other protocols don't work. 

We need transaction ID's to be stable.  Can we make the tx hash by exclusively hashing things that nobody outside the original transaction set can change? 

[jl2012]

You're correct, TX maleability is only an issue if people use the TX hashes as Ids.

The problem with not using tx hashes as a transaction ID, is that tx hashes are exactly what the block chain itself uses as a tx ID when specifying what transaction's output to use as an input.  If you don't know the transaction hash in advance, you can't make a transaction that spends its output in advance.  And if you can't make transactions that spend outputs before the outputs they spend actually get into the block chain, then a lot of escrow and other protocols don't work. 

We need transaction ID's to be stable.  Can we make the tx hash by exclusively hashing things that nobody outside the original transaction set can change? 

Yes, but that would need a hardfork, or a very complicated softfork.

I proposed this last year:

(1) The txid will be the hash of the tx with all scriptSig removed.
(currently, txid is the hash of the tx, including all scriptSig)

(2) The first level of merkle root will be hash of (txid-a|size-a|txid-b|size-b), where txid-a and size-a are the txid and size of tx-a respectively
(currently, the first level of merkle root is (txid-a|txid-b))

With (1), no third party mutation of the txid is possible. Even when spending n-of-m multi-sig output, the txid is mutable only if n signers agree (currently, any 1 signers may mutate it)

However, due to scriptSig malleability, there is an infinite number of ways to record the same tx. Therefore, we need to put the tx size in the formula of the merkle root. For a tx to be valid, it must be equal or smaller than the size indicated. This guarantees that blocks in different nodes will have an upper size limit. However, the actual content the txs could be different, as long as they are valid.