📅 Original date posted:2015-03-27
📝 Original message:I agree that someone could do this, but why is that a problem? Isn't the goal of this exercise to ensure more full nodes on the network? In order to be able to answer the challenges, an entity would need to be running a full node somewhere. Thus, they have contributed at least one additional full node to the network. I could certainly see a case for a company to host hundreds of lightweight (e.g., EC2) servers all backed by a single copy of the block chain. Why force every single machine to have its own copy? All you really need to require is that each agency/participant have its own copy.
On Friday, 27 March 2015, at 2:32 pm, Robert McKay wrote:
> Basically the problem with that is that someone could setup a single
> full node that has the blockchain and can answer those challenges and
> then a bunch of other non-full nodes that just proxy any such challenges
> to the single full node.
>
> Rob
>
> On 2015-03-26 23:04, Matt Whitlock wrote:
> > Maybe I'm overlooking something, but I've been watching this thread
> > with increasing skepticism at the complexity of the offered solution.
> > I don't understand why it needs to be so complex. I'd like to offer
> > an
> > alternative for your consideration...
> >
> > Challenge:
> > "Send me: SHA256(SHA256(concatenation of N pseudo-randomly selected
> > bytes from the block chain))."
> >
> > Choose N such that it would be infeasible for the responding node to
> > fetch all of the needed blocks in a short amount of time. In other
> > words, assume that a node can seek to a given byte in a block stored
> > on local disk much faster than it can download the entire block from
> > a
> > remote peer. This is almost certainly a safe assumption.
> >
> > For example, choose N = 1024. Then the proving node needs to perform
> > 1024 random reads from local disk. On spinning media, this is likely
> > to take somewhere on the order of 15 seconds. Assuming blocks are
> > averaging 500 KiB each, then 1024 blocks would comprise 500 MiB of
> > data. Can 500 MiB be downloaded in 15 seconds? This data transfer
> > rate
> > is 280 Mbps. Almost certainly not possible. And if it is, just
> > increase N. The challenge also becomes more difficult as average
> > block
> > size increases.
> >
> > This challenge-response protocol relies on the lack of a "partial
> > getdata" command in the Bitcoin protocol: a node cannot ask for only
> > part of a block; it must ask for an entire block. Furthermore, nodes
> > could ban other nodes for making too many random requests for blocks.
> >
> >
> > On Thursday, 26 March 2015, at 7:09 pm, Sergio Lerner wrote:
> >>
> >> > If I understand correctly, transforming raw blocks to keyed blocks
> >> > takes 512x longer than transforming keyed blocks back to raw. The
> >> key
> >> > is public, like the IP, or some other value which perhaps changes
> >> less
> >> > frequently.
> >> >
> >> Yes. I was thinking that the IP could be part of a first layer of
> >> encryption done to the blockchain data prior to the asymetric
> >> operation.
> >> That way the asymmetric operation can be the same for all users (no
> >> different primers for different IPs, and then the verifiers does not
> >> have to verify that a particular p is actually a pseudo-prime
> >> suitable
> >> for P.H. ) and the public exponent can be just 3.
> >>
> >> >
> >> >> Two protocols can be performed to prove local possession:
> >> >> 1. (prover and verifier pay a small cost) The verifier sends a
> >> seed to
> >> >> derive some n random indexes, and the prover must respond with
> >> the hash
> >> >> of the decrypted blocks within a certain time bound. Suppose that
> >> >> decryption of n blocks take 100 msec (+-100 msec of network
> >> jitter).
> >> >> Then an attacker must have a computer 50 faster to be able to
> >> >> consistently cheat. The last 50 blocks should not be part of the
> >> list to
> >> >> allow nodes to catch-up and encrypt the blocks in background.
> >> >>
> >> >
> >> > Can you clarify, the prover is hashing random blocks of
> >> *decrypted*,
> >> > as-in raw, blockchain data? What does this prove other than,
> >> perhaps,
> >> > fast random IO of the blockchain? (which is useful in its own
> >> right,
> >> > e.g. as a way to ensure only full-node IO-bound mining if baked
> >> into
> >> > the PoW)
> >> >
> >> > How is the verifier validating the response without possession of
> >> the
> >> > full blockchain?
> >>
> >> You're right, It is incorrect. Not the decrypted blocks must be
> >> sent,
> >> but the encrypted blocks. There correct protocol is this:
> >>
> >> 1. (prover and verifier pay a small cost) The verifier sends a seed
> >> to
> >> derive some n random indexes, and the prover must respond with the
> >> the
> >> encrypted blocks within a certain time bound. The verifier decrypts
> >> those blocks to check if they are part of the block-chain.
> >>
> >> But then there is this improvement which allows the verifier do
> >> detect
> >> non full-nodes with much less computation:
> >>
> >> 3. (prover pays a small cost, verifier smaller cost) The verifier
> >> asks
> >> the prover to send a Merkle tree root of hashes of encrypted blocks
> >> with
> >> N indexes selected by a psudo-random function seeded by a challenge
> >> value, where each encrypted-block is previously prefixed with the
> >> seed
> >> before being hashed (e.g. N=100). The verifier receives the Markle
> >> Root
> >> and performs a statistical test on the received information. From
> >> the N
> >> hashes blocks, it chooses M < N (e.g. M = 20), and asks the proved
> >> for
> >> the blocks at these indexes. The prover sends the blocks, the
> >> verifier
> >> validates the blocks by decrypting them and also verifies that the
> >> Merkle tree was well constructed for those block nodes. This proves
> >> with
> >> high probability that the Merkle tree was built on-the-fly and
> >> specifically for this challenge-response protocol.
> >>
> >> > I also wonder about the effect of spinning disk versus SSD. Seek
> >> time
> >> > for 1,000 random reads is either nearly zero or dominating
> >> depending
> >> > on the two modes. I wonder if a sequential read from a random
> >> index is
> >> > a possible trade-off,; it doesn't prove possession of the whole
> >> chain
> >> > nearly as well, but at least iowait converges significantly. Then
> >> > again, that presupposes a specific ordering on disk which might
> >> not
> >> > exist. In X years it will all be solid-state, so eventually it's
> >> moot.
> >> >
> >> Good idea.
> >>
> >> Also we don't need that every node implements the protocol, but only
> >> nodes that want to prove full-node-ness, such as the ones which want
> >> to
> >> receive bitnodes subsidy.
> >
> >
> >
> > ------------------------------------------------------------------------------
> > Dive into the World of Parallel Programming The Go Parallel Website,
> > sponsored
> > by Intel and developed in partnership with Slashdot Media, is your
> > hub for all
> > things parallel software development, from weekly thought leadership
> > blogs to
> > news, videos, case studies, tutorials and more. Take a look and join
> > the
> > conversation now. http://goparallel.sourceforge.net/
> > _______________________________________________
> > Bitcoin-development mailing list
> > Bitcoin-development at lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming The Go Parallel Website, sponsored
> by Intel and developed in partnership with Slashdot Media, is your hub for all
> things parallel software development, from weekly thought leadership blogs to
> news, videos, case studies, tutorials and more. Take a look and join the
> conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Matt Whitlock [ARCHIVE] /
npub17q…upwet
2023-06-07 15:32:02
in reply to nevent1q…cdry
Author Public Key
npub17qxssk9sj2r7jswvh3y32e7vwz7mcckhz33gk9nurdmw0lhsfkgswupwetPublished at
2023-06-07 15:32:02Event JSON
{
"id": "3d92deb7ffc8fcd220382edf032087c3741283e5d82d836c2c92eca95c313525",
"pubkey": "f00d0858b09287e941ccbc491567cc70bdbc62d714628b167c1b76e7fef04d91",
"created_at": 1686151922,
"kind": 1,
"tags": [
[
"e",
"aec2e2b18209ddcfa5d1a18863a1af4d14b80da9d7f8b7d06dfabe62f3ba4546",
"",
"root"
],
[
"e",
"d3883f369e2fba722abdb84dd6edaf3234e7ca3d031603566c40cf00d4947e0f",
"",
"reply"
],
[
"p",
"5ea1cbeab9d50021496bba53fd43b1c7501d58bc84cd506595942424f8dc69c3"
]
],
"content": "📅 Original date posted:2015-03-27\n📝 Original message:I agree that someone could do this, but why is that a problem? Isn't the goal of this exercise to ensure more full nodes on the network? In order to be able to answer the challenges, an entity would need to be running a full node somewhere. Thus, they have contributed at least one additional full node to the network. I could certainly see a case for a company to host hundreds of lightweight (e.g., EC2) servers all backed by a single copy of the block chain. Why force every single machine to have its own copy? All you really need to require is that each agency/participant have its own copy.\n\n\nOn Friday, 27 March 2015, at 2:32 pm, Robert McKay wrote:\n\u003e Basically the problem with that is that someone could setup a single \n\u003e full node that has the blockchain and can answer those challenges and \n\u003e then a bunch of other non-full nodes that just proxy any such challenges \n\u003e to the single full node.\n\u003e \n\u003e Rob\n\u003e \n\u003e On 2015-03-26 23:04, Matt Whitlock wrote:\n\u003e \u003e Maybe I'm overlooking something, but I've been watching this thread\n\u003e \u003e with increasing skepticism at the complexity of the offered solution.\n\u003e \u003e I don't understand why it needs to be so complex. I'd like to offer \n\u003e \u003e an\n\u003e \u003e alternative for your consideration...\n\u003e \u003e\n\u003e \u003e Challenge:\n\u003e \u003e \"Send me: SHA256(SHA256(concatenation of N pseudo-randomly selected\n\u003e \u003e bytes from the block chain)).\"\n\u003e \u003e\n\u003e \u003e Choose N such that it would be infeasible for the responding node to\n\u003e \u003e fetch all of the needed blocks in a short amount of time. In other\n\u003e \u003e words, assume that a node can seek to a given byte in a block stored\n\u003e \u003e on local disk much faster than it can download the entire block from \n\u003e \u003e a\n\u003e \u003e remote peer. This is almost certainly a safe assumption.\n\u003e \u003e\n\u003e \u003e For example, choose N = 1024. Then the proving node needs to perform\n\u003e \u003e 1024 random reads from local disk. On spinning media, this is likely\n\u003e \u003e to take somewhere on the order of 15 seconds. Assuming blocks are\n\u003e \u003e averaging 500 KiB each, then 1024 blocks would comprise 500 MiB of\n\u003e \u003e data. Can 500 MiB be downloaded in 15 seconds? This data transfer \n\u003e \u003e rate\n\u003e \u003e is 280 Mbps. Almost certainly not possible. And if it is, just\n\u003e \u003e increase N. The challenge also becomes more difficult as average \n\u003e \u003e block\n\u003e \u003e size increases.\n\u003e \u003e\n\u003e \u003e This challenge-response protocol relies on the lack of a \"partial\n\u003e \u003e getdata\" command in the Bitcoin protocol: a node cannot ask for only\n\u003e \u003e part of a block; it must ask for an entire block. Furthermore, nodes\n\u003e \u003e could ban other nodes for making too many random requests for blocks.\n\u003e \u003e\n\u003e \u003e\n\u003e \u003e On Thursday, 26 March 2015, at 7:09 pm, Sergio Lerner wrote:\n\u003e \u003e\u003e\n\u003e \u003e\u003e \u003e If I understand correctly, transforming raw blocks to keyed blocks\n\u003e \u003e\u003e \u003e takes 512x longer than transforming keyed blocks back to raw. The \n\u003e \u003e\u003e key\n\u003e \u003e\u003e \u003e is public, like the IP, or some other value which perhaps changes \n\u003e \u003e\u003e less\n\u003e \u003e\u003e \u003e frequently.\n\u003e \u003e\u003e \u003e\n\u003e \u003e\u003e Yes. I was thinking that the IP could be part of a first layer of\n\u003e \u003e\u003e encryption done to the blockchain data prior to the asymetric \n\u003e \u003e\u003e operation.\n\u003e \u003e\u003e That way the asymmetric operation can be the same for all users (no\n\u003e \u003e\u003e different primers for different IPs, and then the verifiers does not\n\u003e \u003e\u003e have to verify that a particular p is actually a pseudo-prime \n\u003e \u003e\u003e suitable\n\u003e \u003e\u003e for P.H. ) and the public exponent can be just 3.\n\u003e \u003e\u003e\n\u003e \u003e\u003e \u003e\n\u003e \u003e\u003e \u003e\u003e Two protocols can be performed to prove local possession:\n\u003e \u003e\u003e \u003e\u003e 1. (prover and verifier pay a small cost) The verifier sends a \n\u003e \u003e\u003e seed to\n\u003e \u003e\u003e \u003e\u003e derive some n random indexes, and the prover must respond with \n\u003e \u003e\u003e the hash\n\u003e \u003e\u003e \u003e\u003e of the decrypted blocks within a certain time bound. Suppose that\n\u003e \u003e\u003e \u003e\u003e decryption of n blocks take 100 msec (+-100 msec of network \n\u003e \u003e\u003e jitter).\n\u003e \u003e\u003e \u003e\u003e Then an attacker must have a computer 50 faster to be able to\n\u003e \u003e\u003e \u003e\u003e consistently cheat. The last 50 blocks should not be part of the \n\u003e \u003e\u003e list to\n\u003e \u003e\u003e \u003e\u003e allow nodes to catch-up and encrypt the blocks in background.\n\u003e \u003e\u003e \u003e\u003e\n\u003e \u003e\u003e \u003e\n\u003e \u003e\u003e \u003e Can you clarify, the prover is hashing random blocks of \n\u003e \u003e\u003e *decrypted*,\n\u003e \u003e\u003e \u003e as-in raw, blockchain data? What does this prove other than, \n\u003e \u003e\u003e perhaps,\n\u003e \u003e\u003e \u003e fast random IO of the blockchain? (which is useful in its own \n\u003e \u003e\u003e right,\n\u003e \u003e\u003e \u003e e.g. as a way to ensure only full-node IO-bound mining if baked \n\u003e \u003e\u003e into\n\u003e \u003e\u003e \u003e the PoW)\n\u003e \u003e\u003e \u003e\n\u003e \u003e\u003e \u003e How is the verifier validating the response without possession of \n\u003e \u003e\u003e the\n\u003e \u003e\u003e \u003e full blockchain?\n\u003e \u003e\u003e\n\u003e \u003e\u003e You're right, It is incorrect. Not the decrypted blocks must be \n\u003e \u003e\u003e sent,\n\u003e \u003e\u003e but the encrypted blocks. There correct protocol is this:\n\u003e \u003e\u003e\n\u003e \u003e\u003e 1. (prover and verifier pay a small cost) The verifier sends a seed \n\u003e \u003e\u003e to\n\u003e \u003e\u003e derive some n random indexes, and the prover must respond with the \n\u003e \u003e\u003e the\n\u003e \u003e\u003e encrypted blocks within a certain time bound. The verifier decrypts\n\u003e \u003e\u003e those blocks to check if they are part of the block-chain.\n\u003e \u003e\u003e\n\u003e \u003e\u003e But then there is this improvement which allows the verifier do \n\u003e \u003e\u003e detect\n\u003e \u003e\u003e non full-nodes with much less computation:\n\u003e \u003e\u003e\n\u003e \u003e\u003e 3. (prover pays a small cost, verifier smaller cost) The verifier \n\u003e \u003e\u003e asks\n\u003e \u003e\u003e the prover to send a Merkle tree root of hashes of encrypted blocks \n\u003e \u003e\u003e with\n\u003e \u003e\u003e N indexes selected by a psudo-random function seeded by a challenge\n\u003e \u003e\u003e value, where each encrypted-block is previously prefixed with the \n\u003e \u003e\u003e seed\n\u003e \u003e\u003e before being hashed (e.g. N=100). The verifier receives the Markle \n\u003e \u003e\u003e Root\n\u003e \u003e\u003e and performs a statistical test on the received information. From \n\u003e \u003e\u003e the N\n\u003e \u003e\u003e hashes blocks, it chooses M \u003c N (e.g. M = 20), and asks the proved \n\u003e \u003e\u003e for\n\u003e \u003e\u003e the blocks at these indexes. The prover sends the blocks, the \n\u003e \u003e\u003e verifier\n\u003e \u003e\u003e validates the blocks by decrypting them and also verifies that the\n\u003e \u003e\u003e Merkle tree was well constructed for those block nodes. This proves \n\u003e \u003e\u003e with\n\u003e \u003e\u003e high probability that the Merkle tree was built on-the-fly and\n\u003e \u003e\u003e specifically for this challenge-response protocol.\n\u003e \u003e\u003e\n\u003e \u003e\u003e \u003e I also wonder about the effect of spinning disk versus SSD. Seek \n\u003e \u003e\u003e time\n\u003e \u003e\u003e \u003e for 1,000 random reads is either nearly zero or dominating \n\u003e \u003e\u003e depending\n\u003e \u003e\u003e \u003e on the two modes. I wonder if a sequential read from a random \n\u003e \u003e\u003e index is\n\u003e \u003e\u003e \u003e a possible trade-off,; it doesn't prove possession of the whole \n\u003e \u003e\u003e chain\n\u003e \u003e\u003e \u003e nearly as well, but at least iowait converges significantly. Then\n\u003e \u003e\u003e \u003e again, that presupposes a specific ordering on disk which might \n\u003e \u003e\u003e not\n\u003e \u003e\u003e \u003e exist. In X years it will all be solid-state, so eventually it's \n\u003e \u003e\u003e moot.\n\u003e \u003e\u003e \u003e\n\u003e \u003e\u003e Good idea.\n\u003e \u003e\u003e\n\u003e \u003e\u003e Also we don't need that every node implements the protocol, but only\n\u003e \u003e\u003e nodes that want to prove full-node-ness, such as the ones which want \n\u003e \u003e\u003e to\n\u003e \u003e\u003e receive bitnodes subsidy.\n\u003e \u003e\n\u003e \u003e\n\u003e \u003e \n\u003e \u003e ------------------------------------------------------------------------------\n\u003e \u003e Dive into the World of Parallel Programming The Go Parallel Website,\n\u003e \u003e sponsored\n\u003e \u003e by Intel and developed in partnership with Slashdot Media, is your\n\u003e \u003e hub for all\n\u003e \u003e things parallel software development, from weekly thought leadership \n\u003e \u003e blogs to\n\u003e \u003e news, videos, case studies, tutorials and more. Take a look and join \n\u003e \u003e the\n\u003e \u003e conversation now. http://goparallel.sourceforge.net/\n\u003e \u003e _______________________________________________\n\u003e \u003e Bitcoin-development mailing list\n\u003e \u003e Bitcoin-development at lists.sourceforge.net\n\u003e \u003e https://lists.sourceforge.net/lists/listinfo/bitcoin-development\n\u003e \n\u003e \n\u003e ------------------------------------------------------------------------------\n\u003e Dive into the World of Parallel Programming The Go Parallel Website, sponsored\n\u003e by Intel and developed in partnership with Slashdot Media, is your hub for all\n\u003e things parallel software development, from weekly thought leadership blogs to\n\u003e news, videos, case studies, tutorials and more. Take a look and join the \n\u003e conversation now. http://goparallel.sourceforge.net/\n\u003e _______________________________________________\n\u003e Bitcoin-development mailing list\n\u003e Bitcoin-development at lists.sourceforge.net\n\u003e https://lists.sourceforge.net/lists/listinfo/bitcoin-development",
"sig": "08a668e74e34b87c47966697486dfe166cf9cc19c4a601266e71331bd024d4c7eb04743d84ff32abb1c96af9d5652191ebe68815c20e5283d347aa86bc7c508d"
}