Blind signatures for Bitcoin transactions

blind_oleg.go

package main

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/sha256"
	"fmt"
	"math/big"
)

// author: Oleg Andreev
// Blind signatures for Bitcoin transactions
// Second draft
// http://oleganza.com/blind-ecdsa-draft-v2.pdf
func main() {
	type Alice struct {
		// message
		m *big.Int
		// Let a, b, c and d be unique random numbers within [1, n – 1] chosen by Alice.
		a, b, c, d *big.Int
	}

	type Bob struct {
		// Let p and q be unique random numbers within [1, n – 1] chosen by Bob.
		p, q *big.Int
	}

	// curve
	E := elliptic.P256()
	// params
	params := E.Params()
	n := params.N

	alice, bob := Alice{m: big.NewInt(7)}, Bob{}
	// 1. Alice chooses random numbers a, b, c, d within [1, n – 1].
	alice.a, alice.b, alice.c, alice.d = big.NewInt(11), big.NewInt(13), big.NewInt(17), big.NewInt(19)
	// help vars for calcs
	tmp, x, y := new(big.Int), new(big.Int), new(big.Int)
	// 2. Bob chooses random numbers p, q within [1, n – 1]
	// and sends two EC points to Alice: P = (p -1 ·G) and Q = (q·p -1 ·G).
	bob.p, bob.q = big.NewInt(23), big.NewInt(29)
	Px, Py := E.ScalarBaseMult(new(big.Int).ModInverse(bob.p, n).Bytes())
	Qx, Qy := E.ScalarBaseMult(new(big.Int).Mul(bob.q, new(big.Int).ModInverse(bob.p, n)).Bytes())
	// 3. Alice computes K = (c·a) -1 ·P and public key T = (a·Kx) -1 ·(b·G + Q + d·c -1 ·P).
	// Bob cannot know if his parameters were involved in K or T without the knowledge of a, b, c and d.
	// Thus, Alice can safely publish T (e.g. in a Bitcoin transaction that locks funds with T).
	tmp = new(big.Int)
	Kx, Ky := E.ScalarMult(Px, Py, tmp.Mul(alice.c, alice.a).ModInverse(tmp, n).Bytes())

	Tx, Ty := E.ScalarBaseMult(alice.b.Bytes())
	Tx, Ty = E.Add(Tx, Ty, Qx, Qy)
	x, y = E.ScalarMult(Px, Py, new(big.Int).Mul(alice.d, new(big.Int).ModInverse(alice.c, n)).Bytes())
	Tx, Ty = E.Add(Tx, Ty, x, y)
	tmp = new(big.Int)
	Tx, Ty = E.ScalarMult(Tx, Ty, tmp.Mul(alice.a, Kx).ModInverse(tmp, n).Bytes())

	// 4. When time comes to sign a message (e.g. redeeming funds locked in a Bitcoin transaction),
	// Alice computes the hash h of her message.
	h := hashToInt(hash(alice.m.Bytes()), E)
	// 5. Alice blinds the hash and sends h 2 = a·h + b (mod n) to Bob.
	tmp = new(big.Int)
	h2 := tmp.Mul(alice.a, h).Add(tmp, alice.b).Mod(tmp, n)
	// 6. Bob verifies the identity of Alice via separate communications channel.
	// 7. Bob signs the blinded hash and returns the signature to Alice: s 1 = p·h 2 + q (mod n).
	tmp = new(big.Int)
	s1 := tmp.Mul(bob.p, h2).Add(tmp, bob.q).Mod(tmp, n)
	// 8. Alice unblinds the signature: s 2 = c·s 1 + d (mod n).
	tmp = new(big.Int)
	s2 := tmp.Mul(alice.c, s1).Add(tmp, alice.d).Mod(tmp, n)
	// 9. Now Alice has (Kx, s 2 ) which is a valid ECDSA signature of hash h verifiable by public key T.
	// If she uses it in a Bitcoin transaction, she will be able to redeem her locked funds without Bob
	// knowing which transaction he just helped to sign.

	// verify with standar ecdsa package
	fmt.Println(ecdsa.Verify(&ecdsa.PublicKey{Curve: E, X: Tx, Y: Ty}, h.Bytes(), Kx, s2))
	_ = Ky
}

func hash(msg []byte) []byte {
	hasher := sha256.New()
	hasher.Write(msg)
	return hasher.Sum(nil)
}

// from http://golang.org/src/pkg/crypto/ecdsa/ecdsa.go

// hashToInt converts a hash value to an integer. There is some disagreement
// about how this is done. [NSA] suggests that this is done in the obvious
// manner, but [SECG] truncates the hash to the bit-length of the curve order
// first. We follow [SECG] because that's what OpenSSL does. Additionally,
// OpenSSL right shifts excess bits from the number if the hash is too large
// and we mirror that too.
func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
	orderBits := c.Params().N.BitLen()
	orderBytes := (orderBits + 7) / 8
	if len(hash) > orderBytes {
		hash = hash[:orderBytes]
	}

	ret := new(big.Int).SetBytes(hash)
	excess := len(hash)*8 - orderBits
	if excess > 0 {
		ret.Rsh(ret, uint(excess))
	}
	return ret
}

Go playground

Thanx for the Go implementation, looks rather simple in fact.

Alice or any third party how to prove (Kx, s2) was signed by bob? The verify function just use alice's public key and (Kx, s2) , it can not connect it to bob's public keys . I think that is a big problem !