diff options
| -rw-r--r-- | bip-0069.mediawiki | 44 |
1 files changed, 19 insertions, 25 deletions
diff --git a/bip-0069.mediawiki b/bip-0069.mediawiki index d265aae..e01a792 100644 --- a/bip-0069.mediawiki +++ b/bip-0069.mediawiki @@ -61,31 +61,21 @@ In the event that future protocol upgrades introduce new signature hash types, c 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. -===Lexicographical Sorting=== - -Ordering of inputs and outputs will rely on the output of sorting functions. -These functions can be defined as taking two inputs or two outputs as parameters and returning their appropriate ordering with respect to each other. - -Byte arrays must be sorted with an algorithm that produces the same output as the following comparison algorithm: - - <nowiki>#returns -1 if barr1 is lesser, 1 if barr1 is greater, and 0 if equal - def bytearr_cmp(barr1, barr2): - pos = 0 - while (pos < len(barr1) and pos < len(barr2)): - if (barr1[pos] < barr2[pos]): - return -1; - elif (barr1[pos] > barr2[pos]): - return 1; - pos = pos + 1 - #the shorter array will be ordered first - if (len(barr1) < len(barr2)): - return -1 - elif (len(barr1) > len(barr2)): - return 1 - else: - return 0</nowiki> - -N.B. These comparisons do not need to operate in constant time since they are not processing secret information. +===Lexicographical Ordering=== + +Lexicographical ordering is an algorithm for comparison used to sort two sets based on their cartesian order within their common superset. +Lexicographic order is also often known as alphabetical order, or dictionary order. + +Common implementations include: + +* `std::lexicographical_compare` in C++ [5] +* `cmp` in Python 2.7 +* `memcmp` in C [6] +* `Buffer.compare` in Node.js [7] + +For more information, see the wikipedia entry on Lexicographical order. [8] + +N.B. All comparisons do not need to operate in constant time since they are not processing secret information. ===Transaction Inputs=== @@ -159,6 +149,10 @@ Outputs: * [[https://github.com/OpenBitcoinPrivacyProject/wallet-ratings/blob/master/2015-1/criteria.md|2: OBPP Random Indexing as Countermeasure]] * [[https://github.com/aantonop/bitcoinbook/blob/develop/ch05.asciidoc|3: Mastering Bitcoin]] * [[https://en.bitcoin.it/wiki/Script|4: Bitcoin Wiki on Script]] +* [[http://www.cplusplus.com/reference/algorithm/lexicographical_compare|5: std::lexicographical_compare]] +* [[http://www.cplusplus.com/reference/cstring/memcmp|6: memcmp]] +* [[https://nodejs.org/api/buffer.html#buffer_class_method_buffer_compare_buf1_buf2|7: Buffer.compare]] +* [[https://en.wikipedia.org/wiki/Lexicographical_order|8: Lexicographical order]] ==Implementations== |