Duplicate tx ids

Question

Is there a quick and dirty way to detect all transactions whose tx-id can be found in more than one transaction since the genesis block?

I would also like to see mutated transactions as well although I am not sure if the blockchain keeps a historical track of the mutated transactions.

Answer 1

Is there a quick and dirty way to detect all transactions whose tx-id can be found in more than one transaction since the genesis block?

There are multiple ways to read your question.

Are there cases where the same transaction has been included into the blockchain multiple times?

Yes. There is one recorded instance of the same coinbase appearing twice. The problem this causes is that only one of these can be redeemed. It also makes it possible to reduce a fully-confirmed transaction to one confirmation, though I don't understand the details. BIP34 fixed this.

Are there cases where the same input hash appears in multiple transactions?

Yes. It happens all the time. For example, transaction 9fa3... has two outputs. Those two outputs were spent by two different transactions. Each transaction needed to include the same input hash (though the vout field was different.)

Are there are any known collisions in SHA256?

No.

I would also like to see mutated transactions as well although I am not sure if the blockchain keeps a historical track of the mutated transactions.

It doesn't.

Answer 2

The coinbase transactions e3bf3d07d4b0375638d5f1db5255fe07ba2c4cb067cd81b84ee974b6585fb468 and d5d27987d2a3dfc724e359870c6644b40e497bdc0589a033220fe15429d88599 both exist in two blocks.

This problem was solved in BIP30 so this cannot happen again.

BIP30 also dictates that it is the newest version of these transactions that is spendable.

Answer 3

I've written a NodeJS script that uses Bitcoin Core's REST API to scan up to block 227835, which is the last version 1 block. It takes about half an hour to run and it reports the full list of duplicate coinbase transactions as:

454279874213763724535987336644243549a273058910332236515429488599 91812 91842
5356640744203756384561725255950751537320676481287559742658862468 91722 91880

The script (sometimes when requests timeout, it reports the request for which block failed, so you can see the progress):

const { performance } = require("perf_hooks");
const fetch = require("node-fetch");

const LAST_V1_BLOCK = 227835;
var hashes = [];
var hashes_len = 0;
var block_heights = [];

async function getBlockHash(height) {
  return (await fetch("http://127.0.0.1:8332/rest/blockhashbyheight/" + height + ".json")
    .then((response) => {
      return response.json();
    }).catch((err) => {
      console.log("Retrying " + height);
      return getBlockHash(height);
    }))
}

async function getCoinbaseHash(hash) {
  return (await fetch("http://127.0.0.1:8332/rest/block/" + hash + ".json")
    .then((response) => {
      return response.json();
    }).catch((err) => {
      console.log("Retrying " + hash);
      return getCoinbaseHash(hash);
    }))
}

async function getCoinbaseHashByHeight(height) {
  return (await getCoinbaseHash((await getBlockHash(height)).blockhash)).tx[0].txid
}

const hex_alphabet = Uint32Array.from([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15]);
const hex_encode = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f"];

// I'm forcing big endian, even though order doesn't matter in this code
// It means you can use this code to find the block with the lowest hash
function eightTo32(a) {
  var out = new Uint32Array(8);
  for (var i = 0; i < 8; i++)
    out[i] = a[4 * i] << 24 | a[4 * i + 1] << 16 | a[4 * i + 2] << 8 | a[4 * i + 3];
  return out;
}

function thirty2To8(a) {
  var out = new Uint8Array(32);
  for (var i = 0; i < 8; i++) {
    out[4 * i] = (a[i] >> 24) & 255;
    out[4 * i + 1] = (a[i] >> 16) & 255;
    out[4 * i + 2] = (a[i] >> 8) & 255;
    out[4 * i + 3] = (a[i]) & 255;
  }
  return out;
}

function decodeHex(str) {
  var out = new Uint8Array(32);
  var scratch = new Uint32Array(64);
  for (var i = 0; i < 64; i++)
    scratch[i] = str.charCodeAt(i);
  for (var i = 0; i < 64; i++)
    scratch[i] -= 48;
  for (var i = 0; i < 32; i++)
    out[i] = scratch[i << 1];
  for (var i = 0; i < 32; i++)
    out[i] <<= 4;
  for (var i = 0; i < 64; i += 2)
    out[i >>> 1] += scratch[i + 1];
  return eightTo32(out);
}

function encodeHex(arr) {
  var x = thirty2To8(arr)
  var s = "";
  for (var i = 0; i < 32; i++)
    s += hex_encode[x[i] >>> 4] + hex_encode[x[i] & 15];
  return s;
}

function compareHashes(a, b) {
  for (var i = 0; i < 8; i++)
    if (a[i] < b[i])
      return -1;
    else if (a[i] > b[i])
      return 1;
  return 0;
}

// We need a binary tree
// Taken from https://stackoverflow.com/q/1344500
// Start = 0
// End = length
function locationOf(element, start, end) {
  const pivot = start + ((end - start) >>> 1);
  const arrPiv = hashes[pivot];
  const com = compareHashes(arrPiv, element)
  if (!com) return pivot;
  if (end - start <= 1) {
    if (com == 1)
      return pivot - 1;
    return pivot;
  }
  if (com == -1)
    return locationOf(element, pivot, end);
  return locationOf(element, start, pivot);
}

// Taken from https://stackoverflow.com/q/1344500
function insert(element, height) {
  var l = locationOf(element, 0, hashes_len);
  hashes.splice(l + 1, 0, element);
  block_heights.splice(l + 1, 0, height);
  hashes_len++;
  return 0;
}

async function run() {
  var t0 = performance.now();

  // Process the genesis block out of the loop
  hashes.push(decodeHex(await getCoinbaseHashByHeight(0)));
  block_heights.push(0);
  hashes_len++;

  var pre_hashes = [];
  // Batches of 5 for await
  for (var i = 0, r = (LAST_V1_BLOCK / 5 | 0) * 5; i < r; i += 5) {
    for (var x = 0; x < 5; x++)
      pre_hashes[i + x] = getCoinbaseHashByHeight(i + x + 1);
    for (var x = 0; x < 5; x++)
      pre_hashes[i + x] = await pre_hashes[i + x];
  }
  for (; i < LAST_V1_BLOCK; i++) pre_hashes[i] = await getCoinbaseHashByHeight(i + 1);

  console.log("Done acquiring");

  for (var i = 0; i < LAST_V1_BLOCK; i++)
    pre_hashes[i] = decodeHex(pre_hashes[i]);
  for (var i = 0; i < LAST_V1_BLOCK; i++)
    insert(pre_hashes[i], i + 1);

  console.log("Sorting done")

  for (var i = 1; i < hashes_len; i++)
    if (!compareHashes(hashes[i - 1], hashes[i]))
      console.log(encodeHex(hashes[i]) + " " + block_heights[i - 1] + " " + block_heights[i]);
  console.log("Duplicate check done")
  var t1 = performance.now();
  console.log("Took " + (t1 - t0) + " ms.");
}

run()