From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 20 Mar 2024 13:53:08 -0700 Received: from mail-yb1-f188.google.com ([209.85.219.188]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1rn2vs-0003o0-B5 for bitcoindev@gnusha.org; Wed, 20 Mar 2024 13:53:08 -0700 Received: by mail-yb1-f188.google.com with SMTP id 3f1490d57ef6-dc693399655sf414557276.1 for ; Wed, 20 Mar 2024 13:53:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1710967982; x=1711572782; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=V2KqAfLyzStKA9lgG+00KyimMMkXvcr+XYuryjRKZEo=; b=prmjwwbdEn0cin3I1jxy1WH3t9o5dPuV9Hhg6k9AREZ1S+b93Y8rz9wK7qKIuE7ikf ujKHRCSxNwq5fANChG5x0NjwaPoy7rDmIaywhJnAwN4YiVk0nO4of1ar4ER12K5g8aLl NqQAlmogwBu7XMC1X0pLwhyanZOuw8ANSmypF4WcgvkAQMUcxL0nHUDKxaF2JAgfy48K BVXSrOlfxgE53mYxp7co+wWxSFStBKfstCE4ssGw+9eW/Pf8cryryJJ8G12LI7mYnhaI BTg+3KoIbgBlDeJAwNwVNvG0HSykTwxhlNWiWApbLrtHVDyvs7wovGil0Dju1lZfiBQC Xofw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710967982; x=1711572782; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=V2KqAfLyzStKA9lgG+00KyimMMkXvcr+XYuryjRKZEo=; b=aLabVQkbdm67p6ekTAjgyIZjmGZNvH6RQ0s6zHu36YtioZHNBNF6PdcoNr64mEKr0w egqt9BZvB4uD4c9O3D+ZgDFXbFS+iE79jKhY9tiKskSUxb6y6AtlQuhkyMjnSaN2xOtR c+Wh6523hKddSpPZgctrfbyi4kBNFgtd59wjwA/Mokvr1BiqhXMClKo4n25uzmAaTmk+ 5jL7b/2IdibV+Dh9jIXHBe3zfuQLelaTMsN1CvE/6jB1+QZ3Q5fYBDV5HUh8Q5eI9ciQ OaBEPma9w7FaBmGxrpcUdKEz43pBY8DQW9B7rx0RGZULTFYZA5Gk6Lgc8OjnW2KypZlC O5Zg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710967982; x=1711572782; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=V2KqAfLyzStKA9lgG+00KyimMMkXvcr+XYuryjRKZEo=; b=DuEIyg9G7bGg5gwGKOG0krX07xxRQ67OEU6dChp5RNAk5KV9LoaY+uv3FMXEvHDeZI l4EJE7wRQ4AfgXpM5838uZR0NMKx3K8IuW4PKWvZvhrUE9myNl7UOVcywEP7O4870syX qlTdneQxishhrxammQzi/zomME4n01C6Dys3kwExLR6WSM9K05tBqDpzupzynrEXic+i iwNw3rFmOZkfca5H0OrhAdjuFacV1cE/EplVDmi19ZG1VpxlZydeZ4Pt9627gE+p5hoI lhrT1dx93C7LiXjggvoivjVouG1l1znjqgAUPmGyB9S93c/1m5Lex/A6aNfEPvmcC3rl zN4w== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCUknS7oUPedwps/lKFcphy2g6xe0eAmcn4sNpEz+BSVbHeoNsl0J3Ny/m97QIc1GDkHwLegoJkyNB2bNIUrZH/h/K4bt3s= X-Gm-Message-State: AOJu0Yw39YRH/O6XsswH8g6DYxGYs8xnJtC+z40aZeEWGEgI5lBEQTd4 TSfujaKKVsuc/sYmH26ASFxlZ7MMX1D6YqUciXzOALTB3P4B6SBt X-Google-Smtp-Source: AGHT+IGfipP+BbJCbQN50SURtohj+uqSqs6TNFBkwxskdJ7I1Dlv6PsRxFI01zIsvtFTUR9HCvzaTw== X-Received: by 2002:a5b:51:0:b0:dcc:4cdc:e98e with SMTP id e17-20020a5b0051000000b00dcc4cdce98emr3019545ybp.5.1710967981971; Wed, 20 Mar 2024 13:53:01 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a25:e0d2:0:b0:dcc:4b24:c0da with SMTP id x201-20020a25e0d2000000b00dcc4b24c0dals502748ybg.2.-pod-prod-02-us; Wed, 20 Mar 2024 13:53:01 -0700 (PDT) X-Received: by 2002:a0d:ea0f:0:b0:60c:ca9c:7d10 with SMTP id t15-20020a0dea0f000000b0060cca9c7d10mr3488314ywe.2.1710967980990; Wed, 20 Mar 2024 13:53:00 -0700 (PDT) Received: by 2002:a05:690c:ed0:b0:610:e5cb:e605 with SMTP id 00721157ae682-610f20c60b3ms7b3; Wed, 20 Mar 2024 13:42:35 -0700 (PDT) X-Received: by 2002:a81:fe0e:0:b0:610:c400:9e8a with SMTP id j14-20020a81fe0e000000b00610c4009e8amr1696359ywn.2.1710967354378; Wed, 20 Mar 2024 13:42:34 -0700 (PDT) Date: Wed, 20 Mar 2024 13:42:33 -0700 (PDT) From: Antoine Riard To: Bitcoin Development Mailing List Message-Id: In-Reply-To: <573ba0d7-522c-424e-898f-caa780c6ecf0n@googlegroups.com> References: <573ba0d7-522c-424e-898f-caa780c6ecf0n@googlegroups.com> Subject: [bitcoindev] Re: 51% Attack via Difficulty Increase with a Small Quantum Miner MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_3960_2107380359.1710967353965" X-Original-Sender: antoine.riard@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_Part_3960_2107380359.1710967353965 Content-Type: multipart/alternative; boundary="----=_Part_3961_1012099564.1710967353965" ------=_Part_3961_1012099564.1710967353965 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Or, Thanks for the research. > The complexity of the attack is ~1/r^2 epochs, where r is the fraction of= =20 the block rewards that the quantum miner would have received if they mined= =20 honestly. This attack (or variants thereof) provides essentially the same= =20 benefits as classical 51% attacks, including double spending, and all the= =20 revenue from the block rewards.=20 Quantum algorithm like Grover's algorithm are well-adapted to solve=20 problems with a hidden structure, e.g where the answer can be easily=20 verified. This is the case any randomly yielded state from a qubit vector can be fast= =20 verified as a PoW on a classical computer architecture. However, I'm not sure Grover's algorithm works well for dynamic block=20 template construction and corresponding PoW calculations. Any last-minute high-fee transaction might be selected in the block=20 template, invalidating all the oracle calls performed so far by the run of= =20 the Grover's algorithm. Classical computers do not have this issue that you cannot observe the=20 state until the computation ends, contrary to quantum computers. Inability to adapt to a fast-dynamic fee market might render this 51%=20 attack unsustainable, in a post-subsidy world. > *The attack isn't relevant for the forthcoming years, requiring an=20 extremely fast, noise-tolerant quantum computer.* Information on what is the qubit format and associated solid-state=20 technology used for the estimation can be valuable. Especially to estimate= =20 the real-world energy cost compared to hydro pure ASIC-based mining=20 infrastructure. Best, Antoine Le lundi 18 mars 2024 =C3=A0 13:31:37 UTC, Or Sattath a =C3=A9crit : > Hi, > In a recent work with Bolton Bailey=20 > (still not peer-reviewed) , we showed how a single quantum miner, with=20 > relatively little hashing power, can execute a 51% attack. *The attack=20 > isn't relevant for the forthcoming years, requiring an extremely fast,=20 > noise-tolerant quantum computer.* > The attack is surprisingly simple. The attacker creates a private fork,= =20 > increasing the difficulty by a factor c. Due to the properties of Grover'= s=20 > algorithm, it is only \sqrt c harder for the quantum miner to mine at the= =20 > new difficulty level, but these blocks count as $c$ times more for the Po= W.=20 > Therefore, by mining even a single epoch for a large enough $c$, the=20 > quantum miner can generate more proof-of-work than the competing=20 > (classical) chain. The complexity of the attack is ~1/r^2 epochs, where r= =20 > is the fraction of the block rewards that the quantum miner would have=20 > received if they mined honestly. This attack (or variants thereof) provid= es=20 > essentially the same benefits as classical 51% attacks, including double= =20 > spending, and all the revenue from the block rewards.=20 > > This attack might be relevant when considering future protocol=20 > modifications. > > Or > > > > --=20 You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/= bitcoindev/ee24a4e6-52fe-4e9a-93bb-f37a24f87a89n%40googlegroups.com. ------=_Part_3961_1012099564.1710967353965 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Or,

Thanks for the research.

=
> The complexity of the attack is ~1/r^2 epochs, where r is the fra= ction of the block rewards that the quantum miner would have received if th= ey mined honestly. This attack (or variants thereof) provides essentially t= he same benefits as classical 51% attacks, including double spending, and a= ll the revenue from the block rewards.=C2=A0

Qua= ntum algorithm like Grover's algorithm are well-adapted to solve problems w= ith a hidden structure, e.g where the answer can be easily verified.
<= div>This is the case any randomly yielded state from a qubit vector can be = fast verified as a PoW on a classical computer architecture.
Howe= ver, I'm not sure Grover's algorithm works well for dynamic block template = construction and corresponding PoW calculations.
Any last-minute = high-fee transaction might be selected in the block template, invalidating = all the oracle calls performed so far by the run of the Grover's algorithm.=
Classical computers do not have this issue that you cannot obser= ve the state until the computation ends, contrary to quantum computers.
Inability to adapt to a fast-dynamic fee market might render this 51= % attack unsustainable, in a post-subsidy world.

>=C2=A0The attack isn't relevant for the=C2=A0forthcoming years, requiring an extremely fa= st, noise-tolerant quantum computer.

= Information on what is the qubit format and associated solid-state technolo= gy used for the estimation can be valuable. Especially to estimate the real= -world energy cost compared to hydro pure ASIC-based mining infrastructure.=

Best,
Antoine


<= /div>
Le l= undi 18 mars 2024 =C3=A0 13:31:37 UTC, Or Sattath a =C3=A9crit=C2=A0:
<= /div>
Hi,
In a recen= t work=C2=A0with=C2=A0Bolton B= ailey (still not peer-reviewed)=C2=A0, we showed how a single quantum miner= , with relatively little hashing power, can execute a 51% attack. The at= tack isn't relevant for the=C2=A0forthcoming years, requiring an extremely fast, noise-tolerant quantum = computer.
The attack is surprisingly simple. The attac= ker creates a private fork, increasing the difficulty by a factor c. Due to= the properties of Grover's algorithm, it is only \sqrt c harder for th= e quantum miner to mine at the new difficulty level, but these blocks count= as $c$ times more for the PoW. Therefore, by mining even a single epoch fo= r a large enough $c$, the quantum miner can generate more proof-of-work tha= n the competing (classical) chain. The complexity of the attack is ~1/r^2 e= pochs, where r is the fraction of the block rewards that the quantum miner = would have received if they mined honestly. This attack (or variants thereo= f) provides essentially the same benefits as classical 51% attacks, includi= ng double spending, and all the revenue from the block rewards.=C2=A0
=

This attack might be relevant when considering future p= rotocol modifications.

Or



--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msg= id/bitcoindev/ee24a4e6-52fe-4e9a-93bb-f37a24f87a89n%40googlegroups.com.=
------=_Part_3961_1012099564.1710967353965-- ------=_Part_3960_2107380359.1710967353965--