vss.go 3.54 KB
Newer Older
1
2
3
4
5
// Package pedersen implements verifiable secret sharing using Shamir's
// secret sharing algorithm and Pedersens commitment scheme.
package pedersen

import (
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
6
	"bsc-shamir/crypto/common"
7
8
9
10
11
	"bsc-shamir/math/polynomial"
	"bsc-shamir/math/zn"
	"math/big"
)

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
12
13
14
15
16
17
// Params are required parameters
type Params struct {
	Zp *zn.Zn
	Zq *zn.Zn
	G  *big.Int
	H  *big.Int
18
19
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
20
21
22
23
24
25
26
// NewParams returns the parameters used by pedersen
func NewParams(params *common.Params) *Params {
	return &Params{
		Zp: params.Zp,
		Zq: params.Zq,
		G:  params.G,
		H:  params.H,
27
28
29
30
31
32
	}
}

// Proof is a commitment to polynomial coefficients.
type Proof []*big.Int

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
33
34
35
36
37
// Share represents a verifiable secret share.
type Share struct {
	X *big.Int
	Y *big.Int
	T *big.Int
38
39
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
40
41
42
43
44
45
46
47
48
49
// Verify the share is valid
func (params *Params) Verify(share *Share, proof Proof) bool {
	result := big.NewInt(1)
	for j, e := range proof {
		t1 := params.Zq.Exp(share.X, big.NewInt(int64(j)))
		t2 := params.Zp.Exp(e, t1)
		result = params.Zp.Mul(result, t2)
	}
	commit := params.Commit(share.Y, share.T)
	return result.Cmp(commit) == 0
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
50
51
}

52
// Commit to s using t as witness.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
53
54
55
56
func (params *Params) Commit(s, t *big.Int) *big.Int {
	t1 := params.Zp.Exp(params.G, s)
	t2 := params.Zp.Exp(params.H, t)
	return params.Zp.Mul(t1, t2)
57
58
59
60
61
}

// Create a (t, n) threshold scheme for secret s using Pedersens verifiable
// secret sharing scheme. Create returns n shares with t required to recover
// the value of s.
62
func (params *Params) Create(t int, xs []*big.Int, s, w *big.Int) ([]*Share, Proof) {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
63
64
65
66
67
	degree := t - 1
	f := polynomial.RandomPolynomial(degree, params.Zq)
	f.A[0] = s
	g := polynomial.RandomPolynomial(degree, params.Zq)
	g.A[0] = w
68
69
70

	proof := make([]*big.Int, t)
	for i := range proof {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
71
		proof[i] = params.Commit(f.A[i], g.A[i])
72
73
	}

74
75
76
	shares := make([]*Share, 0, len(xs))
	for _, x := range xs {
		shares = append(shares, &Share{
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
77
78
79
			X: x,
			Y: f.Evaluate(x),
			T: g.Evaluate(x),
80
		})
81
82
	}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
83
	return shares, proof
84
85
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
86
87
88
// Combine shares to recover the secret. All shares are assumed to be valid.
// If the shares does not satisfy the threshold scheme, they were created under
// no information is revealed about the secret.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
89
func (params *Params) Combine(shares []*Share) *big.Int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
90
	secret := big.NewInt(0)
91

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
92
93
94
	for j := range shares {
		numerator := big.NewInt(1)
		denominator := big.NewInt(1)
95

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
96
97
		for k := range shares {
			if j != k {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
98
				numerator = params.Zq.Mul(numerator, shares[k].X)
99

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
100
101
				t1 := params.Zq.Sub(shares[k].X, shares[j].X)
				denominator = params.Zq.Mul(denominator, t1)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
102
103
104
			}
		}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
105
106
107
		t1 := params.Zq.Mul(shares[j].Y, numerator)
		t2 := params.Zq.Mul(t1, params.Zq.ModInverse(denominator))
		secret = params.Zq.Add(secret, t2)
108
109
	}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
110
111
112
113
114
115
116
117
118
	return secret
}

// AddShares returns a share is is the sum of the given shares.
func (params *Params) AddShares(shares []*Share) *Share {
	result := &Share{
		X: big.NewInt(0),
		Y: big.NewInt(0),
		T: big.NewInt(0),
119
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
120

121
	for _, share := range shares {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
122
123
124
		result.X = share.X
		result.Y = params.Zq.Add(result.Y, share.Y)
		result.T = params.Zq.Add(result.T, share.T)
125
	}
126

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
127
	return result
128
129
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
130
131
132
133
134
135
// MulProofs returns a proof which is the product of the given proofs
func (params *Params) MulProofs(proofs []Proof) Proof {
	n := len(proofs[0])
	result := make([]*big.Int, n)
	for i := range result {
		result[i] = big.NewInt(1)
136
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
137
138
139
140
141
142
143
144

	for _, proof := range proofs {
		for i, e := range proof {
			result[i] = params.Zp.Mul(result[i], e)
		}
	}

	return result
145
}
Mikkel Wienberg Madsen's avatar
Mikkel Wienberg Madsen committed
146
147
148
149
150
151
152
153
154
155
156
157

func (proof Proof) Equals(other Proof) bool {
	if len(other) != len(proof) {
		return false
	}
	for i, e := range proof {
		if other[i].Cmp(e) != 0 {
			return false
		}
	}
	return true
}