refactoring

algorand · id-ms · May 10, 2022 · Feb 16, 2022 · Mar 10, 2022 · Mar 13, 2022
commit b5483449826efaf15af4be1cf510413fc705e329
diff --git a/crypto/compactcert/const.go b/crypto/compactcert/const.go
@@ -22,11 +22,11 @@ import (
 
 // HashType/ hashSize relate to the type of hash this package uses.
 const (
-	HashType      = crypto.Sumhash
-	HashSize      = crypto.SumhashDigestSize
-	CoinHashType  = crypto.Sumhash
-	precisionBits = uint64(1 << 16) // number of bits used for log approximation
-	ln2AsInteger  = uint64(45427)   // the value of the ln(2) with 16 bits of precision
+	HashType            = crypto.Sumhash
+	HashSize            = crypto.SumhashDigestSize
+	CoinHashType        = crypto.Sumhash
+	precisionBits       = uint64(1 << 16) // number of bits used for log approximation
+	ln2IntApproximation = uint64(45427)   // the value of the ln(2) with 16 bits of precision
 )
 
 const (

diff --git a/crypto/compactcert/verifier.go b/crypto/compactcert/verifier.go
@@ -19,11 +19,12 @@ package compactcert
 import (
 	"errors"
 	"fmt"
-	"github.com/algorand/go-algorand/crypto"
-	"github.com/algorand/go-algorand/crypto/merklearray"
 	"math"
 	"math/big"
 	"math/bits"
+
+	"github.com/algorand/go-algorand/crypto"
+	"github.com/algorand/go-algorand/crypto/merklearray"
 )
 
 // Errors for the CompactCert verifier
@@ -33,29 +34,47 @@ var (
 	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")
 )
 
 // Verifier is used to verify a compact certificate.
 type Verifier struct {
 	Params
 
-	lnProvenWeightThresholdAsInteger uint64 // ln(provenWeightThreshold) with 16 bits of precision
-	partcom                          crypto.GenericDigest
+	lnProvenWeightThreshold uint64 // ln(provenWeightThreshold) as integer with 16 bits of precision
+	partcom                 crypto.GenericDigest
 }
 
 // MkVerifier constructs a verifier to check the compact certificate
 // on the message specified in p, with partcom specifying the Merkle
 // root of the participants that must sign the message.
 func MkVerifier(p Params, partcom crypto.GenericDigest) *Verifier {
-	provenWt := lnWithPrecision(p.ProvenWeightThreshold, precisionBits)
+	lnProvenWt := lnIntApproximation(p.ProvenWeightThreshold, precisionBits)
+
 	return &Verifier{
-		Params:                           p,
-		lnProvenWeightThresholdAsInteger: provenWt,
-		partcom:                          partcom,
+		Params:                  p,
+		lnProvenWeightThreshold: lnProvenWt,
+		partcom:                 partcom,
 	}
 }
 
+// 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
@@ -65,6 +84,10 @@ func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error
 		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)
 	}
@@ -77,21 +100,19 @@ func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error
 	signedWtPower2.Mul(signedWtPower2, signedWtPower2)
 
 	// Y = signedWt^2 + 4*2^d*signedWt +2^2d
-	// 		   tmp = 4*2^d*signedWt
 	tmp := &big.Int{}
 	tmp.SetUint64(4)
 	tmp.Mul(tmp, (&big.Int{}).SetUint64(1<<d))
-	tmp.Mul(tmp, (&big.Int{}).SetUint64(signedWeight))
+	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 = d*(T-1)*Y
 	tmp.SetUint64(d)
-	tmp.Mul(tmp, (&big.Int{}).SetUint64(ln2AsInteger-1))
-	tmp.Mul(tmp, y)
+	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)))
@@ -106,10 +127,10 @@ func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error
 	// right = (secParam*t + NumReveals*P)*Y
 	//			tmp = secParam*t
 	tmp.SetUint64(v.SecKQ)
-	tmp.Mul(tmp, (&big.Int{}).SetUint64(ln2AsInteger))
+	tmp.Mul(tmp, (&big.Int{}).SetUint64(ln2IntApproximation))
 
 	right := &big.Int{}
-	right.Mul((&big.Int{}).SetUint64(v.lnProvenWeightThresholdAsInteger), (&big.Int{}).SetUint64(numOfReveals))
+	right.Mul((&big.Int{}).SetUint64(v.lnProvenWeightThreshold), (&big.Int{}).SetUint64(numOfReveals))
 	right.Add(tmp, right)
 	right.Mul(right, y)
 
@@ -120,7 +141,10 @@ func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error
 	return nil
 }
 
-func lnWithPrecision(x uint64, precisionBits uint64) uint64 {
+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))

diff --git a/crypto/compactcert/verifier_test.go b/crypto/compactcert/verifier_test.go
@@ -17,14 +17,14 @@
 package compactcert
 
 import (
-	"fmt"
 	"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"
-	"github.com/stretchr/testify/require"
-	"testing"
 )
 
 func TestVerifyRevelForEachPosition(t *testing.T) {
@@ -122,7 +122,6 @@ func TestVerifyImpliedProvenBiggerThanThreshold(t *testing.T) {
 	provenWeight := uint64(1<<10 - 1)
 
 	numOfReveals, err := numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
-	fmt.Println(numOfReveals)
 
 	param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
 	verifier := MkVerifier(param, crypto.GenericDigest{})
@@ -138,7 +137,6 @@ func TestVerifyImpliedProvenBiggerThanThresholdApproximationError(t *testing.T)
 	provenWeight := uint64(1 << 10)
 
 	numOfReveals, err := numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
-	fmt.Println(numOfReveals)
 
 	param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
 	verifier := MkVerifier(param, crypto.GenericDigest{})
@@ -152,12 +150,33 @@ func TestLnWithPrecision(t *testing.T) {
 
 	for i := 1; i < 32; i++ {
 		exp := 1 << i
-		val := lnWithPrecision(2, uint64(exp))
+		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(ln2AsInteger, lnWithPrecision(2, precisionBits))
+	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) {
@@ -182,6 +201,28 @@ func TestNumReveals(t *testing.T) {
 		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)
+		}
 	}
 }
diff --git a/data/stateproof/message.go b/data/stateproof/message.go
@@ -26,7 +26,7 @@ import (
 type Message struct {
 	_struct struct{} `codec:",omitempty,omitemptyarray"`
 	// Commitment over the sha256 of the block headers in the interval between two compact certificates.
-	BlockHeadersCommitment []byte `codec:"b"`
+	BlockHeadersCommitment []byte `codec:"b,allocbound=crypto.Sha256Size"`
 }
 
 // ToBeHashed returns the bytes of the message.

diff --git a/data/stateproof/msgp_gen.go b/data/stateproof/msgp_gen.go
diff --git a/ledger/internal/compactcert_test.go b/ledger/internal/compactcert_test.go
@@ -50,6 +50,7 @@ func TestValidateCompactCert(t *testing.T) {
 	certHdr.Round = 1
 	proto := config.Consensus[certHdr.CurrentProtocol]
 	proto.CompactCertRounds = 2
+	proto.CompactCertSecKQ = 128
 	config.Consensus[certHdr.CurrentProtocol] = proto
 
 	err = validateCompactCert(certHdr, cert, votersHdr, nextCertRnd, atRound, msg)