Make stateproof verifier snark friendly #3895

id-ms · 2022-04-17T09:17:28Z

Summary

The goal of this PR is to change part of the stateproof (compactcert) verifier to be SNARK friendly.
this change contains:
1- The verifier no longer computes the exact number of reveals on the cert. Alternatively, it computes a lower bound on the proven weight.
2- To support 1, the verifier uses a log approximation technic.
3- use SHAKE256 for the coin hashing to be more SNARK friendly
4- use rejection sampling for selecting the next coin
5- the positions to reveal (the result of the coin hashing) are given as part of the cert.

Test Plan

unittest are updated

codecov-commenter · 2022-04-17T10:14:33Z

Codecov Report

Merging #3895 (9c6a06a) into feature/stateproofs (c34780a) will increase coverage by 0.02%.
The diff coverage is 67.37%.

@@                   Coverage Diff                   @@
##           feature/stateproofs    #3895      +/-   ##
=======================================================
+ Coverage                50.06%   50.08%   +0.02%     
=======================================================
  Files                      396      396              
  Lines                    68413    68364      -49     
=======================================================
- Hits                     34251    34242       -9     
+ Misses                   30454    30426      -28     
+ Partials                  3708     3696      -12

Impacted Files	Coverage Δ
crypto/merklesignature/merkleSignatureScheme.go	`68.81% <0.00%> (ø)`
data/stateproof/message.go	`0.00% <ø> (ø)`
ledger/ledger.go	`60.66% <0.00%> (ø)`
data/stateproof/msgp_gen.go	`36.25% <12.50%> (-5.94%)`	⬇️
crypto/compactcert/msgp_gen.go	`39.34% <39.66%> (-2.83%)`	⬇️
compactcert/builder.go	`66.99% <41.66%> (-2.12%)`	⬇️
crypto/compactcert/verifier.go	`78.26% <86.66%> (+14.62%)`	⬆️
ledger/internal/compactcert.go	`77.02% <87.50%> (ø)`
crypto/compactcert/builder.go	`89.00% <97.91%> (+20.11%)`	⬆️
config/consensus.go	`85.53% <100.00%> (ø)`
... and 17 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update c34780a...9c6a06a. Read the comment docs.

config/consensus.go

crypto/compactcert/weights.go

crypto/compactcert/const.go

crypto/compactcert/weights.go

Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com>

crypto/compactcert/weights.go

crypto/compactcert/coinGenerator.go

id-ms · 2022-04-28T15:25:39Z

@cpeikert could you please take a second look at the coinGenerator.go?
we've removed some unnecessary use of big.Int
https://github.com/algorand/go-algorand/pull/3895/files#diff-4862db594aa7aea35dee5566adeff18c0be35acdd4094abaeb50781613fc964f
Thanks!

crypto/compactcert/builder.go

algonautshant · 2022-04-29T20:17:04Z

crypto/compactcert/builder.go

-		copy(cpy, b.Params.StateProofMessageHash[:]) // TODO: onmce cfalcon is fixed can remove this copy.
-		if err := p.PK.VerifyBytes(uint64(b.SigRound), cpy, sig); err != nil {
+		cpy := make([]byte, len(b.data))
+		copy(cpy, b.data[:]) // TODO: onmce cfalcon is fixed can remove this copy.


Why is this copy still needed here?
The TODO comment seems can be resolved.

we still have a might have problem with c-falcon. when everything will be ready to merge into master we will remove it.

crypto/compactcert/builder.go

algonautshant · 2022-05-02T14:34:25Z

compactcert/builder.go

@@ -115,7 +120,7 @@ func (ccw *Worker) initBuilders() {
 				continue
 			}

-			if builder.Present(pos) {
+			if isPresent, err := builder.Present(pos); err != nil || isPresent {


The error message below needs to be updated here to also consider the possibility of the err and not just isPresent.

crypto/compactcert/builder.go

crypto/compactcert/weights.go

algonautshant · 2022-05-02T21:41:49Z

crypto/compactcert/builder.go

 	lo := uint64(0)
 	hi := uint64(len(b.sigs))

 again:
 	if lo >= hi {
-		return 0, fmt.Errorf("coinIndex: lo %d >= hi %d", lo, hi)
+		return 0, fmt.Errorf("%w: lo %d >= hi %d", ErrInternalCoinIndexError, lo, hi)


This should never happen in the code path. It is expected to have:

b.sigs[0].L = 0 // by construction b.sigs[last].L + b.sigs[last].Weight == signedWeight // b.sigs[last].L + b.sigs[last].Weight == signedWeight and coinWeight in [0, signedWeight)

In case it happens, the error should say something like:
coinIndex unexpected behavior: lo = %d hi = %d coinWeight = %d

algonautshant · 2022-05-04T00:42:20Z

ledger/internal/compactcert.go

 	}

 	if hdr.Round != votersHdr.Round+basics.Round(proto.CompactCertRounds) {
-		err = fmt.Errorf("certifying block %d not %d ahead of voters %d",
+		err := fmt.Errorf("certifying block %d not %d ahead of voters %d",


The convention followed elsewhere in the code, is to identify the reporter of the error, by mentioning the name of the function.
For example:

./cow_creatables.go�155: return fmt.Errorf("DeleteAppParams: %s not found in deltas for %d", addr.String(), aidx) ./cow_creatables.go�163: return fmt.Errorf("DeleteAppLocalState: %s not found in deltas for %d", addr.String(), aidx) ./cow_creatables.go�171: return fmt.Errorf("DeleteAssetHolding: %s not found in deltas for %d", addr.String(), aidx) ./cow_creatables.go�179: return fmt.Errorf("DeleteAssetParams: %s not found in deltas for %d", addr.String(), aidx)

This convention is not followed in many places in the compactCert code.

algonautshant · 2022-05-04T00:47:12Z

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


Returning the error directly like this is problematic. When eventually the error is logged or reported to the user, it will be very difficult, if not impossible, to know where the error came from.
The convention followed is to wrap the received error before reporting it upwards.
For example, see below (which should be %w and not %v):

ccw.log.Warnf("ccw.handleSigMessage(): decode: %v", err)

compactcert/builder.go

Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com>

algonautshant

Looks great!
The logic implementation is correct, well structured, and readable. Very well documented.
I don't have any more suggestions to change anything.
The tests cover the code very well.
Thank you for addressing my previous comments.

A few areas needs some improvement, which can be addressed in a separate PR:

The error reporting in many places do not list the function generating the error. These error messages need updating to identify the function generating them, as is the convention in the code.
When a function gets an error and returns it, it needs to wrap it and identify itself, so that when the error is logged upstream, not only the originator of the error is identified, but also the context in which the error occurred.
The tests do not cover many of the error cases. Most of these cases are fairly simple and basic, but some of them report in the error messages, local variable values. If these messages are not tested, possible panic situation may go unnoticed, and the program panics when it should just be an error.

crypto/compactcert/builder.go

algonautshant · 2022-05-04T20:22:14Z

crypto/merklesignature/merkleSignatureScheme.go

-	if !s.Signature.IsVersionEqual(version) {
-		return ErrInvalidSignatureVersion
+// IsSaltVersionEqual validates that the version of the signature is matching the expected version
+func (s *Signature) IsSaltVersionEqual(version byte) error {


We need a test for this.

it is being tested in TestFalconSignature_ValidateVersion and more important, it is being tested in TestBuilder_AddRejectsInvalidSigVersion .

algonautshant · 2022-05-04T20:22:46Z

crypto/merklesignature/merkleSignatureScheme.go

@@ -267,23 +267,23 @@ func (v *Verifier) VerifyBytes(round uint64, msg []byte, sig Signature) error {
 func (s *Signature) GetFixedLengthHashableRepresentation() ([]byte, error) {


Unit test is missing for this function.

it is being tested here TestSimulateSignatureVerification

crypto/compactcert/builder_test.go

crypto/compactcert/builder.go

crypto/compactcert/builder_test.go

crypto/compactcert/verifier_test.go

id-ms added Enhancement Team Sphinx labels Apr 17, 2022

id-ms self-assigned this Apr 17, 2022

id-ms linked an issue Apr 17, 2022 that may be closed by this pull request

make stateproofs verification SNARK-friendly #3407

Closed

4 tasks

id-ms force-pushed the make-stateproof-verifier-snark-friendly branch from ac56d80 to 6901d2a Compare April 17, 2022 09:23

algoidan added 24 commits April 17, 2022 17:24

change coin filps to be shake(sumhash(seed))

ebd1016

add sequence of coin positions to the cert

5446cae

compute CC security using implied provenWeight

4363c91

create a log2 appr func

3ee4616

fix stateproof message issues.

6f4de56

remove proven weight form the coin hash

92ce531

fix cc test

a21f7b7

use reject sampling in coin hash.

f8168fe

use logarithmic approximation

0afd674

refactoring

b548344

builder uses same appox function

27c4e11

comments and doc

b4c9be4

handle negative value in number of reveals equation

4ce22b6

add lnProvenWe to coinhash

40a9de2

fixed hash representation for coinhash

2f275f3

fix CC benchmark

c76184b

refactor

ac4df71

remove old numberofreveals code

8911552

change secKQ to 256

593b62f

fix CRs

e794180

CR fixes + rename

c13ce05

more CR fix

106e6f4

refactor the trusted params on the verifer.

a3507ad

more refactoring

3789b44

update falcon lib + use byte as salt version

cffa28a

id-ms requested a review from algonautshant April 19, 2022 15:08

add coinhash kat generator

dd70755

algonautshant reviewed Apr 25, 2022

View reviewed changes

fix some CR comments

485b44d

id-ms force-pushed the make-stateproof-verifier-snark-friendly branch from 026a39e to 485b44d Compare April 26, 2022 09:06

algonautshant reviewed Apr 26, 2022

View reviewed changes

crypto/compactcert/weights.go Show resolved Hide resolved

crypto/compactcert/weights.go Show resolved Hide resolved

crypto/compactcert/weights.go Show resolved Hide resolved

crypto/compactcert/weights.go Outdated Show resolved Hide resolved

algoidan and others added 2 commits April 27, 2022 10:24

clear out some documentation

2cea300

Apply suggestions from code review

2f03f65

Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com>

id-ms force-pushed the make-stateproof-verifier-snark-friendly branch from 82d799a to 2f03f65 Compare April 27, 2022 07:57

algonautshant reviewed Apr 27, 2022

View reviewed changes

crypto/compactcert/weights.go Show resolved Hide resolved

algonautshant reviewed Apr 28, 2022

View reviewed changes

fix comments

b566381

refactor rejection sampling

ab2a2ff

id-ms force-pushed the make-stateproof-verifier-snark-friendly branch from e929cab to ab2a2ff Compare April 28, 2022 20:37

algonautshant reviewed Apr 29, 2022

View reviewed changes

algoidan added 2 commits May 1, 2022 14:05

CR fix

112e5e7

refactoring

b7f38d9

algonautshant reviewed May 2, 2022

View reviewed changes

algoidan added 2 commits May 3, 2022 11:52

fix comments

25a33d3

reduce the bytes allocated for stateproof message

30ee541

algonautshant reviewed May 4, 2022

View reviewed changes

id-ms and others added 2 commits May 4, 2022 09:42

Apply suggestions from code review

ed9f141

Co-authored-by: Shant Karakashian <55754073+algonautshant@users.noreply.github.com>

fix test since stateproof message hash was reduce

5ae415b

algonautshant approved these changes May 5, 2022

View reviewed changes

algoidan added 2 commits May 8, 2022 15:32

fix CR comments

32a8164

more refactoring

9c6a06a

algonautshant approved these changes May 9, 2022

View reviewed changes

id-ms merged commit 8a53a76 into algorand:feature/stateproofs May 10, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Make stateproof verifier snark friendly #3895

Make stateproof verifier snark friendly #3895

id-ms commented Apr 17, 2022 •

edited

Loading

codecov-commenter commented Apr 17, 2022 •

edited

Loading

id-ms commented Apr 28, 2022 •

edited

Loading

algonautshant Apr 29, 2022

id-ms May 1, 2022

algonautshant May 2, 2022

algonautshant May 2, 2022

algonautshant May 4, 2022

algonautshant May 4, 2022

algonautshant left a comment

algonautshant May 4, 2022

id-ms May 8, 2022

algonautshant May 4, 2022

id-ms May 8, 2022

		@@ -267,23 +267,23 @@ func (v *Verifier) VerifyBytes(round uint64, msg []byte, sig Signature) error {
		func (s *Signature) GetFixedLengthHashableRepresentation() ([]byte, error) {

Make stateproof verifier snark friendly #3895

Make stateproof verifier snark friendly #3895

Conversation

id-ms commented Apr 17, 2022 • edited Loading

Summary

Test Plan

codecov-commenter commented Apr 17, 2022 • edited Loading

Codecov Report

id-ms commented Apr 28, 2022 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

algonautshant left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

id-ms commented Apr 17, 2022 •

edited

Loading

codecov-commenter commented Apr 17, 2022 •

edited

Loading

id-ms commented Apr 28, 2022 •

edited

Loading