-
Notifications
You must be signed in to change notification settings - Fork 9
/
fs.go
92 lines (73 loc) · 2.32 KB
/
fs.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package zkstarks
import (
"encoding/hex"
"math/big"
"strings"
"golang.org/x/crypto/sha3"
)
// This file contains an implementation of the Fiat-Shamir heuristic channel
// The prover-verifier interaction is made non-interactive by evaluation
// and sending proofs to random points i.e leafs on the tree.
// On each call to send the channel state is update by transcript hash
// and the proof contains the transcript operations.
// Pragmatically this implementation simulates merlin transcripts where
// each "computation" adds some randomness to the state's hash which we
// use to simulate randomness when emulating prover-verifier interaction.
// More : https://merlin.cool/
var (
sendOperator = "send:"
receiveRandInt = "receiveRandInt:"
receiveRandFE = "receiveRandFE:"
)
// Channel represents a FS transcript cache
type Channel struct {
State []byte
Proof []string
}
// NewChannel creates a new instance of the FS channel
func NewChannel() *Channel {
return &Channel{
State: []byte{0},
Proof: make([]string, 0, 64),
}
}
// Send appends items to the channel state by hashing them
func (ch *Channel) Send(s []byte) {
var builder strings.Builder
builder.WriteString(sendOperator)
builder.WriteString(hex.EncodeToString(s))
ch.Proof = append(ch.Proof, builder.String())
ch.State = hash(concat(ch.State, s))
}
// RandInt emulates a random integer scalar in the range [min,max]
// sent by the verifier
func (ch *Channel) RandInt(min, max *big.Int) *big.Int {
stateAsInt := new(big.Int).SetBytes(ch.State)
diff := new(big.Int).Sub(max, min)
diff = diff.Add(diff, big.NewInt(1))
reduced := new(big.Int).Mod(stateAsInt, diff)
num := new(big.Int).Add(min, reduced)
var builder strings.Builder
builder.WriteString(receiveRandInt)
builder.WriteString(num.String())
ch.Proof = append(ch.Proof, builder.String())
ch.State = hash(ch.State)
return num
}
// RandFE emulates a random field element sent by the verifier given the field's
// modulus.
func (ch *Channel) RandFE(m *big.Int) *big.Int {
max := new(big.Int).Sub(m, big.NewInt(1))
num := ch.RandInt(big.NewInt(0), new(big.Int).Set(max))
var builder strings.Builder
builder.WriteString(receiveRandFE)
builder.WriteString(num.String())
return num
}
func concat(a, b []byte) []byte {
return append(a, b...)
}
func hash(b []byte) []byte {
h := sha3.Sum256(b)
return h[:]
}