Algod: State Proofs (algorand#4226)

Enable state proofs to allow external parties to efficiently validate Algorand stake. Summary of changes: * make state proof verifier SNARK friendly * relaxing the Merkle signature scheme ephemerality * define lightBlockHeaders * define Algorand's state as a commitment on the lightBlockHeaders within a state proof interval * limit the resources (memory and network bandwidth) if state proofs chain stalls Co-authored-by: Jonathan Weiss <85506383+algonathan@users.noreply.github.com> Co-authored-by: Or Aharonee <or.aharonee@algorand.com> Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com> Co-authored-by: Almog Tal <107349997+almog-t@users.noreply.github.com>
mangoplane · Aug 9, 2022 · 2bc55c0 · 2bc55c0
1 parent 49086e8
commit 2bc55c0
Show file tree

Hide file tree

Showing 172 changed files with 14,433 additions and 7,770 deletions.
diff --git a/Makefile b/Makefile
@@ -86,7 +86,7 @@ GOLDFLAGS := $(GOLDFLAGS_BASE) \
 UNIT_TEST_SOURCES := $(sort $(shell GOPATH=$(GOPATH) && GO111MODULE=off && go list ./... | grep -v /go-algorand/test/ ))
 ALGOD_API_PACKAGES := $(sort $(shell GOPATH=$(GOPATH) && GO111MODULE=off && cd daemon/algod/api; go list ./... ))
 
-MSGP_GENERATE	:= ./protocol ./protocol/test ./crypto ./crypto/merklearray ./crypto/merklesignature ./crypto/compactcert ./data/basics ./data/transactions ./data/committee ./data/bookkeeping ./data/hashable ./agreement ./rpcs ./node ./ledger ./ledger/ledgercore ./compactcert ./data/account ./daemon/algod/api/spec/v2
+MSGP_GENERATE	:= ./protocol ./protocol/test ./crypto ./crypto/merklearray ./crypto/merklesignature ./crypto/stateproof ./data/basics ./data/transactions ./data/stateproofmsg ./data/committee ./data/bookkeeping ./data/hashable ./agreement ./rpcs ./node ./ledger ./ledger/ledgercore ./stateproof ./data/account ./daemon/algod/api/spec/v2
 
 default: build
 

diff --git a/agreement/msgp_gen.go b/agreement/msgp_gen.go
diff --git a/catchup/catchpointService.go b/catchup/catchpointService.go
@@ -19,6 +19,7 @@ package catchup
 import (
 	"context"
 	"fmt"
+	"github.com/algorand/go-algorand/stateproof"
 	"sync"
 	"time"
 
@@ -464,6 +465,19 @@ func (cs *CatchpointCatchupService) processStageLastestBlockDownload() (err erro
 	return nil
 }
 
+// lookbackForStateproofsSupport calculates the lookback (from topblock round) needed to be downloaded
+// in order to support state proofs verification.
+func lookbackForStateproofsSupport(topBlock *bookkeeping.Block) uint64 {
+	proto := config.Consensus[topBlock.CurrentProtocol]
+	if proto.StateProofInterval == 0 {
+		return 0
+	}
+	lowestStateProofRound := stateproof.GetOldestExpectedStateProof(&topBlock.BlockHeader)
+	// in order to be able to confirm lowestStateProofRound we need to have round number: (lowestStateProofRound - stateproofInterval)
+	lowestStateProofRound = lowestStateProofRound.SubSaturate(basics.Round(proto.StateProofInterval))
+	return uint64(topBlock.Round().SubSaturate(lowestStateProofRound))
+}
+
 // processStageBlocksDownload is the fourth catchpoint catchup stage. It downloads all the reminder of the blocks, verifying each one of them against it's predecessor.
 func (cs *CatchpointCatchupService) processStageBlocksDownload() (err error) {
 	topBlock, err := cs.ledgerAccessor.EnsureFirstBlock(cs.ctx)
@@ -478,6 +492,11 @@ func (cs *CatchpointCatchupService) processStageBlocksDownload() (err error) {
 	if lookback < proto.MaxBalLookback {
 		lookback = proto.MaxBalLookback
 	}
+
+	lookbackForStateProofSupport := lookbackForStateproofsSupport(&topBlock)
+	if lookback < lookbackForStateProofSupport {
+		lookback = lookbackForStateProofSupport
+	}
 	// in case the effective lookback is going before our rounds count, trim it there.
 	// ( a catchpoint is generated starting round MaxBalLookback, and this is a possible in any round in the range of MaxBalLookback..MaxTxnLife)
 	if lookback >= uint64(topBlock.Round()) {

diff --git a/catchup/service_test.go b/catchup/service_test.go
@@ -26,6 +26,7 @@ import (
 	"time"
 
 	"github.com/algorand/go-deadlock"
+	"github.com/stretchr/testify/assert"
 	"github.com/stretchr/testify/require"
 
 	"github.com/algorand/go-algorand/agreement"
@@ -957,7 +958,7 @@ func TestServiceStartStop(t *testing.T) {
 	s := MakeService(logging.Base(), cfg, &httpTestPeerSource{}, ledger, &mockedAuthenticator{errorRound: int(0 + 1)}, nil, nil)
 	s.Start()
 	s.Stop()
-	_, ok := (<-s.done)
+	_, ok := <-s.done
 	require.False(t, ok)
 }
 
@@ -973,3 +974,39 @@ func TestSynchronizingTime(t *testing.T) {
 	atomic.StoreInt64(&s.syncStartNS, 1000000)
 	require.NotEqual(t, time.Duration(0), s.SynchronizingTime())
 }
+
+func TestDownloadBlocksToSupportStateProofs(t *testing.T) {
+	partitiontest.PartitionTest(t)
+	// make sure we download enough blocks to verify state proof 512
+	topBlk := bookkeeping.Block{}
+	topBlk.BlockHeader.Round = 1500
+	topBlk.BlockHeader.CurrentProtocol = protocol.ConsensusFuture
+	trackingData := bookkeeping.StateProofTrackingData{StateProofNextRound: 512}
+	topBlk.BlockHeader.StateProofTracking = make(map[protocol.StateProofType]bookkeeping.StateProofTrackingData)
+	topBlk.BlockHeader.StateProofTracking[protocol.StateProofBasic] = trackingData
+
+	lookback := lookbackForStateproofsSupport(&topBlk)
+	oldestRound := topBlk.BlockHeader.Round.SubSaturate(basics.Round(lookback))
+	assert.Equal(t, uint64(oldestRound), 512-config.Consensus[protocol.ConsensusFuture].StateProofInterval)
+
+	// the network has made progress and now it is on round 8000. in this case we would not download blocks to cover 512.
+	// instead, we will download blocks to confirm only the recovery period lookback.
+	topBlk = bookkeeping.Block{}
+	topBlk.BlockHeader.Round = 8000
+	topBlk.BlockHeader.CurrentProtocol = protocol.ConsensusFuture
+	trackingData = bookkeeping.StateProofTrackingData{StateProofNextRound: 512}
+	topBlk.BlockHeader.StateProofTracking = make(map[protocol.StateProofType]bookkeeping.StateProofTrackingData)
+	topBlk.BlockHeader.StateProofTracking[protocol.StateProofBasic] = trackingData
+
+	lookback = lookbackForStateproofsSupport(&topBlk)
+	oldestRound = topBlk.BlockHeader.Round.SubSaturate(basics.Round(lookback))
+
+	lowestRoundToRetain := 8000 - (8000 % 256) - (config.Consensus[protocol.ConsensusFuture].StateProofInterval * (config.Consensus[protocol.ConsensusFuture].StateProofMaxRecoveryIntervals + 1))
+	assert.Equal(t, uint64(oldestRound), lowestRoundToRetain)
+
+	topBlk = bookkeeping.Block{}
+	topBlk.BlockHeader.Round = 8000
+	topBlk.BlockHeader.CurrentProtocol = protocol.ConsensusV32
+	lookback = lookbackForStateproofsSupport(&topBlk)
+	assert.Equal(t, uint64(0), lookback)
+}
diff --git a/cmd/algokey/part.go b/cmd/algokey/part.go
@@ -168,8 +168,9 @@ func printPartkey(partkey account.Participation) {
 	fmt.Printf("Parent address:    %s\n", partkey.Parent.String())
 	fmt.Printf("VRF public key:    %s\n", base64.StdEncoding.EncodeToString(partkey.VRF.PK[:]))
 	fmt.Printf("Voting public key: %s\n", base64.StdEncoding.EncodeToString(partkey.Voting.OneTimeSignatureVerifier[:]))
-	if partkey.StateProofSecrets != nil && !partkey.StateProofSecrets.GetVerifier().IsEmpty() {
-		fmt.Printf("State proof key:   %s\n", base64.StdEncoding.EncodeToString(partkey.StateProofSecrets.GetVerifier()[:]))
+	if partkey.StateProofSecrets != nil && !partkey.StateProofSecrets.GetVerifier().MsgIsZero() {
+		fmt.Printf("State proof key:   %s\n", base64.StdEncoding.EncodeToString(partkey.StateProofSecrets.GetVerifier().Commitment[:]))
+		fmt.Printf("State proof key lifetime:   %d\n", partkey.StateProofSecrets.GetVerifier().KeyLifetime)
 	}
 	fmt.Printf("First round:       %d\n", partkey.FirstValid)
 	fmt.Printf("Last round:        %d\n", partkey.LastValid)