From a7cfb274d651e858ab06eff5b28a6f77e0178cf1 Mon Sep 17 00:00:00 2001 From: Determinant Date: Mon, 16 Jul 2018 05:00:14 -0400 Subject: move header files to include/hotstuff --- include/hotstuff/client.h | 66 ++++ include/hotstuff/core.h | 631 ++++++++++++++++++++++++++++++++++++ include/hotstuff/crypto.h | 386 ++++++++++++++++++++++ include/hotstuff/entity.h | 309 ++++++++++++++++++ include/hotstuff/promise.hpp | 745 +++++++++++++++++++++++++++++++++++++++++++ include/hotstuff/type.h | 46 +++ include/hotstuff/util.h | 119 +++++++ 7 files changed, 2302 insertions(+) create mode 100644 include/hotstuff/client.h create mode 100644 include/hotstuff/core.h create mode 100644 include/hotstuff/crypto.h create mode 100644 include/hotstuff/entity.h create mode 100644 include/hotstuff/promise.hpp create mode 100644 include/hotstuff/type.h create mode 100644 include/hotstuff/util.h (limited to 'include') diff --git a/include/hotstuff/client.h b/include/hotstuff/client.h new file mode 100644 index 0000000..dd1cfee --- /dev/null +++ b/include/hotstuff/client.h @@ -0,0 +1,66 @@ +#ifndef _HOTSTUFF_CLIENT_H +#define _HOTSTUFF_CLIENT_H + +#include "type.h" +#include "salticidae/msg.h" +#include "entity.h" + +namespace hotstuff { + +enum { + REQ_CMD = 0x4, + RESP_CMD = 0x5, + CHK_CMD = 0x6 +}; + +class CommandDummy: public Command { + static uint64_t cnt; + uint64_t n; + uint256_t hash; + + public: + + CommandDummy() {} + + ~CommandDummy() override {} + + CommandDummy(uint64_t n): + n(n), hash(salticidae::get_hash(*this)) {} + + static command_t make_cmd() { + return new CommandDummy(cnt++); + } + + void serialize(DataStream &s) const override { + s << n; + } + + void unserialize(DataStream &s) override { + s >> n; + hash = salticidae::get_hash(*this); + } + + const uint256_t &get_hash() const override { + return hash; + } + + bool verify() const override { + return true; + } +}; + +struct MsgClient: public salticidae::MsgBase<> { + using MsgBase::MsgBase; + void gen_reqcmd(const Command &cmd); + void parse_reqcmd(CommandDummy &cmd) const; + + void gen_respcmd(const uint256_t &cmd_hash, const Finality &fin); + void parse_respcmd(uint256_t &cmd_hash, Finality &fin) const; + + void gen_chkcmd(const uint256_t &cmd_hash); + void parse_chkcmd(uint256_t &cmd_hash) const; +}; + +} + +#endif diff --git a/include/hotstuff/core.h b/include/hotstuff/core.h new file mode 100644 index 0000000..c7e1fe6 --- /dev/null +++ b/include/hotstuff/core.h @@ -0,0 +1,631 @@ +#ifndef _HOTSTUFF_CORE_H +#define _HOTSTUFF_CORE_H + +#include +#include +#include +#include + +#include "salticidae/stream.h" +#include "salticidae/util.h" +#include "salticidae/network.h" +#include "salticidae/msg.h" + +#include "promise.hpp" +#include "util.h" +#include "entity.h" +#include "crypto.h" + +using salticidae::EventContext; +using salticidae::Event; +using salticidae::NetAddr; +using salticidae::MsgNetwork; +using salticidae::PeerNetwork; +using salticidae::ElapsedTime; +using salticidae::_1; +using salticidae::_2; + +namespace hotstuff { + +const double ent_waiting_timeout = 10; +const double double_inf = 1e10; + +enum { + PROPOSE = 0x0, + VOTE = 0x1, + QUERY_FETCH_BLK = 0x2, + RESP_FETCH_BLK = 0x3, +}; + +using promise::promise_t; + +struct Proposal; +struct Vote; + +/** Abstraction for HotStuff protocol state machine (without network implementation). */ +class HotStuffCore { + block_t b0; /** the genesis block */ + /* === state variables === */ + /** block containing the QC for the highest block having one */ + block_t bqc; + block_t bexec; /**< last executed block */ + uint32_t vheight; /**< height of the block last voted for */ + /* === auxilliary variables === */ + privkey_bt priv_key; /**< private key for signing votes */ + std::set tails; /**< set of tail blocks */ + ReplicaConfig config; /**< replica configuration */ + /* === async event queues === */ + std::unordered_map qc_waiting; + promise_t propose_waiting; + + block_t sanity_check_delivered(const uint256_t &blk_hash); + void sanity_check_delivered(const block_t &blk); + void check_commit(const block_t &_bqc); + bool update(const uint256_t &bqc_hash); + void on_qc_finish(const block_t &blk); + void on_propose_(const block_t &blk); + + protected: + ReplicaID id; /**< identity of the replica itself */ + const int32_t parent_limit; /**< maximum number of parents */ + + public: + BoxObj storage; + + HotStuffCore(ReplicaID id, + privkey_bt &&priv_key, + int32_t parent_limit); + virtual ~HotStuffCore() = default; + + /* Inputs of the state machine triggered by external events, should called + * by the class user, with proper invariants. */ + + /** Call to initialize the protocol, should be called once before all other + * functions. */ + void on_init(uint32_t nfaulty) { config.nmajority = 2 * nfaulty + 1; } + + /** Call to deliver a block. + * A block is only delivered if itself is fetched, the block for the + * contained qc is fetched and all parents are delivered. The user should + * always ensure this invariant. The invalid blocks will be dropped by this + * function. + * @return true if valid */ + bool on_deliver_blk(const block_t &blk); + + /** Call upon the delivery of a proposal message. + * The block mentioned in the message should be already delivered. */ + void on_receive_proposal(const Proposal &prop); + + /** Call upon the delivery of a vote message. + * The block mentioned in the message should be already delivered. */ + void on_receive_vote(const Vote &vote); + + /** Call to submit new commands to be decided (executed). */ + void on_propose(const std::vector &cmds); + + /* Functions required to construct concrete instances for abstract classes. + * */ + + /* Outputs of the state machine triggering external events. The virtual + * functions should be implemented by the user to specify the behavior upon + * the events. */ + protected: + /** Called by HotStuffCore upon the decision being made for cmd. */ + virtual void do_decide(const command_t &cmd) = 0; + /** Called by HotStuffCore upon broadcasting a new proposal. + * The user should send the proposal message to all replicas except for + * itself. */ + virtual void do_broadcast_proposal(const Proposal &prop) = 0; + /** Called upon sending out a new vote to the next proposer. The user + * should send the vote message to a *good* proposer to have good liveness, + * while safety is always guaranteed by HotStuffCore. */ + virtual void do_vote(ReplicaID last_proposer, const Vote &vote) = 0; + + /* The user plugs in the detailed instances for those + * polymorphic data types. */ + public: + /** Create a partial certificate that proves the vote for a block. */ + virtual part_cert_bt create_part_cert(const PrivKey &priv_key, const uint256_t &blk_hash) = 0; + /** Create a partial certificate from its seralized form. */ + virtual part_cert_bt parse_part_cert(DataStream &s) = 0; + /** Create a quorum certificate that proves 2f+1 votes for a block. */ + virtual quorum_cert_bt create_quorum_cert(const uint256_t &blk_hash) = 0; + /** Create a quorum certificate from its serialized form. */ + virtual quorum_cert_bt parse_quorum_cert(DataStream &s) = 0; + /** Create a command object from its serialized form. */ + virtual command_t parse_cmd(DataStream &s) = 0; + + public: + /** Add a replica to the current configuration. This should only be called + * before running HotStuffCore protocol. */ + void add_replica(ReplicaID rid, const NetAddr &addr, pubkey_bt &&pub_key); + /** Try to prune blocks lower than last committed height - staleness. */ + void prune(uint32_t staleness); + + /* PaceMaker can use these functions to monitor the core protocol state + * transition */ + /** Get a promise resolved when the block gets a QC. */ + promise_t async_qc_finish(const block_t &blk); + /** Get a promise resolved when a new block is proposed. */ + promise_t async_wait_propose(); + + /* Other useful functions */ + block_t get_genesis() { return b0; } + const ReplicaConfig &get_config() { return config; } + int8_t get_cmd_decision(const uint256_t &cmd_hash); + ReplicaID get_id() { return id; } + operator std::string () const; +}; + +/** Abstraction for proposal messages. */ +struct Proposal: public Serializable { + ReplicaID proposer; + /** hash for the block containing the highest QC */ + uint256_t bqc_hash; + /** block being proposed */ + block_t blk; + + /** handle of the core object to allow polymorphism. The user should use + * a pointer to the object of the class derived from HotStuffCore */ + HotStuffCore *hsc; + + Proposal(HotStuffCore *hsc): blk(nullptr), hsc(hsc) {} + Proposal(ReplicaID proposer, + const uint256_t &bqc_hash, + block_t &blk, + HotStuffCore *hsc): + proposer(proposer), + bqc_hash(bqc_hash), + blk(blk), hsc(hsc) {} + + void serialize(DataStream &s) const override { + s << proposer + << bqc_hash + << *blk; + } + + void unserialize(DataStream &s) override { + assert(hsc != nullptr); + s >> proposer + >> bqc_hash; + Block _blk; + _blk.unserialize(s, hsc); + blk = hsc->storage->add_blk(std::move(_blk)); + } + + operator std::string () const { + DataStream s; + s << ""; + return std::string(std::move(s)); + } +}; + +/** Abstraction for vote messages. */ +struct Vote: public Serializable { + ReplicaID voter; + /** hash for the block containing the highest QC */ + uint256_t bqc_hash; + /** block being voted */ + uint256_t blk_hash; + /** proof of validity for the vote (nullptr for a negative vote) */ + part_cert_bt cert; + + /** handle of the core object to allow polymorphism */ + HotStuffCore *hsc; + + Vote(HotStuffCore *hsc): cert(nullptr), hsc(hsc) {} + Vote(ReplicaID voter, + const uint256_t &bqc_hash, + const uint256_t &blk_hash, + part_cert_bt &&cert, + HotStuffCore *hsc): + voter(voter), + bqc_hash(bqc_hash), + blk_hash(blk_hash), + cert(std::move(cert)), hsc(hsc) {} + + Vote(const Vote &other): + voter(other.voter), + bqc_hash(other.bqc_hash), + blk_hash(other.blk_hash), + cert(other.cert->clone()), + hsc(other.hsc) {} + + Vote(Vote &&other) = default; + + void serialize(DataStream &s) const override { + s << voter + << bqc_hash + << blk_hash; + if (cert == nullptr) + s << (uint8_t)0; + else + s << (uint8_t)1 << *cert; + } + + void unserialize(DataStream &s) override { + assert(hsc != nullptr); + uint8_t has_cert; + s >> voter + >> bqc_hash + >> blk_hash + >> has_cert; + cert = has_cert ? hsc->parse_part_cert(s) : nullptr; + } + + bool verify() const { + assert(hsc != nullptr); + return cert->verify(hsc->get_config().get_pubkey(voter)) && + cert->get_blk_hash() == blk_hash; + } + + operator std::string () const { + DataStream s; + s << ""; + return std::string(std::move(s)); + } +}; + +/** Abstraction for liveness gadget (oracle). */ +class PaceMaker { + public: + virtual ~PaceMaker() = default; + /** Get a promise resolved when the pace maker thinks it is a *good* time + * to issue new commands. When promise is resolved with the ID of itself, + * the replica should propose the command, otherwise it will forward the + * command to the proposer indicated by the ID. */ + virtual promise_t beat() = 0; + /** Get a promise resolved when the pace maker thinks it is a *good* time + * to vote for a block. The promise is resolved with the next proposer's ID + * */ + virtual promise_t next_proposer(ReplicaID last_proposer) = 0; +}; + +using pacemaker_bt = BoxObj; + +/** A pace maker that waits for the qc of the last proposed block. */ +class PaceMakerDummy: public PaceMaker { + HotStuffCore *hsc; + std::queue pending_beats; + block_t last_proposed; + bool locked; + + void schedule_next() { + if (!pending_beats.empty() && !locked) + { + auto pm = pending_beats.front(); + pending_beats.pop(); + hsc->async_qc_finish(last_proposed).then( + [id = hsc->get_id(), pm]() { + pm.resolve(id); + }); + locked = true; + } + } + + void update_last_proposed() { + hsc->async_wait_propose().then([this](block_t blk) { + update_last_proposed(); + last_proposed = blk; + locked = false; + schedule_next(); + }); + } + + public: + PaceMakerDummy(HotStuffCore *hsc): + hsc(hsc), + last_proposed(hsc->get_genesis()), + locked(false) { + update_last_proposed(); + } + + promise_t beat() override { + promise_t pm; + pending_beats.push(pm); + schedule_next(); + return pm; + } + + promise_t next_proposer(ReplicaID last_proposer) override { + return promise_t([last_proposer](promise_t &pm) { + pm.resolve(last_proposer); + }); + } +}; + +/** Network message format for HotStuff. */ +struct MsgHotStuff: public salticidae::MsgBase<> { + using MsgBase::MsgBase; + void gen_propose(const Proposal &); + void parse_propose(Proposal &) const; + + void gen_vote(const Vote &); + void parse_vote(Vote &) const; + + void gen_qfetchblk(const std::vector &blk_hashes); + void parse_qfetchblk(std::vector &blk_hashes) const; + + void gen_rfetchblk(const std::vector &blks); + void parse_rfetchblk(std::vector &blks, HotStuffCore *hsc) const; +}; + +using promise::promise_t; + +class HotStuffBase; + +template +class FetchContext: public promise_t { + Event timeout; + HotStuffBase *hs; + MsgHotStuff fetch_msg; + const uint256_t ent_hash; + std::unordered_set replica_ids; + inline void timeout_cb(evutil_socket_t, short); + public: + FetchContext(const FetchContext &) = delete; + FetchContext &operator=(const FetchContext &) = delete; + FetchContext(FetchContext &&other); + + FetchContext(const uint256_t &ent_hash, HotStuffBase *hs); + ~FetchContext() {} + + inline void send(const NetAddr &replica_id); + inline void reset_timeout(); + inline void add_replica(const NetAddr &replica_id, bool fetch_now = true); +}; + +class BlockDeliveryContext: public promise_t { + public: + ElapsedTime elapsed; + BlockDeliveryContext &operator=(const BlockDeliveryContext &) = delete; + BlockDeliveryContext(const BlockDeliveryContext &other): + promise_t(static_cast(other)), + elapsed(other.elapsed) {} + BlockDeliveryContext(BlockDeliveryContext &&other): + promise_t(static_cast(other)), + elapsed(std::move(other.elapsed)) {} + template + BlockDeliveryContext(Func callback): promise_t(callback) { + elapsed.start(); + } +}; + + +/** HotStuff protocol (with network implementation). */ +class HotStuffBase: public HotStuffCore { + using BlockFetchContext = FetchContext; + using CmdFetchContext = FetchContext; + using conn_t = MsgNetwork::conn_t; + + friend BlockFetchContext; + friend CmdFetchContext; + + protected: + /** the binding address in replica network */ + NetAddr listen_addr; + /** the block size */ + size_t blk_size; + /** libevent handle */ + EventContext eb; + pacemaker_bt pmaker; + + private: + /** whether libevent handle is owned by itself */ + bool eb_loop; + /** network stack */ + PeerNetwork pn; +#ifdef HOTSTUFF_ENABLE_BLK_PROFILE + BlockProfiler blk_profiler; +#endif + /* queues for async tasks */ + std::unordered_map blk_fetch_waiting; + std::unordered_map blk_delivery_waiting; + std::unordered_map cmd_fetch_waiting; + std::unordered_map decision_waiting; + std::queue cmd_pending; + + /* statistics */ + uint64_t fetched; + uint64_t delivered; + mutable uint64_t nsent; + mutable uint64_t nrecv; + + mutable uint32_t part_parent_size; + mutable uint32_t part_fetched; + mutable uint32_t part_delivered; + mutable uint32_t part_decided; + mutable uint32_t part_gened; + mutable double part_delivery_time; + mutable double part_delivery_time_min; + mutable double part_delivery_time_max; + mutable std::unordered_map part_fetched_replica; + + void on_fetch_cmd(const command_t &cmd); + void on_fetch_blk(const block_t &blk); + void on_deliver_blk(const block_t &blk); + + /** deliver consensus message: */ + inline void propose_handler(const MsgHotStuff &, conn_t); + /** deliver consensus message: */ + inline void vote_handler(const MsgHotStuff &, conn_t); + /** fetches full block data */ + inline void query_fetch_blk_handler(const MsgHotStuff &, conn_t); + /** receives a block */ + inline void resp_fetch_blk_handler(const MsgHotStuff &, conn_t); + + void do_broadcast_proposal(const Proposal &) override; + void do_vote(ReplicaID, const Vote &) override; + void do_decide(const command_t &) override; + + public: + HotStuffBase(uint32_t blk_size, + int32_t parent_limit, + ReplicaID rid, + privkey_bt &&priv_key, + NetAddr listen_addr, + EventContext eb = EventContext(), + pacemaker_bt pmaker = nullptr); + + ~HotStuffBase(); + + /* the API for HotStuffBase */ + + /* Submit the command to be decided. */ + void add_command(command_t cmd) { + cmd_pending.push(storage->add_cmd(cmd)); + if (cmd_pending.size() >= blk_size) + { + std::vector cmds; + for (uint32_t i = 0; i < blk_size; i++) + { + cmds.push_back(cmd_pending.front()); + cmd_pending.pop(); + } + pmaker->beat().then([this, cmds = std::move(cmds)]() { + on_propose(cmds); + }); + } + } + + void add_replica(ReplicaID idx, const NetAddr &addr, pubkey_bt &&pub_key); + void start(bool eb_loop = false); + + size_t size() const { return pn.all_peers().size(); } + void print_stat() const; + + /* Helper functions */ + /** Returns a promise resolved (with command_t cmd) when Command is fetched. */ + promise_t async_fetch_cmd(const uint256_t &cmd_hash, const NetAddr *replica_id, bool fetch_now = true); + /** Returns a promise resolved (with block_t blk) when Block is fetched. */ + promise_t async_fetch_blk(const uint256_t &blk_hash, const NetAddr *replica_id, bool fetch_now = true); + /** Returns a promise resolved (with block_t blk) when Block is delivered (i.e. prefix is fetched). */ + promise_t async_deliver_blk(const uint256_t &blk_hash, const NetAddr &replica_id); + /** Returns a promise resolved (with command_t cmd) when Command is decided. */ + promise_t async_decide(const uint256_t &cmd_hash); +}; + +/** HotStuff protocol (templated by cryptographic implementation). */ +template +class HotStuff: public HotStuffBase { + using HotStuffBase::HotStuffBase; + protected: + + part_cert_bt create_part_cert(const PrivKey &priv_key, const uint256_t &blk_hash) override { + return new PartCertType( + static_cast(priv_key), + blk_hash); + } + + part_cert_bt parse_part_cert(DataStream &s) override { + PartCert *pc = new PartCertType(); + s >> *pc; + return pc; + } + + quorum_cert_bt create_quorum_cert(const uint256_t &blk_hash) override { + return new QuorumCertType(get_config(), blk_hash); + } + + quorum_cert_bt parse_quorum_cert(DataStream &s) override { + QuorumCert *qc = new QuorumCertType(); + s >> *qc; + return qc; + } + + public: + HotStuff(uint32_t blk_size, + int32_t parent_limit, + ReplicaID rid, + const bytearray_t &raw_privkey, + NetAddr listen_addr, + EventContext eb = nullptr): + HotStuffBase(blk_size, + parent_limit, + rid, + new PrivKeyType(raw_privkey), + listen_addr, + eb) {} + + void add_replica(ReplicaID idx, const NetAddr &addr, const bytearray_t &pubkey_raw) { + DataStream s(pubkey_raw); + HotStuffBase::add_replica(idx, addr, new PubKeyType(pubkey_raw)); + } +}; + +using HotStuffNoSig = HotStuff<>; +using HotStuffSecp256k1 = HotStuff; + +template +FetchContext::FetchContext(FetchContext && other): + promise_t(static_cast(other)), + hs(other.hs), + fetch_msg(std::move(other.fetch_msg)), + ent_hash(other.ent_hash), + replica_ids(std::move(other.replica_ids)) { + other.timeout.del(); + timeout = Event(hs->eb, -1, 0, + std::bind(&FetchContext::timeout_cb, this, _1, _2)); + reset_timeout(); +} + +template<> +inline void FetchContext::timeout_cb(evutil_socket_t, short) { + HOTSTUFF_LOG_WARN("cmd fetching %.10s timeout", get_hex(ent_hash).c_str()); + for (const auto &replica_id: replica_ids) + send(replica_id); + reset_timeout(); +} + +template<> +inline void FetchContext::timeout_cb(evutil_socket_t, short) { + HOTSTUFF_LOG_WARN("block fetching %.10s timeout", get_hex(ent_hash).c_str()); + for (const auto &replica_id: replica_ids) + send(replica_id); + reset_timeout(); +} + +template +FetchContext::FetchContext( + const uint256_t &ent_hash, HotStuffBase *hs): + promise_t([](promise_t){}), + hs(hs), ent_hash(ent_hash) { + fetch_msg.gen_qfetchblk(std::vector{ent_hash}); + + timeout = Event(hs->eb, -1, 0, + std::bind(&FetchContext::timeout_cb, this, _1, _2)); + reset_timeout(); +} + +template +void FetchContext::send(const NetAddr &replica_id) { + hs->part_fetched_replica[replica_id]++; + hs->pn.send_msg(fetch_msg, replica_id); +} + +template +void FetchContext::reset_timeout() { + timeout.add_with_timeout(salticidae::gen_rand_timeout(ent_waiting_timeout)); +} + +template +void FetchContext::add_replica(const NetAddr &replica_id, bool fetch_now) { + if (replica_ids.empty() && fetch_now) + send(replica_id); + replica_ids.insert(replica_id); +} + +} + +#endif diff --git a/include/hotstuff/crypto.h b/include/hotstuff/crypto.h new file mode 100644 index 0000000..2fbf745 --- /dev/null +++ b/include/hotstuff/crypto.h @@ -0,0 +1,386 @@ +#ifndef _HOTSTUFF_CRYPTO_H +#define _HOTSTUFF_CRYPTO_H + +#include "salticidae/crypto.h" +#include "salticidae/ref.h" +#include "secp256k1.h" +#include +#include "type.h" + +using salticidae::RcObj; +using salticidae::BoxObj; + +namespace hotstuff { + +using salticidae::SHA256; + +class PubKey: public Serializable, Cloneable { + public: + virtual ~PubKey() = default; + virtual PubKey *clone() override = 0; +}; + +using pubkey_bt = BoxObj; + +class PrivKey: public Serializable { + public: + virtual ~PrivKey() = default; + virtual pubkey_bt get_pubkey() const = 0; + virtual void from_rand() = 0; +}; + +using privkey_bt = BoxObj; + +class PartCert: public Serializable, public Cloneable { + public: + virtual ~PartCert() = default; + virtual bool verify(const PubKey &pubkey) = 0; + virtual const uint256_t &get_blk_hash() const = 0; + virtual PartCert *clone() override = 0; +}; + +class ReplicaConfig; + +class QuorumCert: public Serializable, public Cloneable { + public: + virtual ~QuorumCert() = default; + virtual void add_part(ReplicaID replica, const PartCert &pc) = 0; + virtual void compute() = 0; + virtual bool verify(const ReplicaConfig &config) = 0; + virtual const uint256_t &get_blk_hash() const = 0; + virtual QuorumCert *clone() override = 0; +}; + +using part_cert_bt = BoxObj; +using quorum_cert_bt = BoxObj; + +class PubKeyDummy: public PubKey { + PubKeyDummy *clone() override { return new PubKeyDummy(*this); } + void serialize(DataStream &) const override {} + void unserialize(DataStream &) override {} +}; + +class PrivKeyDummy: public PrivKey { + pubkey_bt get_pubkey() const override { return new PubKeyDummy(); } + void serialize(DataStream &) const override {} + void unserialize(DataStream &) override {} + void from_rand() override {} +}; + +class PartCertDummy: public PartCert { + uint256_t blk_hash; + public: + PartCertDummy() {} + PartCertDummy(const uint256_t &blk_hash): + blk_hash(blk_hash) {} + + void serialize(DataStream &s) const override { + s << (uint32_t)0 << blk_hash; + } + + void unserialize(DataStream &s) override { + uint32_t tmp; + s >> tmp >> blk_hash; + } + + PartCert *clone() override { + return new PartCertDummy(blk_hash); + } + + bool verify(const PubKey &) override { return true; } + + const uint256_t &get_blk_hash() const override { return blk_hash; } +}; + +class QuorumCertDummy: public QuorumCert { + uint256_t blk_hash; + public: + QuorumCertDummy() {} + QuorumCertDummy(const ReplicaConfig &, const uint256_t &blk_hash): + blk_hash(blk_hash) {} + + void serialize(DataStream &s) const override { + s << (uint32_t)1 << blk_hash; + } + + void unserialize(DataStream &s) override { + uint32_t tmp; + s >> tmp >> blk_hash; + } + + QuorumCert *clone() override { + return new QuorumCertDummy(*this); + } + + void add_part(ReplicaID, const PartCert &) override {} + void compute() override {} + bool verify(const ReplicaConfig &) override { return true; } + + const uint256_t &get_blk_hash() const override { return blk_hash; } +}; + + +class Secp256k1Context { + secp256k1_context *ctx; + friend class PubKeySecp256k1; + friend class SigSecp256k1; + public: + Secp256k1Context(bool sign = false): + ctx(secp256k1_context_create( + sign ? SECP256K1_CONTEXT_SIGN : + SECP256K1_CONTEXT_VERIFY)) {} + + Secp256k1Context(const Secp256k1Context &) = delete; + + Secp256k1Context(Secp256k1Context &&other): ctx(other.ctx) { + other.ctx = nullptr; + } + + ~Secp256k1Context() { + if (ctx) secp256k1_context_destroy(ctx); + } +}; + +using secp256k1_context_t = RcObj; + +extern secp256k1_context_t secp256k1_default_sign_ctx; +extern secp256k1_context_t secp256k1_default_verify_ctx; + +class PrivKeySecp256k1; + +class PubKeySecp256k1: public PubKey { + static const auto _olen = 33; + friend class SigSecp256k1; + secp256k1_pubkey data; + secp256k1_context_t ctx; + + public: + PubKeySecp256k1(const secp256k1_context_t &ctx = + secp256k1_default_sign_ctx): + PubKey(), ctx(ctx) {} + + PubKeySecp256k1(const bytearray_t &raw_bytes, + const secp256k1_context_t &ctx = + secp256k1_default_sign_ctx): + PubKeySecp256k1(ctx) { from_bytes(raw_bytes); } + + inline PubKeySecp256k1(const PrivKeySecp256k1 &priv_key, + const secp256k1_context_t &ctx = + secp256k1_default_sign_ctx); + + void serialize(DataStream &s) const override { + static uint8_t output[_olen]; + size_t olen = _olen; + (void)secp256k1_ec_pubkey_serialize( + ctx->ctx, (unsigned char *)output, + &olen, &data, SECP256K1_EC_COMPRESSED); + s.put_data(output, output + _olen); + } + + void unserialize(DataStream &s) override { + static const auto _exc = std::invalid_argument("ill-formed public key"); + try { + if (!secp256k1_ec_pubkey_parse( + ctx->ctx, &data, s.get_data_inplace(_olen), _olen)) + throw _exc; + } catch (std::ios_base::failure &) { + throw _exc; + } + } + + PubKeySecp256k1 *clone() override { + return new PubKeySecp256k1(*this); + } +}; + +class PrivKeySecp256k1: public PrivKey { + static const auto nbytes = 32; + friend class PubKeySecp256k1; + friend class SigSecp256k1; + uint8_t data[nbytes]; + secp256k1_context_t ctx; + + public: + PrivKeySecp256k1(const secp256k1_context_t &ctx = + secp256k1_default_sign_ctx): + PrivKey(), ctx(ctx) {} + + PrivKeySecp256k1(const bytearray_t &raw_bytes, + const secp256k1_context_t &ctx = + secp256k1_default_sign_ctx): + PrivKeySecp256k1(ctx) { from_bytes(raw_bytes); } + + void serialize(DataStream &s) const override { + s.put_data(data, data + nbytes); + } + + void unserialize(DataStream &s) override { + static const auto _exc = std::invalid_argument("ill-formed private key"); + try { + memmove(data, s.get_data_inplace(nbytes), nbytes); + } catch (std::ios_base::failure &) { + throw _exc; + } + } + + void from_rand() override { + if (!RAND_bytes(data, nbytes)) + throw std::runtime_error("cannot get rand bytes from openssl"); + } + + inline pubkey_bt get_pubkey() const override; +}; + +pubkey_bt PrivKeySecp256k1::get_pubkey() const { + return new PubKeySecp256k1(*this, ctx); +} + +PubKeySecp256k1::PubKeySecp256k1( + const PrivKeySecp256k1 &priv_key, + const secp256k1_context_t &ctx): PubKey(), ctx(ctx) { + if (!secp256k1_ec_pubkey_create(ctx->ctx, &data, priv_key.data)) + throw std::invalid_argument("invalid secp256k1 private key"); +} + +class SigSecp256k1: public Serializable { + secp256k1_ecdsa_signature data; + secp256k1_context_t ctx; + + void check_msg_length(const bytearray_t &msg) { + if (msg.size() != 32) + throw std::invalid_argument("the message should be 32-bytes"); + } + + public: + SigSecp256k1(const secp256k1_context_t &ctx = + secp256k1_default_sign_ctx): + Serializable(), ctx(ctx) {} + SigSecp256k1(const uint256_t &digest, + const PrivKeySecp256k1 &priv_key, + secp256k1_context_t &ctx = + secp256k1_default_sign_ctx): + Serializable(), ctx(ctx) { + sign(digest, priv_key); + } + + void serialize(DataStream &s) const override { + static uint8_t output[64]; + (void)secp256k1_ecdsa_signature_serialize_compact( + ctx->ctx, (unsigned char *)output, + &data); + s.put_data(output, output + 64); + } + + void unserialize(DataStream &s) override { + static const auto _exc = std::invalid_argument("ill-formed signature"); + try { + if (!secp256k1_ecdsa_signature_parse_compact( + ctx->ctx, &data, s.get_data_inplace(64))) + throw _exc; + } catch (std::ios_base::failure &) { + throw _exc; + } + } + + void sign(const bytearray_t &msg, const PrivKeySecp256k1 &priv_key) { + check_msg_length(msg); + if (!secp256k1_ecdsa_sign( + ctx->ctx, &data, + (unsigned char *)&*msg.begin(), + (unsigned char *)priv_key.data, + NULL, // default nonce function + NULL)) + throw std::invalid_argument("failed to create secp256k1 signature"); + } + + bool verify(const bytearray_t &msg, const PubKeySecp256k1 &pub_key, + const secp256k1_context_t &_ctx) { + check_msg_length(msg); + return secp256k1_ecdsa_verify( + _ctx->ctx, &data, + (unsigned char *)&*msg.begin(), + &pub_key.data) == 1; + } + + bool verify(const bytearray_t &msg, const PubKeySecp256k1 &pub_key) { + return verify(msg, pub_key, ctx); + } +}; + +class PartCertSecp256k1: public SigSecp256k1, public PartCert { + uint256_t blk_hash; + + public: + PartCertSecp256k1() = default; + PartCertSecp256k1(const PrivKeySecp256k1 &priv_key, const uint256_t &blk_hash): + SigSecp256k1(blk_hash, priv_key), + PartCert(), + blk_hash(blk_hash) {} + + bool verify(const PubKey &pub_key) override { + return SigSecp256k1::verify(blk_hash, + static_cast(pub_key), + secp256k1_default_verify_ctx); + } + + const uint256_t &get_blk_hash() const override { return blk_hash; } + + PartCertSecp256k1 *clone() override { + return new PartCertSecp256k1(*this); + } + + void serialize(DataStream &s) const override { + s << blk_hash; + this->SigSecp256k1::serialize(s); + } + + void unserialize(DataStream &s) override { + s >> blk_hash; + this->SigSecp256k1::unserialize(s); + } +}; + +class QuorumCertSecp256k1: public QuorumCert { + uint256_t blk_hash; + salticidae::Bits rids; + std::vector sigs; + + public: + QuorumCertSecp256k1() = default; + QuorumCertSecp256k1(const ReplicaConfig &config, const uint256_t &blk_hash); + + void add_part(ReplicaID rid, const PartCert &pc) override { + if (pc.get_blk_hash() != blk_hash) + throw std::invalid_argument("PartCert does match the block hash"); + if (!rids.get(rid)) + { + rids.set(rid); + sigs.push_back(static_cast(pc)); + } + } + + void compute() override {} + + bool verify(const ReplicaConfig &config) override; + + const uint256_t &get_blk_hash() const override { return blk_hash; } + + QuorumCertSecp256k1 *clone() override { + return new QuorumCertSecp256k1(*this); + } + + void serialize(DataStream &s) const override { + s << blk_hash << rids; + for (const auto &sig: sigs) s << sig; + } + + void unserialize(DataStream &s) override { + s >> blk_hash >> rids; + sigs.resize(rids.size()); + for (auto &sig: sigs) s >> sig; + } +}; + +} + +#endif diff --git a/include/hotstuff/entity.h b/include/hotstuff/entity.h new file mode 100644 index 0000000..b3a0df4 --- /dev/null +++ b/include/hotstuff/entity.h @@ -0,0 +1,309 @@ +#ifndef _HOTSTUFF_ENT_H +#define _HOTSTUFF_ENT_H + +#include +#include +#include +#include +#include +#include + +#include "salticidae/netaddr.h" +#include "salticidae/ref.h" +#include "type.h" +#include "util.h" +#include "crypto.h" + +namespace hotstuff { + +enum EntityType { + ENT_TYPE_CMD = 0x0, + ENT_TYPE_BLK = 0x1 +}; + +struct ReplicaInfo { + ReplicaID id; + salticidae::NetAddr addr; + pubkey_bt pubkey; + + ReplicaInfo(ReplicaID id, + const salticidae::NetAddr &addr, + pubkey_bt &&pubkey): + id(id), addr(addr), pubkey(std::move(pubkey)) {} + + ReplicaInfo(const ReplicaInfo &other): + id(other.id), addr(other.addr), + pubkey(other.pubkey->clone()) {} + + ReplicaInfo(ReplicaInfo &&other): + id(other.id), addr(other.addr), + pubkey(std::move(other.pubkey)) {} +}; + +class ReplicaConfig { + std::unordered_map replica_map; + + public: + size_t nmajority; + + void add_replica(ReplicaID rid, const ReplicaInfo &info) { + replica_map.insert(std::make_pair(rid, info)); + } + + const ReplicaInfo &get_info(ReplicaID rid) const { + auto it = replica_map.find(rid); + if (it == replica_map.end()) + throw HotStuffError("rid %s not found", + get_hex(rid).c_str()); + return it->second; + } + + const PubKey &get_pubkey(ReplicaID rid) const { + return *(get_info(rid).pubkey); + } + + const salticidae::NetAddr &get_addr(ReplicaID rid) const { + return get_info(rid).addr; + } +}; + +class Block; +class HotStuffCore; + +using block_t = salticidae::RcObj; +using block_weak_t = salticidae::WeakObj; + +struct Finality: public Serializable { + int8_t decision; + uint256_t blk_hash; + + public: + Finality(): decision(0) {} + Finality(int8_t decision, uint256_t blk_hash): + decision(decision), blk_hash(blk_hash) {} + + void serialize(DataStream &s) const override { + s << decision; + if (decision == 1) s << blk_hash; + } + + void unserialize(DataStream &s) override { + s >> decision; + if (decision == 1) s >> blk_hash; + } +}; + +class Command: public Serializable { + friend HotStuffCore; + block_weak_t container; + public: + virtual ~Command() = default; + virtual const uint256_t &get_hash() const = 0; + virtual bool verify() const = 0; + inline int8_t get_decision() const; + inline Finality get_finality() const; + block_t get_container() const { + return container; + } +}; + +using command_t = RcObj; + +template +inline static std::vector +get_hashes(const std::vector &plist) { + std::vector hashes; + for (const auto &p: plist) + hashes.push_back(p->get_hash()); + return std::move(hashes); +} + +class Block { + friend HotStuffCore; + std::vector parent_hashes; + std::vector cmds; + quorum_cert_bt qc; + uint256_t hash; + + std::vector parents; + block_t qc_ref; + quorum_cert_bt self_qc; + uint32_t height; + bool delivered; + int8_t decision; + + std::unordered_set voted; + + public: + Block(): + qc(nullptr), + qc_ref(nullptr), + self_qc(nullptr), height(0), + delivered(false), decision(0) {} + + Block(bool delivered, int8_t decision): + qc(nullptr), + hash(salticidae::get_hash(*this)), + qc_ref(nullptr), + self_qc(nullptr), height(0), + delivered(delivered), decision(decision) {} + + Block(const std::vector &parents, + const std::vector &cmds, + uint32_t height, + quorum_cert_bt &&qc, + const block_t &qc_ref, + quorum_cert_bt &&self_qc, + int8_t decision = 0): + parent_hashes(get_hashes(parents)), + cmds(cmds), + qc(std::move(qc)), + hash(salticidae::get_hash(*this)), + parents(parents), + qc_ref(qc_ref), + self_qc(std::move(self_qc)), + height(height), + delivered(0), + decision(decision) {} + + void serialize(DataStream &s) const; + + void unserialize(DataStream &s, HotStuffCore *hsc); + + const std::vector &get_cmds() const { + return cmds; + } + + const std::vector &get_parents() const { + return parents; + } + + const std::vector &get_parent_hashes() const { + return parent_hashes; + } + + const uint256_t &get_hash() const { return hash; } + + bool verify(const ReplicaConfig &config) const { + if (qc && !qc->verify(config)) return false; + for (auto cmd: cmds) + if (!cmd->verify()) return false; + return true; + } + + int8_t get_decision() const { return decision; } + + bool is_delivered() const { return delivered; } + + uint32_t get_height() const { return height; } + + const quorum_cert_bt &get_qc() const { return qc; } + + operator std::string () const { + DataStream s; + s << ""; + return std::string(std::move(s)); + } +}; + +struct BlockHeightCmp { + bool operator()(const block_t &a, const block_t &b) const { + return a->get_height() < b->get_height(); + } +}; + +int8_t Command::get_decision() const { + block_t cptr = container; + return cptr ? cptr->get_decision() : 0; +} + +Finality Command::get_finality() const { + block_t blk = get_container(); + return Finality(get_decision(), + blk ? blk->get_hash() : uint256_t()); +} + +class EntityStorage { + std::unordered_map blk_cache; + std::unordered_map cmd_cache; + public: + bool is_blk_delivered(const uint256_t &blk_hash) { + auto it = blk_cache.find(blk_hash); + if (it == blk_cache.end()) return false; + return it->second->is_delivered(); + } + + bool is_blk_fetched(const uint256_t &blk_hash) { + return blk_cache.count(blk_hash); + } + + const block_t &add_blk(Block &&_blk) { + block_t blk = new Block(std::move(_blk)); + return blk_cache.insert(std::make_pair(blk->get_hash(), blk)).first->second; + } + + const block_t &add_blk(const block_t &blk) { + return blk_cache.insert(std::make_pair(blk->get_hash(), blk)).first->second; + } + + block_t find_blk(const uint256_t &blk_hash) { + auto it = blk_cache.find(blk_hash); + return it == blk_cache.end() ? nullptr : it->second; + } + + bool is_cmd_fetched(const uint256_t &cmd_hash) { + return cmd_cache.count(cmd_hash); + } + + const command_t &add_cmd(const command_t &cmd) { + return cmd_cache.insert(std::make_pair(cmd->get_hash(), cmd)).first->second; + } + + command_t find_cmd(const uint256_t &cmd_hash) { + auto it = cmd_cache.find(cmd_hash); + return it == cmd_cache.end() ? nullptr: it->second; + } + + size_t get_cmd_cache_size() { + return cmd_cache.size(); + } + size_t get_blk_cache_size() { + return blk_cache.size(); + } + + bool try_release_cmd(const command_t &cmd) { + if (cmd.get_cnt() == 2) /* only referred by cmd and the storage */ + { + const auto &cmd_hash = cmd->get_hash(); + cmd_cache.erase(cmd_hash); + return true; + } + return false; + } + + bool try_release_blk(const block_t &blk) { + if (blk.get_cnt() == 2) /* only referred by blk and the storage */ + { + const auto &blk_hash = blk->get_hash(); +#ifdef HOTSTUFF_ENABLE_LOG_PROTO + HOTSTUFF_LOG_INFO("releasing blk %.10s", get_hex(blk_hash).c_str()); +#endif + for (const auto &cmd: blk->get_cmds()) + try_release_cmd(cmd); + blk_cache.erase(blk_hash); + return true; + } +#ifdef HOTSTUFF_ENABLE_LOG_PROTO + else + HOTSTUFF_LOG_INFO("cannot release (%lu)", blk.get_cnt()); +#endif + return false; + } +}; + +} + +#endif diff --git a/include/hotstuff/promise.hpp b/include/hotstuff/promise.hpp new file mode 100644 index 0000000..593d5c1 --- /dev/null +++ b/include/hotstuff/promise.hpp @@ -0,0 +1,745 @@ +#ifndef _CPPROMISE_HPP +#define _CPPROMISE_HPP + +/** + * MIT License + * Copyright (c) 2018 Ted Yin + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include +#include +#include +#include +#include + +#if __cplusplus >= 201703L +#ifdef __has_include +# if __has_include() +# include +# ifdef __cpp_lib_any +# define _CPPROMISE_STD_ANY +# endif +# endif +#endif +#endif + +#ifndef _CPPROMISE_STD_ANY +#include +#endif + +/** + * Implement type-safe Promise primitives similar to the ones specified by + * Javascript Promise/A+. + */ +namespace promise { +#ifdef _CPPROMISE_STD_ANY + using pm_any_t = std::any; + template + constexpr auto any_cast = static_cast(std::any_cast); + using bad_any_cast = std::bad_any_cast; +#else +# warning "using boost::any" +# pragma message "using boost::any" + using pm_any_t = boost::any; + template + constexpr auto any_cast = static_cast(boost::any_cast); + using bad_any_cast = boost::bad_any_cast; +#endif + using callback_t = std::function; + using values_t = std::vector; + + /* match lambdas */ + template + struct function_traits: + public function_traits {}; + + template + struct function_traits { + using ret_type = ReturnType; + using arg_type = void; + using empty_arg = void; + }; + + /* match plain functions */ + template + struct function_traits { + using ret_type = ReturnType; + using arg_type = ArgType; + using non_empty_arg = void; + }; + + /* match function pointers */ + template + struct function_traits: + public function_traits {}; + + /* match const member functions */ + template + struct function_traits: + public function_traits {}; + + /* match member functions */ + template + struct function_traits: + public function_traits {}; + + template + using enable_if_return = typename std::enable_if< + std::is_same::ret_type, + ReturnType>::value>; + + template + using disable_if_return = typename std::enable_if< + !std::is_same::ret_type, + ReturnType>::value>; + + template + using enable_if_arg = typename std::enable_if< + std::is_same::arg_type, + ArgType>::value>; + + template + using disable_if_arg = typename std::enable_if< + !std::is_same::arg_type, + ArgType>::value>; + + class Promise; + //class promise_t: public std::shared_ptr { + class promise_t { + Promise *pm; + size_t *ref_cnt; + public: + friend Promise; + template friend promise_t all(const PList &promise_list); + template friend promise_t race(const PList &promise_list); + + inline promise_t(); + inline ~promise_t(); + template inline promise_t(Func callback); + + void swap(promise_t &other) { + std::swap(pm, other.pm); + std::swap(ref_cnt, other.ref_cnt); + } + + promise_t &operator=(const promise_t &other) { + if (this != &other) + { + promise_t tmp(other); + tmp.swap(*this); + } + return *this; + } + + promise_t &operator=(promise_t &&other) { + if (this != &other) + { + promise_t tmp(std::move(other)); + tmp.swap(*this); + } + return *this; + } + + promise_t(const promise_t &other): + pm(other.pm), + ref_cnt(other.ref_cnt) { + ++*ref_cnt; + } + + promise_t(promise_t &&other): + pm(other.pm), + ref_cnt(other.ref_cnt) { + other.pm = nullptr; + } + + Promise *operator->() const { + return pm; + } + + template inline void resolve(T result) const; + template inline void reject(T reason) const; + inline void resolve() const; + inline void reject() const; + + template + inline promise_t then(FuncFulfilled on_fulfilled) const; + + template + inline promise_t then(FuncFulfilled on_fulfilled, + FuncRejected on_rejected) const; + + template + inline promise_t fail(FuncRejected on_rejected) const; + }; + +#define PROMISE_ERR_INVALID_STATE do {throw std::runtime_error("invalid promise state");} while (0) +#define PROMISE_ERR_MISMATCH_TYPE do {throw std::runtime_error("mismatching promise value types");} while (0) + + class Promise { + template friend promise_t all(const PList &promise_list); + template friend promise_t race(const PList &promise_list); + std::vector fulfilled_callbacks; + std::vector rejected_callbacks; +#ifdef CPPROMISE_USE_STACK_FREE + std::vector fulfilled_pms; + std::vector rejected_pms; +#endif + enum class State { + Pending, +#ifdef CPPROMISE_USE_STACK_FREE + PreFulfilled, + PreRejected, +#endif + Fulfilled, + Rejected, + } state; + pm_any_t result; + pm_any_t reason; + + void add_on_fulfilled(callback_t &&cb) { + fulfilled_callbacks.push_back(std::move(cb)); + } + + void add_on_rejected(callback_t &&cb) { + rejected_callbacks.push_back(std::move(cb)); + } + + template::non_empty_arg * = nullptr> + static constexpr auto cps_transform( + Func f, const pm_any_t &result, const promise_t &npm) { + return [&result, npm, f = std::forward(f)]() mutable { +#ifndef CPPROMISE_USE_STACK_FREE + f(result)->then( + [npm] (pm_any_t result) {npm->resolve(result);}, + [npm] (pm_any_t reason) {npm->reject(reason);}); +#else + promise_t rpm{f(result)}; + rpm->then( + [rpm, npm] (pm_any_t result) { + npm->_resolve(result); + }, + [rpm, npm] (pm_any_t reason) { + npm->_reject(reason); + }); + rpm->_dep_resolve(npm); + rpm->_dep_reject(npm); +#endif + }; + } + + template::empty_arg * = nullptr> + static constexpr auto cps_transform( + Func f, const pm_any_t &, const promise_t &npm) { + return [npm, f = std::forward(f)]() mutable { +#ifndef CPPROMISE_USE_STACK_FREE + f()->then( + [npm] (pm_any_t result) {npm->resolve(result);}, + [npm] (pm_any_t reason) {npm->reject(reason);}); +#else + promise_t rpm{f()}; + rpm->then( + [rpm, npm] (pm_any_t result) { + npm->_resolve(result); + }, + [rpm, npm] (pm_any_t reason) { + npm->_reject(reason); + }); + rpm->_dep_resolve(npm); + rpm->_dep_reject(npm); +#endif + }; + } + + template::type * = nullptr> + constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) { + return cps_transform(std::forward(on_fulfilled), this->result, npm); + } + + template::type * = nullptr> + constexpr auto gen_on_rejected(Func on_rejected, const promise_t &npm) { + return cps_transform(std::forward(on_rejected), this->reason, npm); + } + + + template::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) { + return [this, npm, + on_fulfilled = std::forward(on_fulfilled)]() mutable { + on_fulfilled(result); + npm->_resolve(); + }; + } + + template::type * = nullptr, + typename function_traits::empty_arg * = nullptr> + constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) { + return [on_fulfilled = std::forward(on_fulfilled), npm]() mutable { + on_fulfilled(); + npm->_resolve(); + }; + } + + template::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_on_rejected(Func on_rejected, const promise_t &npm) { + return [this, npm, + on_rejected = std::forward(on_rejected)]() mutable { + on_rejected(reason); + npm->_reject(); + }; + } + + template::type * = nullptr, + typename function_traits::empty_arg * = nullptr> + constexpr auto gen_on_rejected(Func on_rejected, const promise_t &npm) { + return [npm, + on_rejected = std::forward(on_rejected)]() mutable { + on_rejected(); + npm->_reject(); + }; + } + + template::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) { + return [this, npm, + on_fulfilled = std::forward(on_fulfilled)]() mutable { + npm->_resolve(on_fulfilled(result)); + }; + } + + template::type * = nullptr, + typename function_traits::empty_arg * = nullptr> + constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) { + return [npm, on_fulfilled = std::forward(on_fulfilled)]() mutable { + npm->_resolve(on_fulfilled()); + }; + } + + template::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_on_rejected(Func on_rejected, const promise_t &npm) { + return [this, npm, on_rejected = std::forward(on_rejected)]() mutable { + npm->_reject(on_rejected(reason)); + }; + } + + template::type * = nullptr, + typename function_traits::empty_arg * = nullptr> + constexpr auto gen_on_rejected(Func on_rejected, const promise_t &npm) { + return [npm, on_rejected = std::forward(on_rejected)]() mutable { + npm->_reject(on_rejected()); + }; + } + +#ifdef CPPROMISE_USE_STACK_FREE + void _trigger() { + std::stack::const_iterator, + std::vector *, + Promise *>> s; + auto push_frame = [&s](Promise *pm) { + if (pm->state == State::PreFulfilled) + { + pm->state = State::Fulfilled; + for (auto &cb: pm->fulfilled_callbacks) cb(); + s.push(std::make_tuple(pm->fulfilled_pms.begin(), + &pm->fulfilled_pms, + pm)); + } + else if (pm->state == State::PreRejected) + { + pm->state = State::Rejected; + for (auto &cb: pm->rejected_callbacks) cb(); + s.push(std::make_tuple(pm->rejected_pms.begin(), + &pm->rejected_pms, + pm)); + } + }; + push_frame(this); + while (!s.empty()) + { + auto &u = s.top(); + auto &it = std::get<0>(u); + auto vec = std::get<1>(u); + auto pm = std::get<2>(u); + if (it == vec->end()) + { + s.pop(); + vec->clear(); + pm->fulfilled_callbacks.clear(); + pm->rejected_callbacks.clear(); + continue; + } + push_frame(*it++); + } + } + + void trigger_fulfill() { + state = State::PreFulfilled; + _trigger(); + } + + void trigger_reject() { + state = State::PreRejected; + _trigger(); + } + + void _resolve() { + if (state == State::Pending) state = State::PreFulfilled; + } + + void _reject() { + if (state == State::Pending) state = State::PreRejected; + } + + void _dep_resolve(const promise_t &npm) { + if (state == State::Pending) + fulfilled_pms.push_back(npm.pm); + else + npm->_trigger(); + } + + void _dep_reject(const promise_t &npm) { + if (state == State::Pending) + rejected_pms.push_back(npm.pm); + else + npm->_trigger(); + } + + void _resolve(pm_any_t _result) { + if (state == State::Pending) + { + result = _result; + state = State::PreFulfilled; + } + } + + void _reject(pm_any_t _reason) { + if (state == State::Pending) + { + reason = _reason; + state = State::PreRejected; + } + } +#else + void _resolve() { resolve(); } + void _reject() { reject(); } + void _resolve(pm_any_t result) { resolve(result); } + void _reject(pm_any_t reason) { reject(reason); } + + void trigger_fulfill() { + state = State::Fulfilled; + for (const auto &cb: fulfilled_callbacks) cb(); + fulfilled_callbacks.clear(); + } + + void trigger_reject() { + state = State::Rejected; + for (const auto &cb: rejected_callbacks) cb(); + rejected_callbacks.clear(); + } +#endif + public: + + Promise(): state(State::Pending) {} + ~Promise() {} + + template + promise_t then(FuncFulfilled on_fulfilled, + FuncRejected on_rejected) { + switch (state) + { + case State::Pending: + return promise_t([this, + on_fulfilled = std::forward(on_fulfilled), + on_rejected = std::forward(on_rejected) + ](promise_t &npm) { + add_on_fulfilled(gen_on_fulfilled(std::move(on_fulfilled), npm)); + add_on_rejected(gen_on_rejected(std::move(on_rejected), npm)); +#ifdef CPPROMISE_USE_STACK_FREE + _dep_resolve(npm); + _dep_reject(npm); +#endif + }); + case State::Fulfilled: + return promise_t([this, + on_fulfilled = std::forward(on_fulfilled) + ](promise_t &npm) { + gen_on_fulfilled(std::move(on_fulfilled), npm)(); + }); + case State::Rejected: + return promise_t([this, + on_rejected = std::forward(on_rejected) + ](promise_t &npm) { + gen_on_rejected(std::move(on_rejected), npm)(); + }); + default: PROMISE_ERR_INVALID_STATE; + } + } + + template + promise_t then(FuncFulfilled &&on_fulfilled) { + switch (state) + { + case State::Pending: + return promise_t([this, + on_fulfilled = std::forward(on_fulfilled) + ](promise_t &npm) { + add_on_fulfilled(gen_on_fulfilled(std::move(on_fulfilled), npm)); + add_on_rejected([this, npm]() {npm->_reject(reason);}); +#ifdef CPPROMISE_USE_STACK_FREE + _dep_resolve(npm); + _dep_reject(npm); +#endif + }); + case State::Fulfilled: + return promise_t([this, + on_fulfilled = std::forward(on_fulfilled) + ](promise_t &npm) { + gen_on_fulfilled(std::move(on_fulfilled), npm)(); + }); + case State::Rejected: + return promise_t([this](promise_t &npm) {npm->_reject(reason);}); + default: PROMISE_ERR_INVALID_STATE; + } + } + + template + promise_t fail(FuncRejected &&on_rejected) { + switch (state) + { + case State::Pending: + return promise_t([this, + on_rejected = std::forward(on_rejected) + ](promise_t &npm) { + callback_t ret; + add_on_rejected(gen_on_rejected(std::move(on_rejected), npm)); + add_on_fulfilled([this, npm]() {npm->_resolve(result);}); +#ifdef CPPROMISE_USE_STACK_FREE + _dep_resolve(npm); + _dep_reject(npm); +#endif + }); + case State::Fulfilled: + return promise_t([this](promise_t &npm) {npm->_resolve(result);}); + case State::Rejected: + return promise_t([this, + on_rejected = std::forward(on_rejected) + ](promise_t &npm) { + gen_on_rejected(std::move(on_rejected), npm)(); + }); + default: PROMISE_ERR_INVALID_STATE; + } + } + + void resolve() { + if (state == State::Pending) trigger_fulfill(); + } + + void reject() { + if (state == State::Pending) trigger_reject(); + } + + void resolve(pm_any_t _result) { + if (state == State::Pending) + { + result = _result; + trigger_fulfill(); + } + } + + void reject(pm_any_t _reason) { + if (state == State::Pending) + { + reason = _reason; + trigger_reject(); + } + } + }; + + template promise_t all(const PList &promise_list) { + return promise_t([&promise_list] (promise_t &npm) { + auto size = std::make_shared(promise_list.size()); + auto results = std::make_shared(); + if (!*size) PROMISE_ERR_MISMATCH_TYPE; + results->resize(*size); + size_t idx = 0; + for (const auto &pm: promise_list) { + pm->then( + [results, size, idx, npm](pm_any_t result) { + (*results)[idx] = result; + if (!--(*size)) + npm->_resolve(*results); + }, + [npm](pm_any_t reason) {npm->_reject(reason);}); +#ifdef CPPROMISE_USE_STACK_FREE + pm->_dep_resolve(npm); + pm->_dep_reject(npm); +#endif + idx++; + } + }); + } + + template promise_t race(const PList &promise_list) { + return promise_t([&promise_list] (promise_t &npm) { + for (const auto &pm: promise_list) { + pm->then([npm](pm_any_t result) {npm->_resolve(result);}, + [npm](pm_any_t reason) {npm->_reject(reason);}); +#ifdef CPPROMISE_USE_STACK_FREE + pm->_dep_resolve(npm); + pm->_dep_reject(npm); +#endif + } + }); + } + + template + inline promise_t::promise_t(Func callback): + pm(new Promise()), + ref_cnt(new size_t(1)) { + callback(*this); + } + + inline promise_t::promise_t(): + pm(new Promise()), + ref_cnt(new size_t(1)) {} + + inline promise_t::~promise_t() { + if (pm) + { + if (--*ref_cnt) return; + delete pm; + delete ref_cnt; + } + } + + template + inline void promise_t::resolve(T result) const { (*this)->resolve(result); } + + template + inline void promise_t::reject(T reason) const { (*this)->reject(reason); } + + inline void promise_t::resolve() const { (*this)->resolve(); } + inline void promise_t::reject() const { (*this)->reject(); } + + template + struct callback_types { + using arg_type = typename function_traits::arg_type; + using ret_type = typename std::conditional< + std::is_same::ret_type, promise_t>::value, + promise_t, pm_any_t>::type; + }; + + template::type * = nullptr, + typename enable_if_return::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_any_callback(Func f) { + using func_t = callback_types; + return [f = std::forward(f)](pm_any_t v) mutable { + try { + f(any_cast(v)); + } catch (bad_any_cast &e) { PROMISE_ERR_MISMATCH_TYPE; } + }; + } + + template::type * = nullptr, + typename enable_if_return::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_any_callback(Func f) { + return [f = std::forward(f)](pm_any_t v) mutable {f(v);}; + } + + template::type * = nullptr, + typename function_traits::empty_arg * = nullptr> + constexpr auto gen_any_callback(Func f) { return std::forward(f); } + + template::type * = nullptr, + typename disable_if_return::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_any_callback(Func f) { + using func_t = callback_types; + return [f = std::forward(f)](pm_any_t v) mutable { + return typename func_t::ret_type(f(v)); + }; + } + + template::type * = nullptr, + typename disable_if_return::type * = nullptr, + typename function_traits::non_empty_arg * = nullptr> + constexpr auto gen_any_callback(Func f) { + using func_t = callback_types; + return [f = std::forward(f)](pm_any_t v) mutable { + try { + return typename func_t::ret_type( + f(any_cast(v))); + } catch (bad_any_cast &e) { PROMISE_ERR_MISMATCH_TYPE; } + }; + } + + template::type * = nullptr, + typename function_traits::empty_arg * = nullptr> + constexpr auto gen_any_callback(Func f) { + using func_t = callback_types; + return [f = std::forward(f)]() mutable { + return typename func_t::ret_type(f()); + }; + } + + template + inline promise_t promise_t::then(FuncFulfilled on_fulfilled) const { + return (*this)->then(gen_any_callback(std::forward(on_fulfilled))); + } + + template + inline promise_t promise_t::then(FuncFulfilled on_fulfilled, + FuncRejected on_rejected) const { + return (*this)->then(gen_any_callback(std::forward(on_fulfilled)), + gen_any_callback(std::forward(on_rejected))); + } + + template + inline promise_t promise_t::fail(FuncRejected on_rejected) const { + return (*this)->fail(gen_any_callback(std::forward(on_rejected))); + } +} + +#endif diff --git a/include/hotstuff/type.h b/include/hotstuff/type.h new file mode 100644 index 0000000..4665979 --- /dev/null +++ b/include/hotstuff/type.h @@ -0,0 +1,46 @@ +#ifndef _HOTSTUFF_TYPE_H +#define _HOTSTUFF_TYPE_H + +#include "salticidae/stream.h" +#include "salticidae/type.h" +#include "salticidae/util.h" + +namespace hotstuff { + +using salticidae::uint256_t; +using salticidae::DataStream; +using salticidae::htole; +using salticidae::letoh; +using salticidae::get_hex; +using salticidae::from_hex; +using salticidae::bytearray_t; + +inline std::string get_hex10(const uint256_t &x) { + return get_hex(x).substr(0, 10); +} + +class HotStuffError: public salticidae::SalticidaeError { + public: + template + HotStuffError(Args... args): salticidae::SalticidaeError(args...) {} +}; + +class HotStuffInvalidEntity: public HotStuffError { + public: + template + HotStuffInvalidEntity(Args... args): HotStuffError(args...) {} +}; + +using salticidae::Serializable; + +class Cloneable { + public: + virtual ~Cloneable() = default; + virtual Cloneable *clone() = 0; +}; + +using ReplicaID = uint16_t; + +} + +#endif diff --git a/include/hotstuff/util.h b/include/hotstuff/util.h new file mode 100644 index 0000000..42c0135 --- /dev/null +++ b/include/hotstuff/util.h @@ -0,0 +1,119 @@ +#ifndef _HOTSTUFF_UTIL_H +#define _HOTSTUFF_UTIL_H + +#include "salticidae/util.h" + +namespace hotstuff { + +class Logger: public salticidae::Logger { + public: + using salticidae::Logger::Logger; +}; + +extern Logger logger; + +#ifdef HOTSTUFF_DEBUG_LOG +#define HOTSTUFF_NORMAL_LOG +#define HOTSTUFF_ENABLE_LOG_DEBUG +#endif + +#ifdef HOTSTUFF_NORMAL_LOG +#define HOTSTUFF_ENABLE_LOG_INFO +#define HOTSTUFF_ENABLE_LOG_WARN +#endif + +#ifdef HOTSTUFF_ENABLE_LOG_INFO +#define HOTSTUFF_LOG_INFO(...) hotstuff::logger.info(__VA_ARGS__) +#else +#define HOTSTUFF_LOG_INFO(...) ((void)0) +#endif + +#ifdef HOTSTUFF_ENABLE_LOG_DEBUG +#define HOTSTUFF_LOG_DEBUG(...) hotstuff::logger.debug(__VA_ARGS__) +#else +#define HOTSTUFF_LOG_DEBUG(...) ((void)0) +#endif + +#ifdef HOTSTUFF_ENABLE_LOG_WARN +#define HOTSTUFF_LOG_WARN(...) hotstuff::logger.warning(__VA_ARGS__) +#else +#define HOTSTUFF_LOG_WARN(...) ((void)0) +#endif + +#define HOTSTUFF_LOG_ERROR(...) hotstuff::logger.error(__VA_ARGS__) + +#ifdef HOTSTUFF_ENABLE_BLK_PROFILE +class BlockProfiler { + enum BlockState { + BLK_SEEN, + BLK_FETCH, + BLK_CC + }; + + struct BlockProfile { + bool is_local; /* is the block proposed by the replica itself? */ + BlockState state; + double hash_seen_time; /* the first time to see block hash */ + double full_fetch_time; /* the first time to get full block content */ + double cc_time; /* the time when it receives cc */ + double commit_time; /* the time when it commits */ + }; + + std::unordered_map blocks; + ElapsedTime timer; + + public: + BlockProfiler() { timer.start(); } + + auto rec_blk(const uint256 &blk_hash, bool is_local) { + auto it = blocks.find(blk_hash); + assert(it == blocks.end()); + timer.stop(false); + return blocks.insert(std::make_pair(blk_hash, + BlockProfile{is_local, BLK_SEEN, timer.elapsed_sec, 0, 0, 0})).first; + } + + void get_blk(const uint256 &blk_hash) { + auto it = blocks.find(blk_hash); + if (it == blocks.end()) + it = rec_blk(blk_hash, false); + BlockProfile &blkp = it->second; + assert(blkp.state == BLK_SEEN); + timer.stop(false); + blkp.full_fetch_time = timer.elapsed_sec; + blkp.state = BLK_FETCH; + } + + void have_cc(const uint256 &blk_hash) { + auto it = blocks.find(blk_hash); + assert(it != blocks.end()); + BlockProfile &blkp = it->second; + assert(blkp.state == BLK_FETCH); + timer.stop(false); + blkp.polling_start_time = timer.elapsed_sec; + blkp.state = BLK_CC; + } + + const char *decide_blk(const uint256 &blk_hash) { + static char buff[1024]; + auto it = blocks.find(blk_hash); + assert(it != blocks.end()); + BlockProfile &blkp = it->second; + assert(blkp.state == BLK_CC); + timer.stop(false); + blkp.commit_time = timer.elapsed_sec; + snprintf(buff, sizeof buff, "(%d,%.4f,%.4f,%.4f,%.4f,%.4f)", + blkp.is_local, + blkp.hash_seen_time, blkp.full_fetch_time, + blkp.polling_start_time, blkp.polling_end_time, + blkp.commit_time); + blocks.erase(it); + return buff; + } +}; + +#endif + +} + +#endif -- cgit v1.2.3-70-g09d2 f='#n2040'>2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562 3563 3564 3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743 3744 3745 3746 3747 3748 3749 3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761