4 ms·

Smart idea doing the hash choice per-commit. Just make sure that somebody putting in an obscure hash doesn't mess up everybody's usage of the repo if they don'

by AdamN 3y ago

Smart idea doing the hash choice per-commit. Just make sure that somebody putting in an obscure hash doesn't mess up everybody's usage of the repo if they don't have a library to evaluate that hash installed.

gavinhoward 3y ago
I agree. There will be a set of presets of hash function and settings; if BLAKE3 fails, then I'll actually have to add SHA3 or something, with a set of settings, as presets. The per-commit storage will then be an enum identifying the hash and its settings. This will let me do other things, like letting companies use a 512-bit hash if they expect the repo to be large.
- agodfrey 3y ago
  Maybe you’re already aware, but you glossed over something: Since you’re using the hash to locate/identify the contect (you mentioned Merkle and git), if you support multiple hash functions you need some assurance that the chance of collisions is low across all supported hash functions. For example two identical functions that differ only in the value of their padding bytes (when the input size doesn’t match the block size) can’t coexist.
  - gavinhoward 3y ago
    You are absolutely right. And yes, I am aware. Location will actually be done by prefixing the hash with the value of the enum for the hash function/settings pair that made the hash.
    - tczMUFlmoNk 3y ago
      Since you seem to have done a fair bit of research in this area, do you have any opinions or thoughts about the Multihash format? https://multiformats.io/multihash/ https://multiformats.io/multihash/ It fills in some of the blanks in your "prefixing the hash with the value of the enum for the hash" step.
      - gavinhoward 3y ago
        The multihash format is an excellent format that I am tempted to use. However, there are a two general problems: * The spec is not done, and it doesn't look like much has been done. * While I agree with the FAQ that agreeing on a set of hash functions is possible, the format only allows 256 possible hash functions, so it can run out of space, especially since there can be multiple formats of the same function (BLAKE2B and BLAKE2S, for example), and especially since they want to allow non-cryptographic hash functions. Then specifically for my use case: * There is the problem brought up by AdamN [1]: if multihash is supported, an obscure hash may be supported, and that may cause problems. * As an extension of that, once a hash function and set of settings is supported, it's supported forever, so I want to be more picky, and an enum allows me to restrict what is usable. * By using a 16-bit enum, I have more space to grow. * And finally, by using an enum, if my software encounters a repo with a enum value greater than all of the values it knows, it knows that that repo needs a later version of the software, since I will only add enum values. [1]: https://news.ycombinator.com/item?id=38250444 https://news.ycombinator.com/item?id=38250444
- FabHK 3y ago
  > letting companies use a 512-bit hash if they expect the repo to be large. A repo would have to have more than 1e32 documents for a one in a trillion chance of a collision with a 256 bit hash. (Total annual world data production is estimated at less than 1e24 bytes.) A 512 bit hash thus seems overkill for almost all purposes. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem https://www.weforum.org/agenda/2021/05/world-data-produced-stored-global-gb-tb-zb/ https://www.weforum.org/agenda/2021/05/world-data-produced-s...
  - gavinhoward 3y ago
    For normal VCS's, you are absolutely right. And you're actually right for mine, but I decided to redo the math to make sure. My VCS will track things at a finer level than documents. In a C file, it will track individual functions and structs. In a Java file, it will track individual fields and classes. In a Microsoft Word document, it might track individual paragraphs. And in a Blender file, it will track each object, material, texture, etc. individually. Yes, it will handle binary files. Anyway, it will also be designed for non-technical users. To that end, it will hook into the source software and do a "commit" every time the user saves. It will also track individual directories to make renames work. I am a ctrl+s freak, so I save once a minute or more. However, other people are not, so let's assume 10 minutes (for autosave, perhaps). Now let's assume a monorepo for a company of 100,000 people. And let's assume that when they save every 10 minutes, they save one object in one file (also tracked) two directories down. That means they create 5 hashes every 10 minutes (the fifth is the top level). Let's assume an effective 6-hour work day. That's 5 objects times 6 times per hour times 6 hours. That's 180 objects a day per person. That's 18,000,000 total objects per day. Times 5 for days in a week, times 50 for work weeks in a year. That's 4.5 billion. Let's multiply that by 40 for 40 years that the repo exists, which includes some of the oldest software. That's 1.8e11 objects. According to [1], a 128-bit hash would not be enough for the error correction on a disk at that point. However, a 256-bit hash would give us a 10^31 objects before reaching that point, which gives us 10^20 times 40 years of space. Yep, you're absolutely right that 512 bits is overkill. I stand corrected. [1]: https://en.m.wikipedia.org/wiki/Birthday_attack https://en.m.wikipedia.org/wiki/Birthday_attack
MikusR 3y ago
zpaq archiver solves that by including decompression bytecode inside archives. So check if repository supports your algorithm, if not then include it inside your commit.
- tatersolid 3y ago
  Remote code execution by design. What could possibly go wrong?

by AdamN 3y ago

gavinhoward 3y ago

I agree. There will be a set of presets of hash function and settings; if BLAKE3 fails, then I'll actually have to add SHA3 or something, with a set of settings, as presets. The per-commit storage will then be an enum identifying the hash and its settings. This will let me do other things, like letting companies use a 512-bit hash if they expect the repo to be large.

agodfrey 3y ago
Maybe you’re already aware, but you glossed over something: Since you’re using the hash to locate/identify the contect (you mentioned Merkle and git), if you support multiple hash functions you need some assurance that the chance of collisions is low across all supported hash functions. For example two identical functions that differ only in the value of their padding bytes (when the input size doesn’t match the block size) can’t coexist.
- gavinhoward 3y ago
  You are absolutely right. And yes, I am aware. Location will actually be done by prefixing the hash with the value of the enum for the hash function/settings pair that made the hash.
  - tczMUFlmoNk 3y ago
    Since you seem to have done a fair bit of research in this area, do you have any opinions or thoughts about the Multihash format? https://multiformats.io/multihash/ https://multiformats.io/multihash/ It fills in some of the blanks in your "prefixing the hash with the value of the enum for the hash" step.
    - gavinhoward 3y ago
      The multihash format is an excellent format that I am tempted to use. However, there are a two general problems: * The spec is not done, and it doesn't look like much has been done. * While I agree with the FAQ that agreeing on a set of hash functions is possible, the format only allows 256 possible hash functions, so it can run out of space, especially since there can be multiple formats of the same function (BLAKE2B and BLAKE2S, for example), and especially since they want to allow non-cryptographic hash functions. Then specifically for my use case: * There is the problem brought up by AdamN [1]: if multihash is supported, an obscure hash may be supported, and that may cause problems. * As an extension of that, once a hash function and set of settings is supported, it's supported forever, so I want to be more picky, and an enum allows me to restrict what is usable. * By using a 16-bit enum, I have more space to grow. * And finally, by using an enum, if my software encounters a repo with a enum value greater than all of the values it knows, it knows that that repo needs a later version of the software, since I will only add enum values. [1]: https://news.ycombinator.com/item?id=38250444 https://news.ycombinator.com/item?id=38250444
FabHK 3y ago
> letting companies use a 512-bit hash if they expect the repo to be large. A repo would have to have more than 1e32 documents for a one in a trillion chance of a collision with a 256 bit hash. (Total annual world data production is estimated at less than 1e24 bytes.) A 512 bit hash thus seems overkill for almost all purposes. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem https://www.weforum.org/agenda/2021/05/world-data-produced-stored-global-gb-tb-zb/ https://www.weforum.org/agenda/2021/05/world-data-produced-s...
- gavinhoward 3y ago
  For normal VCS's, you are absolutely right. And you're actually right for mine, but I decided to redo the math to make sure. My VCS will track things at a finer level than documents. In a C file, it will track individual functions and structs. In a Java file, it will track individual fields and classes. In a Microsoft Word document, it might track individual paragraphs. And in a Blender file, it will track each object, material, texture, etc. individually. Yes, it will handle binary files. Anyway, it will also be designed for non-technical users. To that end, it will hook into the source software and do a "commit" every time the user saves. It will also track individual directories to make renames work. I am a ctrl+s freak, so I save once a minute or more. However, other people are not, so let's assume 10 minutes (for autosave, perhaps). Now let's assume a monorepo for a company of 100,000 people. And let's assume that when they save every 10 minutes, they save one object in one file (also tracked) two directories down. That means they create 5 hashes every 10 minutes (the fifth is the top level). Let's assume an effective 6-hour work day. That's 5 objects times 6 times per hour times 6 hours. That's 180 objects a day per person. That's 18,000,000 total objects per day. Times 5 for days in a week, times 50 for work weeks in a year. That's 4.5 billion. Let's multiply that by 40 for 40 years that the repo exists, which includes some of the oldest software. That's 1.8e11 objects. According to [1], a 128-bit hash would not be enough for the error correction on a disk at that point. However, a 256-bit hash would give us a 10^31 objects before reaching that point, which gives us 10^20 times 40 years of space. Yep, you're absolutely right that 512 bits is overkill. I stand corrected. [1]: https://en.m.wikipedia.org/wiki/Birthday_attack https://en.m.wikipedia.org/wiki/Birthday_attack

MikusR 3y ago

zpaq archiver solves that by including decompression bytecode inside archives. So check if repository supports your algorithm, if not then include it inside your commit.

tatersolid 3y ago
Remote code execution by design. What could possibly go wrong?