[libre-riscv-dev] web-of-trust for code reviews to manage trusting dependencies

Luke Kenneth Casson Leighton lkcl at lkcl.net
Wed Aug 28 19:20:25 BST 2019

On Wed, Aug 28, 2019 at 5:44 PM Jacob Lifshay <programmerjake at gmail.com> wrote:
> crev's main dev responded on Matrix.

hi dpc, glad you're entertained by what i wrote, off-the-cuff, no
filters at all, with a complete misunderstanding of the context for
which crev has been designed :)

what you are doing is tackling a particularly fascinating area of research.

where i said that there's no links to security papers or comparative
analysis, that's what's important for a code *distribution* system to
have, because it's [potentially] being used to "blindly" distribute
"packages" in the order of 10^5 to 10^6 downloads a month, with the
end-users doing *absolutely no manual verification whatsoever*.

that is *radically* different from what crev is designed for, which is
*specifically* to aid and assist a *developer* - not an end-user - in
a *manual* review process as to whether code may be "trusted" or not.

for that, you should definitely investigate Advogato and look up
"Trust Metrics".  i reimplemented Advogato's main algorithm in python,
and it can be found here: https://sourceforge.net/projects/pymmetry/

the important thing about pymmetry is that unlike Raph's original
implementation (Ford-Fulkersson) the max-flow graph algorithm in
pymmetry is *breadth* first, *not* depth first.  this allows the
execution to stop at the point where it is no longer needed, whereas
with a "depth" first algorithm, the entire network (entire trust
graph) *has* to be downloaded prior to evaluation.

that makes the graph a high-value DDOS target.  whoops.

should crev take off in a big way, to the point where even the
"legitimate" reviews are coming in at a rate of a hundred thousand a
month (and are permanently cumulative), or if crev takes off and gets
subjected to the same type of multi-million-spammer DDOS attack that
GPG's "keyring" servers were polluted with a couple of months back,
you *will* need an algorithm that can chop off spammers at the knees.

and also one that can stop at the point where the evidence is clearly
overwhelmingly "positive" as far as the developer's needs are

by setting the developer as the "centre" - the "seed" - of the trust
metric pymmetry graph, their friends become the 2nd level of the
max-flow algorithm, their friends-of-friends become the 3rd, and where
there are degrees of separation that overlap, a max-flow algorithm
*automatically* notices the redundancy, and takes care of it.

by using "weights" (gas "flow capacity" pipes) between each level,
progressively dropping each time, very quickly the capacity will be
saturated to the point where there is no need to include any extra
"levels" (another degree of separation): the answer is already clear,
and the algorithm can terminate early.

this *specifically* allows DDOS spammers to be excluded from the
network, particularly if the "queries" [requests for an additional
"level" in the degree of separation, starting from a speciific person]
are performed via, e.g., a global peer-to-peer DHT.  only if someone
was stupid enough to "trust" one of the spammers would the spammers'
certificates even *enter* a DHT network, and "negative Certs"
(blacklists) can easily fix that.

anyway.  lots to think about.  fascinating area.


More information about the libre-riscv-dev mailing list