6 ms·

Lots of comments are asking what problem this solves. First, content addressing is the best general solution to exactly-once message delivery in a distributed

by btrask 11y ago

Lots of comments are asking what problem this solves. First, content addressing is the best general solution to exactly-once message delivery in a distributed system. Examples of distributed message protocols include (ahem) email, HTTP and RSS. The alternative, UUIDs, is strictly worse in almost every way (which is to say, if you're currently using UUIDs for anything, consider switching to hashes of the content). Second, content addressing guarantees the integrity of messages, meaning as long as you have the hash, you can get the data from anywhere. This is highly useful for mirroring and failover. Basically, we might be able to solve linkrot to a large degree, and make easier to mirror sites (especially locally, which is useful for high latency and offline). I wrote up a short comparison of this protocol, along with a few alternatives a while back.[1] (Note that the IPFS comparison is incorrect, it should have an /ipfs/ path prefix.) [1] https://bentrask.com/?q=hash://sha256/1e9a6b770ef9f1ca894af47ca7541f8fd36da624631d3fe79ede0cef1e5a0c1f https://bentrask.com/?q=hash://sha256/1e9a6b770ef9f1ca894af4...

DyslexicAtheist 11y ago
"Oh, you wanted to increment a counter. I'm sorry it's not that simple Dave" -- distributed computing literature
- anon4 11y ago
  You just contact the central authorisation server and get a universal authorisation request authorisation. Then, you take the universal authorisation request authorisation token and hand it off to the counter incrementing authorisation server which gives you a counter incrementing authorisation token. Then, you take the counter incrementing authorisation token to your local counter incrementing server and ask it to increment the counter by 1. In turn, your local counter incrementing server checks that your counter incrementing authorisation token was indeed signed by the central authorisation server and issues a counter incrementing operation to one of the 8 central counter incrementing servers. Of course, your local counter incrementing server is itself authorised by the central authorisation server and the counter incrementing authorisation server to issue authoritative counter increment operations; so if its own local counter incrementing authorisation token has expired (5 minutes), it also has to do steps 1-3 to renew its authorisation to perform authoritative counter incrementing operations. This doesn't concern you, as all those requests are buffered so this section is purely informative. Your own authorisation tokens also have expirations (5 minutes for the unviersal authorisation request authorisation token and ~10 seconds for the specific authorisation tokens) so you best issue your requests promptly and make sure to renew the tokens. Should your token expire before you have completed your counter increment request to your local counter increment server, perform steps 2-4 (or 1-4 if more than 5 minutes have elapsed since you acquired your universal authorisation request authorisation token). Expect to receive a counter increment confirmation message within the next 2 full moons by carrier pigeon. Super simple stuff.
  - fla 11y ago
    Don't forget to instantiate a CounterIncrementingAuthorizationTokenFactoryFactory in your local cluster ;)
  - fennecfoxen 11y ago
    > You just contact the central authorisation server No! No!! No!!! First, we're doing distributed computing. There is no central authorization server. There are N authorization servers, and by the time you know for 100% sure whether the majority agree on whether you're authorized, someone has revoked the authorization. So take your authorization token, we'll write it down when you use it, and if you're de-authorized we'll adjust the counter after the fact to compensate, during our periodic audit. But more importantly, the real problem is that your counter increment message was sent to a machine that has been taken offline by an errant backhoe and we don't know whether it took. Fortunately you sent the counter-increment message to three different servers, so once we have time to go through all the counter increment messages to de-duplicate we'll have your count, and the problem today is making sure that we have a full three copies of the message stored instead of just two.
  - DyslexicAtheist 11y ago
    new counter increment pigeon. who dis?
jjtheblunt 11y ago
Content addressing most definitely does NOT guarantee the integrity of a message, because hashes are non isomorphic homomorphisms. Cf. an article on "cryptographic hash"ing, for instance, which are hashes with strong statements about how hard it is to find distinct messages with the same hash, etc. .
- btrask 11y ago
  I'm not sure I understand your criticism, but I should've clarified "content addressing using long, cryptographically secure hashes". Most of the major projects are using SHA-256.
  - jjtheblunt 11y ago
    The point is that hash functions of fixed bit length b have 2^b possible values, but are used to "represent" bit sequences of length longer than b, of which there are more than 2^b values. Collisions necessarily occur, but finding colliding values isn't necessarily easy (cf. cryptographic hashes), which means if you want to tamper with a message, which has an associated hash, without being detected, you're constrained by the hash function to tamperings which produce the same hash.
    - drdaeman 11y ago
      I guess, the most widely used content-addressing system is BitTorrent. Wonder, if anyone had already did a research how many different torrents with the same `info_hash` one can find out there.
      - deleted 11y ago
        [deleted]
      - versteegen 11y ago
        I had to look it up, and found info_hash is the SHA-1 of the 'info' section of the metainfo file, which lists the files and the SHA-1 hashes of each of their pieces. So you are asking how many torrents have exactly the same file data but different metadata. So yes, interesting question. If two torrents differ only in metadata, will any bittorrent clients actually allow the data be shared (without manual intervention like symlinking files)?
ec109685 11y ago
There are applications where you want to be able to update a piece of content of the document without changing how it is addressed.
haberman 11y ago
If you use a message hash as your unique identifier for exactly-once delivery, your messaging system won't let a user send the same message twice, even if they mean to. You could wrap the user's message in some metadata including a uuid to ensure the overall content is distinct from anytime the user previously posted that message. But now you're back at uuids, which you say you don't like.
- redka 11y ago
  A counter solves this without UUID
  - ketralnis 11y ago
    Counters have a host of other problems, like making sure that you never issue the same counter twice in a system without a central authority (or just one that doesn't desire a single point of failure)
- btrask 11y ago
  You need to think about what makes messages distinct. Content addressing will help you as long as you have a rigorous definition of identity, which you might otherwise be doing ad-hoc when you assign UUIDs. If the same message is meaningful at different points in time, your hashed content should include a timestamp (and of course you need to choose an appropriate level of precision). If your message is meaningful in different contents, it needs to reference that context somehow (ideally by hash). The payoff for doing this well is 1. an elimination of double-sent emails, double-posts, etc. (when the software might not know if it went through the first time), and 2. the ability to deduplicate across a network partition, for example if a user makes the same change on their computer and on their phone and then syncs them.
  - zAy0LfpBZLC8mAC 11y ago
    ... except wallclock timestamps for ordering of events in a distributed system is a terrible idea in most cases for the simple reason that (a) it's not a (even close to) guaranteed unique event identifier (the same time happens in many locations), (b) you usually don't have a clock of sufficient precision to even reliably establish a total order of distinct moments and (c) even if you have, that order does not necessarily preserve causality. Now, UUIDs don't solve (b) or (c) either, but at least they actually give you a reliable identifier for events.

by btrask 11y ago

DyslexicAtheist 11y ago

"Oh, you wanted to increment a counter. I'm sorry it's not that simple Dave" -- distributed computing literature

anon4 11y ago
You just contact the central authorisation server and get a universal authorisation request authorisation. Then, you take the universal authorisation request authorisation token and hand it off to the counter incrementing authorisation server which gives you a counter incrementing authorisation token. Then, you take the counter incrementing authorisation token to your local counter incrementing server and ask it to increment the counter by 1. In turn, your local counter incrementing server checks that your counter incrementing authorisation token was indeed signed by the central authorisation server and issues a counter incrementing operation to one of the 8 central counter incrementing servers. Of course, your local counter incrementing server is itself authorised by the central authorisation server and the counter incrementing authorisation server to issue authoritative counter increment operations; so if its own local counter incrementing authorisation token has expired (5 minutes), it also has to do steps 1-3 to renew its authorisation to perform authoritative counter incrementing operations. This doesn't concern you, as all those requests are buffered so this section is purely informative. Your own authorisation tokens also have expirations (5 minutes for the unviersal authorisation request authorisation token and ~10 seconds for the specific authorisation tokens) so you best issue your requests promptly and make sure to renew the tokens. Should your token expire before you have completed your counter increment request to your local counter increment server, perform steps 2-4 (or 1-4 if more than 5 minutes have elapsed since you acquired your universal authorisation request authorisation token). Expect to receive a counter increment confirmation message within the next 2 full moons by carrier pigeon. Super simple stuff.
- fla 11y ago
  Don't forget to instantiate a CounterIncrementingAuthorizationTokenFactoryFactory in your local cluster ;)
- fennecfoxen 11y ago
  > You just contact the central authorisation server No! No!! No!!! First, we're doing distributed computing. There is no central authorization server. There are N authorization servers, and by the time you know for 100% sure whether the majority agree on whether you're authorized, someone has revoked the authorization. So take your authorization token, we'll write it down when you use it, and if you're de-authorized we'll adjust the counter after the fact to compensate, during our periodic audit. But more importantly, the real problem is that your counter increment message was sent to a machine that has been taken offline by an errant backhoe and we don't know whether it took. Fortunately you sent the counter-increment message to three different servers, so once we have time to go through all the counter increment messages to de-duplicate we'll have your count, and the problem today is making sure that we have a full three copies of the message stored instead of just two.
- DyslexicAtheist 11y ago
  new counter increment pigeon. who dis?

jjtheblunt 11y ago

Content addressing most definitely does NOT guarantee the integrity of a message, because hashes are non isomorphic homomorphisms. Cf. an article on "cryptographic hash"ing, for instance, which are hashes with strong statements about how hard it is to find distinct messages with the same hash, etc. .

btrask 11y ago
I'm not sure I understand your criticism, but I should've clarified "content addressing using long, cryptographically secure hashes". Most of the major projects are using SHA-256.
- jjtheblunt 11y ago
  The point is that hash functions of fixed bit length b have 2^b possible values, but are used to "represent" bit sequences of length longer than b, of which there are more than 2^b values. Collisions necessarily occur, but finding colliding values isn't necessarily easy (cf. cryptographic hashes), which means if you want to tamper with a message, which has an associated hash, without being detected, you're constrained by the hash function to tamperings which produce the same hash.
  - drdaeman 11y ago
    I guess, the most widely used content-addressing system is BitTorrent. Wonder, if anyone had already did a research how many different torrents with the same `info_hash` one can find out there.
    - deleted 11y ago
      [deleted]
    - versteegen 11y ago
      I had to look it up, and found info_hash is the SHA-1 of the 'info' section of the metainfo file, which lists the files and the SHA-1 hashes of each of their pieces. So you are asking how many torrents have exactly the same file data but different metadata. So yes, interesting question. If two torrents differ only in metadata, will any bittorrent clients actually allow the data be shared (without manual intervention like symlinking files)?

ec109685 11y ago

There are applications where you want to be able to update a piece of content of the document without changing how it is addressed.

haberman 11y ago

If you use a message hash as your unique identifier for exactly-once delivery, your messaging system won't let a user send the same message twice, even if they mean to. You could wrap the user's message in some metadata including a uuid to ensure the overall content is distinct from anytime the user previously posted that message. But now you're back at uuids, which you say you don't like.

redka 11y ago
A counter solves this without UUID
- ketralnis 11y ago
  Counters have a host of other problems, like making sure that you never issue the same counter twice in a system without a central authority (or just one that doesn't desire a single point of failure)
btrask 11y ago
You need to think about what makes messages distinct. Content addressing will help you as long as you have a rigorous definition of identity, which you might otherwise be doing ad-hoc when you assign UUIDs. If the same message is meaningful at different points in time, your hashed content should include a timestamp (and of course you need to choose an appropriate level of precision). If your message is meaningful in different contents, it needs to reference that context somehow (ideally by hash). The payoff for doing this well is 1. an elimination of double-sent emails, double-posts, etc. (when the software might not know if it went through the first time), and 2. the ability to deduplicate across a network partition, for example if a user makes the same change on their computer and on their phone and then syncs them.
- zAy0LfpBZLC8mAC 11y ago
  ... except wallclock timestamps for ordering of events in a distributed system is a terrible idea in most cases for the simple reason that (a) it's not a (even close to) guaranteed unique event identifier (the same time happens in many locations), (b) you usually don't have a clock of sufficient precision to even reliably establish a total order of distinct moments and (c) even if you have, that order does not necessarily preserve causality. Now, UUIDs don't solve (b) or (c) either, but at least they actually give you a reliable identifier for events.