Threshold Multisignature implementation by ValarDragon · Pull Request #2164 · tendermint/tendermint

ValarDragon · 2018-08-07T02:19:24Z

This adds an implementation of the threshold multisig. I also merged develop in, for the change to the crypto.Signature interface. This is the only commit with new code changes: e7dd76c.

This may be easier to review if we merged the compact bitmap PR first, and then I aimed this PR at develop / remade this PR.

Updated all relevant documentation in docs
Updated all code comments where relevant
Wrote tests
Updated CHANGELOG_PENDING.md

This is in a separate PR for ease of review.

codecov-io · 2018-08-07T02:27:31Z

Codecov Report

Merging #2164 into develop will increase coverage by 0.12%.
The diff coverage is 72.5%.

@@             Coverage Diff             @@
##           develop    #2164      +/-   ##
===========================================
+ Coverage    62.23%   62.35%   +0.12%     
===========================================
  Files          212      215       +3     
  Lines        17567    17632      +65     
===========================================
+ Hits         10932    10994      +62     
  Misses        5725     5725              
- Partials       910      913       +3

Impacted Files	Coverage Δ
crypto/multisig/wire.go	`100% <100%> (ø)`
crypto/multisig/compact_bit_array.go	`77.77% <100%> (+1.2%)`	⬆️
crypto/multisig/threshold_multisig.go	`58.97% <58.97%> (ø)`
crypto/multisig/multisignature.go	`77.77% <77.77%> (ø)`
rpc/grpc/client_server.go	`66.66% <0%> (-4.77%)`	⬇️
state/validation.go	`52.32% <0%> (-3.93%)`	⬇️
blockchain/pool.go	`65.73% <0%> (-0.7%)`	⬇️
abci/example/kvstore/persistent_kvstore.go	`64.04% <0%> (ø)`	⬆️
cmd/tendermint/commands/init.go	`0% <0%> (ø)`	⬆️
p2p/pex/file.go	`78.04% <0%> (ø)`	⬆️
... and 13 more

liamsi · 2018-08-08T12:41:47Z

crypto/multisig/threshold_multisig_test.go

 	pubkeysCpy[3] = pubkeys[4]
 	multisigKey2 := NewThresholdMultiSignaturePubKey(2, pubkeysCpy)
-	require.NotEqual(t, multisigKey, multisigKey2)
+	require.False(t, multisigKey.Equals(multisigKey2))


Interesting, I would also have expected this to call the underlying Equal instead

liamsi

LGTM

ebuchman · 2018-08-08T14:24:25Z

Looks like there's some commit chaos here - can we get the relevant commits rebased on develop?

ValarDragon · 2018-08-08T16:04:03Z

Absolutely! Let's merge the compact bit array pr first, that should simplify rebasing

melekes

Needs to be rebased against latest develop.

ebuchman

Awesome work @ValarDragon. Lots of minor comments/questions about comments, code structure, and some additional checks we could do.

We should definitely up the tests and use tables, and figure out how we want to address the recursion.

Haven't reviewed the bit array yet - will do that next.

Happy for this to be merged if we open an issue to address this review - but we should address everything before it makes it to a release.

ebuchman · 2018-08-10T15:28:21Z

crypto/multisig/multisignature.go

+// Sigs is a list of signatures, sorted by corresponding index.
+type Multisignature struct {
+	BitArray *CompactBitArray
+	Sigs     [][]byte


What do you think of introducing a type Signature []byte instead of using []byte directly everywhere?

If you think that improves clarity, then sure. I didn't really see it as a problem.

Leave for now. Maybe we'll open an issue for it later

ebuchman · 2018-08-10T15:29:57Z

crypto/multisig/multisignature.go

+	return -1
+}
+
+// AddSignature adds a signature to the multisig, at the corresponding index.


// If the signature already exists, replace it.

ebuchman · 2018-08-10T15:33:16Z

crypto/multisig/threshold_multisig.go

+
+var _ crypto.PubKey = &ThresholdMultiSignaturePubKey{}
+
+// NewThresholdMultiSignaturePubKey returns a new ThresholdMultiSignaturePubKey.


// Panics if len(pubkeys) < k

I saw your comment about Go not having these panics. I think that's bad on their part. We should be as clear as possible to users about when we panic.

ebuchman · 2018-08-10T15:34:17Z

crypto/multisig/threshold_multisig.go

+
+// NewThresholdMultiSignaturePubKey returns a new ThresholdMultiSignaturePubKey.
+func NewThresholdMultiSignaturePubKey(k int, pubkeys []crypto.PubKey) crypto.PubKey {
+	if len(pubkeys) < k {


lets also check that k > 0 since the construction is meaningless otherwise and the uint will make k > len(pubkeys ) :P

ebuchman · 2018-08-10T15:37:21Z

crypto/multisig/multisignature.go

+}
+
+// NewMultisig returns a new Multisignature of size n.
+func NewMultisig(n int) *Multisignature {


Should we consider not using a pointer here? The methods could return new Multisignature, and the object becomes immutable

The object shouldn't be immutable? You want to call AddSignature to it repeatedly.

Was suggesting AddSignature to return a new Multisignature, but yeh it's silly

ebuchman · 2018-08-10T16:00:28Z

crypto/multisig/threshold_multisig.go

+		return false
+	}
+	size := sig.BitArray.Size()
+	if len(sig.Sigs) < int(pk.K) || len(pk.Pubkeys) != size || sig.BitArray.NumOfTrueBitsBefore(size) < int(pk.K) {


Should we also do a consistency check that len(sig.Sigs) < size?

Maybe it would be better if we split this up and evaluate the concerns separately.

Like first we check the size of the bitarray against the number of sigs and the number of pubkeys.

Then we handle the K stuff.

Theres no point in checking len(sig.Sigs) < size. k <= size. If k was > size, the sig would be impossible to verify. (I guess we can ban that case in marshalling / unmarshalling the multisig)

but we allow len(sigs.Sigs) > k, so we should set an upper bound.

Oh woops, your totally right, great catch!

ebuchman · 2018-08-10T16:04:19Z

crypto/multisig/threshold_multisig_test.go

+	"github.com/tendermint/tendermint/crypto/secp256k1"
+)
+
+func TestThresholdMultisig(t *testing.T) {


I think this test is ripe for table-driven testing.

We should be testing multiple values of N, and make sure we get expected behaviour when N<=0 and when N=1.

We should be testing multiple values of K, including that we get expected behaviour in the edges, eg. when K<=0, K=1, K=N-1, K=N, K>N

Same with the other tests really ...

We should also test what happens with recursive multisig pubkeys. Or if we want to restrict it, then test it fails.

We should also test unmarshalling

Table driven sounds good. I do think we should enable recursive multisigs.

Not really sure why we would test unmarshalling. We assume that amino works, and all variables are public?

ebuchman · 2018-08-10T16:06:52Z

crypto/multisig/wire.go

+)
+
+// TODO: Figure out API for others to either add their own pubkey types, or
+// to make verify / marshal accept a cdc.


Huh. We don't really expose this as an API at all, which perhaps suggests that PubKey really could be a oneof

I'm confused. Don't we have to register the pubkey type in order to decode it? I'm not really sure what your suggesting. (Perhaps due to my unfamiliarity with oneof)

Yes I wasn't suggesting you do anything. But it goes back to the larger conversation of "do we really need pubkey to be an any-one-can-implement-it-without-permission interface" ie. the kind of thing Amino was built for, or would pure protobuf (using protobufs union type, called oneof) do just fine, since there isn't really a nice way to add new pubkey types right now without changing our crypto lib

Note this is unlike Msg in the SDK which really does want to be an interface.

Oh, I think pure protobuf is better here. We have to register it in all the codecs, so its not really like anyone can just implement it.

ebuchman · 2018-08-10T16:08:19Z

crypto/multisig/wire.go

+	cdc.RegisterConcrete(ThresholdMultiSignaturePubKey{},
+		ThresholdPubkeyAminoRoute, nil)
+	cdc.RegisterConcrete(ed25519.PubKeyEd25519{},
+		ed25519.Ed25519PubKeyAminoRoute, nil)


oh, should these just becomePubKeyAminoRoute since it's an anti-pattern to have the double prefix (pkg and var name)?

You're right, they should

I'll address this in a separate PR

Addressed in #2205

ebuchman · 2018-08-10T16:09:37Z

crypto/multisig/wire.go

+// TODO: Figure out API for others to either add their own pubkey types, or
+// to make verify / marshal accept a cdc.
+const (
+	ThresholdPubkeyAminoRoute = "tendermint/ThresholdMultisigPubkey"


We use eg. tendermint/PubKeyEd25519 so this should be tendermint/PubKeyMultisigThreshold

Good catch!

ebuchman · 2018-08-10T16:51:15Z

Some review of the compact bit array PR: #2140 (review)

ValarDragon · 2018-08-10T18:23:24Z

I think we should merge this. I can add more test cases and documentation for the recursive case in a separate PR. (I'll make those other tests table driven there as well. I made the main test table driven for what its aimed for, though I need to populate that table more as well)

The remaining things should be discussed in seperate issues or require seperate PR's.

ValarDragon · 2018-08-10T19:07:20Z

Follow up comment made in an open issue!

jaekwon · 2018-08-13T23:15:22Z

crypto/multisig/compact_bit_array.go

+// e.g. if bA = _XX_X_X, NumOfTrueBitsBefore(4) = 2, since
+// the value at index 4 of the bit array is the third
+// value that is true. (And it is 0-indexed)
+func (bA *CompactBitArray) NumOfTrueBitsBefore(index int) int {


minor point, I'd just call this NumTrueBitsBefore(index int). I think "of" is implied.

jaekwon · 2018-08-14T00:39:20Z

crypto/multisig/compact_bit_array.go

 	return true
 }

+// NumOfTrueBitsBefore returns the location of the given index, among the


"returns the location of the given index" is not the right wording since it doesn't return a location, but number of bits true.

jaekwon · 2018-08-14T00:39:56Z

crypto/multisig/compact_bit_array.go


+// NumOfTrueBitsBefore returns the location of the given index, among the
+// values in the bit array that are set to true.
+// e.g. if bA = _XX_X_X, NumOfTrueBitsBefore(4) = 2, since


"since ... value at index 4 .... is true"
"since" seems like a strange modifier and the following statement a bit orthogonal.

Maybe it make sense to let the user specify 0 to count the total number of true bits?
And then we can comment that, which makes it clear that you don't want to enter NumTrueBitsBefore(0) when you really mean NumTrueBitsBefore(1).

I feel like making edge cases like letting 0 counting the number of true bits makes it more confusing. I do definitely agree with your point about the comments here!

melekes · 2018-08-14T15:21:17Z

--> Running linter
crypto/multisig/compact_bit_array_test.go:173:44:warning: invalid operation: bA (variable of type *CompactBitArray) has no field or method NumOfTrueBitsBefore (gosimple)

# github.com/tendermint/tendermint/crypto/multisig
crypto/multisig/compact_bit_array_test.go:173:46: bA.NumOfTrueBitsBefore undefined (type *CompactBitArray has no field or method NumOfTrueBitsBefore)

ebuchman · 2018-08-14T21:51:03Z

Sorry I forgot to squash everything.

Follow up is in #2163 (comment)

ValarDragon added 3 commits August 2, 2018 23:18

crypto: Add compact bit array for intended usage in the multisig

96fdec0

This is in a separate PR for ease of review.

crypto: Add compact bit array for intended usage in the multisig

21448bc

This is in a separate PR for ease of review.

crypto: Threshold multisig implementation

e7dd76c

ValarDragon requested review from ebuchman, melekes, xla and zramsay as code owners August 7, 2018 02:19

Merge branch 'dev/compact_bitmap' into dev/multisig

6dbbdb9

ValarDragon changed the title ~~Dev/multisig~~ Threshold Multisignature implementation Aug 7, 2018

ValarDragon requested a review from liamsi August 7, 2018 02:26

(squash this) address PR comments + fix bug in equality check

67b6d51

ValarDragon force-pushed the dev/multisig branch from e532602 to 67b6d51 Compare August 7, 2018 15:44

(squash this) squashed bug with multiple signatures at same index.

4e7bf10

liamsi reviewed Aug 8, 2018

View reviewed changes

liamsi approved these changes Aug 8, 2018

View reviewed changes

melekes changed the base branch from dev/compact_bitmap to develop August 9, 2018 05:39

melekes approved these changes Aug 9, 2018

View reviewed changes

Merge remote-tracking branch 'origin/develop' into dev/multisig

aab26c3

ebuchman approved these changes Aug 10, 2018

View reviewed changes

ValarDragon added 2 commits August 10, 2018 13:14

(squash this) begin addressing PR comments

00db469

(squash this) fix amino route

4cf1dbd

ValarDragon mentioned this pull request Aug 10, 2018

crypto: Switch pubkeys to protobuf oneof #2204

Closed

(Squash this) switch to bare

8d28344

ValarDragon force-pushed the dev/multisig branch from 31a0567 to 8d28344 Compare August 10, 2018 18:59

ValarDragon mentioned this pull request Aug 10, 2018

Implement multisig ADR #2163

Closed

ValarDragon mentioned this pull request Aug 10, 2018

crypto: Remove unnecessary prefixes from amino route variable names #2205

Merged

1 task

jaekwon reviewed Aug 13, 2018

View reviewed changes

jaekwon reviewed Aug 14, 2018

View reviewed changes

(squash this) address Jae's comments on NumTrueBitsBefore

6beaf6e

(squash this) Fix build errors

2fe3449

ebuchman merged commit db53dc5 into develop Aug 14, 2018

ebuchman deleted the dev/multisig branch August 14, 2018 20:37


		var _ crypto.PubKey = &ThresholdMultiSignaturePubKey{}

		// NewThresholdMultiSignaturePubKey returns a new ThresholdMultiSignaturePubKey.

Conversation

ValarDragon commented Aug 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov-io commented Aug 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Choose a reason for hiding this comment

Uh oh!

liamsi left a comment

Choose a reason for hiding this comment

Uh oh!

ebuchman commented Aug 8, 2018

Uh oh!

ValarDragon commented Aug 8, 2018

Uh oh!

melekes left a comment

Choose a reason for hiding this comment

Uh oh!

ebuchman left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

ValarDragon commented Aug 7, 2018 •

edited

Loading

codecov-io commented Aug 7, 2018 •

edited

Loading

ValarDragon commented Aug 10, 2018 •

edited

Loading

melekes commented Aug 14, 2018 •

edited

Loading