Regarding Prollyferation: Followup to "People Keep Inventing Prolly Trees"

5 days ago (dolthub.com)

People keep inventing Merkle trees, too.

I made the short bibliography of the original bitcoin paper because of Merkle trees. Damn, I wish I'd put $1,000 into bitcoins then; I'd be a billionaire. I thought bitcoin was a Ponzi scheme.

A pure mathematician far from CS, I nevertheless wondered about digital timestamps, and convinced myself they were impossible. Then I went to a talk by Stuart Haber, supported by a paper with funny quotes starting each section. He explained the purpose of an observer to make timestamps work, but they were using a linear linked list.

As a coauthor of the original Macaulay computer algebra system, with some low-level coding chops, it was obvious to me a tree would help here. And there had just been a NYTimes story about how the nascent internet was accelerating research in CS, people would be on vacation for a week and miss entire start-to-finish events.

I stayed up to dawn writing a polite parody of their paper, introducing the use of a tree, emailed it to everyone I recalled had been at the talk, and went to sleep. That's all I ever contributed; I ended up on the joint paper even though my contribution turned out to be a "Merkle tree".

  • > I wish I'd put $1,000 into bitcoins then; I'd be a billionaire. I thought bitcoin was a Ponzi scheme.

    These are not mutually exclusive statements. Actually, this is how Ponzi schemes work ; -)

    (Somehow I never connected Bayer et al. and Bayer & Diaconis. Wow!)

    • It's not a Ponzi scheme, because those have a specific definition. But it does sort of look like one. And all of the "meme" coins seem to be actual, if incredibly short-lived Ponzi schemes.

      3 replies →

    • Yeah, I thought bitcoin could never really be used as a currency because it is inherently deflationary, and therefore the price would only go up...

      I was not wrong...

  • You were basically right about Bitcoin, but tragically mistaken about the wisdom of getting in on the ground floor of the biggest Ponzi(-ish) scheme in history.

Is there any similar algorithm that trades degraded performance for a guaranteed maximum node size? Using fixed size buffers can be more important than average-case performance.