Non-bitcoin cryptography question

[jl777]

jl777, if the originator signed the root hash of the Merkel tree when he provided it to the intermediary, then the intermediary can prove that any fragment(s) of the document was signed by the originator. The originator is the one who breaks the document up into words or characters at the leaves. A Merkel tree is a very efficient structure space wise if the granularity is very high.

I suppose yours of deterministic mapping each hash to a field element and multiplying all together (and the originator signs the product) is more space efficient, but it is I think roughly an order-of-magnitude slower. Why not add instead of multiply since adding is much faster (one assumes hashes are difficult to preimage)?

I just iterare over fixed size chunks of the file, do sha256 and map that hash to field element

in curve25519 field the fmul is the fast operator, millions per second, and is typically called the "addition". both addition and multiply are order independent with unit element and I avoid the zero, so no issues with additive zero vs multiplicative zero

the "multiply" is cmult (complex multiply with montgomery)
even with cmult it does hundreds of thousands per second.

also, by keeping at the 320 bit polynomial form for the fmul, there is only the one fexpand per field element and one fcontract at the end

My guess is that the fmul will be speed competitive with sha256 of the merkle leaves

James

[jl777]

I added some benchmarking:

Code:

#include <sys/time.h>

double milliseconds()
{
    struct timeval tv; double millis;
    gettimeofday(&tv,NULL);
    millis = ((double)tv.tv_sec * 1000. + (double)tv.tv_usec / 1000.);
    //printf("tv_sec.%ld usec.%d %f\n",tv.tv_sec,tv.tv_usec,millis);
    return(millis);
}

int main(int argc,const char * argv[])
{
    int32_t i,j,sblocksize,len; uint8_t *buf; bits320 prod; bits256 tmp,hash;
    struct sha256_vstate md; FILE *fp,*sblocks; double startmilli = milliseconds();
    memset(tmp.bytes,0,sizeof(tmp)), tmp.bytes[0] = 9;
    prod = fexpand(tmp); // start with valid field element. might want to use the unit element
    for (j=0; j<8; j++)
        hash.uints[j] = rand();
    for (i=0; i<10000000; i++)
    {
        hash.bytes[0] &= 0xf8, hash.bytes[31] &= 0x7f, hash.bytes[31] |= 0x40;
        prod = fmul(prod,fexpand(hash)); // multiple field element
        for (j=0; j<8; j++)
            hash.uints[j]++;
    }
    printf("%d expand/fmuls in %.3f milliseconds\n",i,(milliseconds() - startmilli));

on a 1.3Ghz Intel i5: 10000000 expand/fmuls in 2497.819 milliseconds
so 250 nanoseconds on an old laptop
On a server caliber machine, should be around 100 nanoseconds per iteration.

I dont think a quarter of a second overhead for 1TB of data and 1MB sblocks is any issue

James

[TPTB_need_war]

in curve25519 field the fmul is the fast operator, millions per second, and is typically called the "addition". both addition and multiply are order independent with unit element and I avoid the zero, so no issues with additive zero vs multiplicative zero

the "multiply" is cmult (complex multiply with montgomery)
even with cmult it does hundreds of thousands per second.

also, by keeping at the 320 bit polynomial form for the fmul, there is only the one fexpand per field element and one fcontract at the end

My guess is that the fmul will be speed competitive with sha256 of the merkle leaves

Blake2 can do apparently several hundred thousand hashes per second per thread roughly guesstimated for an Intel Xeon.

Since you have to hash each leaf before you multiply, then the multiplies need to be faster then the rest of the Merkel tree other than leaves. Also my other point (you quoted me before I edited my prior post) is that for the intermerdiary and recipient, the Merkel tree is more space efficient because not all the leaves have to provided with the proof.

So seems roughly on par speed wise but Merkel is more space efficient when only a portion of the leaves (i.e. the chunks) are being proved/provided to the recipient.

[jl777]

in curve25519 field the fmul is the fast operator, millions per second, and is typically called the "addition". both addition and multiply are order independent with unit element and I avoid the zero, so no issues with additive zero vs multiplicative zero

the "multiply" is cmult (complex multiply with montgomery)
even with cmult it does hundreds of thousands per second.

also, by keeping at the 320 bit polynomial form for the fmul, there is only the one fexpand per field element and one fcontract at the end

My guess is that the fmul will be speed competitive with sha256 of the merkle leaves

Blake2 can do apparently several hundred thousand hashes per second per thread roughly guesstimated for an Intel Xeon.

Since you have to hash each leaf before you multiply, then the multiplies need to be faster then the rest of the Merkel tree other than leaves. Also my other point (you quoted me before I edited my prior post) is that for the intermerdiary and recipient, the Merkel tree is more space efficient because not all the leaves have to provided with the proof.

So seems roughly on par speed wise but Merkel is more space efficient when only a portion of the leaves (i.e. the chunks) are being proved/provided to the recipient.

Even though I am pretty good at estimating speed of algorithms, I prefer to benchmark based on actual code running vs hypotheticals. It is very easy to overlook effects of the various levels of caching that happens in CPU and system and HDD.

without compiler optimizations:
10000000 expand/fmuls in 2559.064 milliseconds
10000000 sha256(32bytes) in 23867.496 milliseconds

with -O2
10000000 expand/fmuls in 1067.811 milliseconds, about 100 nanoseconds each
10000000 sha256(32bytes) in 7372.751 milliseconds, about 737 nanoseconds
1000 sha256(1MBbytes) in 8808.173 milliseconds, about 8.8 million nanoseconds

With -O2 optimizations, I am getting almost 1.4 million sha256 per second on my blazing fast 1.4Ghz i5. The sha256 of sblock takes almost 9 milliseconds, so just a bit more than 100/second
and 10 million expand/fmul's per second

"seems roughly on par speed wise" not sure what you mean by on par, but 7x to 10x faster seems a different game of golf. And it is literally 4 orders of magnitude faster than the sha256 of 1MB, so clearly some faster hash function is needed for doing TB datasets, if the blake is much faster and is cryptographically strong enough regarding collisions, sounds like a good improvment. But I just cant see anything approaching the 100 nanoseconds speed.

As I estimated, the cost for doing all the field mults is insignificant compared to the sha256 of only 32 bytes(!) or even the HDD data transfer.

As usual it is a speed vs time tradeoff. If you have plenty of time and not much HDD space and dont mind things 10x slower, then merkle tree. [merkle trees add a layer of complication and chance for bugs and also make it harder to explain] If you dont mind using 32 bytes per sblock (1MB) and want the 10 million ops per second, then the fmuls. Keep in mind this was just a lunch break first pass. If space is really so important, then I think I can make it smaller, but really at this point need to hear from OP if this even solves the problem at hand and being 10x faster than sha256 of 32 bytes, I dont think anybody can say the multiplies are too slow.

This is the problem with assuming things that everybody "knows". Sure, use that as a guideline, but I believe my experimental results far more than what is supposed to happen.

That is how I achieve 30 minute sync time for BTC blockchain from scratch. Not a week, not a day, just 30 minutes. It is on a 32GB VPS server with 1gbps connection, but still I think it is a very good result. I used to think BTC blockchain size was a very big problem, now it seems to be a long term issue with time enough to solve. Moore's law wont help, but time to create more efficient solutions will.

At first I thought some sort of ZK with pederson commitments was needed for this (probably since that is what I was looking at for something else). But since I only had half hour for lunch, I tried to come up with something I can code in that time, and a simple set of multiplies was my limit. Hopefully it works. For now I dont have any more time for this, at least till I hear from the OP

James

http://docs.supernet.org/ has first pass docs on the SuperNET API, I used the code from it to create the above solution. It is still a work in progress, but gives a good overview of the scope

[TPTB_need_war]

I wrote blake2, not sha256. Blake2 is 3 - 5X faster than SHA256. I doubt one needs 256-security for this so 128-bit hashes probably suffice, so that would be another doubling in speed.

I think some CPUs now have hardware acceleration for SHA256.

Btw, I wasn't discrediting your contribution. I was just offering another option and comparing the tradeoffs.

[jl777]

I wrote blake2, not sha256. Blake2 is 3 - 5X faster than SHA256. I doubt one needs 256-security for this so 128-bit hashes probably suffice, so that would be another doubling in speed.

I think some CPUs now have hardware acceleration for SHA256.

Btw, I wasn't discrediting your contribution. I was just offering another option and comparing the tradeoffs.

The hashing of raw data will probably take 90%+ of the resources. How exactly the signing and verification of hashes is done is not time sensitive, unless you use really, really slow methods.

My 100 nanoseconds processing per hash is really, really fast, at the cost of 32 bytes per sblock. Your merkle tree would save space, at the cost of more complexity and CPU time. Which method is better cannot be determined in a vacuum, it all depends on the specific requirements of the user.

Also note that my method will work with any hash function that produces 256 per hash, it is totally agnostic whether it is sha256, blake or rot13.

TB data -> hashing -> fmuls

I just did the "-> fmuls" part, with a stub sha256 as the input as the OP stated sha256 was used

James

P.S. This is an intriguing problem and gives me ideas for other usecases, especially the usage of merkletrees for encrypted data transmission

[TPTB_need_war]

The hashing of raw data will probably take 90%+ of the resources.

Not if each chunk not larger than the hash bit width, e.g. 128 or 256-bit. I had stated the chunks could optionally even be each character or word.

Your merkle tree would save space, at the cost of more complexity and CPU time.

For verification by the final recipient, the Merkel tree should be faster if the hash computation time is on par with your fmul+expand, since fewer operations will done, because there are fewer operations due to proving only the subtrees, not every leaf as in your design.

especially the usage of merkletrees for encrypted data transmission

Yeah Merkel trees are another important algorithm in the toolset.

Apparently Ralph Merkel also invented public key cryptography in the 1970s but the journal editors rejected his white paper:

My first paper (and, in fact, the first paper) on public key cryptography was submitted in 1974 and initially rejected by an unknown "cryptography expert" because it was "...not in the main stream of present cryptography thinking...."

[Quickseller]

(I skipped over reading replies after #15 as they are much too technologically advanced for me to understand what is being discussed)
The problem described in the OP sounds a lot like the problem that torrent clients have when they wish to download a large file from a number of "servers" (I don't think this is the proper terminology in regards to torrents, however by "server" I mean from a  host that is uploading a file to other peers) with an unknown reputation. When a torrent client wishes to download a file "x" they will download chunks of the file from a number of servers, and they need to know that the individual chunks of file "x", when put together will actually be a corrupt version of file "x".

I would suggest that you look into how the BitTorrent protocol works, and I believe you will be closer to your solution. My brief research lead me to this research paper, and I believe looking at the below references of this paper may give you additional information for what you are looking for:

[17] S. Knox, D. O’Cearuil, N. S. Holland, and L. Skrba. “Technology Survey: BitTorrent.”
http://ntrg.cs.tcd.ie/undergrad/4ba2.05/group4/index.html

[30] J. A. Pouwelse, P. Garbacki, D. H. Epema, and H. J. Sips, “The BitTorrent P2P File-sharing
System: Measurements and Analysis,” 4th In’ll Workshop on Peer-to-Peer Systems
(IPTPS’05), 2005.

One other thing that I would point out from a non-technical prospective is that a non-technical way to get around your problem is to make an agreement with the entities that you are providing the data to that you would not be held liable for any losses as a result of using such data and/or that you are providing the data on an "as is" basis.

I am unsure if your data provider would be willing to accept potentially liability from your customers in the event they were to make some mistake in sending data to you.