What Happens When The Dealer Leaves The Game: Can We Continue? Meet AVSS
What Happens When The Dealer Leaves The Game: Can We Continue? Meet AVSS
Let’s say we have a deal in a card game, and where there are a number of participants (n). For every card dealt, we could split the value of the card into a number of shares, and where a given number of these shares can be brought together to reveal the value of the card. This support Byzantine fault tolerance, and where a number of the parties can fail to reveal their shares. This might be because they do not respond in time, or are cheating players. But what happens when the dealer leave the game? Can we still reconstruct the card? Well, we can with an Asynchronous Verifiable Secret Sharing (AVSS) method.
Outline
In 2002, Cachin et. al defined the Asynchronous Verifiable Secret Sharing (AVSS) method and which uses bi-variate polynomials [1]. In most secret sharing schemes we have a polynomial with one variable, such as:
With Shamir’s Secret Shares we store the secret share at a_0, and where we distribute points on the polynomial and then rebuild them back into a polynomial, and which should then reveal the secret. With AVSS we use bi-variate polynomials and which has two variables (x and y). Bi-variate polynomials are in the form of:
In this case, the secret is kept at a_00. With the Shamir method, we define a threshold (t) from a number of shares (n), and then aim to recover a polynomial f(x,y) and where the secret share is at f(0,0).
Within secret sharing models we can have three main categories:
- Synchronous model. This is implemented in systems that use a global clock to synchonise messages, and where there will be well-defined delays in processing.
- Asynchronous model. This is where there is no synchonisation of messages, and where delays can vary depending on workloads. One of the key issues is that it is difficult to differentiate a slow response from a participating party from a corrupt sender who refuses to send back messages. This leads to more complexity in the methods used by asynchonous methods.
- Hybrid. This is a mixture of synchonous and asynchronous models, and where there may be a few rounds of synchonization followed by asynchonous operations.
In a typical secret sharing method, the dealer defines a polynomial of:
and where a_0 defines the secret. The dealer then sends out points on the polynomial, such as x=1 and where we have the y value of p(x=1). We can also create a commitment from the dealer so that each participant can check that their share is valid. Within an asynchronous environment, the dealer may not wait around before all the shares have been acknowledged.
AVSS supports a participating party to reconstruct its share using a distributed protocol that does not require the dealer to be present. With an asynchronous setting, we could have f participants failing. This requires f+1 participants to rebuild the share.
The AVSS method
In AVSS, we start with a bivariate polynomial (m×n):
For n=3 and m=3, we have:
In a secret sharing system, we aim to find the solution at p(0,0). We can represent the factors in a matrix form of:
In AVSS, we place the secret at a0,0 and random values in the other positions:
We then generate a random matrix:
We then take a base point on the secp256k1 curve (G) and then scale with f(m,n), and then add this to f′(m,n) to another base point (H). This then gives a number of secp256k1 points for the commitments from the dealer:
Each of the nodes i then get:
- C
- ai(y)=f(i,y)
- a′i(y)=f′(i,y)
- bi(x)=f(x,i)
- b′i(x)=f′(x,i)
Thus Node 1 (x=1) gets the polynomial factors of:
Every node i will receive C, the share polynomial of ai(y) and a′i(y), and the sub-share polynomials are bi(y) and b′i(y). Each node can then check their shares against the commitment from the dealer.
The sequence is then:
1. The Dealer creates a bivariate polynomial and puts the secret at f(0,0) and with random values at all the other places in the matrix:
f := GenerateRandomBivariatePolynomial(secret, threshold)
2. Create random bivariate polynomial:
fprime := GenerateRandomBivariatePolynomial(*RandomBigInt(), threshold)
3. Create commitment matrix, and which is the point assigns the f
as scalar values to the G base point, and fprime with the H based point, and then adds these together, to get the form:
C := GetCommitmentMatrix(f, fprime)
These are points on the secp256k1 curve. When a node receives a share, it can then check that the share is valid. In the following, we will take the first share for its validity:
sigma := polyEval(EvaluateBivarPolyAtX(f, *big.NewInt(int64(threshold))), 0)
sigmaprime := polyEval(EvaluateBivarPolyAtX(fprime, *big.NewInt(int64(threshold))), 0)
fmt.Printf("\n1st share: Sigma=%s, Sigma_p=%s", sigma, sigmaprime)
rtn := AVSSVerifyShare(C, *big.NewInt(int64(threshold)), *sigma, *sigmaprime)
fmt.Printf("\nVerified share: %v ", rtn)
Coding
The following code is based on the Tor.us source. In this case, we will define t for the threshold and n for the number of shares [here]:
// Based on https://github.com/torusresearch/torus-node
package main
import (
"crypto/rand"
"fmt"
"main/secp256k1"
"math/big"
"os"
"strconv"
)
func RandomBigInt() *big.Int {
randomInt, _ := rand.Int(rand.Reader, secp256k1.GeneratorOrder)
return randomInt
}
func AVSSVerifyShare(C [][]secp256k1.Point, m big.Int, sigma big.Int, sigmaprime big.Int) bool {
sG := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarBaseMult(sigma.Bytes()))
rH := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarMult(&secp256k1.H.X, &secp256k1.H.Y, sigmaprime.Bytes()))
sGrH := secp256k1.BigIntToPoint(secp256k1.Curve.Add(&sG.X, &sG.Y, &rH.X, &rH.Y))
pt := secp256k1.Point{X: *big.NewInt(int64(0)), Y: *big.NewInt(int64(0))}
for j := range C {
Cj0 := C[j][0]
mj := new(big.Int).Exp(&m, big.NewInt(int64(j)), secp256k1.GeneratorOrder)
Cj0mj := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarMult(&Cj0.X, &Cj0.Y, mj.Bytes()))
pt = secp256k1.BigIntToPoint(secp256k1.Curve.Add(&pt.X, &pt.Y, &Cj0mj.X, &Cj0mj.Y))
} if sGrH.X.Cmp(&pt.X) != 0 || sGrH.Y.Cmp(&pt.Y) != 0 {
return false
}return true
}
func GenerateRandomBivariatePolynomial(secret big.Int, threshold int) [][]big.Int {
bivarPolyCoeffs := make([][]big.Int, threshold)
for j := range bivarPolyCoeffs {
bivarPolyCoeffs[j] = make([]big.Int, threshold)
for l := range bivarPolyCoeffs[j] {
if j == 0 && l == 0 {
bivarPolyCoeffs[j][l] = secret
} else {
bivarPolyCoeffs[j][l] = *RandomBigInt()
}
}
}return bivarPolyCoeffs
}
func GetCommitmentMatrix(f [][]big.Int, fprime [][]big.Int) [][]secp256k1.Point {
threshold := len(f)
bivarPolyCommits := make([][]secp256k1.Point, threshold)
for j := range bivarPolyCommits {
bivarPolyCommits[j] = make([]secp256k1.Point, threshold)
for l := range bivarPolyCommits[j] {
gfjl := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarBaseMult(f[j][l].Bytes()))
hfprimejl := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarMult(
&secp256k1.H.X,
&secp256k1.H.Y,
fprime[j][l].Bytes(),
))
bivarPolyCommits[j][l] = secp256k1.BigIntToPoint(secp256k1.Curve.Add(&gfjl.X, &gfjl.Y, &hfprimejl.X, &hfprimejl.Y))
}
}
return bivarPolyCommits
}type PrimaryPolynomial struct {
Coeff []big.Int
Threshold int
}func PolyEval(polynomial PrimaryPolynomial, x big.Int) *big.Int {
return polyEval(polynomial, int(x.Int64()))
}func polyEval(polynomial PrimaryPolynomial, x int) *big.Int { // get private share
xi := big.NewInt(int64(x))
sum := new(big.Int)sum.Add(sum, &polynomial.Coeff[0])
for i := 1; i < polynomial.Threshold; i++ {
tmp := new(big.Int).Mul(xi, &polynomial.Coeff[i])
sum.Add(sum, tmp)
sum.Mod(sum, secp256k1.GeneratorOrder)
xi.Mul(xi, big.NewInt(int64(x)))
xi.Mod(xi, secp256k1.GeneratorOrder)
}
return sum
}
func EvaluateBivarPolyAtX(bivarPoly [][]big.Int, index big.Int) PrimaryPolynomial {
fiY := PrimaryPolynomial{
Coeff: make([]big.Int, len(bivarPoly)),
Threshold: len(bivarPoly),
}
for l := range bivarPoly[0] { // loop through horizontally first
for j := range bivarPoly { // loop through vertically
fiY.Coeff[l] = *new(big.Int).Add(
&fiY.Coeff[l],
new(big.Int).Mul(
&bivarPoly[j][l],
new(big.Int).Exp(&index, big.NewInt(int64(j)), secp256k1.GeneratorOrder),
),
)
}
}
return fiY
}
func EvaluateBivarPolyAtY(bivarPoly [][]big.Int, index big.Int) PrimaryPolynomial {
fiX := PrimaryPolynomial{
Coeff: make([]big.Int, len(bivarPoly)),
Threshold: len(bivarPoly),
}
for j := range bivarPoly { // loop through vertically first
for l := range bivarPoly[j] { // loop through horizontally
fiX.Coeff[j] = *new(big.Int).Add(
&fiX.Coeff[j],
new(big.Int).Mul(
&bivarPoly[j][l],
new(big.Int).Exp(&index, big.NewInt(int64(l)), secp256k1.GeneratorOrder),
),
)
}
}
return fiX
}func showMatrix(msg string, m [][]big.Int, size int) {
fmt.Printf("%s\n", msg)
for i := 0; i < size; i++ {
fmt.Printf("Row: ")
for j := 0; j < size; j++ {
fmt.Printf("%s ", m[i][j].String())
}
fmt.Printf("\n")
}
fmt.Printf("\n")
}
func showPoints(msg string, m [][]secp256k1.Point, size int) {
fmt.Printf("%s\n", msg)
for i := 0; i < size; i++ {
fmt.Printf("Row: ")
for j := 0; j < size; j++ {
fmt.Printf("%s ", m[i][j].X.String())
}
fmt.Printf("\n")
}
fmt.Printf("\n")
}
func main() {threshold := 3
s := 5
nodes := 5
// secret := *RandomBigInt()
argCount := len(os.Args[1:])
if argCount > 0 {
s, _ = strconv.Atoi(os.Args[1])
}
if argCount > 1 {
threshold, _ = strconv.Atoi(os.Args[2])}
if argCount > 2 {
nodes, _ = strconv.Atoi(os.Args[3])
}
secret := *big.NewInt(int64(s))
fmt.Printf("Secret=%d, threshold=%d, nodes=%d\n", s, threshold, nodes)f := GenerateRandomBivariatePolynomial(secret, threshold)
showMatrix("=== Show f (share at f(0,0))===", f, threshold)
fprime := GenerateRandomBivariatePolynomial(*RandomBigInt(), threshold)
showMatrix("=== Show f' ===", fprime, threshold)
C := GetCommitmentMatrix(f, fprime)
showPoints("=== Show Commitments (C - X points) ===", C, threshold)
sigma := polyEval(EvaluateBivarPolyAtX(f, *big.NewInt(int64(threshold))), 0)
sigmaprime := polyEval(EvaluateBivarPolyAtX(fprime, *big.NewInt(int64(threshold))), 0)
fmt.Printf("\n1st share: Sigma=%s, Sigma_p=%s", sigma, sigmaprime)
rtn := AVSSVerifyShare(C, *big.NewInt(int64(threshold)), *sigma, *sigmaprime)
fmt.Printf("\nVerified share: %v ", rtn)
/*
for node := 0; node < nodes; node++ {
i := *big.NewInt(int64(node + 1))
AIY := EvaluateBivarPolyAtX(f, i)
AIprimeY := EvaluateBivarPolyAtX(fprime, i)
BIX := EvaluateBivarPolyAtY(f, i)
BIprimeX := EvaluateBivarPolyAtY(fprime, i)
fmt.Printf("AIY=%v, AIprimeY=%v, BIX=%v, BIPrimeX=%v\n", AIY.Coeff, AIprimeY.Coeff, BIX.Coeff, BIprimeX.Coeff)
} */
}
A sample run [here]:
Secret=5, threshold=3, nodes=5
=== Show f (share at f(0,0))===
Row: 5 9743195669945784265736128598508718513383431809992852931467201572222501709532 11921601245529184890572677981314550793638440277120977934507285858736284872764
Row: 38914775169750618295866116389646254021539712841774945361261041297120280450770 39728712398652269566024872460140072549594041362028713476440569412633907719597 93804328507791152440549289202239599104421824368912194876844146484734559224879
Row: 29699601562624258681390881187189276130152510632542564550139048371246796426949 20177829835342526168771993908034295528249900168488246059089443608353861373117 50725914710115279957671906851075719555745896639024880177910113896553695516565
=== Show f' ===
Row: 115470196996176989345349889981956268662981937404082398634901967695935968192584 33044579844575268229918544233776696118670553243354949460102752276645043035280 94715233694196754547344213678075119784007634903399571068809848072191720921783
Row: 4340250202862599175210727375498478088765750740690216946430308017593134758098 36851108627021186689738145561635749516393072041227168049762415989053802072740 85484825408312771819133941960259191534837442943831567555553302176157039053809
Row: 92533102775313911545179309541127851019948561944739879791724032538117151496081 65933151131078972969485082821058756347303210836121412732507767307017160267569 86168717839084739660292482381227107627026797065820199045141906676115087565692
=== Show Commitments (C) ===
Row: 115470196996176989345349889981956268662981937404082398634901967695935968192584 33044579844575268229918544233776696118670553243354949460102752276645043035280 94715233694196754547344213678075119784007634903399571068809848072191720921783
Row: 4340250202862599175210727375498478088765750740690216946430308017593134758098 36851108627021186689738145561635749516393072041227168049762415989053802072740 85484825408312771819133941960259191534837442943831567555553302176157039053809
Row: 92533102775313911545179309541127851019948561944739879791724032538117151496081 65933151131078972969485082821058756347303210836121412732507767307017160267569 86168717839084739660292482381227107627026797065820199045141906676115087565692
Sigma=36664471860921596749403324827578523677479041380983203887219069808027524711845, Sigma_p=34952158684060427389027977909099099286115732896212732538867879459624443976911
Verified share: true
Asecuritysite is provided free and without adverts. If you want to support its development and get access to this blog, subscribe here: