Topic: Non-bitcoin cryptography question (Read 2327 times)

(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:

---

---

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. 

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.


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.


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:

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

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.

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

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.

I added some benchmarking:


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

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, 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)?

Correction: the Merkel tree is also more space efficient (as well as being faster), because the intermediary doesn't specify the hashes for all the leaves when writing a proof.

merkle tree adds complication, not much but compared to 300 lines, measurable. The 300 lines includes the SHA256 and the field multiplication.

but with a merkle tree not sure if it satisfies the requirements of this problem. The originator can be assumed to be non-cooperative and the only one with the entire dataset. If the data is molested I would think we would need to determine if it was the intermediary or the final recipient that modified the data.

How can the intermediary who doesnt have the data use a merkle tree to verify that the final recipient has the right sblock? Since the merkle tree only verifies that all leaves are correct, it seems all we find out is that the data was corrupted, but not who corrupted it. Maybe that is enough if all parties are having signed protocol when the sblocks are delivered.

anyway, interesting problem. need feedback from the OP whether requirements are met. Lunch break is over, back to debugging I go

James

Okay then jl777. Another way to do it is have the originator sign a hash which is a root of a Merkel tree. Then you can break the document into words or even individual characters if you want. And you can send any portions of the document and prove the originator signed those.

I think the issue is that the originator of the data might be antagonistic and not cooperate and put the burden on the intermediary, but it is a good idea to include the signature in the hash of each sblock.

I think just using field multiplication of N different hashes for each sblock will allow to achieve whatever confidence level about collisions, at the cost of more space for this though. Using curve25519 field multiplication is VERY fast. Probably will do more than a million per second on a single core. The limitation will probably be HDD speeds loading the data or the sha256 calcs

James

P.S. Not sure it can get much simpler than 300 lines of C code...

Isn't the simple solution to include the signature of the entire document with each chunk you forward. If the signer claims he provided different text, he will need to produce a document which matches the hash of what he signed, but he can't do that and also lie.

There are usually simpler solutions. Just think out of the box and paradigm shift the problem.

I think the following is a relatively simple way to achieve your goals (at least pretty close to it). It requires the data provider to know how you are splitting up the data, at least at some level of granularity. Each of these blocks of data cant be changed, but you could mix and match any combination of the granular block.

So if you have a terabyte total data, then say 1MB is the smallest block. you would need 1 million hashes, but with a 30,000:1 reduction in size, maybe it is acceptable. It is a tradeoff decision that doesnt affect the calculation. The larger the smallest block (lets call it a sblock) the less flexibility to distribute it, the smaller the sblock the more flexibility, but also more elements need to be stored.

The data creator will need to know the size of the sblock and apply the same calculations as you do and then sign it so you have proof that is what was delivered.

For each sblock worth of data (we assume the last block is zerofilled) do SHA256 hash and then treat that as a curve25519 field element. Five bits will need to be hard coded, but there are still 251 bits and odds of collision are extremely small.

The following code assumes a 64bit CPU and should be close to a working sblocks calculation:


I didnt have a chance to verify it, but all it is doing is calculating SHA256 hash of each sblock, mapping it to a field element and multiplying it for a combined value. The field operations work at the 320 bit size so the 256 bit hash needs to be expanded and contracted.

Since it is a purely field multiplication, it has no other protections, signatures and whatnot will need to be added on top of this. Note that it is unordered as the fmul is just a pure multiply, if you need it to be ordered, then just include the sequence number into the sha256 calculation.

It is totally self contained portable C so save to a file, then gcc it to make the executable. Output is an sblocks file that has the corresponding hash for each sblock along with the total at the end.

Hopefully it works for what you need. It is just quick proof of concept code, but if any bit is changed in any of the sblocks, the hash will change which will change the combined product. By committing to the sblock hashes, you can prove that you didnt corrupt the data you got as long as the data provider also runs the same program and signs it. Any subset that is delivered can be verified independently to match your posted set of sblock hashes.

I think that satisfies your requirement?

James

P.S. If chance of collision (around 1 in 2^120) is too high, then a second hash can be used to create two elements per sblock. Odds of two different hash collisions with the same data is vanishingly small.

I think the hashes need to have some sort of algebraic structure and not just be random, so Pederson commitments seem to be part of the solution.

The part that I am unclear on is if you are not storing the data, but at some point need to provide all the data, that seems mutually exclusive.

But if you just need to be able to prove you didnt change the data, then by showing that your hashes add up to zero and it matches the combined hash from the data source, this seems possible

The data source would need to sign the combined hash.

http://crypto.stackexchange.com/questions/11923/difference-between-pedersen-commitment-and-commitment-based-on-elgamal?rq=1

Also, it seems unrelated, but the maths behind the Dining Cryptographers might be helpful.

James

Onkel - I like.


How about, if he kept the complete last block of data, as well as the last signed statement, so it would not be possible for him to cheat. Since he can show that it does actually hash to the final hash which is signed by Alice. And he can't change that block of data without performing a successful pre-image attack.

Actually I'm not sure how much of the final block of data he would need to keep. Maybe just the final 64 bytes. Since that alone would also require a pre-image attack to break?

What about the following approach:
Assume that you split the data into relatively few chunks without reordering parts, and that the original source of the data computed and signed a SHA-256 hash over the whole data.
Then you could run SHA-256 over the whole dataset, recording the intermediate state of the hashing algorithm wherever you split the data.
SHA-256 runs on 512-bit blocks, so if you split at a block boundary, you only need to note the values in the hashing registers at that point.
If you split the data within a block, you need to note the hashing register values before the block, plus the 512 bit block itself.
Each data recipient receives the states before and after his block in addition to the block data, so they can check whether their pieces are ok. They need to provide you with a signed statement about this fact.
Now you only have to archive these signed statements and the block boundary states of the hashing engine. Since the last boundary state is equal to the hash signed by the original author, these pieces together can be used to prove that you did not tamper with the data.

I see two possible issues with this approach, though:
1. You would disclose a little more of the data to each recipient since you have to cut at 512-bit boundaries. I don't know whether that's a problem, or whether you can nudge your data source to deliver the data in 512-bit chunks, for example by padding each record to a multiple of 64 bytes.
2. Data recipients could claim that you colluded with the recipient of the last block so that he signs an untrue statement about the final hash value. Since the data integrity is only proven when the final hash of the last block is equal to the hash signed by the original data source, this might be a problem. It is also possible to collude with a recipient that got an earlier blocks, but you could cheat only on recipients before the one you colluded with.

I don't know whether there's an easy way of fixing the last issue, and maybe there are more issues than I see at the moment :-(

Onkel Paul

Yep.

CT is Confidential Transactions. It's his system for showing that the sum of the inputs of a txn add up to the sum of the outputs, without revealing any of the values. He's implemented it in his Elements sidechain.

https://bitcointalksearch.org/topic/confidential-transactions-content-privacy-for-bitcoin-transactions-1085273

And the bit that I thought might be helpful to you is :


..

Yes he would. He's bad ass.

This is the reason I started this thread.

I've not heard of "Pallier", but I'm going to go Google it right now.

I believe that what I'm looking for is exactly what you're describing where:
Hash(X+Y+...) = Hash(X) + Hash(Y) + Hash(...)

I didn't know if such a hash existed, but if it does I think that would be exactly what I need.

By the way, when you say gmax, do you mean gmaxwell?  And what is a CT?
(Honestly, I was really hoping that gmaxwell would see and take an interest in this thread. I suspect that if there is a solution to my problem, he knows exactly what it is.)

What about some kind of homomorphic hash functon ?

Hash(X+Y) = Hash(X) + Hash(Y) (Doesn't Paillier do something like this.. ? Or whatever hash function gmax uses in his CT.)

Then Alice signs the Hash(X+Y+...) and you can show that the sum of all your little hashed pieces, adds up to the hash of the big piece. Which is signed by Alice.