5 ms·

Another fundamentally new data structure developed in the last 20 years is the blockchain. Yes, it's overhyped in many ways, and the word "blockchain" itself is

by lacker 6y ago

Another fundamentally new data structure developed in the last 20 years is the blockchain. Yes, it's overhyped in many ways, and the word "blockchain" itself is often used in a nonsensical way, but the fundamental principle of a chain of blocks with proof-of-work included really is a data structure that solves the problem of untrusted coordination in a novel way.

deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
ben_w 6y ago
Perhaps. I’ve seen the chain-of-hashed-commits in version control software being described as an antecedent of the bitcoin style of blockchain, though I don’t know enough about the inner workings of any version control system well enough to compare, let alone the ones in use 20 years ago. Edit: did I misread the title the first time, or has it changed from “the last 20 years” to “the last 35”?
- jcranmer 6y ago
  The distributed version control systems you're talking about (Bazaar, Mercurial, and Git) all come out within a few weeks of each other in 2005. The chaining hash system for VCSes is either new or obscure before these systems adopt them: the major prior systems like RCS, CVS, and SVN instead rely on a central database with more-or-less sequential revision numbers.
dreamcompiler 6y ago
Blockchains are glorified Merkle Trees (and in the case of Bitcoin, with proof-of-work added for zero-trust distributed operation). The data structure is not new. The name is. https://en.wikipedia.org/wiki/Blockchain#History https://en.wikipedia.org/wiki/Blockchain#History
- petertodd 6y ago
  The parent said 20 years, which is just barely long enough to to be the time for which reasonably secure hash functions have been available. If they had said 30 years, they'd have an excellent argument. Chains of blocks and merkle trees are distinguishable from linked lists and binary trees purely by the use of hash functions instead of pointers. But that turns out to be really powerful in a way that the pointer versions aren't, if those hash functions are cryptographically secure.
  - littlestymaar 6y ago
    Being “cryptographically secure” is a relative thing: during the 90s, md5 was cryptographically secure, until it wasn't in the early 2000s. What we take for granted in terms of cryptographic security could collapse after one breakthrough (that's why SHA-3 was designed completely different from SHA-2, to have a replacement handy when the later will be broken).
    - petertodd 6y ago
      The difference is that with MD5, attacks were found relatively quickly. Introduced in 1992, and by 1996 cryptographers were already recommending that people switch to a replacement such as SHA-1 or RIPEMD-160. SHA256 meanwhile was introduced in 2001, and since then no significant attacks have been found. So not only has it withstood attack for much longer, cryptography has advanced greatly compared to what we knew in 1992. That still isn't a guarantee of future success. But look at it this way: I don't think you could have introduced Bitcoin in 1998. Hash functions were just too new to be trusted to the extent that Bitcoin requires.
      - littlestymaar 6y ago
        Cryptography as a field advances and the next generations are better than the previous. But even if md5 was pretty poor compared to modern hash functions, AFAIK there is still no working preimage on md5 (correct me if I'm wrong, maybe there's been recent development I'm not aware of), which means bitcoin would still be fine if it was launched in 1995 with md5 as its hash function! (assuming it had transitioned to a better scheme later to avoid collisions attacks). In fact bitcoin is a pretty good counter-example to your point. It was launched too early, with a poor hash function[1], and yet is still a success. [1] because bitcoin didn't used a brute-force resistant hash function, Satoshi's dream of “everyone is a miner” quickly disappeared a was replaced by a monopolistic cartel of professional miners.

by lacker 6y ago

deleted 6y ago

[deleted]

deleted 6y ago

[deleted]

ben_w 6y ago

Perhaps. I’ve seen the chain-of-hashed-commits in version control software being described as an antecedent of the bitcoin style of blockchain, though I don’t know enough about the inner workings of any version control system well enough to compare, let alone the ones in use 20 years ago. Edit: did I misread the title the first time, or has it changed from “the last 20 years” to “the last 35”?

jcranmer 6y ago
The distributed version control systems you're talking about (Bazaar, Mercurial, and Git) all come out within a few weeks of each other in 2005. The chaining hash system for VCSes is either new or obscure before these systems adopt them: the major prior systems like RCS, CVS, and SVN instead rely on a central database with more-or-less sequential revision numbers.

dreamcompiler 6y ago

Blockchains are glorified Merkle Trees (and in the case of Bitcoin, with proof-of-work added for zero-trust distributed operation). The data structure is not new. The name is. https://en.wikipedia.org/wiki/Blockchain#History https://en.wikipedia.org/wiki/Blockchain#History

petertodd 6y ago
The parent said 20 years, which is just barely long enough to to be the time for which reasonably secure hash functions have been available. If they had said 30 years, they'd have an excellent argument. Chains of blocks and merkle trees are distinguishable from linked lists and binary trees purely by the use of hash functions instead of pointers. But that turns out to be really powerful in a way that the pointer versions aren't, if those hash functions are cryptographically secure.
- littlestymaar 6y ago
  Being “cryptographically secure” is a relative thing: during the 90s, md5 was cryptographically secure, until it wasn't in the early 2000s. What we take for granted in terms of cryptographic security could collapse after one breakthrough (that's why SHA-3 was designed completely different from SHA-2, to have a replacement handy when the later will be broken).
  - petertodd 6y ago
    The difference is that with MD5, attacks were found relatively quickly. Introduced in 1992, and by 1996 cryptographers were already recommending that people switch to a replacement such as SHA-1 or RIPEMD-160. SHA256 meanwhile was introduced in 2001, and since then no significant attacks have been found. So not only has it withstood attack for much longer, cryptography has advanced greatly compared to what we knew in 1992. That still isn't a guarantee of future success. But look at it this way: I don't think you could have introduced Bitcoin in 1998. Hash functions were just too new to be trusted to the extent that Bitcoin requires.
    - littlestymaar 6y ago
      Cryptography as a field advances and the next generations are better than the previous. But even if md5 was pretty poor compared to modern hash functions, AFAIK there is still no working preimage on md5 (correct me if I'm wrong, maybe there's been recent development I'm not aware of), which means bitcoin would still be fine if it was launched in 1995 with md5 as its hash function! (assuming it had transitioned to a better scheme later to avoid collisions attacks). In fact bitcoin is a pretty good counter-example to your point. It was launched too early, with a poor hash function[1], and yet is still a success. [1] because bitcoin didn't used a brute-force resistant hash function, Satoshi's dream of “everyone is a miner” quickly disappeared a was replaced by a monopolistic cartel of professional miners.