Methods and devices for propagating transactions in a network of nodes, each node having one or more connections to other nodes. The method includes determining that one of the nodes is a bottleneck for propagation of transactions; receiving, over a first time period, a plurality of new transactions from one or more first nodes in the network of nodes; combining the plurality of new transactions using network coding and a local encoding vector to generate a message; and sending the message and a global encoding vector to one or more second nodes in the network of nodes instead of sending the plurality of new transactions to the one or more second nodes. The network may be a blockchain network.