Byzantine fault tolerance with verifiable secret sharing at constant overhead
Techniques for implementing Byzantine fault tolerance with verifiable secret sharing at constant overhead are provided. In one set of embodiments, a client can determine a secret value s to be shared with N replicas in a distributed system, s being input data for a service operation provided by the N replicas. The client can further encode s into an f-degree polynomial P(x) where f corresponds to a maximum number of faulty replicas in the distributed system, evaluate P(x) at i for i=1 to N resulting in N evaluations P(i), generate at least one f-degree recovery polynomial R(x) based on a distributed pseudo-random function (DPRF) f α (x), and evaluate R(x) at i for i=1 to N resulting in at least N evaluations R(i). The client can then invoke the service operation, the invoking comprising transmitting a message including P(i) and R(i) to each respective replica i.
1. A method comprising:
receiving, by each replica i in N replicas of a distributed system, a message from a client, the message invoking a service operation provided by the N replicas and including:
an evaluation P(i) of a polynomial P(x) of degree f at value i, wherein f corresponds to a maximum number of faulty replicas in the N replicas, and wherein P(x) encodes a secret value s shared by the client with the N replicas; and
an evaluation R(i) of a recovery polynomial R(x) at value i, wherein R(x) is based on a distributed pseudo-random function (DPRF) f α (x);
sequencing, by replica i, execution of the invoked service operation based at least in part on the received message, wherein the sequencing causes each non-faulty replica in the N replicas to assign an identical sequence number to the invoked service operation;
executing, by said each non-faulty replica, the invoked service operation in accordance with the identical sequence number; and
updating, by said each non-faulty replica, a local state of said each non-faulty replica to reflect a result of the executing of the invoked service operation.
2. The method of claim 1 wherein s corresponds to input data for the service operation.
3. The method of claim 1 wherein a different recovery polynomial is used to generate R(i) for every group off replicas in the N replicas.
4. The method of claim 1 further comprising, prior to the receiving the message:
receiving by replica i a seed value share wherein seed value share α i is generated by performing a (f+1, N) secret sharing of a seed value α for the DPRF f α (x).
5. The method of claim 4 wherein replica i employs a Byzantine fault tolerant (BFT) protocol for carrying out the sequencing.
6. The method of claim 1 further comprising:
transmitting, by replica i, a share recovery request to every other replica j,
wherein upon receiving the share recovery request, replica j is configured to:
compute f α j (i) using seed value share α j ;
compute R(j)+P(j); and
transmit a reply message comprising f α j (i) and R(j)+P(j) to said each replica i.
7. The method of claim 6 further comprising, upon receiving the reply messages from the other replicas:
interpolating R(i)+PQ) and f α (i) based on the reply messages;
subtracting f α (i) from R(i)+P(i) to recover P(i).
8. A non-transitory computer readable storage medium having stored thereon program code executable by each replica i in N replicas of a distributed system, the method comprising:
receiving a message from a client, the message invoking a service operation provided by the N replicas and including:
an evaluation P(i) of a polynomial P(x) of degree fat value i, wherein f corresponds to a maximum number of faulty replicas in the N replicas, and wherein P(x) encodes a secret value s shared by the client with the N replicas; and
an evaluation R(i) of a recovery polynomial R(x) at values i, wherein R(x) is based on a distributed pseudo-random function (DPRF) f α (x);
sequencing execution of the invoked service operation based at least in part on the received message, wherein the sequencing causes each non-faulty replica in the N replicas to assign an identical sequence number to the invoked service operation;
executing, by said each non-faulty replica, the invoked service operation in accordance with the identical sequence number; and
updating, by said each non-faulty replica, a local state of said each non-faulty replica to reflect a result of the executing of the invoked service operation.
9. The non-transitory computer readable storage medium of claim 8 wherein s corresponds to input data for the service operation.
10. The non-transitory computer readable storage medium of claim 8 wherein a different recovery polynomial is used to generate R(i) for every group off replicas in the N replicas.
11. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises, prior to the receiving the message:
receiving a seed value share α i that is generated by performing a (f+1, N) secret sharing of a seed value α for the DPRF f α (x).
12. The non-transitory computer readable storage medium of claim 11 wherein a Byzantine fault tolerant (BFT) protocol is used for carrying out the sequencing.
13. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises:
transmitting a share recovery request to every other replica j,
wherein upon receiving the share recovery request, replica j is configured to:
compute f α j (i) using seed value share α j ;
compute R(j)+P(j); and
transmit a reply message comprising f α j (i) and R(j)+P(j) to replica i.
14. The non-transitory computer readable storage medium of claim 13 wherein the method further comprises, upon receiving the reply messages from the other replicas:
interpolating R(i)+PQ) and f α (i) based on the reply messages;
subtracting f α (i) from R(i)+P(i) to recover P(i).
15. A replica i in a distributed system comprising N replicas, replica i comprising:
a processor;
a local state; and
a non-transitory computer readable medium having stored thereon program code that, when executed, causes the processor to:
receive a message from a client, the message invoking a service operation provided by the N replicas and including:
an evaluation P(i) of a polynomial P(x) of degree f at value i, wherein f corresponds to a maximum number of faulty replicas in the N replicas, and wherein P(x) encodes a secret value s shared by the client with the N replicas; and
an evaluation R(i) of a recovery polynomial R(x) at value i, wherein R(x) is based on a distributed pseudo-random function (DPRF) f α (x);
sequence execution of the invoked service operation based at least in part on the received message, wherein the sequencing causes each non-faulty replica in the N replicas to assign an identical sequence number to the invoked service operation;
execute the invoked service operation in accordance with the identical sequence number; and
update the local state to reflect a result of the executing of the invoked service operation.
16. The replica i of claim 15 wherein s corresponds to input data for the service operation.
17. The replica i of claim 15 wherein a different recovery polynomial is used to generate R(i) for every group off replicas in the N replicas.
18. The replica i of claim 15 wherein the program code further causes the processor to, prior to the receiving the message:
receive a seed value share α i that is generated by performing a (f+1, N) secret sharing of a seed value α for the DPRF f α (x).
19. The replica i of claim 18 wherein a Byzantine fault tolerant (BFT) protocol is used for carrying out the sequencing.
20. The replica i of claim 15 wherein the program code further causes the processor to:
transmit a share recovery request to every other replica j,
wherein upon receiving the share recovery request, replica j is configured to:
compute f α j (i) using seed value share α j ;
compute R(j)+P(j); and
transmit a reply message comprising f α j (i) and R(j)+P(j) to replica i.
21. The replica i of claim 20 wherein the program code further causes the processor to, upon receiving the reply messages from the other replicas:
interpolate R(i)+P(i) and f α (i) based on the reply messages;
subtract f α (i) from R(i)+P(i) to recover P(i).