Added BIP 69: Lexicographical Indexing of Inputs and Outputs #157

kristovatlas commented at 9:32 PM on June 12, 2015: contributor

Lexicographical Indexing of Transaction Inputs and Outputs

Added BIP 79

Lexicographical Indexing of Transaction Inputs and Outputs

61a9711deb

kristovatlas commented at 4:27 PM on June 14, 2015: contributor

Electrum 2.3.2 has implemented BIP 69: https://github.com/spesmilo/electrum/blob/master/RELEASE-NOTES

laanwj commented at 12:18 PM on June 22, 2015: member

Maybe add reference to discussion on mailing list: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-June/008484.html

BIP #69 assigned by gmaxwell 469e7e7f12

BIP 69 not 79 f5b652d6ba

Links to discussion, changed Acknowledgements

Added links to discussion per request from laanwj.

9a0d3bb69e

kristovatlas renamed this:
~~Added BIP 79~~
Added BIP 69
on Jun 24, 2015

laanwj commented at 9:26 AM on July 30, 2015: member

Weird: seems to need rebase

kristovatlas cross-referenced this on Aug 6, 2015 from issue Adhere to BIP69 by dcousens

dcousens commented at 1:31 AM on August 7, 2015: contributor

LGTM, anything holding this back?

edit: added some comments below

in bip-0069.mediawiki:None in 9a0d3bb69e outdated

  66 | +
  67 | +Hashes of previous transactions are considered for the purposes of this BIP in their little-endian, byte array format in order to match the traditional, human-readable string representation of the hashes. They must be sorted in accordance with the output of the bytearr_cmp() function above: the hash with the earliest lesser byte is ordered first, and shorter hashes are ordered before longer ones as a tie-breaker. In the event of two matching transaction hashes, output indices will be compared based on their integer value, with the smaller value ordered first. A further tie is extremely improbable for the aforementioned reasons.
  68 | +
  69 | +Because the hash of previous transactions and output indices must be included in a signed transaction, wallet clients capable of signing transactions will necessarily have access to this data.
  70 | +
  71 | +Transaction malleability will not negatively impact the correctness of this process. Even if a wallet client follows this process using unconfirmed UTXOs as inputs and an attacker changes modifies the blockchain’s record of the hash of the previous transaction, the wallet client will include the invalidated previous transaction hash in its input data, and will still correctly sort with respect to that invalidated hash.

dcousens commented at 3:08 AM on August 7, 2015:

Is malleability even relevant? I don't foresee this being a common question to ask, but, I guess it doesn't hurt to leave it in.

in bip-0069.mediawiki:None in 9a0d3bb69e outdated

  60 | +
  61 | +N.B. These comparisons do not need to operate in constant time since they are not processing secret information.
  62 | +
  63 | +===Transaction Inputs===
  64 | +
  65 | +104	Transaction inputs are defined by the hash of a previous transaction, the output index of of a UTXO from that previous transaction, the size of an unlocking script, the unlocking script, and a sequence number. [3] For sorting inputs, the hash of the previous transaction and the output index within that transaction are sufficient for sorting purposes; each transaction hash has an extremely high probability of being unique in the blockchain — this is enforced for coinbase transactions by BIP30 — and output indices within a transaction are unique. For the sake of efficiency, transaction hashes should be compared first before output indices, since output indices from different transactions are often equivalent, while all bytes of the transaction hash are effectively random variables.

dcousens commented at 3:09 AM on August 7, 2015:

This entire paragraph is quite verbose and seems more like a primer on things we already know in the bitcoin space. I'm not sure if its relevant to describing this process.

in bip-0069.mediawiki:None in 9a0d3bb69e outdated

  62 | +
  63 | +===Transaction Inputs===
  64 | +
  65 | +104	Transaction inputs are defined by the hash of a previous transaction, the output index of of a UTXO from that previous transaction, the size of an unlocking script, the unlocking script, and a sequence number. [3] For sorting inputs, the hash of the previous transaction and the output index within that transaction are sufficient for sorting purposes; each transaction hash has an extremely high probability of being unique in the blockchain — this is enforced for coinbase transactions by BIP30 — and output indices within a transaction are unique. For the sake of efficiency, transaction hashes should be compared first before output indices, since output indices from different transactions are often equivalent, while all bytes of the transaction hash are effectively random variables.
  66 | +
  67 | +Hashes of previous transactions are considered for the purposes of this BIP in their little-endian, byte array format in order to match the traditional, human-readable string representation of the hashes. They must be sorted in accordance with the output of the bytearr_cmp() function above: the hash with the earliest lesser byte is ordered first, and shorter hashes are ordered before longer ones as a tie-breaker. In the event of two matching transaction hashes, output indices will be compared based on their integer value, with the smaller value ordered first. A further tie is extremely improbable for the aforementioned reasons.

dcousens commented at 3:10 AM on August 7, 2015:

A further tie is extremely improbable for the aforementioned reasons.

In this case, why not just define the behaviour and say that the expected behaviour is that they are equal? Why do we need to have a gap in the spec here?

dcousens commented at 3:13 AM on August 7, 2015:

shorter hashes are ordered before longer ones as a tie-breaker

Transaction hashes are always going to be 256-bit (32 bytes), as they are the direct output of SHA256. Why are we accounting for 'shorter hashes'?

in bip-0069.mediawiki:None in 9a0d3bb69e outdated

  33 | +
  34 | +In the event that future protocol upgrades introduce new signature hash types, compliant software should apply the lexicographical ordering principle analogously.
  35 | +
  36 | +While out of scope of this BIP, protocols that do require a specified order of inputs/outputs (e.g. due to use of SIGHASH_SINGLE) should consider the goals of this BIP and how best to adapt them to the specific needs of those protocols.
  37 | +
  38 | +===Lexicographical Sorting===

dcousens commented at 3:12 AM on August 7, 2015:

I'm not sure if an algorithmic description of lexicographical sorting is required, this entire section could be summarised (including the pseudocode) with just a link to the Lexicographical ordering Wikipedia entry.

dcousens commented at 4:31 AM on August 7, 2015: contributor

Test fixtures can be found here.

A Javascript implementation can be found here, and on npm.

dcousens commented at 6:12 AM on August 9, 2015: contributor

@kristovatlas, @petertodd thoughts on integrating the anti-fee-sniping behaviour (see https://github.com/bitcoin/bitcoin/pull/6216) into BIP69?

kristovatlas commented at 3:13 PM on August 9, 2015: contributor

What's fee sniping?

dcousens commented at 12:23 AM on August 10, 2015: contributor

@kristovatlas to quote @petertodd from https://github.com/bitcoin/bitcoin/pull/2340

The more important reason is to discourage "fee sniping" by deliberately mining blocks that orphan the current best block. Basically for a large miner the value of the transactions in the best block and the mempool can exceed the cost of deliberately attempting to mine two blocks to orphan the best block. However with nLockTime you'll soon run out of transactions you can put in the first block, which means they now need to go in the second. With limited block sizes you're run out of room, and additionally another miner now only needs to orphan one block to in-turn snipe the high-fee transactions you had to place in the second block, wrecking all your hard work.

TL;DR: stop miners attempting to orphan current blocks in an attempt to increase their fee subsidy reward, enforced by transactions setting their 'minimum' inclusion time as the current block height.

How that is relevant to this BIP is that it does mean transactions are more easily recognized due to nLockTime being set to activeChain.Height() + 1 (the next block).

kristovatlas commented at 8:56 PM on August 18, 2015: contributor

I can sort of see the relationship there, but I'd prefer to keep this BIP straightforward and restricted to advice to Bitcoin wallet clients.

kristovatlas commented at 8:57 PM on August 18, 2015: contributor

Test fixtures can be found here.

A Javascript implementation can be found here, and on npm.

Thanks a lot! I will add links to these in the BIP.

kristovatlas commented at 8:59 PM on August 18, 2015: contributor

I tried rebasing my local copy but to no avail, so I'm going to try submitting a new PR...

Merge remote-tracking branch 'bitcoin/master'

Conflicts:
	README.mediawiki

0ec82c9c8f

trying to fix git mixup with bip68 5f07cd0d18

kristovatlas commented at 9:45 PM on August 18, 2015: contributor

Looks like I managed to resolve them. Please consider merging, @laanwj

added list of open source implementations

H/T @dcousens

831a003f36

kristovatlas renamed this:
~~Added BIP 69~~
Added BIP 69: Lexicographical Indexing of Inputs and Outputs
on Aug 18, 2015

dcousens commented at 10:41 PM on August 18, 2015: contributor

@kristovatlas any chance of addressing the comments I made above? (on the diff) If you ignore all the rest, please at least respond to #157 (review)

kristovatlas commented at 2:59 AM on August 19, 2015: contributor

@dcousens: Thanks for your feedback. I already spent a long time editing the BIP based on prior feedback and I'm not really interested in spending more editing for the sake of succinctness, which comes with trade-offs. When I interacted with open source contributors to wallets on this topic, I found that they primarily wanted more detail about the scheme and not less. Keep in mind that the audience for BIPs is not necessarily restricted to people who religiously read the dev mailing list -- not that you are suggesting this, it's just a helpful reference point.

dcousens commented at 3:52 AM on August 19, 2015: contributor

@kristovatlas if possible, I'd prefer to stay away from heresay, as, in my experience, I've only heard the opposite in regards to developer opinion on this BIP.

#157 (review) does not make any sense [to me], although it seems well intentioned, I can't imagine why you have accounted for it, could you clarify that?

The BIP is currently a very long explanation for the following algorithm (pseudocode):

inputs.sort((a, b) => {
  return compare(a.txHash, b.txHash, 32) || a.vout - b.vout
})

outputs.sort((a, b) => {
  return a.value - b.value || compare(a.script, b.script, MIN(a.script.length, b.script.length))
})

Where compare is just a standard lexicographical comparison function, of which there are numerous examples you could give before giving a full python implementation as listed above.

std::lexicographical_compare in C++
cmp in Python 2.7
memcmp in C

Very easy to find, very easy to research. Almost always pointless to re-implement, or even give a pseudo-algorithm for.

I'd really like to see this BIP get through, but as an open source library implementer, it took me more time to decipher the paragraphs behind this BIP than it did to write the ~20 line npm module.

I'm not trying to be hostile, I'm genuinely just trying to improve the ecosystem, so please don't take these comments the wrong way.

kristovatlas commented at 4:20 PM on August 19, 2015: contributor

Okey doke. I don't think this matters at all and is a waste of my time. If you want to fork and make a pull request to my repo, I will promise to review it promptly, however.

split sentences over lines for smaller diffs d9acdcb6b1

human-readable string representation is big-endian 66cb8346fe

sort by prevTxHash in little-endian, descending order, lexicographically 8d2a159496

remove probability, specify behaviour for matching prevOut indices 342058602e

remove mention of information typically found in wallets c351ae0b9f

remove malleability foot note c6ed18d8b2

reword transaction outputs in-line with transaction inputs format c60771d229

remove random 104 64a44180b8

add editor note 5f75c82dc4

dont include pseudo-code for lexicographical sorting 64f321e2c9

Revert "remove malleability foot note"

This reverts commit c6ed18d8b27be10b5f0c5f357969e1b0dbf963db.

1d74463fd9

gmaxwell commented at 11:09 PM on September 3, 2015: contributor

@dcousens Any thoughts on if you will try a revision. What you wrote there looks like a reasonable simplification which could be merged with Kristov's work.

dcousens commented at 11:59 PM on September 3, 2015: contributor

@gmaxwell waiting on https://github.com/kristovatlas/bips/pull/1

endianness not relevant, use byte order 8368e7553c

Merge pull request #1 from dcousens/bip69fixes

BIP69 edits by @dcousens

fe9249ac7d

kristovatlas commented at 2:48 PM on September 11, 2015: contributor

@gmaxwell merged @dcousens's edits. I think this PR is ready to be merged.

dcousens commented at 2:57 PM on September 11, 2015: contributor

ACK

kristovatlas commented at 3:00 PM on September 11, 2015: contributor

Thanks for the editing help, @dcousens

kristovatlas commented at 3:03 PM on September 17, 2015: contributor

@laanwj ping

kristovatlas commented at 6:45 PM on September 18, 2015: contributor

@laanwj ping

luke-jr commented at 6:27 PM on September 19, 2015: member

README.mediawiki and bip-0069/bip-0069_examples.py are missing EOF newlines. Anything else needed before merging this draft?

add EOF newlines per @luke-jr

“README.mediawiki and bip-0069/bip-0069_examples.py are missing EOF
newlines. Anything else needed before merging this draft?” — @luke-jr

42c0650ccb

kristovatlas commented at 9:23 PM on September 19, 2015: contributor

done

luke-jr referenced this in commit bde3793421 on Sep 19, 2015

luke-jr merged this on Sep 19, 2015

luke-jr closed this on Sep 19, 2015

MarcoFalke commented at 7:43 AM on September 20, 2015: member

Created two trivial follow up cleanups: #203 and #204. Feedback is welcome.

luke-jr referenced this in commit 8bc2304705 on Jun 6, 2017