Post
Topic
Board Development & Technical Discussion
Re: Non-bitcoin cryptography question
by
jl777
on 17/02/2016, 21:57:02 UTC
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