Fix a bug in Credential.lowestOutput caused by improper domain separa…

…tion (#716) * Fix a bug in Credential.lowestOutput caused by improper domain separation The bug causes larger accounts to be block proposers more often than should happen based on their fraction of online stake. This patch will cause nodes to vote for a protocol upgrade that fixes the buggy behavior. After the protocol upgrade goes through, all the upgrade-related code in this commit should be removed, as it's not necessary to retain the old buggy behavior for catchup. (For convenience code to be removed is marked with a "TODO(upgrade)" comment.) * Typofix; fix merge issue * Fix test * Add a comment to make the linter happy * Typo fixes
algorand · Jan 22, 2020 · ec4d9b5 · ec4d9b5
1 parent c78ada0
commit ec4d9b5
Show file tree

Hide file tree

Showing 5 changed files with 113 additions and 11 deletions.
diff --git a/agreement/proposalTracker.go b/agreement/proposalTracker.go
@@ -19,6 +19,7 @@ package agreement
 import (
 	"fmt"
 
+	"github.com/algorand/go-algorand/config" // TODO(upgrade): Please remove this line after the upgrade goes through
 	"github.com/algorand/go-algorand/data/basics"
 	"github.com/algorand/go-algorand/logging"
 )
@@ -37,14 +38,23 @@ type proposalSeeker struct {
 
 // accept compares a given vote with the current lowest-credentialled vote and
 // sets it if freeze has not been called.
-func (s proposalSeeker) accept(v vote) (proposalSeeker, error) {
+// TODO(upgrade): Please remove the "useBuggyLowestOutput" argument as soon as the protocol upgrade goes through
+func (s proposalSeeker) accept(v vote, useBuggyLowestOutput bool) (proposalSeeker, error) {
 	if s.Frozen {
 		return s, errProposalSeekerFrozen{}
 	}
 
-	if s.Filled && !v.Cred.Less(s.Lowest.Cred) {
-		return s, errProposalSeekerNotLess{NewSender: v.R.Sender, LowestSender: s.Lowest.R.Sender}
-	}
+	// TODO(upgrade): Please remove the lines below as soon as the upgrade goes through
+	if useBuggyLowestOutput {
+		if s.Filled && !v.Cred.LessBuggy(s.Lowest.Cred) {
+			return s, errProposalSeekerNotLess{NewSender: v.R.Sender, LowestSender: s.Lowest.R.Sender}
+		}
+	} else {
+		// TODO(upgrade): Please remove the lines above as soon as the upgrade goes through
+		if s.Filled && !v.Cred.Less(s.Lowest.Cred) {
+			return s, errProposalSeekerNotLess{NewSender: v.R.Sender, LowestSender: s.Lowest.R.Sender}
+		}
+	} // TODO(upgrade): Please remove this line when the upgrade goes through
 
 	s.Lowest = v
 	s.Filled = true
@@ -146,7 +156,7 @@ func (t *proposalTracker) handle(r routerHandle, p player, e event) event {
 		}
 
 		var err error
-		t.Freezer, err = t.Freezer.accept(v)
+		t.Freezer, err = t.Freezer.accept(v, config.Consensus[e.Proto.Version].UseBuggyProposalLowestOutput) // TODO(upgrade): Please remove the second argument as soon as the upgrade goes through
 		if err != nil {
 			err := errProposalTrackerPS{Sub: err}
 			return filteredEvent{T: voteFiltered, Err: makeSerErr(err)}

diff --git a/agreement/proposalTracker_test.go b/agreement/proposalTracker_test.go
@@ -62,19 +62,19 @@ func TestProposalTrackerProposalSeeker(t *testing.T) {
 	assert.False(t, s.Filled)
 
 	// issue events in the following order: 2, 3, 1, (freeze), 0
-	s, err = s.accept(votes[2])
+	s, err = s.accept(votes[2], false) //TODO(upgrade) delete the ", false"
 	assert.NoError(t, err)
 	assert.False(t, s.Frozen)
 	assert.True(t, s.Filled)
 	assert.True(t, s.Lowest.equals(votes[2]))
 
-	s, err = s.accept(votes[3])
+	s, err = s.accept(votes[3], false) //TODO(upgrade) delete the ", false"
 	assert.Error(t, err)
 	assert.False(t, s.Frozen)
 	assert.True(t, s.Filled)
 	assert.True(t, s.Lowest.equals(votes[2]))
 
-	s, err = s.accept(votes[1])
+	s, err = s.accept(votes[1], false) //TODO(upgrade) delete the ", false"
 	assert.NoError(t, err)
 	assert.False(t, s.Frozen)
 	assert.True(t, s.Filled)
@@ -85,7 +85,7 @@ func TestProposalTrackerProposalSeeker(t *testing.T) {
 	assert.True(t, s.Filled)
 	assert.True(t, s.Lowest.equals(votes[1]))
 
-	s, err = s.accept(votes[0])
+	s, err = s.accept(votes[0], false) //TODO(upgrade) delete the ", false"
 	assert.Error(t, err)
 	assert.True(t, s.Frozen)
 	assert.True(t, s.Filled)

diff --git a/config/config.go b/config/config.go
@@ -237,6 +237,10 @@ type ConsensusParams struct {
 
 	// max decimal precision for assets
 	MaxAssetDecimals uint32
+
+	// whether to use the old buggy Credential.lowestOutput function
+	// TODO(upgrade): Please remove as soon as the upgrade goes through
+	UseBuggyProposalLowestOutput bool
 }
 
 // Consensus tracks the protocol-level settings for different versions of the
@@ -311,6 +315,7 @@ func initConsensusProtocols() {
 		MaxBalLookback: 320,
 
 		MaxTxGroupSize: 1,
+		UseBuggyProposalLowestOutput: true, // TODO(upgrade): Please remove as soon as the upgrade goes through
 	}
 
 	v7.ApprovedUpgrades = map[protocol.ConsensusVersion]uint64{}
@@ -476,9 +481,17 @@ func initConsensusProtocols() {
 	// v19 can be upgraded to v20.
 	v19.ApprovedUpgrades[protocol.ConsensusV20] = 0
 
+	// v21 fixes a bug in Credential.lowestOutput that would cause larger accounts to be selected to propose disproportionately more often than small accounts
+	v21 := v20
+	v21.ApprovedUpgrades = map[protocol.ConsensusVersion]uint64{}
+	v21.UseBuggyProposalLowestOutput = false // TODO(upgrade): Please remove this line as soon as the protocol upgrade goes through
+	Consensus[protocol.ConsensusV21] = v21
+	// v20 can be upgraded to v21.
+	v20.ApprovedUpgrades[protocol.ConsensusV21] = 0
+
 	// ConsensusFuture is used to test features that are implemented
 	// but not yet released in a production protocol version.
-	vFuture := v20
+	vFuture := v21
 	vFuture.ApprovedUpgrades = map[protocol.ConsensusVersion]uint64{}
 	vFuture.MinUpgradeWaitRounds = 10000
 	vFuture.MaxUpgradeWaitRounds = 150000

diff --git a/data/committee/credential.go b/data/committee/credential.go
@@ -134,6 +134,7 @@ func MakeCredential(secrets *crypto.VrfPrivkey, sel Selector) UnauthenticatedCre
 
 // Less returns true if this Credential is less than the other credential; false
 // otherwise (i.e., >=).
+// Used for breaking ties when there are multiple proposals.
 //
 // Precondition: both credentials have nonzero weight
 func (cred Credential) Less(otherCred Credential) bool {
@@ -155,9 +156,60 @@ func (cred Credential) Selected() bool {
 	return cred.Weight > 0
 }
 
+// lowestOutput is used for breaking ties when there are multiple proposals.
+// People will vote for the proposal whose credential has the lowest lowestOutput.
+//
+// We hash the credential and interpret the output as a bigint.
+// For credentials with weight w > 1, we hash the credential w times (with
+// different counter values) and use the lowest output.
+//
+// This is because a weight w credential is simulating being selected to be on the
+// leader committee w times, so each of the w proposals would have a different hash,
+// and the lowest would win.
 func (cred Credential) lowestOutput() *big.Int {
 	var lowest big.Int
 
+	h1 := cred.VrfOut
+	// It is important that i start at 1 rather than 0 because cred.Hashable
+	// was already hashed with iter = 0 earlier (in UnauthenticatedCredential.Verify)
+	// for determining the weight of the credential. A nonzero iter provides
+	// domain separation between lowestOutput and UnauthenticatedCredential.Verify
+	//
+	// If we reused the iter = 0 hash output here it would be nonuniformly
+	// distributed (because lowestOutput can only get called if weight > 0).
+	// In particular if i starts at 0 then weight-1 credentials are at a
+	// significant disadvantage because UnauthenticatedCredential.Verify
+	// wants the hash to be large but tiebreaking between proposals wants
+	// the hash to be small.
+	for i := uint64(1); i <= cred.Weight; i++ {
+		var h crypto.Digest
+		if cred.DomainSeparationEnabled {
+			cred.Hashable.Iter = i
+			h = crypto.HashObj(cred.Hashable)
+		} else {
+			var h2 crypto.Digest
+			binary.BigEndian.PutUint64(h2[:], i)
+			h = crypto.Hash(append(h1[:], h2[:]...))
+		}
+
+		if i == 1 {
+			lowest.SetBytes(h[:])
+		} else {
+			var temp big.Int
+			temp.SetBytes(h[:])
+			if temp.Cmp(&lowest) < 0 {
+				lowest.Set(&temp)
+			}
+		}
+	}
+
+	return &lowest
+}
+
+// TODO(upgrade): Please remove the entire lowestOutputBuggy function as soon as the corresponding protocol upgrade goes through.
+func (cred Credential) lowestOutputBuggy() *big.Int {
+	var lowest big.Int
+
 	h1 := cred.VrfOut
 	for i := uint64(0); i < cred.Weight; i++ {
 		var h crypto.Digest
@@ -184,6 +236,28 @@ func (cred Credential) lowestOutput() *big.Int {
 	return &lowest
 }
 
+// LessBuggy is the buggy version of Less
+// TODO(upgrade): Please remove the entire LessBuggy function as soon as the corresponding protocol upgrade goes through
+func (cred Credential) LessBuggy(otherCred Credential) bool {
+	i1 := cred.lowestOutputBuggy()
+	i2 := otherCred.lowestOutputBuggy()
+
+	return i1.Cmp(i2) < 0
+}
+
+// LowestOutputDigest gives the lowestOutput as a crypto.Digest, which allows
+// pretty-printing a proposal's lowest output.
+// This function is only used for debugging.
+func (cred Credential) LowestOutputDigest() crypto.Digest {
+	lbytes := cred.lowestOutput().Bytes()
+	var out crypto.Digest
+	if len(lbytes) > len(out) {
+		panic("Cred lowest output too long")
+	}
+	copy(out[len(out) - len(lbytes):], lbytes)
+	return out
+}
+
 func (cred hashableCredential) ToBeHashed() (protocol.HashID, []byte) {
 	return protocol.Credential, protocol.Encode(cred)
 }
diff --git a/protocol/consensus.go b/protocol/consensus.go
@@ -113,6 +113,11 @@ const ConsensusV20 = ConsensusVersion(
 	"https://github.com/algorandfoundation/specs/tree/4a9db6a25595c6fd097cf9cc137cc83027787eaa",
 )
 
+// ConsensusV21 fixes a bug in credential.lowestOutput
+const ConsensusV21 = ConsensusVersion(
+	"https://github.com/algorandfoundation/specs/tree/8096e2df2da75c3339986317f9abe69d4fa86b4b",
+)
+
 // ConsensusFuture is a protocol that should not appear in any production
 // network, but is used to test features before they are released.
 const ConsensusFuture = ConsensusVersion(
@@ -125,7 +130,7 @@ const ConsensusFuture = ConsensusVersion(
 
 // ConsensusCurrentVersion is the latest version and should be used
 // when a specific version is not provided.
-const ConsensusCurrentVersion = ConsensusV20
+const ConsensusCurrentVersion = ConsensusV21
 
 // ConsensusTest0 is a version of ConsensusV0 used for testing
 // (it has different approved upgrade paths).