I wonder if someone can represent the blockchain encryption problem (used to mine bitcoins) as a TSP-metric problem (where TSP = Traveling-Salesman Problem). Any approach or intuition of the idea to do that is welcome.

  • 1
    $\begingroup$ Maybe it is just me missing knowledge, but can you provide a pointer to "the blockchain encryption problem"? And how is that used to mine bitcoins? $\endgroup$ – Maarten Bodewes Feb 29 at 12:19
  • $\begingroup$ @MaartenBodewes I'd suppose that the "blockchain encryption problem" is bitcoin's mining problem (ie finding a nonce such that the hash of the nonce with some data is smaller than some threshold). $\endgroup$ – SEJPM Feb 29 at 12:42
  • $\begingroup$ In theory this is "easy": TSP is NP-hard, so you can map any NP-problem to it which includes bitcoin mining. $\endgroup$ – SEJPM Feb 29 at 12:42
  • $\begingroup$ @SEJPM TSP-metric (euclidean) is NP-complete as Papadimitrious (es.wikipedia.org/wiki/Christos_Papadimitriou) showed in the 80´s. Anyway .. do you know how to implement a TSP for mining bitcoins? $\endgroup$ – Izar Urdin Feb 29 at 18:49

No, it is not possible. To think that it would be possible is surely to make a category error. Mining Bitcoin is not an issue of finding the shortest possible route between successful mining events, nor, by the way, is it encryption (strictly speaking).

There is a common feature, of course, between the TSP and Bitcoin mining: the need to save time. But a time solution to a TSP problem is very different from one in Bitcoin mining because the TSP looks to find the shortest route of all, and we have to prove that it is absolutely the shortest. This is nothing like mining Bitcoin.

| improve this answer | |
  • $\begingroup$ could you explain graphically the difference? If you can add a link to an extended explanation it would be great. THX $\endgroup$ – Izar Urdin Mar 1 at 16:27
  • 1
    $\begingroup$ How does "the need to save time" manifest itself in the Bitcoin mining problem? $\endgroup$ – dionyziz Mar 1 at 16:33
  • $\begingroup$ @dionyziz time = money $\endgroup$ – Patriot Mar 1 at 23:58
  • $\begingroup$ @Patriot I´m not sure at all about that ... the PoW is not simply a lottery, it is a sequence of the previous known transactions of the block. You can calculate this if you can decipher the previous. $\endgroup$ – Izar Urdin Mar 2 at 11:47

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.