forked from cwtch.im/tapir
120 lines
3.7 KiB
Go
120 lines
3.7 KiB
Go
package bulletproofs
|
|
|
|
import (
|
|
"cwtch.im/tapir/primitives/core"
|
|
"encoding/binary"
|
|
"git.openprivacy.ca/openprivacy/libricochet-go/log"
|
|
ristretto "github.com/gtank/ristretto255"
|
|
)
|
|
|
|
// InnerProductProof encapsulates an inner product proof
|
|
type InnerProductProof struct {
|
|
L core.PointVector
|
|
R core.PointVector
|
|
A *ristretto.Scalar
|
|
B *ristretto.Scalar
|
|
}
|
|
|
|
// ProveInnerProduct generates a proof for <a,b>, the inner product of a and b
|
|
func ProveInnerProduct(a, b core.ScalarVector, u *ristretto.Element, P *ristretto.Element, G, H core.GeneratorVector, transcript *core.Transcript) InnerProductProof {
|
|
n := len(a)
|
|
|
|
transcript.AddToTranscript("dom-sep", []byte("ipp v1"))
|
|
nb := make([]byte, 8)
|
|
binary.LittleEndian.PutUint64(nb, uint64(n))
|
|
transcript.AddToTranscript("n", nb)
|
|
|
|
Lvec := core.PointVector{}
|
|
Rvec := core.PointVector{}
|
|
for n != 1 {
|
|
np := n / 2
|
|
aL, aR := a[:np], a[np:]
|
|
bL, bR := b[:np], b[np:]
|
|
GL, GR := G[:np], G[np:]
|
|
HL, HR := H[:np], H[np:]
|
|
|
|
cL := core.InnerProduct(aL, bR)
|
|
cR := core.InnerProduct(aR, bL)
|
|
|
|
L := core.MultiExp(append(aL.Join(bR), cL), append(GR.Join(HL), u))
|
|
R := core.MultiExp(append(aR.Join(bL), cR), append(GL.Join(HR), u))
|
|
|
|
transcript.AddElementToTranscript("L", L)
|
|
Lvec = append(Lvec, L)
|
|
transcript.AddElementToTranscript("R", R)
|
|
Rvec = append(Rvec, R)
|
|
|
|
u := transcript.CommitToTranscriptScalar("u")
|
|
uinv := new(ristretto.Scalar)
|
|
uinv.Invert(u)
|
|
|
|
for i := 0; i < len(aL); i++ {
|
|
aL_ := new(ristretto.Scalar).Multiply(aL[i], u)
|
|
aL[i] = new(ristretto.Scalar).Add(aL_, new(ristretto.Scalar).Multiply(aR[i], uinv))
|
|
bL_ := new(ristretto.Scalar).Multiply(bL[i], uinv)
|
|
bL[i] = new(ristretto.Scalar).Add(bL_, new(ristretto.Scalar).Multiply(bR[i], u))
|
|
|
|
GL[i] = core.MultiExp(core.ScalarVector{uinv, u}, core.GeneratorVector{GL[i], GR[i]})
|
|
HL[i] = core.MultiExp(core.ScalarVector{u, uinv}, core.GeneratorVector{HL[i], HR[i]})
|
|
}
|
|
|
|
x2 := new(ristretto.Scalar).Multiply(u, u)
|
|
P_ := new(ristretto.Element).ScalarMult(x2, L)
|
|
P_.Add(P_, P)
|
|
P_.Add(P_, new(ristretto.Element).ScalarMult(new(ristretto.Scalar).Invert(x2), R))
|
|
P = P_
|
|
//ranscript.AddToTranscript("P'", []byte(P.String()))
|
|
|
|
a = aL
|
|
b = bL
|
|
G = GL
|
|
H = HL
|
|
n = np
|
|
}
|
|
|
|
return InnerProductProof{Lvec, Rvec, a[0], b[0]}
|
|
}
|
|
|
|
// Verify checks the given inner product proof
|
|
func Verify(proof InnerProductProof, n int, u, P *ristretto.Element, G, H core.GeneratorVector, transcript *core.Transcript) bool {
|
|
np := n / 2
|
|
|
|
transcript.AddToTranscript("dom-sep", []byte("ipp v1"))
|
|
b := make([]byte, 8)
|
|
binary.LittleEndian.PutUint64(b, uint64(n))
|
|
transcript.AddToTranscript("n", b)
|
|
for i := range proof.L {
|
|
GL, GR := G[:np], G[np:]
|
|
HL, HR := H[:np], H[np:]
|
|
|
|
transcript.AddElementToTranscript("L", proof.L[i])
|
|
transcript.AddElementToTranscript("R", proof.R[i])
|
|
x := transcript.CommitToTranscriptScalar("u")
|
|
|
|
log.Debugf("L: %x\n", proof.L[i].Encode([]byte{}))
|
|
log.Debugf("R %x\n", proof.R[i].Encode([]byte{}))
|
|
log.Debugf("u: %x\n", x.Encode([]byte{}))
|
|
xinv := new(ristretto.Scalar)
|
|
xinv.Invert(x)
|
|
|
|
for j := 0; j < np; j++ {
|
|
GL[j] = core.MultiExp(core.ScalarVector{xinv, x}, core.GeneratorVector{GL[j], GR[j]})
|
|
HL[j] = core.MultiExp(core.ScalarVector{x, xinv}, core.GeneratorVector{HL[j], HR[j]})
|
|
}
|
|
|
|
x2 := new(ristretto.Scalar).Multiply(x, x)
|
|
P_ := new(ristretto.Element).ScalarMult(x2, proof.L[i])
|
|
P_.Add(P_, P)
|
|
P_.Add(P_, new(ristretto.Element).ScalarMult(new(ristretto.Scalar).Invert(x2), proof.R[i]))
|
|
P = P_
|
|
G = GL
|
|
H = HL
|
|
np = np / 2
|
|
}
|
|
c := new(ristretto.Scalar)
|
|
c.Multiply(proof.A, proof.B)
|
|
P_ := core.MultiExp(core.ScalarVector{proof.A, proof.B, c}, core.GeneratorVector{G[0], H[0], u})
|
|
log.Debugf("P:%v\nP':%v\n", P, P_)
|
|
return P.Equal(P_) == 1
|
|
}
|