This work is licensed under a Creative Commons Attribution 4.0 International License.
To do a Schnorr multisignature, you just list all the signatures that went into it, and the test key is just adding the all the public keys together. Which gives you pretty fast, though totally non anonymous, voting, with no need for an elaborate, ingenious, and difficult to understand key distribution system.
Supposedly Schnorr multisignature can be done on ED25519 , but I do not see any useful information on how to do it, and Libsodium fails to mention Schnorr.
However we can easily do it with ristretto25519.
Bernstein explains how to do Schnorr, and briefly visits Schnorr multisignature.
The group operation where one obtains a third elliptic point from two elliptic points is represented by addition, A=B+C, capitals represent members of the group, (elliptic points, public keys), lower case represents integers modulo the order of the group (scalars, private keys), and h() is a hash function that maps an arbitrary stream of arguments of arbitrary type to an integer modulo the order of the group.
An upper case letter represents the result of multiplying the base point of
the group by the value represented by the lower case letter. Thus if
B_{base} is the base point then K=kB_{base}\,
h(\cdots) is hash function that generates an integer modulo the order of the group (hence our use of h rather than H) from an arbitrary stream of arguments of arbitrary type. It is hard to reverse, the only efficient way of reversing it being to guess all possible pre images from which it might be constructed..
Signer secret key is k, his public key is K
Generate an unpredictable r from the message and the secret key. If we ever use the same r with two different values of c, we reveal our public key, which is why we make r depend on the same message as we are signing.
we could use some randomness to generate the konce (key used once, single use secret key), but this would mean that we would sign the same thing twice with two different signatures, which in a much signed item, such as a key or a Zooko id, is undesirable.
Compute r = h(k,M), a per message secret scalar. Or r can be an unpredictable secret scalar, randomly generated, but we have to make sure it is truly random and never repeated, which is apt to fail because of computer determinism.
Compute R, a per message elliptic point, a Konce, meaning an elliptic point that can be used only once, never to be reused because made public.
Compute c = h(R, Message)
Compute s = r+c*k\,
Note that:
S= R+c*K
signature is c, s
Obvious problem with multisig – you need proof that each putative signer is able to produce a singlesig, hence no space advantage for konces, which is the major crypto currency use. but for voting on the Paxos protocol, major advantage, since the singlesig is apt to be durable and cached, so the signature signifying approval of the blockchain is single Schnorr signature connected to a possibly large collection of individual signing keys. To prove the multisig on a new block is valid, you need to have and have checked a single sig for each of the signatories, but it does not have to be a new singlesig. It can be an old cached singlesig, so you don’t need to download and check each of the singlesigs with each new block. You only need to check a single signature, assuming you already have old singlesigs.
So, Schnorr multisig, at least in the simple version, presupposes a large existing data structure with good cryptographic properties, presumably a Merkle-patricia tree, listing each party entitled to sign, the self signed signature of that party, and the voting weight and voting rights of that party, and the hash at the root of that tree is a Schnorr multisig.
This, of course, occupies slightly more space than the simple tuple of signatures, but has the advantage that it does not need to change very often, and usually only a small part of it needs to change, while the multisig by itself is relatively small.
But it is not that small. For each possible multisig, you have to list the keys of all the signers, and then look up their rights in the Merkle patricia tree, which is OK if the members of the board are hiring the CEO, but is going to suck mightily if the shareholders are electing the board.
However, chances are in practice, it will commonly be the case that the same group votes over and over again, so, if space and verification time is a concern, you can record previous multisigs and their verification in the Merkle tree, and record the signatures of the latest signing as a delta on some past signature, and do the verification as a delta on some past verification.
Suppose you are doing the Paxos protocol, and every consensus block has to be signed by one hundred peers, every few minutes. Well, you are still going to have to verify the single sigs of the peers signing the group signature, which gives you no savings in time or space over simple tuple of singlesigs. You are still going to have to verify one hundred peers. But if it is usually the same clique signing each each time, it will take you very little time or space to prove that this consensus hash was signed by the same clique as signed the other hundred consensus hashes, which you verified a long time ago, and do not need to repeat the verification. Of course their voting rights might have changed, but if the cliques do not change much, their voting rights probably don’t change much, so you don’t have to do full verification every single time.
If the latest sig is compatible with the current and older voting rights, the sig should reference the older voting rights Merkle-patricia tree of voting rights, and the peers should validate it on the basis of the current voting rights, thus validating that the older voting right suffices. This could produce a false signature and a fork if the voting rights radically change, and old voters don’t like the change, but in such a large scale public event, it will be highly visible and detected. Each client wallet when talking a client wallet on another fork will discover that its root is out of date. We implement default wallet behavior to accept the root with the most recent voting rights list, and of two roots with the same voting rights list, the root most recently signed.
Kevin and Josephine have private keys k_{Kevin} and k_{Josephine}, and public keys K_{Kevin} and K_{Josephine}, and want to generate a multisig to verify to a verifier that both of them signed
Often the checker does not know nor care whether there are multiple co-signers, because the co-signers have already generate an assertion that (K_{Kevin}+K_{Josephine}+\dots) is the public key, and hence does not have to check the singlesig.
If there are quite a few signers, this should be implemented as server-client.
Each of the clients submits the signing key and a konce (key used once),
server replies with
K=\sum\limits_{client}K_{client}, the sum of all signing keys
R=\sum\limits_{client}R_{client}, the sum of all konces
and c=h(R, Message), the value to be signed.
Each of the clients checks c and returns s_{client}
Server replies with
s=\sum\limits_{client}s_{client}\,
Each client checks the signature c, s
For a two party signature, this collapses to a simpler algorithm. Client sends his konce. Server returns s_{server}, the sum of all signing keys, and the sum of all konces. Then client computes the signing key, returns it, and the server checks to see if it works. Should be a three packet handshake.
It is commonly the case that one party is the payee or beneficiary of the thing being signed, an the other party does not particularly need or want the signature, other than he needs to know it exists for his records, and may need to resend the signing secret, accompanied by the signing key and the identifier of the thing being signed.
In this case, the payee sends the konce (key used once, the single use secret), and the payee sends the konce, and does not need the beneficiary’s konce, nor the completed signature, and treats the transaction as completed, because he has seen the thing being signed, and signed it. Doing it the other way around adds an extra point of failure.
For a large number of parties, you are going to have hold the protocol open for a considerable time.
For a vast number of parties, you are never going to get everyone to complete the protocol all the way through, so have to use threshold cryptography, where if everyone gets a enough information, even if they do not get all of it, they can calculate the signature.
A threshold signature has the interesting feature that it is a randomness beacon. If there is one honest participant party to the signing it generates a random value unpredictable to all participants, This has obvious utility in selecting the witness set and leader in blockdag algorithms equivalent to Practical Byzantine Fault Tolerant Consensus, and in distributing discrete shares in a way that is fair and on average over time approximates continuous stake as closely as possible
The participants sign off on assertion that their stake is such and such, and the signature itself controls the random distribution of fractional voting shares in the next signature as whole shares, so that voting shares, as nearly as possible, approximate ownership shares.
This is not in fact a useful discussion of Threshold signatures, so much as a list of links. I don’t entirely trust myself to implement threshold signatures.
Suredbits describes the FROST algorithm for Schnorr distributed key generation and signing. This algorithm is not robust. If any one of the participants goes down in the middle you have to start all over, but it is clean, simple, and easy to understand.
Each of the participants acts as the trusted dealer for his own share, hands out shares in it to everyone else, and the final key is the sum of everyone’s share.
This description is easily the most intelligible description of distributed key generation and signature generation that I have read, because it is adapted to the special case of Schnorr signatures, which have the huge advantage of linearity. But, not robust.
The practical limit for non robust schemes is about fifty participants. If you have a hundred participants it keeps starting over and over again, and eventually this causes more and more people to drop out in the middle as they lose patience.
Practical Large Scale Distributed Key Generation references Revisiting the Distributed Key Generation for Discrete-Log Based Cryptosystems which references Schnorr signatures.
It is a follow up to the (unscalable and arguably inherently centralized) Secure Distributed Key Generation for Discrete-Log Based Cryptosystems
The basic algorithm is that you generate a distributed key, from which a subset of the key recipients can generate a Schnorr signature.
Revisiting the Distributed Key Generation for Discrete-Log Based Cryptosystems gives reasonably detailed instructions for implementing threshold Schnorr, without any trusted central authority but assumes various cryptographic primitives that we do not in fact have, among them a reliable broadcast channel.
A key cryptographic primitive in threshold signatures, and indeed in almost every group cryptographic protocol, is the reliable broadcast channel – that any participant can reliably send a message that is available to all participants.
In actual practice we have unreliable point to point two party communications, from which we have to construct a broadcast channel.
Practical applications of these cryptographic protocols seem to be relying on a trusted broadcaster, who is apt to be untrustworthy when there is money, power, or valuable secrets lying on the table.
Trouble is that in practice, certain messages are likely to be hidden from certain participants, and other participants will be unaware that they are hidden, or they will receive a discrepant message and incorrectly believe they are receiving the same message as others.
In a large group, one can assume that more than half the participants are honest, so one can construct a broadcast channel using the Paxos protocol.
Every distributed cryptographic protocol needs a secure broadcast channel, and every blockchain is a secure broadcast channel.
One of the requirements of secure reliable broadcast channel is that it stays up. But a secure broadcast channel for a lightning type transaction is going to be created and shut down. And if it can be legitimately shut down, it can be shut down at exactly the wrong moment for some of the participants and exactly the right time for some of the participants. Hence the use of a “trusted” broadcast authority, who stays up.
We could attain the same effect by a hierarchy of secure reliable broadcast channels, in which a narrow subchannel involving a narrower set of participants can be set up on the broader channel, and shutdown, with its final shutdown signature available in the broader channel, such that someone who has the right code can find on the durable broadcast channel, the signature he needs.
But interesting protocols are likely to involve small groups for which we want the transaction to fail if any of the participants are defecting.
For example, the lightning protocol is cryptographically enforced correspondence banking, and an eternal problem in correspondence banking is insider check kiting. A shill sends a check to another shill, so that one correspondence banker can scam another correspondence banker, so the group attempting to organize the transaction is going to consist of two shills, one scammer, one pigeon, and one innocent third party roped in to obscure who is doing the scamming and who is being scammed, giving a majority of three evil participants against two good and trusting participants.
By and large, the more money and power that is on the table, the smaller the group engaging in the cryptographic protocol is apt to be.
We want the transaction to fail in such cases. Generalizing to all group cryptographic protocols, we want the broadcast channel to fail and to be seen to fail in such cases.
The Byzantine Paxos protocol is designed for a large group and is intended to keep going permanently in the face of the hardware or software failure of some participants, and Byzantine defection by a small conspiracy of participants.
For a reliable broadcast channel to be reliable, you are relying on it to stay up, because if it goes down and stays down, its state for transactions near the time it went down cannot be clearly defined.
For a reliable broadcast channel to be in a well defined state on shutdown, it has to have continued broadcasting its final state to anyone interested for some considerable time after it reached its final state. So you are trusting someone to keep it going and available. In this sense, no group cryptographic transaction can be entirely trustless.
I intend that the rho blockchain will primarily a notarization system that just happens to special case notarizing rhocoin transactions. The notaries will be a collection of durable broadcast channels, each one typically maintained by a single host, albeit a notarization will not be evidence usable on the blockchain until its notary block is Merkle chained by the blockchain. If the blockchain automatically trusts notary signatures, they will rapidly cease to be trustworthy. The chain, not the signature, makes it officially official. The notary signature and oid is merely a promise to make it official. The blockchain will treat notaries as untrusted, so that everyone else can treat them as trusted at low risk.
According to Practical Large Scale Distributed Key Generation their algorithm is of order {[log (n)]}^3, meaning it should produce a Schnorr signature for thousands of voters with hundreds of thousands of shares, in a a potentially decentralized manner, without a trusted dealer, making it useful for digital corporations, and capable of electing producing a chain of signatures (shareholders sign the board, board signs the CEO, CEO signs every corporate officer identity, CEO organizes the election of the board), capable of being evaluated by everyone interacting with the business over the net.
Obviously the reliable broadcast protocol of such a very large scale key generation will look more like a regular blockchain, since many entities will drop out or fail to complete directly.
Blind Schnorr signatures are vulnerable to the Wagner attack, which can be defeated by refusing to do large numbers of blind signatures in parallel, and/or randomly failing to complete some blind signatures.
Signer secret scalar k. Signer public point K=k*B. B is base point.
Signature is scalar s and point R, such that S = s*B = h(R, Message)*K+ R
Generate random secret scalar r, public point R=r*B
calculate public scalar s = h(R, Message)*k + r$
Reveal s and R for message.
In pairing based cryptography the computational Diffie–Hellman problem is believed to be infeasible while the simpler decisional Diffie–Hellman problem can be easily solved using the pairing function.
In a cryptographic group, given G, xG, and yG it is hard to find xyG, unless you know x or y.
In a pairing based group, given G, xG, yG and xyG you can easily verify that xyG is correct, even though you are unable to calculate the correct value.
Pairing based cryptography can do all sorts of really cool things, and I am not sure how fast it can do them, but we do not in fact have any obvious need for it.
We want money payments to operate in private invitation only messaging and blog groups, without causing the group to be exposed.
We also need pairing based crypto to interface between crypto currency, and the corporate form, though threshold signatures. So we have a white face, a grey face, and a black face. The white face is the interface between crypto cash and to the corporate form that exists both cryptographically and on government registries, the grey face is the interface to the corporate form that exists only cryptographically, not registered with the state (with the result that scams will abound) and the black face is secret invitation only blogs and messaging groups, within which it is possible to make secret payments.
These invitation only blogs and messaging groups will exist with and within open searchable blogs and messaging groups, hidden by the secret handshake protocol.
The structure will be ultimately rooted in Zooko’s triangle, but normal people will most of the time sign in by zero knowledge password protocol, your identity will be derivative from someone else’s Zooko based identity.
Useful links on this topic are “XDH assumption”, “pairing based cryptography”, “Bilinear Diffie-Hellman”, and “gap Diffie—Hellman (GDH) groups”.
A list of libraries now available PBC looks like the best. MIRACL uses a strong copyleft license. AGPL: all the software linked against free software (free in GNU/FSF sense) is also free software and freely available. GNU Public License is the most famous of such “strong copyleft” FOSS licenses. The GPL copyleft clause triggers when an application is distributed outside of company boundaries. And servicing customers from a company server running the code constitutes distribution.
MIRACL is written in C, and can be used from C, but is designed for C++. Comes with inline C++ wrappers.
But hell, I like C++. But C++ not going to fly on android. Scala does not support Visual Studio, and visual studio does not really support android, though it confidently believes that it does.
Useful threshold signatures requires pairing based cryptography. And pairing based cryptography also needed for useful implementation of the secret handshake (green beard, Masonic Lodge) problem. Allegedly good for zero knowledge password protocol, though I am pretty sure that problem has been solved without using pairing based cryptography.
Pairing based cryptography is usually described using the notation that the group operation is multiplication, and the one way function combining an integer with a member of the group to produce another member of the group is exponentiation. But pairing based cryptography is easier to understand if we call the group operation addition, whereupon we call the application of an integer modulo the order of the group multiplication, instead of calling it exponentiation.
In pairing based cryptography, the group supports addition (it is commutative and associative), and also supports something like multiplication (it is also commutative and associative), albeit the result of multiplication is not a member of the original group, but a member of another group, the pair group.
That it supports something like multiplication is described as “Bilinear Diffie-Hellman”, and if you call it “something like multiplication” people who are experts in the field will conclude you are an idiot.
So, let us, as usual, use the notation that members of the group are capital letters, and integers modulo the order of the group are lower case italics. Let us denote members of the pair group, the result of multiplying members of the original group with each other, with Greek letters.
Which notation allows us to leave out all the academic stuff about \forall P \in G. If it is a regular capital, it stands for any member of G, unless otherwise specified. In proper academic language (apart from the fact that I am leaving out all the \forall P \in G stuff):
Let G be an cyclic group of prime order written additively and ϓ another cyclic group of the same order written multiplicatively. A pairing is a map: e : G × G → ϓ , which satisfies the following properties:
Whereupon in this notation: B_{base}, the base point, is widely known, Ann’s private key is a, her public key is A = aB_{base}
In C++ is is useful to represent both groups additively, allowing the operation of the addition of any member of either group to another member of the same group, the multiplication of any member of either group by an integer, producing another member of the same group, and the operation e(P,Q), where P and Q are members of the first group, as infix multiplication producing a member of the second group.
In this notation the magic equality becomes
Bilinearity: \forall a, b, P, Q : (a*P)*(b*Q) == (a*b)*(P*Q)
Requiring us, in C++, to create an infix multiplication operator for the mapping, an infix addition operator for each group, and an infix multiplication by integer operator for each group.
To sign a document with the secret key a, publish $M = ah(Message)B
To test the signature, check that
A*(h(Message)B_{base})=B_{base}*M
Which it should because (a*B_{base})*(h(Message)*B_{base}) = B_{base}*(a*h(Message)*B_{base}) by bilinearity.
The threshold variant of this scheme is called GDH threshold signature scheme, Gap Diffie Hellman threshold signature scheme.
This scheme is also good for blind signatures, because if you sign an arbitrary point of the group, which the person asking for the signature knows is sum of an already signed point of the group, multiplied by a random secret, plus the thing he actually wants signed, he can then subtract the two signed quantities to find a third signed quantity, corresponding to a well formed token, that token unknown to the signer.
The Secret society of evil has a frequently changing secret key k_{evil} Ann has a secret key k_{Ann} and public key K_{Ann} = k_{Ann}B, Bob has a secret key k_{Bob} and public key K_{Bob} = b_{Bob}B
Let h(…) represent a hash of the serialized arguments of H, which hash is an integer modulo the order of the group. Let H(…) = h(…)B. Streams are concatenated with a boundary marker, and accidental occurrences of the boundary marker within a stream are escaped out.
The evil overlord of the evil society of evil issues Ann and Bob a signed hash of their public keys. For Ann, the signature is k_{evil}H(“Ann”, K_{Ann}, “evil secret society of evil”), similarly for Bob
The problem is that Ann does not know whether Bob is also a member of the secret society of evil, and wants to send him a message that is only going to be intelligible to him if he secretly has a key signed by the secret society of evil, but is not going to be recognizable to third parties as signed by the secret society of evil.
So, they use as part of their shared secret whereby they encrypt messages, the secret that Ann can calculate: [k_{evil}H(“Ann”, K_{Ann}, “evil secret society of evil”)]*H(“Bob”, K_{Bob}, “evil secret society of evil”)
Bob calculates: H(“Ann”, K_{Ann}, “evil secret society of evil”) *[k_{evil}H(“Bob”, K_{Bob}, “evil secret society of evil”)]
Thus proving possession of their evil keys to each other without revealing them to each other, and without revealing that possession to someone who does not have the expected evil key.
Overly complicated and excessively clever. In practice, if you have a secret society, you have a secret chatroom, in which case the routing metadata on messages going to and from the chatroom are traceable if they pass through enemy networks.
But suppose you want battlespace iff (Identify Friend or Foe). You want to send a message directly to an unknown target that will identify as friendly if the other guy is a friendly, but not necessarily let him know enemy if he is enemy. If he already knows you are enemy, you don’t want to give him the means to identify enemy iff from your friends.
This work is licensed under a Creative Commons Attribution 4.0 International License.