First off I remind you I am just a simple C programmer and not a cryptographer. If anybody has the math background to confirm or deny my experimental finding, please post!
I was experimenting with Curve25519 yesterday and I observed a very useful property that allows the creation of multisig.
https://forum.thesupernet.org/index.php?topic=154.msg1262#msg1262Now I doubt it was just in the few cases that I discovered that works. I bruteforce searched thousands of combinations and found a very simple relationship that I believe can be used for arbitrary M of N signatures.
The fundamental property of Curve25519 is that if A and B know each others public key, they can create a shared secret. Let A and B be the private keys and a and b the public keys:
curve25519(A,b) == curve25519(B,a)
I searched and searched on the Internet to find little actual useful info, so I started with the above and my intuition and searched for combinations that created the same result and there were many, but the simplest and clearest was:
Add C and c to the above and denote S_ab to being the result of curve25519(A,b) or curve25519(B,a) (they are the same)
curve25519(A,S_bc) == curve25519(B,S_ac) == curve25519(C,S_ab)!
This relationship is quite useful and it is probably obvious to anybody familiar with curve25519 so maybe I am just getting excited over nothing, but the recommendation is to immediately hash the output S_ab. Presumably to avoid any low entropy sections of the point and once you do this, the above relationship does not work as you end up totally scrambling the location of the point in the finite field. I call this the rawsharedkey and maybe it has been explored in depth so we can get some math proofs of the above relationship.
We also know that curve25519(A,curve25519(B,curve25519(C,seed))) is equal to all the permutations of order, I think this is because the field forms an abelian group, but it has been a long time since I did any abstract algebra so I probably have the terms wrong. It is just a fancy way of saying the order doesnt matter.
So how to use these math properties to make multisig?
Since S_xy is constant for each set of keypairs for each node, these values can actually be cached locally. Of course this means that the presence of S_xy in the output does not mean that either X or Y actually signed anything. Turns out this is fine, as the final step requires the signing node to actively participate and the final output can be processed till the dogs come home:
sha256(seed ^ curve25519(A,S_bc))
sha256(seed ^ curve25519(B,S_ac))
sha256(seed ^ curve25519(C,S_ab))
all the above produce the identical result and proves that A, B and C all signed it with the seed (which should have a timestamp in it) and since it goes through sha256 the output gives no useful info about A, B or C. I am not sure if S_xy is leaking any info to the nodes that get access to it, but I dont think so as it is the output of curve25519 and that's supposed to be hard to reverse.
Since it is safe to publish the final number, A, B and C publish it and everybody can verify if 0, 1, 2 or 3 signers signed it. The enforcement of following the result is beyond the scope of this thread, but this can be put into the NXT core and each node can just use the above to verify whether the payment should be released
Now, how can this be generalized? I feel strongly that the "triangle" relationship can be generalized, but so far my experimental results are not finding the right sequence.
Let me ramble a bit, that sometimes helps
Starting with the fundamental triangle:
curve25519(A,S_bc) == curve25519(B,S_ac) == curve25519(C,S_ab)
Let us replace C,c with D, d:
curve25519(A,S_bd) == curve25519(B,S_ad) == curve25519(D,S_ab)
The problem is these are different values as it is S_ab combined with C vs D, however, we can use the priv/pub equivalence:
curve25519(d,curve25519(C,S_ab)) ?? curve25519(c,curve25519(D,S_ab))
nope, that didnt work, but as expected:
curve25519(D,curve25519(C,S_ab)) == curve25519(C,curve25519(D,S_ab))
which means:
curve25519(D,curve25519(C,S_ab)) == curve25519(C,curve25519(D,S_ab)) == curve25519(B,curve25519(D,S_ac)) == curve25519(A,curve25519(D,S_bc))
Hey! That means there is a 4 signer solution, but this requires multiple signings and then correlations, so not exactly what I am looking for. Anyway I hope to get some math help here so an efficient M of N multisig using curve25519 is possible. Experimentally I found the triangle relationship, which I am not sure if it is trivially obvious or something significant.
James