Image for post
Image for post
Photo by Lewis Keegan — Skillscouter.com on Unsplash

Ready to Sign … Go Get a Witness And Make Them Nice and CoSi?

We have seen the problems in the US elections, and where if one partner (eg Donald Trump) doesn’t think the election is fair, they could declare the election as null and void. This is not good for trust. And so, in our elections, we rely on witnesses to prove that votes have been cast correctly, and where it is unlikely that someone who is defrauding the system will be able to do so in front of witnesses to their votes. We also do this when we are signing a document, and where we must gather witnesses to our signature. The more witnesses we can gain, the likely less chance our signature will be fake. So let’s see if we can scale this concept into a large scale network.

An attack point on a network is the release of the private key. To overcome this we can collectively sign, and where we have witness co-signing. With this, every message is publicly witnessed before it is accepted. Each message ( is then collectively signed by witnesses. An attacker is likely to be spotted by at least one of the witnesses. One of the most interesting of these is CoSi (collective signing) [paper]:

Image for post
Image for post

The CoSi architecture elects an authority who has to verify the correctness of a record. For this there are a number of trusted witnesses, and who must apply their signature to the trustworthiness of the record. These witnesses become cosigners:

Image for post
Image for post
Ref [1]

In CoSi we then have are four phases involving participants and where the leader has an index of zero:

Image for post
Image for post
Ref [1]

Each participant has a private key () and a public key =, and where is a base point on an elliptic curve). We can then determine the aggregated public key with:

Image for post
Image for post

Announcement: Initially the leader broadcasts a message () that it wants the participants to sign.

Commitment: Each node will pick a random scalar () and determines the commitment (=[]). The comment is then sent to the leader, who will wait until there are enough commitments received (P’). The leader then creates a participant bitmask and aggregates all the received commitments:

Image for post
Image for post

and creates a participation bitmask . The leader then broadcasts and to the other participants.

Challenge: Each of the participants computes the collective challenge (using a Hash function of SHA512):

Image for post
Image for post

and send the following back to the leader:

Image for post
Image for post

Response: The leader will wait until the participants in P’ have sent their responses. When they have returned them, leader computes the aggregated response:

Image for post
Image for post

And the leader will publish the signature of the message () as:

Image for post
Image for post

Each node can then check their own signature value agrees with the leader.

Coding

The following defines some code [taken from here][sample][coding]:

package mainimport (
"fmt"
"crypto/cipher"
"crypto/sha512"
"hash"
"os" "go.dedis.ch/kyber/v3" "go.dedis.ch/kyber/v3/sign/cosi"
"go.dedis.ch/kyber/v3/suites"
"go.dedis.ch/kyber/v3/group/edwards25519"
"go.dedis.ch/kyber/v3/sign/eddsa"
"go.dedis.ch/kyber/v3/util/key"
"go.dedis.ch/kyber/v3/xof/blake2xb"
"go.dedis.ch/kyber/v3/util/random"
)type cosiSuite struct {
suites.Suite
r kyber.XOF
}
func (m *cosiSuite) Hash() hash.Hash {
return sha512.New()
}
func (m *cosiSuite) RandomStream() cipher.Stream { return m.r }
func main() {
m:="Hello" argCount := len(os.Args[1:]) if (argCount>0) {m= string(os.Args[1])}
fmt.Printf("Message to sign: %s\n\n",m)
message := []byte(m)
testCoSi(message,3, 0)
}
func testCoSi(message []byte, n, f int) {

testSuite := &cosiSuite{edwards25519.NewBlakeSHA256Ed25519(), blake2xb.New(nil)}
// Generate key pairs
var kps []*key.Pair
var privates []kyber.Scalar
var publics []kyber.Point
for i := 0; i < n; i++ {
kp := key.NewKeyPair(testSuite)
kp.Private = testSuite.Scalar().Pick(random.New())
kp.Public = testSuite.Point().Mul(kp.Private, nil) kps = append(kps, kp) privates = append(privates, kp.Private)
publics = append(publics, kp.Public)
}
fmt.Printf("Private keys: %s\n\n",privates)
fmt.Printf("Public keys: %s\n\n",publics)
// Init masks
var masks []*cosi.Mask
var byteMasks [][]byte
for i := 0; i < n-f; i++ {
m, _ := cosi.NewMask(testSuite, publics, publics[i])
masks = append(masks, m)
byteMasks = append(byteMasks, masks[i].Mask())
}
fmt.Printf("Masks: %x\n\n",masks)
fmt.Printf("Byte masks: %x\n\n",byteMasks)
// Compute commitments
var v []kyber.Scalar // random
var V []kyber.Point // commitment
for i := 0; i < n-f; i++ {
x, X := cosi.Commit(testSuite)
v = append(v, x)
V = append(V, X)
}
fmt.Printf("Commitments: %s\n\n",V) // Aggregate commitments
aggV, aggMask, _ := cosi.AggregateCommitments(testSuite, V, byteMasks)

fmt.Printf("Aggregated commitment (V): %s\n\n",aggV)
fmt.Printf("Aggregated mask (Z): %x\n\n",aggMask)
// Set aggregate mask in nodes
for i := 0; i < n-f; i++ {
masks[i].SetMask(aggMask)
}
// Compute challenge
var c []kyber.Scalar
for i := 0; i < n-f; i++ {
ci, _ := cosi.Challenge(testSuite, aggV, masks[i].AggregatePublic, message)

c = append(c, ci)
}
fmt.Printf("Challenge: %s\n\n",c) // Compute responses
var r []kyber.Scalar
for i := 0; i < n-f; i++ {
ri, _ := cosi.Response(testSuite, privates[i], v[i], c[i])
r = append(r, ri)
}
fmt.Printf("Responses: %s\n\n",r)
// Aggregate responses
aggr, _ := cosi.AggregateResponses(testSuite, r)
fmt.Printf("Aggregated responses (r): %s\n\n",aggr) for i := 0; i < n-f; i++ {
// Sign
sig, _ := cosi.Sign(testSuite, aggV, aggr, masks[i])
fmt.Printf("Signature (%d): %x",i,sig)
// Set policy depending on threshold f and then Verify
var p cosi.Policy
if f == 0 {
p = nil
} else {
p = cosi.NewThresholdPolicy(n - f)
}
// send a short sig in, expect an error
if err := cosi.Verify(testSuite, publics, message, sig[0:10], p); err == nil {

}
if err := cosi.Verify(testSuite, publics, message, sig, p); err != nil {

}
// cosi signature should follow the same format as EdDSA except it has no mask
maskLen := len(masks[i].Mask())
if err := eddsa.Verify(masks[i].AggregatePublic, message, sig[0:len(sig)-maskLen]); err != nil {

} else {
fmt.Printf("..Verified.\n")
}
}
}

The following is a sample run:

Message to sign: Testing 123Private keys: [97bb9cebdd5e07e94d2980bb920b83e16cf4f6ed078f50cca8ba19cdd887ea0c 1ef8829b3ab57cd409999d8f8ef2d282fea13e14c5c25e82ba25392372d07005 3b33b8b240724ac33aa4b499a3550e9a3d644cdd565def1ecda19cee3867a702]Public keys: [5d336374bb311cee7e814e961bd27c6aeeddbf2e34e8566d405dc345eb15c7f1 d3a0a9cc5267a8d22ad27d5adab27a63950d844b5ad0116d65144d4b375c7a2b 1d0bde2a1145cb0fe738a937403a013ddd0618693b27982feb0ad8549757c5cb]Masks: [c000054280 c0000542c0 c000054300]Byte masks: [01 02 04]Commitments: [408be095dc4f19858849da7e962b1ca659b3237b04ef966487efe17081bf9d76 cdfca1333a4ab6f8ffbddc94cf0cb4bd94230c7436e7ed601d3eccb214b757c4 a282b1e735850b90c0cbffa7c204a0fa79acdf9ad44ee301d32248bf8c8bde3c]Aggregated commitment (V): 4f29b2c32678c50f0346b7b6c5750027f4f9b1d24a68d1ca60e08e77111c7359Aggregated mask (Z): 07Challenge: [d57627ffd3b34e465c5221562bac21a22ef8d1f1142a7602e967b001dad7900f d57627ffd3b34e465c5221562bac21a22ef8d1f1142a7602e967b001dad7900f d57627ffd3b34e465c5221562bac21a22ef8d1f1142a7602e967b001dad7900f]Responses: [f357cdf7797226084e80877f8bd654e59cf5828c6fc2951e42da0d6d293f6301 568bcec281659cf8600cabf561f26b999668417825d06d2d6fde422c24a3ca0d aae6bce8189b7a2a757ca5052767cb6e00458b6e2a937275e836e018cab9b508]Aggregated responses (r): 06f66246fa0f2bd34d6ce0d73536add833a34f73bf2576c199ef30b2179ce307Signature (0): 4f29b2c32678c50f0346b7b6c5750027f4f9b1d24a68d1ca60e08e77111c735906f66246fa0f2bd34d6ce0d73536add833a34f73bf2576c199ef30b2179ce30707..Verified.
Signature (1): 4f29b2c32678c50f0346b7b6c5750027f4f9b1d24a68d1ca60e08e77111c735906f66246fa0f2bd34d6ce0d73536add833a34f73bf2576c199ef30b2179ce30707..Verified.
Signature (2): 4f29b2c32678c50f0346b7b6c5750027f4f9b1d24a68d1ca60e08e77111c735906f66246fa0f2bd34d6ce0d73536add833a34f73bf2576c199ef30b2179ce30707..Verified.

For NIST P-256, we just add:

import (
"go.dedis.ch/kyber/group/nist"
)
suite := nist.NewBlakeSHA256P256()

For BN256 pairing, we just add:

import (
"go.dedis.ch/kyber/pairing"
)
suite := pairing.NewSuiteBn256()

Conclusions

In our complex digital world, we need to start building systems which have a consensus in the operations they perform. So, here’s the demo of the method we just outlined:

Reference

[1] Syta, E., Tamas, I., Visher, D., Wolinsky, D. I., Jovanovic, P., Gasser, L., … & Ford, B. (2016, May). Keeping authorities” honest or bust” with decentralized witness cosigning. In (pp. 526–545). Ieee.

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store