Skip to content

Instantly share code, notes, and snippets.

@kac-
Last active April 10, 2024 09:59
Show Gist options
  • Save kac-/a25e8410beb2d1514f2c to your computer and use it in GitHub Desktop.
Save kac-/a25e8410beb2d1514f2c to your computer and use it in GitHub Desktop.
Blind signatures for Bitcoin transactions
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
}
@kac-
Copy link
Author

kac- commented Oct 26, 2014

@mably
Copy link

mably commented Oct 26, 2014

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

@xbee
Copy link

xbee commented Feb 1, 2017

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 !

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment