I admit I've given more attention on CPIR (because I think the sybil problem makes the IT assumptions not that useful), so I can't off the top of my head give you a concrete construction for a toy IT PIR that has good communications efficiency.

The thing I think you are probably missing most doesn't require you understand the PIR at that level of detail:

What PIR tools really give you is just an "oblivious array":  An array of (e.g.) 100 byte entries of known size, and the PIR lets the client query any entry without the server(s) learning which entry the client queried.

From this alone you can construct your private "database": E.g. to do a prefix match you might require that the array be sorted and have the client perform a bisection search on the array using log(N) oblivious queries.  Any database operation you can imagine can be constructed this way, but obviously they'll only be efficiency if they don't access to many cells.

While I don't recall what the concrete construction looks like for IT PIR,  I can give a simple-ish (or at least from memory) example of a how a basic CPIR protocol is constructed using the the Goldwasser-Micali (GM) cryptosystem:

In this cryptosystem the public key is an RSA number (the product of two large primes).  The main property of the GM cryptosystem is that if you know the private key (the factorization) you know the order of the multiplicative group mod P. And if you know the order, you can easily tell if a number is a quadratic residue (if it has a sqrt mod P) by computing the jacobi symbol which can be done with an exponentiation ladder or by using the extended euclidean algorithm. Under the assumption of the cryptosystem if you don't know the order you can't tell if a number is a QR or not.

GM is useful because if A=B*C (mod P)  then QR(A) = QR(B) xor QR(C).  So essentially it is a cryptosystem where I can give you encrypted values and you can apply an arbitrary set of XORs on them (and xors on the results of earlier xors) and also xor them with 1 (by squaring them) and then I can decrypt the result of your computation by using my private key to test the QR-ness of the result.

For discussion, we'll imagine that our private database is an array of 2^16 bits which you have and I want to query some particular bit without telling you which.  You arrange the database into a 256x256 square array, and the bit I want to query is at position [i,j].    I pick 256 random numbers mod P such that all of them are quadratic residues, except for the one at position j, Lets call them:  q_0 to q_255

I send you my public key P and these 256 q values. For each row you make a copy of the q values and square (mod P) the value when the bit in that cell is 0, then compute the product (mod P) of all the processed values for that row.  At the end you have 256 values-- one for each row, you send them to me.

reply_row = product(data_(row,col) ? q_col : q_col^2)

I ignore all but the i-th one, and then because I know the private key I can test if the value in question is a 0 by checking if it's a QR or not (because of the above mentioned: QR(A) = QR(B) xor QR(C)).

Now this version is inefficient in that you send me back 256 values, but I only pay attention to the i-th one.   This inefficiency can be fixed by applying the scheme recursively (using the "reply" products as the table being queried).

Extending the scheme to more than 1-bit-per-cell is simple:  You still send the same query, but apply it in parallel to as 1-bit-tables as your message has bits.

Main downside is doing all this mod P work (where P has to be big enough to make it unfactorable!) is slow, and also the queries are size sqrt(table_cells) (with the recursion the response can be as small as you like).

There are multiple kinds of PIR.

Computational PIR is based on asymmetric cryptography. With CPIR you query one server and it learns nothing about what you're querying. But the downside is that it takes a lot of CPU time.

Information theoretic PIR is based on threshold secret sharing. With IT-PIR you query M servers and no one learns anything about your queries so long as N of the M don't collude.  IT PIR is faster, but it's potentially vulnerable to sybil attack (you think you're connecting to N independent parties but they're not really independent).

Percy implements both kinds (and can combine them too)-- and its pages describe the capabilities in great detail.  It might be too technical for some people, --- but that's okay because no one is obligated to give an opinion here if the material is beyond your interest or patience to figure out.

n0nce gave an informal description of a IT-PIR like technique.  The way he described it though doesn't provide much privacy, because his description makes it sound like he's only asking for a couple distractor addresses. I think that's mostly just an artifact of the description.  In IT-PIR every query normally operates on the entire database.

Exactly, and especially no incentive to run PIR version that would be many times more expensive to run.

It's even hard to have the users pay for access-- because without access they can't spend their Bitcoins!  (and plus, most users would not want to pay a fair price when they can get wallet services from someone that will spy on them but lie about it for free)

Don't assume that it's black and white-- that someone is interested or not interested.  Things come in shades. People can be interested without totally falling down the bitcoin rabbit hole and immediately learning enough to securely manage your gift.

I was assuming your hope is that they hold onto them, if you just think they should sell them-- then the thing to do is just walk them through creating an exchange account at an exchange you think they should trust then moving the coins directly to their address there.

As far as trusting you-- well trusting the person giving them a gift over that gift is a bit different than anyone else.  I doubt it encourages anyone to trust in situations where it isn't appropriate, quite the opposite: I think giving people a private key is a great opportunity to discuss and educate about security.

I think it's best to give coins to non-bitcoiners by moving them to a new securely created private keys, store the key on some physical medium, and give it to them with instructions on safe keeping. (also making it clear that its not secure unless they sweep it).

Because it's a gift they're likely not too worried about you robbing them, and so they'll likely leave it alone until they understand Bitcoin better.  This is good because they're also likely to lose their keys or get their online systems hacked.  If they lose the key you gave them you could retain a backup (offline, lest your own hack causes its loss!) and give it back to them again.

This isn't hard fundamentally, -- the rocket science programming has already been done: http://percy.sourceforge.net/

Just make a database of transactions with spv proofs.  And also make another databases of addresses to tx-database-indexes.  Maybe staple a cleartext index of the address database to it to reduce the number of bisections needed.  Feed that to percy++.

Bitcoin-core has rpcs that will import txn with their proofs into the wallet-- created partially with this usage in mind!

But the problem is that the computational cost the server is just astronomical.  Under most reasonable cost metrics it's "cheaper" to just send the client the whole database.  This only becomes reasonable if you're assuming extremely expensive wireless data rates or what not, and then you still have the problem of who is going to pay for the server.

Unfortunately, already pretty much the only incentive for people to run electrum servers is to spy on the clients, and this eliminates that "benefit".

Bitcoin nodes do not store merkle trees, so there is nothing to save.

The particular layout you suggest has poor locality.  E.g. the first node above 0 is at 8 instead of being as soon as it could possibly be, at 2. Even in ram access locality matters. (at least to the extent that performance matters at all)

It also only works for trees which are fully populated at every level-- ones where the size is a power of two-- or otherwise it requires padding up to the next power of two size which wastes a *lot* of space.

P=64231 N=64633 a=0 b=3  G={0x01,0x02}

78 bits is far too small for a secure private key.  You can see in threads here that people have successfully cracked keys quite a bit larger than 78 bits.

So unless you're intentionally creating an insecure key for puzzle purposes, you probably don't want to do this.

To be analogous to secp256k1, your prime should be congruent to 3 mod 4, should have a primitive cube root of unity, and the generated group should be prime.

The curve created by a=0 b=11 over field P=2^32-116325 has these properties. N is 2^32-4443.

There are many such choices that work.  I chose the option with the largest group size subject to the restriction that the order was still under 2^32, that the twist had cofactor of 4 or less, and that the embedding degree was 'large' (in this case almost 2^30, though there are somewhat smaller groups where the embedding degree is close to 2^32). I chose the smallest b among the isomorphic alternatives.

For a generator,  you could use G = {0x02, 0x20c2c3af}  (x=0x01 isn't on the curve). All points on the curve are equally good as a generator.


results=[]
for x in [xf for xf in range(2^32,2^32-300000,-1) if xf%4==3 and Integer(xf).is_prime() and FiniteField(xf)(1).nth_root(3)!=1]:
  for b in range(1,15):
    order=EllipticCurve([FiniteField(x)(0), FiniteField(x)(b)]).order()
    if order<2^32 and order.is_prime()==True:
      ordert=EllipticCurve([FiniteField(x)(0), FiniteField(x)(-b)]).order()
      ordertp=factor(ordert)[-1][0]
      if ordert/ordertp<=4:
        results.append((order,RR(log(FiniteField(order)(x).multiplicative_order(),2)),ordert,-x,-b))
sorted(results)

Finite fields exist far beyond ECC.

For key agreement the passive observer sees aG sent by alice, and bG sent by bob.  The observer cannot compute abG -- their shared secret.  If they could multiply points they could multiply what they saw aG and bG and get the shared secret and read their traffic.

Bitcoin works without DNS seeders too, set dnsseed=0  ... if you do this on the initial run it might take a couple hours to get connected to the network.

If you wanted to be silly you could also implement dividing a point by a scalar more directly.

One efficient way of computing a modular inverse is to use the extended GCD algorithm. A GCD starts with a vector of the number to be inverted and the modulus and applies a series of primitive transformations to the numbers which preserve their GCD and reduce their magnitude, until eventually you end up with the [1,0] vector. An extended GCD has an additional vector of numbers mod n which runs along side it and which it applies the same primitive transformations to, which ends up being the modular inverse at the end.  If the GCD you use is a binary GCD then all the transformation operations you perform are simple operations you can perform on curve points. So if you slap ecc points in place of this this secondary vector, the algorithm will divide a curve point by a number directly.

However, given that scalar operations are so much faster than curve operations, this would be slower than computing the inverse and then using a fast scalar/point multiply algorithm.  But I think it could be fairly said to be an algorithm for directly dividing a curve point by a scalar, although a rather silly one.

You cannot.  As garlonicon noted that it would break a lot of ECC protocols if you could.  Probably the simplest example is that in ECDH key agreement: Alice has private key a and sends aG and Bob has private key b and sends bG, and their joint shared secret is H(abG) which they can both compute by multiplying what they received with their own private key and hashing it.  But a passive observer can't multiply the two points, and so they can't compute the shared secret.

In pairing cryptography which is built with specialized elliptic curves that have a precisely engineered weakness you effectively gain an ability to multiply curve points, but only once: the result is in a different group.  But this extra ability alone lets you create all kinds of fancy cryptographic protocols that you can't create with plain ECC (or only exist in interactive form for plain ECC).

One thing that can be done if I know three points and their discrete logs: A=aG, B=bG, C=abG, I can write a proof that convinces you that C is the product of A and B (and that I know their discrete logs), without revealing to you anything else.  But you can't perform the computation yourself.

Sure!  I mean one of the main features of taproot could be substantially implemented with just using OP_CAT. https://blockstream.com/2015/08/24/en-treesignatures/   (but it's much more cpu/space/fee efficient to implement it directly).

Using string operators on and either a verify-signature-of-data-on-stack or some improved arithmetic operations lets you implement vaults: https://blockstream.com/2016/11/02/en-covenants-in-elements-alpha/

Using substr (or op_cat) you can implement a single show signature--  a output that requires a signature where if someone signs for it more than once, they'll leak the private key.  (You require that the signature use a specific R value). You can use this to make transactions with a double spend penalty.

I think arguably of all the disabled opcodes the "string" ones are really the most useful.

There absolutely are use cases!  Unfortunately the original construction could be abused to cause nodes to require petabytes of ram ...  Fixing that requires imposing additional restrictions, and without planning for specific uses it can be hard to be confident that the restrictions don't break them.

... and demand for fancy use cases seems pretty limited-- which doesn't motivate people to do the design and validation work needed to reintroduce the operations.

I haven't tried anything as old as 0.1.0 but you can take 0.3.2-ish (one of the last before satoshi left) and sync as far as 2013 but then gets stuck because of blocks >500KB exceeding the bdb locks limit.  To do so you need to work around some p2p incompatiblities, and not let it see any new blocks while its syncing because the sync process effectively starts over when it gets sent a new block.

Anything 0.8 from 2013 or newer doesn't have the BDB flaws and can sync all the way to the tip but there are enough bugs exposed by the more resource heavy chain that it can be a bit hard-- so you still need to protect it from seeing reorgs or newly added blocks while it's syncing.

I think it's better than checkmultisig with an extra field that specifies which pubkeys are in use-- because it's also easily adaptable to weighed thresholds.

I'm sure there are many ways to attack it-- but because it iss obscure, worthless, and you can't even deposit/withdraw it pretty much anywhere-- why would anyone bother?  The low hashrate alone makes it completely insecure.  The conmen promoters make it into a joke.

It's like asking if anyone has haxored Craig Wright's speak & spell, I'm sure people could but... why would anyone bother?

FWIW my friend running a BSV node to try to get some real facts about these reorgs had several gaps in his monitoring coverage when the BSV node software attempted to use more than 40 GB of ram as part of a reorg...  Probably some of the issues they had with these reorgs were due to miners crashing due to running out of memory while attempting to reorg.

And this was without any spamming beyond the baseline spam performed by Ayre and his companies to try to fake there being interest and usage of BSV.