Niusha Moshrefi

Niusha Moshrefi, Mahyar Daneshpajooh, Chen Feng

Full nodes in a blockchain network store and verify a copy of the whole blockchain. Unlike full nodes, light clients are low-capacity devices that want to validate certain data on a blockchain. They query the data they want from a full node. If light clients do not verify the data they receive, full nodes might deceive them. SPV, introduced in the Bitcoin paper, is a practical solution to this problem currently used in many PoW blockchains. In SPV, the resources needed to verify a full node's response grow linearly with the blockchain size, making it inefficient over the long run. Another issue with SPV is that the full nodes do not get compensated for the services they provide. In this work, we introduce LightSync, a simple and cost-effective solution for light clients to verify the inclusion of certain data in a PoW blockchain. The resources needed for running LightSync remain constant no matter what the size of the blockchain is. LightSync uses an incentive mechanism that encourages full nodes to participate in the protocol. We perform a thorough analysis of the security of LightSync and discuss the details of deploying it in a real-world environment.

Peter Davies, Vijaykrishna Gurunathan, Niusha Moshrefi et al.

We consider the problem of distributed mean estimation (DME), in which $n$ machines are each given a local $d$-dimensional vector $x_v \in \mathbb{R}^d$, and must cooperate to estimate the mean of their inputs $μ= \frac 1n\sum_{v = 1}^n x_v$, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output $μ$, but $μ$ itself has large norm. In such cases, previous output error bounds perform poorly. In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under $\ell_2$-norm can be computationally impractical, we also present an extension which leverages easy-to-use cubic lattices, and is loose only up to a logarithmic factor in $d$. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches.