Learning from data owned by several parties, as in federated learning, raises\nchallenges regarding the privacy guarantees provided to participants and the\ncorrectness of the computation in the presence of malicious parties. We tackle\nthese challenges in the context of distributed averaging, an essential building\nblock of federated learning algorithms. Our first contribution is a scalable\nprotocol in which participants exchange correlated Gaussian noise along the\nedges of a network graph, complemented by independent noise added by each\nparty. We analyze the differential privacy guarantees of our protocol and the\nimpact of the graph topology under colluding malicious parties, showing that we\ncan nearly match the utility of the trusted curator model even when each honest\nparty communicates with only a logarithmic number of other parties chosen at\nrandom. This is in contrast with protocols in the local model of privacy (with\nlower utility) or based on secure aggregation (where all pairs of users need to\nexchange messages). Our second contribution enables users to prove the\ncorrectness of their computations without compromising the efficiency and\nprivacy guarantees of the protocol. Our verification protocol relies on\nstandard cryptographic primitives like commitment schemes and zero knowledge\nproofs.\n