Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make stateproof verifier snark friendly #3895

Merged
merged 42 commits into from
May 10, 2022
Merged

Make stateproof verifier snark friendly #3895

Changes from 1 commit
Commits
Show all changes
42 commits
Select commit Hold shift + click to select a range
ebd1016
change coin filps to be shake(sumhash(seed))
Feb 16, 2022
5446cae
add sequence of coin positions to the cert
Mar 10, 2022
4363c91
compute CC security using implied provenWeight
Mar 13, 2022
3ee4616
create a log2 appr func
Mar 15, 2022
6f4de56
fix stateproof message issues.
Mar 15, 2022
92ce531
remove proven weight form the coin hash
Mar 16, 2022
a21f7b7
fix cc test
Mar 17, 2022
f8168fe
use reject sampling in coin hash.
Mar 17, 2022
0afd674
use logarithmic approximation
Mar 27, 2022
b548344
refactoring
Mar 28, 2022
27c4e11
builder uses same appox function
Mar 31, 2022
b4c9be4
comments and doc
Mar 31, 2022
4ce22b6
handle negative value in number of reveals equation
Apr 4, 2022
40a9de2
add lnProvenWe to coinhash
Apr 10, 2022
2f275f3
fixed hash representation for coinhash
Apr 10, 2022
c76184b
fix CC benchmark
Apr 10, 2022
ac4df71
refactor
Apr 10, 2022
8911552
remove old numberofreveals code
Apr 10, 2022
593b62f
change secKQ to 256
Apr 11, 2022
e794180
fix CRs
Apr 12, 2022
c13ce05
CR fixes + rename
Apr 13, 2022
106e6f4
more CR fix
Apr 14, 2022
a3507ad
refactor the trusted params on the verifer.
Apr 14, 2022
3789b44
more refactoring
Apr 17, 2022
ec0543c
fix flaky test
Apr 17, 2022
6e35aad
remove Param structure
Apr 17, 2022
867d2cc
more fixes
Apr 17, 2022
cffa28a
update falcon lib + use byte as salt version
Apr 19, 2022
dd70755
add coinhash kat generator
Apr 20, 2022
485b44d
fix some CR comments
Apr 26, 2022
2cea300
clear out some documentation
Apr 27, 2022
2f03f65
Apply suggestions from code review
id-ms Apr 27, 2022
b566381
fix comments
Apr 28, 2022
ab2a2ff
refactor rejection sampling
Apr 28, 2022
112e5e7
CR fix
May 1, 2022
b7f38d9
refactoring
May 1, 2022
25a33d3
fix comments
May 3, 2022
30ee541
reduce the bytes allocated for stateproof message
May 3, 2022
ed9f141
Apply suggestions from code review
id-ms May 4, 2022
5ae415b
fix test since stateproof message hash was reduce
May 4, 2022
32a8164
fix CR comments
May 8, 2022
9c6a06a
more refactoring
May 8, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
comments and doc
  • Loading branch information
algoidan committed Apr 17, 2022
commit b4c9be4ad8a80dad9ab31320c8ffa04aae98dfd0
157 changes: 92 additions & 65 deletions crypto/compactcert/weights.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -24,6 +24,7 @@ import (
"math/bits"
)

// errors for the weights verification
var (
ErrSignedWeightLessThanProvenWeight = errors.New("signed weight is less than or equal to proven weight")
ErrTooManyReveals = errors.New("too many reveals in cert")
Expand All @@ -32,6 +33,30 @@ var (
ErrInsufficientImpliedProvenWeight = errors.New("signed weight and number of reveals yield insufficient proven weight")
)

// The function in this file are used to compute and verify the number of reveals necessary for the security parameter
// of the compactcert. According to section 8 of the ``Compact Certificates'' the following equation must hold to meet
// the security parameter:
//
// numReveals is the smallest number that satisfies
// 2^-k >= 2^q * (provenWeight/signedWeight)^numReveals
//
// in order to make the verification SNARK friendly we will not compute the exact number of reveals.
// Alternatively, we would use a lower bound on the implied provenWeight using a given numReveals and signedWeight.
// i.e we need to verify that:
// numReveals * (log2(signedWeight) - log2(provenWeightThreshold)) >= k+q
// In addition, we would like to avoid the log2 calculation.
//
// For that we will use the following approximation that if it holds the security parameter is guarantee:
// numReveals * (3 * 2^b * (signedWeight^2 - 2^2d) + d * (T-1) * Y) >= ((k+q) * T + numReveals * P) * Y
//
// where signedWeight/(2^d) >=1 for some integer d>=0, p = P/(2^b) >= ln(provenWeightThreshold), t = T/(2^b) >= ln(2) >= (T-1)/(2^b)
// for some integers P,T >= 0 , b=16 and y = signedWeight^2 + 2^(d+2) * signedWeight + 2^2d
//
// In order for the prover to satisfy the equation above, it suffices (by slightly rearranging) to use any value of numReveals that satisfies:
//
// numReveals > = ((k+q) * T * Y / (3 * 2^b * (signedWeight^2 - 2^2d) + (d * (T - 1) - P) * Y))
// more details can be found on the Algorand's spec

func bigInt(num uint64) *big.Int {
return (&big.Int{}).SetUint64(num)
}
Expand All @@ -43,25 +68,17 @@ func lnIntApproximation(x uint64, precisionBits uint64) uint64 {
result := math.Log(float64(x))
expendWithPer := result * float64(precisionBits)
return uint64(math.Ceil(expendWithPer))

}

// verifyWeights makes sure that the number of reveals in the cert is correct with respect
// to the signedWeight and a provenWeight threshold.
// According to the security analysis the number of reveals is given by the following:
// This function that the following equation is satisfied
//
// numReveals is the smallest number that satisfies
// 2^-k >= 2^q * (provenWeight / signedWeight) ^ numReveals
// numReveals * (3 * 2^b * (signedWeight^2 - 2^2d) + d * (T-1) * Y) >= ((k+q) * T + numReveals * P) * Y
//
// in order to make the verification SNARK friendly we will not compute the exact number of reveals (as it is done in the build)
// Alternatively, we would use a lower bound on the implied provenWeight using a given numReveals and signedWeight .
// i.e we need to verify that:
// numReveals*(log2(signedWeight)-log2(provenWeightThreshold)) >= k+q
// In addition, we would like to use a friendly log2 approximation. it is sufficient to verify the following inequality:
//
// numReveals * ( 3 * 2^b * (signedWeight^2-2^2d) + d * (T-1) * Y) >= ((k+q) * T + numReveals * P) * Y
// where signedWeight/(2^d) >=1 for some integer d>=0, p = P/(2^b) >= ln(provenWeightThreshold), t = T/(2^b) >= ln(2) >= (T-1)/(2^b)
// for some integers P,T >= 0 and b=16
algonautshant marked this conversation as resolved.
Show resolved Hide resolved
//
func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error {
if numOfReveals > MaxReveals {
return ErrTooManyReveals
Expand All @@ -79,13 +96,23 @@ func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error
return fmt.Errorf("%w - signed weight %d <= proven weight %d", ErrSignedWeightLessThanProvenWeight, signedWeight, v.ProvenWeightThreshold)
}

// in order to make the code more readable and reusable we will define the following expressions:
// y = signedWeight^2 + 2^(d + 2) * signedWeight + 2^2d
// a = 3 * 2^b * (signedWeight^2 - 2^2d)
// b = d * (T - 1)
//
algonautshant marked this conversation as resolved.
Show resolved Hide resolved
// numReveals * (3 * 2^b * (signedWeight^2 - 2^2d) + d * (T-1) * Y) >= ((k+q) * T + numReveals * P) * Y
// ||
// \/
// numReveals * (a + b * Y) >= ((k+q) * T + numReveals * P) * Y
y, a, b := getSubExpressions(signedWeight)
lhs := &big.Int{}
lhs.Set(b).
Mul(lhs, y).
Add(a, lhs).
Mul(lhs, bigInt(numOfReveals))
Mul(bigInt(numOfReveals), lhs)

// todo canoverflow???
rhs := bigInt(v.SecKQ * ln2IntApproximation)
rhs.Add(rhs, bigInt(numOfReveals*v.lnProvenWeightThreshold)).
Mul(rhs, y)
Expand All @@ -97,31 +124,30 @@ func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error
return nil
}

func (p *Builder) numReveals(signedWeight uint64) (uint64, error) {
return numReveals(signedWeight, p.ProvenWeightThreshold, p.SecKQ, MaxReveals)
}

// numReveals computes the number of reveals necessary to achieve the desired
// security parameters. See section 8 of the ``Compact Certificates''
// document for the analysis.
//
// numReveals is the smallest number that satisfies
//
// 2^-k >= 2^q * (provenWeight / signedWeight) ^ numReveals
//
// which is equivalent to the following:
// security parameters. we use value which satisfies the following equation:
//
// signedWeight ^ numReveals >= 2^(k+q) * provenWeight ^ numReveals
//
// ***********
// numReveals*(3*2^b*(signedWeight^2-2^2d)+d*(T-1)*Y) >= ((k+q)*T+numReveals*P)*Y
// numReveals*(3*2^b*(signedWeight^2-2^2d)+(d*(T-1)-P)*Y) >= (k+q)*T*Y
// numReveals >= (k+q)*T*Y/(3*2^b*(signedWeight^2-2^2d)+(d*(T-1)-P)*Y)
// numReveals =Ceil( (k+q)*T*Y/(3*2^b*(signedWeight^2-2^2d)+(d*(T-1)-P)*Y) )
// To ensure tsdkfjgalskdnglasdg
// numReveals > = ((k+q) * T * Y / (3 * 2^b * (signedWeight^2 - 2^2d) + (d * (T - 1) - P) * Y))
func numReveals(signedWeight uint64, provenWeight uint64, secKQ uint64, bound uint64) (uint64, error) {
if provenWeight == 0 {
return 0, ErrZeroProvenWeightThreshold
}

lnProvenWe := lnIntApproximation(provenWeight, precisionBits)

// in order to make the code more readable and reusable we will define the following expressions:
// y = signedWeight^2 + 2^(d + 2) * signedWeight + 2^2d
// a = 3 * 2^b * (signedWeight^2 - 2^2d)
// b = d * (T - 1)
//
// numReveals > = ((k+q) * T * Y / (3 * 2^b * (signedWeight^2 - 2^2d) + (d * (T - 1) - P) * Y))
// ||
// \/
// numReveals >= ((k+q) * T * Y / (a + (b - P) * Y)
y, a, b := getSubExpressions(signedWeight)

id-ms marked this conversation as resolved.
Show resolved Hide resolved
numerator := bigInt(secKQ)
Expand All @@ -141,6 +167,44 @@ func numReveals(signedWeight uint64, provenWeight uint64, secKQ uint64, bound ui
return res, nil
algonautshant marked this conversation as resolved.
Show resolved Hide resolved
}

// getSubExpressions calculate the following expression to make the code more readable and reusable
// y = signedWeight^2 + 2^(d + 2) * signedWeight + 2^2d
// a = 3 * 2^b * (signedWeight^2 - 2^2d)
// b = d * (T - 1)
func getSubExpressions(signedWeight uint64) (y *big.Int, a *big.Int, b *big.Int) {
// find d s.t 2^(d+1) >= signedWeight >= 2^(d)
d := uint64(bits.Len64(signedWeight)) - 1

signedWtPower2 := &big.Int{}
signedWtPower2.SetUint64(signedWeight)
signedWtPower2.Mul(signedWtPower2, signedWtPower2)

//tmp = 2^(d+2)*signedWt
tmp := (&big.Int{}).Mul(
bigInt(1<<(d+2)),
bigInt(signedWeight),
)

// Y = signedWeight^2 + 2^(d+2)*signedWeight +2^2d == signedWeight^2 + tmp +2^2d
y = bigInt(1)
y.Lsh(y, uint(2*d)).
Add(y, tmp).
Add(y, signedWtPower2)

// a = 3*2^b*(signedWeight^2-2^2d)
a = bigInt(1)
a.Lsh(a, uint(2*d)).
Sub(signedWtPower2, a).
Mul(a, bigInt(3)).
Mul(a, bigInt(precisionBits))

// b = d*(T-1)
b = bigInt(d)
b.Mul(b, bigInt(ln2IntApproximation-1))

return
}

func old(signedWeight uint64, provenWeight uint64, secKQ uint64, bound uint64) (uint64, error) {
n := uint64(0)

Expand Down Expand Up @@ -179,40 +243,3 @@ func old(signedWeight uint64, provenWeight uint64, secKQ uint64, bound uint64) (
n++
}
}
func (p *Builder) numReveals(signedWeight uint64) (uint64, error) {
return numReveals(signedWeight, p.ProvenWeightThreshold, p.SecKQ, MaxReveals)
}

func getSubExpressions(signedWeight uint64) (*big.Int, *big.Int, *big.Int) {
// find d s.t 2^(d+1) >= signedWeight >= 2^(d)
d := uint64(bits.Len64(signedWeight)) - 1

signedWtPower2 := &big.Int{}
signedWtPower2.SetUint64(signedWeight)
signedWtPower2.Mul(signedWtPower2, signedWtPower2)

//tmp = 2^(d+2)*signedWt == 4*2^d*signedWt
tmp := (&big.Int{}).Mul(
bigInt(1<<(d+2)),
bigInt(signedWeight),
)

// Y = signedWt^2 + 2^(d+2)*signedWt +2^2d == signedWt^2 + tmp +2^2d
y := bigInt(1)
y.Lsh(y, uint(2*d)).
Add(y, tmp).
Add(y, signedWtPower2)

// a = 3*2^b*(signedWt^2-2^2d)
a := bigInt(1)
a.Lsh(a, uint(2*d)).
Sub(signedWtPower2, a).
Mul(a, bigInt(3)).
Mul(a, bigInt(precisionBits))

// b = d*(T-1)
b := bigInt(d)
b.Mul(b, bigInt(ln2IntApproximation-1))

return y, a, b
}