builder uses same appox function

algorand · id-ms · May 10, 2022 · Feb 16, 2022 · Mar 10, 2022 · Mar 13, 2022
commit 27c4e110a8a45ae4ba53d010fe6c21a65ea498e1
diff --git a/crypto/compactcert/builder.go b/crypto/compactcert/builder.go
@@ -18,7 +18,6 @@ package compactcert
 
 import (
 	"fmt"
-
 	"github.com/algorand/go-algorand/crypto"
 	"github.com/algorand/go-algorand/crypto/merklearray"
 	"github.com/algorand/go-algorand/crypto/merklesignature"
@@ -163,64 +162,6 @@ again:
 	goto again
 }
 
-// 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:
-//
-// signedWeight ^ numReveals >= 2^(k+q) * provenWeight ^ numReveals
-//
-// To ensure that rounding errors do not reduce the security parameter,
-// we compute the left-hand side with rounding-down, and compute the
-// right-hand side with rounding-up.
-func numReveals(signedWeight uint64, provenWeight uint64, secKQ uint64, bound uint64) (uint64, error) {
-	n := uint64(0)
-
-	sw := &bigFloatDn{}
-	err := sw.setu64(signedWeight)
-	if err != nil {
-		return 0, err
-	}
-
-	pw := &bigFloatUp{}
-	err = pw.setu64(provenWeight)
-	if err != nil {
-		return 0, err
-	}
-
-	lhs := &bigFloatDn{}
-	err = lhs.setu64(1)
-	if err != nil {
-		return 0, err
-	}
-
-	rhs := &bigFloatUp{}
-	rhs.setpow2(int32(secKQ))
-
-	for {
-		if lhs.ge(rhs) {
-			return n, nil
-		}
-
-		if n >= bound {
-			return 0, fmt.Errorf("numReveals(%d, %d, %d) > %d", signedWeight, provenWeight, secKQ, bound)
-		}
-
-		lhs.mul(sw)
-		rhs.mul(pw)
-		n++
-	}
-}
-
-func (p *Params) numReveals(signedWeight uint64) (uint64, error) {
-	return numReveals(signedWeight, p.ProvenWeightThreshold, p.SecKQ, MaxReveals)
-}
-
 // Build returns a compact certificate, if the builder has accumulated
 // enough signatures to construct it.
 func (b *Builder) Build() (*Cert, error) {
@@ -229,7 +170,7 @@ func (b *Builder) Build() (*Cert, error) {
 	}
 
 	if b.signedWeight <= b.Params.ProvenWeightThreshold {
-		return nil, fmt.Errorf("not enough signed weight: %d <= %d", b.signedWeight, b.Params.ProvenWeightThreshold)
+		return nil, fmt.Errorf("%w: %d <= %d", ErrSignedWeightLessThanProvenWeight, b.signedWeight, b.Params.ProvenWeightThreshold)
 	}
 
 	// Commit to the sigs array

diff --git a/crypto/compactcert/builder_test.go b/crypto/compactcert/builder_test.go
@@ -554,24 +554,3 @@ func BenchmarkBuildVerify(b *testing.B) {
 		}
 	})
 }
-
-func BenchmarkNumReveals(b *testing.B) {
-	billion := uint64(1000 * 1000 * 1000)
-	microalgo := uint64(1000 * 1000)
-	provenWeight := 100 * billion * microalgo
-	signedWeight := 110 * billion * microalgo
-	secKQ := uint64(compactCertSecKQForTests)
-	bound := uint64(1000)
-
-	nr, err := numReveals(signedWeight, provenWeight, secKQ, bound)
-	if nr < 900 {
-		b.Errorf("numReveals(%d, %d, %d) = %d < 900", signedWeight, provenWeight, secKQ, nr)
-	}
-
-	for i := 0; i < b.N; i++ {
-		_, err = numReveals(signedWeight, provenWeight, secKQ, bound)
-		if err != nil {
-			b.Error(err)
-		}
-	}
-}
diff --git a/crypto/compactcert/verifier.go b/crypto/compactcert/verifier.go
@@ -19,23 +19,14 @@ package compactcert
 import (
 	"errors"
 	"fmt"
-	"math"
-	"math/big"
-	"math/bits"
-
 	"github.com/algorand/go-algorand/crypto"
 	"github.com/algorand/go-algorand/crypto/merklearray"
 )
 
 // Errors for the CompactCert verifier
 var (
-	ErrCoinNotInRange                   = errors.New("coin is not within slot weight range")
-	ErrNoRevealInPos                    = errors.New("no reveal for position")
-	ErrSignedWeightLessThanProvenWeight = errors.New("signed weight is less than or equal to proven weight")
-	ErrTooManyReveals                   = errors.New("too many reveals in cert")
-	ErrZeroSignedWeight                 = errors.New("signed weight can not be zero")
-	ErrZeroProvenWeightThreshold        = errors.New("proven weight can not be zero")
-	ErrInsufficientImpliedProvenWeight  = errors.New("signed weight and number of reveals yield insufficient proven weight")
+	ErrCoinNotInRange = errors.New("coin is not within slot weight range")
+	ErrNoRevealInPos  = errors.New("no reveal for position")
 )
 
 // Verifier is used to verify a compact certificate.
@@ -59,97 +50,6 @@ func MkVerifier(p Params, partcom crypto.GenericDigest) *Verifier {
 	}
 }
 
-// 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:
-//
-// 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 (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
-func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error {
-	if numOfReveals > MaxReveals {
-		return ErrTooManyReveals
-	}
-
-	if signedWeight == 0 {
-		return ErrZeroSignedWeight
-	}
-
-	if v.ProvenWeightThreshold == 0 {
-		return ErrZeroProvenWeightThreshold
-	}
-
-	if signedWeight <= v.ProvenWeightThreshold {
-		return fmt.Errorf("%w - signed weight %d <= proven weight %d", ErrSignedWeightLessThanProvenWeight, signedWeight, v.ProvenWeightThreshold)
-	}
-
-	// 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)
-
-	// Y = signedWt^2 + 4*2^d*signedWt +2^2d
-	tmp := &big.Int{}
-	tmp.SetUint64(4)
-	tmp.Mul(tmp, (&big.Int{}).SetUint64(1<<d))
-	tmp.Mul(tmp, (&big.Int{}).SetUint64(signedWeight)) //tmp = 4*2^d*signedWt
-
-	y := &big.Int{}
-	y.Add(signedWtPower2, tmp)
-	y.Add(y, (&big.Int{}).SetUint64(1<<(2*d)))
-
-	// a = 3*2^b*(signedWt^2-2^2d) + d*(T-1)*Y
-	tmp.SetUint64(d)
-	tmp.Mul(tmp, (&big.Int{}).SetUint64(ln2IntApproximation-1))
-	tmp.Mul(tmp, y) //tmp = d*(T-1)*Y
-
-	a := &big.Int{}
-	a.Sub(signedWtPower2, (&big.Int{}).SetUint64(1<<(2*d)))
-	a.Mul(a, (&big.Int{}).SetUint64(3))
-	a.Mul(a, (&big.Int{}).SetUint64(precisionBits))
-	a.Add(a, tmp)
-
-	// left = NumReveals*a
-	left := &big.Int{}
-	left.Mul(a, (&big.Int{}).SetUint64(numOfReveals))
-
-	// right = (secParam*t + NumReveals*P)*Y
-	//			tmp = secParam*t
-	tmp.SetUint64(v.SecKQ)
-	tmp.Mul(tmp, (&big.Int{}).SetUint64(ln2IntApproximation))
-
-	right := &big.Int{}
-	right.Mul((&big.Int{}).SetUint64(v.lnProvenWeightThreshold), (&big.Int{}).SetUint64(numOfReveals))
-	right.Add(tmp, right)
-	right.Mul(right, y)
-
-	if left.Cmp(right) < 0 {
-		return ErrInsufficientImpliedProvenWeight
-	}
-
-	return nil
-}
-
-func lnIntApproximation(x uint64, precisionBits uint64) uint64 {
-	if x == 0 {
-		return 0
-	}
-	result := math.Log(float64(x))
-	expendWithPer := result * float64(precisionBits)
-	return uint64(math.Ceil(expendWithPer))
-}
-
 // Verify checks if c is a valid compact certificate for the message
 // and participants that were used to construct the Verifier.
 func (v *Verifier) Verify(c *Cert) error {

diff --git a/crypto/compactcert/verifier_test.go b/crypto/compactcert/verifier_test.go
@@ -17,12 +17,10 @@
 package compactcert
 
 import (
-	"math"
 	"testing"
 
 	"github.com/stretchr/testify/require"
 
-	"github.com/algorand/go-algorand/crypto"
 	"github.com/algorand/go-algorand/crypto/merklesignature"
 	"github.com/algorand/go-algorand/test/partitiontest"
 )
@@ -87,142 +85,3 @@ func TestVerifyBadSignature(t *testing.T) {
 	err = verifier.Verify(cert)
 	a.ErrorIs(err, merklesignature.ErrSignatureSchemeVerificationFailed)
 }
-
-func TestVerifyMaxNumberOfReveals(t *testing.T) {
-	partitiontest.PartitionTest(t)
-	a := require.New(t)
-
-	signedWeight := uint64(10)
-	provenWeight := uint64(10)
-
-	param := Params{SecKQ: 128, ProvenWeightThreshold: provenWeight}
-	verifier := MkVerifier(param, crypto.GenericDigest{})
-	err := verifier.verifyWeights(signedWeight, MaxReveals+1)
-	a.ErrorIs(err, ErrTooManyReveals)
-}
-
-func TestVerifySignedWeightLessThanProvenWeight(t *testing.T) {
-	partitiontest.PartitionTest(t)
-	a := require.New(t)
-
-	signedWeight := uint64(1 << 10)
-	provenWeight := uint64(1<<10 + 1)
-
-	param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
-	verifier := MkVerifier(param, crypto.GenericDigest{})
-	err := verifier.verifyWeights(signedWeight, compactCertSecKQForTests)
-	a.ErrorIs(err, ErrSignedWeightLessThanProvenWeight)
-}
-
-func TestVerifyImpliedProvenBiggerThanThreshold(t *testing.T) {
-	partitiontest.PartitionTest(t)
-	a := require.New(t)
-
-	signedWeight := uint64(1 << 11)
-	provenWeight := uint64(1<<10 - 1)
-
-	numOfReveals, err := numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
-
-	param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
-	verifier := MkVerifier(param, crypto.GenericDigest{})
-	err = verifier.verifyWeights(signedWeight, numOfReveals)
-	a.NoError(err)
-}
-
-func TestVerifyImpliedProvenBiggerThanThresholdApproximationError(t *testing.T) {
-	partitiontest.PartitionTest(t)
-	a := require.New(t)
-
-	signedWeight := uint64(1 << 11)
-	provenWeight := uint64(1 << 10)
-
-	numOfReveals, err := numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
-
-	param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
-	verifier := MkVerifier(param, crypto.GenericDigest{})
-	err = verifier.verifyWeights(signedWeight, numOfReveals)
-	a.ErrorIs(err, ErrInsufficientImpliedProvenWeight)
-}
-
-func TestLnWithPrecision(t *testing.T) {
-	partitiontest.PartitionTest(t)
-	a := require.New(t)
-
-	for i := 1; i < 32; i++ {
-		exp := 1 << i
-		val := lnIntApproximation(2, uint64(exp))
-		a.GreaterOrEqual(float64(val)/float64(exp), math.Log(2))
-		a.Greater(math.Log(2), float64(val-1)/float64(exp))
-	}
-
-	a.Equal(ln2IntApproximation, lnIntApproximation(2, precisionBits))
-}
-
-func TestVerifyLimits(t *testing.T) {
-	partitiontest.PartitionTest(t)
-	a := require.New(t)
-
-	signedWeight := uint64(0)
-	provenWeight := uint64(1<<10 - 1)
-
-	param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
-	verifier := MkVerifier(param, crypto.GenericDigest{})
-	err := verifier.verifyWeights(signedWeight, 130)
-	a.ErrorIs(err, ErrZeroSignedWeight)
-
-	signedWeight = 101
-	provenWeight = 0
-
-	param = Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
-	verifier = MkVerifier(param, crypto.GenericDigest{})
-	err = verifier.verifyWeights(signedWeight, 0)
-	a.ErrorIs(err, ErrZeroProvenWeightThreshold)
-}
-
-func TestNumReveals(t *testing.T) {
-	partitiontest.PartitionTest(t)
-
-	billion := uint64(1000 * 1000 * 1000)
-	microalgo := uint64(1000 * 1000)
-	provenWeight := 2 * billion * microalgo
-	secKQ := uint64(compactCertSecKQForTests)
-	bound := uint64(1000)
-
-	for i := uint64(3); i < 10; i++ {
-		signedWeight := i * billion * microalgo
-		n, err := numReveals(signedWeight, provenWeight, secKQ, bound)
-		require.NoError(t, err)
-		if n < 50 || n > 300 {
-			t.Errorf("numReveals(%d, %d, %d) = %d looks suspect",
-				signedWeight, provenWeight, secKQ, n)
-		}
-
-		param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
-		verifier := MkVerifier(param, crypto.GenericDigest{})
-		err = verifier.verifyWeights(signedWeight, n)
-		require.NoError(t, err)
-	}
-}
-
-func BenchmarkWeight(b *testing.B) {
-	billion := uint64(1000 * 1000 * 1000)
-	microalgo := uint64(1000 * 1000)
-	provenWeight := 100 * billion * microalgo
-	signedWeight := 110 * billion * microalgo
-	secKQ := uint64(compactCertSecKQForTests)
-	bound := uint64(1000)
-
-	nr, err := numReveals(signedWeight, provenWeight, secKQ, bound)
-	if nr < 900 {
-		b.Errorf("numReveals(%d, %d, %d) = %d < 900", signedWeight, provenWeight, secKQ, nr)
-	}
-	param := Params{SecKQ: secKQ, ProvenWeightThreshold: provenWeight}
-	verifier := MkVerifier(param, crypto.GenericDigest{})
-
-	for i := 0; i < b.N; i++ {
-		err = verifier.verifyWeights(signedWeight, nr)
-		if err != nil {
-			b.Error(err)
-		}
-	}
-}