From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 51935B37 for ; Wed, 19 Apr 2017 11:08:24 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from juno.mpi-klsb.mpg.de (srv-40-62.mpi-klsb.mpg.de [139.19.86.44]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 940D9184 for ; Wed, 19 Apr 2017 11:08:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=mmci.uni-saarland.de; s=mail200803; h=Content-Transfer-Encoding:Mime-Version:Content-Type:References:In-Reply-To:Date:To:From:Subject:Message-ID; bh=XSDpN0dZrP7+P+YoLQACFjh6GtcRRHRlJbl5fTqlw2I=; b=anZ07NoRFPtjW36iqZdorMqG42NFYAQNwCsPYzK6GExP4KdjgpmVMv/OpcRxygtHQMdvpocJ0T5mKm3IG9ukIZKTka+BbcRzopDSI6KKbmhBmwxR9w06Tqrd44GAte7mwCpejWyIQGfGyORVj8pPktwbqP5cDRuApvKprQ9tA3U=; Received: from sam.mpi-klsb.mpg.de ([139.19.86.26]:36416) by juno.mpi-klsb.mpg.de (envelope-from ) with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) id 1d0nT5-000BAi-Ow for bitcoin-dev@lists.linuxfoundation.org; Wed, 19 Apr 2017 13:08:21 +0200 Received: from mbpc48.cs.uni-saarland.de ([134.96.225.161]:57858) by sam.mpi-klsb.mpg.de (envelope-from ) with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) id 1d0nT5-000MGP-JE for bitcoin-dev@lists.linuxfoundation.org; Wed, 19 Apr 2017 13:08:15 +0200 Message-ID: <1492600095.1934.1.camel@mmci.uni-saarland.de> From: Tim Ruffing To: bitcoin-dev@lists.linuxfoundation.org Date: Wed, 19 Apr 2017 13:08:15 +0200 In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.22.6 Mime-Version: 1.0 Content-Transfer-Encoding: 8bit X-MPI-Local-Sender: true X-Spam-Status: No, score=-4.3 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Properties of an ideal PoW algorithm & implementation X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 19 Apr 2017 11:08:24 -0000 On Tue, 2017-04-18 at 12:34 +0200, Natanael via bitcoin-dev wrote: > To prove that an implementation is near optimal, you would show > there's a minimum number of necessary transistor activations per > computed hash, and that your implementation is within a reasonable > range of that number.  I'm not an expert on lower bounds of algorithms but I think proving such properties is basically out of reach for mankind currently. > > We also need to show that for a practical implementation you can't > reuse much internal state (easiest way is "whitening" the block > header, pre-hashing or having a slow hash with an initial whitening > step of its own). This is to kill any ASICBOOST type optimization. > Performance should be constant, not linear relative to input size.  Yes, a reasonable thing in practice seems to use a slower hash function (or just iterating the hash function many times), see also this thread: https://twitter.com/Ethan_Heilman/status/850015029189644288 . PoW verification will still be fast enough. That's not the bottleneck of block verification anyway. Also, I don't agree that a PoW function should not rely on memory. Memory-hard functions are the best we have currently. Tim