Vinay J. Ribeiro

Shubham Anand Jain, Rohan Shah, Sanit Gupta et al.

We consider the problem of correctly identifying the \textit{mode} of a discrete distribution $\mathcal{P}$ with sufficiently high probability by observing a sequence of i.i.d. samples drawn from $\mathcal{P}$. This problem reduces to the estimation of a single parameter when $\mathcal{P}$ has a support set of size $K = 2$. After noting that this special case is tackled very well by prior-posterior-ratio (PPR) martingale confidence sequences \citep{waudby-ramdas-ppr}, we propose a generalisation to mode estimation, in which $\mathcal{P}$ may take $K \geq 2$ values. To begin, we show that the "one-versus-one" principle to generalise from $K = 2$ to $K \geq 2$ classes is more efficient than the "one-versus-rest" alternative. We then prove that our resulting stopping rule, denoted PPR-1v1, is asymptotically optimal (as the mistake probability is taken to $0$). PPR-1v1 is parameter-free and computationally light, and incurs significantly fewer samples than competitors even in the non-asymptotic regime. We demonstrate its gains in two practical applications of sampling: election forecasting and verification of smart contracts in blockchains.

Aditya Ahuja, Vinay J. Ribeiro, Ranjan Pal

Permissionless blockchain consensus protocols have been designed primarily for defining decentralized economies for the commercial trade of assets, both virtual and physical, using cryptocurrencies. In most instances, the assets being traded are regulated, which mandates that the legal right to their trade and their trade value are determined by the governmental regulator of the jurisdiction in which the trade occurs. Unfortunately, existing blockchains do not formally recognise proposal of legal cryptocurrency transactions, as part of the execution of their respective consensus protocols, resulting in rampant illegal activities in the associated crypto-economies. In this contribution, we motivate the need for regulated blockchain consensus protocols with a case study of the illegal, cryptocurrency based, Silk Road darknet market. We present a novel regulatory framework for blockchain protocols, for ensuring legal transaction confirmation as part of the blockchain distributed consensus. As per our regulatory framework, we derive conditions under which legal transaction throughput supersedes throughput of traditional transactions, which are, in the worst case, an indifferentiable mix of legal and illegal transactions. Finally, we show that with a small change to the standard blockchain consensus execution policy (appropriately introduced through regulation), the legal transaction throughput in the blockchain network can be maximized.