Merge pull request algorand#5633 from Algo-devops-service/relstable3.…

…17.0
PhearNet · Aug 4, 2023 · 2699dff · 2699dff
2 parents a3a9f62 + 8038555
commit 2699dff
Show file tree

Hide file tree

Showing 27 changed files with 644 additions and 78 deletions.
diff --git a/curve25519.go b/curve25519.go
@@ -210,7 +210,6 @@ func (s *SignatureSecrets) SignBytes(message []byte) Signature {
 // signed a Hashable message.
 //
 // It returns true if this is the case; otherwise, it returns false.
-//
 func (v SignatureVerifier) Verify(message Hashable, sig Signature) bool {
 	cryptoSigSecretsVerifyTotal.Inc(nil)
 	return ed25519Verify(ed25519PublicKey(v), HashRep(message), ed25519Signature(sig))

diff --git a/digest.go b/digest.go
@@ -19,6 +19,7 @@ package crypto
 import "bytes"
 
 // GenericDigest is a digest that implements CustomSizeDigest, and can be used as hash output.
+//
 //msgp:allocbound GenericDigest MaxHashDigestSize
 type GenericDigest []byte
 

diff --git a/hashes.go b/hashes.go
@@ -50,14 +50,15 @@ const (
 // a longer output is introduced.
 const MaxHashDigestSize = SumhashDigestSize
 
-//size of each hash
+// size of each hash
 const (
 	Sha512_256Size    = sha512.Size256
 	SumhashDigestSize = sumhash.Sumhash512DigestSize
 	Sha256Size        = sha256.Size
 )
 
 // HashFactory is responsible for generating new hashes accordingly to the type it stores.
+//
 //msgp:postunmarshalcheck HashFactory Validate
 type HashFactory struct {
 	_struct struct{} `codec:",omitempty,omitemptyarray"`

diff --git a/merklearray/layer.go b/merklearray/layer.go
@@ -26,6 +26,7 @@ import (
 // A Layer of the Merkle tree consists of a dense array of hashes at that
 // level of the tree.  Hashes beyond the end of the array (e.g., if the
 // number of leaves is not an exact power of 2) are implicitly zero.
+//
 //msgp:allocbound Layer MaxNumLeavesOnEncodedTree
 type Layer []crypto.GenericDigest
 

diff --git a/merklearray/merkle.go b/merklearray/merkle.go
@@ -24,6 +24,7 @@ import (
 	"sort"
 
 	"github.com/algorand/go-algorand/crypto"
+	"golang.org/x/exp/slices"
 )
 
 const (
@@ -223,7 +224,7 @@ func (tree *Tree) Prove(idxs []uint64) (*Proof, error) {
 		idxs = VcIdxs
 	}
 
-	sort.Slice(idxs, func(i, j int) bool { return idxs[i] < idxs[j] })
+	slices.Sort(idxs)
 
 	return tree.createProof(idxs)
 }

diff --git a/merklearray/msgp_gen.go b/merklearray/msgp_gen.go
diff --git a/merklearray/partial.go b/merklearray/partial.go
@@ -62,6 +62,7 @@ func (s *siblings) get(l uint64, i uint64) (res crypto.GenericDigest, err error)
 // partialLayer represents a subset of a Layer (i.e., nodes at some
 // level in the Merkle tree).  layerItem represents one element in the
 // partial Layer.
+//
 //msgp:ignore partialLayer
 type partialLayer []layerItem
 

diff --git a/merklearray/proof.go b/merklearray/proof.go
@@ -20,11 +20,38 @@ import (
 	"fmt"
 
 	"github.com/algorand/go-algorand/crypto"
+	"github.com/algorand/msgp/msgp"
 )
 
 // Proof is used to convince a verifier about membership of leaves: h0,h1...hn
 // at indexes i0,i1...in on a tree. The verifier has a trusted value of the tree
 // root hash.
+// Path is bounded by MaxNumLeaves since there could be multiple reveals, and
+// given the distribution of the elt positions and the depth of the tree,
+// the path length can increase up to 2^MaxTreeDepth / 2
+//
+// . Consider two different reveals for the same tree:
+// .
+// .                z5
+// .         z3              z4
+// .     y       z       z1      z2
+// .   q   r   s   t   u   v   w   x
+// .  a b c d e f g h i j k l m n o p
+// .    ^
+// . hints: [a, r, z, z4]
+// . len(hints) = 4
+// . You need a to combine with b to get q, need r to combine with the computed q and get y, and so on.
+// . The worst case is this:
+// .
+// .               z5
+// .        z3              z4
+// .    y       z       z1      z2
+// .  q   r   s   t   u   v   w   x
+// . a b c d e f g h i j k l m n o p
+// . ^   ^     ^   ^ ^   ^     ^   ^
+// .
+// . hints: [b, d, e, g, j, l, m, o]
+// . len(hints) = 2^4/2
 type Proof struct {
 	_struct struct{} `codec:",omitempty,omitemptyarray"`
 
@@ -41,12 +68,34 @@ type Proof struct {
 // SingleLeafProof is used to convince a verifier about membership of a specific
 // leaf h at index i on a tree. The verifier has a trusted value of the tree
 // root hash. it corresponds to merkle verification path.
+// The msgp directive belows tells msgp to not generate SingleLeafProofMaxSize method since we have one manually defined in this file.
+//
+//msgp:maxsize ignore SingleLeafProof
 type SingleLeafProof struct {
 	_struct struct{} `codec:",omitempty,omitemptyarray"`
 
 	Proof
 }
 
+// ProofMaxSizeByElements returns the maximum msgp encoded size of merklearray.Proof structs containing n signatures
+// This is necessary because the allocbounds on the proof are actual theoretical bounds but for calculating maximum
+// proof size for individual message types we have smaller valid bounds.
+// Exported because it's used in the stateproof package for ensuring that SigPartProof constant is correct size.
+func ProofMaxSizeByElements(n int) (s int) {
+	s = 1 + 4
+	// Calculating size of slice: z.Path
+	s += msgp.ArrayHeaderSize + n*(crypto.GenericDigestMaxSize())
+	s += 4 + crypto.HashFactoryMaxSize() + 3 + msgp.Uint8Size
+	return
+}
+
+// SingleLeafProofMaxSize returns the maximum msgp encoded size of proof verifying a single leaf
+// It is manually defined here instead of letting msgp do it since we cannot annotate the embedded Proof struct
+// with maxtotalbytes for msgp to autogenerate it.
+func SingleLeafProofMaxSize() int {
+	return ProofMaxSizeByElements(MaxEncodedTreeDepth)
+}
+
 // GetFixedLengthHashableRepresentation serializes the proof into a sequence of bytes.
 // it basically concatenates the elements of the verification path one after another.
 // The function returns a fixed length array for each hash function. which is 1 + MaxEncodedTreeDepth * digestsize

diff --git a/merklearray/proof_test.go b/merklearray/proof_test.go
@@ -244,3 +244,12 @@ func recomputePath(p []byte) []crypto.GenericDigest {
 	}
 	return computedPath
 }
+
+func TestMaxSizeCalculation(t *testing.T) {
+	partitiontest.PartitionTest(t)
+	t.Parallel()
+
+	// Ensure that the manually generated ProofMaxSizeByElements matches the autogenerated ProofMaxSize() function
+	// If this breaks either the allocbound has changed or the Proof struct definition has changed
+	require.Equal(t, ProofMaxSizeByElements(MaxNumLeavesOnEncodedTree/2), ProofMaxSize())
+}
diff --git a/merklesignature/merkleSignatureScheme_test.go b/merklesignature/merkleSignatureScheme_test.go
@@ -509,7 +509,7 @@ func TestGetAllKeys(t *testing.T) {
 	a.Equal(0, len(keys))
 }
 
-//#region Helper Functions
+// #region Helper Functions
 func makeSig(signer *Secrets, sigRound uint64, a *require.Assertions) ([]byte, Signature) {
 	msg := genMsgForTest()
 

diff --git a/merklesignature/msgp_gen.go b/merklesignature/msgp_gen.go
diff --git a/merkletrie/cache.go b/merkletrie/cache.go
@@ -21,7 +21,9 @@ import (
 	"encoding/binary"
 	"errors"
 	"fmt"
-	"sort"
+
+	"golang.org/x/exp/maps"
+	"golang.org/x/exp/slices"
 )
 
 // storedNodeIdentifier is the "equivalent" of a node-ptr, but oriented around persisting the
@@ -446,11 +448,8 @@ func (mtc *merkleTrieCache) reallocatePendingPages(stats *CommitStats) (pagesToC
 	}
 
 	// create a sorted list of created pages
-	sortedCreatedPages := make([]uint64, 0, len(createdPages))
-	for page := range createdPages {
-		sortedCreatedPages = append(sortedCreatedPages, page)
-	}
-	sort.SliceStable(sortedCreatedPages, func(i, j int) bool { return sortedCreatedPages[i] < sortedCreatedPages[j] })
+	sortedCreatedPages := maps.Keys(createdPages)
+	slices.Sort(sortedCreatedPages)
 
 	mtc.reallocatedPages = make(map[uint64]map[storedNodeIdentifier]*node)