byzq

package module
v0.0.0-...-2511a1a Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 22, 2017 License: MIT Imports: 30 Imported by: 0

README

byzq - Byzantine Quorum Protocol

Authenticated-Data Byzantine Quorum.
  • Ref. Algo. 4.15 in RSDP.
  • Requires authenticated channels
  • RequestID field of messages not needed since gRPC handles request matching.

Running localhost example

Start four servers
cd cmd/byzserver
./startbyzq4.sh
Start a writer client (should be started first so that server has data for the reader client)
cd cmd/byzclient
go build
./byzclient -writer
Start a reader client
cd cmd/byzclient
go build
./byzclient

Quorum function benchmarks

make bench

Documentation

Overview

Package byzq is a generated protocol buffer package.

It is generated from these files: 

byzq.proto

It has these top-level messages: 

Key
Content
Value
WriteResponse

Index

Constants

View Source 
const LevelNotSet = -1

LevelNotSet is the zero value level used to indicate that no level (and thereby no reply) has been set for a correctable quorum call.

Variables

View Source 
var (
	ErrInvalidLengthByzq = fmt.Errorf("proto: negative length found during unmarshaling")
	ErrIntOverflowByzq   = fmt.Errorf("proto: integer overflow")
)
View Source 
var Error = func(n1, n2 *Node) bool {
	if n1.lastErr != nil && n2.lastErr == nil {
		return false
	}
	return true
}

Error sorts nodes by their LastErr() status in increasing order. A node with LastErr() != nil is larger than a node with LastErr() == nil.

View Source 
var ID = func(n1, n2 *Node) bool {
	return n1.id < n2.id
}

ID sorts nodes by their identifier in increasing order.

View Source 
var Latency = func(n1, n2 *Node) bool {
	if n1.latency < 0 {
		return false
	}
	return n1.latency < n2.latency

}

Latency sorts nodes by latency in increasing order. Latencies less then zero (sentinel value) are considered greater than any positive latency.

Functions

func Equal 

func Equal(a, b *Configuration) bool

Equal returns a boolean reporting whether a and b represents the same configuration.

func GenerateKeyfile 

func GenerateKeyfile(keyFile string) error

GenerateKeyfile generates a private key and writes it to the given keyFile. Note that if the file exists it will be overwritten.

func ManagerCreationError 

func ManagerCreationError(err error) error

ManagerCreationError returns an error reporting that a Manager could not be created due to err.

func ParseKey 

func ParseKey(pemKey string) (*ecdsa.PrivateKey, error)

ParseKey takes a PEM formatted string and returns a private key.

func ReadKeyfile 

func ReadKeyfile(keyFile string) (*ecdsa.PrivateKey, error)

ReadKeyfile reads the provided keyFile and returns the private key stored in the file.

func RegisterStorageServer 

func RegisterStorageServer(s *grpc.Server, srv StorageServer)

Types

type AuthDataQ 

type AuthDataQ struct {
	// contains filtered or unexported fields
}

AuthDataQ is the quorum specification for the Authenticated-Data Byzantine Quorum algorithm described in RSDP, Algorithm 4.15, page 181.

func NewAuthDataQ 

func NewAuthDataQ(n int, priv *ecdsa.PrivateKey, pub *ecdsa.PublicKey) (*AuthDataQ, error)

NewAuthDataQ returns a quorum specification or nil and an error if the quorum requirements are not satisfied. Pre-condition: n>3f and f>0 Post-condition:

func (*AuthDataQ) ConcurrentVerifyIndexChanReadQF 

func (aq *AuthDataQ) ConcurrentVerifyIndexChanReadQF(replies []*Value) (*Content, bool)

ConcurrentVerifyIndexChanReadQF returns nil and false until the supplied replies constitute a Byzantine quorum, at which point the method returns the single highest value and true.

func (*AuthDataQ) ConcurrentVerifyWGReadQF 

func (aq *AuthDataQ) ConcurrentVerifyWGReadQF(replies []*Value) (*Content, bool)

ConcurrentVerifyWGReadQF returns nil and false until the supplied replies constitute a Byzantine quorum, at which point the method returns the single highest value and true.

func (*AuthDataQ) ReadQF 

func (aq *AuthDataQ) ReadQF(replies []*Value) (*Content, bool)

ReadQF returns nil and false until the supplied replies constitute a Byzantine quorum, at which point the method returns the single highest value and true.

func (*AuthDataQ) SequentialVerifyReadQF 

func (aq *AuthDataQ) SequentialVerifyReadQF(replies []*Value) (*Content, bool)

SequentialVerifyReadQF returns nil and false until the supplied replies constitute a Byzantine quorum, at which point the method returns the single highest value and true.

func (*AuthDataQ) Sign 

func (aq *AuthDataQ) Sign(content *Content) (*Value, error)

Sign signs the provided content and returns a value to be passed into Write. (This function must currently be exported since our writer client code is not in the byzq package.)

func (*AuthDataQ) VerfiyLastReplyFirstReadQF 

func (aq *AuthDataQ) VerfiyLastReplyFirstReadQF(replies []*Value) (*Content, bool)

VerfiyLastReplyFirstReadQF returns nil and false until the supplied replies constitute a Byzantine quorum, at which point the method returns the single highest value and true.

func (*AuthDataQ) WriteQF 

func (aq *AuthDataQ) WriteQF(req *Value, replies []*WriteResponse) (reply *WriteResponse, quorum bool)

WriteQF returns nil and false until it is possible to check for a quorum. If enough replies with the same timestamp is found, we return true.

type ConfigNotFoundError 

type ConfigNotFoundError uint32

A ConfigNotFoundError reports that a specified configuration could not be found.

func (ConfigNotFoundError) Error 

func (e ConfigNotFoundError) Error() string

type Configuration 

type Configuration struct {
	// contains filtered or unexported fields
}

A Configuration represents a static set of nodes on which quorum remote procedure calls may be invoked.

func (*Configuration) ID 

func (c *Configuration) ID() uint32

ID reports the identifier for the configuration.

func (*Configuration) NodeIDs 

func (c *Configuration) NodeIDs() []uint32

NodeIDs returns a slice containing the local ids of all the nodes in the configuration. IDs are returned in the same order as they were provided in the creation of the Configuration.

func (*Configuration) Nodes 

func (c *Configuration) Nodes() []*Node

Nodes returns a slice of each available node. IDs are returned in the same order as they were provided in the creation of the Configuration.

func (*Configuration) Read 

func (c *Configuration) Read(ctx context.Context, arg *Key) (*Content, error)

Read is invoked as a quorum call on all nodes in configuration c, using the same argument arg, and returns the result.

func (*Configuration) Size 

func (c *Configuration) Size() int

Size returns the number of nodes in the configuration.

func (*Configuration) String 

func (c *Configuration) String() string

func (*Configuration) Write 

func (c *Configuration) Write(ctx context.Context, arg *Value) (*WriteResponse, error)

Write is invoked as a quorum call on all nodes in configuration c, using the same argument arg, and returns the result.

type Content 

type Content struct {
	Key       string `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
	Timestamp int64  `protobuf:"varint,2,opt,name=timestamp,proto3" json:"timestamp,omitempty"`
	Value     string `protobuf:"bytes,3,opt,name=value,proto3" json:"value,omitempty"`
}

func (*Content) Descriptor 

func (*Content) Descriptor() ([]byte, []int)

func (*Content) Equal 

func (this *Content) Equal(that interface{}) bool

func (*Content) GetKey 

func (m *Content) GetKey() string

func (*Content) GetTimestamp 

func (m *Content) GetTimestamp() int64

func (*Content) GetValue 

func (m *Content) GetValue() string

func (*Content) Marshal 

func (m *Content) Marshal() (dAtA []byte, err error)

func (*Content) MarshalTo 

func (m *Content) MarshalTo(dAtA []byte) (int, error)

func (*Content) ProtoMessage 

func (*Content) ProtoMessage()

func (*Content) Reset 

func (m *Content) Reset()

func (*Content) Size 

func (m *Content) Size() (n int)

func (*Content) String 

func (this *Content) String() string

func (*Content) Unmarshal 

func (m *Content) Unmarshal(dAtA []byte) error

type IllegalConfigError 

type IllegalConfigError string

An IllegalConfigError reports that a specified configuration could not be created.

func (IllegalConfigError) Error 

func (e IllegalConfigError) Error() string

type Key 

type Key struct {
	Key string `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
}

[Read, requestID]

func (*Key) Descriptor 

func (*Key) Descriptor() ([]byte, []int)

func (*Key) Equal 

func (this *Key) Equal(that interface{}) bool

func (*Key) GetKey 

func (m *Key) GetKey() string

func (*Key) Marshal 

func (m *Key) Marshal() (dAtA []byte, err error)

func (*Key) MarshalTo 

func (m *Key) MarshalTo(dAtA []byte) (int, error)

func (*Key) ProtoMessage 

func (*Key) ProtoMessage()

func (*Key) Reset 

func (m *Key) Reset()

func (*Key) Size 

func (m *Key) Size() (n int)

func (*Key) String 

func (this *Key) String() string

func (*Key) Unmarshal 

func (m *Key) Unmarshal(dAtA []byte) error

type Manager 

type Manager struct {
	// contains filtered or unexported fields
}

Manager manages a pool of node configurations on which quorum remote procedure calls can be made.

func NewManager 

func NewManager(nodeAddrs []string, opts ...ManagerOption) (*Manager, error)

NewManager attempts to connect to the given set of node addresses and if successful returns a new Manager containing connections to those nodes.

func (*Manager) AddNode 

func (m *Manager) AddNode(addr string) error

AddNode attempts to dial to the provide node address. The node is added to the Manager's pool of nodes if a connection was established.

func (*Manager) Close 

func (m *Manager) Close()

Close closes all node connections and any client streams.

func (*Manager) Configuration 

func (m *Manager) Configuration(id uint32) (config *Configuration, found bool)

Configuration returns the configuration with the given global identifier if present.

func (*Manager) ConfigurationIDs 

func (m *Manager) ConfigurationIDs() []uint32

ConfigurationIDs returns the identifier of each available configuration.

func (*Manager) Configurations 

func (m *Manager) Configurations() []*Configuration

Configurations returns a slice of each available configuration.

func (*Manager) NewConfiguration 

func (m *Manager) NewConfiguration(ids []uint32, qspec QuorumSpec) (*Configuration, error)

NewConfiguration returns a new configuration given quorum specification and a timeout.

func (*Manager) Node 

func (m *Manager) Node(id uint32) (node *Node, found bool)

Node returns the node with the given identifier if present.

func (*Manager) NodeIDs 

func (m *Manager) NodeIDs() []uint32

NodeIDs returns the identifier of each available node. IDs are returned in the same order as they were provided in the creation of the Manager.

func (*Manager) Nodes 

func (m *Manager) Nodes() []*Node

Nodes returns a slice of each available node. IDs are returned in the same order as they were provided in the creation of the Manager.

func (*Manager) Size 

func (m *Manager) Size() (nodes, configs int)

Size returns the number of nodes and configurations in the Manager.

type ManagerOption 

type ManagerOption func(*managerOptions)

ManagerOption provides a way to set different options on a new Manager.

func WithGrpcDialOptions 

func WithGrpcDialOptions(opts ...grpc.DialOption) ManagerOption

WithGrpcDialOptions returns a ManagerOption which sets any gRPC dial options the Manager should use when initially connecting to each node in its pool.

func WithLogger 

func WithLogger(logger *log.Logger) ManagerOption

WithLogger returns a ManagerOption which sets an optional error logger for the Manager.

func WithNoConnect 

func WithNoConnect() ManagerOption

WithNoConnect returns a ManagerOption which instructs the Manager not to connect to any of its nodes. Mainly used for testing purposes.

func WithTracing 

func WithTracing() ManagerOption

WithTracing controls whether to trace qourum calls for this Manager instance using the golang.org/x/net/trace package. Tracing is currently only supported for regular quorum calls.

type MultiSorter 

type MultiSorter struct {
	// contains filtered or unexported fields
}

MultiSorter implements the Sort interface, sorting the nodes within.

func OrderedBy 

func OrderedBy(less ...lessFunc) *MultiSorter

OrderedBy returns a Sorter that sorts using the less functions, in order. Call its Sort method to sort the data.

func (*MultiSorter) Len 

func (ms *MultiSorter) Len() int

Len is part of sort.Interface.

func (*MultiSorter) Less 

func (ms *MultiSorter) Less(i, j int) bool

Less is part of sort.Interface. It is implemented by looping along the less functions until it finds a comparison that is either Less or !Less. Note that it can call the less functions twice per call. We could change the functions to return -1, 0, 1 and reduce the number of calls for greater efficiency: an exercise for the reader.

func (*MultiSorter) Sort 

func (ms *MultiSorter) Sort(nodes []*Node)

Sort sorts the argument slice according to the less functions passed to OrderedBy.

func (*MultiSorter) Swap 

func (ms *MultiSorter) Swap(i, j int)

Swap is part of sort.Interface.

type Node 

type Node struct {
	StorageClient StorageClient
	// contains filtered or unexported fields
}

Node encapsulates the state of a node on which a remote procedure call can be made.

func (*Node) Address 

func (n *Node) Address() string

Address returns network address of m.

func (*Node) ID 

func (n *Node) ID() uint32

ID returns the ID of m.

func (*Node) LastErr 

func (n *Node) LastErr() error

LastErr returns the last error encountered (if any) when invoking a remote procedure call on this node.

func (*Node) Latency 

func (n *Node) Latency() time.Duration

Latency returns the latency of the last successful remote procedure call made to this node.

func (*Node) String 

func (n *Node) String() string

type NodeNotFoundError 

type NodeNotFoundError uint32

A NodeNotFoundError reports that a specified node could not be found.

func (NodeNotFoundError) Error 

func (e NodeNotFoundError) Error() string

type QuorumCallError 

type QuorumCallError struct {
	Reason               string
	ErrCount, ReplyCount int
}

A QuorumCallError is used to report that a quorum call failed.

func (QuorumCallError) Error 

func (e QuorumCallError) Error() string

type QuorumSpec 

type QuorumSpec interface {
	// ReadQF is the quorum function for the Read
	// quorum call method.
	ReadQF(replies []*Value) (*Content, bool)

	// WriteQF is the quorum function for the Write
	// quorum call method.
	WriteQF(req *Value, replies []*WriteResponse) (*WriteResponse, bool)
}

QuorumSpec is the interface that wraps every quorum function.

type StorageClient 

type StorageClient interface {
	Read(ctx context.Context, in *Key, opts ...grpc.CallOption) (*Value, error)
	Write(ctx context.Context, in *Value, opts ...grpc.CallOption) (*WriteResponse, error)
}

func NewStorageClient 

func NewStorageClient(cc *grpc.ClientConn) StorageClient

type StorageServer 

type StorageServer interface {
	Read(context.Context, *Key) (*Value, error)
	Write(context.Context, *Value) (*WriteResponse, error)
}

type Value 

type Value struct {
	C          *Content `protobuf:"bytes,1,opt,name=c" json:"c,omitempty"`
	SignatureR []byte   `protobuf:"bytes,2,opt,name=signatureR,proto3" json:"signatureR,omitempty"`
	SignatureS []byte   `protobuf:"bytes,3,opt,name=signatureS,proto3" json:"signatureS,omitempty"`
}

[Value, requestID, ts, val, signature] [Write, wts, val, signature]

func (*Value) Descriptor 

func (*Value) Descriptor() ([]byte, []int)

func (*Value) Equal 

func (this *Value) Equal(that interface{}) bool

func (*Value) GetC 

func (m *Value) GetC() *Content

func (*Value) GetSignatureR 

func (m *Value) GetSignatureR() []byte

func (*Value) GetSignatureS 

func (m *Value) GetSignatureS() []byte

func (*Value) Marshal 

func (m *Value) Marshal() (dAtA []byte, err error)

func (*Value) MarshalTo 

func (m *Value) MarshalTo(dAtA []byte) (int, error)

func (*Value) ProtoMessage 

func (*Value) ProtoMessage()

func (*Value) Reset 

func (m *Value) Reset()

func (*Value) Size 

func (m *Value) Size() (n int)

func (*Value) String 

func (this *Value) String() string

func (*Value) Unmarshal 

func (m *Value) Unmarshal(dAtA []byte) error

type WriteResponse 

type WriteResponse struct {
	Timestamp int64 `protobuf:"varint,1,opt,name=timestamp,proto3" json:"timestamp,omitempty"`
}

[Ack, ts]

func (*WriteResponse) Descriptor 

func (*WriteResponse) Descriptor() ([]byte, []int)

func (*WriteResponse) Equal 

func (this *WriteResponse) Equal(that interface{}) bool

func (*WriteResponse) GetTimestamp 

func (m *WriteResponse) GetTimestamp() int64

func (*WriteResponse) Marshal 

func (m *WriteResponse) Marshal() (dAtA []byte, err error)

func (*WriteResponse) MarshalTo 

func (m *WriteResponse) MarshalTo(dAtA []byte) (int, error)

func (*WriteResponse) ProtoMessage 

func (*WriteResponse) ProtoMessage()

func (*WriteResponse) Reset 

func (m *WriteResponse) Reset()

func (*WriteResponse) Size 

func (m *WriteResponse) Size() (n int)

func (*WriteResponse) String 

func (this *WriteResponse) String() string

func (*WriteResponse) Unmarshal 

func (m *WriteResponse) Unmarshal(dAtA []byte) error

Source Files

View all Source files

Directories

Path Synopsis
cmd
byzclient
byzserver

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.