News for hackers. Stuff that matters.
Re:Scuttlebutt social network: a decentralised platform by r3trohack3r on Saturday February 24, 2024 @12:23AM (#39489339)
This isn't entirely true.

Scuttelbutt had some design and scaling issues.

But there wasn't a global database. Each user gets their own blockchain.

Its a network of tiny blockchains where the consensus model was the signature from the private key and the chain of hashes.

Re:Scuttlebutt social network: a decentralised platform by p4bl0 on Saturday February 24, 2024 @02:55AM (#39489949)
Not disagreeing with you, just nitpicking on the use of a word:

What you are describing is simply a signed Merkle tree, not a blockchain. You cannot really call an individual signing it's own ledger a consensus mechanism. Maybe "validity" or "authenticity" would be better terms here.

I know a lot of people make this mistake of labelling anything that has a Merkle-tree like structure a blockchain but it's impractical when you need to talk about the technology rigorously to have a word that meant something precise suddenly encompass so many things, including tools such as Git.

Coming back to Scuttlebutt, even the website of Manyverse, the mobile client, explicitly says "no blockchains", so it seems at least some of the people involved in Scuttlebutt development agree with this.

Re:Scuttlebutt social network: a decentralised platform by jazzyjackson on Saturday February 24, 2024 @04:10AM (#39490255)
right, blocks are specifically the result of a global consensus

if there's not a discrete unit of appended data that all peers agree has happened, there's not a block

"hashchain" maybe, but merkle tree is already plenty precise

Re:Scuttlebutt social network: a decentralised platform by hinkley on Saturday February 24, 2024 @03:49PM (#39495039)
Many of these systems also don’t have a Merkle tree, they have a Merkle linked list. Which I think contributes a lot to the syncing problem. A skip list structure where each node has multiple hashes/identities would let you skip the last five years of edits and pull down only the individual edits for the last month.

The “Merkle tree” I worked on before this blockchain nonsense started was a Merkle DAG, representing a mostly linear state flow with some parallel elements.

Re:Scuttlebutt social network: a decentralised platform by r3trohack3r on Saturday February 24, 2024 @04:49PM (#39495417)
> A skip list structure where each node has multiple hashes/identities would let you skip the last five years of edits and pull down only the individual edits for the last month.

Do you have any references or reading material on this pattern? Would love to learn more.

Re:Scuttlebutt social network: a decentralised platform by hinkley on Saturday February 24, 2024 @06:00PM (#39495925)
Not in crypto, but it’s a linked list structure with a logarithmic number of additional pointers that refer forward (or in the case of a diff algorithm, backward) into the list, to provide closer to log n lookup time.

I think they were invented by Bill Pugh, a professor who also had some noteworthiness in Java concurrency fifteen years ago, which is how I heard of them.

Wikipedia agrees (W Pugh for William)

https://en.wikipedia.org/wiki/Skip_list

So the way I see it, you’d overlay the linear tree with one that refers to a single, recent hash, a much older hash (or another meta node of the same degree) and a roll up delta from that older hash, with a new hash that satisfies both. Then every time the number of records double, you add another layer over the previous one.

Re:Scuttlebutt social network: a decentralised platform by r3trohack3r on Saturday February 24, 2024 @04:13PM (#39495189)
I appreciate the nitpick! Words do matter.

I'll share my definition of these terms, for me they have very precise definitions:

A merkle tree is a specific data structure: https://en.wikipedia.org/wiki/Merkle_tree

> In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" (node) is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) is labelled with the cryptographic hash of the labels of its child nodes. A hash tree allows efficient and secure verification of the contents of a large data structure. A hash tree is a generalization of a hash list and a hash chain.

If you have hashes co-located with data, and data spread throughout the chain, it is not a merkle tree.

A blockchain is a linear chain of hashes of the content in each block of the chain. In a blockchain, for any given block, there is only one valid next block.

When a blockchain is propagated over a network, there is a consensus algorithm used to agree on state of that chain. Bitcoin uses proof-of-work to agree on the next block. Anything that allows multiple nodes to reach consensus on the state of a blockchain is a consensus algorithm. SSB uses proof-of-signature, and the sequence number, as its consensus algorithm. The network reaches consensus on the state of any particular chain by validating the signatures and that the sequence numbers are in the correct order.

Colloquially, blockchains have been conflated with their consensus schemes. When people use the term blockchain conversationally, they generally mean a blockchain that propagates over a network using some sort of consensus algorithm. This conflation of consensus with blockchains has lead to many people in the p2p space rejecting the term blockchain to distance themselves from the crypto hype bubble, even though the data structure itself is quite useful.

Finally there is a Merkle-DAG, introduced by Juan Benet, that acts as a unifying data structure for both blockchains and merkle-trees. Merkle-DAGs can also express novel data structures that are neither a merkle-tree nor a blockchain.

tl;dr: a blockchain is not a merkle-tree, and a merkle-dag might be capable of representing a blockchain but they are separate concepts. A blockchain is independent of its consensus algorithm, although colloquially the two have been conflated.

P.S. Merkle-DAG might be capable of representing git, would be fun to give it a try sometime using something like IPLD.

Re:Scuttlebutt social network: a decentralised platform by p4bl0 on Sunday February 25, 2024 @03:55AM (#39498960)
> The network reaches consensus on the state of any particular chain by validating the signatures

Ok I can see that. It's the distributed consensus problem in a centralized setting. It still feels strange to call that a blockchain but maybe it can be qualified like "centralized blockchain" (which questions the need for such a structure to begin with).

Re:Scuttlebutt social network: a decentralised platform by r3trohack3r on Sunday February 25, 2024 @04:56PM (#39505238)
> "centralized blockchain" (which questions the need for such a structure to begin with).

I’ve seen centralized blockchains used to great effect in ledger contexts where the chain is not synced, but references (hashes) of the chain are shared externally (I.e. transaction ids).

If an external auditor has a set of transaction ids that have been communicated externally, they can later audit the centralized chain and prove it has not been tampered with without having to have the full log of blocks.

Re:Scuttlebutt social network: a decentralised platform by p4bl0 on Sunday February 25, 2024 @06:35AM (#39499973)
> If you have hashes co-located with data, and data spread throughout the chain, it is not a merkle tree.

Yes that's the theoretical structure but in practice its usage almost always implies data co-located with the intermediate hashes, if only because it's used to validate the integrity of a tree of files and directory and it's easier to manipulate a single structure with all the information. That's how it's done in Git internally, as well as in IPFS for example. I believe it's also how Merke-trees are used in some backup/synchronization tools.

> In a blockchain, for any given block, there is only one valid next block.

Yes, but that's just a particular kind of tree, where each node only has one child.

Re:Scuttlebutt social network: a decentralised platform by r3trohack3r on Sunday February 25, 2024 @04:52PM (#39505196)
> Yes, but that's just a particular kind of tree, where each node only has one child.

Yes!

I’m personally building a SSB data structure that forks into a tree, forking to allow writes from each new writer, to allow multi-device writes! It is a multi-writer append database that behaves like a CRDT.

It’s a blocktree, not a blockchain. Which is also expressable as a merkledag.

Re:Scuttlebutt social network: a decentralised platform by nightpool on Saturday February 24, 2024 @01:15PM (#39493757)
Yeah, sorry, when I said "entire database" I was handwaving over "the entire database of posts relevant to them". The Merkle tree structure is the root of the scaling issues which is why I think it's fair to describe it as "bitcoin-like" and it serves as an intuition pump for people to understand why it was so difficult to use on mobile, regardless of whether it was actually quite as bad as Bitcoin or not.