Make stateproof verifier snark friendly (#3895)

* change coin filps to be shake(sumhash(seed)) * add sequence of coin positions to the cert * compute CC security using implied provenWeight * create a log2 appr func * fix stateproof message issues. * remove proven weight form the coin hash * fix cc test * use reject sampling in coin hash. * use logarithmic approximation * refactoring * builder uses same appox function * comments and doc * handle negative value in number of reveals equation * add lnProvenWe to coinhash * fixed hash representation for coinhash * fix CC benchmark * refactor * remove old numberofreveals code * change secKQ to 256 * fix CRs * CR fixes + rename * more CR fix * refactor the trusted params on the verifer. * more refactoring * fix flaky test * remove Param structure * more fixes * update falcon lib + use byte as salt version * add coinhash kat generator * fix some CR comments * clear out some documentation * Apply suggestions from code review Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com> * fix comments * refactor rejection sampling * CR fix * refactoring * fix comments * reduce the bytes allocated for stateproof message * Apply suggestions from code review Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com> * fix test since stateproof message hash was reduce * fix CR comments * more refactoring Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com>
algorand · May 10, 2022 · 8a53a76 · 8a53a76
1 parent 4009697
commit 8a53a76
Show file tree

Hide file tree

Showing 33 changed files with 1,525 additions and 1,354 deletions.
diff --git a/compactcert/builder.go b/compactcert/builder.go
@@ -64,15 +64,20 @@ func (ccw *Worker) builderForRound(rnd basics.Round) (builder, error) {
 	}
 	ccw.Message = msg
 
-	p, err := ledger.CompactCertParams(msg, votersHdr, hdr)
+	provenWeight, err := ledger.GetProvenWeight(votersHdr, hdr)
 	if err != nil {
 		return builder{}, err
 	}
 
 	var res builder
 	res.votersHdr = votersHdr
 	res.voters = voters
-	res.Builder, err = compactcert.MkBuilder(p, voters.Participants, voters.Tree)
+	res.Builder, err = compactcert.MkBuilder(msg.IntoStateProofMessageHash(),
+		uint64(hdr.Round),
+		provenWeight,
+		voters.Participants,
+		voters.Tree,
+		config.Consensus[votersHdr.CurrentProtocol].CompactCertStrengthTarget)
 	if err != nil {
 		return builder{}, err
 	}
@@ -96,35 +101,45 @@ func (ccw *Worker) initBuilders() {
 	}
 
 	for rnd, sigs := range roundSigs {
-		_, ok := ccw.builders[rnd]
-		if ok {
+		if _, ok := ccw.builders[rnd]; ok {
 			ccw.log.Warnf("initBuilders: round %d already present", rnd)
 			continue
 		}
+		ccw.addSigsToBuilder(sigs, rnd)
+	}
+}
 
-		builder, err := ccw.builderForRound(rnd)
-		if err != nil {
-			ccw.log.Warnf("initBuilders: builderForRound(%d): %v", rnd, err)
+func (ccw *Worker) addSigsToBuilder(sigs []pendingSig, rnd basics.Round) {
+	builderForRound, err := ccw.builderForRound(rnd)
+	if err != nil {
+		ccw.log.Warnf("addSigsToBuilder: builderForRound(%d): %v", rnd, err)
+		return
+	}
+
+	for _, sig := range sigs {
+		pos, ok := builderForRound.voters.AddrToPos[sig.signer]
+		if !ok {
+			ccw.log.Warnf("addSigsToBuilder: cannot find %v in round %d", sig.signer, rnd)
 			continue
 		}
 
-		for _, sig := range sigs {
-			pos, ok := builder.voters.AddrToPos[sig.signer]
-			if !ok {
-				ccw.log.Warnf("initBuilders: cannot find %v in round %d", sig.signer, rnd)
-				continue
-			}
-
-			if builder.Present(pos) {
-				ccw.log.Warnf("initBuilders: cannot add %v in round %d: position %d already added", sig.signer, rnd, pos)
-				continue
-			}
+		isPresent, err := builderForRound.Present(pos)
+		if err != nil {
+			ccw.log.Warnf("addSigsToBuilder: failed to invoke builderForRound.Present on pos %d - %w ", pos, err)
+			continue
+		}
+		if isPresent {
+			ccw.log.Warnf("addSigsToBuilder: cannot add %v in round %d: position %d already added", sig.signer, rnd, pos)
+			continue
+		}
 
-			if err := builder.IsValid(pos, sig.sig, false); err != nil {
-				ccw.log.Warnf("initBuilders: cannot add %v in round %d: %v", sig.signer, rnd, err)
-				continue
-			}
-			builder.Add(pos, sig.sig)
+		if err := builderForRound.IsValid(pos, sig.sig, false); err != nil {
+			ccw.log.Warnf("addSigsToBuilder: cannot add %v in round %d: %v", sig.signer, rnd, err)
+			continue
+		}
+		if err := builderForRound.Add(pos, sig.sig); err != nil {
+			ccw.log.Warnf("addSigsToBuilder: error while adding sig. inner error: %w", err)
+			continue
 		}
 	}
 }
@@ -149,7 +164,7 @@ func (ccw *Worker) handleSig(sfa sigFromAddr, sender network.Peer) (network.Forw
 	ccw.mu.Lock()
 	defer ccw.mu.Unlock()
 
-	builder, ok := ccw.builders[sfa.Round]
+	builderForRound, ok := ccw.builders[sfa.Round]
 	if !ok {
 		latest := ccw.ledger.Latest()
 		latestHdr, err := ccw.ledger.BlockHdr(latest)
@@ -163,23 +178,23 @@ func (ccw *Worker) handleSig(sfa sigFromAddr, sender network.Peer) (network.Forw
 			return network.Ignore, nil
 		}
 
-		builder, err = ccw.builderForRound(sfa.Round)
+		builderForRound, err = ccw.builderForRound(sfa.Round)
 		if err != nil {
 			return network.Disconnect, err
 		}
 	}
 
-	pos, ok := builder.voters.AddrToPos[sfa.Signer]
+	pos, ok := builderForRound.voters.AddrToPos[sfa.Signer]
 	if !ok {
 		return network.Disconnect, fmt.Errorf("handleSig: %v not in participants for %d", sfa.Signer, sfa.Round)
 	}
 
-	if builder.Present(pos) {
-		// Signature already part of the builder, ignore.
+	if isPresent, err := builderForRound.Present(pos); err != nil || isPresent {
+		// Signature already part of the builderForRound, ignore.
 		return network.Ignore, nil
 	}
 
-	if err := builder.IsValid(pos, sfa.Sig, true); err != nil {
+	if err := builderForRound.IsValid(pos, sfa.Sig, true); err != nil {
 		return network.Disconnect, err
 	}
 
@@ -194,7 +209,9 @@ func (ccw *Worker) handleSig(sfa sigFromAddr, sender network.Peer) (network.Forw
 		return network.Ignore, err
 	}
 	// validated that we can add the sig previously.
-	builder.Add(pos, sfa.Sig)
+	if err := builderForRound.Add(pos, sfa.Sig); err != nil {
+		return network.Ignore, err
+	}
 	return network.Broadcast, nil
 }
 

diff --git a/compactcert/worker_test.go b/compactcert/worker_test.go
@@ -294,18 +294,13 @@ func TestWorkerAllSigs(t *testing.T) {
 			provenWeight, overflowed := basics.Muldiv(uint64(s.totalWeight), uint64(proto.CompactCertWeightThreshold), 1<<32)
 			require.False(t, overflowed)
 
-			ccparams := compactcert.Params{
-				StateProofMessageHash: tx.Txn.CertMsg.IntoStateProofMessageHash(),
-				ProvenWeight:          provenWeight,
-				SigRound:              tx.Txn.CertIntervalLatestRound,
-				SecKQ:                 proto.CompactCertSecKQ,
-			}
-
 			voters, err := s.CompactCertVoters(tx.Txn.CertIntervalLatestRound - basics.Round(proto.CompactCertRounds) - basics.Round(proto.CompactCertVotersLookback))
 			require.NoError(t, err)
 
-			verif := compactcert.MkVerifier(ccparams, voters.Tree.Root())
-			err = verif.Verify(&tx.Txn.Cert)
+			verif, err := compactcert.MkVerifier(voters.Tree.Root(), provenWeight, proto.CompactCertStrengthTarget)
+			require.NoError(t, err)
+
+			err = verif.Verify(uint64(tx.Txn.CertIntervalLatestRound), tx.Txn.CertMsg.IntoStateProofMessageHash(), &tx.Txn.Cert)
 			require.NoError(t, err)
 			break
 		}
@@ -358,18 +353,12 @@ func TestWorkerPartialSigs(t *testing.T) {
 	provenWeight, overflowed := basics.Muldiv(uint64(s.totalWeight), uint64(proto.CompactCertWeightThreshold), 1<<32)
 	require.False(t, overflowed)
 
-	ccparams := compactcert.Params{
-		StateProofMessageHash: msg.IntoStateProofMessageHash(),
-		ProvenWeight:          provenWeight,
-		SigRound:              basics.Round(tx.Txn.CertIntervalLatestRound),
-		SecKQ:                 proto.CompactCertSecKQ,
-	}
-
 	voters, err := s.CompactCertVoters(tx.Txn.CertIntervalLatestRound - basics.Round(proto.CompactCertRounds) - basics.Round(proto.CompactCertVotersLookback))
 	require.NoError(t, err)
 
-	verif := compactcert.MkVerifier(ccparams, voters.Tree.Root())
-	err = verif.Verify(&tx.Txn.Cert)
+	verif, err := compactcert.MkVerifier(voters.Tree.Root(), provenWeight, proto.CompactCertStrengthTarget)
+	require.NoError(t, err)
+	err = verif.Verify(uint64(tx.Txn.CertIntervalLatestRound), msg.IntoStateProofMessageHash(), &tx.Txn.Cert)
 	require.NoError(t, err)
 }
 

diff --git a/config/consensus.go b/config/consensus.go
@@ -382,9 +382,8 @@ type ConsensusParams struct {
 	// The threshold is computed as CompactCertWeightThreshold/(1<<32).
 	CompactCertWeightThreshold uint32
 
-	// CompactCertSecKQ is the security parameter (k+q) for the compact
-	// certificate scheme.
-	CompactCertSecKQ uint64
+	// CompactCertStrengthTarget represents either k+q (for pre-quantum security) or k+2q (for post-quantum security)
+	CompactCertStrengthTarget uint64
 
 	// EnableAssetCloseAmount adds an extra field to the ApplyData. The field contains the amount of the remaining
 	// asset that were sent to the close-to address.
@@ -1130,7 +1129,7 @@ func initConsensusProtocols() {
 	vFuture.CompactCertTopVoters = 1024 * 1024
 	vFuture.CompactCertVotersLookback = 16
 	vFuture.CompactCertWeightThreshold = (1 << 32) * 30 / 100
-	vFuture.CompactCertSecKQ = 128
+	vFuture.CompactCertStrengthTarget = 256
 
 	vFuture.LogicSigVersion = 7
 

diff --git a/crypto/compactcert/bigfloat.go b/crypto/compactcert/bigfloat.go