Pedersen Verifiable Secret Shares (PVSS), Commitments and Spotting A Bad Dealer and a Cheating…

Pedersen Verifiable Secret Shares (PVSS), Commitments and Spotting A Bad Dealer and a Cheating Player

Okay. Let’s say you are in a card game, how do you know that the dealer is honest, and that the other players are also honest? Well, let’s say we have n players in the card game, and we want to make it fair. For this, we could agree that t players can come together and agree on the card that has been dealt. This would mean that there was a consensus of t people who would approve the card. This would define t as the threshold for approving the card.

For example, we could have Bob, Alice, Carol and Peggy playing the card game, and where Trent is the dealer. If we define that three of the four will agree to the card that is dealt, then we can cope with one cheating player. In this way, Bob, Alice and Carol can agree on a card, even if Peggy disagrees with the card dealt. This is known as Byzantine Fault Tolerance, and where we can cope with players turning bad.

To implement this we can use a Shamir Secret Sharing mechanism to allow at least t players to come together to reveal the card dealt. So first, I will explain the Shamir Sharing mechanism and for us to be able to cope with a player going bad, and then I will outline how the players can spot a corrupt dealer (using the Pedersen Verfiable Secret Share method).

Sharing the card: Shamir Secret Share

With secret sharing, we take a secret value and then share it with others. For example, we might have a share for Bob, Alice, Carol and Dave and then for three of them to come together to bring their shares together. For this, we define a threshold (t) and a number of shares (n). We reconstruct the shares we need at least t shares to come together to reveal the secret. If we have (t-1) shares it should be impossible to reconstruct the secret.

For an any 3-from-4, we can use a quadratic equation, such as f(x)=20x²−2x+10, and where the value of 10 is the secret. Bob then gets the value of f(x) when x=0 — and which is defined as f(1). Carol gets f(2), Dave gets f(3) and Alice gets f(4). The secret value is thus f(0). They then each know a y-coordinate point on the quadratic equation. When they want to bring the value back, we can curve fit the gathered points. Thus if we have f(1), f(2) and f(3) we can regenerate the quadratic equation and thus determine f(0). We, of course, need to remember the x co-ordinate values for each share, so we give each share an ID of 1, 2, 3, and so on. Here we have three sample shares from an any 2-from-3 share, and notice that we have the x-coordinate value so that when we reconstruct, we know the x-coordinate for the share:

== Secret shares == 2 from 3 ===
00000001a971463eae26ff1dc6dd19db77f209643fe72ee384101f6e2bd6e97674ef630c 000000022faa84e5c3a2756b3b3accdbabe548eb67ea81283296913ae9d0fdd45ca25a0d 00000003b5e2c28cd91eecb8b0967edcdfd8877290edd46ddf1b0407a7cb11334555510e =================

These days we often use elliptic curves to perform efficient operations. With this, we start with a secret (s) and then take the base point of the curve (G) and produce a secret of sG. Next, we convert sG into a number of polynomial factors for a given threshold t and with n shares. We will then take the share point and then split it into a number of polynomial values, and where the point that we cut the y-axis will recover the share. Initially, we will fit a polynomial to the secret with:

P(x)=p_0+p_1x+p_2x²+…

and where p_0, p_1 and so on, are coefficients of the required polynomial. Then we will create the shares for P(1), P(2), and so on. These are the points when x=1, x=2 and so on. These shares can then be distributed to the entities that will store the shares. When required, we gather back at least t shares to recreate the secret (sG). For example, we may use P(0), P(1) … P(t−1) and use a curve fitting method to find P(0) and which is the point of the polynomial where x=0. The value we recover for P(0) is then covered back into an elliptic curve point to give sG:

Now we can use the Kryptology library developed by Coinbase to implement Shamir Secret Shares. In this case, we will define t for the threshold and n for the number of shares. In this case, we will use Ed25519 for our curve, and hash a message to this curve (mysecret) [here]:

package mainimport (
	crand "crypto/rand"
	"fmt"
	"os"
	"strconv"	"github.com/coinbase/kryptology/pkg/core/curves"
	"github.com/coinbase/kryptology/pkg/sharing"
)func main() {	msg := "Hello"
	var t uint32 = uint32(2)
	var n uint32 = uint32(3)
	argCount := len(os.Args[1:])	if argCount > 0 {
		msg = os.Args[1]
	}
	if argCount > 1 {
		val, err := strconv.Atoi(os.Args[2])
		if err == nil {
			t = uint32(val)
		}
	}
	if argCount > 2 {
		val, err := strconv.Atoi(os.Args[3])
		if err == nil {
			n = uint32(val)
		}
	}	curve := curves.ED25519()
	scheme, _ := sharing.NewShamir(t, n, curve)	shares, _ := scheme.Split(curve.NewScalar().Hash([]byte(msg)), crand.Reader)	fmt.Printf("== Secret shares == %d from %d ===\n", t, n)
	for _, s := range shares {
		fmt.Printf("%x ", s.Bytes())
	}
	fmt.Printf("\n=================\n")	mysecret := curve.NewScalar().Hash([]byte(msg))	fmt.Printf("Message: %s\n", msg)
	fmt.Printf("\nOriginal Hash: %x\n\n", mysecret.Bytes())	secret, err := scheme.Combine(shares...)
	if err == nil {
		fmt.Printf("Recorded Hash with all the shares: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with all shares\n")
	}	secret, err = scheme.Combine(shares[0])
	if err == nil {
		fmt.Printf("Recorded Hash with one share: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with one share\n")
	}	secret, err = scheme.Combine(shares[0], shares[1])
	if err == nil {
		fmt.Printf("Recorded Hash with two shares: %x\n", secret.Bytes())
	} else {
		fmt.Printf("Cannot recover with two shares\n")
	}}

A sample run [here]:

== Secret shares == 2 from 3 ===
00000001cdd7b102063bd58b6d785823a686aab5fef297d0820d36d9ef3e2c51bd5ff604
00000002d2fc951ff25611d8d816dac4604e76f544970df5cac8c3d2234a4de4e71bc60a
00000003ea4d84dfc30f3bcc6d1864c33c1c63208b3b8319138451cc57556e7712d89500 
=================
Message: helloOriginal Hash: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260fRecorded Hash with all the shares: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f
Cannot recover with one share
Recorded Hash with two shares: b586c3423482ab97d876ce24cab8bd8ab84e22ac3a52a8dfbb330bbe92a3260f

Here is a presentation of the method:

Okay. Hopefully, you understand the basics of Shamir Secret Shares, so now we will define a method that allows us to detect a corrupt dealer.

Spotting a corrupt dealer: Pedersen Verifiable Secret Share

With the Pedersen Verifiable Secret Sharing Scheme (PVSS), we create a blinding factor (b), and then split this value into coefficients:

g(x)=b+b_1 x+b_2 x²…

The dealer (who is distributing the shares), initially privately sends out each share with:

S_1=(p(1),g(1)) — for Bob

S2=(p(2),g(2)) — for Alice

and where the p() is the secret share and g() will be used to verify the share. The dealer also creates a number of commitments for elliptic curve point additions:

C1=p(1)+g(1)

C2=p(2)+g(2)

and so on. These are then passed to the entities involved. It will not be possible for any other player to reveal the secret share from the commitments, as the blinding factor has been applied.

Each player receives a share then checks the commitment against the share elements. If they do not match, the player will tell the other players that they have a complaint against the dealer. They will then reveal the commitment and their share. The dealer will also reveal its commitment. Next, the players will then check who is right against the commitments. If the commitment does not match the share, they will remove the dealer from the game, if not, they will remove the accusing entity from the game.

We can use the Kryptology library developed by Coinbase to implement PVSS. In this case, we will define t for the threshold and n for the number of shares [here]:

package main

import (
	crand "crypto/rand"
	"fmt"
	"os"
	"strconv"

	"github.com/coinbase/kryptology/pkg/core/curves"
	"github.com/coinbase/kryptology/pkg/sharing"
)

func main() {

	msg := "Hello"
	var t uint32 = uint32(3)
	var n uint32 = uint32(4)
	argCount := len(os.Args[1:])

	if argCount > 0 {
		msg = os.Args[1]
	}
	if argCount > 1 {
		val, err := strconv.Atoi(os.Args[2])
		if err == nil {
			t = uint32(val)
		}
	}
	if argCount > 2 {
		val, err := strconv.Atoi(os.Args[3])
		if err == nil {
			n = uint32(val)
		}
	}

	curve := curves.ED25519()
	secret := curve.NewScalar().Hash([]byte(msg))

	pt := curve.ScalarBaseMult(secret)

	pedersen, _ := sharing.NewPedersen(t, n, pt)

	shares, _ := pedersen.Split(secret, crand.Reader)

	fmt.Printf("== Secret shares == %d from %d ===\n", t, n)
	for _, s := range shares.SecretShares {
		fmt.Printf("Share: %x\n", s.Bytes())
	}
	fmt.Printf("=================\n")

	fmt.Printf("== Blinding shares == %d from %d ===\n", t, n)
	for _, s := range shares.BlindingShares {
		fmt.Printf("Blinding shares: %x\n", s.Bytes())
	}
	fmt.Printf("=================\n")

	//	recovered, _ := pedersen.Combine(shares.SecretShares...)
	sG, _ := pedersen.Combine(shares.SecretShares...)
	bH, _ := pedersen.Combine(shares.BlindingShares...)

	fmt.Printf("Secret: %x\n", secret.Bytes())
	fmt.Printf("Recovered: %x\n", sG.Bytes())

	fmt.Printf("\nBlinding: %x\n", shares.Blinding.Bytes())
	fmt.Printf("Blinding Recovered: %x\n", bH.Bytes())

	err := shares.PedersenVerifier.Verify(shares.SecretShares[0], shares.BlindingShares[0])
	if err == nil {
		fmt.Printf("\nShare 1 verified\n")
	}
	err = shares.PedersenVerifier.Verify(shares.SecretShares[1], shares.BlindingShares[1])
	if err == nil {
		fmt.Printf("\nShare 2 verified\n")
	}

}

A sample run [here]:

== Secret shares == 3 from 4 ===
Share: 0000000150eb0b9e5d50954c83bcec58a4a6b491b75849655ee955dcdc4c4c6a7767e092
Share: 000000024524c932a2cbbf2f800ef261e69decb27a3bc7d7eabda4f6706f28fe14ffed79
Share: 000000032baccdd2026ace45f92bd2de7763bffdb6700b4cf42bc90e83eaea3d34d4979d
Share: 000000040483197c7c2dc28fef138dce56f82e736bf513c47b33c22516bf9027d6e5defe
=================
== Secret shares == 3 from 4 ===
Blinding shares: 0000000108eeaf5d770301e932bb209c8d7d8c3a0d46cc86fba56ec5ccbfdf8c8a76350e
Blinding shares: 000000025a631f20f73bb0aa2c25dd42e55c758c7ceedc5b21f50df8eed5b8dcea3f8010
Blinding shares: 0000000317314991e644e98f89bb355bbf8683e324bcdc271d2b5df583c0be0983a5d528
Blinding shares: 0000000427347d569759a729b1eed8f72f3f6748ac2c13f0ed4516b98b80ef1056a93458
=================
Secret: 4eff951531f9509d0435c0c2b17e179b6dc58ff550aedbc1c78254825c0c70e8
Recovered: 4eff951531f9509d0435c0c2b17e179b6dc58ff550aedbc1c78254825c0c70e8

Blinding: 0aaf48edb8d5d7dd03eeaf78cb2d77f67d3ff4b0aa39385a1d7f32166449f424
Blinding Recovered: 0aaf48edb8d5d7dd03eeaf78cb2d77f67d3ff4b0aa39385a1d7f32166449f424

Share 1 verified
Share 2 verified

The code is here:

https://asecuritysite.com/kryptology/sss02

Conclusions

And there you go. That’s how to spot a bad dealer! In a trusted network, the distribution of secret shares allow us to securely distribute a shared value, and then for entities to come together to reveal it. We can then cope with a failure of a number of nodes, or where these nodes go bad. This allows us to have a consensus on the correct state of our data infrastructure. But what happens when the leader goes bad — the one distributing the secrets? Well, we can use commitments for that, and let the network nodes decide if they don’t want the controller to lead any more, and elect a new one.

In 2020, I had the honour of chatting to Torben: