add lnProvenWe to coinhash

algorand · id-ms · May 10, 2022 · Feb 16, 2022 · Mar 10, 2022 · Mar 13, 2022
commit 40a9de2ed549a0099e086b75d7136ae8385a189b
diff --git a/crypto/compactcert/builder.go b/crypto/compactcert/builder.go
@@ -41,11 +41,12 @@ type sigslot struct {
 // a compact certificate for that message.
 type Builder struct {
 	Params
-	sigs          []sigslot // Indexed by pos in participants
-	sigsHasValidL bool      // The L values in sigs are consistent with weights
-	signedWeight  uint64    // Total weight of signatures so far
-	participants  []basics.Participant
-	parttree      *merklearray.Tree
+	sigs                    []sigslot // Indexed by pos in participants
+	sigsHasValidL           bool      // The L values in sigs are consistent with weights
+	signedWeight            uint64    // Total weight of signatures so far
+	lnProvenWeightThreshold uint64    // ln(provenWeightThreshold) as integer with 16 bits of precision
+	participants            []basics.Participant
+	parttree                *merklearray.Tree
 
 	// Cached cert, if Build() was called and no subsequent
 	// Add() calls were made.
@@ -58,15 +59,17 @@ type Builder struct {
 // parttree.
 func MkBuilder(param Params, part []basics.Participant, parttree *merklearray.Tree) (*Builder, error) {
 	npart := len(part)
+	lnProvenWt := lnIntApproximation(param.ProvenWeightThreshold, precisionBits)
 
 	b := &Builder{
 		Params: param,
 
-		sigs:          make([]sigslot, npart),
-		sigsHasValidL: false,
-		signedWeight:  0,
-		participants:  part,
-		parttree:      parttree,
+		sigs:                    make([]sigslot, npart),
+		sigsHasValidL:           false,
+		signedWeight:            0,
+		participants:            part,
+		parttree:                parttree,
+		lnProvenWeightThreshold: lnProvenWt,
 	}
 
 	return b, nil
@@ -193,20 +196,23 @@ func (b *Builder) Build() (*Cert, error) {
 		MerkleSignatureVersion: merklesignature.SchemeVersion,
 	}
 
-	nr, err := b.numReveals(b.signedWeight)
+	nr, err := b.numReveals()
 	if err != nil {
 		return nil, err
 	}
 
 	var proofPositions []uint64
 
 	revealsSequence := make([]uint64, nr)
+
 	choice := coinChoiceSeed{
-		SignedWeight: c.SignedWeight,
-		Sigcom:       c.SigCommit,
-		Partcom:      b.parttree.Root(),
-		MsgHash:      b.StateProofMessageHash,
+		MsgHash:                 b.StateProofMessageHash,
+		LnProvenWeightThreshold: b.lnProvenWeightThreshold,
+		SignedWeight:            c.SignedWeight,
+		Sigcom:                  c.SigCommit,
+		Partcom:                 b.parttree.Root(),
 	}
+
 	coinHash := makeCoinGenerator(choice)
 
 	for j := uint64(0); j < nr; j++ {

diff --git a/crypto/compactcert/coinGenerator.go b/crypto/compactcert/coinGenerator.go
@@ -30,10 +30,11 @@ import (
 type coinChoiceSeed struct {
 	_struct struct{} `codec:",omitempty,omitemptyarray"`
 
-	SignedWeight uint64                `codec:"sigweight"`
-	Sigcom       crypto.GenericDigest  `codec:"sigcom"`
-	Partcom      crypto.GenericDigest  `codec:"partcom"`
-	MsgHash      StateProofMessageHash `codec:"msghash"`
+	MsgHash                 StateProofMessageHash `codec:"msghash"`
+	SignedWeight            uint64                `codec:"sigweight"`
+	LnProvenWeightThreshold uint64                `codec:"lnweight"`
+	Sigcom                  crypto.GenericDigest  `codec:"sigcom"`
+	Partcom                 crypto.GenericDigest  `codec:"partcom"`
 }
 
 // ToBeHashed implements the crypto.Hashable interface.

diff --git a/crypto/compactcert/verifier.go b/crypto/compactcert/verifier.go
@@ -101,10 +101,11 @@ func (v *Verifier) Verify(c *Cert) error {
 	}
 
 	choice := coinChoiceSeed{
-		SignedWeight: c.SignedWeight,
-		Sigcom:       c.SigCommit,
-		Partcom:      v.partcom,
-		MsgHash:      v.StateProofMessageHash,
+		MsgHash:                 v.StateProofMessageHash,
+		LnProvenWeightThreshold: v.lnProvenWeightThreshold,
+		SignedWeight:            c.SignedWeight,
+		Sigcom:                  c.SigCommit,
+		Partcom:                 v.partcom,
 	}
 
 	coinHash := makeCoinGenerator(choice)

diff --git a/crypto/compactcert/weights.go b/crypto/compactcert/weights.go
@@ -100,15 +100,15 @@ func (v *Verifier) verifyWeights(signedWeight uint64, numOfReveals uint64) error
 	// 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)
+	// w = d * (T - 1)
 	//
 	//  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)
+	y, a, w := getSubExpressions(signedWeight)
 	lhs := &big.Int{}
-	lhs.Set(b).
+	lhs.Set(w).
 		Mul(lhs, y).
 		Add(a, lhs).
 		Mul(bigInt(numOfReveals), lhs)
@@ -129,39 +129,33 @@ 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. we use value which satisfies the following equation:
 //
 // 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 {
+func (b *Builder) numReveals() (uint64, error) {
+	if b.ProvenWeightThreshold == 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)
+	// w = 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)
+	y, a, w := getSubExpressions(b.signedWeight)
 
-	numerator := bigInt(secKQ)
+	numerator := bigInt(b.SecKQ)
 	numerator.Mul(numerator, bigInt(ln2IntApproximation)).
 		Mul(numerator, y)
 
 	denom := &big.Int{}
-	denom.Set(b).
-		Sub(denom, bigInt(lnProvenWe)).
+	denom.Set(w).
+		Sub(denom, bigInt(b.lnProvenWeightThreshold)).
 		Mul(denom, y).
 		Add(a, denom)
 
@@ -179,7 +173,7 @@ func numReveals(signedWeight uint64, provenWeight uint64, secKQ uint64, bound ui
 // 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)
+// w = 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
@@ -207,7 +201,7 @@ func getSubExpressions(signedWeight uint64) (y *big.Int, a *big.Int, b *big.Int)
 		Mul(a, bigInt(3)).
 		Mul(a, bigInt(precisionBits))
 
-	// b = d*(T-1)
+	// w = d*(T-1)
 	b = bigInt(d)
 	b.Mul(b, bigInt(ln2IntApproximation-1))
 

diff --git a/crypto/compactcert/weights_test.go b/crypto/compactcert/weights_test.go
@@ -17,13 +17,25 @@
 package compactcert
 
 import (
+	"math"
+	"testing"
+
 	"github.com/algorand/go-algorand/crypto"
 	"github.com/algorand/go-algorand/test/partitiontest"
 	"github.com/stretchr/testify/require"
-	"math"
-	"testing"
 )
 
+func numRevealsForTests(signedWeight uint64, provenWeight uint64, secKQ uint64) (uint64, error) {
+	p := Params{SecKQ: secKQ, ProvenWeightThreshold: provenWeight}
+	lnProvenWt := lnIntApproximation(provenWeight, precisionBits)
+	b := &Builder{
+		Params:                  p,
+		signedWeight:            signedWeight,
+		lnProvenWeightThreshold: lnProvenWt,
+	}
+	return b.numReveals()
+}
+
 func TestVerifyMaxNumberOfRevealsInVerify(t *testing.T) {
 	partitiontest.PartitionTest(t)
 	a := require.New(t)
@@ -44,7 +56,7 @@ func TestVerifyMaxNumberOfReveals(t *testing.T) {
 	signedWeight := uint64(1<<10 + 1)
 	provenWeight := uint64(1 << 10)
 
-	_, err := numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
+	_, err := numRevealsForTests(signedWeight, provenWeight, compactCertSecKQForTests)
 	a.ErrorIs(err, ErrTooManyReveals)
 }
 
@@ -68,7 +80,7 @@ func TestVerifyImpliedProvenGreaterThanThreshold(t *testing.T) {
 	signedWeight := uint64(1<<10 + 93)
 	provenWeight := uint64(1 << 10)
 
-	numOfReveals, err := numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
+	numOfReveals, err := numRevealsForTests(signedWeight, provenWeight, compactCertSecKQForTests)
 
 	param := Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
 	verifier := MkVerifier(param, crypto.GenericDigest{})
@@ -78,7 +90,7 @@ func TestVerifyImpliedProvenGreaterThanThreshold(t *testing.T) {
 	signedWeight = uint64(1<<10 + 92)
 	provenWeight = uint64(1 << 10)
 
-	numOfReveals, err = numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
+	numOfReveals, err = numRevealsForTests(signedWeight, provenWeight, compactCertSecKQForTests)
 
 	param = Params{SecKQ: compactCertSecKQForTests, ProvenWeightThreshold: provenWeight}
 	verifier = MkVerifier(param, crypto.GenericDigest{})
@@ -93,7 +105,7 @@ func TestVerifyZeroNumberOfRevealsEquation(t *testing.T) {
 	signedWeight := uint64(1<<15 + 1)
 	provenWeight := uint64(1 << 15)
 
-	_, err := numReveals(signedWeight, provenWeight, compactCertSecKQForTests, MaxReveals)
+	_, err := numRevealsForTests(signedWeight, provenWeight, compactCertSecKQForTests)
 	a.ErrorIs(err, ErrNegativeNumOfRevealsEquation)
 }
 
@@ -143,7 +155,7 @@ func TestNumReveals(t *testing.T) {
 
 	for i := uint64(3); i < 10; i++ {
 		signedWeight := i * billion * microalgo
-		n, err := numReveals(signedWeight, provenWeight, secKQ, bound)
+		n, err := numRevealsForTests(signedWeight, provenWeight, secKQ)
 		require.NoError(t, err)
 		n2, err := old(signedWeight, provenWeight, secKQ, bound)
 		t.Logf("%f", float64(n2)/float64(n))
@@ -167,9 +179,8 @@ func BenchmarkWeight(b *testing.B) {
 	provenWeight := 100 * billion * microalgo
 	signedWeight := 110 * billion * microalgo
 	secKQ := uint64(compactCertSecKQForTests)
-	bound := uint64(1000)
 
-	nr, err := numReveals(signedWeight, provenWeight, secKQ, bound)
+	nr, err := numRevealsForTests(signedWeight, provenWeight, secKQ)
 	if nr < 900 {
 		b.Errorf("numReveals(%d, %d, %d) = %d < 900", signedWeight, provenWeight, secKQ, nr)
 	}
@@ -190,15 +201,14 @@ func BenchmarkNumReveals(b *testing.B) {
 	provenWeight := 100 * billion * microalgo
 	signedWeight := 110 * billion * microalgo
 	secKQ := uint64(compactCertSecKQForTests)
-	bound := uint64(1000)
 
-	nr, err := numReveals(signedWeight, provenWeight, secKQ, bound)
+	nr, err := numRevealsForTests(signedWeight, provenWeight, secKQ)
 	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)
+		_, err = numRevealsForTests(signedWeight, provenWeight, secKQ)
 		if err != nil {
 			b.Error(err)
 		}