anonbcast

package
v0.0.0-...-22f7c09 Latest Latest
Warning

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

Go to latest
Published: Sep 7, 2021 License: MIT Imports: 27 Imported by: 0

Documentation

Index

Constants

View Source
const (
	OK             = "OK"
	ErrWrongLeader = "ErrWrongLeader"
)
View Source
const NumRoundsPersisted = 3
View Source
const TEST_MESSAGE_TIMEOUT = 5 * time.Second
View Source
const TEST_PROTOCOL_TIMEOUT = 5 * time.Second

Variables

This section is empty.

Functions

func IsDebug

func IsDebug() bool

func IsDump

func IsDump() bool

func SetDebug

func SetDebug(debug bool)

func SetDump

func SetDump(dump bool)

Types

type AbortOp

type AbortOp struct {
	R int
}

AbortOp aborts the current round. If Round is not equal to the current round, it is a no-op. The state machine will transition to the FailedPhase, and increment its current round.

func (AbortOp) Round

func (op AbortOp) Round() int

func (AbortOp) Type

func (op AbortOp) Type() OpType

type AddProvisionalArgs

type AddProvisionalArgs struct {
	Server string
}

type AddProvisionalReply

type AddProvisionalReply struct {
	Error libraft.AddProvisionalError
}

type AddRemoveArgs

type AddRemoveArgs struct {
	Server string
	IsAdd  bool
}

type AddRemoveReply

type AddRemoveReply struct {
	Submitted bool
	Error     libraft.AddRemoveServerError
}

type Client

type Client struct {
	// Id is the id of this client. Each client has its own unique id.
	// Immutable.
	Id uuid.UUID

	// Config contains an immutable store of the configuration parameters for this particular instance
	Config ClientConfig
	// contains filtered or unexported fields
}

Client performs the anonymous broadcasting protocol, and exposes the bare minimum of communication necessary for an application to broadcast anonymous messages. A Client interacts with a local Server instance to get information, and a possibly remote Server instance to write information.

func NewClient

func NewClient(s *Server, m Messager, cp network.ConnectionProvider, seedConf map[string]bool, conf ClientConfig) *Client

seedConfg is a set

func (*Client) BecomeActive

func (c *Client) BecomeActive()

Handles joining the raft configuration. Submits the raft configuration change. Blocks return until it confirms the client state is active or the client is dead.

func (*Client) BecomeInactive

func (c *Client) BecomeInactive()

Handles leaving the raft configuration. Prevents the client from joining any further rounds. Submits the raft configuration change. Blocks return until it confirms the client state is inactive or the client is dead.

func (*Client) CreateResCh

func (c *Client) CreateResCh() <-chan RoundResult

CreateResCh returns a channel on which the results of rounds are sent. sent. Each round result that the user participated in will be sent exactly once, but it is not guaranteed that the results will be sent in order, if, for example, the user application does not continuously read from the channel.

This method may only be called after an equal number of CreateResCh and DestroyResCh have been called and returned.

func (*Client) DestroyResCh

func (c *Client) DestroyResCh(resCh <-chan RoundResult)

DestroyResCh destroys the result channel, meaning that the user after calling this no longer need to be continuously reading from the channel.

This method may only be called ONCE after CreateResCh has been called and returned.

func (*Client) GetLastStateMachine

func (c *Client) GetLastStateMachine() StateMachine

GetLastStateMachine returns the last known version of the state machine.

func (*Client) Kill

func (c *Client) Kill()

Kill kills all long-running goroutines and releases any memory used by the Client instance. After calling Kill no other methods may be called, except DestroyResCh.

Remember to call DestroyResCh too if CreateResCh was ever called.

func (*Client) Start

func (c *Client) Start(round int) error

Start indicates the intent of the user to start the round.

type ClientConfig

type ClientConfig struct {
	// MessageTimeout is the amount of time that the user has to return from when
	// the client calls the user's Message method. The client will abort the submit
	// phase if more than MessageTimeout + ProtocolTimeout seconds have passed.
	// A reasonable value is 30 seconds, allowing the user to come up with a message and send it.
	MessageTimeout time.Duration

	// ProtocolTimeout is the amount of time that the client will wait for another
	// client j to complete its task. Specifically, if this client has not heard of
	// an update from client j in the last ProtocolTimeout time, and client j should
	// have sent an update at the start of that interval, then this client will abort the round.
	// A reasonable value is 10 seconds, which may allow clients to crash and restart.
	ProtocolTimeout time.Duration

	// MessageSize is the maximum size, in bytes, of the message that the user can send in a round.
	// Note that to make sure that each message has indistinguishable length, each message will
	// need to be padded to this length, so in terms of cost analysis the messages will always have
	// the maximum length.
	MessageSize int
}

type CommutativeCrypto

type CommutativeCrypto interface {
	// PrepareMsg converts a plaintext message to a plaintext Msg.
	// Returns an error if the message is too long.
	PrepareMsg(msg []byte) (Msg, error)

	// Encrypt encrypts a message
	Encrypt(key PrivateKey, m Msg) Msg

	// Decrypt decrypts a message
	Decrypt(key PrivateKey, m Msg) Msg

	// ExtractMsg reverses PrepareMsg
	ExtractMsg(m Msg) []byte

	// GenKey generates a private key
	GenKey() PrivateKey

	// DeepCopy copies itself, to avoid race conditions
	DeepCopy() CommutativeCrypto

	// Verify returns nil if and only if this crypto is safe for message sizes
	// up to and including messageSize bytes
	Verify(messageSize int) error
}

type DecryptedOp

type DecryptedOp struct {
	Id       uuid.UUID
	R        int
	Messages []Msg
	// Prev is the number of participants who have previously submitted a scrambled.
	// This supports the test-and-set behavior.
	Prev int
}

DecryptedOp announces that a participant has decrypted all messages. If Round is not equal to current round, or the current phase isn't DecryptPhase, it is a no-op. If a participant with the given Id does not exist, it is a no-op (and logs a warning, because it should never happen with a legal client). If Prev is not the previous number of participants who have decrypted, it is a no-op. If this participant has already decrypted, it is a no-op. If this is the last participant to decrypt, the state machine will transition to the RevealPhase.

func (DecryptedOp) Round

func (op DecryptedOp) Round() int

func (DecryptedOp) Type

func (op DecryptedOp) Type() OpType

type EncryptedOp

type EncryptedOp struct {
	Id uuid.UUID
	R  int
	// Messages need to be in same order as before.
	Messages []Msg
	// Prev is the number of participants who have previously encrypted.
	// This supports the test-and-set behavior.
	Prev int
}

EncryptedOp announces that a participant has encrypted all messages exactly once with its encryption key. If Round is not equal to the current round, or the current phase isn't EncryptPhase, it is a no-op. If a participant with the given Id does not exist, it is a no-op (and logs a warning, because it should never happen with a legal client). If Prev is not the previous number of participants who have encrypted, it is a no-op. If this participant has already encrypted, it is a no-op. If this is the last participant to encrypt, the state machine will transition to the ScramblePhase.

func (EncryptedOp) Round

func (op EncryptedOp) Round() int

func (EncryptedOp) Type

func (op EncryptedOp) Type() OpType

type Err

type Err string

type InConfigurationArgs

type InConfigurationArgs struct {
	Server           string
	IsProvisionalReq bool
}

type InConfigurationReply

type InConfigurationReply struct {
	InConfiguration bool
	IsLeader        bool
}

type JoinOp

type JoinOp struct {
	Id uuid.UUID
	R  int
}

JoinOp indicates participation for a participant in a round, submitting their UUID. If Round is not equal to current round, or the current phase isn't PreparePhase, it is a no-op. If the participant Id has already been submitted, it is a no-op.

func (JoinOp) Round

func (op JoinOp) Round() int

func (JoinOp) Type

func (op JoinOp) Type() OpType

type MessageOp

type MessageOp struct {
	Id            uuid.UUID
	R             int
	Message       Msg
	RevealKeyHash []byte
}

MessageOp submits a message that has been encrypted once with the participant's own encryption key. If Round is not equal to the current round, or the current phase isn't SubmitPhase, it is a no-op. If a participant with the given Id does not exist, it is a no-op (and logs a warning, because it should never happen with a legal client). If a message for this user has already been submitted, it is overwritten. If a reveal key hash for this user has already been submitted, it is overwritten. If this is the last participant to submit a message, the state machine will transition to the EncryptPhase.

func (MessageOp) Round

func (op MessageOp) Round() int

func (MessageOp) Type

func (op MessageOp) Type() OpType

type Messager

type Messager interface {
	// Message returns the message for this participant in the given round.
	// It may block. If it takes too much time, its return value may be ignored.
	// (i.e., the protocol has timed out and moved on to the next round)
	Message(round int) []byte
}

type Msg

type Msg struct {
	// M stores the raw value of the big.Int.
	// Ideally we would have used a *big.Int here, but unfortunately it cannot be sent over RPC.
	M []byte
}

func NewMsg

func NewMsg(m *big.Int) Msg

func NilMsg

func NilMsg() Msg

func (Msg) DeepCopy

func (m Msg) DeepCopy() Msg

func (Msg) Equal

func (m Msg) Equal(m2 Msg) (bool, error)

func (Msg) Nil

func (m Msg) Nil() bool

type Op

type Op interface {
	Type() OpType
	Round() int
}

Op represents an operation to be applied to the state machine. The operation is submitted by an RPC call to the leader of the Raft cluster, and gets stored in the Raft log. An Op is immutable and thread safe.

type OpRpcReply

type OpRpcReply struct {
	Err Err
}

type OpType

type OpType string
const (
	JoinOpType      OpType = "join"
	StartOpType     OpType = "start"
	MessageOpType   OpType = "message"
	EncryptedOpType OpType = "encrypted"
	ScrambledOpType OpType = "scrambled"
	DecryptedOpType OpType = "decrypted"
	RevealOpType    OpType = "reveal"
	AbortOpType     OpType = "abort"
)

type Phase

type Phase string
const (
	PreparePhase  Phase = "PREPARE"
	SubmitPhase   Phase = "SUBMIT"
	EncryptPhase  Phase = "ENCRYPT"
	ScramblePhase Phase = "SCRAMBLE"
	DecryptPhase  Phase = "DECRYPT"
	RevealPhase   Phase = "REVEAL"
	DonePhase     Phase = "DONE"
	FailedPhase   Phase = "FAILED"
)

type PrivateKey

type PrivateKey struct {
	E, D []byte
}

func NilPrivateKey

func NilPrivateKey() PrivateKey

func (PrivateKey) DeepCopy

func (pk PrivateKey) DeepCopy() PrivateKey

func (PrivateKey) Hash

func (pk PrivateKey) Hash() []byte

func (PrivateKey) HashEquals

func (pk PrivateKey) HashEquals(hash []byte) (bool, error)

func (PrivateKey) Nil

func (pk PrivateKey) Nil() bool

type RespChannels

type RespChannels interface {
	Create(i int, j int) chan bool
	Get(i int, j int) chan bool
	Close(i int, j int)
	Clear()
}

RespChannels provides a simple interface for storing channels over which messages can be sent. It is NOT thread safe (but the individual channels are, of course).

func NewRespChannels

func NewRespChannels() RespChannels

type RevealOp

type RevealOp struct {
	Id        uuid.UUID
	R         int
	RevealKey PrivateKey
}

RevealOp is reveals a participant's reveal key pair. If Round is not equal to the current round, or the current phase isn't RevealPhase, it is a no-op. If a participant with the given Id does not exist, it is a no-op (and logs a warning, because it should never happen with a legal client). If a reveal key pair for this participant has already been submitted, it is overwritten. If this is the last participant to submit a reveal key pair, the state machine will transition to the DonePhase, as well as increment its current round.

func (RevealOp) Round

func (op RevealOp) Round() int

func (RevealOp) Type

func (op RevealOp) Type() OpType

type RoundInfo

type RoundInfo struct {
	// Phase is the phase that the round is in.
	Phase Phase
	// Crypto is an object that allows us to do consistent commutative encryption. It is typically a big prime.
	Crypto CommutativeCrypto
	// Participants is a list of uuids for every participant, uniquely identifying them
	Participants []uuid.UUID
	// Messages is a list of messages, should have same length as Participants. If participant i
	// hasn't sent in a message yet, Messages[i] is the null value (i.e. "")
	// The messages change over the course of the progress of the protocol.
	Messages []Msg
	// Encrypted[i] is true if and only if participant Participants[i] has encrypted the messages
	Encrypted []bool
	// Scrambled[i] is true if and only if participant Participants[i] has scrambled the messages
	Scrambled []bool
	// Decrypted[i] is true if and only if participant Participants[i] has decrypted the messages
	Decrypted []bool
	// RevealedKeys[i] is the public/private reveal keypair of participant Participants[i],
	// or the nil value of the type if the participant has yet to submit it
	RevealedKeys []PrivateKey
	// RevealKeyHashes[i] is a SHA256 hash of the reveal key of participant Participants[i],
	// or a length 0 or nil slice if the participant has yet to submit it
	RevealKeyHashes [][]byte
}

func (RoundInfo) DeepCopy

func (ri RoundInfo) DeepCopy() RoundInfo

type RoundResult

type RoundResult struct {
	// Round is the round we're looking at.
	Round int
	// Succeeded is true if the round resulted in the DonePhase
	// and no malicious failure was detected; false otherwise.
	Succeeded bool
	// Messages contains all the plaintext messages from this round.
	Messages [][]byte
	// MaliciousError is non-nil if an inconsistency was detected where a possible
	// explanation is that a malicious user found the authors of some messages.
	// If MaliciousError is nil, then it is guaranteed that no user was able to
	// determine the origin of any messages.
	MaliciousError error
}

RoundResult represents the final outcome of a round.

type ScrambledOp

type ScrambledOp struct {
	Id       uuid.UUID
	R        int
	Messages []Msg
}

ScrambledOp announces that a participant has scrambled all messages. If Round is not equal to the current round, or the current phase isn't ScramblePhase, it is a no-op. If a participant with the given Id does not exist, it is a no-op (and logs a warning, because it should never happen with a legal client). If not all participants with index < this participant's index have scrambled, it is a no-op. If this participant has already scrambled, it is a no-op. If this is the last participant to scramble, the state machine will transition to the DecryptPhase.

func (ScrambledOp) Round

func (op ScrambledOp) Round() int

func (ScrambledOp) Type

func (op ScrambledOp) Type() OpType

type Server

type Server struct {
	Me string
	// contains filtered or unexported fields
}

Server implements the shared state machine on top of Raft, that is used for performing the anonymous broadcasting protocol. It exposes RPCs that can be called by a Client on a different machine, and exposes a channel that can be consumed by a local Client for reading the latest state.

func MakeServer

func MakeServer(cp network.ConnectionProvider, initialCfg map[string]bool, persister *libraft.Persister, maxraftstate int) (*Server, libraft.Raft)

Creates and starts new anonbcast server using a real raft instance

func NewServer

func NewServer(me string, rf libraft.Raft) *Server

func (*Server) AddProvisional

func (s *Server) AddProvisional(ctx context.Context, args *AddProvisionalArgs, reply *AddProvisionalReply) error

Essentially a pass through for the AddProvisional raft RPC

func (*Server) AddRemove

func (s *Server) AddRemove(ctx context.Context, args *AddRemoveArgs, reply *AddRemoveReply) error

Essentially a pass through for the AddRemove raft RPC

func (*Server) CloseUpdCh

func (s *Server) CloseUpdCh(index int)

func (*Server) GetUpdCh

func (s *Server) GetUpdCh() (<-chan UpdateMsg, int)

GetUpdCh returns a channel on which the server will send a copy of the state machine every time it updates. This method can be called multiple times; in that case, it will return distinct channels, each of which will receive all updates. At the time this method is called, the current state of the state machine will be immediately sent on the channel. All updates are guaranteed to come, and they are guaranteed to come in order.

The client MUST almost always be reading from the channel. It may never block for an extended amount of time not reading on the returned channel. Before the client stops reading from the channel, it must call CloseUpdCh.

func (*Server) InConfiguration

func (s *Server) InConfiguration(ctx context.Context, args *InConfigurationArgs, reply *InConfigurationReply) error

Returns whether or not this Raft is a leader and whether or not the given server is in this raft's configuration.

func (*Server) IsLeader

func (s *Server) IsLeader(args interface{}, reply *OpRpcReply)

func (*Server) Kill

func (s *Server) Kill()

Kill kills all long-running goroutines and releases any memory used by the Server instance. After calling Kill no other methods may be called.

func (*Server) SubmitOp

func (s *Server) SubmitOp(ctx context.Context, args *Op, reply *OpRpcReply) error

SubmitOp is an RPC for clients to submit operations to the state machine. Returns OK if this operation shouldn't be retried (because it has been committed or because it is a no-op), and ErrWrongLeader if the operation should be submitted to another server that might be the leader.

type StartOp

type StartOp struct {
	Id     uuid.UUID
	R      int
	Crypto CommutativeCrypto
}

StartOp transitions from the PreparePhase to the SubmitPhase. It also submits Crypto to the round, overwriting the value if it exists. If Round is not equal to the current round, or the current phase isn't PreparePhase, it is a no-op.

func (StartOp) Round

func (op StartOp) Round() int

func (StartOp) Type

func (op StartOp) Type() OpType

type StateMachine

type StateMachine struct {
	// Round is the current round that the state machine is in. It increases
	// monotonically, starting at 0.
	Round int
	// Rounds store the data for the NumRoundsPersisted last rounds, at
	// index round # mod 3
	Rounds [NumRoundsPersisted]RoundInfo
}

StateMachine is the shared state machine that records the state of the anonymous broadcasting protocol. It is NOT thread safe.

func NewStateMachine

func NewStateMachine(snapshot []byte) StateMachine

NewStateMachine returns a new state machine. If snapshot is nil, it creates the state machine from the initial state. Otherwise, it creates the state machine from the given snapshot.

func (*StateMachine) Apply

func (sm *StateMachine) Apply(op Op) bool

Apply applies an operation to the state machine. Note that operations may not always have an effect, for example if the round number is out of date. If an operation has an effect, this method must return true; otherwise, it may return false.

func (*StateMachine) CurrentRoundInfo

func (sm *StateMachine) CurrentRoundInfo() *RoundInfo

func (*StateMachine) DeepCopy

func (sm *StateMachine) DeepCopy() StateMachine

DeepCopy returns a deep copy of this state machine, sharing no data with the original state machine. This means that it is fine to use a deep-copied state machine concurrently with its original.

func (*StateMachine) GetRoundInfo

func (sm *StateMachine) GetRoundInfo(round int) (*RoundInfo, error)

GetRoundInfo returns the round info associated with the given round, or an error if that round is either (1) too old or (2) to new to have an associated round info.

func (*StateMachine) GuaranteedNoEffect

func (sm *StateMachine) GuaranteedNoEffect(op Op) bool

GuaranteedNoEffect returns true only if the supplied operation is a no-op on the state machine in its current state AND all possible future states. For example, if the state machine is in round 10 and op has round 9, this should return true. It is always safe to return false, but it may improve performance to return true when allowed.

func (*StateMachine) MayPrecede

func (sm *StateMachine) MayPrecede(sm2 StateMachine) bool

MayPrecede returns true if and only if the phase and round of sm may come before the phase and round of sm2.

func (*StateMachine) Snapshot

func (sm *StateMachine) Snapshot() []byte

Snapshot returns a snapshot of the state machine, from which it can be deterministically recreated using NewStateMachine.

type UpdateMsg

type UpdateMsg struct {
	ConfigurationValid bool
	Configuration      map[string]bool

	StateMachineValid bool
	StateMachine      StateMachine
}

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL