bdls: github.com/Sperax/bdls Index | Files | Directories

package bdls

import "github.com/Sperax/bdls"

Package bdls implements Sperax Byzantine Fault Tolerance in Partially Connected Asynchronous Networks based on https://eprint.iacr.org/2019/1460.pdf.

To make the runtime behavior of consensus algorithm predictable, as a function: y = f(x, t), where 'x' is the message it received, and 't' is the time while being called, and 'y' is the deterministic status of consensus after 'x' and 't' applied to 'f', this library has been designed in a deterministic scheme, without parallel computing, networking, and current time is a parameter to this library.

As it's a pure algorithm implementation, it's not thread-safe! Users of this library should take care of their own sychronziation mechanism.

Index

Package Files

config.go consensus.go doc.go errors.go ipc_peer.go message.go message.pb.go peer.go

Constants

const (
    // ProtocolVersion is the current BDLS protocol implementation version,
    // version wil be sent along with messages for protocol upgrading.
    ProtocolVersion = 1
    // DefaultConsensusLatency is the default propagation latency setting for
    // consensus protocol, user can adjust consensus object's latency setting
    // via Consensus.SetLatency()
    DefaultConsensusLatency = 300 * time.Millisecond
)
const (
    // SizeAxis defines byte size of X-axis or Y-axis in a public key
    SizeAxis = 32
    // SignaturePrefix is the prefix for signing a consensus message
    SignaturePrefix = "BDLS_CONSENSUS_SIGNATURE"
)
const (
    // ConfigMinimumParticipants is the minimum number of participant allow in consensus protocol
    ConfigMinimumParticipants = 4
)

Variables

var (
    // Config Related
    ErrConfigEpoch              = errors.New("Config.Epoch is nil")
    ErrConfigStateNil           = errors.New("Config.CurrentState is nil")
    ErrConfigStateCompare       = errors.New("Config.StateCompare function has not set")
    ErrConfigStateValidate      = errors.New("Config.StateValidate function has not set")
    ErrConfigPrivateKey         = errors.New("Config.PrivateKey has not set")
    ErrConfigParticipants       = errors.New("Config.Participants must contain at least 4 participants")
    ErrConfigPubKeyToCoordinate = errors.New("Config.must contain at least 4 participants")

    // common errors related to every message
    ErrMessageVersion            = errors.New("the message has different version")
    ErrMessageValidator          = errors.New("the message has been rejected by external validator")
    ErrMessageIsEmpty            = errors.New("the message being verified is empty")
    ErrMessageUnknownMessageType = errors.New("unrecognized message type")
    ErrMessageSignature          = errors.New("cannot verify the signature of this message")
    ErrMessageUnknownParticipant = errors.New("the message is from unknown partcipants")

    // <roundchange> related
    ErrRoundChangeHeightMismatch  = errors.New("the <roundchange> message has another height than expected")
    ErrRoundChangeRoundLower      = errors.New("the <roundchange> message has lower round than expected")
    ErrRoundChangeStateValidation = errors.New("the state data validation failed <roundchange> message")

    // <lock> related
    ErrLockEmptyState              = errors.New("the state is empty in <lock> message")
    ErrLockStateValidation         = errors.New("the state data validation failed <lock> message")
    ErrLockHeightMismatch          = errors.New("the <lock> message has another height than expected")
    ErrLockRoundLower              = errors.New("the <lock> message has lower round than expected")
    ErrLockNotSignedByLeader       = errors.New("the <lock> message is not signed by leader")
    ErrLockProofUnknownParticipant = errors.New("the proofs in <lock> message has unknown participant")
    ErrLockProofTypeMismatch       = errors.New("the proofs in <lock> message is not <roundchange>")
    ErrLockProofHeightMismatch     = errors.New("the proofs in <lock> message has mismatched height")
    ErrLockProofRoundMismatch      = errors.New("the proofs in <lock> message has mismatched round")
    ErrLockProofStateValidation    = errors.New("the proofs in <lock> message has invalid state data")
    ErrLockProofInsufficient       = errors.New("the <lock> message has insufficient <roundchange> proofs to the proposed state")

    // <select> related
    ErrSelectStateValidation         = errors.New("the state data validation failed <select> message")
    ErrSelectHeightMismatch          = errors.New("the <select> message has another height than expected")
    ErrSelectRoundLower              = errors.New("the <select> message has lower round than expected")
    ErrSelectNotSignedByLeader       = errors.New("the <select> message is not signed by leader")
    ErrSelectStateMismatch           = errors.New("the <select> message has nil state but proof contains non-nil state")
    ErrSelectProofUnknownParticipant = errors.New("the proofs in <select> message has unknown participant")
    ErrSelectProofTypeMismatch       = errors.New("the proofs in <select> message is not <roundchange>")
    ErrSelectProofHeightMismatch     = errors.New("the proofs in <select> message has mismatched height")
    ErrSelectProofRoundMismatch      = errors.New("the proofs in <select> message has mismatched round")
    ErrSelectProofStateValidation    = errors.New("the proofs in <select> message has invalid state data")
    ErrSelectProofNotTheMaximal      = errors.New("the proposed state is not the maximal one in the <select> message")
    ErrSelectProofInsufficient       = errors.New("the <select> message has insufficient overall proofs")
    ErrSelectProofExceeded           = errors.New("the <select> message overall state proposals exceeded maximal")

    // <decide> Related
    ErrDecideHeightLower             = errors.New("the <decide> message has lower height than expected")
    ErrDecideEmptyState              = errors.New("the state is empty in <decide> message")
    ErrDecideStateValidation         = errors.New("the state data validation failed <decide> message")
    ErrDecideNotSignedByLeader       = errors.New("the <decide> message is not signed by leader")
    ErrDecideProofUnknownParticipant = errors.New("the proofs in <decide> message has unknown participant")
    ErrDecideProofTypeMismatch       = errors.New("the proofs in <decide> message is not <commit>")
    ErrDecideProofHeightMismatch     = errors.New("the proofs in <decide> message has mismatched height")
    ErrDecideProofRoundMismatch      = errors.New("the proofs in <decide> message has mismatched round")
    ErrDecideProofStateValidation    = errors.New("the proofs in <decide> message has invalid state data")
    ErrDecideProofInsufficient       = errors.New("the <decide> message has insufficient <commit> proofs to the proposed state")

    // <lock-release> related
    ErrLockReleaseStatus = errors.New("received <lock-release> message in non LOCK-RELEASE state")

    // <commit> related
    ErrCommitEmptyState      = errors.New("the state is empty in <commit> message")
    ErrCommitStateMismatch   = errors.New("the state in <commit> message does not match what leader has locked")
    ErrCommitStateValidation = errors.New("the state data validation failed <commit> message")
    ErrCommitStatus          = errors.New("received <commit> message in non COMMIT state")
    ErrCommitHeightMismatch  = errors.New("the <commit> messge has another height than expected")
    ErrCommitRoundMismatch   = errors.New("the <commit> message is from another round")

    // <decide> verification
    ErrMismatchedTargetState = errors.New("the state in <decide> message does not match the provided target state")
)
var (
    ErrInvalidLengthMessage        = fmt.Errorf("proto: negative length found during unmarshaling")
    ErrIntOverflowMessage          = fmt.Errorf("proto: integer overflow")
    ErrUnexpectedEndOfGroupMessage = fmt.Errorf("proto: unexpected end of group")
)
var ErrPubKey = errors.New("incorrect pubkey format")

ErrPubKey will be returned if error found while decoding message's public key

var MessageType_name = map[int32]string{
    0:  "Nop",
    1:  "RoundChange",
    2:  "Lock",
    3:  "Select",
    4:  "Commit",
    5:  "LockRelease",
    6:  "Decide",
    7:  "Resync",
}
var MessageType_value = map[string]int32{
    "Nop":         0,
    "RoundChange": 1,
    "Lock":        2,
    "Select":      3,
    "Commit":      4,
    "LockRelease": 5,
    "Decide":      6,
    "Resync":      7,
}
var S256Curve elliptic.Curve = btcec.S256()

secp256k1 elliptic curve

func VerifyConfig Uses

func VerifyConfig(c *Config) error

VerifyConfig verifies the integrity of this config when creating new consensus object

type Config Uses

type Config struct {
    // the starting time point for consensus
    Epoch time.Time
    // CurrentHeight
    CurrentHeight uint64
    // PrivateKey
    PrivateKey *ecdsa.PrivateKey
    // Consensus Group
    Participants []Identity
    // EnableCommitUnicast sets to true to enable <commit> message to be delivered via unicast
    // if not(by default), <commit> message will be broadcasted
    EnableCommitUnicast bool

    // StateCompare is a function from user to compare states,
    // The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
    // Usually this will lead to block header comparsion in blockchain, or replication log in database,
    // users should check fields in block header to make comparison.
    StateCompare func(a State, b State) int

    // StateValidate is a function from user to validate the integrity of
    // state data.
    StateValidate func(State) bool

    // MessageValidator is an external validator to be called when a message inputs into ReceiveMessage
    MessageValidator func(c *Consensus, m *Message, signed *SignedProto) bool

    // MessageOutCallback will be called if not nil before a message send out
    MessageOutCallback func(m *Message, signed *SignedProto)

    // Identity derviation from ecdsa.PublicKey
    // (optional). Default to DefaultPubKeyToIdentity
    PubKeyToIdentity func(pubkey *ecdsa.PublicKey) (ret Identity)
}

Config is to config the parameters of BDLS consensus protocol

type Consensus Uses

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

Consensus implements a deterministic BDLS consensus protocol.

It has no internal clocking or IO, and no parallel processing. The runtime behavior is predictable and deterministic. Users should write their own timing and IO function to feed in messages and ticks to trigger timeouts.

func NewConsensus Uses

func NewConsensus(config *Config) (*Consensus, error)

NewConsensus creates a BDLS consensus object to participant in consensus procedure, the consensus object returned is data in memory without goroutines or other non-deterministic objects, and errors will be returned if there is problem, with the given config.

func (*Consensus) CurrentProof Uses

func (c *Consensus) CurrentProof() *SignedProto

CurrentProof returns current <decide> message for current height

func (*Consensus) CurrentState Uses

func (c *Consensus) CurrentState() (height uint64, round uint64, data State)

CurrentState returns current state along with current height & round, It's caller's responsibility to check if ReceiveMessage() has created a new height.

func (*Consensus) HasProposed Uses

func (c *Consensus) HasProposed(state State) bool

HasProposed checks whether some state has been proposed via <roundchange> <lock> or left in c.unconfirmed

func (*Consensus) Join Uses

func (c *Consensus) Join(p PeerInterface) bool

Join adds a peer to consensus for message delivery, a peer is identified by its address.

func (*Consensus) Leave Uses

func (c *Consensus) Leave(addr net.Addr) bool

Leave removes a peer from consensus, identified by its address

func (*Consensus) Propose Uses

func (c *Consensus) Propose(s State)

Propose adds a new state to unconfirmed queue to particpate in consensus at next height.

func (*Consensus) ReceiveMessage Uses

func (c *Consensus) ReceiveMessage(bts []byte, now time.Time) (err error)

ReceiveMessage processes incoming consensus messages, and returns error if message cannot be processed for some reason.

func (*Consensus) SetLatency Uses

func (c *Consensus) SetLatency(latency time.Duration)

SetLatency sets participants expected latency for consensus core

func (*Consensus) Update Uses

func (c *Consensus) Update(now time.Time) error

Update will process timing event for the state machine, callers from outside MUST call this function periodically(like 20ms).

func (*Consensus) ValidateDecideMessage Uses

func (c *Consensus) ValidateDecideMessage(bts []byte, targetState []byte) error

ValidateDecideMessage validates a <decide> message for non-participants, the consensus core must be correctly initialized to validate. the targetState is to compare the target state enclosed in decide message

type IPCPeer Uses

type IPCPeer struct {
    sync.Mutex
    // contains filtered or unexported fields
}

IPCPeer represents an in-process peer for testing, which sends messages directly via function call, message delivery latency can be customizable to emulate variety of network latency. Delay is randomized with standard normal distribution based on given parameters.

func NewIPCPeer Uses

func NewIPCPeer(c *Consensus, latency time.Duration) *IPCPeer

NewIPCPeer creates IPC based peer with latency, latency is distributed with standard normal distribution.

func (*IPCPeer) Close Uses

func (p *IPCPeer) Close()

Close this peer

func (*IPCPeer) GetBytesCount Uses

func (p *IPCPeer) GetBytesCount() int64

GetBytesCount returns messages bytes count this peer received

func (*IPCPeer) GetLatencies Uses

func (p *IPCPeer) GetLatencies() (min time.Duration, max time.Duration, total time.Duration)

GetLatencies returns actual generated latency

func (*IPCPeer) GetLatestState Uses

func (p *IPCPeer) GetLatestState() (height uint64, round uint64, data State)

GetLatestState returns latest state

func (*IPCPeer) GetMessageCount Uses

func (p *IPCPeer) GetMessageCount() int64

GetMessageCount returns messages count this peer received

func (*IPCPeer) GetPublicKey Uses

func (p *IPCPeer) GetPublicKey() *ecdsa.PublicKey

GetPublicKey returns peer's public key as identity

func (*IPCPeer) Propose Uses

func (p *IPCPeer) Propose(s State)

Propose a state, awaiting to be finalized at next height.

func (*IPCPeer) RemoteAddr Uses

func (p *IPCPeer) RemoteAddr() net.Addr

RemoteAddr implements Peer.RemoteAddr, the address is p's memory address

func (*IPCPeer) Send Uses

func (p *IPCPeer) Send(msg []byte) error

Send implements Peer.Send

func (*IPCPeer) Update Uses

func (p *IPCPeer) Update()

Update will call itself perodically

type Identity Uses

type Identity [2 * SizeAxis]byte

Identity is a user-defined struct to encode X-axis and Y-axis for a publickey in an array

func DefaultPubKeyToIdentity Uses

func DefaultPubKeyToIdentity(pubkey *ecdsa.PublicKey) (ret Identity)

default method to derive coordinate from public key

type Message Uses

type Message struct {
    // Type of this message
    Type MessageType `protobuf:"varint,1,opt,name=Type,proto3,enum=bdls.MessageType" json:"Type,omitempty"`
    // Height in consensus
    Height uint64 `protobuf:"varint,2,opt,name=Height,proto3" json:"Height,omitempty"`
    // Round in consensus
    Round uint64 `protobuf:"varint,3,opt,name=Round,proto3" json:"Round,omitempty"`
    // Proposed state (optional)
    State []byte `protobuf:"bytes,4,opt,name=State,proto3" json:"State,omitempty"`
    // Proofs related
    Proof []*SignedProto `protobuf:"bytes,5,rep,name=Proof,proto3" json:"Proof,omitempty"`
    // for lock-release, it's an embeded <lock> message
    LockRelease          *SignedProto `protobuf:"bytes,6,opt,name=LockRelease,proto3" json:"LockRelease,omitempty"`
    XXX_NoUnkeyedLiteral struct{}     `json:"-"`
    XXX_unrecognized     []byte       `json:"-"`
    XXX_sizecache        int32        `json:"-"`
}

Message defines a consensus message

func DecodeMessage Uses

func DecodeMessage(bts []byte) (*Message, error)

DecodeMessage decodes a binary representation of consensus message.

func (*Message) Descriptor Uses

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

func (*Message) GetHeight Uses

func (m *Message) GetHeight() uint64

func (*Message) GetLockRelease Uses

func (m *Message) GetLockRelease() *SignedProto

func (*Message) GetProof Uses

func (m *Message) GetProof() []*SignedProto

func (*Message) GetRound Uses

func (m *Message) GetRound() uint64

func (*Message) GetState Uses

func (m *Message) GetState() []byte

func (*Message) GetType Uses

func (m *Message) GetType() MessageType

func (*Message) Marshal Uses

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

func (*Message) MarshalTo Uses

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

func (*Message) MarshalToSizedBuffer Uses

func (m *Message) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*Message) ProtoMessage Uses

func (*Message) ProtoMessage()

func (*Message) Reset Uses

func (m *Message) Reset()

func (*Message) Size Uses

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

func (*Message) String Uses

func (m *Message) String() string

func (*Message) Unmarshal Uses

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

func (*Message) XXX_DiscardUnknown Uses

func (m *Message) XXX_DiscardUnknown()

func (*Message) XXX_Marshal Uses

func (m *Message) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*Message) XXX_Merge Uses

func (m *Message) XXX_Merge(src proto.Message)

func (*Message) XXX_Size Uses

func (m *Message) XXX_Size() int

func (*Message) XXX_Unmarshal Uses

func (m *Message) XXX_Unmarshal(b []byte) error

type MessageType Uses

type MessageType int32

MessageType defines supported message types

const (
    // No operation, for default message type, and keepalive connection
    MessageType_Nop MessageType = 0
    // MessageRoundChange = <roundchange> message
    MessageType_RoundChange MessageType = 1
    // MessageLock = <lock> message
    MessageType_Lock MessageType = 2
    // MessageSelect = <select> message
    MessageType_Select MessageType = 3
    // MessageCommit = <commit> message
    MessageType_Commit MessageType = 4
    // MessageLockRelease = <lock-release> message
    MessageType_LockRelease MessageType = 5
    // MessageDecide = <decide> message
    MessageType_Decide MessageType = 6
    // MessageResync= <resync> message
    MessageType_Resync MessageType = 7
)

func (MessageType) EnumDescriptor Uses

func (MessageType) EnumDescriptor() ([]byte, []int)

func (MessageType) String Uses

func (x MessageType) String() string

type PeerInterface Uses

type PeerInterface interface {
    // GetPublicKey returns peer's public key as identity
    GetPublicKey() *ecdsa.PublicKey
    // RemoteAddr returns remote addr
    RemoteAddr() net.Addr
    // Send a msg to this peer
    Send(msg []byte) error
}

PeerInterface is a channel for consensus to send message to the peer

type PubKeyAxis Uses

type PubKeyAxis [SizeAxis]byte

PubKeyAxis defines X-axis or Y-axis in a public key

func (PubKeyAxis) Marshal Uses

func (t PubKeyAxis) Marshal() ([]byte, error)

Marshal implements protobuf MarshalTo

func (*PubKeyAxis) MarshalTo Uses

func (t *PubKeyAxis) MarshalTo(data []byte) (n int, err error)

MarshalTo implements protobuf MarshalTo

func (*PubKeyAxis) Size Uses

func (t *PubKeyAxis) Size() int

Size implements protobuf Size

func (*PubKeyAxis) Unmarshal Uses

func (t *PubKeyAxis) Unmarshal(data []byte) error

Unmarshal implements protobuf Unmarshal

type SignedProto Uses

type SignedProto struct {
    Version uint32 `protobuf:"varint,1,opt,name=version,proto3" json:"version,omitempty"`
    // the Message encoded raw protobuf in bytes
    Message []byte `protobuf:"bytes,2,opt,name=Message,proto3" json:"Message,omitempty"`
    // signer's public key
    X   PubKeyAxis `protobuf:"bytes,3,opt,name=x,proto3,customtype=PubKeyAxis" json:"x"`
    Y   PubKeyAxis `protobuf:"bytes,4,opt,name=y,proto3,customtype=PubKeyAxis" json:"y"`
    // signature r,s for prefix+messages+version+x+y above
    R                    []byte   `protobuf:"bytes,5,opt,name=r,proto3" json:"r,omitempty"`
    S                    []byte   `protobuf:"bytes,6,opt,name=s,proto3" json:"s,omitempty"`
    XXX_NoUnkeyedLiteral struct{} `json:"-"`
    XXX_unrecognized     []byte   `json:"-"`
    XXX_sizecache        int32    `json:"-"`
}

SignedProto defines a message with signature and it's publickey

func DecodeSignedMessage Uses

func DecodeSignedMessage(bts []byte) (*SignedProto, error)

DecodeSignedMessage decodes a binary representation of signed consensus message.

func (*SignedProto) Descriptor Uses

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

func (*SignedProto) GetMessage Uses

func (m *SignedProto) GetMessage() []byte

func (*SignedProto) GetR Uses

func (m *SignedProto) GetR() []byte

func (*SignedProto) GetS Uses

func (m *SignedProto) GetS() []byte

func (*SignedProto) GetVersion Uses

func (m *SignedProto) GetVersion() uint32

func (*SignedProto) Hash Uses

func (sp *SignedProto) Hash() []byte

Hash concats and hash as follows: blake2b(signPrefix + version + pubkey.X + pubkey.Y+len_32bit(msg) + message)

func (*SignedProto) Marshal Uses

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

func (*SignedProto) MarshalTo Uses

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

func (*SignedProto) MarshalToSizedBuffer Uses

func (m *SignedProto) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*SignedProto) ProtoMessage Uses

func (*SignedProto) ProtoMessage()

func (*SignedProto) PublicKey Uses

func (sp *SignedProto) PublicKey(curve elliptic.Curve) *ecdsa.PublicKey

PublicKey returns the public key of this signed message

func (*SignedProto) Reset Uses

func (m *SignedProto) Reset()

func (*SignedProto) Sign Uses

func (sp *SignedProto) Sign(m *Message, privateKey *ecdsa.PrivateKey)

Sign the message with a private key

func (*SignedProto) Size Uses

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

func (*SignedProto) String Uses

func (m *SignedProto) String() string

func (*SignedProto) Unmarshal Uses

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

func (*SignedProto) Verify Uses

func (sp *SignedProto) Verify(curve elliptic.Curve) bool

Verify the signature of this signed message

func (*SignedProto) XXX_DiscardUnknown Uses

func (m *SignedProto) XXX_DiscardUnknown()

func (*SignedProto) XXX_Marshal Uses

func (m *SignedProto) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*SignedProto) XXX_Merge Uses

func (m *SignedProto) XXX_Merge(src proto.Message)

func (*SignedProto) XXX_Size Uses

func (m *SignedProto) XXX_Size() int

func (*SignedProto) XXX_Unmarshal Uses

func (m *SignedProto) XXX_Unmarshal(b []byte) error

type State Uses

type State []byte

State is the data to participant in consensus

type StateHash Uses

type StateHash [blake2b.Size256]byte

StateHash is a fixed size hash to identify a state

Directories

PathSynopsis
agent-tcpPackage agent-tcp implements a TCP based agent to participate in consensus Challenge-Response scheme has been adopted to do interactive authentication
crypto/blake2bPackage blake2b implements the BLAKE2b hash algorithm defined by RFC 7693 and the extendable output function (XOF) BLAKE2Xb.
crypto/btcecPackage btcec implements support for the elliptic curves needed for bitcoin.
timer

Package bdls imports 23 packages (graph) and is imported by 1 packages. Updated 2020-10-22. Refresh now. Tools for package owners.