4

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.

  • Are you asking for duplicate transactions, that is 2 transactions with the same id? If so there aren't any. – ike Dec 26 '14 at 18:39
  • @ike how did you come up to this conclusion? Tx-ids are not supposed to be unique bitcointalk.org/index.php?topic=28387.0 – Doug Peters Dec 26 '14 at 18:47
  • They are sha-256 hashes, and it would take more computing power than exists in the world to create one deliberately. You want to look for an improbable scenario to make sure it didn't happen? I'm sure there are people who've searched and found none; if there was, we'd hear about it. – ike Dec 26 '14 at 18:49
  • In the same way that I didn't just generate your private key on my computer. – ike Dec 26 '14 at 18:50
  • @ike I understand that the propabilty for this to happen is close to zero but not zero and that the 55 million txs that took place since genesis in total is not even close to what it would normally take to brute-force the sha256 algo, all I am asking is if there is a handy way to query the bitcoin network for such scenarios. – Doug Peters Dec 26 '14 at 19:03
5

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.

| improve this answer | |
  • Thanks, Nick. "There are multiple ways to read your question." What I need is a fast way to query the blockchain: SELECT TxId, COUNT(*) c FROM blockchain GROUP BY TxId HAVING c > 1; – Doug Peters Dec 26 '14 at 22:28
  • @DougPeters Is that different from the first interpretation of your question? – Nick ODell Dec 26 '14 at 22:31
  • Not really, I was just wondering if you are aware of a neat way to achieve this without having to look it up on blockchain.info or any other third-party service. – Doug Peters Dec 26 '14 at 23:52
0

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.

| improve this answer | |
0

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()
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.